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"),
343#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
363 OS <<
"(ptrto" << OpS <<
" " << *
Op->getType() <<
" " << *
Op <<
" to "
370 OS <<
"(trunc " << *
Op->getType() <<
" " << *
Op <<
" to "
377 OS <<
"(zext " << *
Op->getType() <<
" " << *
Op <<
" to "
384 OS <<
"(sext " << *
Op->getType() <<
" " << *
Op <<
" to "
413 const char *OpStr =
nullptr;
426 OpStr =
" umin_seq ";
450 OS <<
"(" << *UDiv->
getLHS() <<
" /u " << *UDiv->
getRHS() <<
")";
457 OS <<
"***COULDNOTCOMPUTE***";
535 if (!
Mul)
return false;
539 if (!SC)
return false;
557 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
559 UniqueSCEVs.InsertNode(S, IP);
574 ConstantInt::get(ITy, V, isSigned,
true));
582 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
585 UniqueSCEVs.InsertNode(S, IP);
606 "Must be a non-bit-width-changing pointer-to-integer cast!");
613 "Must be a non-bit-width-changing pointer-to-integer cast!");
625 "Cannot truncate non-integer value!");
632 "Cannot zero extend non-integer value!");
639 "Cannot sign extend non-integer value!");
644 SE->forgetMemoizedResults({
this});
647 SE->UniqueSCEVs.RemoveNode(
this);
653void SCEVUnknown::allUsesReplacedWith(
Value *New) {
655 SE->forgetMemoizedResults({
this});
658 SE->UniqueSCEVs.RemoveNode(
this);
680 if (LIsPointer != RIsPointer)
681 return (
int)LIsPointer - (int)RIsPointer;
686 return (
int)LID - (int)RID;
691 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
692 return (
int)LArgNo - (int)RArgNo;
698 if (
auto L = LGV->getLinkage() - RGV->getLinkage())
701 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
702 auto LT = GV->getLinkage();
709 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
710 return LGV->getName().compare(RGV->getName());
721 if (LParent != RParent) {
724 if (LDepth != RDepth)
725 return (
int)LDepth - (int)RDepth;
729 unsigned LNumOps = LInst->getNumOperands(),
730 RNumOps = RInst->getNumOperands();
731 if (LNumOps != RNumOps)
732 return (
int)LNumOps - (int)RNumOps;
734 for (
unsigned Idx :
seq(LNumOps)) {
736 RInst->getOperand(Idx),
Depth + 1);
750static std::optional<int>
760 return (
int)LType - (int)RType;
785 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
786 if (LBitWidth != RBitWidth)
787 return (
int)LBitWidth - (int)RBitWidth;
788 return LA.
ult(
RA) ? -1 : 1;
794 return LTy->getBitWidth() - RTy->getBitWidth();
805 if (LLoop != RLoop) {
807 assert(LHead != RHead &&
"Two loops share the same header?");
811 "No dominance between recurrences used by one SCEV?");
835 unsigned LNumOps = LOps.
size(), RNumOps = ROps.
size();
836 if (LNumOps != RNumOps)
837 return (
int)LNumOps - (int)RNumOps;
839 for (
unsigned i = 0; i != LNumOps; ++i) {
865 if (
Ops.size() < 2)
return;
870 return Complexity && *Complexity < 0;
872 if (
Ops.size() == 2) {
876 if (IsLessComplex(
RHS,
LHS))
889 for (
unsigned i = 0, e =
Ops.size(); i != e-2; ++i) {
895 for (
unsigned j = i+1; j != e &&
Ops[j]->getSCEVType() == Complexity; ++j) {
900 if (i == e-2)
return;
922template <
typename FoldT,
typename IsIdentityT,
typename IsAbsorberT>
926 IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) {
928 for (
unsigned Idx = 0; Idx <
Ops.size();) {
936 Ops.erase(
Ops.begin() + Idx);
943 assert(Folded &&
"Must have folded value");
947 if (Folded && IsAbsorber(Folded->
getAPInt()))
951 if (Folded && !IsIdentity(Folded->
getAPInt()))
952 Ops.insert(
Ops.begin(), Folded);
954 return Ops.size() == 1 ?
Ops[0] :
nullptr;
1029 APInt OddFactorial(W, 1);
1031 for (
unsigned i = 3; i <= K; ++i) {
1034 OddFactorial *= (i >> TwoFactors);
1038 unsigned CalculationBits = W +
T;
1052 for (
unsigned i = 1; i != K; ++i) {
1085 for (
unsigned i = 1, e =
Operands.size(); i != e; ++i) {
1114 ConversionFn CreatePtrCast;
1118 ConversionFn CreatePtrCast)
1119 : Base(
SE), TargetTy(TargetTy), CreatePtrCast(
std::
move(CreatePtrCast)) {}
1122 Type *TargetTy, ConversionFn CreatePtrCast) {
1124 return Rewriter.visit(Scev);
1160 "Should only reach pointer-typed SCEVUnknown's.");
1165 return SE.getZero(TargetTy);
1166 return CreatePtrCast(Expr);
1171 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1190 Op, *
this, IntPtrTy, [
this, IntPtrTy](
const SCEVUnknown *U) {
1195 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1197 SCEV *S =
new (SCEVAllocator)
1199 UniqueSCEVs.InsertNode(S, IP);
1202 return static_cast<const SCEV *
>(S);
1205 "We must have succeeded in sinking the cast, "
1206 "and ending up with an integer-typed expression!");
1211 assert(
Op->getType()->isPointerTy() &&
"Op must be a pointer");
1215 if (DL.hasUnstableRepresentation(
Op->getType()))
1218 Type *Ty = DL.getAddressType(
Op->getType());
1229 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1231 SCEV *S =
new (SCEVAllocator)
1233 UniqueSCEVs.InsertNode(S, IP);
1236 return static_cast<const SCEV *
>(S);
1239 "We must have succeeded in sinking the cast, "
1240 "and ending up with an integer-typed expression!");
1245 assert(Ty->isIntegerTy() &&
"Target type must be an integer type!");
1257 "This is not a truncating conversion!");
1259 "This is not a conversion to a SCEVable type!");
1260 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1268 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1290 UniqueSCEVs.InsertNode(S, IP);
1303 unsigned numTruncs = 0;
1304 for (
unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2;
1312 if (numTruncs < 2) {
1322 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
1329 for (
const SCEV *
Op : AddRec->operands())
1344 UniqueSCEVs.InsertNode(S, IP);
1385struct ExtendOpTraitsBase {
1386 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(
const SCEV *,
Type *,
1391template <
typename ExtendOp>
struct ExtendOpTraits {
1407 static const GetExtendExprTy GetExtendExpr;
1409 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1410 ICmpInst::Predicate *Pred,
1411 ScalarEvolution *SE) {
1416const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1423 static const GetExtendExprTy GetExtendExpr;
1425 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1426 ICmpInst::Predicate *Pred,
1427 ScalarEvolution *SE) {
1432const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1444template <
typename ExtendOpTy>
1447 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1448 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1464 for (
auto It = DiffOps.
begin(); It != DiffOps.
end(); ++It)
1477 auto PreStartFlags =
1495 const SCEV *OperandExtendedStart =
1497 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1498 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1510 const SCEV *OverflowLimit =
1511 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1513 if (OverflowLimit &&
1521template <
typename ExtendOpTy>
1525 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1533 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1568template <
typename ExtendOpTy>
1569bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1572 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1582 APInt StartAI = StartC->
getAPInt();
1584 for (
unsigned Delta : {-2, -1, 1, 2}) {
1585 const SCEV *PreStart =
getConstant(StartAI - Delta);
1587 FoldingSetNodeID
ID;
1589 ID.AddPointer(PreStart);
1590 ID.AddPointer(Step);
1594 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
1598 if (PreAR &&
any(PreAR->getNoWrapFlags(WrapType))) {
1601 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1602 DeltaS, &Pred,
this);
1620 const unsigned BitWidth =
C.getBitWidth();
1638 const APInt &ConstantStart,
1657 auto &UserIDs = FoldCacheUser[
I.first->second];
1658 assert(
count(UserIDs,
ID) == 1 &&
"unexpected duplicates in UserIDs");
1659 for (
unsigned I = 0;
I != UserIDs.size(); ++
I)
1660 if (UserIDs[
I] ==
ID) {
1665 I.first->second = S;
1667 FoldCacheUser[S].push_back(
ID);
1673 "This is not an extending conversion!");
1675 "This is not a conversion to a SCEVable type!");
1676 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1680 if (
const SCEV *S = FoldCache.lookup(
ID))
1692 "This is not an extending conversion!");
1694 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1711 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1715 UniqueSCEVs.InsertNode(S, IP);
1725 const SCEV *
X = ST->getOperand();
1739 if (AR->isAffine()) {
1740 const SCEV *Start = AR->getStart();
1741 const SCEV *Step = AR->getStepRecurrence(*
this);
1743 const Loop *L = AR->getLoop();
1747 if (AR->hasNoUnsignedWrap()) {
1768 const SCEV *CastedMaxBECount =
1772 if (MaxBECount == RecastedMaxBECount) {
1782 const SCEV *WideMaxBECount =
1784 const SCEV *OperandExtendedAdd =
1790 if (ZAdd == OperandExtendedAdd) {
1801 OperandExtendedAdd =
1807 if (ZAdd == OperandExtendedAdd) {
1828 !AC.assumptions().empty()) {
1830 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1832 if (AR->hasNoUnsignedWrap()) {
1867 const APInt &
C = SC->getAPInt();
1871 const SCEV *SResidual =
1879 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1904 if (SA->hasNoUnsignedWrap()) {
1925 const SCEV *SResidual =
1936 if (
SM->hasNoUnsignedWrap()) {
1958 const SCEV *TruncRHS;
1995 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
1998 UniqueSCEVs.InsertNode(S, IP);
2007 "This is not an extending conversion!");
2009 "This is not a conversion to a SCEVable type!");
2010 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
2014 if (
const SCEV *S = FoldCache.lookup(
ID))
2026 "This is not an extending conversion!");
2028 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
2050 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2055 UniqueSCEVs.InsertNode(S, IP);
2065 const SCEV *
X = ST->getOperand();
2076 if (SA->hasNoSignedWrap()) {
2098 const SCEV *SResidual =
2111 if (AR->isAffine()) {
2112 const SCEV *Start = AR->getStart();
2113 const SCEV *Step = AR->getStepRecurrence(*
this);
2115 const Loop *L = AR->getLoop();
2119 if (AR->hasNoSignedWrap()) {
2141 const SCEV *CastedMaxBECount =
2145 if (MaxBECount == RecastedMaxBECount) {
2155 const SCEV *WideMaxBECount =
2157 const SCEV *OperandExtendedAdd =
2163 if (SAdd == OperandExtendedAdd) {
2174 OperandExtendedAdd =
2180 if (SAdd == OperandExtendedAdd) {
2200 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2202 if (AR->hasNoSignedWrap()) {
2217 const APInt &
C = SC->getAPInt();
2221 const SCEV *SResidual =
2229 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2257 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
2260 UniqueSCEVs.InsertNode(S, IP);
2287 "This is not an extending conversion!");
2289 "This is not a conversion to a SCEVable type!");
2294 if (SC->getAPInt().isNegative())
2299 const SCEV *NewOp =
T->getOperand();
2318 for (
const SCEV *
Op : AR->operands())
2356 APInt &AccumulatedConstant,
2360 bool Interesting =
false;
2367 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
2369 AccumulatedConstant += Scale *
C->getAPInt();
2374 for (; i !=
Ops.size(); ++i) {
2383 M, NewOps, AccumulatedConstant,
Add->operands(), NewScale, SE);
2389 auto Pair = M.insert({
Key, NewScale});
2393 Pair.first->second += NewScale;
2401 auto Pair = M.insert({
Ops[i], Scale});
2405 Pair.first->second += Scale;
2424 case Instruction::Add:
2427 case Instruction::Sub:
2430 case Instruction::Mul:
2444 const SCEV *
A = (this->*Extension)(
2446 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
2447 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
2455 if (BinOp == Instruction::Mul)
2461 APInt C = RHSC->getAPInt();
2462 unsigned NumBits =
C.getBitWidth();
2463 bool IsSub = (BinOp == Instruction::Sub);
2464 bool IsNegativeConst = (
Signed &&
C.isNegative());
2466 bool OverflowDown = IsSub ^ IsNegativeConst;
2468 if (IsNegativeConst) {
2481 APInt Limit = Min + Magnitude;
2487 APInt Limit = Max - Magnitude;
2492std::optional<SCEV::NoWrapFlags>
2497 return std::nullopt;
2506 bool Deduced =
false;
2508 if (OBO->
getOpcode() != Instruction::Add &&
2511 return std::nullopt;
2520 false, LHS, RHS, CtxI)) {
2527 true, LHS, RHS, CtxI)) {
2534 return std::nullopt;
2544 using namespace std::placeholders;
2551 assert(CanAnalyze &&
"don't call from other places!");
2558 auto IsKnownNonNegative = [&](
SCEVUse U) {
2567 if (SignOrUnsignWrap != SignOrUnsignMask &&
2574 return Instruction::Add;
2576 return Instruction::Mul;
2587 Opcode,
C, OBO::NoSignedWrap);
2595 Opcode,
C, OBO::NoUnsignedWrap);
2605 Ops[0]->isZero() && IsKnownNonNegative(
Ops[1]))
2612 if (UDiv->getOperand(1) ==
Ops[1])
2615 if (UDiv->getOperand(1) ==
Ops[0])
2631 "only nuw or nsw allowed");
2632 assert(!
Ops.empty() &&
"Cannot get empty add!");
2633 if (
Ops.size() == 1)
return Ops[0];
2636 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
2638 "SCEVAddExpr operand types don't match!");
2640 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2641 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2646 [](
const APInt &C1,
const APInt &C2) {
return C1 + C2; },
2647 [](
const APInt &
C) {
return C.isZero(); },
2648 [](
const APInt &
C) {
return false; });
2661 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
2666 if (
Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2667 Add->setNoWrapFlags(ComputeFlags(
Ops));
2675 bool FoundMatch =
false;
2676 for (
unsigned i = 0, e =
Ops.size(); i != e-1; ++i)
2677 if (
Ops[i] ==
Ops[i+1]) {
2689 --i; e -=
Count - 1;
2699 auto FindTruncSrcType = [&]() ->
Type * {
2705 return T->getOperand()->getType();
2707 SCEVUse LastOp =
Mul->getOperand(
Mul->getNumOperands() - 1);
2709 return T->getOperand()->getType();
2713 if (
auto *SrcType = FindTruncSrcType()) {
2720 if (
T->getOperand()->getType() != SrcType) {
2729 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
2732 if (
T->getOperand()->getType() != SrcType) {
2760 if (
Ops.size() == 2) {
2770 auto C2 =
C->getAPInt();
2773 APInt ConstAdd = C1 + C2;
2774 auto AddFlags = AddExpr->getNoWrapFlags();
2815 if (
Ops.size() == 2 &&
2826 if (Idx <
Ops.size()) {
2827 bool DeletedAdd =
false;
2838 Ops.erase(
Ops.begin()+Idx);
2841 CommonFlags =
maskFlags(CommonFlags,
Add->getNoWrapFlags());
2864 struct APIntCompare {
2865 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
2866 return LHS.ult(RHS);
2873 std::map<APInt, SmallVector<SCEVUse, 4>, APIntCompare> MulOpLists;
2874 for (
const SCEV *NewOp : NewOps)
2875 MulOpLists[M.find(NewOp)->second].push_back(NewOp);
2878 if (AccumulatedConstant != 0)
2880 for (
auto &MulOp : MulOpLists) {
2881 if (MulOp.first == 1) {
2883 }
else if (MulOp.first != 0) {
2892 if (
Ops.size() == 1)
2903 for (
unsigned MulOp = 0, e =
Mul->getNumOperands(); MulOp != e; ++MulOp) {
2904 const SCEV *MulOpSCEV =
Mul->getOperand(MulOp);
2907 for (
unsigned AddOp = 0, e =
Ops.size(); AddOp != e; ++AddOp)
2908 if (MulOpSCEV ==
Ops[AddOp]) {
2910 const SCEV *InnerMul =
Mul->getOperand(MulOp == 0);
2911 if (
Mul->getNumOperands() != 2) {
2918 const SCEV *AddOne =
2922 if (
Ops.size() == 2)
return OuterMul;
2924 Ops.erase(
Ops.begin()+AddOp);
2925 Ops.erase(
Ops.begin()+Idx-1);
2927 Ops.erase(
Ops.begin()+Idx);
2928 Ops.erase(
Ops.begin()+AddOp-1);
2930 Ops.push_back(OuterMul);
2935 for (
unsigned OtherMulIdx = Idx+1;
2942 OMulOp != e; ++OMulOp)
2943 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2945 const SCEV *InnerMul1 =
Mul->getOperand(MulOp == 0);
2946 if (
Mul->getNumOperands() != 2) {
2954 OtherMul->
operands().take_front(OMulOp));
2958 const SCEV *InnerMulSum =
2962 if (
Ops.size() == 2)
return OuterMul;
2963 Ops.erase(
Ops.begin()+Idx);
2964 Ops.erase(
Ops.begin()+OtherMulIdx-1);
2965 Ops.push_back(OuterMul);
2985 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
2988 Ops.erase(
Ops.begin()+i);
2993 if (!LIOps.
empty()) {
3018 auto *DefI = getDefiningScopeBound(LIOps);
3020 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
3032 if (
Ops.size() == 1)
return NewRec;
3035 for (
unsigned i = 0;; ++i)
3036 if (
Ops[i] == AddRec) {
3046 for (
unsigned OtherIdx = Idx+1;
3054 "AddRecExprs are not sorted in reverse dominance order?");
3061 if (OtherAddRec->getLoop() == AddRecLoop) {
3062 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
3064 if (i >= AddRecOps.
size()) {
3065 append_range(AddRecOps, OtherAddRec->operands().drop_front(i));
3069 getAddExpr(AddRecOps[i], OtherAddRec->getOperand(i),
3072 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3087 return getOrCreateAddExpr(
Ops, ComputeFlags(
Ops));
3098 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3102 S =
new (SCEVAllocator)
3104 UniqueSCEVs.InsertNode(S, IP);
3115 FoldingSetNodeID
ID;
3117 for (
const SCEV *
Op :
Ops)
3122 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3126 S =
new (SCEVAllocator)
3127 SCEVAddRecExpr(
ID.Intern(SCEVAllocator), O,
Ops.size(), L);
3128 UniqueSCEVs.InsertNode(S, IP);
3130 LoopUsers[
L].push_back(S);
3139 FoldingSetNodeID
ID;
3141 for (
const SCEV *
Op :
Ops)
3145 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(
ID, IP));
3149 S =
new (SCEVAllocator) SCEVMulExpr(
ID.Intern(SCEVAllocator),
3151 UniqueSCEVs.InsertNode(S, IP);
3161 if (j > 1 && k / j != i) Overflow =
true;
3177 if (n == 0 || n == k)
return 1;
3178 if (k > n)
return 0;
3184 for (
uint64_t i = 1; i <= k; ++i) {
3185 r =
umul_ov(r, n-(i-1), Overflow);
3194 struct FindConstantInAddMulChain {
3195 bool FoundConstant =
false;
3197 bool follow(
const SCEV *S) {
3202 bool isDone()
const {
3203 return FoundConstant;
3207 FindConstantInAddMulChain
F;
3209 ST.visitAll(StartExpr);
3210 return F.FoundConstant;
3218 "only nuw or nsw allowed");
3219 assert(!
Ops.empty() &&
"Cannot get empty mul!");
3220 if (
Ops.size() == 1)
return Ops[0];
3222 Type *ETy =
Ops[0]->getType();
3224 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i)
3226 "SCEVMulExpr operand types don't match!");
3231 [](
const APInt &C1,
const APInt &C2) {
return C1 * C2; },
3232 [](
const APInt &
C) {
return C.isOne(); },
3233 [](
const APInt &
C) {
return C.isZero(); });
3244 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3249 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3250 Mul->setNoWrapFlags(ComputeFlags(
Ops));
3255 if (
Ops.size() == 2) {
3263 const SCEV *Op0, *Op1;
3271 if (
Ops[0]->isAllOnesValue()) {
3276 bool AnyFolded =
false;
3277 for (
const SCEV *AddOp :
Add->operands()) {
3297 if (AddRec->hasNoSignedWrap()) {
3304 AddRec->getNoWrapFlags(FlagsMask));
3327 APInt C1V = LHSC->getAPInt();
3337 const SCEV *NewMul =
nullptr;
3341 assert(C1V.
ugt(1) &&
"C1 <= 1 should have been folded earlier");
3356 if (Idx <
Ops.size()) {
3357 bool DeletedMul =
false;
3363 Ops.erase(
Ops.begin()+Idx);
3387 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i)
3390 Ops.erase(
Ops.begin()+i);
3395 if (!LIOps.
empty()) {
3408 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
3424 if (
Ops.size() == 1)
return NewRec;
3427 for (
unsigned i = 0;; ++i)
3428 if (
Ops[i] == AddRec) {
3449 bool OpsModified =
false;
3450 for (
unsigned OtherIdx = Idx+1;
3464 bool Overflow =
false;
3471 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
3475 z < ze && !Overflow; ++z) {
3478 if (LargerThan64Bits)
3479 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3481 Coeff = Coeff1*Coeff2;
3496 if (
Ops.size() == 2)
return NewAddRec;
3497 Ops[Idx] = NewAddRec;
3498 Ops.erase(
Ops.begin() + OtherIdx); --OtherIdx;
3514 return getOrCreateMulExpr(
Ops, ComputeFlags(
Ops));
3521 "SCEVURemExpr operand types don't match!");
3526 if (RHSC->getValue()->isOne())
3527 return getZero(LHS->getType());
3530 if (RHSC->getAPInt().isPowerOf2()) {
3531 Type *FullTy = LHS->getType();
3547 assert(!LHS->getType()->isPointerTy() &&
3548 "SCEVUDivExpr operand can't be pointer!");
3549 assert(LHS->getType() == RHS->getType() &&
3550 "SCEVUDivExpr operand types don't match!");
3557 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3565 if (RHSC->getValue()->isOne())
3570 if (!RHSC->getValue()->isZero()) {
3574 Type *Ty = LHS->getType();
3575 unsigned LZ = RHSC->getAPInt().countl_zero();
3579 if (!RHSC->getAPInt().isPowerOf2())
3587 const APInt &StepInt = Step->getAPInt();
3588 const APInt &DivInt = RHSC->getAPInt();
3589 if (!StepInt.
urem(DivInt) &&
3595 for (
const SCEV *
Op : AR->operands())
3601 const APInt *StartRem;
3614 bool CanFoldWithWrap = StepInt.
ule(DivInt) &&
3618 const SCEV *NewStart =
3620 if (*StartRem != 0 && (NoWrap || CanFoldWithWrap) &&
3622 const SCEV *NewLHS =
3625 if (LHS != NewLHS) {
3635 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
3644 for (
const SCEV *
Op : M->operands())
3648 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
3649 const SCEV *
Op = M->getOperand(i);
3661 if (
auto *DivisorConstant =
3663 bool Overflow =
false;
3665 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3676 for (
const SCEV *
Op :
A->operands())
3680 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
3687 if (Operands.
size() ==
A->getNumOperands())
3694 return getConstant(LHSC->getAPInt().udiv(RHSC->getAPInt()));
3704 return getZero(LHS->getType());
3708 const SCEV *NewLHS, *NewRHS;
3716 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP))
return S;
3719 UniqueSCEVs.InsertNode(S, IP);
3749 if (!
Mul || !
Mul->hasNoUnsignedWrap())
3756 if (LHSCst == RHSCst) {
3764 APInt Factor =
gcd(LHSCst, RHSCst);
3782 for (
int i = 0, e =
Mul->getNumOperands(); i != e; ++i) {
3783 if (
Mul->getOperand(i) == RHS) {
3802 if (StepChrec->getLoop() == L) {
3816 if (Operands.
size() == 1)
return Operands[0];
3821 "SCEVAddRecExpr operand types don't match!");
3822 assert(!
Op->getType()->isPointerTy() &&
"Step must be integer");
3824 for (
const SCEV *
Op : Operands)
3826 "SCEVAddRecExpr operand is not available at loop entry!");
3829 if (Operands.
back()->isZero()) {
3844 const Loop *NestedLoop = NestedAR->getLoop();
3845 if (L->contains(NestedLoop)
3848 DT.dominates(L->getHeader(), NestedLoop->
getHeader()))) {
3850 Operands[0] = NestedAR->getStart();
3854 bool AllInvariant =
all_of(
3866 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3877 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3881 Operands[0] = NestedAR;
3887 return getOrCreateAddRecExpr(Operands, L, Flags);
3903 if (!GEPI || !isSCEVExprNeverPoison(GEPI))
3907 return getGEPExpr(BaseExpr, IndexExprs,
GEP->getSourceElementType(), NW);
3921 bool FirstIter =
true;
3923 for (
SCEVUse IndexExpr : IndexExprs) {
3930 Offsets.push_back(FieldOffset);
3933 CurTy = STy->getTypeAtIndex(Index);
3938 "The first index of a GEP indexes a pointer");
3939 CurTy = SrcElementTy;
3950 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3951 Offsets.push_back(LocalOffset);
3956 if (Offsets.empty())
3969 "GEP should not change type mid-flight.");
3973SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3976 ID.AddInteger(SCEVType);
3980 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
3983SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3986 ID.AddInteger(SCEVType);
3990 return UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4000 assert(SCEVMinMaxExpr::isMinMaxType(Kind) &&
"Not a SCEVMinMaxExpr!");
4001 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4002 if (
Ops.size() == 1)
return Ops[0];
4005 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4007 "Operand types don't match!");
4010 "min/max should be consistently pointerish");
4036 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
4038 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
4043 return IsSigned ?
C.isMaxSignedValue() :
C.isMaxValue();
4045 return IsSigned ?
C.isMinSignedValue() :
C.isMinValue();
4051 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops)) {
4057 while (Idx <
Ops.size() &&
Ops[Idx]->getSCEVType() < Kind)
4062 if (Idx <
Ops.size()) {
4063 bool DeletedAny =
false;
4064 while (
Ops[Idx]->getSCEVType() == Kind) {
4066 Ops.erase(
Ops.begin()+Idx);
4084 for (
unsigned i = 0, e =
Ops.size() - 1; i != e; ++i) {
4085 if (
Ops[i] ==
Ops[i + 1] ||
4086 isKnownViaNonRecursiveReasoning(FirstPred,
Ops[i],
Ops[i + 1])) {
4089 Ops.erase(
Ops.begin() + i + 1,
Ops.begin() + i + 2);
4092 }
else if (isKnownViaNonRecursiveReasoning(SecondPred,
Ops[i],
4095 Ops.erase(
Ops.begin() + i,
Ops.begin() + i + 1);
4101 if (
Ops.size() == 1)
return Ops[0];
4103 assert(!
Ops.empty() &&
"Reduced smax down to nothing!");
4108 ID.AddInteger(Kind);
4112 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4114 return ExistingSCEV;
4117 SCEV *S =
new (SCEVAllocator)
4120 UniqueSCEVs.InsertNode(S, IP);
4128class SCEVSequentialMinMaxDeduplicatingVisitor final
4129 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
4130 std::optional<const SCEV *>> {
4131 using RetVal = std::optional<const SCEV *>;
4139 bool canRecurseInto(
SCEVTypes Kind)
const {
4142 return RootKind == Kind || NonSequentialRootKind == Kind;
4145 RetVal visitAnyMinMaxExpr(
const SCEV *S) {
4147 "Only for min/max expressions.");
4150 if (!canRecurseInto(Kind))
4160 return std::nullopt;
4167 RetVal
visit(
const SCEV *S) {
4169 if (!SeenOps.
insert(S).second)
4170 return std::nullopt;
4171 return Base::visit(S);
4175 SCEVSequentialMinMaxDeduplicatingVisitor(ScalarEvolution &SE,
4177 : SE(SE), RootKind(RootKind),
4178 NonSequentialRootKind(
4179 SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(
4183 SmallVectorImpl<SCEVUse> &NewOps) {
4188 for (
const SCEV *
Op : OrigOps) {
4193 Ops.emplace_back(*NewOp);
4197 NewOps = std::move(
Ops);
4201 RetVal visitConstant(
const SCEVConstant *Constant) {
return Constant; }
4203 RetVal visitVScale(
const SCEVVScale *VScale) {
return VScale; }
4205 RetVal visitPtrToAddrExpr(
const SCEVPtrToAddrExpr *Expr) {
return Expr; }
4207 RetVal visitPtrToIntExpr(
const SCEVPtrToIntExpr *Expr) {
return Expr; }
4209 RetVal visitTruncateExpr(
const SCEVTruncateExpr *Expr) {
return Expr; }
4211 RetVal visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
return Expr; }
4213 RetVal visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
return Expr; }
4215 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
4217 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
4219 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
4221 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
4223 RetVal visitSMaxExpr(
const SCEVSMaxExpr *Expr) {
4224 return visitAnyMinMaxExpr(Expr);
4227 RetVal visitUMaxExpr(
const SCEVUMaxExpr *Expr) {
4228 return visitAnyMinMaxExpr(Expr);
4231 RetVal visitSMinExpr(
const SCEVSMinExpr *Expr) {
4232 return visitAnyMinMaxExpr(Expr);
4235 RetVal visitUMinExpr(
const SCEVUMinExpr *Expr) {
4236 return visitAnyMinMaxExpr(Expr);
4239 RetVal visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *Expr) {
4240 return visitAnyMinMaxExpr(Expr);
4243 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4245 RetVal visitCouldNotCompute(
const SCEVCouldNotCompute *Expr) {
return Expr; }
4288struct SCEVPoisonCollector {
4289 bool LookThroughMaybePoisonBlocking;
4290 SmallPtrSet<const SCEVUnknown *, 4> MaybePoison;
4291 SCEVPoisonCollector(
bool LookThroughMaybePoisonBlocking)
4292 : LookThroughMaybePoisonBlocking(LookThroughMaybePoisonBlocking) {}
4294 bool follow(
const SCEV *S) {
4295 if (!LookThroughMaybePoisonBlocking &&
4305 bool isDone()
const {
return false; }
4315 SCEVPoisonCollector PC1(
true);
4320 if (PC1.MaybePoison.empty())
4326 SCEVPoisonCollector PC2(
false);
4336 SCEVPoisonCollector PC(
false);
4359 while (!Worklist.
empty()) {
4361 if (!Visited.
insert(V).second)
4365 if (Visited.
size() > 16)
4370 if (PoisonVals.
contains(V) || ::isGuaranteedNotToBePoison(V))
4381 if (PDI->isDisjoint())
4388 II &&
II->getIntrinsicID() == Intrinsic::vscale)
4395 if (
I->hasPoisonGeneratingAnnotations())
4406 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
4407 "Not a SCEVSequentialMinMaxExpr!");
4408 assert(!
Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4409 if (
Ops.size() == 1)
4413 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4415 "Operand types don't match!");
4418 "min/max should be consistently pointerish");
4426 if (
const SCEV *S = findExistingSCEVInCache(Kind,
Ops))
4433 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this, Kind);
4443 bool DeletedAny =
false;
4444 while (Idx <
Ops.size()) {
4445 if (
Ops[Idx]->getSCEVType() != Kind) {
4450 Ops.erase(
Ops.begin() + Idx);
4451 Ops.insert(
Ops.begin() + Idx, SMME->operands().begin(),
4452 SMME->operands().end());
4460 const SCEV *SaturationPoint;
4471 for (
unsigned i = 1, e =
Ops.size(); i != e; ++i) {
4472 if (!isGuaranteedNotToCauseUB(
Ops[i]))
4484 Ops.erase(
Ops.begin() + i);
4489 if (isKnownViaNonRecursiveReasoning(Pred,
Ops[i - 1],
Ops[i])) {
4490 Ops.erase(
Ops.begin() + i);
4498 ID.AddInteger(Kind);
4502 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP);
4504 return ExistingSCEV;
4508 SCEV *S =
new (SCEVAllocator)
4511 UniqueSCEVs.InsertNode(S, IP);
4559 if (
Size.isScalable())
4580 "Cannot get offset for structure containing scalable vector types");
4594 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(
ID, IP)) {
4596 "Stale SCEVUnknown in uniquing map!");
4602 UniqueSCEVs.InsertNode(S, IP);
4617 return Ty->isIntOrPtrTy();
4624 if (Ty->isPointerTy())
4635 if (Ty->isIntegerTy())
4639 assert(Ty->isPointerTy() &&
"Unexpected non-pointer non-integer type!");
4651 bool PreciseA, PreciseB;
4652 auto *ScopeA = getDefiningScopeBound({
A}, PreciseA);
4653 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4654 if (!PreciseA || !PreciseB)
4657 return (ScopeA == ScopeB) || DT.dominates(ScopeA, ScopeB) ||
4658 DT.dominates(ScopeB, ScopeA);
4662 return CouldNotCompute.get();
4665bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
4668 return SU && SU->getValue() ==
nullptr;
4671 return !ContainsNulls;
4676 if (
I != HasRecMap.end())
4681 HasRecMap.insert({S, FoundAddRec});
4689 if (
SI == ExprValueMap.
end())
4691 return SI->second.getArrayRef();
4697void ScalarEvolution::eraseValueFromMap(
Value *V) {
4699 if (
I != ValueExprMap.end()) {
4700 auto EVIt = ExprValueMap.find(
I->second);
4701 bool Removed = EVIt->second.remove(V);
4703 assert(Removed &&
"Value not in ExprValueMap?");
4704 ValueExprMap.erase(
I);
4708void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *S) {
4712 auto It = ValueExprMap.find_as(V);
4713 if (It == ValueExprMap.end()) {
4715 ExprValueMap[S].insert(V);
4726 return createSCEVIter(V);
4733 if (
I != ValueExprMap.end()) {
4734 const SCEV *S =
I->second;
4735 assert(checkValidity(S) &&
4736 "existing SCEV has not been properly invalidated");
4749 Type *Ty = V->getType();
4765 assert(!V->getType()->isPointerTy() &&
"Can't negate pointer");
4778 return (
const SCEV *)
nullptr;
4784 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4788 Type *Ty = V->getType();
4794 assert(
P->getType()->isPointerTy());
4809 if (AddOp->getType()->isPointerTy()) {
4810 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4828 return getZero(LHS->getType());
4833 if (RHS->getType()->isPointerTy()) {
4834 if (!LHS->getType()->isPointerTy() ||
4844 const bool RHSIsNotMinSigned =
4875 Type *SrcTy = V->getType();
4876 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4877 "Cannot truncate or zero extend with non-integer arguments!");
4887 Type *SrcTy = V->getType();
4888 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4889 "Cannot truncate or zero extend with non-integer arguments!");
4899 Type *SrcTy = V->getType();
4900 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4901 "Cannot noop or zero extend with non-integer arguments!");
4903 "getNoopOrZeroExtend cannot truncate!");
4911 Type *SrcTy = V->getType();
4912 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4913 "Cannot noop or sign extend with non-integer arguments!");
4915 "getNoopOrSignExtend cannot truncate!");
4923 Type *SrcTy = V->getType();
4924 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4925 "Cannot noop or any extend with non-integer arguments!");
4927 "getNoopOrAnyExtend cannot truncate!");
4935 Type *SrcTy = V->getType();
4936 assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
4937 "Cannot truncate or noop with non-integer arguments!");
4939 "getTruncateOrNoop cannot extend!");
4947 const SCEV *PromotedLHS = LHS;
4948 const SCEV *PromotedRHS = RHS;
4968 assert(!
Ops.empty() &&
"At least one operand must be!");
4970 if (
Ops.size() == 1)
4974 Type *MaxType =
nullptr;
4980 assert(MaxType &&
"Failed to find maximum type!");
4993 if (!V->getType()->isPointerTy())
4998 V = AddRec->getStart();
5000 const SCEV *PtrOp =
nullptr;
5001 for (
const SCEV *AddOp :
Add->operands()) {
5002 if (AddOp->getType()->isPointerTy()) {
5003 assert(!PtrOp &&
"Cannot have multiple pointer ops");
5007 assert(PtrOp &&
"Must have pointer op");
5019 for (
User *U :
I->users()) {
5021 if (Visited.
insert(UserInsn).second)
5035 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE,
5036 bool IgnoreOtherLoops =
true) {
5039 if (
Rewriter.hasSeenLoopVariantSCEVUnknown())
5041 return Rewriter.hasSeenOtherLoops() && !IgnoreOtherLoops
5046 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5048 SeenLoopVariantSCEVUnknown =
true;
5052 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5056 SeenOtherLoops =
true;
5060 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5062 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5065 explicit SCEVInitRewriter(
const Loop *L, ScalarEvolution &SE)
5066 : SCEVRewriteVisitor(SE),
L(
L) {}
5069 bool SeenLoopVariantSCEVUnknown =
false;
5070 bool SeenOtherLoops =
false;
5079 static const SCEV *rewrite(
const SCEV *S,
const Loop *L, ScalarEvolution &SE) {
5080 SCEVPostIncRewriter
Rewriter(L, SE);
5082 return Rewriter.hasSeenLoopVariantSCEVUnknown()
5087 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5089 SeenLoopVariantSCEVUnknown =
true;
5093 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5097 SeenOtherLoops =
true;
5101 bool hasSeenLoopVariantSCEVUnknown() {
return SeenLoopVariantSCEVUnknown; }
5103 bool hasSeenOtherLoops() {
return SeenOtherLoops; }
5106 explicit SCEVPostIncRewriter(
const Loop *L, ScalarEvolution &SE)
5107 : SCEVRewriteVisitor(SE),
L(
L) {}
5110 bool SeenLoopVariantSCEVUnknown =
false;
5111 bool SeenOtherLoops =
false;
5117class SCEVBackedgeConditionFolder
5120 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5121 ScalarEvolution &SE) {
5122 bool IsPosBECond =
false;
5123 Value *BECond =
nullptr;
5124 if (BasicBlock *Latch =
L->getLoopLatch()) {
5126 assert(BI->getSuccessor(0) != BI->getSuccessor(1) &&
5127 "Both outgoing branches should not target same header!");
5128 BECond = BI->getCondition();
5129 IsPosBECond = BI->getSuccessor(0) ==
L->getHeader();
5134 SCEVBackedgeConditionFolder
Rewriter(L, BECond, IsPosBECond, SE);
5138 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5139 const SCEV *
Result = Expr;
5144 switch (
I->getOpcode()) {
5145 case Instruction::Select: {
5147 std::optional<const SCEV *> Res =
5148 compareWithBackedgeCondition(
SI->getCondition());
5156 std::optional<const SCEV *> Res = compareWithBackedgeCondition(
I);
5167 explicit SCEVBackedgeConditionFolder(
const Loop *L,
Value *BECond,
5168 bool IsPosBECond, ScalarEvolution &SE)
5169 : SCEVRewriteVisitor(SE),
L(
L), BackedgeCond(BECond),
5170 IsPositiveBECond(IsPosBECond) {}
5172 std::optional<const SCEV *> compareWithBackedgeCondition(
Value *IC);
5176 Value *BackedgeCond =
nullptr;
5178 bool IsPositiveBECond;
5181std::optional<const SCEV *>
5182SCEVBackedgeConditionFolder::compareWithBackedgeCondition(
Value *IC) {
5187 if (BackedgeCond == IC)
5190 return std::nullopt;
5195 static const SCEV *rewrite(
const SCEV *S,
const Loop *L,
5196 ScalarEvolution &SE) {
5202 const SCEV *visitUnknown(
const SCEVUnknown *Expr) {
5209 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
5219 explicit SCEVShiftRewriter(
const Loop *L, ScalarEvolution &SE)
5220 : SCEVRewriteVisitor(SE),
L(
L) {}
5229ScalarEvolution::proveNoWrapViaConstantRanges(
const SCEVAddRecExpr *AR) {
5233 using OBO = OverflowingBinaryOperator;
5241 const APInt &BECountAP = BECountMax->getAPInt();
5242 unsigned NoOverflowBitWidth =
5254 Instruction::Add, IncRange, OBO::NoSignedWrap);
5255 if (NSWRegion.contains(AddRecRange))
5264 Instruction::Add, IncRange, OBO::NoUnsignedWrap);
5265 if (NUWRegion.contains(AddRecRange))
5273ScalarEvolution::proveNoSignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5283 if (!SignedWrapViaInductionTried.insert(AR).second)
5308 AC.assumptions().empty())
5316 const SCEV *OverflowLimit =
5318 if (OverflowLimit &&
5326ScalarEvolution::proveNoUnsignedWrapViaInduction(
const SCEVAddRecExpr *AR) {
5336 if (!UnsignedWrapViaInductionTried.insert(AR).second)
5362 AC.assumptions().empty())
5397 explicit BinaryOp(Operator *
Op)
5401 IsNSW = OBO->hasNoSignedWrap();
5402 IsNUW = OBO->hasNoUnsignedWrap();
5406 explicit BinaryOp(
unsigned Opcode,
Value *
LHS,
Value *
RHS,
bool IsNSW =
false,
5408 : Opcode(Opcode),
LHS(
LHS),
RHS(
RHS), IsNSW(IsNSW), IsNUW(IsNUW) {}
5420 return std::nullopt;
5426 switch (
Op->getOpcode()) {
5427 case Instruction::Add:
5428 case Instruction::Sub:
5429 case Instruction::Mul:
5430 case Instruction::UDiv:
5431 case Instruction::URem:
5432 case Instruction::And:
5433 case Instruction::AShr:
5434 case Instruction::Shl:
5435 return BinaryOp(
Op);
5437 case Instruction::Or: {
5440 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
5442 return BinaryOp(
Op);
5445 case Instruction::Xor:
5449 if (RHSC->getValue().isSignMask())
5450 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5452 if (V->getType()->isIntegerTy(1))
5453 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1));
5454 return BinaryOp(
Op);
5456 case Instruction::LShr:
5465 if (SA->getValue().ult(
BitWidth)) {
5467 ConstantInt::get(SA->getContext(),
5469 return BinaryOp(Instruction::UDiv,
Op->getOperand(0),
X);
5472 return BinaryOp(
Op);
5474 case Instruction::ExtractValue: {
5476 if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
5484 bool Signed = WO->isSigned();
5487 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
5492 return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
5503 if (
II->getIntrinsicID() == Intrinsic::loop_decrement_reg)
5504 return BinaryOp(Instruction::Sub,
II->getOperand(0),
II->getOperand(1));
5506 return std::nullopt;
5532 if (
Op == SymbolicPHI)
5537 if (SourceBits != NewBits)
5555 if (!L || L->getHeader() != PN->
getParent())
5613std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5614ScalarEvolution::createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI) {
5622 assert(L &&
"Expecting an integer loop header phi");
5627 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5628 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
5629 Value *
V = PN->getIncomingValue(i);
5630 if (
L->contains(PN->getIncomingBlock(i))) {
5633 }
else if (BEValueV != V) {
5637 }
else if (!StartValueV) {
5639 }
else if (StartValueV != V) {
5640 StartValueV =
nullptr;
5644 if (!BEValueV || !StartValueV)
5645 return std::nullopt;
5647 const SCEV *BEValue =
getSCEV(BEValueV);
5654 return std::nullopt;
5658 unsigned FoundIndex =
Add->getNumOperands();
5659 Type *TruncTy =
nullptr;
5661 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5664 if (FoundIndex == e) {
5669 if (FoundIndex ==
Add->getNumOperands())
5670 return std::nullopt;
5674 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5675 if (i != FoundIndex)
5676 Ops.push_back(
Add->getOperand(i));
5682 return std::nullopt;
5735 const SCEV *StartVal =
getSCEV(StartValueV);
5736 const SCEV *PHISCEV =
5763 auto getExtendedExpr = [&](
const SCEV *Expr,
5764 bool CreateSignExtend) ->
const SCEV * {
5767 const SCEV *ExtendedExpr =
5770 return ExtendedExpr;
5778 auto PredIsKnownFalse = [&](
const SCEV *Expr,
5779 const SCEV *ExtendedExpr) ->
bool {
5780 return Expr != ExtendedExpr &&
5784 const SCEV *StartExtended = getExtendedExpr(StartVal,
Signed);
5785 if (PredIsKnownFalse(StartVal, StartExtended)) {
5787 return std::nullopt;
5792 const SCEV *AccumExtended = getExtendedExpr(Accum,
true);
5793 if (PredIsKnownFalse(Accum, AccumExtended)) {
5795 return std::nullopt;
5798 auto AppendPredicate = [&](
const SCEV *Expr,
5799 const SCEV *ExtendedExpr) ->
void {
5800 if (Expr != ExtendedExpr &&
5808 AppendPredicate(StartVal, StartExtended);
5809 AppendPredicate(Accum, AccumExtended);
5817 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite =
5818 std::make_pair(NewAR, Predicates);
5820 PredicatedSCEVRewrites[{SymbolicPHI,
L}] = PredRewrite;
5824std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5829 return std::nullopt;
5832 auto I = PredicatedSCEVRewrites.find({SymbolicPHI, L});
5833 if (
I != PredicatedSCEVRewrites.end()) {
5834 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite =
5837 if (Rewrite.first == SymbolicPHI)
5838 return std::nullopt;
5842 assert(!(Rewrite.second).empty() &&
"Expected to find Predicates");
5846 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5847 Rewrite = createAddRecFromPHIWithCastsImpl(SymbolicPHI);
5852 PredicatedSCEVRewrites[{SymbolicPHI, L}] = {SymbolicPHI, Predicates};
5853 return std::nullopt;
5870 auto areExprsEqual = [&](
const SCEV *Expr1,
const SCEV *Expr2) ->
bool {
5871 if (Expr1 != Expr2 &&
5872 !Preds->implies(SE.getEqualPredicate(Expr1, Expr2), SE) &&
5873 !Preds->implies(SE.getEqualPredicate(Expr2, Expr1), SE))
5890const SCEV *ScalarEvolution::createSimpleAffineAddRec(
PHINode *PN,
5892 Value *StartValueV) {
5895 assert(BEValueV && StartValueV);
5901 if (BO->Opcode != Instruction::Add)
5904 const SCEV *Accum =
nullptr;
5905 if (BO->LHS == PN && L->isLoopInvariant(BO->RHS))
5907 else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS))
5921 insertValueToMap(PN, PHISCEV);
5933 "Accum is defined outside L, but is not invariant?");
5934 if (isAddRecNeverPoison(BEInst, L))
5941const SCEV *ScalarEvolution::createAddRecFromPHI(
PHINode *PN) {
5942 const Loop *
L = LI.getLoopFor(PN->
getParent());
5949 Value *BEValueV =
nullptr, *StartValueV =
nullptr;
5955 }
else if (BEValueV != V) {
5959 }
else if (!StartValueV) {
5961 }
else if (StartValueV != V) {
5962 StartValueV =
nullptr;
5966 if (!BEValueV || !StartValueV)
5969 assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
5970 "PHI node already processed?");
5974 if (
auto *S = createSimpleAffineAddRec(PN, BEValueV, StartValueV))
5979 insertValueToMap(PN, SymbolicName);
5983 const SCEV *BEValue =
getSCEV(BEValueV);
5993 unsigned FoundIndex =
Add->getNumOperands();
5994 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
5995 if (
Add->getOperand(i) == SymbolicName)
5996 if (FoundIndex == e) {
6001 if (FoundIndex !=
Add->getNumOperands()) {
6004 for (
unsigned i = 0, e =
Add->getNumOperands(); i != e; ++i)
6005 if (i != FoundIndex)
6006 Ops.push_back(SCEVBackedgeConditionFolder::rewrite(
Add->getOperand(i),
6018 if (BO->Opcode == Instruction::Add && BO->LHS == PN) {
6025 if (
GEP->getOperand(0) == PN) {
6026 GEPNoWrapFlags NW =
GEP->getNoWrapFlags();
6044 const SCEV *StartVal =
getSCEV(StartValueV);
6045 const SCEV *PHISCEV =
getAddRecExpr(StartVal, Accum, L, Flags);
6050 forgetMemoizedResults({SymbolicName});
6051 insertValueToMap(PN, PHISCEV);
6055 const_cast<SCEVAddRecExpr *
>(AR),
6081 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *
this);
6082 const SCEV *
Start = SCEVInitRewriter::rewrite(Shifted, L, *
this,
false);
6084 isGuaranteedNotToCauseUB(Shifted) &&
::impliesPoison(Shifted, Start)) {
6085 const SCEV *StartVal =
getSCEV(StartValueV);
6086 if (Start == StartVal) {
6090 forgetMemoizedResults({SymbolicName});
6091 insertValueToMap(PN, Shifted);
6101 eraseValueFromMap(PN);
6116 Use &LeftUse =
Merge->getOperandUse(0);
6117 Use &RightUse =
Merge->getOperandUse(1);
6153 assert(IDom &&
"At least the entry block should dominate PN");
6161const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(
PHINode *PN) {
6166 return createNodeForSelectOrPHI(PN,
Cond,
LHS,
RHS);
6183 CommonInst = IncomingInst;
6199ScalarEvolution::createNodeForPHIWithIdenticalOperands(
PHINode *PN) {
6205 const SCEV *CommonSCEV =
getSCEV(CommonInst);
6206 bool SCEVExprsIdentical =
6208 [
this, CommonSCEV](
Value *V) { return CommonSCEV == getSCEV(V); });
6209 return SCEVExprsIdentical ? CommonSCEV :
nullptr;
6212const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
6213 if (
const SCEV *S = createAddRecFromPHI(PN))
6223 if (
const SCEV *S = createNodeForPHIWithIdenticalOperands(PN))
6226 if (
const SCEV *S = createNodeFromSelectLikePHI(PN))
6235 struct FindClosure {
6236 const SCEV *OperandToFind;
6242 bool canRecurseInto(
SCEVTypes Kind)
const {
6245 return RootKind == Kind || NonSequentialRootKind == Kind ||
6250 : OperandToFind(OperandToFind), RootKind(RootKind),
6251 NonSequentialRootKind(
6255 bool follow(
const SCEV *S) {
6256 Found = S == OperandToFind;
6258 return !isDone() && canRecurseInto(S->
getSCEVType());
6261 bool isDone()
const {
return Found; }
6264 FindClosure FC(OperandToFind, RootKind);
6269std::optional<const SCEV *>
6270ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty,
6280 switch (ICI->getPredicate()) {
6294 bool Signed = ICI->isSigned();
6295 const SCEV *LA =
getSCEV(TrueVal);
6303 if (LA == LS &&
RA == RS)
6305 if (LA == RS &&
RA == LS)
6308 auto CoerceOperand = [&](
const SCEV *
Op) ->
const SCEV * {
6309 if (
Op->getType()->isPointerTy()) {
6320 LS = CoerceOperand(LS);
6321 RS = CoerceOperand(RS);
6345 const SCEV *TrueValExpr =
getSCEV(TrueVal);
6346 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6360 X = ZExt->getOperand();
6362 const SCEV *FalseValExpr =
getSCEV(FalseVal);
6373 return std::nullopt;
6376static std::optional<const SCEV *>
6378 const SCEV *TrueExpr,
const SCEV *FalseExpr) {
6382 "Unexpected operands of a select.");
6394 return std::nullopt;
6409static std::optional<const SCEV *>
6413 return std::nullopt;
6416 const auto *SETrue = SE->
getSCEV(TrueVal);
6417 const auto *SEFalse = SE->
getSCEV(FalseVal);
6421const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
6423 assert(
Cond->getType()->isIntegerTy(1) &&
"Select condition is not an i1?");
6425 V->getType() ==
TrueVal->getType() &&
6426 "Types of select hands and of the result must match.");
6429 if (!
V->getType()->isIntegerTy(1))
6432 if (std::optional<const SCEV *> S =
6445 return getSCEV(CI->isOne() ? TrueVal : FalseVal);
6449 if (std::optional<const SCEV *> S =
6450 createNodeForSelectOrPHIInstWithICmpInstCond(
I->getType(), ICI,
6456 return createNodeForSelectOrPHIViaUMinSeq(V,
Cond, TrueVal, FalseVal);
6462 assert(
GEP->getSourceElementType()->isSized() &&
6463 "GEP source element type must be sized");
6466 for (
Value *Index :
GEP->indices())
6471APInt ScalarEvolution::getConstantMultipleImpl(
const SCEV *S,
6474 auto GetShiftedByZeros = [
BitWidth](uint32_t TrailingZeros) {
6477 : APInt::getOneBitSet(
BitWidth, TrailingZeros);
6479 auto GetGCDMultiple = [
this, CtxI](
const SCEVNAryExpr *
N) {
6482 for (
unsigned I = 1,
E =
N->getNumOperands();
I <
E && Res != 1; ++
I)
6501 return GetShiftedByZeros(TZ);
6511 return GetShiftedByZeros(TZ);
6515 if (
M->hasNoUnsignedWrap()) {
6518 for (
const SCEV *Operand :
M->operands().drop_front())
6526 for (
const SCEV *Operand :
M->operands())
6528 return GetShiftedByZeros(TZ);
6533 if (
N->hasNoUnsignedWrap())
6534 return GetGCDMultiple(
N);
6537 for (
const SCEV *Operand :
N->operands().drop_front())
6539 return GetShiftedByZeros(TZ);
6556 CtxI = &*F.getEntryBlock().begin();
6562 .countMinTrailingZeros();
6563 return GetShiftedByZeros(Known);
6576 return getConstantMultipleImpl(S, CtxI);
6578 auto I = ConstantMultipleCache.find(S);
6579 if (
I != ConstantMultipleCache.end())
6582 APInt Result = getConstantMultipleImpl(S, CtxI);
6583 auto InsertPair = ConstantMultipleCache.insert({S, Result});
6584 assert(InsertPair.second &&
"Should insert a new key");
6585 return InsertPair.first->second;
6602 if (
MDNode *MD =
I->getMetadata(LLVMContext::MD_range))
6605 if (std::optional<ConstantRange>
Range = CB->getRange())
6609 if (std::optional<ConstantRange>
Range =
A->getRange())
6612 return std::nullopt;
6619 UnsignedRanges.erase(AddRec);
6620 SignedRanges.erase(AddRec);
6621 ConstantMultipleCache.erase(AddRec);
6626getRangeForUnknownRecurrence(
const SCEVUnknown *U) {
6652 Value *Start, *Step;
6659 assert(L && L->getHeader() ==
P->getParent());
6672 case Instruction::AShr:
6673 case Instruction::LShr:
6674 case Instruction::Shl:
6689 KnownStep.getBitWidth() ==
BitWidth);
6692 auto MaxShiftAmt = KnownStep.getMaxValue();
6694 bool Overflow =
false;
6695 auto TotalShift = MaxShiftAmt.umul_ov(TCAP, Overflow);
6702 case Instruction::AShr: {
6710 if (KnownStart.isNonNegative())
6713 KnownStart.getMaxValue() + 1);
6714 if (KnownStart.isNegative())
6717 KnownEnd.getMaxValue() + 1);
6720 case Instruction::LShr: {
6729 KnownStart.getMaxValue() + 1);
6731 case Instruction::Shl: {
6735 if (TotalShift.ult(KnownStart.countMinLeadingZeros()))
6736 return ConstantRange(KnownStart.getMinValue(),
6737 KnownEnd.getMaxValue() + 1);
6762 [&](
Value *Operand) { return DT.dominates(Operand, PHI); }))
6769ScalarEvolution::getRangeRefIter(
const SCEV *S,
6770 ScalarEvolution::RangeSignHint SignHint) {
6771 DenseMap<const SCEV *, ConstantRange> &Cache =
6772 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6775 SmallPtrSet<const SCEV *, 8> Seen;
6779 auto AddToWorklist = [&WorkList, &Seen, &Cache](
const SCEV *Expr) {
6780 if (!Seen.
insert(Expr).second)
6814 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
6815 const SCEV *
P = WorkList[
I];
6819 for (
const SCEV *
Op :
P->operands())
6832 if (!WorkList.
empty()) {
6837 getRangeRef(
P, SignHint);
6841 return getRangeRef(S, SignHint, 0);
6848 const SCEV *S, ScalarEvolution::RangeSignHint SignHint,
unsigned Depth) {
6849 DenseMap<const SCEV *, ConstantRange> &Cache =
6850 SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
6858 if (
I != Cache.
end())
6862 return setRange(
C, SignHint, ConstantRange(
C->getAPInt()));
6867 return getRangeRefIter(S, SignHint);
6870 ConstantRange ConservativeResult(
BitWidth,
true);
6871 using OBO = OverflowingBinaryOperator;
6875 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
6879 ConservativeResult =
6886 ConservativeResult = ConstantRange(
6902 ConservativeResult.intersectWith(
X.truncate(
BitWidth), RangeType));
6909 ConservativeResult.intersectWith(
X.zeroExtend(
BitWidth), RangeType));
6916 ConservativeResult.intersectWith(
X.signExtend(
BitWidth), RangeType));
6922 return setRange(Cast, SignHint,
X);
6927 const SCEV *URemLHS =
nullptr, *URemRHS =
nullptr;
6928 if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED &&
6930 ConstantRange LHSRange = getRangeRef(URemLHS, SignHint,
Depth + 1);
6931 ConstantRange RHSRange = getRangeRef(URemRHS, SignHint,
Depth + 1);
6932 ConservativeResult =
6933 ConservativeResult.intersectWith(LHSRange.
urem(RHSRange), RangeType);
6935 ConstantRange
X = getRangeRef(
Add->getOperand(0), SignHint,
Depth + 1);
6936 unsigned WrapType = OBO::AnyWrap;
6937 if (
Add->hasNoSignedWrap())
6938 WrapType |= OBO::NoSignedWrap;
6939 if (
Add->hasNoUnsignedWrap())
6940 WrapType |= OBO::NoUnsignedWrap;
6942 X =
X.addWithNoWrap(getRangeRef(
Op, SignHint,
Depth + 1), WrapType,
6944 return setRange(
Add, SignHint,
6945 ConservativeResult.intersectWith(
X, RangeType));
6949 ConstantRange
X = getRangeRef(
Mul->getOperand(0), SignHint,
Depth + 1);
6951 X =
X.multiply(getRangeRef(
Op, SignHint,
Depth + 1));
6952 return setRange(
Mul, SignHint,
6953 ConservativeResult.intersectWith(
X, RangeType));
6957 ConstantRange
X = getRangeRef(UDiv->
getLHS(), SignHint,
Depth + 1);
6958 ConstantRange
Y = getRangeRef(UDiv->
getRHS(), SignHint,
Depth + 1);
6959 return setRange(UDiv, SignHint,
6960 ConservativeResult.intersectWith(
X.udiv(
Y), RangeType));
6968 if (!UnsignedMinValue.
isZero())
6969 ConservativeResult = ConservativeResult.intersectWith(
6970 ConstantRange(UnsignedMinValue, APInt(
BitWidth, 0)), RangeType);
6979 bool AllNonNeg =
true;
6980 bool AllNonPos =
true;
6981 for (
unsigned i = 1, e = AddRec->
getNumOperands(); i != e; ++i) {
6988 ConservativeResult = ConservativeResult.intersectWith(
6993 ConservativeResult = ConservativeResult.intersectWith(
7002 const SCEV *MaxBEScev =
7016 auto RangeFromAffine = getRangeForAffineAR(
7018 ConservativeResult =
7019 ConservativeResult.intersectWith(RangeFromAffine, RangeType);
7021 auto RangeFromFactoring = getRangeViaFactoring(
7023 ConservativeResult =
7024 ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
7030 const SCEV *SymbolicMaxBECount =
7035 auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
7036 AddRec, SymbolicMaxBECount,
BitWidth, SignHint);
7037 ConservativeResult =
7038 ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
7043 return setRange(AddRec, SignHint, std::move(ConservativeResult));
7053 ID = Intrinsic::umax;
7056 ID = Intrinsic::smax;
7060 ID = Intrinsic::umin;
7063 ID = Intrinsic::smin;
7070 ConstantRange
X = getRangeRef(NAry->getOperand(0), SignHint,
Depth + 1);
7071 for (
unsigned i = 1, e = NAry->getNumOperands(); i != e; ++i)
7073 ID, {
X, getRangeRef(NAry->getOperand(i), SignHint,
Depth + 1)});
7074 return setRange(S, SignHint,
7075 ConservativeResult.intersectWith(
X, RangeType));
7084 ConservativeResult =
7085 ConservativeResult.intersectWith(*MDRange, RangeType);
7090 auto CR = getRangeForUnknownRecurrence(U);
7091 ConservativeResult = ConservativeResult.intersectWith(CR);
7102 if (
U->getType()->isPointerTy()) {
7105 unsigned ptrSize = DL.getPointerTypeSizeInBits(
U->getType());
7106 int ptrIdxDiff = ptrSize -
BitWidth;
7107 if (ptrIdxDiff > 0 && ptrSize >
BitWidth && NS > (
unsigned)ptrIdxDiff)
7120 ConservativeResult = ConservativeResult.intersectWith(
7124 ConservativeResult = ConservativeResult.intersectWith(
7129 if (
U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
7132 bool CanBeNull, CanBeFreed;
7133 uint64_t DerefBytes =
7134 V->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
7144 uint64_t
Align =
U->getValue()->getPointerAlignment(DL).value();
7145 uint64_t Rem = MaxVal.
urem(Align);
7150 ConservativeResult = ConservativeResult.intersectWith(
7160 return getRangeRef(AR, SignHint,
Depth + 1);
7164 ConstantRange RangeFromOps(
BitWidth,
false);
7166 for (
const auto &
Op :
Phi->operands()) {
7168 RangeFromOps = RangeFromOps.unionWith(OpRange);
7170 if (RangeFromOps.isFullSet())
7173 ConservativeResult =
7174 ConservativeResult.intersectWith(RangeFromOps, RangeType);
7180 if (
II->getIntrinsicID() == Intrinsic::vscale) {
7182 ConservativeResult = ConservativeResult.difference(Disallowed);
7185 return setRange(U, SignHint, std::move(ConservativeResult));
7191 return setRange(S, SignHint, std::move(ConservativeResult));
7200 const APInt &MaxBECount,
7207 if (Step == 0 || MaxBECount == 0)
7214 return ConstantRange::getFull(
BitWidth);
7230 return ConstantRange::getFull(
BitWidth);
7242 APInt MovedBoundary = Descending ? (StartLower - std::move(
Offset))
7243 : (StartUpper + std::move(
Offset));
7248 if (StartRange.
contains(MovedBoundary))
7249 return ConstantRange::getFull(
BitWidth);
7252 Descending ? std::move(MovedBoundary) : std::move(StartLower);
7254 Descending ? std::move(StartUpper) : std::move(MovedBoundary);
7263 const APInt &MaxBECount) {
7267 "mismatched bit widths");
7276 StepSRange.
getSignedMin(), StartSRange, MaxBECount,
true);
7278 StartSRange, MaxBECount,
7290ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
7292 ScalarEvolution::RangeSignHint SignHint) {
7293 assert(AddRec->
isAffine() &&
"Non-affine AddRecs are not suppored!\n");
7295 "This only works for non-self-wrapping AddRecs!");
7296 const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
7300 return ConstantRange::getFull(
BitWidth);
7308 return ConstantRange::getFull(
BitWidth);
7312 const SCEV *MaxItersWithoutWrap =
getUDivExpr(RangeWidth, StepAbs);
7314 MaxItersWithoutWrap))
7315 return ConstantRange::getFull(
BitWidth);
7336 ConstantRange StartRange = getRangeRef(Start, SignHint);
7337 ConstantRange EndRange = getRangeRef(End, SignHint);
7338 ConstantRange RangeBetween = StartRange.
unionWith(EndRange);
7342 return RangeBetween;
7347 return ConstantRange::getFull(
BitWidth);
7350 isKnownPredicateViaConstantRanges(LEPred, Start, End))
7351 return RangeBetween;
7353 isKnownPredicateViaConstantRanges(GEPred, Start, End))
7354 return RangeBetween;
7355 return ConstantRange::getFull(
BitWidth);
7360 const APInt &MaxBECount) {
7367 "mismatched bit widths");
7369 struct SelectPattern {
7370 Value *Condition =
nullptr;
7374 explicit SelectPattern(ScalarEvolution &SE,
unsigned BitWidth,
7376 std::optional<unsigned> CastOp;
7390 CastOp = SCast->getSCEVType();
7391 S = SCast->getOperand();
7394 using namespace llvm::PatternMatch;
7401 Condition =
nullptr;
7433 bool isRecognized() {
return Condition !=
nullptr; }
7436 SelectPattern StartPattern(*
this,
BitWidth, Start);
7437 if (!StartPattern.isRecognized())
7438 return ConstantRange::getFull(
BitWidth);
7440 SelectPattern StepPattern(*
this,
BitWidth, Step);
7441 if (!StepPattern.isRecognized())
7442 return ConstantRange::getFull(
BitWidth);
7444 if (StartPattern.Condition != StepPattern.Condition) {
7448 return ConstantRange::getFull(
BitWidth);
7459 const SCEV *TrueStart = this->
getConstant(StartPattern.TrueValue);
7460 const SCEV *TrueStep = this->
getConstant(StepPattern.TrueValue);
7461 const SCEV *FalseStart = this->
getConstant(StartPattern.FalseValue);
7462 const SCEV *FalseStep = this->
getConstant(StepPattern.FalseValue);
7464 ConstantRange TrueRange =
7465 this->getRangeForAffineAR(TrueStart, TrueStep, MaxBECount);
7466 ConstantRange FalseRange =
7467 this->getRangeForAffineAR(FalseStart, FalseStep, MaxBECount);
7489ScalarEvolution::getNonTrivialDefiningScopeBound(
const SCEV *S) {
7502 SmallPtrSet<const SCEV *, 16> Visited;
7504 auto pushOp = [&](
const SCEV *S) {
7505 if (!Visited.
insert(S).second)
7508 if (Visited.
size() > 30) {
7519 while (!Worklist.
empty()) {
7521 if (
auto *DefI = getNonTrivialDefiningScopeBound(S)) {
7522 if (!Bound || DT.dominates(Bound, DefI))
7529 return Bound ? Bound : &*F.getEntryBlock().begin();
7535 return getDefiningScopeBound(
Ops, Discard);
7538bool ScalarEvolution::isGuaranteedToTransferExecutionTo(
const Instruction *
A,
7540 if (
A->getParent() ==
B->getParent() &&
7545 auto *BLoop = LI.getLoopFor(
B->getParent());
7546 if (BLoop && BLoop->getHeader() ==
B->getParent() &&
7547 BLoop->getLoopPreheader() ==
A->getParent() &&
7549 A->getParent()->end()) &&
7556bool ScalarEvolution::isGuaranteedNotToBePoison(
const SCEV *
Op) {
7557 SCEVPoisonCollector PC(
true);
7559 return PC.MaybePoison.empty();
7562bool ScalarEvolution::isGuaranteedNotToCauseUB(
const SCEV *
Op) {
7568 return M && (!
isKnownNonZero(Op1) || !isGuaranteedNotToBePoison(Op1));
7572bool ScalarEvolution::isSCEVExprNeverPoison(
const Instruction *
I) {
7589 for (
const Use &
Op :
I->operands()) {
7595 auto *DefI = getDefiningScopeBound(SCEVOps);
7596 return isGuaranteedToTransferExecutionTo(DefI,
I);
7599bool ScalarEvolution::isAddRecNeverPoison(
const Instruction *
I,
const Loop *L) {
7601 if (isSCEVExprNeverPoison(
I))
7612 auto *ExitingBB =
L->getExitingBlock();
7616 SmallPtrSet<const Value *, 16> KnownPoison;
7625 while (!Worklist.
empty()) {
7628 for (
const Use &U :
Poison->uses()) {
7631 DT.dominates(PoisonUser->
getParent(), ExitingBB))
7635 if (KnownPoison.
insert(PoisonUser).second)
7643ScalarEvolution::LoopProperties
7644ScalarEvolution::getLoopProperties(
const Loop *L) {
7645 using LoopProperties = ScalarEvolution::LoopProperties;
7647 auto Itr = LoopPropertiesCache.find(L);
7648 if (Itr == LoopPropertiesCache.end()) {
7651 return !
SI->isSimple();
7661 return I->mayWriteToMemory();
7664 LoopProperties LP = {
true,
7667 for (
auto *BB :
L->getBlocks())
7668 for (
auto &
I : *BB) {
7670 LP.HasNoAbnormalExits =
false;
7671 if (HasSideEffects(&
I))
7672 LP.HasNoSideEffects =
false;
7673 if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
7677 auto InsertPair = LoopPropertiesCache.insert({
L, LP});
7678 assert(InsertPair.second &&
"We just checked!");
7679 Itr = InsertPair.first;
7692const SCEV *ScalarEvolution::createSCEVIter(
Value *V) {
7698 Stack.emplace_back(V,
true);
7699 Stack.emplace_back(V,
false);
7700 while (!Stack.empty()) {
7701 auto E = Stack.pop_back_val();
7702 Value *CurV = E.getPointer();
7708 const SCEV *CreatedSCEV =
nullptr;
7711 CreatedSCEV = createSCEV(CurV);
7716 CreatedSCEV = getOperandsToCreate(CurV,
Ops);
7720 insertValueToMap(CurV, CreatedSCEV);
7724 Stack.emplace_back(CurV,
true);
7726 Stack.emplace_back(
Op,
false);
7743 if (!DT.isReachableFromEntry(
I->getParent()))
7756 switch (BO->Opcode) {
7757 case Instruction::Add:
7758 case Instruction::Mul: {
7765 Ops.push_back(BO->
Op);
7769 Ops.push_back(BO->RHS);
7773 (BO->Opcode == Instruction::Add &&
7774 (NewBO->Opcode != Instruction::Add &&
7775 NewBO->Opcode != Instruction::Sub)) ||
7776 (BO->Opcode == Instruction::Mul &&
7777 NewBO->Opcode != Instruction::Mul)) {
7778 Ops.push_back(BO->LHS);
7783 if (BO->
Op && (BO->IsNSW || BO->IsNUW)) {
7786 Ops.push_back(BO->LHS);
7794 case Instruction::Sub:
7795 case Instruction::UDiv:
7796 case Instruction::URem:
7798 case Instruction::AShr:
7799 case Instruction::Shl:
7800 case Instruction::Xor:
7804 case Instruction::And:
7805 case Instruction::Or:
7809 case Instruction::LShr:
7816 Ops.push_back(BO->LHS);
7817 Ops.push_back(BO->RHS);
7821 switch (
U->getOpcode()) {
7822 case Instruction::Trunc:
7823 case Instruction::ZExt:
7824 case Instruction::SExt:
7825 case Instruction::PtrToAddr:
7826 case Instruction::PtrToInt:
7827 Ops.push_back(
U->getOperand(0));
7830 case Instruction::BitCast:
7832 Ops.push_back(
U->getOperand(0));
7837 case Instruction::SDiv:
7838 case Instruction::SRem:
7839 Ops.push_back(
U->getOperand(0));
7840 Ops.push_back(
U->getOperand(1));
7843 case Instruction::GetElementPtr:
7845 "GEP source element type must be sized");
7849 case Instruction::IntToPtr:
7852 case Instruction::PHI:
7883 Ops.push_back(CondICmp->getOperand(0));
7884 Ops.push_back(CondICmp->getOperand(1));
7904 case Instruction::Select: {
7906 auto CanSimplifyToUnknown = [
this,
U]() {
7924 if (CanSimplifyToUnknown())
7931 case Instruction::Call:
7932 case Instruction::Invoke:
7939 switch (
II->getIntrinsicID()) {
7940 case Intrinsic::abs:
7941 Ops.push_back(
II->getArgOperand(0));
7943 case Intrinsic::umax:
7944 case Intrinsic::umin:
7945 case Intrinsic::smax:
7946 case Intrinsic::smin:
7947 case Intrinsic::usub_sat:
7948 case Intrinsic::uadd_sat:
7949 Ops.push_back(
II->getArgOperand(0));
7950 Ops.push_back(
II->getArgOperand(1));
7952 case Intrinsic::start_loop_iterations:
7953 case Intrinsic::annotation:
7954 case Intrinsic::ptr_annotation:
7955 Ops.push_back(
II->getArgOperand(0));
7967const SCEV *ScalarEvolution::createSCEV(
Value *V) {
7976 if (!DT.isReachableFromEntry(
I->getParent()))
7991 switch (BO->Opcode) {
7992 case Instruction::Add: {
8018 if (BO->Opcode == Instruction::Sub)
8026 if (BO->Opcode == Instruction::Sub)
8033 if (!NewBO || (NewBO->Opcode != Instruction::Add &&
8034 NewBO->Opcode != Instruction::Sub)) {
8044 case Instruction::Mul: {
8065 if (!NewBO || NewBO->Opcode != Instruction::Mul) {
8074 case Instruction::UDiv:
8078 case Instruction::URem:
8082 case Instruction::Sub: {
8085 Flags = getNoWrapFlagsFromUB(BO->
Op);
8090 case Instruction::And:
8096 if (CI->isMinusOne())
8098 const APInt &
A = CI->getValue();
8104 unsigned LZ =
A.countl_zero();
8105 unsigned TZ =
A.countr_zero();
8110 APInt EffectiveMask =
8112 if ((LZ != 0 || TZ != 0) && !((~
A & ~Known.
Zero) & EffectiveMask)) {
8115 const SCEV *ShiftedLHS =
nullptr;
8119 unsigned MulZeros = OpC->getAPInt().countr_zero();
8120 unsigned GCD = std::min(MulZeros, TZ);
8125 auto *NewMul =
getMulExpr(MulOps, LHSMul->getNoWrapFlags());
8147 case Instruction::Or:
8156 case Instruction::Xor:
8159 if (CI->isMinusOne())
8168 if (LBO->getOpcode() == Instruction::And &&
8169 LCI->getValue() == CI->getValue())
8170 if (
const SCEVZeroExtendExpr *Z =
8173 const SCEV *Z0 =
Z->getOperand();
8180 if (CI->getValue().isMask(Z0TySize))
8186 APInt Trunc = CI->getValue().trunc(Z0TySize);
8195 case Instruction::Shl:
8213 auto MulFlags = getNoWrapFlagsFromUB(BO->
Op);
8222 ConstantInt *
X = ConstantInt::get(
8228 case Instruction::AShr:
8250 const SCEV *AddTruncateExpr =
nullptr;
8251 ConstantInt *ShlAmtCI =
nullptr;
8252 const SCEV *AddConstant =
nullptr;
8254 if (L &&
L->getOpcode() == Instruction::Add) {
8262 if (LShift && LShift->
getOpcode() == Instruction::Shl) {
8269 APInt AddOperand = AddOperandCI->
getValue().
ashr(AShrAmt);
8277 }
else if (L &&
L->getOpcode() == Instruction::Shl) {
8282 const SCEV *ShlOp0SCEV =
getSCEV(
L->getOperand(0));
8287 if (AddTruncateExpr && ShlAmtCI) {
8299 const APInt &ShlAmt = ShlAmtCI->
getValue();
8303 const SCEV *CompositeExpr =
8305 if (
L->getOpcode() != Instruction::Shl)
8306 CompositeExpr =
getAddExpr(CompositeExpr, AddConstant);
8315 switch (
U->getOpcode()) {
8316 case Instruction::Trunc:
8319 case Instruction::ZExt:
8322 case Instruction::SExt:
8332 if (BO->Opcode == Instruction::Sub && BO->IsNSW) {
8333 Type *Ty =
U->getType();
8341 case Instruction::BitCast:
8347 case Instruction::PtrToAddr: {
8354 case Instruction::PtrToInt: {
8357 Type *DstIntTy =
U->getType();
8365 case Instruction::IntToPtr:
8369 case Instruction::SDiv:
8376 case Instruction::SRem:
8383 case Instruction::GetElementPtr:
8386 case Instruction::PHI:
8389 case Instruction::Select:
8390 return createNodeForSelectOrPHI(U,
U->getOperand(0),
U->getOperand(1),
8393 case Instruction::Call:
8394 case Instruction::Invoke:
8399 switch (
II->getIntrinsicID()) {
8400 case Intrinsic::abs:
8404 case Intrinsic::umax:
8408 case Intrinsic::umin:
8412 case Intrinsic::smax:
8416 case Intrinsic::smin:
8420 case Intrinsic::usub_sat: {
8421 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8422 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8426 case Intrinsic::uadd_sat: {
8427 const SCEV *
X =
getSCEV(
II->getArgOperand(0));
8428 const SCEV *
Y =
getSCEV(
II->getArgOperand(1));
8432 case Intrinsic::start_loop_iterations:
8433 case Intrinsic::annotation:
8434 case Intrinsic::ptr_annotation:
8438 case Intrinsic::vscale:
8458 auto *ExitCountType = ExitCount->
getType();
8459 assert(ExitCountType->isIntegerTy());
8461 1 + ExitCountType->getScalarSizeInBits());
8474 auto CanAddOneWithoutOverflow = [&]() {
8476 getRangeRef(ExitCount, RangeSignHint::HINT_RANGE_UNSIGNED);
8487 if (EvalSize > ExitCountSize && CanAddOneWithoutOverflow())
8517 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8518 assert(L->isLoopExiting(ExitingBlock) &&
8519 "Exiting block must actually branch out of the loop!");
8528 const auto *MaxExitCount =
8536 L->getExitingBlocks(ExitingBlocks);
8538 std::optional<unsigned> Res;
8539 for (
auto *ExitingBB : ExitingBlocks) {
8543 Res = std::gcd(*Res, Multiple);
8545 return Res.value_or(1);
8549 const SCEV *ExitCount) {
8579 assert(ExitingBlock &&
"Must pass a non-null exiting block!");
8580 assert(L->isLoopExiting(ExitingBlock) &&
8581 "Exiting block must actually branch out of the loop!");
8591 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
8593 return getBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this);
8595 return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this);
8605 return getPredicatedBackedgeTakenInfo(L).getExact(ExitingBlock,
this,
8608 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(ExitingBlock,
this,
8611 return getPredicatedBackedgeTakenInfo(L).getConstantMax(ExitingBlock,
this,
8619 return getPredicatedBackedgeTakenInfo(L).getExact(L,
this, &Preds);
8626 return getBackedgeTakenInfo(L).getExact(L,
this);
8628 return getBackedgeTakenInfo(L).getConstantMax(
this);
8630 return getBackedgeTakenInfo(L).getSymbolicMax(L,
this);
8637 return getPredicatedBackedgeTakenInfo(L).getSymbolicMax(L,
this, &Preds);
8642 return getPredicatedBackedgeTakenInfo(L).getConstantMax(
this, &Preds);
8646 return getBackedgeTakenInfo(L).isConstantMaxOrZero(
this);
8656 for (
PHINode &PN : Header->phis())
8657 if (Visited.
insert(&PN).second)
8661ScalarEvolution::BackedgeTakenInfo &
8662ScalarEvolution::getPredicatedBackedgeTakenInfo(
const Loop *L) {
8663 auto &BTI = getBackedgeTakenInfo(L);
8664 if (BTI.hasFullInfo())
8667 auto Pair = PredicatedBackedgeTakenCounts.try_emplace(L);
8670 return Pair.first->second;
8672 BackedgeTakenInfo
Result =
8673 computeBackedgeTakenCount(L,
true);
8675 return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
8678ScalarEvolution::BackedgeTakenInfo &
8679ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
8685 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
8686 BackedgeTakenCounts.try_emplace(L);
8688 return Pair.first->second;
8693 BackedgeTakenInfo
Result = computeBackedgeTakenCount(L);
8700 if (
Result.hasAnyInfo()) {
8703 auto LoopUsersIt = LoopUsers.find(L);
8704 if (LoopUsersIt != LoopUsers.end())
8706 forgetMemoizedResults(ToForget);
8709 for (PHINode &PN :
L->getHeader()->phis())
8710 ConstantEvolutionLoopExitValue.erase(&PN);
8718 return BackedgeTakenCounts.find(L)->second = std::move(Result);
8727 BackedgeTakenCounts.clear();
8728 PredicatedBackedgeTakenCounts.clear();
8729 BECountUsers.clear();
8730 LoopPropertiesCache.clear();
8731 ConstantEvolutionLoopExitValue.clear();
8732 ValueExprMap.clear();
8733 ValuesAtScopes.clear();
8734 ValuesAtScopesUsers.clear();
8735 LoopDispositions.clear();
8736 BlockDispositions.clear();
8737 UnsignedRanges.clear();
8738 SignedRanges.clear();
8739 ExprValueMap.clear();
8741 ConstantMultipleCache.clear();
8742 PredicatedSCEVRewrites.clear();
8744 FoldCacheUser.clear();
8746void ScalarEvolution::visitAndClearUsers(
8750 while (!Worklist.
empty()) {
8757 if (It != ValueExprMap.
end()) {
8758 eraseValueFromMap(It->first);
8761 ConstantEvolutionLoopExitValue.erase(PN);
8775 while (!LoopWorklist.
empty()) {
8779 forgetBackedgeTakenCounts(CurrL,
false);
8780 forgetBackedgeTakenCounts(CurrL,
true);
8783 for (
auto I = PredicatedSCEVRewrites.begin();
8784 I != PredicatedSCEVRewrites.end();) {
8785 std::pair<const SCEV *, const Loop *> Entry =
I->first;
8786 if (Entry.second == CurrL)
8787 PredicatedSCEVRewrites.erase(
I++);
8792 auto LoopUsersItr = LoopUsers.find(CurrL);
8793 if (LoopUsersItr != LoopUsers.end())
8798 visitAndClearUsers(Worklist, Visited, ToForget);
8800 LoopPropertiesCache.erase(CurrL);
8803 LoopWorklist.
append(CurrL->begin(), CurrL->end());
8805 forgetMemoizedResults(ToForget);
8822 visitAndClearUsers(Worklist, Visited, ToForget);
8824 forgetMemoizedResults(ToForget);
8836 struct InvalidationRootCollector {
8840 InvalidationRootCollector(
Loop *L) : L(L) {}
8842 bool follow(
const SCEV *S) {
8848 if (L->contains(AddRec->
getLoop()))
8853 bool isDone()
const {
return false; }
8856 InvalidationRootCollector
C(L);
8858 forgetMemoizedResults(
C.Roots);
8871 BlockDispositions.clear();
8872 LoopDispositions.clear();
8889 while (!Worklist.
empty()) {
8891 bool LoopDispoRemoved = LoopDispositions.erase(Curr);
8892 bool BlockDispoRemoved = BlockDispositions.erase(Curr);
8893 if (!LoopDispoRemoved && !BlockDispoRemoved)
8895 auto Users = SCEVUsers.find(Curr);
8896 if (
Users != SCEVUsers.end())
8909const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
8913 if (!isComplete() || ExitNotTaken.
empty())
8924 for (
const auto &ENT : ExitNotTaken) {
8925 const SCEV *BECount = ENT.ExactNotTaken;
8928 "We should only have known counts for exiting blocks that dominate "
8931 Ops.push_back(BECount);
8936 assert((Preds || ENT.hasAlwaysTruePredicate()) &&
8937 "Predicate should be always true!");
8946const ScalarEvolution::ExitNotTakenInfo *
8947ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
8948 const BasicBlock *ExitingBlock,
8949 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8950 for (
const auto &ENT : ExitNotTaken)
8951 if (ENT.ExitingBlock == ExitingBlock) {
8952 if (ENT.hasAlwaysTruePredicate())
8954 else if (Predicates) {
8964const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
8966 SmallVectorImpl<const SCEVPredicate *> *Predicates)
const {
8967 if (!getConstantMax())
8970 for (
const auto &ENT : ExitNotTaken)
8971 if (!ENT.hasAlwaysTruePredicate()) {
8979 "No point in having a non-constant max backedge taken count!");
8980 return getConstantMax();
8983const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
8985 SmallVectorImpl<const SCEVPredicate *> *Predicates) {
8993 for (
const auto &ENT : ExitNotTaken) {
8994 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken;
8997 "We should only have known counts for exiting blocks that "
9003 assert((Predicates || ENT.hasAlwaysTruePredicate()) &&
9004 "Predicate should be always true!");
9007 if (ExitCounts.
empty())
9016bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
9018 auto PredicateNotAlwaysTrue = [](
const ExitNotTakenInfo &ENT) {
9019 return !ENT.hasAlwaysTruePredicate();
9021 return MaxOrZero && !
any_of(ExitNotTaken, PredicateNotAlwaysTrue);
9037 this->ExactNotTaken = E = ConstantMaxNotTaken;
9038 this->SymbolicMaxNotTaken = SymbolicMaxNotTaken = ConstantMaxNotTaken;
9043 "Exact is not allowed to be less precise than Constant Max");
9046 "Exact is not allowed to be less precise than Symbolic Max");
9049 "Symbolic Max is not allowed to be less precise than Constant Max");
9052 "No point in having a non-constant max backedge taken count!");
9054 for (
const auto PredList : PredLists)
9055 for (
const auto *
P : PredList) {
9063 "Backedge count should be int");
9066 "Max backedge count should be int");
9079ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
9081 bool IsComplete,
const SCEV *ConstantMax,
bool MaxOrZero)
9082 : ConstantMax(ConstantMax), IsComplete(IsComplete), MaxOrZero(MaxOrZero) {
9083 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9085 ExitNotTaken.reserve(ExitCounts.
size());
9086 std::transform(ExitCounts.
begin(), ExitCounts.
end(),
9087 std::back_inserter(ExitNotTaken),
9088 [&](
const EdgeExitInfo &EEI) {
9089 BasicBlock *ExitBB = EEI.first;
9090 const ExitLimit &EL = EEI.second;
9091 return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken,
9092 EL.ConstantMaxNotTaken, EL.SymbolicMaxNotTaken,
9097 "No point in having a non-constant max backedge taken count!");
9101ScalarEvolution::BackedgeTakenInfo
9102ScalarEvolution::computeBackedgeTakenCount(
const Loop *L,
9103 bool AllowPredicates) {
9105 L->getExitingBlocks(ExitingBlocks);
9107 using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo;
9110 bool CouldComputeBECount =
true;
9112 const SCEV *MustExitMaxBECount =
nullptr;
9113 const SCEV *MayExitMaxBECount =
nullptr;
9114 bool MustExitMaxOrZero =
false;
9115 bool IsOnlyExit = ExitingBlocks.
size() == 1;
9126 bool ExitIfTrue = !L->contains(BI->getSuccessor(0));
9127 if (ExitIfTrue == CI->
isZero())
9131 ExitLimit EL = computeExitLimit(L, ExitBB, IsOnlyExit, AllowPredicates);
9133 assert((AllowPredicates || EL.Predicates.empty()) &&
9134 "Predicated exit limit when predicates are not allowed!");
9139 ++NumExitCountsComputed;
9143 CouldComputeBECount =
false;
9150 "Exact is known but symbolic isn't?");
9151 ++NumExitCountsNotComputed;
9166 DT.dominates(ExitBB, Latch)) {
9167 if (!MustExitMaxBECount) {
9168 MustExitMaxBECount = EL.ConstantMaxNotTaken;
9169 MustExitMaxOrZero = EL.MaxOrZero;
9172 EL.ConstantMaxNotTaken);
9176 MayExitMaxBECount = EL.ConstantMaxNotTaken;
9179 EL.ConstantMaxNotTaken);
9183 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
9187 bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
9193 for (
const auto &Pair : ExitCounts) {
9195 BECountUsers[Pair.second.ExactNotTaken].insert({
L, AllowPredicates});
9197 BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
9198 {
L, AllowPredicates});
9200 return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
9201 MaxBECount, MaxOrZero);
9204ScalarEvolution::ExitLimit
9205ScalarEvolution::computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
9206 bool IsOnlyExit,
bool AllowPredicates) {
9207 assert(
L->contains(ExitingBlock) &&
"Exit count for non-loop block?");
9211 if (!Latch || !DT.dominates(ExitingBlock, Latch))
9216 bool ExitIfTrue = !
L->contains(BI->getSuccessor(0));
9217 assert(ExitIfTrue ==
L->contains(BI->getSuccessor(1)) &&
9218 "It should have one successor in loop and one exit block!");
9229 if (!
L->contains(SBB)) {
9234 assert(Exit &&
"Exiting block must have at least one exit");
9235 return computeExitLimitFromSingleExitSwitch(
9236 L, SI, Exit, IsOnlyExit);
9243 const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9244 bool AllowPredicates) {
9245 ScalarEvolution::ExitLimitCacheTy Cache(L, ExitIfTrue, AllowPredicates);
9246 return computeExitLimitFromCondCached(Cache, L, ExitCond, ExitIfTrue,
9247 ControlsOnlyExit, AllowPredicates);
9250std::optional<ScalarEvolution::ExitLimit>
9251ScalarEvolution::ExitLimitCache::find(
const Loop *L,
Value *ExitCond,
9252 bool ExitIfTrue,
bool ControlsOnlyExit,
9253 bool AllowPredicates) {
9255 (void)this->ExitIfTrue;
9256 (void)this->AllowPredicates;
9258 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9259 this->AllowPredicates == AllowPredicates &&
9260 "Variance in assumed invariant key components!");
9261 auto Itr = TripCountMap.find({ExitCond, ControlsOnlyExit});
9262 if (Itr == TripCountMap.end())
9263 return std::nullopt;
9267void ScalarEvolution::ExitLimitCache::insert(
const Loop *L,
Value *ExitCond,
9269 bool ControlsOnlyExit,
9270 bool AllowPredicates,
9272 assert(this->L == L && this->ExitIfTrue == ExitIfTrue &&
9273 this->AllowPredicates == AllowPredicates &&
9274 "Variance in assumed invariant key components!");
9276 auto InsertResult = TripCountMap.insert({{ExitCond, ControlsOnlyExit}, EL});
9277 assert(InsertResult.second &&
"Expected successful insertion!");
9282ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
9283 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9284 bool ControlsOnlyExit,
bool AllowPredicates) {
9286 if (
auto MaybeEL = Cache.find(L, ExitCond, ExitIfTrue, ControlsOnlyExit,
9290 ExitLimit EL = computeExitLimitFromCondImpl(
9291 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates);
9292 Cache.insert(L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates, EL);
9296ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
9297 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9298 bool ControlsOnlyExit,
bool AllowPredicates) {
9300 if (
auto LimitFromBinOp = computeExitLimitFromCondFromBinOp(
9301 Cache, L, ExitCond, ExitIfTrue, ControlsOnlyExit, AllowPredicates))
9302 return *LimitFromBinOp;
9308 computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue, ControlsOnlyExit);
9309 if (EL.hasFullInfo() || !AllowPredicates)
9313 return computeExitLimitFromICmp(L, ExitCondICmp, ExitIfTrue,
9333 const WithOverflowInst *WO;
9348 auto EL = computeExitLimitFromICmp(L, Pred,
LHS,
getConstant(NewRHSC),
9349 ControlsOnlyExit, AllowPredicates);
9350 if (EL.hasAnyInfo())
9355 return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9358std::optional<ScalarEvolution::ExitLimit>
9359ScalarEvolution::computeExitLimitFromCondFromBinOp(
9360 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
9361 bool ControlsOnlyExit,
bool AllowPredicates) {
9370 return std::nullopt;
9375 bool EitherMayExit = IsAnd ^ ExitIfTrue;
9376 ExitLimit EL0 = computeExitLimitFromCondCached(
9377 Cache, L, Op0, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9379 ExitLimit EL1 = computeExitLimitFromCondCached(
9380 Cache, L, Op1, ExitIfTrue, ControlsOnlyExit && !EitherMayExit,
9384 const Constant *NeutralElement = ConstantInt::get(ExitCond->
getType(), IsAnd);
9386 return Op1 == NeutralElement ? EL0 : EL1;
9388 return Op0 == NeutralElement ? EL1 : EL0;
9393 if (EitherMayExit) {
9403 ConstantMaxBECount = EL1.ConstantMaxNotTaken;
9405 ConstantMaxBECount = EL0.ConstantMaxNotTaken;
9408 EL1.ConstantMaxNotTaken);
9410 SymbolicMaxBECount = EL1.SymbolicMaxNotTaken;
9412 SymbolicMaxBECount = EL0.SymbolicMaxNotTaken;
9415 EL0.SymbolicMaxNotTaken, EL1.SymbolicMaxNotTaken, UseSequentialUMin);
9419 if (EL0.ExactNotTaken == EL1.ExactNotTaken)
9420 BECount = EL0.ExactNotTaken;
9433 SymbolicMaxBECount =
9435 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
9439ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9440 const Loop *L, ICmpInst *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
9441 bool AllowPredicates) {
9453 ExitLimit EL = computeExitLimitFromICmp(L, Pred,
LHS,
RHS, ControlsOnlyExit,
9455 if (EL.hasAnyInfo())
9458 auto *ExhaustiveCount =
9459 computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
9462 return ExhaustiveCount;
9464 return computeShiftCompareExitLimit(ExitCond->
getOperand(0),
9467ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
9469 bool ControlsOnlyExit,
bool AllowPredicates) {
9494 ConstantRange CompRange =
9512 InnerLHS = ZExt->getOperand();
9559 if (EL.hasAnyInfo())
9576 if (EL.hasAnyInfo())
return EL;
9608 ExitLimit EL = howManyLessThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9610 if (EL.hasAnyInfo())
9626 ExitLimit EL = howManyGreaterThans(
LHS,
RHS, L, IsSigned, ControlsOnlyExit,
9628 if (EL.hasAnyInfo())
9639ScalarEvolution::ExitLimit
9640ScalarEvolution::computeExitLimitFromSingleExitSwitch(
const Loop *L,
9642 BasicBlock *ExitingBlock,
9643 bool ControlsOnlyExit) {
9644 assert(!
L->contains(ExitingBlock) &&
"Not an exiting block!");
9647 if (
Switch->getDefaultDest() == ExitingBlock)
9651 "Default case must not exit the loop!");
9657 if (EL.hasAnyInfo())
9669 "Evaluation of SCEV at constant didn't fold correctly?");
9673ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
9683 const BasicBlock *Predecessor =
L->getLoopPredecessor();
9689 auto MatchPositiveShift =
9692 using namespace PatternMatch;
9694 ConstantInt *ShiftAmt;
9696 OutOpCode = Instruction::LShr;
9698 OutOpCode = Instruction::AShr;
9700 OutOpCode = Instruction::Shl;
9715 auto MatchShiftRecurrence =
9717 std::optional<Instruction::BinaryOps> PostShiftOpCode;
9732 if (MatchPositiveShift(
LHS, V, OpC)) {
9733 PostShiftOpCode = OpC;
9739 if (!PNOut || PNOut->getParent() !=
L->getHeader())
9742 Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
9748 MatchPositiveShift(BEValue, OpLHS, OpCodeOut) &&
9755 (!PostShiftOpCode || *PostShiftOpCode == OpCodeOut);
9760 if (!MatchShiftRecurrence(
LHS, PN, OpCode))
9772 ConstantInt *StableValue =
nullptr;
9777 case Instruction::AShr: {
9785 StableValue = ConstantInt::get(Ty, 0);
9787 StableValue = ConstantInt::get(Ty, -1,
true);
9793 case Instruction::LShr:
9794 case Instruction::Shl:
9804 "Otherwise cannot be an operand to a branch instruction");
9806 if (
Result->isNullValue()) {
9808 const SCEV *UpperBound =
9825 if (
const Function *
F = CI->getCalledFunction())
9834 if (!L->contains(
I))
return false;
9839 return L->getHeader() ==
I->getParent();
9915 if (!
I)
return nullptr;
9928 std::vector<Constant*> Operands(
I->getNumOperands());
9930 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
9934 if (!Operands[i])
return nullptr;
9939 if (!
C)
return nullptr;
9961 if (IncomingVal != CurrentVal) {
9964 IncomingVal = CurrentVal;
9976ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
9979 auto [
I,
Inserted] = ConstantEvolutionLoopExitValue.try_emplace(PN);
9988 DenseMap<Instruction *, Constant *> CurrentIterVals;
9990 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
9996 for (PHINode &
PHI : Header->phis()) {
9998 CurrentIterVals[&
PHI] = StartCST;
10000 if (!CurrentIterVals.
count(PN))
10001 return RetVal =
nullptr;
10007 "BEs is <= MaxBruteForceIterations which is an 'unsigned'!");
10010 unsigned IterationNum = 0;
10012 for (; ; ++IterationNum) {
10013 if (IterationNum == NumIterations)
10014 return RetVal = CurrentIterVals[PN];
10018 DenseMap<Instruction *, Constant *> NextIterVals;
10023 NextIterVals[PN] = NextPHI;
10025 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
10031 for (
const auto &
I : CurrentIterVals) {
10033 if (!
PHI ||
PHI == PN ||
PHI->getParent() != Header)
continue;
10038 for (
const auto &
I : PHIsToCompute) {
10039 PHINode *
PHI =
I.first;
10042 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10045 if (NextPHI !=
I.second)
10046 StoppedEvolving =
false;
10051 if (StoppedEvolving)
10052 return RetVal = CurrentIterVals[PN];
10054 CurrentIterVals.swap(NextIterVals);
10058const SCEV *ScalarEvolution::computeExitCountExhaustively(
const Loop *L,
10068 DenseMap<Instruction *, Constant *> CurrentIterVals;
10070 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
10073 assert(Latch &&
"Should follow from NumIncomingValues == 2!");
10075 for (PHINode &
PHI : Header->phis()) {
10077 CurrentIterVals[&
PHI] = StartCST;
10079 if (!CurrentIterVals.
count(PN))
10087 for (
unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
10094 if (CondVal->getValue() == uint64_t(ExitWhen)) {
10095 ++NumBruteForceTripCountsComputed;
10100 DenseMap<Instruction *, Constant *> NextIterVals;
10106 for (
const auto &
I : CurrentIterVals) {
10108 if (!
PHI ||
PHI->getParent() != Header)
continue;
10111 for (PHINode *
PHI : PHIsToCompute) {
10113 if (NextPHI)
continue;
10115 Value *BEValue =
PHI->getIncomingValueForBlock(Latch);
10118 CurrentIterVals.
swap(NextIterVals);
10129 for (
auto &LS : Values)
10131 return LS.second ? LS.second : V;
10136 const SCEV *
C = computeSCEVAtScope(V, L);
10137 for (
auto &LS :
reverse(ValuesAtScopes[V]))
10138 if (LS.first == L) {
10141 ValuesAtScopesUsers[
C].push_back({L, V});
10152 switch (V->getSCEVType()) {
10192 assert(!
C->getType()->isPointerTy() &&
10193 "Can only have one pointer, and it must be last");
10218const SCEV *ScalarEvolution::getWithOperands(
const SCEV *S,
10219 SmallVectorImpl<SCEVUse> &NewOps) {
10254const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
10255 switch (
V->getSCEVType()) {
10266 for (
unsigned i = 0, e = AddRec->
getNumOperands(); i != e; ++i) {
10277 for (++i; i !=
e; ++i)
10322 for (
unsigned i = 0, e =
Ops.size(); i != e; ++i) {
10332 for (++i; i !=
e; ++i) {
10337 return getWithOperands(V, NewOps);
10352 const Loop *CurrLoop = this->LI[
I->getParent()];
10363 if (BackedgeTakenCount->
isZero()) {
10364 Value *InitValue =
nullptr;
10365 bool MultipleInitValues =
false;
10371 MultipleInitValues =
true;
10376 if (!MultipleInitValues && InitValue)
10385 unsigned InLoopPred =
10396 getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), CurrLoop);
10410 SmallVector<Constant *, 4> Operands;
10411 Operands.
reserve(
I->getNumOperands());
10412 bool MadeImprovement =
false;
10427 MadeImprovement |= OrigV != OpV;
10432 assert(
C->getType() ==
Op->getType() &&
"Type mismatch");
10437 if (!MadeImprovement)
10458const SCEV *ScalarEvolution::stripInjectiveFunctions(
const SCEV *S)
const {
10460 return stripInjectiveFunctions(ZExt->getOperand());
10462 return stripInjectiveFunctions(SExt->getOperand());
10480 assert(
A != 0 &&
"A must be non-zero.");
10496 if (MinTZ < Mult2 && L->getLoopPredecessor())
10498 if (MinTZ < Mult2) {
10521 APInt AD =
A.lshr(Mult2).trunc(BW - Mult2);
10541static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
10547 LLVM_DEBUG(
dbgs() << __func__ <<
": analyzing quadratic addrec: "
10548 << *AddRec <<
'\n');
10551 if (!LC || !MC || !
NC) {
10552 LLVM_DEBUG(
dbgs() << __func__ <<
": coefficients are not constant\n");
10553 return std::nullopt;
10559 assert(!
N.isZero() &&
"This is not a quadratic addrec");
10567 N =
N.sext(NewWidth);
10568 M = M.sext(NewWidth);
10569 L = L.sext(NewWidth);
10586 <<
"x + " <<
C <<
", coeff bw: " << NewWidth
10587 <<
", multiplied by " <<
T <<
'\n');
10596 std::optional<APInt>
Y) {
10598 unsigned W = std::max(
X->getBitWidth(),
Y->getBitWidth());
10601 return XW.
slt(YW) ? *
X : *
Y;
10604 return std::nullopt;
10605 return X ? *
X : *
Y;
10622 return std::nullopt;
10623 unsigned W =
X->getBitWidth();
10643static std::optional<APInt>
10649 return std::nullopt;
10652 LLVM_DEBUG(
dbgs() << __func__ <<
": solving for unsigned overflow\n");
10653 std::optional<APInt>
X =
10656 return std::nullopt;
10661 return std::nullopt;
10676static std::optional<APInt>
10680 "Starting value of addrec should be 0");
10681 LLVM_DEBUG(
dbgs() << __func__ <<
": solving boundary crossing for range "
10682 <<
Range <<
", addrec " << *AddRec <<
'\n');
10686 "Addrec's initial value should be in range");
10692 return std::nullopt;
10702 auto SolveForBoundary =
10703 [&](
APInt Bound) -> std::pair<std::optional<APInt>,
bool> {
10706 LLVM_DEBUG(
dbgs() <<
"SolveQuadraticAddRecRange: checking boundary "
10707 << Bound <<
" (before multiplying by " << M <<
")\n");
10710 std::optional<APInt> SO;
10713 "signed overflow\n");
10717 "unsigned overflow\n");
10718 std::optional<APInt> UO =
10721 auto LeavesRange = [&] (
const APInt &
X) {
10738 return {std::nullopt,
false};
10743 if (LeavesRange(*Min))
10744 return { Min,
true };
10745 std::optional<APInt> Max = Min == SO ? UO : SO;
10746 if (LeavesRange(*Max))
10747 return { Max,
true };
10750 return {std::nullopt,
true};
10757 auto SL = SolveForBoundary(
Lower);
10758 auto SU = SolveForBoundary(
Upper);
10761 if (!SL.second || !SU.second)
10762 return std::nullopt;
10805ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(
const SCEV *V,
10807 bool ControlsOnlyExit,
10808 bool AllowPredicates) {
10819 if (
C->getValue()->isZero())
return C;
10823 const SCEVAddRecExpr *AddRec =
10826 if (!AddRec && AllowPredicates)
10832 if (!AddRec || AddRec->
getLoop() != L)
10843 return ExitLimit(R, R, R,
false, Predicates);
10901 const SCEV *DistancePlusOne =
getAddExpr(Distance, One);
10927 const SCEV *
Exact =
10935 const SCEV *SymbolicMax =
10937 return ExitLimit(
Exact, ConstantMax, SymbolicMax,
false, Predicates);
10946 AllowPredicates ? &Predicates :
nullptr, *
this, L);
10954 return ExitLimit(
E, M, S,
false, Predicates);
10957ScalarEvolution::ExitLimit
10958ScalarEvolution::howFarToNonZero(
const SCEV *V,
const Loop *L) {
10966 if (!
C->getValue()->isZero())
10976std::pair<const BasicBlock *, const BasicBlock *>
10977ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
10988 if (
const Loop *L = LI.getLoopFor(BB))
10989 return {
L->getLoopPredecessor(),
L->getHeader()};
10991 return {
nullptr, BB};
11000 if (
A ==
B)
return true;
11015 if (ComputesEqualValues(AI, BI))
11023 const SCEV *Op0, *Op1;
11042 auto TrivialCase = [&](
bool TriviallyTrue) {
11051 const SCEV *NewLHS, *NewRHS;
11075 return TrivialCase(
false);
11076 return TrivialCase(
true);
11099 const APInt &
RA = RC->getAPInt();
11101 bool SimplifiedByConstantRange =
false;
11106 return TrivialCase(
true);
11108 return TrivialCase(
false);
11117 Changed = SimplifiedByConstantRange =
true;
11121 if (!SimplifiedByConstantRange) {
11138 assert(!
RA.isMinValue() &&
"Should have been caught earlier!");
11144 assert(!
RA.isMaxValue() &&
"Should have been caught earlier!");
11150 assert(!
RA.isMinSignedValue() &&
"Should have been caught earlier!");
11156 assert(!
RA.isMaxSignedValue() &&
"Should have been caught earlier!");
11168 return TrivialCase(
true);
11170 return TrivialCase(
false);
11275 auto NonRecursive = [OrNegative](
const SCEV *S) {
11277 return C->getAPInt().isPowerOf2() ||
11278 (OrNegative &&
C->getAPInt().isNegatedPowerOf2());
11284 if (NonRecursive(S))
11310 APInt C = Cst->getAPInt();
11311 return C.urem(M) == 0;
11319 const SCEV *SmodM =
11334 for (
auto *
A : Assumptions)
11335 if (
A->implies(
P, *
this))
11348std::pair<const SCEV *, const SCEV *>
11351 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *
this);
11353 return { Start, Start };
11355 const SCEV *
PostInc = SCEVPostIncRewriter::rewrite(S, L, *
this);
11364 getUsedLoops(LHS, LoopsUsed);
11365 getUsedLoops(RHS, LoopsUsed);
11367 if (LoopsUsed.
empty())
11372 for (
const auto *L1 : LoopsUsed)
11373 for (
const auto *L2 : LoopsUsed)
11374 assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
11375 DT.dominates(L2->getHeader(), L1->getHeader())) &&
11376 "Domination relationship is not a linear order");
11406 SplitRHS.second) &&
11418 if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
11422 return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
11432 return std::nullopt;
11447 if (KnownWithoutContext)
11448 return KnownWithoutContext;
11455 return std::nullopt;
11461 const Loop *L = LHS->getLoop();
11466std::optional<ScalarEvolution::MonotonicPredicateType>
11469 auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);
11475 auto ResultSwapped =
11478 assert(*ResultSwapped != *Result &&
11479 "monotonicity should flip as we flip the predicate");
11486std::optional<ScalarEvolution::MonotonicPredicateType>
11487ScalarEvolution::getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *LHS,
11501 return std::nullopt;
11505 "Should be greater or less!");
11509 if (!LHS->hasNoUnsignedWrap())
11510 return std::nullopt;
11514 "Relational predicate is either signed or unsigned!");
11515 if (!
LHS->hasNoSignedWrap())
11516 return std::nullopt;
11518 const SCEV *Step =
LHS->getStepRecurrence(*
this);
11526 return std::nullopt;
11529std::optional<ScalarEvolution::LoopInvariantPredicate>
11536 return std::nullopt;
11543 if (!ArLHS || ArLHS->
getLoop() != L)
11544 return std::nullopt;
11548 return std::nullopt;
11574 return std::nullopt;
11611 return std::nullopt;
11614std::optional<ScalarEvolution::LoopInvariantPredicate>
11619 Pred, LHS, RHS, L, CtxI, MaxIter))
11629 Pred, LHS, RHS, L, CtxI,
Op))
11631 return std::nullopt;
11634std::optional<ScalarEvolution::LoopInvariantPredicate>
11649 return std::nullopt;
11656 if (!AR || AR->
getLoop() != L)
11657 return std::nullopt;
11662 Pred = Pred.dropSameSign();
11666 return std::nullopt;
11672 if (Step != One && Step != MinusOne)
11673 return std::nullopt;
11679 return std::nullopt;
11685 return std::nullopt;
11693 if (Step == MinusOne)
11697 return std::nullopt;
11703bool ScalarEvolution::isKnownPredicateViaConstantRanges(
CmpPredicate Pred,
11709 auto CheckRange = [&](
bool IsSigned) {
11712 return RangeLHS.
icmp(Pred, RangeRHS);
11721 if (CheckRange(
true) || CheckRange(
false))
11730bool ScalarEvolution::isKnownPredicateViaNoOverflow(CmpPredicate Pred,
11739 SCEVUse XNonConstOp, XConstOp;
11740 SCEVUse YNonConstOp, YConstOp;
11744 if (!splitBinaryAdd(
X, XConstOp, XNonConstOp, XFlagsPresent)) {
11747 XFlagsPresent = ExpectedFlags;
11752 if (!splitBinaryAdd(
Y, YConstOp, YNonConstOp, YFlagsPresent)) {
11755 YFlagsPresent = ExpectedFlags;
11758 if (YNonConstOp != XNonConstOp)
11766 if ((YFlagsPresent & ExpectedFlags) != ExpectedFlags)
11769 (XFlagsPresent & ExpectedFlags) != ExpectedFlags) {
11829bool ScalarEvolution::isKnownPredicateViaSplitting(CmpPredicate Pred,
11850bool ScalarEvolution::isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
11851 const SCEV *
LHS,
const SCEV *
RHS) {
11856 return any_of(*BB, [&](
const Instruction &
I) {
11857 using namespace llvm::PatternMatch;
11862 isImpliedCond(Pred,
LHS,
RHS, Condition,
false);
11876 if (!L || !DT.isReachableFromEntry(L->getHeader()))
11881 "This cannot be done on broken IR!");
11884 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
11893 if (LoopContinuePredicate &&
11894 isImpliedCond(Pred, LHS, RHS, LoopContinuePredicate->
getCondition(),
11895 LoopContinuePredicate->
getSuccessor(0) != L->getHeader()))
11900 if (WalkingBEDominatingConds)
11906 const auto &BETakenInfo = getBackedgeTakenInfo(L);
11907 const SCEV *LatchBECount = BETakenInfo.getExact(Latch,
this);
11914 const SCEV *LoopCounter =
11922 for (
auto &AssumeVH : AC.assumptions()) {
11929 if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0),
false))
11933 if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
11936 for (
DomTreeNode *DTN = DT[Latch], *HeaderDTN = DT[L->getHeader()];
11937 DTN != HeaderDTN; DTN = DTN->getIDom()) {
11938 assert(DTN &&
"should reach the loop header before reaching the root!");
11941 if (isImpliedViaGuard(BB, Pred, LHS, RHS))
11959 if (isImpliedCond(Pred, LHS, RHS, ContBr->
getCondition(),
11972 if (!DT.isReachableFromEntry(BB))
11976 "This cannot be done on broken IR!");
11984 const bool ProvingStrictComparison =
11986 bool ProvedNonStrictComparison =
false;
11987 bool ProvedNonEquality =
false;
11990 if (!ProvedNonStrictComparison)
11991 ProvedNonStrictComparison = Fn(NonStrictPredicate);
11992 if (!ProvedNonEquality)
11994 if (ProvedNonStrictComparison && ProvedNonEquality)
11999 if (ProvingStrictComparison) {
12001 return isKnownViaNonRecursiveReasoning(
P, LHS, RHS);
12003 if (SplitAndProve(ProofFn))
12008 auto ProveViaCond = [&](
const Value *Condition,
bool Inverse) {
12010 if (isImpliedCond(Pred, LHS, RHS, Condition,
Inverse, CtxI))
12012 if (ProvingStrictComparison) {
12014 return isImpliedCond(
P, LHS, RHS, Condition,
Inverse, CtxI);
12016 if (SplitAndProve(ProofFn))
12025 const Loop *ContainingLoop = LI.getLoopFor(BB);
12027 if (ContainingLoop && ContainingLoop->
getHeader() == BB)
12031 for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
12032 Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
12035 if (!BlockEntryPredicate)
12044 for (
auto &AssumeVH : AC.assumptions()) {
12048 if (!DT.dominates(CI, BB))
12051 if (ProveViaCond(CI->getArgOperand(0),
false))
12057 F.getParent(), Intrinsic::experimental_guard);
12059 for (
const auto *GU : GuardDecl->users())
12061 if (Guard->getFunction() == BB->
getParent() && DT.dominates(Guard, BB))
12062 if (ProveViaCond(Guard->getArgOperand(0),
false))
12077 "LHS is not available at Loop Entry");
12079 "RHS is not available at Loop Entry");
12081 if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS))
12092 if (FoundCondValue ==
12096 if (!PendingLoopPredicates.insert(FoundCondValue).second)
12100 [&]() { PendingLoopPredicates.erase(FoundCondValue); });
12103 const Value *Op0, *Op1;
12106 return isImpliedCond(Pred,
LHS,
RHS, Op0,
Inverse, CtxI) ||
12110 return isImpliedCond(Pred,
LHS,
RHS, Op0, Inverse, CtxI) ||
12111 isImpliedCond(Pred,
LHS,
RHS, Op1, Inverse, CtxI);
12115 if (!ICI)
return false;
12119 CmpPredicate FoundPred;
12128 return isImpliedCond(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS, CtxI);
12131bool ScalarEvolution::isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
12132 const SCEV *
RHS, CmpPredicate FoundPred,
12133 const SCEV *FoundLHS,
const SCEV *FoundRHS,
12134 const Instruction *CtxI) {
12144 auto *WideType = FoundLHS->
getType();
12156 TruncFoundLHS, TruncFoundRHS, CtxI))
12182 return isImpliedCondBalancedTypes(Pred,
LHS,
RHS, FoundPred, FoundLHS,
12186bool ScalarEvolution::isImpliedCondBalancedTypes(
12191 "Types should be balanced!");
12198 if (FoundLHS == FoundRHS)
12202 if (
LHS == FoundRHS ||
RHS == FoundLHS) {
12214 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12231 LHS, FoundLHS, FoundRHS, CtxI);
12233 return isImpliedCondOperands(*
P,
LHS,
RHS, FoundRHS, FoundLHS, CtxI);
12255 assert(P1 != P2 &&
"Handled earlier!");
12259 if (IsSignFlippedPredicate(Pred, FoundPred)) {
12263 return isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI);
12266 CmpPredicate CanonicalPred = Pred, CanonicalFoundPred = FoundPred;
12267 const SCEV *CanonicalLHS =
LHS, *CanonicalRHS =
RHS,
12268 *CanonicalFoundLHS = FoundLHS, *CanonicalFoundRHS = FoundRHS;
12273 std::swap(CanonicalFoundLHS, CanonicalFoundRHS);
12284 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12285 CanonicalRHS, CanonicalFoundLHS,
12286 CanonicalFoundRHS);
12291 return isImpliedCondOperands(CanonicalFoundPred, CanonicalLHS,
12292 CanonicalRHS, CanonicalFoundLHS,
12293 CanonicalFoundRHS);
12300 const SCEVConstant *
C =
nullptr;
12301 const SCEV *
V =
nullptr;
12319 if (Min ==
C->getAPInt()) {
12324 APInt SharperMin = Min + 1;
12327 case ICmpInst::ICMP_SGE:
12328 case ICmpInst::ICMP_UGE:
12331 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(SharperMin),
12336 case ICmpInst::ICMP_SGT:
12337 case ICmpInst::ICMP_UGT:
12347 if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min), CtxI))
12352 case ICmpInst::ICMP_SLE:
12353 case ICmpInst::ICMP_ULE:
12354 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12355 LHS, V, getConstant(SharperMin), CtxI))
12359 case ICmpInst::ICMP_SLT:
12360 case ICmpInst::ICMP_ULT:
12361 if (isImpliedCondOperands(ICmpInst::getSwappedCmpPredicate(Pred), RHS,
12362 LHS, V, getConstant(Min), CtxI))
12376 if (isImpliedCondOperands(Pred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12380 if (isImpliedCondOperands(FoundPred,
LHS,
RHS, FoundLHS, FoundRHS, CtxI))
12383 if (isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, FoundPred, FoundLHS, FoundRHS))
12399std::optional<APInt>
12406 APInt DiffMul(BW, 1);
12409 for (
unsigned I = 0;
I < 8; ++
I) {
12418 if (LAR->getLoop() != MAR->getLoop())
12419 return std::nullopt;
12423 if (!LAR->isAffine() || !MAR->isAffine())
12424 return std::nullopt;
12426 if (LAR->getStepRecurrence(*
this) != MAR->getStepRecurrence(*
this))
12427 return std::nullopt;
12429 Less = LAR->getStart();
12430 More = MAR->getStart();
12435 auto MatchConstMul =
12436 [](
const SCEV *S) -> std::optional<std::pair<const SCEV *, APInt>> {
12441 return std::nullopt;
12443 if (
auto MatchedMore = MatchConstMul(More)) {
12444 if (
auto MatchedLess = MatchConstMul(
Less)) {
12445 if (MatchedMore->second == MatchedLess->second) {
12446 More = MatchedMore->first;
12447 Less = MatchedLess->first;
12448 DiffMul *= MatchedMore->second;
12459 Diff +=
C->getAPInt() * DiffMul;
12462 Diff -=
C->getAPInt() * DiffMul;
12465 Multiplicity[S] +=
Mul;
12467 auto Decompose = [&](
const SCEV *S,
int Mul) {
12474 Decompose(More, 1);
12475 Decompose(
Less, -1);
12479 const SCEV *NewMore =
nullptr, *NewLess =
nullptr;
12480 for (
const auto &[S,
Mul] : Multiplicity) {
12485 return std::nullopt;
12487 }
else if (
Mul == -1) {
12489 return std::nullopt;
12492 return std::nullopt;
12496 if (NewMore == More || NewLess ==
Less)
12497 return std::nullopt;
12503 if (!More && !
Less)
12507 if (!More || !
Less)
12508 return std::nullopt;
12512 return std::nullopt;
12515bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
12537 const auto *Latch = L->getLoopLatch();
12540 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12549 const auto *Latch = L->getLoopLatch();
12552 if (!L->contains(ContextBB) || !Latch || !DT.
dominates(ContextBB, Latch))
12562bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
12565 const SCEV *FoundLHS,
12566 const SCEV *FoundRHS) {
12575 if (!AddRecFoundLHS)
12582 const Loop *
L = AddRecFoundLHS->getLoop();
12583 if (L != AddRecLHS->getLoop())
12622 if (!RDiff || *LDiff != *RDiff)
12625 if (LDiff->isMinValue())
12628 APInt FoundRHSLimit;
12631 FoundRHSLimit = -(*RDiff);
12643bool ScalarEvolution::isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
12644 const SCEV *
RHS,
const SCEV *FoundLHS,
12645 const SCEV *FoundRHS,
unsigned Depth) {
12646 const PHINode *LPhi =
nullptr, *RPhi =
nullptr;
12650 bool Erased = PendingMerges.erase(LPhi);
12651 assert(Erased &&
"Failed to erase LPhi!");
12655 bool Erased = PendingMerges.erase(RPhi);
12656 assert(Erased &&
"Failed to erase RPhi!");
12664 if (!PendingMerges.insert(Phi).second)
12678 if (!PendingMerges.insert(Phi).second)
12684 if (!LPhi && !RPhi)
12695 assert(LPhi &&
"LPhi should definitely be a SCEVUnknown Phi!");
12699 auto ProvedEasily = [&](
const SCEV *
S1,
const SCEV *S2) {
12700 return isKnownViaNonRecursiveReasoning(Pred,
S1, S2) ||
12701 isImpliedCondOperandsViaRanges(Pred,
S1, S2, Pred, FoundLHS, FoundRHS) ||
12702 isImpliedViaOperations(Pred,
S1, S2, FoundLHS, FoundRHS,
Depth);
12705 if (RPhi && RPhi->getParent() == LBB) {
12712 const SCEV *
R =
getSCEV(RPhi->getIncomingValueForBlock(IncBB));
12713 if (!ProvedEasily(L, R))
12724 auto *RLoop = RAR->
getLoop();
12725 auto *Predecessor = RLoop->getLoopPredecessor();
12726 assert(Predecessor &&
"Loop with AddRec with no predecessor?");
12728 if (!ProvedEasily(L1, RAR->
getStart()))
12730 auto *Latch = RLoop->getLoopLatch();
12731 assert(Latch &&
"Loop with AddRec with no latch?");
12752 if (
auto *Loop = LI.getLoopFor(LBB))
12755 if (!ProvedEasily(L,
RHS))
12762bool ScalarEvolution::isImpliedCondOperandsViaShift(CmpPredicate Pred,
12765 const SCEV *FoundLHS,
12766 const SCEV *FoundRHS) {
12769 if (
RHS == FoundRHS) {
12774 if (
LHS != FoundLHS)
12781 Value *Shiftee, *ShiftValue;
12783 using namespace PatternMatch;
12784 if (
match(SUFoundRHS->getValue(),
12786 auto *ShifteeS =
getSCEV(Shiftee);
12804bool ScalarEvolution::isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
12806 const SCEV *FoundLHS,
12807 const SCEV *FoundRHS,
12808 const Instruction *CtxI) {
12809 return isImpliedCondOperandsViaRanges(Pred,
LHS,
RHS, Pred, FoundLHS,
12811 isImpliedCondOperandsViaNoOverflow(Pred,
LHS,
RHS, FoundLHS,
12813 isImpliedCondOperandsViaShift(Pred,
LHS,
RHS, FoundLHS, FoundRHS) ||
12814 isImpliedCondOperandsViaAddRecStart(Pred,
LHS,
RHS, FoundLHS, FoundRHS,
12816 isImpliedCondOperandsHelper(Pred,
LHS,
RHS, FoundLHS, FoundRHS);
12820template <
typename MinMaxExprType>
12822 const SCEV *Candidate) {
12827 return is_contained(MinMaxExpr->operands(), Candidate);
12840 const SCEV *LStart, *RStart, *Step;
12890bool ScalarEvolution::isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
12892 const SCEV *FoundLHS,
12893 const SCEV *FoundRHS,
12897 "LHS and RHS have different sizes?");
12900 "FoundLHS and FoundRHS have different sizes?");
12934 auto GetOpFromSExt = [&](
const SCEV *S) ->
const SCEV * {
12936 return Ext->getOperand();
12943 auto *OrigLHS =
LHS;
12944 auto *OrigFoundLHS = FoundLHS;
12945 LHS = GetOpFromSExt(
LHS);
12946 FoundLHS = GetOpFromSExt(FoundLHS);
12949 auto IsSGTViaContext = [&](
const SCEV *
S1,
const SCEV *S2) {
12952 FoundRHS,
Depth + 1);
12965 if (!LHSAddExpr->hasNoSignedWrap())
12968 SCEVUse LL = LHSAddExpr->getOperand(0);
12969 SCEVUse LR = LHSAddExpr->getOperand(1);
12973 auto IsSumGreaterThanRHS = [&](
const SCEV *
S1,
const SCEV *S2) {
12974 return IsSGTViaContext(
S1, MinusOne) && IsSGTViaContext(S2,
RHS);
12979 if (IsSumGreaterThanRHS(LL, LR) || IsSumGreaterThanRHS(LR, LL))
12985 using namespace llvm::PatternMatch;
13004 if (!Numerator || Numerator->getType() != FoundLHS->
getType())
13012 auto *DTy = Denominator->getType();
13013 auto *FRHSTy = FoundRHS->
getType();
13014 if (DTy->isPointerTy() != FRHSTy->isPointerTy())
13033 IsSGTViaContext(FoundRHSExt, DenomMinusTwo))
13044 auto *NegDenomMinusOne =
getMinusSCEV(MinusOne, DenominatorExt);
13046 IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
13054 if (isImpliedViaMerge(Pred, OrigLHS,
RHS, OrigFoundLHS, FoundRHS,
Depth + 1))
13087bool ScalarEvolution::isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
13091 isKnownPredicateViaConstantRanges(Pred,
LHS,
RHS) ||
13094 isKnownPredicateViaNoOverflow(Pred,
LHS,
RHS);
13097bool ScalarEvolution::isImpliedCondOperandsHelper(CmpPredicate Pred,
13100 const SCEV *FoundLHS,
13101 const SCEV *FoundRHS) {
13137 if (isImpliedViaOperations(Pred,
LHS,
RHS, FoundLHS, FoundRHS))
13143bool ScalarEvolution::isImpliedCondOperandsViaRanges(
13144 CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS, CmpPredicate FoundPred,
13145 const SCEV *FoundLHS,
const SCEV *FoundRHS) {
13159 ConstantRange FoundLHSRange =
13163 ConstantRange LHSRange = FoundLHSRange.
add(ConstantRange(*Addend));
13170 return LHSRange.
icmp(Pred, ConstRHS);
13173bool ScalarEvolution::canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
13186 return (std::move(MaxValue) - MaxStrideMinusOne).slt(MaxRHS);
13194 return (std::move(MaxValue) - MaxStrideMinusOne).ult(MaxRHS);
13197bool ScalarEvolution::canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
13209 return (std::move(MinValue) + MaxStrideMinusOne).sgt(MinRHS);
13217 return (std::move(MinValue) + MaxStrideMinusOne).ugt(MinRHS);
13229const SCEV *ScalarEvolution::computeMaxBECountForLT(
const SCEV *Start,
13230 const SCEV *Stride,
13261 APInt Limit = MaxValue - (StrideForMaxBECount - 1);
13272 :
APIntOps::umax(MaxEnd, MinStart);
13279ScalarEvolution::howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
13280 const Loop *L,
bool IsSigned,
13281 bool ControlsOnlyExit,
bool AllowPredicates) {
13285 bool PredicatedIV =
false;
13290 auto canProveNUW = [&]() {
13293 if (!ControlsOnlyExit)
13314 Limit = Limit.
zext(OuterBitWidth);
13326 Type *Ty = ZExt->getType();
13337 if (!
IV && AllowPredicates) {
13342 PredicatedIV =
true;
13346 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13360 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13363 const SCEV *Stride =
IV->getStepRecurrence(*
this);
13368 if (!PositiveStride) {
13420 auto wouldZeroStrideBeUB = [&]() {
13432 if (!wouldZeroStrideBeUB()) {
13436 }
else if (!NoWrap) {
13439 if (canIVOverflowOnLT(
RHS, Stride, IsSigned))
13452 const SCEV *
Start =
IV->getStart();
13458 const SCEV *OrigStart =
Start;
13459 const SCEV *OrigRHS =
RHS;
13460 if (
Start->getType()->isPointerTy()) {
13471 const SCEV *End =
nullptr, *BECount =
nullptr,
13472 *BECountIfBackedgeTaken =
nullptr;
13475 if (PositiveStride && RHSAddRec !=
nullptr && RHSAddRec->getLoop() == L &&
13476 any(RHSAddRec->getNoWrapFlags())) {
13489 const SCEV *RHSStart = RHSAddRec->getStart();
13490 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*
this);
13502 const SCEV *Denominator =
getMinusSCEV(Stride, RHSStride);
13511 BECountIfBackedgeTaken =
13516 if (BECount ==
nullptr) {
13521 const SCEV *MaxBECount = computeMaxBECountForLT(
13524 MaxBECount,
false , Predicates);
13531 auto *OrigStartMinusStride =
getMinusSCEV(OrigStart, Stride);
13558 const SCEV *Numerator =
13564 auto canProveRHSGreaterThanEqualStart = [&]() {
13583 auto *StartMinusOne =
13590 if (canProveRHSGreaterThanEqualStart()) {
13605 BECountIfBackedgeTaken =
13621 bool MayAddOverflow = [&] {
13667 if (Start == Stride || Start ==
getMinusSCEV(Stride, One)) {
13681 if (!MayAddOverflow) {
13693 const SCEV *ConstantMaxBECount;
13694 bool MaxOrZero =
false;
13696 ConstantMaxBECount = BECount;
13697 }
else if (BECountIfBackedgeTaken &&
13702 ConstantMaxBECount = BECountIfBackedgeTaken;
13705 ConstantMaxBECount = computeMaxBECountForLT(
13713 const SCEV *SymbolicMaxBECount =
13715 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount, MaxOrZero,
13719ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
13720 const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
bool IsSigned,
13721 bool ControlsOnlyExit,
bool AllowPredicates) {
13728 if (!
IV && AllowPredicates)
13735 if (!
IV ||
IV->getLoop() != L || !
IV->isAffine())
13739 bool NoWrap = ControlsOnlyExit &&
any(
IV->getNoWrapFlags(WrapType));
13752 if (!Stride->
isOne() && !NoWrap)
13753 if (canIVOverflowOnGT(
RHS, Stride, IsSigned))
13756 const SCEV *
Start =
IV->getStart();
13757 const SCEV *End =
RHS;
13768 if (
Start->getType()->isPointerTy()) {
13803 const SCEV *ConstantMaxBECount =
13810 ConstantMaxBECount = BECount;
13811 const SCEV *SymbolicMaxBECount =
13814 return ExitLimit(BECount, ConstantMaxBECount, SymbolicMaxBECount,
false,
13820 if (
Range.isFullSet())
13825 if (!SC->getValue()->isZero()) {
13831 return ShiftedAddRec->getNumIterationsInRange(
13832 Range.subtract(SC->getAPInt()), SE);
13863 APInt ExitVal = (End +
A).udiv(
A);
13876 ConstantInt::get(SE.
getContext(), ExitVal - 1), SE)->getValue()) &&
13877 "Linear scev computation is off in a bad way!");
13908 assert(!
Last->isZero() &&
"Recurrency with zero step?");
13933 Ty = Store->getValueOperand()->getType();
13935 Ty = Load->getType();
13948 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13950 SE->ConstantEvolutionLoopExitValue.erase(PN);
13951 SE->eraseValueFromMap(getValPtr());
13955void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
13956 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
13966 : CallbackVH(
V), SE(se) {}
13975 : F(F), DL(F.
getDataLayout()), TLI(TLI), AC(AC), DT(DT), LI(LI),
13977 LoopDispositions(64), BlockDispositions(64) {
13989 F.getParent(), Intrinsic::experimental_guard);
13990 HasGuards = GuardDecl && !GuardDecl->use_empty();
13994 : F(Arg.F), DL(Arg.DL), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC),
13995 DT(Arg.DT), LI(Arg.LI), CouldNotCompute(
std::
move(Arg.CouldNotCompute)),
13996 ValueExprMap(
std::
move(Arg.ValueExprMap)),
13997 PendingLoopPredicates(
std::
move(Arg.PendingLoopPredicates)),
13998 PendingMerges(
std::
move(Arg.PendingMerges)),
13999 ConstantMultipleCache(
std::
move(Arg.ConstantMultipleCache)),
14000 BackedgeTakenCounts(
std::
move(Arg.BackedgeTakenCounts)),
14001 PredicatedBackedgeTakenCounts(
14002 std::
move(Arg.PredicatedBackedgeTakenCounts)),
14003 BECountUsers(
std::
move(Arg.BECountUsers)),
14004 ConstantEvolutionLoopExitValue(
14005 std::
move(Arg.ConstantEvolutionLoopExitValue)),
14006 ValuesAtScopes(
std::
move(Arg.ValuesAtScopes)),
14007 ValuesAtScopesUsers(
std::
move(Arg.ValuesAtScopesUsers)),
14008 LoopDispositions(
std::
move(Arg.LoopDispositions)),
14009 LoopPropertiesCache(
std::
move(Arg.LoopPropertiesCache)),
14010 BlockDispositions(
std::
move(Arg.BlockDispositions)),
14011 SCEVUsers(
std::
move(Arg.SCEVUsers)),
14012 UnsignedRanges(
std::
move(Arg.UnsignedRanges)),
14013 SignedRanges(
std::
move(Arg.SignedRanges)),
14014 UniqueSCEVs(
std::
move(Arg.UniqueSCEVs)),
14015 UniquePreds(
std::
move(Arg.UniquePreds)),
14016 SCEVAllocator(
std::
move(Arg.SCEVAllocator)),
14017 LoopUsers(
std::
move(Arg.LoopUsers)),
14018 PredicatedSCEVRewrites(
std::
move(Arg.PredicatedSCEVRewrites)),
14019 FirstUnknown(Arg.FirstUnknown) {
14020 Arg.FirstUnknown =
nullptr;
14029 Tmp->~SCEVUnknown();
14031 FirstUnknown =
nullptr;
14033 ExprValueMap.clear();
14034 ValueExprMap.clear();
14036 BackedgeTakenCounts.clear();
14037 PredicatedBackedgeTakenCounts.clear();
14039 assert(PendingLoopPredicates.empty() &&
"isImpliedCond garbage");
14040 assert(PendingMerges.empty() &&
"isImpliedViaMerge garbage");
14041 assert(!WalkingBEDominatingConds &&
"isLoopBackedgeGuardedByCond garbage!");
14042 assert(!ProvingSplitPredicate &&
"ProvingSplitPredicate garbage!");
14064 L->getHeader()->printAsOperand(OS,
false);
14068 L->getExitingBlocks(ExitingBlocks);
14069 if (ExitingBlocks.
size() != 1)
14070 OS <<
"<multiple exits> ";
14074 OS <<
"backedge-taken count is ";
14077 OS <<
"Unpredictable backedge-taken count.";
14080 if (ExitingBlocks.
size() > 1)
14081 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14082 OS <<
" exit count for " << ExitingBlock->
getName() <<
": ";
14090 OS <<
"\n predicated exit count for " << ExitingBlock->
getName()
14093 OS <<
"\n Predicates:\n";
14094 for (
const auto *
P : Predicates)
14102 L->getHeader()->printAsOperand(OS,
false);
14107 OS <<
"constant max backedge-taken count is ";
14110 OS <<
", actual taken count either this or zero.";
14112 OS <<
"Unpredictable constant max backedge-taken count. ";
14117 L->getHeader()->printAsOperand(OS,
false);
14122 OS <<
"symbolic max backedge-taken count is ";
14125 OS <<
", actual taken count either this or zero.";
14127 OS <<
"Unpredictable symbolic max backedge-taken count. ";
14131 if (ExitingBlocks.
size() > 1)
14132 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
14133 OS <<
" symbolic max exit count for " << ExitingBlock->
getName() <<
": ";
14143 OS <<
"\n predicated symbolic max exit count for "
14144 << ExitingBlock->
getName() <<
": ";
14146 OS <<
"\n Predicates:\n";
14147 for (
const auto *
P : Predicates)
14157 assert(!Preds.
empty() &&
"Different predicated BTC, but no predicates");
14159 L->getHeader()->printAsOperand(OS,
false);
14162 OS <<
"Predicated backedge-taken count is ";
14165 OS <<
"Unpredictable predicated backedge-taken count.";
14167 OS <<
" Predicates:\n";
14168 for (
const auto *
P : Preds)
14173 auto *PredConstantMax =
14175 if (PredConstantMax != ConstantBTC) {
14177 "different predicated constant max BTC but no predicates");
14179 L->getHeader()->printAsOperand(OS,
false);
14182 OS <<
"Predicated constant max backedge-taken count is ";
14185 OS <<
"Unpredictable predicated constant max backedge-taken count.";
14187 OS <<
" Predicates:\n";
14188 for (
const auto *
P : Preds)
14193 auto *PredSymbolicMax =
14195 if (SymbolicBTC != PredSymbolicMax) {
14197 "Different predicated symbolic max BTC, but no predicates");
14199 L->getHeader()->printAsOperand(OS,
false);
14202 OS <<
"Predicated symbolic max backedge-taken count is ";
14205 OS <<
"Unpredictable predicated symbolic max backedge-taken count.";
14207 OS <<
" Predicates:\n";
14208 for (
const auto *
P : Preds)
14214 L->getHeader()->printAsOperand(OS,
false);
14238 OS <<
"Computable";
14248 OS <<
"DoesNotDominate";
14254 OS <<
"ProperlyDominates";
14271 OS <<
"Classifying expressions for: ";
14272 F.printAsOperand(OS,
false);
14287 const Loop *L = LI.getLoopFor(
I.getParent());
14302 OS <<
"\t\t" "Exits: ";
14305 OS <<
"<<Unknown>>";
14311 for (
const auto *Iter = L; Iter; Iter = Iter->getParentLoop()) {
14313 Iter->getHeader()->printAsOperand(OS,
false);
14321 InnerL->getHeader()->printAsOperand(OS,
false);
14332 OS <<
"Determining loop execution counts for: ";
14333 F.printAsOperand(OS,
false);
14341 auto &Values = LoopDispositions[S];
14342 for (
auto &V : Values) {
14343 if (V.getPointer() == L)
14348 auto &Values2 = LoopDispositions[S];
14350 if (V.getPointer() == L) {
14359ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
14378 assert(!L->contains(AR->
getLoop()) &&
"Containing loop's header does not"
14379 " dominate the contained loop's header?");
14407 bool HasVarying =
false;
14441 auto &Values = BlockDispositions[S];
14442 for (
auto &V : Values) {
14443 if (V.getPointer() == BB)
14448 auto &Values2 = BlockDispositions[S];
14450 if (V.getPointer() == BB) {
14459ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
14489 bool Proper =
true;
14500 if (Instruction *
I =
14502 if (
I->getParent() == BB)
14504 if (DT.properlyDominates(
I->getParent(), BB))
14527void ScalarEvolution::forgetBackedgeTakenCounts(
const Loop *L,
14530 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14531 auto It = BECounts.find(L);
14532 if (It != BECounts.end()) {
14533 for (
const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
14534 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14536 auto UserIt = BECountUsers.find(S);
14537 assert(UserIt != BECountUsers.end());
14542 BECounts.erase(It);
14550 while (!Worklist.
empty()) {
14552 auto Users = SCEVUsers.find(Curr);
14553 if (
Users != SCEVUsers.end())
14554 for (
const auto *User :
Users->second)
14555 if (ToForget.
insert(User).second)
14559 for (
const auto *S : ToForget)
14560 forgetMemoizedResultsImpl(S);
14562 for (
auto I = PredicatedSCEVRewrites.begin();
14563 I != PredicatedSCEVRewrites.end();) {
14564 std::pair<const SCEV *, const Loop *>
Entry =
I->first;
14565 if (ToForget.count(
Entry.first))
14566 PredicatedSCEVRewrites.erase(
I++);
14572void ScalarEvolution::forgetMemoizedResultsImpl(
const SCEV *S) {
14573 LoopDispositions.erase(S);
14574 BlockDispositions.erase(S);
14575 UnsignedRanges.erase(S);
14576 SignedRanges.erase(S);
14577 HasRecMap.erase(S);
14578 ConstantMultipleCache.erase(S);
14581 UnsignedWrapViaInductionTried.erase(AR);
14582 SignedWrapViaInductionTried.erase(AR);
14585 auto ExprIt = ExprValueMap.find(S);
14586 if (ExprIt != ExprValueMap.end()) {
14587 for (
Value *V : ExprIt->second) {
14588 auto ValueIt = ValueExprMap.find_as(V);
14589 if (ValueIt != ValueExprMap.end())
14590 ValueExprMap.erase(ValueIt);
14592 ExprValueMap.erase(ExprIt);
14595 auto ScopeIt = ValuesAtScopes.find(S);
14596 if (ScopeIt != ValuesAtScopes.end()) {
14597 for (
const auto &Pair : ScopeIt->second)
14600 std::make_pair(Pair.first, S));
14601 ValuesAtScopes.erase(ScopeIt);
14604 auto ScopeUserIt = ValuesAtScopesUsers.find(S);
14605 if (ScopeUserIt != ValuesAtScopesUsers.end()) {
14606 for (
const auto &Pair : ScopeUserIt->second)
14607 llvm::erase(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
14608 ValuesAtScopesUsers.erase(ScopeUserIt);
14611 auto BEUsersIt = BECountUsers.find(S);
14612 if (BEUsersIt != BECountUsers.end()) {
14614 auto Copy = BEUsersIt->second;
14615 for (
const auto &Pair : Copy)
14616 forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
14617 BECountUsers.erase(BEUsersIt);
14620 auto FoldUser = FoldCacheUser.find(S);
14621 if (FoldUser != FoldCacheUser.end())
14622 for (
auto &KV : FoldUser->second)
14623 FoldCache.erase(KV);
14624 FoldCacheUser.erase(S);
14628ScalarEvolution::getUsedLoops(
const SCEV *S,
14630 struct FindUsedLoops {
14631 FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
14632 : LoopsUsed(LoopsUsed) {}
14633 SmallPtrSetImpl<const Loop *> &LoopsUsed;
14634 bool follow(
const SCEV *S) {
14640 bool isDone()
const {
return false; }
14643 FindUsedLoops
F(LoopsUsed);
14644 SCEVTraversal<FindUsedLoops>(F).visitAll(S);
14647void ScalarEvolution::getReachableBlocks(
14650 Worklist.
push_back(&F.getEntryBlock());
14651 while (!Worklist.
empty()) {
14653 if (!Reachable.
insert(BB).second)
14661 Worklist.
push_back(
C->isOne() ? TrueBB : FalseBB);
14668 if (isKnownPredicateViaConstantRanges(
Cmp->getCmpPredicate(), L, R)) {
14672 if (isKnownPredicateViaConstantRanges(
Cmp->getInverseCmpPredicate(), L,
14707 SCEVMapper SCM(SE2);
14709 SE2.getReachableBlocks(ReachableBlocks, F);
14711 auto GetDelta = [&](
const SCEV *Old,
const SCEV *New) ->
const SCEV * {
14729 while (!LoopStack.
empty()) {
14735 if (!ReachableBlocks.
contains(L->getHeader()))
14740 auto It = BackedgeTakenCounts.find(L);
14741 if (It == BackedgeTakenCounts.end())
14745 SCM.visit(It->second.getExact(L,
const_cast<ScalarEvolution *
>(
this)));
14765 const SCEV *Delta = GetDelta(CurBECount, NewBECount);
14766 if (Delta && !Delta->
isZero()) {
14767 dbgs() <<
"Trip Count for " << *L <<
" Changed!\n";
14768 dbgs() <<
"Old: " << *CurBECount <<
"\n";
14769 dbgs() <<
"New: " << *NewBECount <<
"\n";
14770 dbgs() <<
"Delta: " << *Delta <<
"\n";
14778 while (!Worklist.
empty()) {
14780 if (ValidLoops.
insert(L).second)
14781 Worklist.
append(L->begin(), L->end());
14783 for (
const auto &KV : ValueExprMap) {
14788 "AddRec references invalid loop");
14793 auto It = ExprValueMap.find(KV.second);
14794 if (It == ExprValueMap.end() || !It->second.contains(KV.first)) {
14795 dbgs() <<
"Value " << *KV.first
14796 <<
" is in ValueExprMap but not in ExprValueMap\n";
14801 if (!ReachableBlocks.
contains(
I->getParent()))
14803 const SCEV *OldSCEV = SCM.visit(KV.second);
14805 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV);
14806 if (Delta && !Delta->
isZero()) {
14807 dbgs() <<
"SCEV for value " << *
I <<
" changed!\n"
14808 <<
"Old: " << *OldSCEV <<
"\n"
14809 <<
"New: " << *NewSCEV <<
"\n"
14810 <<
"Delta: " << *Delta <<
"\n";
14816 for (
const auto &KV : ExprValueMap) {
14817 for (
Value *V : KV.second) {
14818 const SCEV *S = ValueExprMap.lookup(V);
14820 dbgs() <<
"Value " << *V
14821 <<
" is in ExprValueMap but not in ValueExprMap\n";
14824 if (S != KV.first) {
14825 dbgs() <<
"Value " << *V <<
" mapped to " << *S <<
" rather than "
14826 << *KV.first <<
"\n";
14833 for (
const auto &S : UniqueSCEVs) {
14838 auto It = SCEVUsers.find(
Op);
14839 if (It != SCEVUsers.end() && It->second.count(&S))
14841 dbgs() <<
"Use of operand " << *
Op <<
" by user " << S
14842 <<
" is not being tracked!\n";
14848 for (
const auto &ValueAndVec : ValuesAtScopes) {
14850 for (
const auto &LoopAndValueAtScope : ValueAndVec.second) {
14851 const Loop *L = LoopAndValueAtScope.first;
14852 const SCEV *ValueAtScope = LoopAndValueAtScope.second;
14854 auto It = ValuesAtScopesUsers.find(ValueAtScope);
14855 if (It != ValuesAtScopesUsers.end() &&
14858 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14859 << *ValueAtScope <<
" missing in ValuesAtScopesUsers\n";
14865 for (
const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
14866 const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
14867 for (
const auto &LoopAndValue : ValueAtScopeAndVec.second) {
14868 const Loop *L = LoopAndValue.first;
14869 const SCEV *
Value = LoopAndValue.second;
14871 auto It = ValuesAtScopes.find(
Value);
14872 if (It != ValuesAtScopes.end() &&
14873 is_contained(It->second, std::make_pair(L, ValueAtScope)))
14875 dbgs() <<
"Value: " << *
Value <<
", Loop: " << *L <<
", ValueAtScope: "
14876 << *ValueAtScope <<
" missing in ValuesAtScopes\n";
14882 auto VerifyBECountUsers = [&](
bool Predicated) {
14884 Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
14885 for (
const auto &LoopAndBEInfo : BECounts) {
14886 for (
const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
14887 for (
const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) {
14889 auto UserIt = BECountUsers.find(S);
14890 if (UserIt != BECountUsers.end() &&
14891 UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
14893 dbgs() <<
"Value " << *S <<
" for loop " << *LoopAndBEInfo.first
14894 <<
" missing from BECountUsers\n";
14901 VerifyBECountUsers(
false);
14902 VerifyBECountUsers(
true);
14905 for (
auto &[S, Values] : LoopDispositions) {
14906 for (
auto [
Loop, CachedDisposition] : Values) {
14908 if (CachedDisposition != RecomputedDisposition) {
14909 dbgs() <<
"Cached disposition of " << *S <<
" for loop " << *
Loop
14910 <<
" is incorrect: cached " << CachedDisposition <<
", actual "
14911 << RecomputedDisposition <<
"\n";
14918 for (
auto &[S, Values] : BlockDispositions) {
14919 for (
auto [BB, CachedDisposition] : Values) {
14921 if (CachedDisposition != RecomputedDisposition) {
14922 dbgs() <<
"Cached disposition of " << *S <<
" for block %"
14923 << BB->
getName() <<
" is incorrect: cached " << CachedDisposition
14924 <<
", actual " << RecomputedDisposition <<
"\n";
14931 for (
auto [
FoldID, Expr] : FoldCache) {
14932 auto I = FoldCacheUser.find(Expr);
14933 if (
I == FoldCacheUser.end()) {
14934 dbgs() <<
"Missing entry in FoldCacheUser for cached expression " << *Expr
14939 dbgs() <<
"Missing FoldID in cached users of " << *Expr <<
"!\n";
14943 for (
auto [Expr, IDs] : FoldCacheUser) {
14944 for (
auto &
FoldID : IDs) {
14947 dbgs() <<
"Missing entry in FoldCache for expression " << *Expr
14952 dbgs() <<
"Entry in FoldCache doesn't match FoldCacheUser: " << *S
14953 <<
" != " << *Expr <<
"!\n";
14964 for (
auto [S, Multiple] : ConstantMultipleCache) {
14966 if ((Multiple != 0 && RecomputedMultiple != 0 &&
14967 Multiple.
urem(RecomputedMultiple) != 0 &&
14968 RecomputedMultiple.
urem(Multiple) != 0)) {
14969 dbgs() <<
"Incorrect cached computation in ConstantMultipleCache for "
14970 << *S <<
" : Computed " << RecomputedMultiple
14971 <<
" but cache contains " << Multiple <<
"!\n";
14979 FunctionAnalysisManager::Invalidator &Inv) {
15011 OS <<
"Printing analysis 'Scalar Evolution Analysis' for function '"
15012 <<
F.getName() <<
"':\n";
15018 "Scalar Evolution Analysis",
false,
true)
15067 const SCEV *LHS,
const SCEV *RHS) {
15069 assert(LHS->getType() == RHS->getType() &&
15070 "Type mismatch between LHS and RHS");
15073 ID.AddInteger(Pred);
15074 ID.AddPointer(LHS);
15075 ID.AddPointer(RHS);
15076 void *IP =
nullptr;
15077 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
15081 UniquePreds.InsertNode(Eq, IP);
15092 ID.AddInteger(AddedFlags);
15093 void *IP =
nullptr;
15094 if (
const auto *S = UniquePreds.FindNodeOrInsertPos(
ID, IP))
15096 auto *OF =
new (SCEVAllocator)
15098 UniquePreds.InsertNode(OF, IP);
15118 SCEVPredicateRewriter
Rewriter(L, SE, NewPreds, Pred);
15119 return Rewriter.visit(S);
15125 for (
const auto *Pred : U->getPredicates())
15127 if (IPred->getLHS() == Expr &&
15129 return IPred->getRHS();
15131 if (IPred->getLHS() == Expr &&
15132 IPred->getPredicate() == ICmpInst::ICMP_EQ)
15133 return IPred->getRHS();
15136 return convertToAddRecWithPreds(Expr);
15139 const SCEV *visitZeroExtendExpr(
const SCEVZeroExtendExpr *Expr) {
15155 const SCEV *visitSignExtendExpr(
const SCEVSignExtendExpr *Expr) {
15172 explicit SCEVPredicateRewriter(
15173 const Loop *L, ScalarEvolution &SE,
15174 SmallVectorImpl<const SCEVPredicate *> *NewPreds,
15175 const SCEVPredicate *Pred)
15176 : SCEVRewriteVisitor(SE), NewPreds(NewPreds), Pred(Pred),
L(
L) {}
15178 bool addOverflowAssumption(
const SCEVPredicate *
P) {
15181 return Pred && Pred->
implies(
P, SE);
15187 bool addOverflowAssumption(
const SCEVAddRecExpr *AR,
15190 return addOverflowAssumption(
A);
15199 const SCEV *convertToAddRecWithPreds(
const SCEVUnknown *Expr) {
15203 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
15205 if (!PredicatedRewrite)
15207 for (
const auto *
P : PredicatedRewrite->second){
15210 if (L != WP->getExpr()->getLoop())
15213 if (!addOverflowAssumption(
P))
15216 return PredicatedRewrite->first;
15219 SmallVectorImpl<const SCEVPredicate *> *NewPreds;
15220 const SCEVPredicate *Pred;
15229 return SCEVPredicateRewriter::rewrite(S, L, *
this,
nullptr, &Preds);
15236 S = SCEVPredicateRewriter::rewrite(S, L, *
this, &TransformPreds,
nullptr);
15256 if (!Step->
isOne())
15281 assert(LHS->getType() == RHS->getType() &&
"LHS and RHS types don't match");
15282 assert(LHS != RHS &&
"LHS and RHS are the same SCEV");
15295 return Op->LHS == LHS &&
Op->RHS == RHS;
15302 OS.
indent(
Depth) <<
"Equal predicate: " << *LHS <<
" == " << *RHS <<
"\n";
15304 OS.
indent(
Depth) <<
"Compare predicate: " << *LHS <<
" " << Pred <<
") "
15329 const SCEV *Start = AR->getStart();
15330 const SCEV *OpStart =
Op->AR->getStart();
15335 if (Start->getType()->isPointerTy() && Start->getType() != OpStart->
getType())
15338 const SCEV *Step = AR->getStepRecurrence(SE);
15339 const SCEV *OpStep =
Op->AR->getStepRecurrence(SE);
15392 if (Step->getValue()->getValue().isNonNegative())
15396 return ImpliedFlags;
15403 for (
const auto *
P : Preds)
15416 return this->implies(I, SE);
15424 for (
const auto *Pred : Preds)
15425 Pred->print(OS,
Depth);
15430 for (
const auto *Pred : Set->Preds)
15438 bool CheckImplies = Preds.
size() < 16;
15441 if (CheckImplies &&
implies(
N, SE))
15447 for (
auto *
P : Preds) {
15448 if (CheckImplies &&
N->implies(
P, SE))
15452 Preds = std::move(PrunedPreds);
15453 Preds.push_back(
N);
15460 Preds = std::make_unique<SCEVUnionPredicate>(
Empty, SE);
15465 for (
const auto *
Op :
Ops)
15470 SCEVUsers[
Op].insert(
User);
15479 SCEVUsers[
Op].insert(
User);
15483 const SCEV *Expr = SE.getSCEV(V);
15488 RewriteEntry &Entry = RewriteMap[Expr];
15491 if (Entry.second && Generation == Entry.first)
15492 return Entry.second;
15497 Expr = Entry.second;
15499 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds);
15500 Entry = {Generation, NewSCEV};
15506 if (!BackedgeCount) {
15508 BackedgeCount = SE.getPredicatedBackedgeTakenCount(&L, Preds);
15509 for (
const auto *
P : Preds)
15512 return BackedgeCount;
15516 if (!SymbolicMaxBackedgeCount) {
15518 SymbolicMaxBackedgeCount =
15519 SE.getPredicatedSymbolicMaxBackedgeTakenCount(&L, Preds);
15520 for (
const auto *
P : Preds)
15523 return SymbolicMaxBackedgeCount;
15527 if (!SmallConstantMaxTripCount) {
15529 SmallConstantMaxTripCount = SE.getSmallConstantMaxTripCount(&L, &Preds);
15530 for (
const auto *
P : Preds)
15533 return *SmallConstantMaxTripCount;
15537 if (Preds->implies(&Pred, SE))
15542 Preds = std::make_unique<SCEVUnionPredicate>(NewPreds, SE);
15543 updateGeneration();
15550void PredicatedScalarEvolution::updateGeneration() {
15552 if (++Generation == 0) {
15553 for (
auto &
II : RewriteMap) {
15554 const SCEV *Rewritten =
II.second.second;
15571 auto II = FlagsMap.insert({V, Flags});
15584 auto II = FlagsMap.find(V);
15586 if (
II != FlagsMap.end())
15595 auto *New = SE.convertSCEVToAddRecWithPredicates(Expr, &L, NewPreds);
15600 for (
const auto *
P : NewPreds)
15603 RewriteMap[SE.getSCEV(V)] = {Generation, New};
15609 : RewriteMap(
Init.RewriteMap), SE(
Init.SE), L(
Init.L),
15612 Generation(
Init.Generation), BackedgeCount(
Init.BackedgeCount) {
15613 for (
auto I :
Init.FlagsMap)
15614 FlagsMap.insert(
I);
15619 for (
auto *BB : L.getBlocks())
15620 for (
auto &
I : *BB) {
15621 if (!SE.isSCEVable(
I.getType()))
15624 auto *Expr = SE.getSCEV(&
I);
15625 auto II = RewriteMap.find(Expr);
15627 if (
II == RewriteMap.end())
15631 if (
II->second.second == Expr)
15636 OS.
indent(
Depth + 2) <<
"--> " << *
II->second.second <<
"\n";
15644 LoopGuards Guards(SE);
15652void ScalarEvolution::LoopGuards::collectFromPHI(
15660 using MinMaxPattern = std::pair<const SCEVConstant *, SCEVTypes>;
15661 auto GetMinMaxConst = [&](
unsigned IncomingIdx) -> MinMaxPattern {
15675 auto &RewriteMap =
G->second.RewriteMap;
15676 if (RewriteMap.empty())
15678 auto S = RewriteMap.find(SE.
getSCEV(
Phi.getIncomingValue(IncomingIdx)));
15679 if (S == RewriteMap.end())
15685 return {C0,
SM->getSCEVType()};
15688 auto MergeMinMaxConst = [](MinMaxPattern
P1,
15689 MinMaxPattern
P2) -> MinMaxPattern {
15690 auto [C1,
T1] =
P1;
15691 auto [C2, T2] =
P2;
15692 if (!C1 || !C2 ||
T1 != T2)
15696 return {C1->getAPInt().
ult(C2->getAPInt()) ? C1 : C2,
T1};
15698 return {C1->getAPInt().
slt(C2->getAPInt()) ? C1 : C2,
T1};
15700 return {C1->getAPInt().
ugt(C2->getAPInt()) ? C1 : C2,
T1};
15702 return {C1->getAPInt().
sgt(C2->getAPInt()) ? C1 : C2,
T1};
15707 auto P = GetMinMaxConst(0);
15708 for (
unsigned int In = 1;
In <
Phi.getNumIncomingValues();
In++) {
15711 P = MergeMinMaxConst(
P, GetMinMaxConst(In));
15714 const SCEV *
LHS = SE.
getSCEV(
const_cast<PHINode *
>(&Phi));
15717 Guards.RewriteMap.insert({
LHS,
RHS});
15725 const APInt &DivisorVal,
15727 const APInt *ExprVal;
15740 const APInt &DivisorVal,
15742 const APInt *ExprVal;
15750 return SE.
getConstant(*ExprVal + DivisorVal - Rem);
15764 const SCEV *URemRHS =
nullptr;
15768 const SCEV *Multiple =
15770 DivInfo[URemLHS] = Multiple;
15772 Multiples[URemLHS] =
C->getAPInt();
15792 auto IsMinMaxSCEVWithNonNegativeConstant =
15796 if (
MinMax->getNumOperands() != 2)
15799 if (
C->getAPInt().isNegative())
15801 SCTy =
MinMax->getSCEVType();
15810 const SCEV *MinMaxLHS =
nullptr, *MinMaxRHS =
nullptr;
15812 if (!IsMinMaxSCEVWithNonNegativeConstant(MinMaxExpr, SCTy, MinMaxLHS,
15817 auto *DivisibleExpr =
15825void ScalarEvolution::LoopGuards::collectFromBlock(
15827 const BasicBlock *
Block,
const BasicBlock *Pred,
15835 DenseMap<const SCEV *, const SCEV *> &RewriteMap,
15846 &ExprsToRewrite]() {
15847 const SCEVConstant *C1;
15860 if (ExactRegion.isWrappedSet() || ExactRegion.isFullSet())
15862 auto [
I,
Inserted] = RewriteMap.try_emplace(LHSUnknown);
15863 const SCEV *RewrittenLHS =
Inserted ? LHSUnknown :
I->second;
15871 if (MatchRangeCheckIdiom())
15888 auto AddRewrite = [&](
const SCEV *From,
const SCEV *FromRewritten,
15890 if (From == FromRewritten)
15892 RewriteMap[From] = To;
15898 auto GetMaybeRewritten = [&](
const SCEV *S) {
15899 return RewriteMap.lookup_or(S, S);
15902 const SCEV *RewrittenLHS = GetMaybeRewritten(
LHS);
15904 const APInt &DividesBy =
15919 switch (Predicate) {
15948 SmallPtrSet<const SCEV *, 16> Visited;
15950 auto EnqueueOperands = [&Worklist](
const SCEVNAryExpr *S) {
15954 while (!Worklist.
empty()) {
15958 if (!Visited.
insert(From).second)
15960 const SCEV *FromRewritten = GetMaybeRewritten(From);
15961 const SCEV *To =
nullptr;
15963 switch (Predicate) {
15968 EnqueueOperands(
UMax);
15974 EnqueueOperands(
SMax);
15980 EnqueueOperands(
UMin);
15986 EnqueueOperands(
SMin);
15994 const SCEV *OneAlignedUp =
15996 To = SE.
getUMaxExpr(FromRewritten, OneAlignedUp);
16008 const SCEVConstant *
C;
16017 Guards.NotEqual.insert({
LHS,
RHS});
16026 AddRewrite(From, FromRewritten, To);
16043 SE.F.
getParent(), Intrinsic::experimental_guard);
16045 for (
const auto *GU : GuardDecl->users())
16047 if (Guard->getFunction() ==
Block->getParent() &&
16056 unsigned NumCollectedConditions = 0;
16058 std::pair<const BasicBlock *, const BasicBlock *> Pair(Pred,
Block);
16060 Pair = SE.getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
16062 const CondBrInst *LoopEntryPredicate =
16064 if (!LoopEntryPredicate)
16069 NumCollectedConditions++;
16073 if (
Depth > 0 && NumCollectedConditions == 2)
16081 if (Pair.second->hasNPredecessorsOrMore(2) &&
16083 SmallDenseMap<const BasicBlock *, LoopGuards> IncomingGuards;
16084 for (
auto &Phi : Pair.second->phis())
16095 for (
auto [Term, EnterIfTrue] :
reverse(Terms)) {
16096 SmallVector<Value *, 8> Worklist;
16097 SmallPtrSet<Value *, 8> Visited;
16099 while (!Worklist.
empty()) {
16106 EnterIfTrue ?
Cmp->getPredicate() :
Cmp->getInversePredicate();
16130 DenseMap<const SCEV *, APInt> Multiples;
16132 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess) {
16139 for (
const auto &[Predicate,
LHS,
RHS] : GuardsToProcess)
16140 CollectCondition(Predicate,
LHS,
RHS, Guards.RewriteMap, DivGuards);
16144 for (
const auto &[K, Divisor] : Multiples) {
16145 const SCEV *DivisorSCEV = SE.
getConstant(Divisor);
16146 Guards.RewriteMap[
K] =
16148 Guards.
rewrite(K), Divisor, SE),
16157 Guards.PreserveNUW =
true;
16158 Guards.PreserveNSW =
true;
16159 for (
const SCEV *Expr : ExprsToRewrite) {
16160 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16161 Guards.PreserveNUW &=
16163 Guards.PreserveNSW &=
16170 if (ExprsToRewrite.size() > 1) {
16171 for (
const SCEV *Expr : ExprsToRewrite) {
16172 const SCEV *RewriteTo = Guards.RewriteMap[Expr];
16173 Guards.RewriteMap.erase(Expr);
16174 Guards.RewriteMap.insert({Expr, Guards.
rewrite(RewriteTo)});
16183 class SCEVLoopGuardRewriter
16194 NotEqual(Guards.NotEqual) {
16195 if (Guards.PreserveNUW)
16197 if (Guards.PreserveNSW)
16204 return Map.lookup_or(Expr, Expr);
16208 if (
const SCEV *S = Map.lookup(Expr))
16215 unsigned Bitwidth = Ty->getScalarSizeInBits() / 2;
16216 while (Bitwidth % 8 == 0 && Bitwidth >= 8 &&
16217 Bitwidth >
Op->getType()->getScalarSizeInBits()) {
16219 auto *NarrowExt = SE.getZeroExtendExpr(
Op, NarrowTy);
16220 if (
const SCEV *S = Map.lookup(NarrowExt))
16221 return SE.getZeroExtendExpr(S, Ty);
16222 Bitwidth = Bitwidth / 2;
16230 if (
const SCEV *S = Map.lookup(Expr))
16237 if (
const SCEV *S = Map.lookup(Expr))
16243 if (
const SCEV *S = Map.lookup(Expr))
16251 auto RewriteSubtraction = [&](
const SCEV *S) ->
const SCEV * {
16256 if (NotEqual.contains({LHS, RHS})) {
16258 SE.getOne(S->
getType()), SE.getConstantMultiple(S), SE);
16259 return SE.getUMaxExpr(OneAlignedUp, S);
16266 if (
const SCEV *Rewritten = RewriteSubtraction(Expr))
16277 if (
const SCEV *Rewritten = RewriteSubtraction(
Add))
16278 return SE.getAddExpr(
16281 if (
const SCEV *S = Map.lookup(
Add))
16282 return SE.getAddExpr(Expr->
getOperand(0), S);
16294 : SE.getAddExpr(Operands,
16310 : SE.getMulExpr(Operands,
16316 if (RewriteMap.empty() && NotEqual.empty())
16319 SCEVLoopGuardRewriter
Rewriter(SE, *
this);
16320 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< 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.
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
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
static constexpr unsigned SM(unsigned Version)
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 ConstantRange getRangeForAffineARHelper(APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, bool Signed)
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 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 make_scope_exit function, which executes user-defined cleanup logic at scope ex...
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< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
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.
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
LLVM_ABI APInt getHiBits(unsigned numBits) const
Compute an APInt containing numBits highbits from this APInt.
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.
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
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.
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()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - 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 * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
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 IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space.
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
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
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.
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
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)
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 in 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 PointerType * getUnqual(Type *ElementType)
This constructs a pointer to an object of the specified type in the default address space (address sp...
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 hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
LLVM_ABI void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
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 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 class represents a cast from a pointer to a pointer-sized integer value.
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.
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.
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.
LLVM_ABI void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize)
SCEVTypes getSCEVType() const
static constexpr auto FlagNW
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
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.
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 * getLosslessPtrToIntExpr(const SCEV *Op)
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 const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
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 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.
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.
StringRef - Represent a constant reference to a string, i.e.
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 isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
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)
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
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.
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)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
IntrinsicID_match m_Intrinsic()
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
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.
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
class_match< const SCEVVScale > m_SCEVVScale()
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.
class_match< const SCEVConstant > m_SCEVConstant()
cst_pred_ty< is_one > m_scev_One()
Match an integer 1.
specificloop_ty m_SpecificLoop(const Loop *L)
SCEVAffineAddRec_match< Op0_t, Op1_t, class_match< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
bind_ty< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
SCEVUnaryExpr_match< SCEVSignExtendExpr, Op0_t > m_scev_SExt(const Op0_t &Op0)
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.
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t, SCEV::FlagNUW, true > m_scev_c_NUWMul(const Op0_t &Op0, const Op1_t &Op1)
class_match< const Loop > m_Loop()
bind_ty< const SCEVAddExpr > m_scev_Add(const SCEVAddExpr *&V)
bind_ty< const SCEVUnknown > m_SCEVUnknown(const SCEVUnknown *&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.
class_match< const SCEV > m_SCEV()
@ 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.
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.
FunctionAddr VTableAddr Value
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...
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 >
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.
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)
FunctionAddr VTableAddr Count
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.
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()).
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 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)
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
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...
Incoming for lane mask phi as machine instruction, incoming register Reg and incoming block Block are...
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
bool isNonNegative() const
Returns true if this value is known to be non-negative.
static LLVM_ABI KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
unsigned getBitWidth() const
Get the bit width of this value.
static LLVM_ABI KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
KnownBits zextOrTrunc(unsigned BitWidth) const
Return known bits for a zero extension or truncation of the value we're tracking.
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
bool isNegative() const
Returns true if this value is known to be negative.
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