20#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
21#define LLVM_ANALYSIS_SCALAREVOLUTION_H
189 return ID ==
X.FastID;
193 return X.FastID.ComputeHash();
267 return ID ==
X.FastID;
272 return X.FastID.ComputeHash();
356 "Invalid flags value!");
373 "Invalid flags value!");
385 IncrementWrapFlags Flags;
390 IncrementWrapFlags Flags);
399 bool isAlwaysTrue()
const override;
431 bool isAlwaysTrue()
const override;
482 return TestFlags ==
maskFlags(Flags, TestFlags);
543 LLVM_ABI std::optional<SCEV::NoWrapFlags>
590 unsigned Depth = 0) {
596 unsigned Depth = 0) {
605 unsigned Depth = 0) {
611 unsigned Depth = 0) {
633 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
660 bool Sequential =
false);
662 bool Sequential =
false);
762 bool Sequential =
false);
768 bool Sequential =
false);
859 const SCEV *ExitCount);
1024 return getRangeRef(S, HINT_RANGE_UNSIGNED);
1029 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin();
1034 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax();
1040 return getRangeRef(S, HINT_RANGE_SIGNED);
1045 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin();
1050 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax();
1071 bool OrNegative =
false);
1097 LLVM_ABI std::pair<const SCEV *, const SCEV *>
1208 bool ControlsOnlyExit,
1209 bool AllowPredicates =
false);
1226 LLVM_ABI std::optional<MonotonicPredicateType>
1241 LLVM_ABI std::optional<LoopInvariantPredicate>
1250 LLVM_ABI std::optional<LoopInvariantPredicate>
1255 const SCEV *MaxIter);
1257 LLVM_ABI std::optional<LoopInvariantPredicate>
1310 FunctionAnalysisManager::Invalidator &Inv);
1353 bool PreserveNUW =
false;
1354 bool PreserveNSW =
false;
1366 unsigned Depth = 0);
1372 static void collectFromPHI(
1397 return getLoopProperties(L).HasNoAbnormalExits;
1419 const SCEV *Op =
nullptr;
1420 const Type *Ty =
nullptr;
1434 reinterpret_cast<uintptr_t
>(Ty)));
1438 return std::tie(Op, Ty, C) == std::tie(
RHS.Op,
RHS.Ty,
RHS.C);
1448 void deleted()
override;
1449 void allUsesReplacedWith(
Value *New)
override;
1455 friend class SCEVCallbackVH;
1483 std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1489 HasRecMapType HasRecMap;
1497 ExprValueMapType ExprValueMap;
1500 using ValueExprMapType =
1504 ValueExprMapType ValueExprMap;
1525 bool WalkingBEDominatingConds =
false;
1529 bool ProvingSplitPredicate =
false;
1539 APInt getConstantMultipleImpl(
const SCEV *S,
1544 struct ExitNotTakenInfo {
1546 const SCEV *ExactNotTaken;
1547 const SCEV *ConstantMaxNotTaken;
1548 const SCEV *SymbolicMaxNotTaken;
1552 const SCEV *ExactNotTaken,
1553 const SCEV *ConstantMaxNotTaken,
1554 const SCEV *SymbolicMaxNotTaken,
1556 : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1557 ConstantMaxNotTaken(ConstantMaxNotTaken),
1558 SymbolicMaxNotTaken(SymbolicMaxNotTaken), Predicates(Predicates) {}
1560 bool hasAlwaysTruePredicate()
const {
1561 return Predicates.
empty();
1568 class BackedgeTakenInfo {
1569 friend class ScalarEvolution;
1573 SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1578 const SCEV *ConstantMax =
nullptr;
1582 bool IsComplete =
false;
1586 const SCEV *SymbolicMax =
nullptr;
1589 bool MaxOrZero =
false;
1591 bool isComplete()
const {
return IsComplete; }
1592 const SCEV *getConstantMax()
const {
return ConstantMax; }
1594 LLVM_ABI const ExitNotTakenInfo *getExitNotTaken(
1595 const BasicBlock *ExitingBlock,
1596 SmallVectorImpl<const SCEVPredicate *> *Predicates =
nullptr)
const;
1599 BackedgeTakenInfo() =
default;
1600 BackedgeTakenInfo(BackedgeTakenInfo &&) =
default;
1601 BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) =
default;
1603 using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1607 bool IsComplete,
const SCEV *ConstantMax,
1612 bool hasAnyInfo()
const {
1613 return !ExitNotTaken.empty() ||
1618 bool hasFullInfo()
const {
return isComplete(); }
1639 const Loop *L, ScalarEvolution *SE,
1640 SmallVectorImpl<const SCEVPredicate *> *Predicates =
nullptr)
const;
1647 const SCEV *getExact(
1648 const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1649 SmallVectorImpl<const SCEVPredicate *> *Predicates =
nullptr)
const {
1650 if (
auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1651 return ENT->ExactNotTaken;
1653 return SE->getCouldNotCompute();
1657 LLVM_ABI const SCEV *getConstantMax(
1658 ScalarEvolution *SE,
1659 SmallVectorImpl<const SCEVPredicate *> *Predicates =
nullptr)
const;
1662 const SCEV *getConstantMax(
1663 const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1664 SmallVectorImpl<const SCEVPredicate *> *Predicates =
nullptr)
const {
1665 if (
auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1666 return ENT->ConstantMaxNotTaken;
1668 return SE->getCouldNotCompute();
1672 LLVM_ABI const SCEV *getSymbolicMax(
1673 const Loop *L, ScalarEvolution *SE,
1674 SmallVectorImpl<const SCEVPredicate *> *Predicates =
nullptr);
1677 const SCEV *getSymbolicMax(
1678 const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1679 SmallVectorImpl<const SCEVPredicate *> *Predicates =
nullptr)
const {
1680 if (
auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1681 return ENT->SymbolicMaxNotTaken;
1683 return SE->getCouldNotCompute();
1688 LLVM_ABI bool isConstantMaxOrZero(ScalarEvolution *SE)
const;
1693 DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1697 DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1700 DenseMap<const SCEV *, SmallPtrSet<PointerIntPair<const Loop *, 1, bool>, 4>>
1707 DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1712 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1717 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1718 ValuesAtScopesUsers;
1721 DenseMap<
const SCEV *,
1725 struct LoopProperties {
1731 bool HasNoAbnormalExits;
1735 bool HasNoSideEffects;
1739 DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1742 LLVM_ABI LoopProperties getLoopProperties(
const Loop *L);
1744 bool loopHasNoSideEffects(
const Loop *L) {
1745 return getLoopProperties(L).HasNoSideEffects;
1758 BlockDisposition computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB);
1761 DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 8> > SCEVUsers;
1764 DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1767 DenseMap<const SCEV *, ConstantRange> SignedRanges;
1770 enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1773 const ConstantRange &setRange(
const SCEV *S, RangeSignHint Hint,
1775 DenseMap<const SCEV *, ConstantRange> &Cache =
1776 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1778 auto Pair = Cache.insert_or_assign(S, std::move(CR));
1779 return Pair.first->second;
1785 LLVM_ABI const ConstantRange &getRangeRef(
const SCEV *S, RangeSignHint Hint,
1786 unsigned Depth = 0);
1790 const ConstantRange &getRangeRefIter(
const SCEV *S, RangeSignHint Hint);
1794 ConstantRange getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
1795 const APInt &MaxBECount);
1799 ConstantRange getRangeForAffineNoSelfWrappingAR(
const SCEVAddRecExpr *AddRec,
1800 const SCEV *MaxBECount,
1802 RangeSignHint SignHint);
1807 ConstantRange getRangeViaFactoring(
const SCEV *Start,
const SCEV *Step,
1808 const APInt &MaxBECount);
1814 ConstantRange getRangeForUnknownRecurrence(
const SCEVUnknown *U);
1818 const SCEV *createSCEV(
Value *V);
1822 const SCEV *createSCEVIter(
Value *V);
1826 const SCEV *getOperandsToCreate(
Value *V, SmallVectorImpl<Value *> &
Ops);
1830 const SCEV *createNodeForPHIWithIdenticalOperands(PHINode *PN);
1833 const SCEV *createNodeForPHI(PHINode *PN);
1836 const SCEV *createAddRecFromPHI(PHINode *PN);
1839 const SCEV *createSimpleAffineAddRec(PHINode *PN,
Value *BEValueV,
1840 Value *StartValueV);
1843 const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1849 std::optional<const SCEV *>
1850 createNodeForSelectOrPHIInstWithICmpInstCond(
Type *Ty, ICmpInst *
Cond,
1866 const SCEV *createNodeForGEP(GEPOperator *
GEP);
1870 const SCEV *computeSCEVAtScope(
const SCEV *S,
const Loop *L);
1875 BackedgeTakenInfo &getBackedgeTakenInfo(
const Loop *L);
1879 BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(
const Loop *L);
1884 BackedgeTakenInfo computeBackedgeTakenCount(
const Loop *L,
1885 bool AllowPredicates =
false);
1891 ExitLimit computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
1892 bool IsOnlyExit,
bool AllowPredicates =
false);
1897 class ExitLimitCache {
1903 SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1907 bool AllowPredicates;
1910 ExitLimitCache(
const Loop *L,
bool ExitIfTrue,
bool AllowPredicates)
1911 : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1913 LLVM_ABI std::optional<ExitLimit> find(
const Loop *L,
Value *ExitCond,
1915 bool ControlsOnlyExit,
1916 bool AllowPredicates);
1918 LLVM_ABI void insert(
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
1919 bool ControlsOnlyExit,
bool AllowPredicates,
1920 const ExitLimit &EL);
1923 using ExitLimitCacheTy = ExitLimitCache;
1925 ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1926 const Loop *L,
Value *ExitCond,
1928 bool ControlsOnlyExit,
1929 bool AllowPredicates);
1930 ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache,
const Loop *L,
1931 Value *ExitCond,
bool ExitIfTrue,
1932 bool ControlsOnlyExit,
1933 bool AllowPredicates);
1934 std::optional<ScalarEvolution::ExitLimit> computeExitLimitFromCondFromBinOp(
1935 ExitLimitCacheTy &Cache,
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
1936 bool ControlsOnlyExit,
bool AllowPredicates);
1943 ExitLimit computeExitLimitFromICmp(
const Loop *L, ICmpInst *ExitCond,
1946 bool AllowPredicates =
false);
1952 ExitLimit computeExitLimitFromICmp(
const Loop *L, CmpPredicate Pred,
1953 const SCEV *
LHS,
const SCEV *
RHS,
1955 bool AllowPredicates =
false);
1960 ExitLimit computeExitLimitFromSingleExitSwitch(
const Loop *L,
1962 BasicBlock *ExitingBB,
1980 const SCEV *computeExitCountExhaustively(
const Loop *L,
Value *
Cond,
1987 ExitLimit howFarToZero(
const SCEV *V,
const Loop *L,
bool IsSubExpr,
1988 bool AllowPredicates =
false);
1993 ExitLimit howFarToNonZero(
const SCEV *V,
const Loop *L);
2007 ExitLimit howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
2008 bool isSigned,
bool ControlsOnlyExit,
2009 bool AllowPredicates =
false);
2011 ExitLimit howManyGreaterThans(
const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
2013 bool AllowPredicates =
false);
2018 std::pair<const BasicBlock *, const BasicBlock *>
2019 getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
const;
2025 LLVM_ABI bool isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
2026 const SCEV *
RHS,
const Value *FoundCondValue,
2028 const Instruction *
Context =
nullptr);
2034 LLVM_ABI bool isImpliedCondBalancedTypes(CmpPredicate Pred,
const SCEV *
LHS,
2036 CmpPredicate FoundPred,
2037 const SCEV *FoundLHS,
2038 const SCEV *FoundRHS,
2039 const Instruction *CtxI);
2045 LLVM_ABI bool isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
2046 const SCEV *
RHS, CmpPredicate FoundPred,
2047 const SCEV *FoundLHS,
const SCEV *FoundRHS,
2048 const Instruction *
Context =
nullptr);
2054 bool isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
2055 const SCEV *
RHS,
const SCEV *FoundLHS,
2056 const SCEV *FoundRHS,
2057 const Instruction *
Context =
nullptr);
2063 bool isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
2064 const SCEV *
RHS,
const SCEV *FoundLHS,
2065 const SCEV *FoundRHS,
unsigned Depth = 0);
2069 bool isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
const SCEV *
LHS,
2075 bool isImpliedCondOperandsHelper(CmpPredicate Pred,
const SCEV *
LHS,
2076 const SCEV *
RHS,
const SCEV *FoundLHS,
2077 const SCEV *FoundRHS);
2083 bool isImpliedCondOperandsViaRanges(CmpPredicate Pred,
const SCEV *
LHS,
2084 const SCEV *
RHS, CmpPredicate FoundPred,
2085 const SCEV *FoundLHS,
2086 const SCEV *FoundRHS);
2090 bool isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
2091 const SCEV *
LHS,
const SCEV *
RHS);
2099 bool isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
const SCEV *
LHS,
2100 const SCEV *
RHS,
const SCEV *FoundLHS,
2101 const SCEV *FoundRHS);
2109 bool isImpliedCondOperandsViaAddRecStart(CmpPredicate Pred,
const SCEV *
LHS,
2111 const SCEV *FoundLHS,
2112 const SCEV *FoundRHS,
2113 const Instruction *CtxI);
2122 bool isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
2123 const SCEV *FoundLHS,
const SCEV *FoundRHS,
2131 bool isImpliedCondOperandsViaShift(CmpPredicate Pred,
const SCEV *
LHS,
2132 const SCEV *
RHS,
const SCEV *FoundLHS,
2133 const SCEV *FoundRHS);
2138 Constant *getConstantEvolutionLoopExitValue(PHINode *PN,
const APInt &BEs,
2143 bool isKnownPredicateViaConstantRanges(CmpPredicate Pred,
const SCEV *
LHS,
2151 bool isKnownPredicateViaNoOverflow(CmpPredicate Pred,
const SCEV *
LHS,
2156 bool isKnownPredicateViaSplitting(CmpPredicate Pred,
const SCEV *
LHS,
2160 bool splitBinaryAdd(
const SCEV *Expr,
const SCEV *&L,
const SCEV *&R,
2164 void forgetBackedgeTakenCounts(
const Loop *L,
bool Predicated);
2170 void forgetMemoizedResultsImpl(
const SCEV *S);
2174 void visitAndClearUsers(SmallVectorImpl<Instruction *> &Worklist,
2175 SmallPtrSetImpl<Instruction *> &Visited,
2176 SmallVectorImpl<const SCEV *> &ToForget);
2179 void eraseValueFromMap(
Value *V);
2182 void insertValueToMap(
Value *V,
const SCEV *S);
2186 bool checkValidity(
const SCEV *S)
const;
2193 template <
typename ExtendOpTy>
2194 bool proveNoWrapByVaryingStart(
const SCEV *Start,
const SCEV *Step,
2208 std::optional<MonotonicPredicateType>
2209 getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *
LHS,
2221 const Instruction *getNonTrivialDefiningScopeBound(
const SCEV *S);
2235 bool isGuaranteedToTransferExecutionTo(
const Instruction *
A,
2236 const Instruction *
B);
2239 bool isGuaranteedNotToCauseUB(
const SCEV *
Op);
2242 static bool isGuaranteedNotToBePoison(
const SCEV *
Op);
2260 bool isSCEVExprNeverPoison(
const Instruction *
I);
2266 bool isAddRecNeverPoison(
const Instruction *
I,
const Loop *L);
2278 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2279 createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI);
2290 const SCEV *computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
2291 const SCEV *End,
unsigned BitWidth,
2297 bool canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
bool IsSigned);
2302 bool canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
bool IsSigned);
2317 const SCEV *stripInjectiveFunctions(
const SCEV *Val)
const;
2322 void getUsedLoops(
const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
2330 void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable,
2335 const SCEV *getWithOperands(
const SCEV *S,
2336 SmallVectorImpl<const SCEV *> &NewOps);
2338 FoldingSet<SCEV> UniqueSCEVs;
2339 FoldingSet<SCEVPredicate> UniquePreds;
2343 DenseMap<const Loop *, SmallVector<const SCEVAddRecExpr *, 4>> LoopUsers;
2347 DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
2348 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2349 PredicatedSCEVRewrites;
2353 SmallPtrSet<const SCEVAddRecExpr *, 16> UnsignedWrapViaInductionTried;
2357 SmallPtrSet<const SCEVAddRecExpr *, 16> SignedWrapViaInductionTried;
2400 std::unique_ptr<ScalarEvolution> SE;
2411 void releaseMemory()
override;
2414 void verifyAnalysis()
const override;
2488 void updateGeneration();
2492 using RewriteEntry = std::pair<unsigned, const SCEV *>;
2512 std::unique_ptr<SCEVUnionPredicate> Preds;
2518 unsigned Generation = 0;
2521 const SCEV *BackedgeCount =
nullptr;
2524 const SCEV *SymbolicMaxBackedgeCount =
nullptr;
2527 std::optional<unsigned> SmallConstantMaxTripCount;
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
static bool runOnFunction(Function &F, bool PostInlining)
static bool isSigned(unsigned int Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
This header defines various interfaces for pass management in LLVM.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
This file defines the PointerIntPair class.
const SmallVectorImpl< MachineOperand > & Cond
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
Class for arbitrary precision integers.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
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.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
This is the shared class of boolean and integer constants.
This class represents a range of values.
This is an important base class in LLVM.
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.
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Represents flags for the getelementptr instruction/expression.
static GEPNoWrapFlags none()
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 ...
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
LLVM_ABI void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
LLVM_ABI const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
This node represents a polynomial recurrence on the trip count of the specified loop.
SCEVComparePredicate(const FoldingSetNodeIDRef ID, const ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
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, ScalarEvolution &SE) const override
Implementation of the SCEVPredicate interface.
This class represents an assumption made using SCEV expressions which can be checked at run-time.
SCEVPredicateKind getKind() const
virtual unsigned getComplexity() const
Returns the estimated complexity of this predicate.
SCEVPredicate & operator=(const SCEVPredicate &)=default
SCEVPredicate(const SCEVPredicate &)=default
virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const =0
Returns true if this predicate implies N.
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.
unsigned getComplexity() const override
We estimate the complexity of a union predicate as the size number of predicates in the union.
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds, ScalarEvolution &SE)
Union predicates don't get cached so create a dummy set ID for it.
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.
SCEVWrapPredicate(const FoldingSetNodeIDRef ID, const SCEVAddRecExpr *AR, IncrementWrapFlags Flags)
static SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
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:
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.
LLVM_ABI ArrayRef< const SCEV * > operands() const
Return operands of this SCEV expression.
unsigned short getExpressionSize() const
SCEV & operator=(const SCEV &)=delete
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
SCEV(const SCEV &)=delete
LLVM_ABI void dump() const
This method is used for debugging.
LLVM_ABI bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
LLVM_ABI bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
const unsigned short ExpressionSize
LLVM_ABI void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize)
SCEVTypes getSCEVType() const
unsigned short SubclassData
This field is initialized to zero and may be used in subclasses to store miscellaneous information.
LLVM_ABI 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.
LLVM_ABI ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
ScalarEvolutionPrinterPass(raw_ostream &OS)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Verifier pass for the ScalarEvolutionAnalysis results.
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
ScalarEvolution & getSE()
ScalarEvolutionWrapperPass()
const ScalarEvolution & getSE() const
bool operator==(const FoldID &RHS) const
FoldID(SCEVTypes C, const SCEV *Op, const Type *Ty)
unsigned computeHash() const
static LLVM_ABI LoopGuards collect(const Loop *L, ScalarEvolution &SE)
Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...
LLVM_ABI const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
static bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI bool isKnownOnEveryIteration(CmpPredicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
LLVM_ABI const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI const SCEV * getURemExpr(const SCEV *LHS, const SCEV *RHS)
Represents an unsigned remainder expression based on unsigned division.
LLVM_ABI bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
LLVM_ABI const SCEV * getPredicatedConstantMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getConstantMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
LLVM_ABI bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
LLVM_ABI bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
LLVM_ABI const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
LLVM_ABI const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI 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)
LLVM_ABI const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM_ABI ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
LLVM_ABI const SCEV * getZeroExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
friend class SCEVExpander
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
LLVM_ABI const SCEV * getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth=0)
LLVM_ABI std::optional< bool > evaluatePredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
LLVM_ABI const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
const SCEV * getMulExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
LLVM_ABI bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
LLVM_ABI void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
LLVM_ABI bool SimplifyICmpOperands(CmpPredicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
LLVM_ABI const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LLVM_ABI LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
LLVM_ABI bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
LLVM_ABI const SCEV * getSignExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
LLVM_ABI const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
const SCEV * getAddRecExpr(const SmallVectorImpl< const SCEV * > &Operands, const Loop *L, SCEV::NoWrapFlags Flags)
LLVM_ABI const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
LLVM_ABI const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
LLVM_ABI bool instructionCouldExistWithOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM_ABI void print(raw_ostream &OS) const
LLVM_ABI const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
LLVM_ABI const SCEV * getPredicatedExitCount(const Loop *L, const BasicBlock *ExitingBlock, SmallVectorImpl< const SCEVPredicate * > *Predicates, ExitCountKind Kind=Exact)
Same as above except this uses the predicated backedge taken info and may require predicates.
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
LLVM_ABI void forgetTopmostLoop(const Loop *L)
friend class ScalarEvolutionsTest
LLVM_ABI void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
const SCEV * getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
LLVM_ABI const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LLVM_ABI const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
MonotonicPredicateType
A predicate is said to be monotonically increasing if may go from being false to being true as the lo...
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
LLVM_ABI const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
LLVM_ABI const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
LLVM_ABI bool isLoopBackedgeGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
LLVM_ABI bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
LLVM_ABI BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
LLVM_ABI const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
LLVM_ABI bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
LLVM_ABI const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)
Returns the max constant multiple of S.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopComputable
The SCEV varies predictably with the loop.
@ LoopVariant
The SCEV is loop-variant (unknown).
@ LoopInvariant
The SCEV is loop-invariant.
friend class SCEVCallbackVH
LLVM_ABI bool isKnownMultipleOf(const SCEV *S, uint64_t M, SmallVectorImpl< const SCEVPredicate * > &Assumptions)
Check that S is a multiple of M.
LLVM_ABI const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
LLVM_ABI bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
LLVM_ABI std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
LLVM_ABI void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI uint32_t getMinTrailingZeros(const SCEV *S, const Instruction *CtxI=nullptr)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
LLVM_ABI const SCEV * getGEPExpr(GEPOperator *GEP, ArrayRef< const SCEV * > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
LLVM_ABI const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI void getPoisonGeneratingValues(SmallPtrSetImpl< const Value * > &Result, const SCEV *S)
Return the set of Values that, if poison, will definitively result in S being poison as well.
LLVM_ABI void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
LLVM_ABI const SCEV * getVScale(Type *Ty)
LLVM_ABI unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
LLVM_ABI bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
LLVM_ABI const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
const SCEV * getPowerOfTwo(Type *Ty, unsigned Power)
Return a SCEV for the constant Power of two.
LLVM_ABI const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
LLVM_ABI void forgetAllLoops()
LLVM_ABI bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI 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.
LLVM_ABI const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
LLVM_ABI const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
LLVM_ABI const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
LLVM_ABI std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
LLVM_ABI const SCEV * getUnknown(Value *V)
LLVM_ABI std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
LLVM_ABI const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
LLVM_ABI std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
LLVM_ABI bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
const SCEV * getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
LLVM_ABI const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
LLVM_ABI std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
LLVM_ABI bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
LLVM_ABI bool isKnownPredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI ~ScalarEvolution()
LLVM_ABI const SCEV * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI 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.
LLVM_ABI bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI bool isKnownViaInduction(CmpPredicate 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 ...
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVM_ABI void verify() const
LLVMContext & getContext() const
Implements a dense probed hash-table based set with some number of buckets stored inline.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
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.
unsigned combineHashValue(unsigned a, unsigned b)
Simplistic combination of 32-bit hash values into 32-bit hash values.
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
FunctionAddr VTableAddr Value
FoldingSetBase::Node FoldingSetNode
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
DWARFExpression::Operation Op
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
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.
LLVM_ABI SCEVCouldNotCompute()
static LLVM_ABI 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...
LLVM_ABI ExitLimit(const SCEV *E)
Construct either an exact exit limit from a constant, or an unknown one from a SCEVCouldNotCompute.
bool hasAnyInfo() const
Test whether this ExitLimit contains any computed information, or whether it's all SCEVCouldNotComput...
const SCEV * ExactNotTaken
const SCEV * SymbolicMaxNotTaken
SmallVector< const SCEVPredicate *, 4 > Predicates
A vector of predicate guards for this ExitLimit.
bool hasFullInfo() const
Test whether this ExitLimit contains all information.
const SCEV * ConstantMaxNotTaken
LoopInvariantPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)