20#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
21#define LLVM_ANALYSIS_SCALAREVOLUTION_H
47class OverflowingBinaryOperator;
65class TargetLibraryInfo;
192 return ID ==
X.FastID;
196 return X.FastID.ComputeHash();
270 return ID ==
X.FastID;
275 return X.FastID.ComputeHash();
359 "Invalid flags value!");
376 "Invalid flags value!");
546 std::optional<SCEV::NoWrapFlags>
583 unsigned Depth = 0) {
589 unsigned Depth = 0) {
598 unsigned Depth = 0) {
604 unsigned Depth = 0) {
625 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
647 bool Sequential =
false);
649 bool Sequential =
false);
746 bool Sequential =
false);
751 bool Sequential =
false);
845 const SCEV *ExitCount);
979 return getRangeRef(S, HINT_RANGE_UNSIGNED);
995 return getRangeRef(S, HINT_RANGE_SIGNED);
1000 return getRangeRef(S, HINT_RANGE_SIGNED).
getSignedMin();
1005 return getRangeRef(S, HINT_RANGE_SIGNED).
getSignedMax();
1110 assert(!isa<SCEVUnionPredicate>(
P) &&
"Only add leaf predicates here!");
1153 bool ExitIfTrue,
bool ControlsOnlyExit,
1154 bool AllowPredicates =
false);
1171 std::optional<MonotonicPredicateType>
1187 std::optional<LoopInvariantPredicate>
1197 std::optional<LoopInvariantPredicate>
1202 const SCEV *MaxIter);
1204 std::optional<LoopInvariantPredicate>
1304 return getLoopProperties(L).HasNoAbnormalExits;
1316 if (
sizeof(
long) ==
sizeof(
int))
1318 else if (
sizeof(
long) ==
sizeof(
long long))
1336 static_assert(
sizeof(uintptr_t) <=
sizeof(
unsigned long long),
1337 "unexpected pointer size");
1342 unsigned Hash = Bits.size();
1343 for (
unsigned I = 0;
I != Bits.size(); ++
I)
1348 if (Bits.size() !=
RHS.Bits.size())
1350 for (
unsigned I = 0;
I != Bits.size(); ++
I)
1351 if (Bits[
I] !=
RHS.Bits[
I])
1360 class SCEVCallbackVH final :
public CallbackVH {
1363 void deleted()
override;
1364 void allUsesReplacedWith(
Value *New)
override;
1395 std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1437 bool WalkingBEDominatingConds =
false;
1441 bool ProvingSplitPredicate =
false;
1450 APInt getConstantMultipleImpl(
const SCEV *S);
1454 struct ExitNotTakenInfo {
1456 const SCEV *ExactNotTaken;
1457 const SCEV *ConstantMaxNotTaken;
1458 const SCEV *SymbolicMaxNotTaken;
1461 explicit ExitNotTakenInfo(
1463 const SCEV *ConstantMaxNotTaken,
const SCEV *SymbolicMaxNotTaken,
1465 : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1466 ConstantMaxNotTaken(ConstantMaxNotTaken),
1467 SymbolicMaxNotTaken(SymbolicMaxNotTaken), Predicates(Predicates) {}
1469 bool hasAlwaysTruePredicate()
const {
1470 return Predicates.
empty();
1477 class BackedgeTakenInfo {
1478 friend class ScalarEvolution;
1482 SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1487 const SCEV *ConstantMax =
nullptr;
1491 bool IsComplete =
false;
1495 const SCEV *SymbolicMax =
nullptr;
1498 bool MaxOrZero =
false;
1500 bool isComplete()
const {
return IsComplete; }
1501 const SCEV *getConstantMax()
const {
return ConstantMax; }
1504 BackedgeTakenInfo() =
default;
1505 BackedgeTakenInfo(BackedgeTakenInfo &&) =
default;
1506 BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) =
default;
1508 using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1511 BackedgeTakenInfo(ArrayRef<EdgeExitInfo> ExitCounts,
bool IsComplete,
1512 const SCEV *ConstantMax,
bool MaxOrZero);
1516 bool hasAnyInfo()
const {
1517 return !ExitNotTaken.empty() ||
1518 !isa<SCEVCouldNotCompute>(getConstantMax());
1522 bool hasFullInfo()
const {
return isComplete(); }
1542 const SCEV *getExact(
const Loop *L, ScalarEvolution *SE,
1543 SmallVector<const SCEVPredicate *, 4> *Predicates =
nullptr)
const;
1549 const SCEV *getExact(
const BasicBlock *ExitingBlock,
1550 ScalarEvolution *SE)
const;
1553 const SCEV *getConstantMax(ScalarEvolution *SE)
const;
1556 const SCEV *getConstantMax(
const BasicBlock *ExitingBlock,
1557 ScalarEvolution *SE)
const;
1560 const SCEV *getSymbolicMax(
const Loop *L, ScalarEvolution *SE);
1563 const SCEV *getSymbolicMax(
const BasicBlock *ExitingBlock,
1564 ScalarEvolution *SE)
const;
1568 bool isConstantMaxOrZero(ScalarEvolution *SE)
const;
1573 DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1577 DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1580 DenseMap<const SCEV *, SmallPtrSet<PointerIntPair<const Loop *, 1, bool>, 4>>
1587 DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1592 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1597 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1598 ValuesAtScopesUsers;
1601 DenseMap<
const SCEV *,
1602 SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
1605 struct LoopProperties {
1611 bool HasNoAbnormalExits;
1615 bool HasNoSideEffects;
1619 DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1622 LoopProperties getLoopProperties(
const Loop *L);
1624 bool loopHasNoSideEffects(
const Loop *L) {
1625 return getLoopProperties(L).HasNoSideEffects;
1634 SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
1638 BlockDisposition computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB);
1641 DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 8> > SCEVUsers;
1644 DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1647 DenseMap<const SCEV *, ConstantRange> SignedRanges;
1650 enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1653 const ConstantRange &setRange(
const SCEV *S, RangeSignHint Hint,
1655 DenseMap<const SCEV *, ConstantRange> &Cache =
1656 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1658 auto Pair = Cache.try_emplace(S, std::move(CR));
1660 Pair.first->second = std::move(CR);
1661 return Pair.first->second;
1667 const ConstantRange &getRangeRef(
const SCEV *S, RangeSignHint Hint,
1668 unsigned Depth = 0);
1672 const ConstantRange &getRangeRefIter(
const SCEV *S, RangeSignHint Hint);
1676 ConstantRange getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
1677 const APInt &MaxBECount);
1681 ConstantRange getRangeForAffineNoSelfWrappingAR(
const SCEVAddRecExpr *AddRec,
1682 const SCEV *MaxBECount,
1684 RangeSignHint SignHint);
1689 ConstantRange getRangeViaFactoring(
const SCEV *Start,
const SCEV *Step,
1690 const APInt &MaxBECount);
1696 ConstantRange getRangeForUnknownRecurrence(
const SCEVUnknown *U);
1700 const SCEV *createSCEV(Value *V);
1704 const SCEV *createSCEVIter(Value *V);
1708 const SCEV *getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops);
1711 const SCEV *createNodeForPHI(PHINode *PN);
1714 const SCEV *createAddRecFromPHI(PHINode *PN);
1717 const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
1718 Value *StartValueV);
1721 const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1727 std::optional<const SCEV *>
1728 createNodeForSelectOrPHIInstWithICmpInstCond(Type *Ty, ICmpInst *
Cond,
1729 Value *TrueVal, Value *FalseVal);
1732 const SCEV *createNodeForSelectOrPHIViaUMinSeq(Value *
I, Value *
Cond,
1740 const SCEV *createNodeForSelectOrPHI(Value *V, Value *
Cond, Value *TrueVal,
1744 const SCEV *createNodeForGEP(GEPOperator *
GEP);
1748 const SCEV *computeSCEVAtScope(
const SCEV *S,
const Loop *L);
1753 BackedgeTakenInfo &getBackedgeTakenInfo(
const Loop *L);
1757 const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(
const Loop *L);
1762 BackedgeTakenInfo computeBackedgeTakenCount(
const Loop *L,
1763 bool AllowPredicates =
false);
1769 ExitLimit computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
1770 bool AllowPredicates =
false);
1775 const SCEV *computeSymbolicMaxBackedgeTakenCount(
const Loop *L);
1780 class ExitLimitCache {
1786 SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1790 bool AllowPredicates;
1793 ExitLimitCache(
const Loop *L,
bool ExitIfTrue,
bool AllowPredicates)
1794 :
L(
L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1796 std::optional<ExitLimit>
find(
const Loop *L, Value *ExitCond,
1797 bool ExitIfTrue,
bool ControlsOnlyExit,
1798 bool AllowPredicates);
1800 void insert(
const Loop *L, Value *ExitCond,
bool ExitIfTrue,
1801 bool ControlsOnlyExit,
bool AllowPredicates,
1802 const ExitLimit &EL);
1805 using ExitLimitCacheTy = ExitLimitCache;
1807 ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1808 const Loop *L, Value *ExitCond,
1810 bool ControlsOnlyExit,
1811 bool AllowPredicates);
1812 ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache,
const Loop *L,
1813 Value *ExitCond,
bool ExitIfTrue,
1814 bool ControlsOnlyExit,
1815 bool AllowPredicates);
1816 std::optional<ScalarEvolution::ExitLimit> computeExitLimitFromCondFromBinOp(
1817 ExitLimitCacheTy &Cache,
const Loop *L, Value *ExitCond,
bool ExitIfTrue,
1818 bool ControlsOnlyExit,
bool AllowPredicates);
1825 ExitLimit computeExitLimitFromICmp(
const Loop *L, ICmpInst *ExitCond,
1828 bool AllowPredicates =
false);
1835 const SCEV *
LHS,
const SCEV *
RHS,
1837 bool AllowPredicates =
false);
1842 ExitLimit computeExitLimitFromSingleExitSwitch(
const Loop *L,
1844 BasicBlock *ExitingBB,
1854 ExitLimit computeShiftCompareExitLimit(Value *
LHS, Value *
RHS,
const Loop *L,
1862 const SCEV *computeExitCountExhaustively(
const Loop *L, Value *
Cond,
1869 ExitLimit howFarToZero(
const SCEV *V,
const Loop *L,
bool IsSubExpr,
1870 bool AllowPredicates =
false);
1875 ExitLimit howFarToNonZero(
const SCEV *V,
const Loop *L);
1889 ExitLimit howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
1890 bool isSigned,
bool ControlsOnlyExit,
1891 bool AllowPredicates =
false);
1893 ExitLimit howManyGreaterThans(
const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
1895 bool AllowPredicates =
false);
1900 std::pair<const BasicBlock *, const BasicBlock *>
1901 getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
const;
1908 const Value *FoundCondValue,
bool Inverse,
1909 const Instruction *Context =
nullptr);
1918 const SCEV *FoundLHS,
const SCEV *FoundRHS,
1919 const Instruction *CtxI);
1927 const SCEV *FoundRHS,
1928 const Instruction *Context =
nullptr);
1935 const SCEV *
RHS,
const SCEV *FoundLHS,
1936 const SCEV *FoundRHS,
1937 const Instruction *Context =
nullptr);
1944 const SCEV *
LHS,
const SCEV *
RHS,
1945 const SCEV *FoundLHS,
const SCEV *FoundRHS,
1946 unsigned Depth = 0);
1951 const SCEV *
LHS,
const SCEV *
RHS);
1957 const SCEV *
RHS,
const SCEV *FoundLHS,
1958 const SCEV *FoundRHS);
1965 const SCEV *
RHS,
const SCEV *FoundLHS,
1966 const SCEV *FoundRHS);
1971 const SCEV *
LHS,
const SCEV *
RHS);
1980 const SCEV *
LHS,
const SCEV *
RHS,
1981 const SCEV *FoundLHS,
1982 const SCEV *FoundRHS);
1991 const SCEV *
LHS,
const SCEV *
RHS,
1992 const SCEV *FoundLHS,
1993 const SCEV *FoundRHS,
1994 const Instruction *CtxI);
2004 const SCEV *
LHS,
const SCEV *
RHS,
2005 const SCEV *FoundLHS,
const SCEV *FoundRHS,
2014 const SCEV *
RHS,
const SCEV *FoundLHS,
2015 const SCEV *FoundRHS);
2020 Constant *getConstantEvolutionLoopExitValue(PHINode *PN,
const APInt &BEs,
2026 const SCEV *
LHS,
const SCEV *
RHS);
2042 bool splitBinaryAdd(
const SCEV *Expr,
const SCEV *&L,
const SCEV *&R,
2046 void forgetBackedgeTakenCounts(
const Loop *L,
bool Predicated);
2049 void forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs);
2052 void forgetMemoizedResultsImpl(
const SCEV *S);
2056 void visitAndClearUsers(SmallVectorImpl<Instruction *> &Worklist,
2057 SmallPtrSetImpl<Instruction *> &Visited,
2058 SmallVectorImpl<const SCEV *> &ToForget);
2061 const SCEV *getExistingSCEV(Value *V);
2064 void eraseValueFromMap(Value *V);
2067 void insertValueToMap(Value *V,
const SCEV *S);
2071 bool checkValidity(
const SCEV *S)
const;
2078 template <
typename ExtendOpTy>
2079 bool proveNoWrapByVaryingStart(
const SCEV *Start,
const SCEV *Step,
2093 std::optional<MonotonicPredicateType>
2094 getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *
LHS,
2106 const Instruction *getNonTrivialDefiningScopeBound(
const SCEV *S);
2111 const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops,
2116 const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops);
2120 bool isGuaranteedToTransferExecutionTo(
const Instruction *
A,
2121 const Instruction *
B);
2139 bool isSCEVExprNeverPoison(
const Instruction *
I);
2145 bool isAddRecNeverPoison(
const Instruction *
I,
const Loop *L);
2157 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2158 createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI);
2169 const SCEV *computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
2176 bool canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
bool IsSigned);
2181 bool canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
bool IsSigned);
2184 const SCEV *getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
2188 const SCEV *getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
2192 const SCEV *getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
2196 const SCEV *stripInjectiveFunctions(
const SCEV *Val)
const;
2201 void getUsedLoops(
const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
2205 bool matchURem(
const SCEV *Expr,
const SCEV *&
LHS,
const SCEV *&
RHS);
2209 SCEV *findExistingSCEVInCache(
SCEVTypes SCEVType, ArrayRef<const SCEV *> Ops);
2213 void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable,
2218 const SCEV *getWithOperands(
const SCEV *S,
2219 SmallVectorImpl<const SCEV *> &NewOps);
2221 FoldingSet<SCEV> UniqueSCEVs;
2222 FoldingSet<SCEVPredicate> UniquePreds;
2226 DenseMap<const Loop *, SmallVector<const SCEVAddRecExpr *, 4>> LoopUsers;
2230 DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
2231 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2232 PredicatedSCEVRewrites;
2236 SmallPtrSet<const SCEVAddRecExpr *, 16> UnsignedWrapViaInductionTried;
2240 SmallPtrSet<const SCEVAddRecExpr *, 16> SignedWrapViaInductionTried;
2280 std::unique_ptr<ScalarEvolution> SE;
2359 void updateGeneration();
2363 using RewriteEntry = std::pair<unsigned, const SCEV *>;
2383 std::unique_ptr<SCEVUnionPredicate> Preds;
2389 unsigned Generation = 0;
2392 const SCEV *BackedgeCount =
nullptr;
2398 ID.addInteger(~0ULL);
2403 ID.addInteger(~0ULL - 1ULL);
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
This file implements a class to represent arbitrary precision integral constant values and operations...
SmallVector< MachineOperand, 4 > Cond
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.
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.
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.
Module * getParent()
Get the module that this global value is contained inside of...
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.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
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 * 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...
const SmallVectorImpl< const SCEVPredicate * > & getPredicates() const
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.
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
void addInteger(unsigned long I)
void addInteger(unsigned long long I)
unsigned computeHash() const
void addInteger(unsigned I)
void addPointer(const void *Ptr)
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...
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.
bool instructionCouldExistWitthOperands(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...
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...
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,...
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 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.
const SCEV * getConstantMaxTripCountFromArray(const Loop *L)
Returns the upper bound of the loop trip count infered from array size.
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.
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.
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 * 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.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ BasicBlock
Various leaf nodes.
static 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)