Go to the documentation of this file.
20 #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
21 #define LLVM_ANALYSIS_SCALAREVOLUTION_H
47 class OverflowingBinaryOperator;
48 class AssumptionCache;
61 class ScalarEvolution;
65 class TargetLibraryInfo;
70 extern bool VerifySCEV;
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!");
483 return TestFlags ==
maskFlags(Flags, TestFlags);
571 unsigned Depth = 0) {
577 unsigned Depth = 0) {
586 unsigned Depth = 0) {
592 unsigned Depth = 0) {
635 bool Sequential =
false);
637 bool Sequential =
false);
730 bool Sequential =
false);
735 bool Sequential =
false);
826 const SCEV *ExitCount);
947 return getRangeRef(
S, HINT_RANGE_UNSIGNED);
963 return getRangeRef(
S, HINT_RANGE_SIGNED);
1102 const SCEV *MaxIter);
1111 bool ControllingFiniteLoop =
false);
1200 return getLoopProperties(L).HasNoAbnormalExits;
1213 void deleted()
override;
1214 void allUsesReplacedWith(
Value *New)
override;
1245 std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1279 bool WalkingBEDominatingConds =
false;
1283 bool ProvingSplitPredicate =
false;
1299 const SCEV *ExactNotTaken;
1300 const SCEV *MaxNotTaken;
1303 bool MaxOrZero =
false;
1311 assert(!isa<SCEVUnionPredicate>(
P) &&
"Only add leaf predicates here!");
1318 ExitLimit(
const SCEV *
E);
1321 const SCEV *
E,
const SCEV *M,
bool MaxOrZero,
1324 ExitLimit(
const SCEV *
E,
const SCEV *M,
bool MaxOrZero,
1327 ExitLimit(
const SCEV *
E,
const SCEV *M,
bool MaxOrZero);
1331 bool hasAnyInfo()
const {
1332 return !isa<SCEVCouldNotCompute>(ExactNotTaken) ||
1333 !isa<SCEVCouldNotCompute>(MaxNotTaken);
1337 bool hasFullInfo()
const {
1338 return !isa<SCEVCouldNotCompute>(ExactNotTaken);
1344 struct ExitNotTakenInfo {
1345 PoisoningVH<BasicBlock> ExitingBlock;
1346 const SCEV *ExactNotTaken;
1347 const SCEV *MaxNotTaken;
1348 SmallPtrSet<const SCEVPredicate *, 4> Predicates;
1350 explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock,
1351 const SCEV *ExactNotTaken,
1352 const SCEV *MaxNotTaken,
1353 const SmallPtrSet<const SCEVPredicate *, 4> &Predicates)
1354 : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1355 MaxNotTaken(ExactNotTaken), Predicates(Predicates) {}
1357 bool hasAlwaysTruePredicate()
const {
1358 return Predicates.empty();
1365 class BackedgeTakenInfo {
1370 SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1375 const SCEV *ConstantMax;
1383 const SCEV *SymbolicMax =
nullptr;
1386 bool MaxOrZero =
false;
1388 bool isComplete()
const {
return IsComplete; }
1389 const SCEV *getConstantMax()
const {
return ConstantMax; }
1392 BackedgeTakenInfo() : ConstantMax(nullptr), IsComplete(
false) {}
1393 BackedgeTakenInfo(BackedgeTakenInfo &&) =
default;
1394 BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) =
default;
1396 using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1399 BackedgeTakenInfo(ArrayRef<EdgeExitInfo> ExitCounts,
bool IsComplete,
1400 const SCEV *ConstantMax,
bool MaxOrZero);
1404 bool hasAnyInfo()
const {
1405 return !ExitNotTaken.empty() ||
1406 !isa<SCEVCouldNotCompute>(getConstantMax());
1410 bool hasFullInfo()
const {
return isComplete(); }
1431 SmallVector<const SCEVPredicate *, 4> *Predicates =
nullptr)
const;
1437 const SCEV *getExact(
const BasicBlock *ExitingBlock,
1444 const SCEV *getConstantMax(
const BasicBlock *ExitingBlock,
1457 DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1461 DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1464 DenseMap<const SCEV *, SmallPtrSet<PointerIntPair<const Loop *, 1, bool>, 4>>
1471 DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1476 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1481 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1482 ValuesAtScopesUsers;
1485 DenseMap<
const SCEV *,
1486 SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
1489 struct LoopProperties {
1495 bool HasNoAbnormalExits;
1499 bool HasNoSideEffects;
1503 DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1506 LoopProperties getLoopProperties(
const Loop *L);
1508 bool loopHasNoSideEffects(
const Loop *L) {
1509 return getLoopProperties(L).HasNoSideEffects;
1518 SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
1525 DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 8> > SCEVUsers;
1528 DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1531 DenseMap<const SCEV *, ConstantRange> SignedRanges;
1534 enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1537 const ConstantRange &setRange(
const SCEV *
S, RangeSignHint Hint,
1539 DenseMap<const SCEV *, ConstantRange> &Cache =
1540 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1542 auto Pair = Cache.try_emplace(
S,
std::move(CR));
1545 return Pair.first->second;
1551 const ConstantRange &getRangeRef(
const SCEV *
S, RangeSignHint Hint);
1555 ConstantRange getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
1556 const SCEV *MaxBECount,
unsigned BitWidth);
1560 ConstantRange getRangeForAffineNoSelfWrappingAR(
const SCEVAddRecExpr *AddRec,
1561 const SCEV *MaxBECount,
1563 RangeSignHint SignHint);
1568 ConstantRange getRangeViaFactoring(
const SCEV *Start,
const SCEV *Step,
1569 const SCEV *MaxBECount,
unsigned BitWidth);
1575 ConstantRange getRangeForUnknownRecurrence(
const SCEVUnknown *U);
1579 const SCEV *createSCEV(
Value *V);
1582 const SCEV *createNodeForPHI(PHINode *PN);
1585 const SCEV *createAddRecFromPHI(PHINode *PN);
1588 const SCEV *createSimpleAffineAddRec(PHINode *PN,
Value *BEValueV,
1589 Value *StartValueV);
1592 const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1598 const SCEV *createNodeForSelectOrPHIInstWithICmpInstCond(Instruction *
I,
1616 const SCEV *createNodeForGEP(GEPOperator *
GEP);
1620 const SCEV *computeSCEVAtScope(
const SCEV *
S,
const Loop *L);
1625 BackedgeTakenInfo &getBackedgeTakenInfo(
const Loop *L);
1629 const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(
const Loop *L);
1634 BackedgeTakenInfo computeBackedgeTakenCount(
const Loop *L,
1635 bool AllowPredicates =
false);
1641 ExitLimit computeExitLimit(
const Loop *L,
BasicBlock *ExitingBlock,
1642 bool AllowPredicates =
false);
1654 ExitLimit computeExitLimitFromCond(
const Loop *L,
Value *ExitCond,
1655 bool ExitIfTrue,
bool ControlsExit,
1656 bool AllowPredicates =
false);
1661 const SCEV *computeSymbolicMaxBackedgeTakenCount(
const Loop *L);
1666 class ExitLimitCache {
1672 SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1676 bool AllowPredicates;
1679 ExitLimitCache(
const Loop *L,
bool ExitIfTrue,
bool AllowPredicates)
1680 : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1682 Optional<ExitLimit>
find(
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
1683 bool ControlsExit,
bool AllowPredicates);
1685 void insert(
const Loop *L,
Value *ExitCond,
bool ExitIfTrue,
1686 bool ControlsExit,
bool AllowPredicates,
const ExitLimit &EL);
1689 using ExitLimitCacheTy = ExitLimitCache;
1691 ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1692 const Loop *L,
Value *ExitCond,
1695 bool AllowPredicates);
1696 ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache,
const Loop *L,
1697 Value *ExitCond,
bool ExitIfTrue,
1699 bool AllowPredicates);
1700 Optional<ScalarEvolution::ExitLimit>
1701 computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache,
const Loop *L,
1702 Value *ExitCond,
bool ExitIfTrue,
1703 bool ControlsExit,
bool AllowPredicates);
1710 ExitLimit computeExitLimitFromICmp(
const Loop *L, ICmpInst *ExitCond,
1713 bool AllowPredicates =
false);
1720 const SCEV *
LHS,
const SCEV *
RHS,
1722 bool AllowPredicates =
false);
1727 ExitLimit computeExitLimitFromSingleExitSwitch(
const Loop *L,
1739 ExitLimit computeShiftCompareExitLimit(
Value *
LHS,
Value *
RHS,
const Loop *L,
1747 const SCEV *computeExitCountExhaustively(
const Loop *L,
Value *
Cond,
1754 ExitLimit howFarToZero(
const SCEV *V,
const Loop *L,
bool IsSubExpr,
1755 bool AllowPredicates =
false);
1760 ExitLimit howFarToNonZero(
const SCEV *V,
const Loop *L);
1774 ExitLimit howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
1775 bool isSigned,
bool ControlsExit,
1776 bool AllowPredicates =
false);
1778 ExitLimit howManyGreaterThans(
const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
1779 bool isSigned,
bool IsSubExpr,
1780 bool AllowPredicates =
false);
1785 std::pair<const BasicBlock *, const BasicBlock *>
1786 getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *
BB)
const;
1793 const Value *FoundCondValue,
bool Inverse,
1794 const Instruction *
Context =
nullptr);
1803 const SCEV *FoundLHS,
const SCEV *FoundRHS,
1804 const Instruction *CtxI);
1812 const SCEV *FoundRHS,
1813 const Instruction *
Context =
nullptr);
1820 const SCEV *
RHS,
const SCEV *FoundLHS,
1821 const SCEV *FoundRHS,
1822 const Instruction *
Context =
nullptr);
1829 const SCEV *
LHS,
const SCEV *
RHS,
1830 const SCEV *FoundLHS,
const SCEV *FoundRHS,
1831 unsigned Depth = 0);
1836 const SCEV *
LHS,
const SCEV *
RHS);
1842 const SCEV *
RHS,
const SCEV *FoundLHS,
1843 const SCEV *FoundRHS);
1850 const SCEV *
RHS,
const SCEV *FoundLHS,
1851 const SCEV *FoundRHS);
1856 const SCEV *
LHS,
const SCEV *
RHS);
1865 const SCEV *
LHS,
const SCEV *
RHS,
1866 const SCEV *FoundLHS,
1867 const SCEV *FoundRHS);
1876 const SCEV *
LHS,
const SCEV *
RHS,
1877 const SCEV *FoundLHS,
1878 const SCEV *FoundRHS,
1879 const Instruction *CtxI);
1889 const SCEV *
LHS,
const SCEV *
RHS,
1890 const SCEV *FoundLHS,
const SCEV *FoundRHS,
1899 const SCEV *
RHS,
const SCEV *FoundLHS,
1900 const SCEV *FoundRHS);
1905 Constant *getConstantEvolutionLoopExitValue(PHINode *PN,
const APInt &BEs,
1911 const SCEV *
LHS,
const SCEV *
RHS);
1927 bool splitBinaryAdd(
const SCEV *Expr,
const SCEV *&L,
const SCEV *&R,
1931 void forgetBackedgeTakenCounts(
const Loop *L,
bool Predicated);
1934 void forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs);
1937 void forgetMemoizedResultsImpl(
const SCEV *
S);
1940 const SCEV *getExistingSCEV(
Value *V);
1943 void eraseValueFromMap(
Value *V);
1946 void insertValueToMap(
Value *V,
const SCEV *
S);
1950 bool checkValidity(
const SCEV *
S)
const;
1957 template <
typename ExtendOpTy>
1958 bool proveNoWrapByVaryingStart(
const SCEV *Start,
const SCEV *Step,
1972 Optional<MonotonicPredicateType>
1973 getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *
LHS,
1985 const Instruction *getNonTrivialDefiningScopeBound(
const SCEV *
S);
1990 const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops,
1995 const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops);
1999 bool isGuaranteedToTransferExecutionTo(
const Instruction *A,
2000 const Instruction *
B);
2018 bool isSCEVExprNeverPoison(
const Instruction *
I);
2024 bool isAddRecNeverPoison(
const Instruction *
I,
const Loop *L);
2036 Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2037 createAddRecFromPHIWithCastsImpl(
const SCEVUnknown *SymbolicPHI);
2048 const SCEV *computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
2049 const SCEV *End,
unsigned BitWidth,
2055 bool canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
bool IsSigned);
2060 bool canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
bool IsSigned);
2063 const SCEV *getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
2067 const SCEV *getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
2071 const SCEV *getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
2075 const SCEV *stripInjectiveFunctions(
const SCEV *Val)
const;
2080 void getUsedLoops(
const SCEV *
S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
2084 bool matchURem(
const SCEV *Expr,
const SCEV *&
LHS,
const SCEV *&
RHS);
2088 SCEV *findExistingSCEVInCache(
SCEVTypes SCEVType, ArrayRef<const SCEV *> Ops);
2092 void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable,
2095 FoldingSet<SCEV> UniqueSCEVs;
2096 FoldingSet<SCEVPredicate> UniquePreds;
2100 DenseMap<const Loop *, SmallVector<const SCEVAddRecExpr *, 4>> LoopUsers;
2104 DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
2105 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2106 PredicatedSCEVRewrites;
2146 std::unique_ptr<ScalarEvolution> SE;
2225 void updateGeneration();
2229 using RewriteEntry = std::pair<unsigned, const SCEV *>;
2249 std::unique_ptr<SCEVUnionPredicate> Preds;
2255 unsigned Generation = 0;
2258 const SCEV *BackedgeCount =
nullptr;
2263 #endif // LLVM_ANALYSIS_SCALAREVOLUTION_H
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds)
Union predicates don't get cached so create a dummy set ID for it.
A set of analyses that are preserved following a run of a transformation pass.
LLVMContext & getContext() const
static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID)
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.
const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
Class to represent scalable SIMD vectors.
Analysis pass that exposes the ScalarEvolution for a function.
SCEV & operator=(const SCEV &)=delete
bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0, bool ControllingFiniteLoop=false)
Simplify LHS and RHS in a comparison with predicate Pred.
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 * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
This is an optimization pass for GlobalISel generic memory operations.
static LLVM_NODISCARD SCEVWrapPredicate::IncrementWrapFlags maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask)
const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const ScalarEvolution & getSE() const
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 SCEVPredicate & getPredicate() const
A parsed version of the target data layout string in and methods for querying it.
const SCEV * getLHS() const
Returns the left hand side of the predicate.
SCEVPredicate & operator=(const SCEVPredicate &)=default
bool implies(const SCEVPredicate *N) const override
Returns true if this predicate implies N.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
virtual void print(raw_ostream &OS, unsigned Depth=0) const =0
Prints a textual representation of this predicate with an indentation of Depth.
A CRTP mix-in to automatically provide informational APIs needed for passes.
void forgetLoopDispositions(const Loop *L)
Called when the client has changed the disposition of values in this loop.
unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
const SCEV * getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth=0)
bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
Represents a single loop in the control flow graph.
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
This class uses information about analyze scalars to rewrite expressions in canonical form.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
bool implies(const SCEVPredicate *N) const override
Implementation of the SCEVPredicate interface.
PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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 ...
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
The main scalar evolution driver.
BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
Printer pass for the ScalarEvolutionAnalysis results.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
void dump() const
This method is used for debugging.
Verifier pass for the ScalarEvolutionAnalysis results.
@ LoopInvariant
The SCEV is loop-invariant.
The instances of the Type class are immutable: once they are created, they are never changed.
@ LoopComputable
The SCEV varies predictably with the loop.
static LLVM_NODISCARD SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
static LLVM_NODISCARD SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
static LLVM_NODISCARD SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
const SCEV * getConstantMaxTripCountFromArray(const Loop *L)
Returns the upper bound of the loop trip count infered from array size.
@ LoopVariant
The SCEV is loop-variant (unknown).
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
static LLVM_NODISCARD bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
const SCEV * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
ScalarEvolution & getSE()
Type * getWiderType(Type *Ty1, Type *Ty2) const
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.
const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
const SCEV * getUnknown(Value *V)
SCEVTypes getSCEVType() const
bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
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.
std::pair< SCEV::NoWrapFlags, bool > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
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 ...
bool implies(const SCEVPredicate *N) const override
Returns true if this predicate implies N.
static void Profile(const SCEV &X, FoldingSetNodeID &ID)
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.
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 None if it isn't.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
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 * getURemExpr(const SCEV *LHS, const SCEV *RHS)
Represents an unsigned remainder expression based on unsigned division.
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...
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.
LLVM Basic Block Representation.
const SCEV * getSizeOfExpr(Type *IntTy, Type *AllocTy)
Return an expression for the alloc size of AllocTy that is type IntTy.
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.
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.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
This is the shared class of boolean and integer constants.
MonotonicPredicateType
A predicate is said to be monotonically increasing if may go from being false to being true as the lo...
const SCEV * getTripCountFromExitCount(const SCEV *ExitCount, bool Extend=true)
Convert from an "exit count" (i.e.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
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...
bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
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)
const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
unsigned short getExpressionSize() const
Represent the analysis usage information of a pass.
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
const SCEV * getMulExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
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,...
static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
static unsigned ComputeHash(const SCEVPredicate &X, FoldingSetNodeID &TempID)
const SCEV * getRHS() const
Returns the right hand side of the predicate.
SCEVComparePredicate(const FoldingSetNodeIDRef ID, const ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
API to communicate dependencies between analyses during invalidation.
const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
mir Rename Register Operands
bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
unsigned short SubclassData
This field is initialized to zero and may be used in subclasses to store miscellaneous information.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
ScalarEvolutionPrinterPass(raw_ostream &OS)
bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
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.
This class represents an analyzed expression in the program.
unsigned getComplexity() const override
We estimate the complexity of a union predicate as the size number of predicates in the union.
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
FoldingSetTrait - This trait class is used to define behavior of how to "profile" (in the FoldingSet ...
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 ...
ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
bool instructionCouldExistWitthOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
SCEVPredicateKind getKind() const
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
Module * getParent()
Get the module that this global value is contained inside of...
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
This is an important class for using LLVM in a threaded context.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
unsigned getSmallConstantMaxTripCount(const Loop *L)
Returns the upper bound of the loop trip count as a normal unsigned value.
A special type used by analysis passes to provide an address that identifies that particular analysis...
const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
const SCEV * getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
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 * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
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.
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
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...
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,...
@ MonotonicallyIncreasing
static LLVM_NODISCARD SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
static LLVM_NODISCARD SCEVWrapPredicate::IncrementWrapFlags getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Returns the set of SCEVWrapPredicate no wrap flags implied by a SCEVAddRecExpr.
bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
friend class SCEVCallbackVH
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
uint32_t GetMinTrailingZeros(const SCEV *S)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
LoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
const SCEV * getAddExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
virtual bool isAlwaysTrue() const =0
Returns true if the predicate is always true.
@ BasicBlock
Various leaf nodes.
An object of this class is returned by queries that could not be answered.
static LLVM_NODISCARD SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
void print(raw_ostream &OS) const
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.
void forgetTopmostLoop(const Loop *L)
A Module instance is used to store all the information related to an LLVM module.
const SCEV * getSizeOfScalableVectorExpr(Type *IntTy, ScalableVectorType *ScalableTy)
Return an expression for sizeof ScalableTy that is type IntTy, where ScalableTy is a scalable vector ...
const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
A CRTP mix-in that provides informational APIs needed for analysis passes.
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Class for arbitrary precision integers.
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
const SCEV * getAddRecExpr(const SmallVectorImpl< const SCEV * > &Operands, const Loop *L, SCEV::NoWrapFlags Flags)
const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
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...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Class to represent struct types.
SmallVector< MachineOperand, 4 > Cond
virtual unsigned getComplexity() const
Returns the estimated complexity of this predicate.
A cache of @llvm.assume calls within a function.
Node - This class is used to maintain the singly linked bucket list in a folding set.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
friend class ScalarEvolutionsTest
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
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.
@ DominatesBlock
The SCEV dominates the block.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
SCEVWrapPredicate(const FoldingSetNodeIDRef ID, const SCEVAddRecExpr *AR, IncrementWrapFlags Flags)
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 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 * getGEPExpr(GEPOperator *GEP, const SmallVectorImpl< const SCEV * > &IndexExprs)
Returns an expression for a GEP.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
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...
This class represents a composition of other SCEV predicates, and is the class that most clients will...
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
DefaultFoldingSetTrait - This class provides default implementations for FoldingSetTrait implementati...
bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
This node represents a polynomial recurrence on the trip count of the specified loop.
This class represents an assumption made on an AddRec expression.
const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
constexpr unsigned BitWidth
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Provides information about what library functions are available for the current target.
bool isOne() const
Return true if the expression is a constant one.
const SCEV * getCouldNotCompute()
void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
Value handle with callbacks on RAUW and destruction.
This class represents a range of values.
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
const SCEV * getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
@ MonotonicallyDecreasing
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
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 SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID)
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
Optional< LoopInvariantPredicate > getLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
size_t size() const
size - Get the array size.
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
ScalarEvolutionWrapperPass()
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Type * getType() const
Return the LLVM type of this SCEV expression.
A SetVector that performs no allocations if smaller than a certain size.
A container for analyses that lazily runs them and caches their results.
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.
FunctionPass class - This class is used to implement most global optimizations.
const SmallVectorImpl< const SCEVPredicate * > & getPredicates() const
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
SCEVPredicate(const SCEVPredicate &)=default
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
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...
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
bool isZero() const
Return true if the expression is a constant 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.
bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM Value Representation.
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 unsigned short ExpressionSize
ICmpInst::Predicate getPredicate() const
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.