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!");
486 return TestFlags ==
maskFlags(Flags, TestFlags);
546 std::optional<SCEV::NoWrapFlags>
587 unsigned Depth = 0) {
593 unsigned Depth = 0) {
602 unsigned Depth = 0) {
608 unsigned Depth = 0) {
629 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
651 bool Sequential =
false);
653 bool Sequential =
false);
750 bool Sequential =
false);
755 bool Sequential =
false);
842 const SCEV *ExitCount);
980 return getRangeRef(S, HINT_RANGE_UNSIGNED);
996 return getRangeRef(S, HINT_RANGE_SIGNED);
1001 return getRangeRef(S, HINT_RANGE_SIGNED).
getSignedMin();
1006 return getRangeRef(S, HINT_RANGE_SIGNED).
getSignedMax();
1111 assert(!isa<SCEVUnionPredicate>(
P) &&
"Only add leaf predicates here!");
1154 bool ExitIfTrue,
bool ControlsOnlyExit,
1155 bool AllowPredicates =
false);
1172 std::optional<MonotonicPredicateType>
1188 std::optional<LoopInvariantPredicate>
1198 std::optional<LoopInvariantPredicate>
1203 const SCEV *MaxIter);
1205 std::optional<LoopInvariantPredicate>
1305 return getLoopProperties(L).HasNoAbnormalExits;
1326 const SCEV *
Op =
nullptr;
1327 const Type *Ty =
nullptr;
1341 reinterpret_cast<uintptr_t
>(Ty)));
1345 return std::tie(
Op, Ty, C) == std::tie(
RHS.Op,
RHS.Ty,
RHS.C);
1352 class SCEVCallbackVH final :
public CallbackVH {
1355 void deleted()
override;
1356 void allUsesReplacedWith(
Value *New)
override;
1387 std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1429 bool WalkingBEDominatingConds =
false;
1433 bool ProvingSplitPredicate =
false;
1442 APInt getConstantMultipleImpl(
const SCEV *S);
1446 struct ExitNotTakenInfo {
1448 const SCEV *ExactNotTaken;
1449 const SCEV *ConstantMaxNotTaken;
1450 const SCEV *SymbolicMaxNotTaken;
1453 explicit ExitNotTakenInfo(
1455 const SCEV *ConstantMaxNotTaken,
const SCEV *SymbolicMaxNotTaken,
1457 : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1458 ConstantMaxNotTaken(ConstantMaxNotTaken),
1459 SymbolicMaxNotTaken(SymbolicMaxNotTaken), Predicates(Predicates) {}
1461 bool hasAlwaysTruePredicate()
const {
1462 return Predicates.
empty();
1469 class BackedgeTakenInfo {
1470 friend class ScalarEvolution;
1474 SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1479 const SCEV *ConstantMax =
nullptr;
1483 bool IsComplete =
false;
1487 const SCEV *SymbolicMax =
nullptr;
1490 bool MaxOrZero =
false;
1492 bool isComplete()
const {
return IsComplete; }
1493 const SCEV *getConstantMax()
const {
return ConstantMax; }
1496 BackedgeTakenInfo() =
default;
1497 BackedgeTakenInfo(BackedgeTakenInfo &&) =
default;
1498 BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) =
default;
1500 using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1503 BackedgeTakenInfo(ArrayRef<EdgeExitInfo> ExitCounts,
bool IsComplete,
1504 const SCEV *ConstantMax,
bool MaxOrZero);
1508 bool hasAnyInfo()
const {
1509 return !ExitNotTaken.empty() ||
1510 !isa<SCEVCouldNotCompute>(getConstantMax());
1514 bool hasFullInfo()
const {
return isComplete(); }
1534 const SCEV *getExact(
const Loop *L, ScalarEvolution *SE,
1535 SmallVector<const SCEVPredicate *, 4> *Predicates =
nullptr)
const;
1541 const SCEV *getExact(
const BasicBlock *ExitingBlock,
1542 ScalarEvolution *SE)
const;
1545 const SCEV *getConstantMax(ScalarEvolution *SE)
const;
1548 const SCEV *getConstantMax(
const BasicBlock *ExitingBlock,
1549 ScalarEvolution *SE)
const;
1552 const SCEV *getSymbolicMax(
const Loop *L, ScalarEvolution *SE);
1555 const SCEV *getSymbolicMax(
const BasicBlock *ExitingBlock,
1556 ScalarEvolution *SE)
const;
1560 bool isConstantMaxOrZero(ScalarEvolution *SE)
const;
1565 DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1569 DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1572 DenseMap<const SCEV *, SmallPtrSet<PointerIntPair<const Loop *, 1, bool>, 4>>
1579 DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1584 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1589 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1590 ValuesAtScopesUsers;
1593 DenseMap<
const SCEV *,
1594 SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
1597 struct LoopProperties {
1603 bool HasNoAbnormalExits;
1607 bool HasNoSideEffects;
1611 DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1614 LoopProperties getLoopProperties(
const Loop *L);
1616 bool loopHasNoSideEffects(
const Loop *L) {
1617 return getLoopProperties(L).HasNoSideEffects;
1626 SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
1630 BlockDisposition computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB);
1633 DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 8> > SCEVUsers;
1636 DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1639 DenseMap<const SCEV *, ConstantRange> SignedRanges;
1642 enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1645 const ConstantRange &setRange(
const SCEV *S, RangeSignHint Hint,
1647 DenseMap<const SCEV *, ConstantRange> &Cache =
1648 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1650 auto Pair = Cache.try_emplace(S, std::move(CR));
1652 Pair.first->second = std::move(CR);
1653 return Pair.first->second;
1659 const ConstantRange &getRangeRef(
const SCEV *S, RangeSignHint Hint,
1660 unsigned Depth = 0);
1664 const ConstantRange &getRangeRefIter(
const SCEV *S, RangeSignHint Hint);
1668 ConstantRange getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
1669 const APInt &MaxBECount);
1673 ConstantRange getRangeForAffineNoSelfWrappingAR(
const SCEVAddRecExpr *AddRec,
1674 const SCEV *MaxBECount,
1676 RangeSignHint SignHint);
1681 ConstantRange getRangeViaFactoring(
const SCEV *Start,
const SCEV *Step,
1682 const APInt &MaxBECount);
1688 ConstantRange getRangeForUnknownRecurrence(
const SCEVUnknown *U);
1692 const SCEV *createSCEV(Value *V);
1696 const SCEV *createSCEVIter(Value *V);
1700 const SCEV *getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops);
1703 const SCEV *createNodeForPHI(PHINode *PN);
1706 const SCEV *createAddRecFromPHI(PHINode *PN);
1709 const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
1710 Value *StartValueV);
1713 const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1719 std::optional<const SCEV *>
1720 createNodeForSelectOrPHIInstWithICmpInstCond(Type *Ty, ICmpInst *
Cond,
1721 Value *TrueVal, Value *FalseVal);
1724 const SCEV *createNodeForSelectOrPHIViaUMinSeq(Value *
I, Value *
Cond,
1732 const SCEV *createNodeForSelectOrPHI(Value *V, Value *
Cond, Value *TrueVal,
1736 const SCEV *createNodeForGEP(GEPOperator *
GEP);
1740 const SCEV *computeSCEVAtScope(
const SCEV *S,
const Loop *L);
1745 BackedgeTakenInfo &getBackedgeTakenInfo(
const Loop *L);
1749 const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(
const Loop *L);
1754 BackedgeTakenInfo computeBackedgeTakenCount(
const Loop *L,
1755 bool AllowPredicates =
false);
1761 ExitLimit computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
1762 bool AllowPredicates =
false);
1767 const SCEV *computeSymbolicMaxBackedgeTakenCount(
const Loop *L);
1772 class ExitLimitCache {
1778 SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1782 bool AllowPredicates;
1785 ExitLimitCache(
const Loop *L,
bool ExitIfTrue,
bool AllowPredicates)
1786 :
L(
L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1788 std::optional<ExitLimit>
find(
const Loop *L, Value *ExitCond,
1789 bool ExitIfTrue,
bool ControlsOnlyExit,
1790 bool AllowPredicates);
1792 void insert(
const Loop *L, Value *ExitCond,
bool ExitIfTrue,
1793 bool ControlsOnlyExit,
bool AllowPredicates,
1794 const ExitLimit &EL);
1797 using ExitLimitCacheTy = ExitLimitCache;
1799 ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1800 const Loop *L, Value *ExitCond,
1802 bool ControlsOnlyExit,
1803 bool AllowPredicates);
1804 ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache,
const Loop *L,
1805 Value *ExitCond,
bool ExitIfTrue,
1806 bool ControlsOnlyExit,
1807 bool AllowPredicates);
1808 std::optional<ScalarEvolution::ExitLimit> computeExitLimitFromCondFromBinOp(
1809 ExitLimitCacheTy &Cache,
const Loop *L, Value *ExitCond,
bool ExitIfTrue,
1810 bool ControlsOnlyExit,
bool AllowPredicates);
1817 ExitLimit computeExitLimitFromICmp(
const Loop *L, ICmpInst *ExitCond,
1820 bool AllowPredicates =
false);
1827 const SCEV *
LHS,
const SCEV *
RHS,
1829 bool AllowPredicates =
false);
1834 ExitLimit computeExitLimitFromSingleExitSwitch(
const Loop *L,
1836 BasicBlock *ExitingBB,
1846 ExitLimit computeShiftCompareExitLimit(Value *
LHS, Value *
RHS,
const Loop *L,
1854 const SCEV *computeExitCountExhaustively(
const Loop *L, Value *
Cond,
1861 ExitLimit howFarToZero(
const SCEV *V,
const Loop *L,
bool IsSubExpr,
1862 bool AllowPredicates =
false);
1867 ExitLimit howFarToNonZero(
const SCEV *V,
const Loop *L);
1881 ExitLimit howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
1882 bool isSigned,
bool ControlsOnlyExit,
1883 bool AllowPredicates =
false);
1885 ExitLimit howManyGreaterThans(
const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
1887 bool AllowPredicates =
false);
1892 std::pair<const BasicBlock *, const BasicBlock *>
1893 getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
const;
1900 const Value *FoundCondValue,
bool Inverse,
1901 const Instruction *Context =
nullptr);
1910 const SCEV *FoundLHS,
const SCEV *FoundRHS,
1911 const Instruction *CtxI);
1919 const SCEV *FoundRHS,
1920 const Instruction *Context =
nullptr);
1927 const SCEV *
RHS,
const SCEV *FoundLHS,
1928 const SCEV *FoundRHS,
1929 const Instruction *Context =
nullptr);
1936 const SCEV *
LHS,
const SCEV *
RHS,
1937 const SCEV *FoundLHS,
const SCEV *FoundRHS,
1938 unsigned Depth = 0);
1943 const SCEV *
LHS,
const SCEV *
RHS);
1949 const SCEV *
RHS,
const SCEV *FoundLHS,
1950 const SCEV *FoundRHS);
1959 const SCEV *FoundLHS,
1960 const SCEV *FoundRHS);
1965 const SCEV *
LHS,
const SCEV *
RHS);
1974 const SCEV *
LHS,
const SCEV *
RHS,
1975 const SCEV *FoundLHS,
1976 const SCEV *FoundRHS);
1985 const SCEV *
LHS,
const SCEV *
RHS,
1986 const SCEV *FoundLHS,
1987 const SCEV *FoundRHS,
1988 const Instruction *CtxI);
1998 const SCEV *
LHS,
const SCEV *
RHS,
1999 const SCEV *FoundLHS,
const SCEV *FoundRHS,
2008 const SCEV *
RHS,
const SCEV *FoundLHS,
2009 const SCEV *FoundRHS);
2014 Constant *getConstantEvolutionLoopExitValue(PHINode *PN,
const APInt &BEs,
2020 const SCEV *
LHS,
const SCEV *
RHS);
2036 bool splitBinaryAdd(
const SCEV *Expr,
const SCEV *&L,
const SCEV *&R,
2040 void forgetBackedgeTakenCounts(
const Loop *L,
bool Predicated);
2043 void forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs);
2046 void forgetMemoizedResultsImpl(
const SCEV *S);
2050 void visitAndClearUsers(SmallVectorImpl<Instruction *> &Worklist,
2051 SmallPtrSetImpl<Instruction *> &Visited,
2052 SmallVectorImpl<const SCEV *> &ToForget);
2055 void eraseValueFromMap(Value *V);
2058 void insertValueToMap(Value *V,
const SCEV *S);
2062 bool checkValidity(
const SCEV *S)
const;
2069 template <
typename ExtendOpTy>
2070 bool proveNoWrapByVaryingStart(
const SCEV *Start,
const SCEV *Step,
2084 std::optional<MonotonicPredicateType>
2085 getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *
LHS,
2097 const Instruction *getNonTrivialDefiningScopeBound(
const SCEV *S);
2102 const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops,
2107 const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops);
2111 bool isGuaranteedToTransferExecutionTo(
const Instruction *
A,
2112 const Instruction *
B);
2130 bool isSCEVExprNeverPoison(
const Instruction *
I);
2136 bool isAddRecNeverPoison(
const Instruction *
I,
const Loop *L);
2148 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2149 createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI);
2160 const SCEV *computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
2167 bool canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
bool IsSigned);
2172 bool canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
bool IsSigned);
2175 const SCEV *getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
2179 const SCEV *getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
2183 const SCEV *getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
2187 const SCEV *stripInjectiveFunctions(
const SCEV *Val)
const;
2192 void getUsedLoops(
const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
2196 bool matchURem(
const SCEV *Expr,
const SCEV *&
LHS,
const SCEV *&
RHS);
2200 SCEV *findExistingSCEVInCache(
SCEVTypes SCEVType, ArrayRef<const SCEV *> Ops);
2204 void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable,
2209 const SCEV *getWithOperands(
const SCEV *S,
2210 SmallVectorImpl<const SCEV *> &NewOps);
2212 FoldingSet<SCEV> UniqueSCEVs;
2213 FoldingSet<SCEVPredicate> UniquePreds;
2217 DenseMap<const Loop *, SmallVector<const SCEVAddRecExpr *, 4>> LoopUsers;
2221 DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
2222 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2223 PredicatedSCEVRewrites;
2227 SmallPtrSet<const SCEVAddRecExpr *, 16> UnsignedWrapViaInductionTried;
2231 SmallPtrSet<const SCEVAddRecExpr *, 16> SignedWrapViaInductionTried;
2274 std::unique_ptr<ScalarEvolution> SE;
2353 void updateGeneration();
2357 using RewriteEntry = std::pair<unsigned, const SCEV *>;
2377 std::unique_ptr<SCEVUnionPredicate> Preds;
2383 unsigned Generation = 0;
2386 const SCEV *BackedgeCount =
nullptr;
This file implements a class to represent arbitrary precision integral constant values and operations...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isSigned(unsigned int Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
mir Rename Register Operands
This header defines various interfaces for pass management in LLVM.
This file defines the PointerIntPair class.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Class for arbitrary precision integers.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Value handle with callbacks on RAUW and destruction.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
This is the shared class of boolean and integer constants.
This class represents a range of values.
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Node - This class is used to maintain the singly linked bucket list in a folding set.
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
FunctionPass class - This class is used to implement most global optimizations.
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
FoldID(SCEVTypes C, const SCEV *Op, const Type *Ty)
unsigned computeHash() const
The main scalar evolution driver.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
static bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
const SCEV * getGEPExpr(GEPOperator *GEP, const SmallVectorImpl< const SCEV * > &IndexExprs)
Returns an expression for a GEP.
Type * getWiderType(Type *Ty1, Type *Ty2) const
const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
const SCEV * getURemExpr(const SCEV *LHS, const SCEV *RHS)
Represents an unsigned remainder expression based on unsigned division.
bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
APInt getConstantMultiple(const SCEV *S)
Returns the max constant multiple of S.
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
const SCEV * getAddExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?...
ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
const SCEV * getZeroExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
unsigned getSmallConstantMaxTripCount(const Loop *L)
Returns the upper bound of the loop trip count as a normal unsigned value.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
const SCEV * getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth=0)
bool isKnownViaInduction(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
std::optional< bool > evaluatePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
bool isKnownPredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
const SCEV * getMulExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
const SCEV * getSignExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
bool isKnownOnEveryIteration(ICmpInst::Predicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
const SCEV * getAddRecExpr(const SmallVectorImpl< const SCEV * > &Operands, const Loop *L, SCEV::NoWrapFlags Flags)
const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
bool instructionCouldExistWithOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
std::optional< bool > evaluatePredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
uint32_t getMinTrailingZeros(const SCEV *S)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
void print(raw_ostream &OS) const
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVector< const SCEVPredicate *, 4 > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
void forgetTopmostLoop(const Loop *L)
friend class ScalarEvolutionsTest
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
const SCEV * getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
MonotonicPredicateType
A predicate is said to be monotonically increasing if may go from being false to being true as the lo...
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopComputable
The SCEV varies predictably with the loop.
@ LoopVariant
The SCEV is loop-variant (unknown).
@ LoopInvariant
The SCEV is loop-invariant.
friend class SCEVCallbackVH
const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallPtrSetImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
const SCEV * getCouldNotCompute()
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
void getPoisonGeneratingValues(SmallPtrSetImpl< const Value * > &Result, const SCEV *S)
Return the set of Values that, if poison, will definitively result in S being poison as well.
void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
const SCEV * getVScale(Type *Ty)
unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
const SCEV * getPowerOfTwo(Type *Ty, unsigned Power)
Return a SCEV for the constant Power of two.
const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
const SCEV * getUnknown(Value *V)
std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
const SCEV * getElementCount(Type *Ty, ElementCount EC)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
const SCEV * getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
const SCEV * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVMContext & getContext() const
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Class to represent struct types.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM Value Representation.
This class implements an extremely fast bulk output stream that can only output to a stream.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ BasicBlock
Various leaf nodes.
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)