20#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
21#define LLVM_ANALYSIS_SCALAREVOLUTION_H
46class OverflowingBinaryOperator;
62class TargetLibraryInfo;
188 return ID ==
X.FastID;
192 return X.FastID.ComputeHash();
266 return ID ==
X.FastID;
271 return X.FastID.ComputeHash();
355 "Invalid flags value!");
372 "Invalid flags value!");
480 return TestFlags ==
maskFlags(Flags, TestFlags);
540 std::optional<SCEV::NoWrapFlags>
581 unsigned Depth = 0) {
587 unsigned Depth = 0) {
596 unsigned Depth = 0) {
602 unsigned Depth = 0) {
623 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
645 bool Sequential =
false);
647 bool Sequential =
false);
744 bool Sequential =
false);
749 bool Sequential =
false);
836 const SCEV *ExitCount);
981 return getRangeRef(S, HINT_RANGE_UNSIGNED);
997 return getRangeRef(S, HINT_RANGE_SIGNED);
1002 return getRangeRef(S, HINT_RANGE_SIGNED).
getSignedMin();
1007 return getRangeRef(S, HINT_RANGE_SIGNED).
getSignedMax();
1028 bool OrNegative =
false);
1117 assert(!isa<SCEVUnionPredicate>(
P) &&
"Only add leaf predicates here!");
1160 bool ExitIfTrue,
bool ControlsOnlyExit,
1161 bool AllowPredicates =
false);
1178 std::optional<MonotonicPredicateType>
1194 std::optional<LoopInvariantPredicate>
1204 std::optional<LoopInvariantPredicate>
1209 const SCEV *MaxIter);
1211 std::optional<LoopInvariantPredicate>
1303 bool PreserveNUW =
false;
1304 bool PreserveNSW =
false;
1327 return getLoopProperties(L).HasNoAbnormalExits;
1348 const SCEV *
Op =
nullptr;
1349 const Type *Ty =
nullptr;
1363 reinterpret_cast<uintptr_t
>(Ty)));
1367 return std::tie(
Op, Ty, C) == std::tie(
RHS.Op,
RHS.Ty,
RHS.C);
1374 class SCEVCallbackVH final :
public CallbackVH {
1377 void deleted()
override;
1378 void allUsesReplacedWith(
Value *New)
override;
1412 std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1454 bool WalkingBEDominatingConds =
false;
1458 bool ProvingSplitPredicate =
false;
1467 APInt getConstantMultipleImpl(
const SCEV *S);
1471 struct ExitNotTakenInfo {
1473 const SCEV *ExactNotTaken;
1474 const SCEV *ConstantMaxNotTaken;
1475 const SCEV *SymbolicMaxNotTaken;
1478 explicit ExitNotTakenInfo(
1480 const SCEV *ConstantMaxNotTaken,
const SCEV *SymbolicMaxNotTaken,
1482 : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1483 ConstantMaxNotTaken(ConstantMaxNotTaken),
1484 SymbolicMaxNotTaken(SymbolicMaxNotTaken), Predicates(Predicates) {}
1486 bool hasAlwaysTruePredicate()
const {
1487 return Predicates.
empty();
1494 class BackedgeTakenInfo {
1495 friend class ScalarEvolution;
1499 SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1504 const SCEV *ConstantMax =
nullptr;
1508 bool IsComplete =
false;
1512 const SCEV *SymbolicMax =
nullptr;
1515 bool MaxOrZero =
false;
1517 bool isComplete()
const {
return IsComplete; }
1518 const SCEV *getConstantMax()
const {
return ConstantMax; }
1521 BackedgeTakenInfo() =
default;
1522 BackedgeTakenInfo(BackedgeTakenInfo &&) =
default;
1523 BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) =
default;
1525 using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1528 BackedgeTakenInfo(ArrayRef<EdgeExitInfo> ExitCounts,
bool IsComplete,
1529 const SCEV *ConstantMax,
bool MaxOrZero);
1533 bool hasAnyInfo()
const {
1534 return !ExitNotTaken.empty() ||
1535 !isa<SCEVCouldNotCompute>(getConstantMax());
1539 bool hasFullInfo()
const {
return isComplete(); }
1559 const SCEV *getExact(
const Loop *L, ScalarEvolution *SE,
1560 SmallVector<const SCEVPredicate *, 4> *Predicates =
nullptr)
const;
1566 const SCEV *getExact(
const BasicBlock *ExitingBlock,
1567 ScalarEvolution *SE)
const;
1570 const SCEV *getConstantMax(ScalarEvolution *SE)
const;
1573 const SCEV *getConstantMax(
const BasicBlock *ExitingBlock,
1574 ScalarEvolution *SE)
const;
1578 getSymbolicMax(
const Loop *L, ScalarEvolution *SE,
1579 SmallVector<const SCEVPredicate *, 4> *Predicates =
nullptr);
1582 const SCEV *getSymbolicMax(
const BasicBlock *ExitingBlock,
1583 ScalarEvolution *SE)
const;
1587 bool isConstantMaxOrZero(ScalarEvolution *SE)
const;
1592 DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1596 DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1599 DenseMap<const SCEV *, SmallPtrSet<PointerIntPair<const Loop *, 1, bool>, 4>>
1606 DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1611 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1616 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1617 ValuesAtScopesUsers;
1620 DenseMap<
const SCEV *,
1621 SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
1624 struct LoopProperties {
1630 bool HasNoAbnormalExits;
1634 bool HasNoSideEffects;
1638 DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1641 LoopProperties getLoopProperties(
const Loop *L);
1643 bool loopHasNoSideEffects(
const Loop *L) {
1644 return getLoopProperties(L).HasNoSideEffects;
1653 SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
1657 BlockDisposition computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB);
1660 DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 8> > SCEVUsers;
1663 DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1666 DenseMap<const SCEV *, ConstantRange> SignedRanges;
1669 enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1672 const ConstantRange &setRange(
const SCEV *S, RangeSignHint Hint,
1674 DenseMap<const SCEV *, ConstantRange> &Cache =
1675 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1677 auto Pair = Cache.insert_or_assign(S, std::move(CR));
1678 return Pair.first->second;
1684 const ConstantRange &getRangeRef(
const SCEV *S, RangeSignHint Hint,
1685 unsigned Depth = 0);
1689 const ConstantRange &getRangeRefIter(
const SCEV *S, RangeSignHint Hint);
1693 ConstantRange getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
1694 const APInt &MaxBECount);
1698 ConstantRange getRangeForAffineNoSelfWrappingAR(
const SCEVAddRecExpr *AddRec,
1699 const SCEV *MaxBECount,
1701 RangeSignHint SignHint);
1706 ConstantRange getRangeViaFactoring(
const SCEV *Start,
const SCEV *Step,
1707 const APInt &MaxBECount);
1713 ConstantRange getRangeForUnknownRecurrence(
const SCEVUnknown *U);
1717 const SCEV *createSCEV(Value *V);
1721 const SCEV *createSCEVIter(Value *V);
1725 const SCEV *getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops);
1728 const SCEV *createNodeForPHI(PHINode *PN);
1731 const SCEV *createAddRecFromPHI(PHINode *PN);
1734 const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
1735 Value *StartValueV);
1738 const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1744 std::optional<const SCEV *>
1745 createNodeForSelectOrPHIInstWithICmpInstCond(Type *Ty, ICmpInst *
Cond,
1746 Value *TrueVal, Value *FalseVal);
1749 const SCEV *createNodeForSelectOrPHIViaUMinSeq(Value *
I, Value *
Cond,
1757 const SCEV *createNodeForSelectOrPHI(Value *V, Value *
Cond, Value *TrueVal,
1761 const SCEV *createNodeForGEP(GEPOperator *
GEP);
1765 const SCEV *computeSCEVAtScope(
const SCEV *S,
const Loop *L);
1770 BackedgeTakenInfo &getBackedgeTakenInfo(
const Loop *L);
1774 BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(
const Loop *L);
1779 BackedgeTakenInfo computeBackedgeTakenCount(
const Loop *L,
1780 bool AllowPredicates =
false);
1786 ExitLimit computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
1787 bool IsOnlyExit,
bool AllowPredicates =
false);
1792 class ExitLimitCache {
1798 SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1802 bool AllowPredicates;
1805 ExitLimitCache(
const Loop *L,
bool ExitIfTrue,
bool AllowPredicates)
1806 :
L(
L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1808 std::optional<ExitLimit>
find(
const Loop *L, Value *ExitCond,
1809 bool ExitIfTrue,
bool ControlsOnlyExit,
1810 bool AllowPredicates);
1812 void insert(
const Loop *L, Value *ExitCond,
bool ExitIfTrue,
1813 bool ControlsOnlyExit,
bool AllowPredicates,
1814 const ExitLimit &EL);
1817 using ExitLimitCacheTy = ExitLimitCache;
1819 ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1820 const Loop *L, Value *ExitCond,
1822 bool ControlsOnlyExit,
1823 bool AllowPredicates);
1824 ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache,
const Loop *L,
1825 Value *ExitCond,
bool ExitIfTrue,
1826 bool ControlsOnlyExit,
1827 bool AllowPredicates);
1828 std::optional<ScalarEvolution::ExitLimit> computeExitLimitFromCondFromBinOp(
1829 ExitLimitCacheTy &Cache,
const Loop *L, Value *ExitCond,
bool ExitIfTrue,
1830 bool ControlsOnlyExit,
bool AllowPredicates);
1837 ExitLimit computeExitLimitFromICmp(
const Loop *L, ICmpInst *ExitCond,
1840 bool AllowPredicates =
false);
1847 const SCEV *
LHS,
const SCEV *
RHS,
1849 bool AllowPredicates =
false);
1854 ExitLimit computeExitLimitFromSingleExitSwitch(
const Loop *L,
1856 BasicBlock *ExitingBB,
1866 ExitLimit computeShiftCompareExitLimit(Value *
LHS, Value *
RHS,
const Loop *L,
1874 const SCEV *computeExitCountExhaustively(
const Loop *L, Value *
Cond,
1881 ExitLimit howFarToZero(
const SCEV *V,
const Loop *L,
bool IsSubExpr,
1882 bool AllowPredicates =
false);
1887 ExitLimit howFarToNonZero(
const SCEV *V,
const Loop *L);
1901 ExitLimit howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
1902 bool isSigned,
bool ControlsOnlyExit,
1903 bool AllowPredicates =
false);
1905 ExitLimit howManyGreaterThans(
const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
1907 bool AllowPredicates =
false);
1912 std::pair<const BasicBlock *, const BasicBlock *>
1913 getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
const;
1920 const Value *FoundCondValue,
bool Inverse,
1921 const Instruction *Context =
nullptr);
1930 const SCEV *FoundLHS,
const SCEV *FoundRHS,
1931 const Instruction *CtxI);
1939 const SCEV *FoundRHS,
1940 const Instruction *Context =
nullptr);
1947 const SCEV *
RHS,
const SCEV *FoundLHS,
1948 const SCEV *FoundRHS,
1949 const Instruction *Context =
nullptr);
1956 const SCEV *
LHS,
const SCEV *
RHS,
1957 const SCEV *FoundLHS,
const SCEV *FoundRHS,
1958 unsigned Depth = 0);
1963 const SCEV *
LHS,
const SCEV *
RHS);
1969 const SCEV *
RHS,
const SCEV *FoundLHS,
1970 const SCEV *FoundRHS);
1979 const SCEV *FoundLHS,
1980 const SCEV *FoundRHS);
1985 const SCEV *
LHS,
const SCEV *
RHS);
1994 const SCEV *
LHS,
const SCEV *
RHS,
1995 const SCEV *FoundLHS,
1996 const SCEV *FoundRHS);
2005 const SCEV *
LHS,
const SCEV *
RHS,
2006 const SCEV *FoundLHS,
2007 const SCEV *FoundRHS,
2008 const Instruction *CtxI);
2018 const SCEV *
LHS,
const SCEV *
RHS,
2019 const SCEV *FoundLHS,
const SCEV *FoundRHS,
2028 const SCEV *
RHS,
const SCEV *FoundLHS,
2029 const SCEV *FoundRHS);
2034 Constant *getConstantEvolutionLoopExitValue(PHINode *PN,
const APInt &BEs,
2040 const SCEV *
LHS,
const SCEV *
RHS);
2056 bool splitBinaryAdd(
const SCEV *Expr,
const SCEV *&L,
const SCEV *&R,
2060 void forgetBackedgeTakenCounts(
const Loop *L,
bool Predicated);
2063 void forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs);
2066 void forgetMemoizedResultsImpl(
const SCEV *S);
2070 void visitAndClearUsers(SmallVectorImpl<Instruction *> &Worklist,
2071 SmallPtrSetImpl<Instruction *> &Visited,
2072 SmallVectorImpl<const SCEV *> &ToForget);
2075 void eraseValueFromMap(Value *V);
2078 void insertValueToMap(Value *V,
const SCEV *S);
2082 bool checkValidity(
const SCEV *S)
const;
2089 template <
typename ExtendOpTy>
2090 bool proveNoWrapByVaryingStart(
const SCEV *Start,
const SCEV *Step,
2104 std::optional<MonotonicPredicateType>
2105 getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *
LHS,
2117 const Instruction *getNonTrivialDefiningScopeBound(
const SCEV *S);
2122 const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops,
2127 const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops);
2131 bool isGuaranteedToTransferExecutionTo(
const Instruction *
A,
2132 const Instruction *
B);
2150 bool isSCEVExprNeverPoison(
const Instruction *
I);
2156 bool isAddRecNeverPoison(
const Instruction *
I,
const Loop *L);
2168 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2169 createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI);
2180 const SCEV *computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
2187 bool canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
bool IsSigned);
2192 bool canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
bool IsSigned);
2195 const SCEV *getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
2199 const SCEV *getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
2203 const SCEV *getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
2207 const SCEV *stripInjectiveFunctions(
const SCEV *Val)
const;
2212 void getUsedLoops(
const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
2216 bool matchURem(
const SCEV *Expr,
const SCEV *&
LHS,
const SCEV *&
RHS);
2220 SCEV *findExistingSCEVInCache(
SCEVTypes SCEVType, ArrayRef<const SCEV *> Ops);
2224 void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable,
2229 const SCEV *getWithOperands(
const SCEV *S,
2230 SmallVectorImpl<const SCEV *> &NewOps);
2232 FoldingSet<SCEV> UniqueSCEVs;
2233 FoldingSet<SCEVPredicate> UniquePreds;
2237 DenseMap<const Loop *, SmallVector<const SCEVAddRecExpr *, 4>> LoopUsers;
2241 DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
2242 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2243 PredicatedSCEVRewrites;
2247 SmallPtrSet<const SCEVAddRecExpr *, 16> UnsignedWrapViaInductionTried;
2251 SmallPtrSet<const SCEVAddRecExpr *, 16> SignedWrapViaInductionTried;
2294 std::unique_ptr<ScalarEvolution> SE;
2376 void updateGeneration();
2380 using RewriteEntry = std::pair<unsigned, const SCEV *>;
2400 std::unique_ptr<SCEVUnionPredicate> Preds;
2406 unsigned Generation = 0;
2409 const SCEV *BackedgeCount =
nullptr;
2412 const SCEV *SymbolicMaxBackedgeCount =
nullptr;
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
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")
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isSigned(unsigned int Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
mir Rename Register Operands
This header defines various interfaces for pass management in LLVM.
This file defines the PointerIntPair class.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Class for arbitrary precision integers.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Value handle with callbacks on RAUW and destruction.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
This is the shared class of boolean and integer constants.
This class represents a range of values.
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Node - This class is used to maintain the singly linked bucket list in a folding set.
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.
FunctionPass class - This class is used to implement most global optimizations.
This is an important class for using LLVM in a threaded context.
Represents a single loop in the control flow graph.
A Module instance is used to store all the information related to an LLVM module.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
Value handle that poisons itself if the Value is deleted.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
const SCEVPredicate & getPredicate() const
bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
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.
This node represents a polynomial recurrence on the trip count of the specified loop.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
const SCEV * getRHS() const
Returns the right hand side of the predicate.
ICmpInst::Predicate getPredicate() const
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEV * getLHS() const
Returns the left hand side of the predicate.
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
bool implies(const SCEVPredicate *N) const override
Implementation of the SCEVPredicate interface.
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
This class uses information about analyze scalars to rewrite expressions in canonical form.
This class represents an assumption made using SCEV expressions which can be checked at run-time.
virtual bool implies(const SCEVPredicate *N) const =0
Returns true if this predicate implies N.
SCEVPredicateKind getKind() const
virtual unsigned getComplexity() const
Returns the estimated complexity of this predicate.
SCEVPredicate & operator=(const SCEVPredicate &)=default
SCEVPredicate(const SCEVPredicate &)=default
virtual void print(raw_ostream &OS, unsigned Depth=0) const =0
Prints a textual representation of this predicate with an indentation of Depth.
virtual bool isAlwaysTrue() const =0
Returns true if the predicate is always true.
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.
unsigned getComplexity() const override
We estimate the complexity of a union predicate as the size number of predicates in the union.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
bool implies(const SCEVPredicate *N) const override
Returns true if this predicate implies N.
ArrayRef< const SCEVPredicate * > getPredicates() const
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an assumption made on an AddRec expression.
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
bool implies(const SCEVPredicate *N) 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 bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
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.
static SCEVWrapPredicate::IncrementWrapFlags maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask)
This class represents an analyzed expression in the program.
ArrayRef< const SCEV * > operands() const
Return operands of this SCEV expression.
unsigned short getExpressionSize() const
SCEV & operator=(const SCEV &)=delete
bool isOne() const
Return true if the expression is a constant one.
bool isZero() const
Return true if the expression is a constant zero.
SCEV(const SCEV &)=delete
void dump() const
This method is used for debugging.
bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
const unsigned short ExpressionSize
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
unsigned short SubclassData
This field is initialized to zero and may be used in subclasses to store miscellaneous information.
Type * getType() const
Return the LLVM type of this SCEV expression.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Analysis pass that exposes the ScalarEvolution for a function.
ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
Printer pass for the ScalarEvolutionAnalysis results.
ScalarEvolutionPrinterPass(raw_ostream &OS)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Verifier pass for the ScalarEvolutionAnalysis results.
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...
ScalarEvolution & getSE()
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
ScalarEvolutionWrapperPass()
const ScalarEvolution & getSE() const
bool operator==(const FoldID &RHS) const
FoldID(SCEVTypes C, const SCEV *Op, const Type *Ty)
unsigned computeHash() const
static 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 ...
const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
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.
bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
const SCEV * getGEPExpr(GEPOperator *GEP, const SmallVectorImpl< const SCEV * > &IndexExprs)
Returns an expression for a GEP.
Type * getWiderType(Type *Ty1, Type *Ty2) const
const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
const SCEV * getURemExpr(const SCEV *LHS, const SCEV *RHS)
Represents an unsigned remainder expression based on unsigned division.
bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
APInt getConstantMultiple(const SCEV *S)
Returns the max constant multiple of S.
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
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...
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
const SCEV * getAddExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
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.
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)?...
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...
const SCEV * getZeroExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
unsigned getSmallConstantMaxTripCount(const Loop *L)
Returns the upper bound of the loop trip count as a normal unsigned value.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
const SCEV * getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth=0)
bool isKnownViaInduction(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
std::optional< bool > evaluatePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
bool isKnownPredicateAt(ICmpInst::Predicate 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,...
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
const SCEV * getMulExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
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...
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
const SCEV * getSignExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
bool isKnownOnEveryIteration(ICmpInst::Predicate 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 ...
bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
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...
const SCEV * getAddRecExpr(const SmallVectorImpl< const SCEV * > &Operands, const Loop *L, SCEV::NoWrapFlags Flags)
const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(ICmpInst::Predicate 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...
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...
std::optional< bool > evaluatePredicateAt(ICmpInst::Predicate 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.
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
uint32_t getMinTrailingZeros(const SCEV *S)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
void print(raw_ostream &OS) const
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVector< const SCEVPredicate *, 4 > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
void forgetTopmostLoop(const Loop *L)
friend class ScalarEvolutionsTest
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.
const SCEV * getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
MonotonicPredicateType
A predicate is said to be monotonically increasing if may go from being false to being true as the lo...
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
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)
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
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...
bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
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
const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallPtrSetImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
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,...
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...
bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
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,...
const SCEV * getCouldNotCompute()
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
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.
std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
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...
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
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.
void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
const SCEV * getVScale(Type *Ty)
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.
bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
const SCEV * getPowerOfTwo(Type *Ty, unsigned Power)
Return a SCEV for the constant Power of two.
const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(ICmpInst::Predicate 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...
const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
const SCEV * getUnknown(Value *V)
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.
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.
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
const SCEV * getElementCount(Type *Ty, ElementCount EC)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
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'...
bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
const SCEV * getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
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.
const SCEV * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
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.
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 * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVector< const SCEVPredicate *, 4 > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
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.
LLVMContext & getContext() const
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Class to represent struct types.
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.
LLVM Value Representation.
This class implements an extremely fast bulk output stream that can only output to a stream.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ BasicBlock
Various leaf nodes.
unsigned combineHashValue(unsigned a, unsigned b)
Simplistic combination of 32-bit hash values into 32-bit hash values.
This is an optimization pass for GlobalISel generic memory operations.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
constexpr unsigned BitWidth
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
DefaultFoldingSetTrait - This class provides default implementations for FoldingSetTrait implementati...
static unsigned getHashValue(const ScalarEvolution::FoldID &Val)
static ScalarEvolution::FoldID getTombstoneKey()
static ScalarEvolution::FoldID getEmptyKey()
static bool isEqual(const ScalarEvolution::FoldID &LHS, const ScalarEvolution::FoldID &RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID)
static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
static unsigned ComputeHash(const SCEVPredicate &X, FoldingSetNodeID &TempID)
static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID)
static void Profile(const SCEV &X, FoldingSetNodeID &ID)
FoldingSetTrait - This trait class is used to define behavior of how to "profile" (in the FoldingSet ...
A CRTP mix-in to automatically provide informational APIs needed for passes.
An object of this class is returned by queries that could not be answered.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Information about the number of loop iterations for which a loop exit's branch condition evaluates to...
bool hasAnyInfo() const
Test whether this ExitLimit contains any computed information, or whether it's all SCEVCouldNotComput...
const SCEV * ExactNotTaken
const SCEV * SymbolicMaxNotTaken
bool hasFullInfo() const
Test whether this ExitLimit contains all information.
void addPredicate(const SCEVPredicate *P)
const SCEV * ConstantMaxNotTaken
SmallPtrSet< const SCEVPredicate *, 4 > Predicates
A set of predicate guards for this ExitLimit.
LoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)