LLVM 17.0.0git
|
The main scalar evolution driver. More...
#include "llvm/Analysis/ScalarEvolution.h"
Classes | |
struct | ExitLimit |
Information about the number of loop iterations for which a loop exit's branch condition evaluates to the not-taken path. More... | |
class | FoldID |
struct | LoopInvariantPredicate |
Public Types | |
enum | LoopDisposition { LoopVariant , LoopInvariant , LoopComputable } |
An enum describing the relationship between a SCEV and a loop. More... | |
enum | BlockDisposition { DoesNotDominateBlock , DominatesBlock , ProperlyDominatesBlock } |
An enum describing the relationship between a SCEV and a basic block. More... | |
enum | ExitCountKind { Exact , ConstantMaximum , SymbolicMaximum } |
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of times the backedge of a loop has executed before the loop is exited. More... | |
enum | MonotonicPredicateType { MonotonicallyIncreasing , MonotonicallyDecreasing } |
A predicate is said to be monotonically increasing if may go from being false to being true as the loop iterates, but never the other way around. More... | |
Public Member Functions | |
ScalarEvolution (Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI) | |
ScalarEvolution (ScalarEvolution &&Arg) | |
~ScalarEvolution () | |
LLVMContext & | getContext () const |
bool | isSCEVable (Type *Ty) const |
Test if values of the given type are analyzable within the SCEV framework. | |
uint64_t | getTypeSizeInBits (Type *Ty) const |
Return the size in bits of the specified type, for which isSCEVable must return true. | |
Type * | getEffectiveSCEVType (Type *Ty) const |
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the given type, for which isSCEVable must return true. | |
Type * | getWiderType (Type *Ty1, Type *Ty2) const |
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 same instruction. | |
bool | containsAddRecurrence (const SCEV *S) |
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr. | |
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 )? If CtxI is specified, the no-overflow fact should be true in the context of this instruction. | |
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, and deduce flag[s] that aren't known yet. | |
void | registerUser (const SCEV *User, ArrayRef< const SCEV * > Ops) |
Notify this ScalarEvolution that User directly uses SCEVs in Ops . | |
bool | containsUndefs (const SCEV *S) const |
Return true if the SCEV expression contains an undef value. | |
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 * | getSCEV (Value *V) |
Return a SCEV expression for the full generality of the specified expression. | |
const SCEV * | getConstant (ConstantInt *V) |
const SCEV * | getConstant (const APInt &Val) |
const SCEV * | getConstant (Type *Ty, uint64_t V, bool isSigned=false) |
const SCEV * | getLosslessPtrToIntExpr (const SCEV *Op, unsigned Depth=0) |
const SCEV * | getPtrToIntExpr (const SCEV *Op, Type *Ty) |
const SCEV * | getTruncateExpr (const SCEV *Op, Type *Ty, unsigned Depth=0) |
const SCEV * | getZeroExtendExpr (const SCEV *Op, Type *Ty, unsigned Depth=0) |
const SCEV * | getZeroExtendExprImpl (const SCEV *Op, Type *Ty, unsigned Depth=0) |
const SCEV * | getSignExtendExpr (const SCEV *Op, Type *Ty, unsigned Depth=0) |
const SCEV * | getSignExtendExprImpl (const SCEV *Op, Type *Ty, unsigned Depth=0) |
const SCEV * | getCastExpr (SCEVTypes Kind, const SCEV *Op, Type *Ty) |
const SCEV * | getAnyExtendExpr (const SCEV *Op, Type *Ty) |
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the given type. | |
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 * | getAddExpr (const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0) |
const SCEV * | getAddExpr (const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0) |
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 * | getMulExpr (const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0) |
const SCEV * | getMulExpr (const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0) |
const SCEV * | getUDivExpr (const SCEV *LHS, const SCEV *RHS) |
Get a canonical unsigned division expression, or something simpler if possible. | |
const SCEV * | getUDivExactExpr (const SCEV *LHS, const SCEV *RHS) |
Get a canonical unsigned division expression, or something simpler if possible. | |
const SCEV * | getURemExpr (const SCEV *LHS, const SCEV *RHS) |
Represents an unsigned remainder expression based on unsigned division. | |
const SCEV * | getAddRecExpr (const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags) |
Get an add recurrence expression for the specified loop. | |
const SCEV * | getAddRecExpr (SmallVectorImpl< const SCEV * > &Operands, const Loop *L, SCEV::NoWrapFlags Flags) |
Get an add recurrence expression for the specified loop. | |
const SCEV * | getAddRecExpr (const SmallVectorImpl< const SCEV * > &Operands, const Loop *L, SCEV::NoWrapFlags Flags) |
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 * | getGEPExpr (GEPOperator *GEP, const SmallVectorImpl< const SCEV * > &IndexExprs) |
Returns an expression for a GEP. | |
const SCEV * | getAbsExpr (const SCEV *Op, bool IsNSW) |
const SCEV * | getMinMaxExpr (SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands) |
const SCEV * | getSequentialMinMaxExpr (SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands) |
const SCEV * | getSMaxExpr (const SCEV *LHS, const SCEV *RHS) |
const SCEV * | getSMaxExpr (SmallVectorImpl< const SCEV * > &Operands) |
const SCEV * | getUMaxExpr (const SCEV *LHS, const SCEV *RHS) |
const SCEV * | getUMaxExpr (SmallVectorImpl< const SCEV * > &Operands) |
const SCEV * | getSMinExpr (const SCEV *LHS, const SCEV *RHS) |
const SCEV * | getSMinExpr (SmallVectorImpl< const SCEV * > &Operands) |
const SCEV * | getUMinExpr (const SCEV *LHS, const SCEV *RHS, bool Sequential=false) |
const SCEV * | getUMinExpr (SmallVectorImpl< const SCEV * > &Operands, bool Sequential=false) |
const SCEV * | getUnknown (Value *V) |
const SCEV * | getCouldNotCompute () |
const SCEV * | getZero (Type *Ty) |
Return a SCEV for the constant 0 of a specific type. | |
const SCEV * | getOne (Type *Ty) |
Return a SCEV for the constant 1 of a specific type. | |
const SCEV * | getMinusOne (Type *Ty) |
Return a SCEV for the constant -1 of a specific type. | |
const SCEV * | getSizeOfScalableVectorExpr (Type *IntTy, ScalableVectorType *ScalableTy) |
Return an expression for sizeof ScalableTy that is type IntTy, where ScalableTy is a scalable vector type. | |
const SCEV * | getSizeOfExpr (Type *IntTy, Type *AllocTy) |
Return an expression for the alloc size of AllocTy that is type IntTy. | |
const SCEV * | getStoreSizeOfExpr (Type *IntTy, Type *StoreTy) |
Return an expression for the store size of StoreTy that is type IntTy. | |
const SCEV * | getOffsetOfExpr (Type *IntTy, StructType *STy, unsigned FieldNo) |
Return an expression for offsetof on the given field with type IntTy. | |
const SCEV * | getNegativeSCEV (const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap) |
Return the SCEV object corresponding to -V. | |
const SCEV * | getNotSCEV (const SCEV *V) |
Return the SCEV object corresponding to ~V. | |
const SCEV * | getMinusSCEV (const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0) |
Return LHS-RHS. | |
const SCEV * | getUDivCeilSCEV (const SCEV *N, const SCEV *D) |
Compute ceil(N / D). | |
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. | |
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. | |
const SCEV * | getNoopOrZeroExtend (const SCEV *V, Type *Ty) |
Return a SCEV corresponding to a conversion of the input value to the specified type. | |
const SCEV * | getNoopOrSignExtend (const SCEV *V, Type *Ty) |
Return a SCEV corresponding to a conversion of the input value to the specified type. | |
const SCEV * | getNoopOrAnyExtend (const SCEV *V, Type *Ty) |
Return a SCEV corresponding to a conversion of the input value to the specified 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 * | getUMaxFromMismatchedTypes (const SCEV *LHS, const SCEV *RHS) |
Promote the operands to the wider of the types using zero-extension, and then perform a umax operation with them. | |
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 operation with them. | |
const SCEV * | getUMinFromMismatchedTypes (SmallVectorImpl< const SCEV * > &Ops, bool Sequential=false) |
Promote the operands to the wider of the types using zero-extension, and then perform a umin operation with them. | |
const SCEV * | getPointerBase (const SCEV *V) |
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a single pointer operand. | |
const SCEV * | removePointerBase (const SCEV *S) |
Compute an expression equivalent to S - getPointerBase(S). | |
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 * | getSCEVAtScope (Value *V, const Loop *L) |
This is a convenience function which does getSCEVAtScope(getSCEV(V), L). | |
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. | |
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 | 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 * | getTripCountFromExitCount (const SCEV *ExitCount, bool Extend=true) |
Convert from an "exit count" (i.e. | |
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. | |
unsigned | getSmallConstantTripCount (const Loop *L, const BasicBlock *ExitingBlock) |
Return the exact trip count for this loop if we exit through ExitingBlock. | |
unsigned | getSmallConstantMaxTripCount (const Loop *L) |
Returns the upper bound of the loop trip count as a normal unsigned value. | |
const SCEV * | getConstantMaxTripCountFromArray (const Loop *L) |
Returns the upper bound of the loop trip count infered from array size. | |
unsigned | getSmallConstantTripMultiple (const Loop *L, const SCEV *ExitCount) |
Returns the largest constant divisor of the trip count as a normal unsigned value, if possible. | |
unsigned | getSmallConstantTripMultiple (const Loop *L) |
Returns the largest constant divisor of the trip count of the loop. | |
unsigned | getSmallConstantTripMultiple (const Loop *L, const BasicBlock *ExitingBlock) |
Returns the largest constant divisor of the trip count of this loop as a normal unsigned value, if possible. | |
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 computable, return SCEVCouldNotCompute. | |
const SCEV * | getBackedgeTakenCount (const Loop *L, ExitCountKind Kind=Exact) |
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCouldNotCompute object. | |
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 required to be true in order for the answer to be correct. | |
const SCEV * | getConstantMaxBackedgeTakenCount (const Loop *L) |
When successful, this returns a SCEVConstant that is greater than or equal to (i.e. | |
const SCEV * | getSymbolicMaxBackedgeTakenCount (const Loop *L) |
When successful, this returns a SCEV that is greater than or equal to (i.e. | |
bool | isBackedgeTakenCountMaxOrZero (const Loop *L) |
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCount or zero. | |
bool | hasLoopInvariantBackedgeTakenCount (const Loop *L) |
Return true if the specified loop has an analyzable loop-invariant backedge-taken count. | |
void | forgetAllLoops () |
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 ScalarEvolution's ability to compute a trip count, or if the loop is deleted. | |
void | forgetTopmostLoop (const Loop *L) |
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 value, or which may disconnect it from a def-use chain linking it to a loop. | |
void | forgetLoopDispositions () |
Called when the client has changed the disposition of values in this loop. | |
void | forgetBlockAndLoopDispositions (Value *V=nullptr) |
Called when the client has changed the disposition of values in a loop or block. | |
uint32_t | GetMinTrailingZeros (const SCEV *S) |
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration). | |
ConstantRange | getUnsignedRange (const SCEV *S) |
Determine the unsigned range for a particular SCEV. | |
APInt | getUnsignedRangeMin (const SCEV *S) |
Determine the min of the unsigned range for a particular SCEV. | |
APInt | getUnsignedRangeMax (const SCEV *S) |
Determine the max of the unsigned range for a particular SCEV. | |
ConstantRange | getSignedRange (const SCEV *S) |
Determine the signed range for a particular SCEV. | |
APInt | getSignedRangeMin (const SCEV *S) |
Determine the min of the signed range for a particular SCEV. | |
APInt | getSignedRangeMax (const SCEV *S) |
Determine the max of the signed range for a particular SCEV. | |
bool | isKnownNegative (const SCEV *S) |
Test if the given expression is known to be negative. | |
bool | isKnownPositive (const SCEV *S) |
Test if the given expression is known to be positive. | |
bool | isKnownNonNegative (const SCEV *S) |
Test if the given expression is known to be non-negative. | |
bool | isKnownNonPositive (const SCEV *S) |
Test if the given expression is known to be non-positive. | |
bool | isKnownNonZero (const SCEV *S) |
Test if the given expression is known to be non-zero. | |
std::pair< const SCEV *, const SCEV * > | SplitIntoInitAndPostInc (const Loop *L, const SCEV *S) |
Splits SCEV expression S into two SCEVs. | |
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 LHS and RHS. | |
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, and RHS. | |
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, and RHS in the given Context. | |
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 . | |
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 of the recurrency LHS. | |
ExitLimit | computeExitLimitFromCond (const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsExit, bool AllowPredicates=false) |
Compute the number of times the backedge of the specified loop will execute if its exit condition were a conditional branch of ExitCond. | |
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, returns Some(MonotonicallyIncreasing) and Some(MonotonicallyDecreasing) respectively. | |
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 LoopInvariantPredicate with LHS and RHS being invariants, available at L's entry. | |
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 during at least first MaxIter iterations, return a LoopInvariantPredicate with LHS and RHS being invariants, available at L's entry. | |
std::optional< LoopInvariantPredicate > | getLoopInvariantExitCondDuringFirstIterationsImpl (ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter) |
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. | |
LoopDisposition | getLoopDisposition (const SCEV *S, const Loop *L) |
Return the "disposition" of the given SCEV with respect to the given loop. | |
bool | isLoopInvariant (const SCEV *S, const Loop *L) |
Return true if the value of the given SCEV is unchanging in the specified loop. | |
bool | isAvailableAtLoopEntry (const SCEV *S, const Loop *L) |
Determine if the SCEV can be evaluated at loop's entry. | |
bool | hasComputableLoopEvolution (const SCEV *S, const Loop *L) |
Return true if the given SCEV changes value in a known way in the specified loop. | |
BlockDisposition | getBlockDisposition (const SCEV *S, const BasicBlock *BB) |
Return the "disposition" of the given SCEV with respect to the given block. | |
bool | dominates (const SCEV *S, const BasicBlock *BB) |
Return true if elements that makes up the given SCEV dominate the specified basic block. | |
bool | properlyDominates (const SCEV *S, const BasicBlock *BB) |
Return true if elements that makes up the given SCEV properly dominate the specified basic block. | |
bool | hasOperand (const SCEV *S, const SCEV *Op) const |
Test whether the given SCEV has Op as a direct or indirect operand. | |
const SCEV * | getElementSize (Instruction *Inst) |
Return the size of an element read or written by Inst. | |
void | print (raw_ostream &OS) const |
void | verify () const |
bool | invalidate (Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv) |
const DataLayout & | getDataLayout () const |
Return the DataLayout associated with the module this SCEV instance is operating on. | |
const SCEVPredicate * | getEqualPredicate (const SCEV *LHS, const SCEV *RHS) |
const SCEVPredicate * | getComparePredicate (ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) |
const SCEVPredicate * | getWrapPredicate (const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags) |
const SCEV * | rewriteUsingPredicate (const SCEV *S, const Loop *L, const SCEVPredicate &A) |
Re-writes the SCEV according to the Predicates in A . | |
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 required. | |
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't. | |
void | setNoWrapFlags (SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags) |
Update no-wrap flags of an AddRec. | |
const SCEV * | applyLoopGuards (const SCEV *Expr, const Loop *L) |
Try to apply information from loop guards for L to Expr . | |
bool | loopHasNoAbnormalExits (const Loop *L) |
Return true if the loop has no abnormal exits. | |
bool | loopIsFiniteByAssumption (const Loop *L) |
Return true if this loop is finite by assumption. | |
Static Public Member Functions | |
static SCEV::NoWrapFlags | maskFlags (SCEV::NoWrapFlags Flags, int Mask) |
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name space. | |
static SCEV::NoWrapFlags | setFlags (SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags) |
static SCEV::NoWrapFlags | clearFlags (SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) |
static bool | hasFlags (SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags) |
Friends | |
class | ScalarEvolutionsTest |
class | SCEVCallbackVH |
class | SCEVExpander |
class | SCEVUnknown |
The main scalar evolution driver.
Because client code (intentionally) can't do much with the SCEV objects directly, they must ask this class for services.
Definition at line 452 of file ScalarEvolution.h.
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of times the backedge of a loop has executed before the loop is exited.
Definition at line 856 of file ScalarEvolution.h.
A predicate is said to be monotonically increasing if may go from being false to being true as the loop iterates, but never the other way around.
A predicate is said to be monotonically decreasing if may go from being true to being false as the loop iterates, but never the other way around.
Enumerator | |
---|---|
MonotonicallyIncreasing | |
MonotonicallyDecreasing |
Definition at line 1147 of file ScalarEvolution.h.
ScalarEvolution::ScalarEvolution | ( | Function & | F, |
TargetLibraryInfo & | TLI, | ||
AssumptionCache & | AC, | ||
DominatorTree & | DT, | ||
LoopInfo & | LI | ||
) |
Definition at line 13433 of file ScalarEvolution.cpp.
ScalarEvolution::ScalarEvolution | ( | ScalarEvolution && | Arg | ) |
Definition at line 13440 of file ScalarEvolution.cpp.
References Arg.
ScalarEvolution::~ScalarEvolution | ( | ) |
Definition at line 13471 of file ScalarEvolution.cpp.
References assert(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear().
Try to apply information from loop guards for L
to Expr
.
Definition at line 14965 of file ScalarEvolution.cpp.
References llvm::AssumptionCache::assumptions(), Cond, containsAddRecurrence(), llvm::DominatorTree::dominates(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::empty(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), getAddExpr(), llvm::BranchInst::getCondition(), getConstant(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopPredecessor(), getMinusSCEV(), getMulExpr(), getOne(), getSCEV(), getSMaxExpr(), getSMinExpr(), llvm::BranchInst::getSuccessor(), llvm::CmpInst::getSwappedPredicate(), llvm::Value::getType(), getUDivExpr(), getUMaxExpr(), getUMinExpr(), llvm::SCEVConstant::getValue(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Constant::isNullValue(), llvm::Type::isPointerTy(), llvm::BranchInst::isUnconditional(), LHS, llvm::PatternMatch::m_LogicalAnd(), llvm::PatternMatch::m_LogicalOr(), llvm::PatternMatch::m_Value(), llvm::ConstantRange::makeExactICmpRegion(), llvm::PatternMatch::match(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::reverse(), Rewriter, RHS, llvm::SmallVectorBase< Size_T >::size(), llvm::ConstantRange::sub(), and std::swap().
Referenced by llvm::LoopVectorizationCostModel::computeMaxVF(), and getSmallConstantTripMultiple().
|
inlinestatic |
Definition at line 481 of file ScalarEvolution.h.
std::optional< APInt > ScalarEvolution::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't.
This is intended to be a cheaper version of getMinusSCEV. We can be frugal here since we just bail out of actually constructing and canonicalizing an expression in the cases where the result isn't going to be a constant.
Definition at line 11904 of file ScalarEvolution.cpp.
References llvm::SCEVConstant::getAPInt(), llvm::SCEV::getType(), and getTypeSizeInBits().
Referenced by SalvageDVI().
ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCond | ( | const Loop * | L, |
Value * | ExitCond, | ||
bool | ExitIfTrue, | ||
bool | ControlsExit, | ||
bool | AllowPredicates = false |
||
) |
Compute the number of times the backedge of the specified loop will execute if its exit condition were a conditional branch of ExitCond.
ControlsExit
is true if ExitCond directly controls the exit branch. In this case, we can assume that the loop exits only if the condition is true and can infer that failing to meet the condition prior to integer wraparound results in undefined behavior.
If AllowPredicates
is set, this call will try to use a minimal set of SCEV predicates in order to return an exact answer.
Definition at line 8903 of file ScalarEvolution.cpp.
Referenced by optimizeLoopExitWithUnknownExitCount().
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
The result will be cached in HasRecMap.
Definition at line 4480 of file ScalarEvolution.cpp.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), and llvm::SCEVExprContains().
Referenced by applyLoopGuards().
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
Definition at line 13363 of file ScalarEvolution.cpp.
References llvm::SCEVUnknown::getValue(), and llvm::SCEVExprContains().
Referenced by SalvageDVI().
Return true if the SCEV expression contains an undef value.
Definition at line 13354 of file ScalarEvolution.cpp.
References llvm::SCEVUnknown::getValue(), and llvm::SCEVExprContains().
Referenced by DbgGatherSalvagableDVI(), GetInductionVariable(), SalvageDVI(), and verify().
const SCEVAddRecExpr * ScalarEvolution::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 required.
Definition at line 14557 of file ScalarEvolution.cpp.
References llvm::SmallPtrSetImpl< PtrType >::insert(), and P.
Referenced by llvm::PredicatedScalarEvolution::getAsAddRec().
std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > ScalarEvolution::createAddRecFromPHIWithCasts | ( | const SCEVUnknown * | SymbolicPHI | ) |
Checks if SymbolicPHI
can be rewritten as an AddRecExpr under some Predicates.
If successful return these <AddRecExpr, Predicates>; The function is intended to be called from PSCEV (the caller will decide whether to actually add the predicates and carry out the rewrites).
Definition at line 5639 of file ScalarEvolution.cpp.
References assert(), llvm::SCEVUnknown::getValue(), I, and isIntegerLoopHeaderPHI().
bool ScalarEvolution::dominates | ( | const SCEV * | S, |
const BasicBlock * | BB | ||
) |
Return true if elements that makes up the given SCEV dominate the specified basic block.
Definition at line 13857 of file ScalarEvolution.cpp.
References DominatesBlock, and getBlockDisposition().
Referenced by llvm::SCEVExpander::isSafeToExpandAt().
std::optional< bool > ScalarEvolution::evaluatePredicate | ( | ICmpInst::Predicate | Pred, |
const SCEV * | LHS, | ||
const SCEV * | RHS | ||
) |
Check whether the condition described by Pred, LHS, and RHS is true or false.
If we know it, return the evaluation of this condition. If neither is proved, return std::nullopt.
Definition at line 10919 of file ScalarEvolution.cpp.
References llvm::CmpInst::getInversePredicate(), isKnownPredicate(), LHS, and RHS.
Referenced by countToEliminateCompares(), and evaluatePredicateAt().
std::optional< bool > ScalarEvolution::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
.
If we know it, return the evaluation of this condition. If neither is proved, return std::nullopt.
Definition at line 10938 of file ScalarEvolution.cpp.
References evaluatePredicate(), llvm::CmpInst::getInversePredicate(), llvm::Instruction::getParent(), isBasicBlockEntryGuardedByCond(), LHS, and RHS.
Referenced by createReplacement().
void ScalarEvolution::forgetAllLoops | ( | ) |
Definition at line 8437 of file ScalarEvolution.cpp.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear().
Referenced by llvm::UnrollLoop().
void ScalarEvolution::forgetBlockAndLoopDispositions | ( | Value * | V = nullptr | ) |
Called when the client has changed the disposition of values in a loop or block.
We don't have a way to invalidate per-loop/per-block dispositions. Clear and recompute is simpler.
Definition at line 8552 of file ScalarEvolution.cpp.
References llvm::SmallVectorBase< Size_T >::empty(), llvm::Value::getType(), llvm::SmallPtrSetImpl< PtrType >::insert(), isSCEVable(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and Users.
Referenced by llvm::breakLoopBackedge(), deleteDeadBlocksFromLoop(), llvm::deleteDeadLoop(), DoFlattenLoopPair(), llvm::Loop::makeLoopInvariant(), mergeBlocksIntoPredecessors(), rebuildLoopAfterUnswitch(), sinkLoopInvariantInstructions(), llvm::UnrollAndJamLoop(), llvm::UnrollLoop(), unswitchNontrivialInvariants(), and unswitchTrivialBranch().
This method should be called by the client when it has changed a loop in a way that may effect ScalarEvolution's ability to compute a trip count, or if the loop is deleted.
This call is potentially expensive for large loop bodies.
Definition at line 8463 of file ScalarEvolution.cpp.
References llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find_as(), I, llvm::SmallVectorImpl< T >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), PushDefUseChildren(), and PushLoopPHIs().
Referenced by llvm::breakLoopBackedge(), llvm::deleteDeadLoop(), deleteLoopIfDead(), DoFlattenLoopPair(), llvm::InnerLoopVectorizer::fixVectorizedLoop(), forgetTopmostLoop(), llvm::formLCSSA(), separateNestedLoop(), llvm::splitLoopBound(), llvm::UnrollAndJamLoop(), unswitchNontrivialInvariants(), unswitchTrivialBranch(), and unswitchTrivialSwitch().
void ScalarEvolution::forgetLoopDispositions | ( | ) |
Called when the client has changed the disposition of values in this loop.
We don't have a way to invalidate per-loop dispositions. Clear and recompute is simpler.
Definition at line 8550 of file ScalarEvolution.cpp.
Definition at line 8519 of file ScalarEvolution.cpp.
References forgetLoop(), and llvm::LoopBase< BlockT, LoopT >::getOutermostLoop().
Referenced by llvm::peelLoop(), simplifyLoopCFG(), simplifyOneLoop(), llvm::UnrollLoop(), llvm::UnrollRuntimeLoopRemainder(), unswitchNontrivialInvariants(), unswitchTrivialBranch(), and unswitchTrivialSwitch().
void ScalarEvolution::forgetValue | ( | Value * | V | ) |
This method should be called by the client when it has changed a value in a way that may effect its value, or which may disconnect it from a def-use chain linking it to a loop.
Definition at line 8523 of file ScalarEvolution.cpp.
References llvm::SmallVectorBase< Size_T >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find_as(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and PushDefUseChildren().
Referenced by buildClonedLoopBlocks(), cloneLoopBlocks(), ConnectEpilog(), ConnectProlog(), llvm::formLCSSAForInstructions(), moveInstructionBefore(), llvm::SCEVExpander::replaceCongruentIVs(), replaceLoopPHINodesWithPreheaderValues(), llvm::rewriteLoopExitValues(), RewriteUsesOfClonedInstructions(), simplifyOneLoop(), and llvm::UnrollLoop().
Definition at line 3832 of file ScalarEvolution.cpp.
References llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, getNegativeSCEV(), and getSMaxExpr().
|
inline |
Definition at line 580 of file ScalarEvolution.h.
References llvm::Depth, getAddExpr(), LHS, and RHS.
|
inline |
Definition at line 586 of file ScalarEvolution.h.
References llvm::Depth, and getAddExpr().
const SCEV * ScalarEvolution::getAddExpr | ( | SmallVectorImpl< const SCEV * > & | Ops, |
SCEV::NoWrapFlags | Flags = SCEV::FlagAnyWrap , |
||
unsigned | Depth = 0 |
||
) |
Get a canonical add expression, or something simpler if possible.
Definition at line 2537 of file ScalarEvolution.cpp.
References A, llvm::APInt::abs(), llvm::Add, AddOpsInlineThreshold, llvm::append_range(), assert(), B, llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::BasicBlock::begin(), llvm::BitWidth, llvm::CallingConv::C, llvm::SmallVectorImpl< T >::clear(), CollectAddOperandsWithScales(), llvm::count_if(), llvm::Depth, llvm::DominatorTree::dominates(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorImpl< T >::erase(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, getAddExpr(), getAddRecExpr(), getAnyExtendExpr(), getConstant(), getEffectiveSCEVType(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::SCEVAddRecExpr::getLoop(), getMulExpr(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVNAryExpr::getNumOperands(), getOne(), llvm::SCEVNAryExpr::getOperand(), llvm::SCEVAddRecExpr::getStart(), getTruncateExpr(), getType(), getTypeSizeInBits(), getUDivExpr(), getZero(), GroupByComplexity(), hasFlags(), hasHugeExpression(), Idx, isAvailableAtLoopEntry(), llvm::APInt::isSignBitSet(), LHS, maskFlags(), MaxArithDepth, llvm::Mul, llvm::SCEVNAryExpr::operands(), llvm::SmallVectorTemplateBase< T, bool >::pop_back(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), RHS, llvm::scAddExpr, llvm::scAddRecExpr, llvm::scMulExpr, setFlags(), llvm::SmallVectorBase< Size_T >::size(), StrengthenNoWrapFlags(), llvm::APInt::ule(), X, and Y.
Referenced by applyLoopGuards(), llvm::calculateUpperBound(), canFoldTermCondOfLoop(), llvm::LoopVectorizationCostModel::computeMaxVF(), countToEliminateCompares(), createNodeForSelectViaUMinSeq(), llvm::createTripCountSCEV(), llvm::SCEVAddRecExpr::evaluateAtIteration(), ExtractImmediate(), ExtractSymbol(), FactorOutConstant(), findForkedSCEVs(), genLoopLimit(), getAddExpr(), getConstantMaxTripCountFromArray(), getExactSDiv(), getExtendAddRecStart(), getGEPExpr(), getLosslessPtrToIntExpr(), getMinusSCEV(), getMulExpr(), getNewAlignment(), llvm::SCEVAddRecExpr::getPostIncExpr(), getPreStartForExtend(), getSignExtendExprImpl(), getTripCount(), getTripCountFromExitCount(), getTruncateExpr(), getUDivCeilSCEV(), getUDivExpr(), getZeroExtendExprImpl(), llvm::RuntimePointerChecking::insert(), llvm::ARMTTIImpl::isHardwareLoopProfitable(), IsIncrementNSW(), IsIncrementNUW(), isSafeDecreasingBound(), isSafeIncreasingBound(), removePointerBase(), SimplifyAddOperands(), SimplifyICmpOperands(), llvm::UnrollRuntimeLoopRemainder(), llvm::SCEVRewriteVisitor< SC >::visitAddExpr(), llvm::SCEVDivision::visitAddExpr(), and willNotOverflow().
const SCEV * ScalarEvolution::getAddRecExpr | ( | const SCEV * | Start, |
const SCEV * | Step, | ||
const Loop * | L, | ||
SCEV::NoWrapFlags | Flags | ||
) |
Get an add recurrence expression for the specified loop.
Simplify the expression as much as possible.
Definition at line 3653 of file ScalarEvolution.cpp.
References llvm::append_range(), llvm::SCEV::FlagNW, getAddRecExpr(), maskFlags(), and Operands.
Referenced by CollectSubexprs(), DoInitialMatch(), ExtractImmediate(), ExtractSymbol(), FactorOutConstant(), getAddExpr(), getAddRecExpr(), getAnyExtendExpr(), getExactSDiv(), getMulExpr(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), llvm::SCEVAddRecExpr::getPostIncExpr(), getPreStartForExtend(), getSignExtendExprImpl(), llvm::SCEVAddRecExpr::getStepRecurrence(), getTruncateExpr(), getUDivExpr(), getZeroExtendExprImpl(), isLoopBackedgeGuardedByCond(), removePointerBase(), SplitAddRecs(), llvm::SCEVRewriteVisitor< SC >::visitAddRecExpr(), llvm::SCEVLoopAddRecRewriter::visitAddRecExpr(), and llvm::SCEVDivision::visitAddRecExpr().
|
inline |
Definition at line 614 of file ScalarEvolution.h.
References getAddRecExpr(), and Operands.
const SCEV * ScalarEvolution::getAddRecExpr | ( | SmallVectorImpl< const SCEV * > & | Operands, |
const Loop * | L, | ||
SCEV::NoWrapFlags | Flags | ||
) |
Get an add recurrence expression for the specified loop.
Simplify the expression as much as possible.
Definition at line 3671 of file ScalarEvolution.cpp.
References llvm::all_of(), assert(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::DominatorTree::dominates(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNW, getAddRecExpr(), getEffectiveSCEVType(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), getType(), isLoopInvariant(), maskFlags(), Operands, llvm::scAddRecExpr, and StrengthenNoWrapFlags().
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the given type.
Definition at line 2208 of file ScalarEvolution.cpp.
References assert(), llvm::SCEV::FlagNW, getAddRecExpr(), getAnyExtendExpr(), getEffectiveSCEVType(), getSignExtendExpr(), getTruncateOrNoop(), llvm::SCEV::getType(), getTypeSizeInBits(), getZeroExtendExpr(), isSCEVable(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().
Referenced by getAddExpr(), getAnyExtendExpr(), and getNoopOrAnyExtend().
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCouldNotCompute object.
The backedge-taken count is the number of times the loop header will be branched to from within the loop, assuming there are no abnormal exists like exception throws. This is one less than the trip count of the loop, since it doesn't count the first iteration, when the header is branched to from outside the loop.
Note that it is not valid to call this method on a loop without a loop-invariant backedge-taken count (see hasLoopInvariantBackedgeTakenCount).
Definition at line 8331 of file ScalarEvolution.cpp.
References ConstantMaximum, Exact, llvm_unreachable, and SymbolicMaximum.
Referenced by breakBackedgeIfNotTaken(), canFoldTermCondOfLoop(), computeTripCount(), getConstantMaxBackedgeTakenCount(), getPreStartForExtend(), getSmallConstantTripCount(), getSymbolicMaxBackedgeTakenCount(), hasLoopInvariantBackedgeTakenCount(), llvm::ARMTTIImpl::isHardwareLoopProfitable(), llvm::IVUsers::print(), PrintLoopInfo(), verify(), and verifyTripCount().
ScalarEvolution::BlockDisposition ScalarEvolution::getBlockDisposition | ( | const SCEV * | S, |
const BasicBlock * | BB | ||
) |
Return the "disposition" of the given SCEV with respect to the given block.
Definition at line 13784 of file ScalarEvolution.cpp.
References D, DoesNotDominateBlock, and llvm::reverse().
Referenced by dominates(), properlyDominates(), and verify().
Definition at line 2190 of file ScalarEvolution.cpp.
References getPtrToIntExpr(), getSignExtendExpr(), getTruncateExpr(), getZeroExtendExpr(), llvm_unreachable, llvm::scPtrToInt, llvm::scSignExtend, llvm::scTruncate, and llvm::scZeroExtend.
const SCEVPredicate * ScalarEvolution::getComparePredicate | ( | ICmpInst::Predicate | Pred, |
const SCEV * | LHS, | ||
const SCEV * | RHS | ||
) |
Definition at line 14392 of file ScalarEvolution.cpp.
References assert(), llvm::Value::getType(), LHS, llvm::SCEVPredicate::P_Compare, and RHS.
Referenced by getEqualPredicate().
Definition at line 508 of file ScalarEvolution.cpp.
References llvm::ConstantInt::get(), getConstant(), and getContext().
const SCEV * ScalarEvolution::getConstant | ( | ConstantInt * | V | ) |
Definition at line 497 of file ScalarEvolution.cpp.
References llvm::scConstant.
Referenced by applyLoopGuards(), BinomialCoefficient(), llvm::calculateUpperBound(), llvm::cannotBeMaxInLoop(), llvm::cannotBeMinInLoop(), CollectSubexprs(), llvm::LoopVectorizationCostModel::computeMaxVF(), llvm::IndexedReference::computeRefCost(), computeTripCount(), countToEliminateCompares(), DoInitialMatch(), EvaluateConstantChrecAtConstant(), ExtractImmediate(), ExtractSymbol(), FactorOutConstant(), getAddExpr(), getConstant(), getConstantMaxTripCountFromArray(), getExactSDiv(), getMinMaxExpr(), getMinusOne(), getMulExpr(), getNegativeSCEV(), getNotSCEV(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), getOffsetOfExpr(), getOne(), getSignedOverflowLimitForStep(), getSignExtendExprImpl(), getSizeOfExpr(), getStoreSizeOfExpr(), getTruncateExpr(), getUDivExactExpr(), getUDivExpr(), getUnsignedOverflowLimitForStep(), getZero(), getZeroExtendExprImpl(), llvm::InductionDescriptor::isInductionPHI(), isSafeDecreasingBound(), isSafeDependenceDistance(), isSafeIncreasingBound(), llvm::VPlanTransforms::optimizeForVFAndUF(), SimplifyAddOperands(), SimplifyICmpOperands(), SolveLinEquationWithOverflow(), SplitAddRecs(), llvm::UnrolledInstAnalyzer::UnrolledInstAnalyzer(), llvm::UnrollRuntimeLoopRemainder(), verify(), llvm::SCEVDivision::visitConstant(), and willNotOverflow().
Definition at line 513 of file ScalarEvolution.cpp.
References llvm::ConstantInt::get(), getConstant(), getEffectiveSCEVType(), and isSigned().
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
a "conservative over-approximation") of the value returend by getBackedgeTakenCount. If such a value cannot be computed, it returns the SCEVCouldNotCompute object.
Definition at line 898 of file ScalarEvolution.h.
References ConstantMaximum, and getBackedgeTakenCount().
Referenced by breakBackedgeIfNotTaken(), getSignExtendExprImpl(), getSmallConstantMaxTripCount(), getZeroExtendExprImpl(), isLoopDead(), mustBeFiniteCountedLoop(), and PrintLoopInfo().
Returns the upper bound of the loop trip count infered from array size.
Can not access bytes starting outside the statically allocated size without being immediate UB. Returns SCEVCouldNotCompute if the trip count could not inferred from array accesses.
Definition at line 8127 of file ScalarEvolution.cpp.
References assert(), llvm::LoopBase< BlockT, LoopT >::contains(), DL, llvm::DominatorTree::dominates(), GEP, getAddExpr(), llvm::AllocaInst::getAllocatedType(), llvm::AllocaInst::getArraySize(), llvm::LoopBase< BlockT, LoopT >::getBlocks(), getConstant(), getCouldNotCompute(), getDataLayout(), getElementSize(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::getLoadStorePointerOperand(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), getOne(), llvm::Instruction::getParent(), getPointerBase(), getSCEV(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEV::getType(), getUDivCeilSCEV(), getUMinFromMismatchedTypes(), llvm::LoopBase< BlockT, LoopT >::isInnermost(), isLoopInvariant(), llvm::Loop::isLoopSimplifyForm(), llvm::SCEV::isZero(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallVectorBase< Size_T >::size().
|
inline |
Definition at line 494 of file ScalarEvolution.h.
References F.
Referenced by BinomialCoefficient(), FactorOutConstant(), getConstant(), llvm::SCEVExpander::getIVIncOperand(), getMinMaxExpr(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), getPreStartForExtend(), getSignExtendExprImpl(), getUDivExpr(), getURemExpr(), getZeroExtendExprImpl(), isAddRecSExtable(), isAddSExtable(), isMulSExtable(), llvm::VPlanTransforms::optimizeForVFAndUF(), SimplifyICmpOperands(), SolveQuadraticAddRecExact(), and SolveQuadraticAddRecRange().
Definition at line 4467 of file ScalarEvolution.cpp.
Referenced by BinomialCoefficient(), getConstantMaxTripCountFromArray(), getLosslessPtrToIntExpr(), getMinAnalyzeableBackedgeTakenCount(), getMinusSCEV(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), getSmallConstantTripMultiple(), getTripCountFromExitCount(), isKnownViaInduction(), isLoopBackedgeGuardedByCond(), SolveLinEquationWithOverflow(), SplitIntoInitAndPostInc(), and verify().
|
inline |
Return the DataLayout associated with the module this SCEV instance is operating on.
Definition at line 1248 of file ScalarEvolution.h.
References llvm::Module::getDataLayout(), and llvm::GlobalValue::getParent().
Referenced by CreateStepValue(), getConstantMaxTripCountFromArray(), getEffectiveSCEVType(), getLosslessPtrToIntExpr(), getOffsetOfExpr(), getSizeOfExpr(), getStoreSizeOfExpr(), getTypeSizeInBits(), and llvm::simplifyLoopIVs().
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the given type, for which isSCEVable must return true.
For pointer types, this is the pointer-sized integer type.
For pointer types, this is the pointer index sized integer type.
Definition at line 4437 of file ScalarEvolution.cpp.
References assert(), getDataLayout(), llvm::DataLayout::getIndexType(), llvm::Type::isIntegerTy(), llvm::Type::isPointerTy(), and isSCEVable().
Referenced by canBeCheaplyTransformed(), canComputePointerDiff(), DoInitialMatch(), findForkedSCEVs(), genLoopLimit(), getAddExpr(), getAddRecExpr(), getAnyExtendExpr(), getConstant(), getElementSize(), getGEPExpr(), getLosslessPtrToIntExpr(), getMinMaxExpr(), getNegativeSCEV(), getNewAlignment(), getNotSCEV(), getSequentialMinMaxExpr(), getSignExtendExpr(), getSignExtendExprImpl(), getTruncateExpr(), getURemExpr(), getZeroExtendExpr(), isExistingPhi(), and visitIVCast().
const SCEV * ScalarEvolution::getElementSize | ( | Instruction * | Inst | ) |
Return the size of an element read or written by Inst.
Definition at line 13372 of file ScalarEvolution.cpp.
References getEffectiveSCEVType(), getSizeOfExpr(), and llvm::PointerType::getUnqual().
Referenced by getConstantMaxTripCountFromArray().
Definition at line 14386 of file ScalarEvolution.cpp.
References getComparePredicate(), llvm::CmpInst::ICMP_EQ, LHS, and RHS.
Referenced by llvm::PredicatedScalarEvolution::areAddRecsEqualWithPreds(), and llvm::replaceSymbolicStrideSCEV().
const SCEV * ScalarEvolution::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 computable, return SCEVCouldNotCompute.
For a single exit loop, this value is equivelent to the result of getBackedgeTakenCount. The loop is guaranteed to exit (via some exit) before the backedge is executed (ExitCount + 1) times. Note that there is no guarantee about which exit is taken on the exiting iteration.
Definition at line 8311 of file ScalarEvolution.cpp.
References ConstantMaximum, Exact, llvm_unreachable, and SymbolicMaximum.
Referenced by llvm::calculateUpperBound(), getMinAnalyzeableBackedgeTakenCount(), getSmallConstantTripCount(), getSmallConstantTripMultiple(), llvm::hasIterationCountInvariantInParent(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), mustBeFiniteCountedLoop(), optimizeLoopExitWithUnknownExitCount(), PrintLoopInfo(), llvm::rewriteLoopExitValues(), and llvm::UnrollRuntimeLoopRemainder().
const SCEV * ScalarEvolution::getGEPExpr | ( | GEPOperator * | GEP, |
const SmallVectorImpl< const SCEV * > & | IndexExprs | ||
) |
Returns an expression for a GEP.
GEP
The GEP. The indices contained in the GEP itself are ignored, instead we use IndexExprs. IndexExprs
The expressions for the indices.
Definition at line 3748 of file ScalarEvolution.cpp.
References assert(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, GEP, getAddExpr(), getEffectiveSCEVType(), getMulExpr(), getOffsetOfExpr(), getSCEV(), getSizeOfExpr(), getTruncateOrSignExtend(), llvm::SCEV::getType(), llvm::GetElementPtrInst::getTypeAtIndex(), llvm::ConstantInt::getValue(), llvm::APInt::getZExtValue(), isKnownNonNegative(), and llvm::Offset.
ScalarEvolution::LoopDisposition ScalarEvolution::getLoopDisposition | ( | const SCEV * | S, |
const Loop * | L | ||
) |
Return the "disposition" of the given SCEV with respect to the given loop.
Definition at line 13686 of file ScalarEvolution.cpp.
References D, LoopVariant, and llvm::reverse().
Referenced by hasComputableLoopEvolution(), llvm::hasIterationCountInvariantInParent(), isLoopInvariant(), print(), and verify().
std::optional< ScalarEvolution::LoopInvariantPredicate > ScalarEvolution::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 during at least first MaxIter iterations, return a LoopInvariantPredicate with LHS and RHS being invariants, available at L's entry.
Otherwise, return std::nullopt. The predicate should be the loop's exit condition.
Definition at line 11112 of file ScalarEvolution.cpp.
References getLoopInvariantExitCondDuringFirstIterationsImpl(), LHS, RHS, and llvm::UMin.
Referenced by createReplacement().
std::optional< ScalarEvolution::LoopInvariantPredicate > ScalarEvolution::getLoopInvariantExitCondDuringFirstIterationsImpl | ( | ICmpInst::Predicate | Pred, |
const SCEV * | LHS, | ||
const SCEV * | RHS, | ||
const Loop * | L, | ||
const Instruction * | CtxI, | ||
const SCEV * | MaxIter | ||
) |
Definition at line 11132 of file ScalarEvolution.cpp.
References llvm::SCEVAddRecExpr::evaluateAtIteration(), llvm::SCEVAddRecExpr::getLoop(), getNegativeSCEV(), getOne(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::CmpInst::getSwappedPredicate(), llvm::SCEV::getType(), llvm::SCEVAddRecExpr::getType(), llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_ULE, isKnownPredicateAt(), isLoopBackedgeGuardedByCond(), isLoopInvariant(), llvm::ICmpInst::isRelational(), llvm::CmpInst::isSigned(), llvm::Last, LHS, RHS, and std::swap().
Referenced by getLoopInvariantExitCondDuringFirstIterations().
std::optional< ScalarEvolution::LoopInvariantPredicate > ScalarEvolution::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 LoopInvariantPredicate with LHS and RHS being invariants, available at L's entry.
Otherwise, return std::nullopt.
Definition at line 11026 of file ScalarEvolution.cpp.
References assert(), llvm::CmpInst::getFlippedSignednessPredicate(), llvm::CmpInst::getInversePredicate(), llvm::SCEVAddRecExpr::getLoop(), getMonotonicPredicateType(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::CmpInst::getSwappedPredicate(), llvm::SCEVNAryExpr::hasNoSignedWrap(), llvm::SCEVNAryExpr::hasNoUnsignedWrap(), llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::SCEVAddRecExpr::isAffine(), isKnownNonNegative(), isKnownPositive(), isKnownPredicateAt(), isLoopBackedgeGuardedByCond(), isLoopInvariant(), LHS, MonotonicallyIncreasing, P, RHS, and std::swap().
The SCEVPtrToIntSinkingRewriter takes a scalar evolution expression, which computes a pointer-typed value, and rewrites the whole expression tree so that all the computations are done on integers, and the only pointer-typed operands in the expression are SCEVUnknown.
Definition at line 1061 of file ScalarEvolution.cpp.
References assert(), llvm::sampleprof::Base, llvm::Depth, getAddExpr(), getCouldNotCompute(), getDataLayout(), getEffectiveSCEVType(), llvm::DataLayout::getIntPtrType(), getLosslessPtrToIntExpr(), getMulExpr(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEV::getType(), llvm::SCEVUnknown::getType(), getTypeSizeInBits(), getZero(), llvm::Type::isIntegerTy(), llvm::Type::isPointerTy(), llvm::SCEVNAryExpr::operands(), Operands, registerUser(), rewrite(), Rewriter, and llvm::scPtrToInt.
Referenced by getLosslessPtrToIntExpr(), and getPtrToIntExpr().
const SCEV * ScalarEvolution::getMinMaxExpr | ( | SCEVTypes | Kind, |
SmallVectorImpl< const SCEV * > & | Operands | ||
) |
Definition at line 3837 of file ScalarEvolution.cpp.
References llvm::BumpPtrAllocatorImpl< AllocatorT, SlabSize, SizeThreshold, GrowthDelay >::Allocate(), llvm::append_range(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::SmallVectorImpl< T >::erase(), llvm::ConstantInt::get(), getConstant(), getContext(), getEffectiveSCEVType(), getMinMaxExpr(), getType(), GroupByComplexity(), llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_ULE, Idx, LHS, llvm_unreachable, llvm::SCEVNAryExpr::operands(), registerUser(), RHS, llvm::scSMaxExpr, llvm::scSMinExpr, llvm::scUMaxExpr, llvm::scUMinExpr, llvm::SmallVectorBase< Size_T >::size(), llvm::APIntOps::smax(), llvm::APIntOps::smin(), llvm::APIntOps::umax(), and llvm::APIntOps::umin().
Referenced by getMinMaxExpr(), getNotSCEV(), getSequentialMinMaxExpr(), getSMaxExpr(), getSMinExpr(), getUMaxExpr(), and getUMinExpr().
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
It is, at the same time, the minimum number of times S is divisible by 2. For example, given {4,+,8} it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S.
Definition at line 6377 of file ScalarEvolution.cpp.
Referenced by extractConstantWithoutWrapping(), getSmallConstantTripMultiple(), getTruncateExpr(), and SolveLinEquationWithOverflow().
Return a SCEV for the constant -1 of a specific type.
Definition at line 659 of file ScalarEvolution.h.
References getConstant().
Referenced by createReplacement(), getNegativeSCEV(), and getNotSCEV().
const SCEV * ScalarEvolution::getMinusSCEV | ( | const SCEV * | LHS, |
const SCEV * | RHS, | ||
SCEV::NoWrapFlags | Flags = SCEV::FlagAnyWrap , |
||
unsigned | Depth = 0 |
||
) |
Return LHS-RHS.
Minus is represented in SCEV as A+B*-1.
If the LHS and RHS are pointers which don't share a common base (according to getPointerBase()), this returns a SCEVCouldNotCompute. To compute the difference between two unrelated pointers, you can explicitly convert the arguments using getPtrToIntExpr(), for pointer types that support it.
Definition at line 4642 of file ScalarEvolution.cpp.
References llvm::Depth, llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, getAddExpr(), getCouldNotCompute(), getNegativeSCEV(), getPointerBase(), getSignedRangeMin(), llvm::Value::getType(), getZero(), hasFlags(), isKnownNonNegative(), llvm::APInt::isMinSignedValue(), llvm::Type::isPointerTy(), LHS, removePointerBase(), and RHS.
Referenced by llvm::SCEVAAResult::alias(), llvm::InterleavedAccessInfo::analyzeInterleaving(), applyLoopGuards(), BinomialCoefficient(), canBeCheaplyTransformed(), createNodeForSelectViaUMinSeq(), createReplacement(), findForkedSCEVs(), getMinFromExprs(), getNewAlignment(), getNotSCEV(), llvm::getPointersDiff(), getStartForNegStride(), getUDivCeilSCEV(), getURemExpr(), llvm::IndexedReference::hasSpacialReuse(), isSafeDecreasingBound(), isSafeDependenceDistance(), isSafeIncreasingBound(), verify(), llvm::SCEVDivision::visitMulExpr(), and willNotOverflow().
std::optional< ScalarEvolution::MonotonicPredicateType > ScalarEvolution::getMonotonicPredicateType | ( | const SCEVAddRecExpr * | LHS, |
ICmpInst::Predicate | Pred | ||
) |
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing, returns Some(MonotonicallyIncreasing) and Some(MonotonicallyDecreasing) respectively.
If we could not prove either of these facts, returns std::nullopt.
Definition at line 10962 of file ScalarEvolution.cpp.
References assert(), llvm::CmpInst::getSwappedPredicate(), and LHS.
Referenced by countToEliminateCompares(), getLoopInvariantPredicate(), and isSafeToTruncateWideIVType().
|
inline |
Definition at line 595 of file ScalarEvolution.h.
References llvm::Depth, getMulExpr(), LHS, and RHS.
|
inline |
Definition at line 601 of file ScalarEvolution.h.
References llvm::Depth, and getMulExpr().
const SCEV * ScalarEvolution::getMulExpr | ( | SmallVectorImpl< const SCEV * > & | Ops, |
SCEV::NoWrapFlags | Flags = SCEV::FlagAnyWrap , |
||
unsigned | Depth = 0 |
||
) |
Get a canonical multiply expression, or something simpler if possible.
Definition at line 3132 of file ScalarEvolution.cpp.
References llvm::Add, llvm::append_range(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), Choose(), containsConstantInAddMulChain(), llvm::Depth, llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorImpl< T >::erase(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, getAddExpr(), getAddRecExpr(), getConstant(), llvm::SCEVAddRecExpr::getLoop(), getMulExpr(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), llvm::SCEVAddRecExpr::getType(), getType(), getTypeSizeInBits(), getZero(), GroupByComplexity(), hasHugeExpression(), Idx, isAvailableAtLoopEntry(), llvm::Type::isPointerTy(), LHS, maskFlags(), MaxAddRecSize, MaxArithDepth, llvm::Mul, MulOpsInlineThreshold, llvm::SCEV::operands(), Operands, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorImpl< T >::reserve(), RHS, llvm::scAddRecExpr, llvm::scMulExpr, llvm::SmallVectorBase< Size_T >::size(), StrengthenNoWrapFlags(), and umul_ov().
Referenced by applyLoopGuards(), BinomialCoefficient(), canFoldTermCondOfLoop(), CollectAddOperandsWithScales(), CollectSubexprs(), llvm::IndexedReference::computeRefCost(), DoInitialMatch(), llvm::SCEVAddRecExpr::evaluateAtIteration(), FactorOutConstant(), findArrayDimensionsRec(), findForkedSCEVs(), getAddExpr(), getExactSDiv(), getGEPExpr(), getLosslessPtrToIntExpr(), getMulExpr(), getNegativeSCEV(), getNumBytes(), getSignExtendExprImpl(), getStartForNegStride(), getTruncateExpr(), getUDivExactExpr(), getUDivExpr(), getURemExpr(), getZeroExtendExprImpl(), isSafeDependenceDistance(), removeConstantFactors(), SolveLinEquationWithOverflow(), llvm::SCEVRewriteVisitor< SC >::visitMulExpr(), llvm::SCEVDivision::visitMulExpr(), and willNotOverflow().
const SCEV * ScalarEvolution::getNegativeSCEV | ( | const SCEV * | V, |
SCEV::NoWrapFlags | Flags = SCEV::FlagAnyWrap |
||
) |
Return the SCEV object corresponding to -V.
Return a SCEV corresponding to -V = -1*V.
Definition at line 4556 of file ScalarEvolution.cpp.
References getConstant(), getEffectiveSCEVType(), getMinusOne(), getMulExpr(), llvm::ConstantExpr::getNeg(), and llvm::SCEV::getType().
Referenced by detectShiftUntilZeroIdiom(), llvm::SCEVExpander::generateOverflowCheck(), getAbsExpr(), getLoopInvariantExitCondDuringFirstIterationsImpl(), getMinusSCEV(), getTripCount(), isOneDimensionalArray(), isSafeDependenceDistance(), and llvm::FullDependence::normalize().
Return a SCEV corresponding to a conversion of the input value to the specified type.
If the type must be extended, it is extended with unspecified bits. The conversion must not be narrowing.
Definition at line 4741 of file ScalarEvolution.cpp.
References assert(), getAnyExtendExpr(), llvm::SCEV::getType(), getTypeSizeInBits(), and llvm::Type::isIntOrPtrTy().
Referenced by llvm::IndexedReference::computeRefCost().
Return a SCEV corresponding to a conversion of the input value to the specified type.
If the type must be extended, it is sign extended. The conversion must not be narrowing.
Definition at line 4729 of file ScalarEvolution.cpp.
References assert(), getSignExtendExpr(), llvm::SCEV::getType(), getTypeSizeInBits(), and llvm::Type::isIntOrPtrTy().
Referenced by getNewAlignment(), isSafeDependenceDistance(), and NoopOrExtend().
Return a SCEV corresponding to a conversion of the input value to the specified type.
If the type must be extended, it is zero extended. The conversion must not be narrowing.
Definition at line 4717 of file ScalarEvolution.cpp.
References assert(), llvm::SCEV::getType(), getTypeSizeInBits(), getZeroExtendExpr(), and llvm::Type::isIntOrPtrTy().
Referenced by llvm::createTripCountSCEV(), getTripCountFromExitCount(), getUMaxFromMismatchedTypes(), getUMinFromMismatchedTypes(), NoopOrExtend(), and optimizeLoopExitWithUnknownExitCount().
Return the SCEV object corresponding to ~V.
Return a SCEV corresponding to ~V = -1-V.
Definition at line 4583 of file ScalarEvolution.cpp.
References assert(), getConstant(), getEffectiveSCEVType(), getMinMaxExpr(), getMinusOne(), getMinusSCEV(), llvm::ConstantExpr::getNot(), llvm::SCEV::getType(), llvm::Type::isPointerTy(), MatchNotExpr(), llvm::SCEVMinMaxExpr::negate(), llvm::SCEV::operands(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().
Referenced by createNodeForSelectViaUMinSeq().
const SCEV * ScalarEvolution::getOffsetOfExpr | ( | Type * | IntTy, |
StructType * | STy, | ||
unsigned | FieldNo | ||
) |
Return an expression for offsetof on the given field with type IntTy.
Definition at line 4380 of file ScalarEvolution.cpp.
References getConstant(), and getDataLayout().
Referenced by getGEPExpr().
Return a SCEV for the constant 1 of a specific type.
Definition at line 656 of file ScalarEvolution.h.
References getConstant().
Referenced by applyLoopGuards(), llvm::calculateUpperBound(), canFoldTermCondOfLoop(), llvm::LoopVectorizationCostModel::computeMaxVF(), createReplacement(), llvm::createTripCountSCEV(), genLoopLimit(), getAddExpr(), getConstantMaxTripCountFromArray(), getLoopInvariantExitCondDuringFirstIterationsImpl(), getTripCount(), getTripCountFromExitCount(), getUDivCeilSCEV(), llvm::ARMTTIImpl::isHardwareLoopProfitable(), isLoopBackedgeGuardedByCond(), isSafeDecreasingBound(), isSafeIncreasingBound(), and llvm::replaceSymbolicStrideSCEV().
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a single pointer operand.
This returns a SCEVUnknown pointer for well-formed pointer-type expressions, but corner cases do exist.
Definition at line 4810 of file ScalarEvolution.cpp.
References llvm::Add, assert(), llvm::SCEV::getType(), and llvm::Type::isPointerTy().
Referenced by llvm::DependenceInfo::depends(), getConstantMaxTripCountFromArray(), getMinusSCEV(), and llvm::tryDelinearizeFixedSizeImpl().
const SCEV * ScalarEvolution::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 required to be true in order for the answer to be correct.
Predicates can be checked with run-time checks and can be used to perform loop versioning.
Definition at line 8326 of file ScalarEvolution.cpp.
Referenced by llvm::SCEVExpander::generateOverflowCheck(), llvm::PredicatedScalarEvolution::getBackedgeTakenCount(), and PrintLoopInfo().
Definition at line 1185 of file ScalarEvolution.cpp.
References assert(), getLosslessPtrToIntExpr(), getTruncateOrZeroExtend(), and llvm::Type::isIntegerTy().
Referenced by getCastExpr(), and llvm::SCEVRewriteVisitor< SC >::visitPtrToIntExpr().
Return a SCEV expression for the full generality of the specified expression.
Return an existing SCEV if it exists, otherwise analyze the expression and create a new one.
Definition at line 4534 of file ScalarEvolution.cpp.
References assert(), llvm::Value::getType(), and isSCEVable().
Referenced by llvm::RecurrenceDescriptor::AddReductionVar(), llvm::IVUsers::AddUsersIfInteresting(), llvm::SCEVAAResult::alias(), llvm::analyzeICmp(), applyLoopGuards(), canFoldTermCondOfLoop(), canOverlap(), canTailPredicateLoop(), countToEliminateCompares(), createNodeForSelectViaUMinSeq(), DbgGatherSalvagableDVI(), DbgRewriteSalvageableDVIs(), llvm::DependenceInfo::depends(), detectShiftUntilZeroIdiom(), DoInitialMatch(), llvm::AlignmentFromAssumptionsPass::extractAlignmentInfo(), findForkedSCEVs(), findIVOperand(), FindLoopCounter(), genLoopLimit(), getAddressAccessSCEV(), llvm::PredicatedScalarEvolution::getAsAddRec(), llvm::Loop::LoopBounds::getBounds(), getBoundsCheckCond(), getConstantMaxTripCountFromArray(), getFalkorUnrollingPreferences(), getGEPExpr(), llvm::getIndexExpressionsFromGEP(), GetInductionVariable(), getNewAlignment(), llvm::getPointersDiff(), llvm::SCEVExpander::getRelatedExistingExpansion(), llvm::IVUsers::getReplacementExpr(), llvm::PredicatedScalarEvolution::getSCEV(), getSCEVAtScope(), llvm::DependenceInfo::getSplitIteration(), getStrengthenedNoWrapFlagsFromBinOp(), llvm::getStrideFromPointer(), llvm::isDereferenceableAndAlignedInLoop(), isExistingPhi(), isHighCostExpansion(), llvm::InductionDescriptor::isInductionPHI(), llvm::LoopVectorizationLegality::isInvariantAddressOfReduction(), isLoopCounter(), isProfitableChain(), isSimpleIVUser(), llvm::LoopAccessInfo::isUniform(), print(), llvm::PredicatedScalarEvolution::print(), llvm::AlignmentFromAssumptionsPass::processAssumption(), llvm::SCEVExpander::replaceCongruentIVs(), llvm::replaceSymbolicStrideSCEV(), llvm::rewriteLoopExitValues(), llvm::splitLoopBound(), llvm::storeToSameAddress(), llvm::stripGetElementPtr(), verify(), verifyTripCount(), and llvm::VPlanTransforms::VPInstructionsToVPRecipes().
Return a SCEV expression for the specified value at the specified scope in the program.
The L value specifies a loop nest to evaluate the expression at, where null is the top-level or a specified loop is immediately inside of the loop.
This method can be used to compute the exit value for a variable defined in a loop by querying what the value will hold in the parent loop.
In the case that a relevant loop exit value cannot be computed, the original value V is returned.
Definition at line 9735 of file ScalarEvolution.cpp.
References llvm::CallingConv::C, llvm::SmallVectorImpl< T >::emplace_back(), and llvm::reverse().
Referenced by computeUnrollAndJamCount(), createReplacement(), getSCEVAtScope(), isInteresting(), print(), and llvm::rewriteLoopExitValues().
This is a convenience function which does getSCEVAtScope(getSCEV(V), L).
Definition at line 10081 of file ScalarEvolution.cpp.
References getSCEV(), and getSCEVAtScope().
const SCEV * ScalarEvolution::getSequentialMinMaxExpr | ( | SCEVTypes | Kind, |
SmallVectorImpl< const SCEV * > & | Operands | ||
) |
Definition at line 4200 of file ScalarEvolution.cpp.
References llvm::BumpPtrAllocatorImpl< AllocatorT, SlabSize, SizeThreshold, GrowthDelay >::Allocate(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::SmallVectorImpl< T >::erase(), getEffectiveSCEVType(), llvm::SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(), getMinMaxExpr(), getSequentialMinMaxExpr(), getType(), getZero(), llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_ULE, Idx, llvm::impliesPoison(), llvm::SmallVectorImpl< T >::insert(), llvm_unreachable, registerUser(), llvm::scSequentialUMinExpr, and llvm::SmallVectorBase< Size_T >::size().
Referenced by getSequentialMinMaxExpr(), and getUMinExpr().
|
inline |
Determine the signed range for a particular SCEV.
NOTE: This returns a copy of the reference returned by getRangeRef.
Definition at line 980 of file ScalarEvolution.h.
Referenced by getSignExtendExprImpl(), print(), and StrengthenNoWrapFlags().
Determine the max of the signed range for a particular SCEV.
Definition at line 990 of file ScalarEvolution.h.
References llvm::ConstantRange::getSignedMax().
Referenced by getSignedOverflowLimitForStep(), isKnownNegative(), isKnownNonPositive(), and SimplifyICmpOperands().
Determine the min of the signed range for a particular SCEV.
Definition at line 985 of file ScalarEvolution.h.
References llvm::ConstantRange::getSignedMin().
Referenced by getMinusSCEV(), getSignedOverflowLimitForStep(), getZeroExtendExprImpl(), isKnownNonNegative(), isKnownPositive(), and SimplifyICmpOperands().
Definition at line 1931 of file ScalarEvolution.cpp.
References assert(), llvm::Depth, getEffectiveSCEVType(), getSignExtendExprImpl(), getTypeSizeInBits(), insertFoldCacheEntry(), isSCEVable(), and llvm::scSignExtend.
Referenced by getAnyExtendExpr(), getCastExpr(), getNoopOrSignExtend(), getSignExtendExprImpl(), getTruncateOrSignExtend(), getZeroExtendExprImpl(), isAddRecSExtable(), isAddSExtable(), IsIncrementNSW(), isMulSExtable(), llvm::SCEVRewriteVisitor< SC >::visitSignExtendExpr(), and willNotOverflow().
const SCEV * ScalarEvolution::getSignExtendExprImpl | ( | const SCEV * | Op, |
Type * | Ty, | ||
unsigned | Depth = 0 |
||
) |
Definition at line 1953 of file ScalarEvolution.cpp.
References assert(), llvm::BitWidth, llvm::CallingConv::C, llvm::ConstantRange::contains(), D, llvm::Depth, extractConstantWithoutWrapping(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, llvm::IntegerType::get(), getAddExpr(), getAddRecExpr(), getConstant(), getConstantMaxBackedgeTakenCount(), getContext(), getEffectiveSCEVType(), getMulExpr(), llvm::ConstantExpr::getSExt(), getSignedRange(), getSignExtendExpr(), getTruncateOrSignExtend(), getTruncateOrZeroExtend(), llvm::SCEV::getType(), getTypeSizeInBits(), getZeroExtendExpr(), isKnownNonNegative(), isSCEVable(), MaxCastDepth, llvm::SmallVectorTemplateBase< T, bool >::push_back(), registerUser(), llvm::scSignExtend, setNoWrapFlags(), llvm::ConstantRange::sextOrTrunc(), llvm::ConstantRange::signExtend(), llvm::ConstantRange::truncate(), and X.
Referenced by getSignExtendExpr().
Return an expression for the alloc size of AllocTy that is type IntTy.
Definition at line 4362 of file ScalarEvolution.cpp.
References getConstant(), getDataLayout(), and getSizeOfScalableVectorExpr().
Referenced by findForkedSCEVs(), getElementSize(), and getGEPExpr().
const SCEV * ScalarEvolution::getSizeOfScalableVectorExpr | ( | Type * | IntTy, |
ScalableVectorType * | ScalableTy | ||
) |
Return an expression for sizeof ScalableTy that is type IntTy, where ScalableTy is a scalable vector type.
Definition at line 4351 of file ScalarEvolution.cpp.
References GEP, llvm::ConstantInt::get(), llvm::ConstantExpr::getGetElementPtr(), llvm::Constant::getNullValue(), llvm::Type::getPointerTo(), llvm::ConstantExpr::getPtrToInt(), and getUnknown().
Referenced by getSizeOfExpr(), and getStoreSizeOfExpr().
Returns the upper bound of the loop trip count as a normal unsigned value.
Returns 0 if the trip count is unknown or not constant.
Definition at line 8121 of file ScalarEvolution.cpp.
References getConstantMaxBackedgeTakenCount(), and getConstantTripCount().
Referenced by llvm::HexagonTTIImpl::getPeelingPreferences(), getSmallBestKnownTC(), llvm::isDereferenceableAndAlignedInLoop(), llvm::LoopVectorizationCostModel::isMoreProfitable(), tryToUnrollLoop(), and llvm::UnrollLoop().
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
'0' is used to represent an unknown or non-constant trip count. Note that a trip count is simply one more than the backedge taken count for the loop.
Definition at line 8105 of file ScalarEvolution.cpp.
References Exact, getBackedgeTakenCount(), and getConstantTripCount().
Referenced by llvm::CacheCost::CacheCost(), llvm::LoopVectorizationCostModel::computeMaxVF(), llvm::HexagonTTIImpl::getPeelingPreferences(), getSmallBestKnownTC(), llvm::PPCTTIImpl::isHardwareLoopProfitable(), tryToUnrollAndJamLoop(), tryToUnrollLoop(), and llvm::UnrollLoop().
unsigned ScalarEvolution::getSmallConstantTripCount | ( | const Loop * | L, |
const BasicBlock * | ExitingBlock | ||
) |
Return the exact trip count for this loop if we exit through ExitingBlock.
'0' is used to represent an unknown or non-constant trip count. Note that a trip count is simply one more than the backedge taken count for the same exit. This "trip count" assumes that control exits via ExitingBlock. More precisely, it is the number of times that control will reach ExitingBlock before taking the branch. For loops with multiple exits, it may not be the number times that the loop header executes if the loop exits prematurely via another branch.
Definition at line 8111 of file ScalarEvolution.cpp.
References assert(), getConstantTripCount(), getExitCount(), and llvm::LoopBase< BlockT, LoopT >::isLoopExiting().
Returns the largest constant divisor of the trip count of the loop.
Will return 1 if no trip count could be computed, or if a divisor could not be found.
Definition at line 8247 of file ScalarEvolution.cpp.
References llvm::LoopBase< BlockT, LoopT >::getExitingBlocks(), and getSmallConstantTripMultiple().
unsigned ScalarEvolution::getSmallConstantTripMultiple | ( | const Loop * | L, |
const BasicBlock * | ExitingBlock | ||
) |
Returns the largest constant divisor of the trip count of this loop as a normal unsigned value, if possible.
This means that the actual trip count is always a multiple of the returned value (don't forget the trip count could very well be zero as well!). As explained in the comments for getSmallConstantTripCount, this assumes that control exits the loop via ExitingBlock.
This means that the actual trip count is always a multiple of the returned value (don't forget the trip count could very well be zero as well!).
Returns 1 if the trip count is unknown or not guaranteed to be the multiple of a constant (which is also the case if the trip count is simply constant, use getSmallConstantTripCount for that case), Will also return 1 if the trip count is very large (>= 2^32).
As explained in the comments for getSmallConstantTripCount, this assumes that control exits the loop via ExitingBlock.
Definition at line 8302 of file ScalarEvolution.cpp.
References assert(), getExitCount(), getSmallConstantTripMultiple(), and llvm::LoopBase< BlockT, LoopT >::isLoopExiting().
Returns the largest constant divisor of the trip count as a normal unsigned value, if possible.
This means that the actual trip count is always a multiple of the returned value. Returns 1 if the trip count is unknown or not guaranteed to be the multiple of a constant., Will also return 1 if the trip count is very large (>= 2^32). Note that the argument is an exit count for loop L, NOT a trip count.
Definition at line 8261 of file ScalarEvolution.cpp.
References applyLoopGuards(), getCouldNotCompute(), GetMinTrailingZeros(), getTripCountFromExitCount(), and llvm::SCEVConstant::getValue().
Referenced by getSmallConstantTripMultiple(), PrintLoopInfo(), tryToUnrollAndJamLoop(), tryToUnrollLoop(), and llvm::UnrollLoop().
Definition at line 4310 of file ScalarEvolution.cpp.
References getSMaxExpr(), LHS, and RHS.
Referenced by applyLoopGuards(), getAbsExpr(), getSMaxExpr(), IntersectSignedRange(), and llvm::SCEVRewriteVisitor< SC >::visitSMaxExpr().
const SCEV * ScalarEvolution::getSMaxExpr | ( | SmallVectorImpl< const SCEV * > & | Operands | ) |
Definition at line 4315 of file ScalarEvolution.cpp.
References getMinMaxExpr(), and llvm::scSMaxExpr.
Definition at line 4328 of file ScalarEvolution.cpp.
References getSMinExpr(), LHS, and RHS.
Referenced by applyLoopGuards(), getSMinExpr(), IntersectSignedRange(), llvm::splitLoopBound(), and llvm::SCEVRewriteVisitor< SC >::visitSMinExpr().
const SCEV * ScalarEvolution::getSMinExpr | ( | SmallVectorImpl< const SCEV * > & | Operands | ) |
Definition at line 4334 of file ScalarEvolution.cpp.
References getMinMaxExpr(), and llvm::scSMinExpr.
Return an expression for the store size of StoreTy that is type IntTy.
Definition at line 4371 of file ScalarEvolution.cpp.
References getConstant(), getDataLayout(), and getSizeOfScalableVectorExpr().
Referenced by llvm::RuntimePointerChecking::insert().
std::optional< SCEV::NoWrapFlags > ScalarEvolution::getStrengthenedNoWrapFlagsFromBinOp | ( | const OverflowingBinaryOperator * | OBO | ) |
Parse NSW/NUW flags from add/sub/mul IR binary operation Op
into SCEV no-wrap flags, and deduce flag[s] that aren't known yet.
Does not mutate the original instruction. Returns std::nullopt if it could not deduce more precise flags than the instruction already has, otherwise returns proven flags.
Definition at line 2402 of file ScalarEvolution.cpp.
References llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::Operator::getOpcode(), llvm::User::getOperand(), getSCEV(), llvm::OverflowingBinaryOperator::hasNoSignedWrap(), llvm::OverflowingBinaryOperator::hasNoUnsignedWrap(), LHS, RHS, setFlags(), UseContextForNoWrapFlagInference, and willNotOverflow().
Referenced by llvm::SCEVExpander::hoistIVInc().
When successful, this returns a SCEV that is greater than or equal to (i.e.
a "conservative over-approximation") of the value returend by getBackedgeTakenCount. If such a value cannot be computed, it returns the SCEVCouldNotCompute object.
Definition at line 906 of file ScalarEvolution.h.
References getBackedgeTakenCount(), and SymbolicMaximum.
Referenced by PrintLoopInfo().
const SCEV * ScalarEvolution::getTripCountFromExitCount | ( | const SCEV * | ExitCount, |
bool | Extend = true |
||
) |
Convert from an "exit count" (i.e.
"backedge taken count") to a "trip
count". A "trip count" is the number of times the header of the loop will execute if an exit is taken after the specified number of backedges have been taken. (e.g. TripCount = ExitCount + 1). Note that the expression can overflow if ExitCount = UINT_MAX. Extend
controls how potential overflow is handled. If true, a wider result type is returned. ex: EC = 255 (i8), TC = 256 (i9). If false, result unsigned wraps with 2s-complement semantics. ex: EC = 255 (i8), TC = 0 (i8)
Definition at line 8074 of file ScalarEvolution.cpp.
References assert(), getAddExpr(), getCouldNotCompute(), llvm::Type::getIntNTy(), getNoopOrZeroExtend(), getOne(), and llvm::SCEV::getType().
Referenced by computeTripCount(), getSmallConstantTripMultiple(), and verifyTripCount().
Definition at line 1195 of file ScalarEvolution.cpp.
References assert(), llvm::Depth, llvm::SCEV::FlagAnyWrap, getAddExpr(), getAddRecExpr(), getConstant(), getEffectiveSCEVType(), GetMinTrailingZeros(), getMulExpr(), llvm::ConstantExpr::getTrunc(), getTruncateExpr(), getTruncateOrSignExtend(), getTruncateOrZeroExtend(), getTypeSizeInBits(), getZero(), isSCEVable(), llvm_unreachable, MaxCastDepth, Operands, registerUser(), and llvm::scTruncate.
Referenced by createReplacement(), generateLoopLatchCheck(), genLoopLimit(), getAddExpr(), getCastExpr(), getTruncateExpr(), getTruncateOrNoop(), getTruncateOrSignExtend(), getTruncateOrZeroExtend(), getURemExpr(), getZeroExtendExprImpl(), llvm::SCEVExpander::replaceCongruentIVs(), and llvm::SCEVRewriteVisitor< SC >::visitTruncateExpr().
Return a SCEV corresponding to a conversion of the input value to the specified type.
The conversion must not be widening.
Definition at line 4753 of file ScalarEvolution.cpp.
References assert(), getTruncateExpr(), llvm::SCEV::getType(), getTypeSizeInBits(), and llvm::Type::isIntOrPtrTy().
Referenced by canBeCheaplyTransformed(), llvm::createTripCountSCEV(), getAnyExtendExpr(), and llvm::SCEVExpander::replaceCongruentIVs().
const SCEV * ScalarEvolution::getTruncateOrSignExtend | ( | const SCEV * | V, |
Type * | Ty, | ||
unsigned | Depth = 0 |
||
) |
Return a SCEV corresponding to a conversion of the input value to the specified type.
If the type must be extended, it is sign extended.
Definition at line 4704 of file ScalarEvolution.cpp.
References assert(), llvm::Depth, getSignExtendExpr(), getTruncateExpr(), llvm::SCEV::getType(), getTypeSizeInBits(), and llvm::Type::isIntOrPtrTy().
Referenced by findForkedSCEVs(), getGEPExpr(), getSignExtendExprImpl(), and getTruncateExpr().
const SCEV * ScalarEvolution::getTruncateOrZeroExtend | ( | const SCEV * | V, |
Type * | Ty, | ||
unsigned | Depth = 0 |
||
) |
Return a SCEV corresponding to a conversion of the input value to the specified type.
If the type must be extended, it is zero extended.
Definition at line 4692 of file ScalarEvolution.cpp.
References assert(), llvm::Depth, getTruncateExpr(), llvm::SCEV::getType(), getTypeSizeInBits(), getZeroExtendExpr(), and llvm::Type::isIntOrPtrTy().
Referenced by BinomialCoefficient(), canFoldTermCondOfLoop(), llvm::AlignmentFromAssumptionsPass::extractAlignmentInfo(), genLoopLimit(), getNewAlignment(), getNumBytes(), getPtrToIntExpr(), getSignExtendExprImpl(), getStartForNegStride(), getTripCount(), getTruncateExpr(), and getZeroExtendExprImpl().
Return the size in bits of the specified type, for which isSCEVable must return true.
Definition at line 4427 of file ScalarEvolution.cpp.
References assert(), getDataLayout(), llvm::DataLayout::getIndexTypeSizeInBits(), llvm::DataLayout::getTypeSizeInBits(), llvm::Type::isPointerTy(), and isSCEVable().
Referenced by llvm::IVUsers::AddUsersIfInteresting(), llvm::SCEVAAResult::alias(), BinomialCoefficient(), computeConstantDifference(), createReplacement(), llvm::createTripCountSCEV(), FindLoopCounter(), llvm::SCEVExpander::generateOverflowCheck(), genLoopLimit(), getAddExpr(), getAnyExtendExpr(), getLosslessPtrToIntExpr(), getMulExpr(), getNoopOrAnyExtend(), getNoopOrSignExtend(), getNoopOrZeroExtend(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), getPreStartForExtend(), getSignedOverflowLimitForStep(), getSignExtendExpr(), getSignExtendExprImpl(), getTruncateExpr(), getTruncateOrNoop(), getTruncateOrSignExtend(), getTruncateOrZeroExtend(), getUDivExpr(), getUMaxFromMismatchedTypes(), getUnsignedOverflowLimitForStep(), getWiderType(), getZeroExtendExpr(), getZeroExtendExprImpl(), isAddRecSExtable(), isAddSExtable(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), isMulSExtable(), isSimpleCastedPHI(), SolveLinEquationWithOverflow(), SolveQuadraticAddRecRange(), verify(), and visitIVCast().
Compute ceil(N / D).
N and D are treated as unsigned values.
Since SCEV doesn't have native ceiling division, this generates a SCEV expression of the following form:
umin(N, 1) + floor((N - umin(N, 1)) / D)
A denominator of zero or poison is handled the same way as getUDivExpr().
Definition at line 12673 of file ScalarEvolution.cpp.
References D, getAddExpr(), getMinusSCEV(), getOne(), getUDivExpr(), getUMinExpr(), and N.
Referenced by getConstantMaxTripCountFromArray().
Get a canonical unsigned division expression, or something simpler if possible.
There is no representation for an exact udiv in SCEV IR, but we can attempt to remove factors from the LHS and RHS. We can't do this when it's not exact because the udiv may be clearing bits.
Definition at line 3599 of file ScalarEvolution.cpp.
References llvm::append_range(), llvm::drop_begin(), gcd(), getConstant(), getMulExpr(), getUDivExactExpr(), getUDivExpr(), llvm::APInt::isIntN(), LHS, llvm::Mul, Operands, and RHS.
Referenced by getUDivExactExpr(), and SolveLinEquationWithOverflow().
Get a canonical unsigned division expression, or something simpler if possible.
Get a canonical UDivExpr for a recurrence. {X,+,N}/C => {Y,+,N}/C where Y=X-(XN). Safe when CN=0.
Definition at line 3427 of file ScalarEvolution.cpp.
References A, assert(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNW, llvm::IntegerType::get(), getAddExpr(), getAddRecExpr(), llvm::SCEVConstant::getAPInt(), getConstant(), getContext(), getMulExpr(), llvm::Value::getType(), getTypeSizeInBits(), getUDivExpr(), getZeroExtendExpr(), llvm::Type::isPointerTy(), LHS, Operands, registerUser(), RHS, llvm::scUDivExpr, llvm::APInt::umul_ov(), and llvm::APInt::urem().
Referenced by applyLoopGuards(), BinomialCoefficient(), llvm::IndexedReference::computeRefCost(), getAddExpr(), getUDivCeilSCEV(), getUDivExactExpr(), getUDivExpr(), getURemExpr(), getZeroExtendExprImpl(), and llvm::SCEVRewriteVisitor< SC >::visitUDivExpr().
Definition at line 4319 of file ScalarEvolution.cpp.
References getUMaxExpr(), LHS, and RHS.
Referenced by applyLoopGuards(), getUMaxExpr(), getUMaxFromMismatchedTypes(), llvm::RuntimePointerChecking::insert(), IntersectUnsignedRange(), and llvm::SCEVRewriteVisitor< SC >::visitUMaxExpr().
const SCEV * ScalarEvolution::getUMaxExpr | ( | SmallVectorImpl< const SCEV * > & | Operands | ) |
Definition at line 4324 of file ScalarEvolution.cpp.
References getMinMaxExpr(), and llvm::scUMaxExpr.
Promote the operands to the wider of the types using zero-extension, and then perform a umax operation with them.
Definition at line 4764 of file ScalarEvolution.cpp.
References getNoopOrZeroExtend(), llvm::Value::getType(), getTypeSizeInBits(), getUMaxExpr(), getZeroExtendExpr(), LHS, and RHS.
const SCEV * ScalarEvolution::getUMinExpr | ( | const SCEV * | LHS, |
const SCEV * | RHS, | ||
bool | Sequential = false |
||
) |
Definition at line 4338 of file ScalarEvolution.cpp.
References getUMinExpr(), LHS, and RHS.
Referenced by applyLoopGuards(), createNodeForSelectViaUMinSeq(), getUDivCeilSCEV(), getUMinExpr(), getUMinFromMismatchedTypes(), llvm::RuntimePointerChecking::insert(), IntersectUnsignedRange(), llvm::splitLoopBound(), llvm::SCEVRewriteVisitor< SC >::visitSequentialUMinExpr(), and llvm::SCEVRewriteVisitor< SC >::visitUMinExpr().
const SCEV * ScalarEvolution::getUMinExpr | ( | SmallVectorImpl< const SCEV * > & | Operands, |
bool | Sequential = false |
||
) |
Definition at line 4344 of file ScalarEvolution.cpp.
References getMinMaxExpr(), getSequentialMinMaxExpr(), llvm::scSequentialUMinExpr, and llvm::scUMinExpr.
const SCEV * ScalarEvolution::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 operation with them.
Definition at line 4777 of file ScalarEvolution.cpp.
References getUMinFromMismatchedTypes(), LHS, and RHS.
Referenced by createReplacement(), getConstantMaxTripCountFromArray(), getMinAnalyzeableBackedgeTakenCount(), and getUMinFromMismatchedTypes().
const SCEV * ScalarEvolution::getUMinFromMismatchedTypes | ( | SmallVectorImpl< const SCEV * > & | Ops, |
bool | Sequential = false |
||
) |
Promote the operands to the wider of the types using zero-extension, and then perform a umin operation with them.
N-ary function.
Definition at line 4785 of file ScalarEvolution.cpp.
References assert(), llvm::SmallVectorBase< Size_T >::empty(), getNoopOrZeroExtend(), llvm::SCEV::getType(), getUMinExpr(), getWiderType(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallVectorBase< Size_T >::size().
Definition at line 4390 of file ScalarEvolution.cpp.
References assert(), SCEVUnknown, and llvm::scUnknown.
Referenced by getSizeOfScalableVectorExpr(), llvm::InductionDescriptor::isFPInductionPHI(), and verify().
|
inline |
Determine the unsigned range for a particular SCEV.
NOTE: This returns a copy of the reference returned by getRangeRef.
Definition at line 964 of file ScalarEvolution.h.
Referenced by llvm::SCEVAAResult::alias(), getBoundsCheckCond(), getZeroExtendExprImpl(), mustBeFiniteCountedLoop(), print(), and StrengthenNoWrapFlags().
Determine the max of the unsigned range for a particular SCEV.
Definition at line 974 of file ScalarEvolution.h.
References llvm::ConstantRange::getUnsignedMax().
Referenced by getUnsignedOverflowLimitForStep(), llvm::ARMTTIImpl::isHardwareLoopProfitable(), and SimplifyICmpOperands().
Determine the min of the unsigned range for a particular SCEV.
Definition at line 969 of file ScalarEvolution.h.
References llvm::ConstantRange::getUnsignedMin().
Referenced by isKnownNonZero(), and SimplifyICmpOperands().
Represents an unsigned remainder expression based on unsigned division.
Definition at line 3398 of file ScalarEvolution.cpp.
References assert(), llvm::SCEV::FlagNUW, llvm::IntegerType::get(), getContext(), getEffectiveSCEVType(), getMinusSCEV(), getMulExpr(), getTruncateExpr(), llvm::Value::getType(), getUDivExpr(), getZero(), getZeroExtendExpr(), LHS, and RHS.
Referenced by llvm::LoopVectorizationCostModel::computeMaxVF(), getNewAlignmentDiff(), and getZeroExtendExprImpl().
Definition at line 4448 of file ScalarEvolution.cpp.
References getTypeSizeInBits(), and T1.
Referenced by llvm::IndexedReference::computeRefCost(), getUMinFromMismatchedTypes(), and optimizeLoopExitWithUnknownExitCount().
const SCEVPredicate * ScalarEvolution::getWrapPredicate | ( | const SCEVAddRecExpr * | AR, |
SCEVWrapPredicate::IncrementWrapFlags | AddedFlags | ||
) |
Definition at line 14411 of file ScalarEvolution.cpp.
References llvm::SCEVPredicate::P_Wrap.
Referenced by llvm::PredicatedScalarEvolution::setNoOverflow().
Return a SCEV for the constant 0 of a specific type.
Definition at line 653 of file ScalarEvolution.h.
References getConstant().
Referenced by detectShiftUntilZeroIdiom(), llvm::AlignmentFromAssumptionsPass::extractAlignmentInfo(), getAddExpr(), getLosslessPtrToIntExpr(), getMinusSCEV(), getMulExpr(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), getSequentialMinMaxExpr(), getTruncateExpr(), getURemExpr(), llvm::isKnownNegativeInLoop(), llvm::isKnownNonNegativeInLoop(), isLoopBackedgeGuardedByCond(), and removePointerBase().
Definition at line 1609 of file ScalarEvolution.cpp.
References assert(), llvm::Depth, getEffectiveSCEVType(), getTypeSizeInBits(), getZeroExtendExprImpl(), insertFoldCacheEntry(), isSCEVable(), and llvm::scZeroExtend.
Referenced by createReplacement(), genLoopLimit(), getAnyExtendExpr(), getCastExpr(), getNoopOrZeroExtend(), getSignExtendExprImpl(), getTripCount(), getTruncateOrZeroExtend(), getUDivExpr(), getUMaxFromMismatchedTypes(), getURemExpr(), getZeroExtendExprImpl(), IsIncrementNUW(), isSafeDependenceDistance(), verify(), verifyTripCount(), llvm::SCEVRewriteVisitor< SC >::visitZeroExtendExpr(), and willNotOverflow().
const SCEV * ScalarEvolution::getZeroExtendExprImpl | ( | const SCEV * | Op, |
Type * | Ty, | ||
unsigned | Depth = 0 |
||
) |
Definition at line 1631 of file ScalarEvolution.cpp.
References assert(), llvm::AssumptionCache::assumptions(), llvm::BitWidth, llvm::CallingConv::C, llvm::ConstantRange::contains(), D, llvm::Depth, extractConstantWithoutWrapping(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, llvm::IntegerType::get(), getAddExpr(), getAddRecExpr(), getConstant(), getConstantMaxBackedgeTakenCount(), getContext(), llvm::APInt::getMaxValue(), getMulExpr(), getSignedRangeMin(), getSignExtendExpr(), getTruncateExpr(), getTruncateOrZeroExtend(), llvm::SCEV::getType(), getTypeSizeInBits(), getUDivExpr(), getUnsignedRange(), getURemExpr(), getZeroExtendExpr(), llvm::ConstantExpr::getZExt(), llvm::CmpInst::ICMP_UGT, isKnownNegative(), isKnownOnEveryIteration(), isLoopBackedgeGuardedByCond(), isSCEVable(), LHS, MaxCastDepth, N, llvm::SmallVectorTemplateBase< T, bool >::push_back(), registerUser(), RHS, llvm::scZeroExtend, setNoWrapFlags(), llvm::ConstantRange::truncate(), X, llvm::ConstantRange::zeroExtend(), and llvm::ConstantRange::zextOrTrunc().
Referenced by getZeroExtendExpr().
Return true if the given SCEV changes value in a known way in the specified loop.
This property being true implies that the value is variant in the loop AND that we can emit an expression to compute the value of the expression at any particular loop iteration.
Definition at line 13779 of file ScalarEvolution.cpp.
References getLoopDisposition(), and LoopComputable.
|
inlinestatic |
Definition at line 484 of file ScalarEvolution.h.
References maskFlags().
Referenced by getAddExpr(), getMinusSCEV(), and StrengthenNoWrapFlags().
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
Definition at line 13494 of file ScalarEvolution.cpp.
References getBackedgeTakenCount().
Referenced by canFoldTermCondOfLoop(), llvm::ARMTTIImpl::isHardwareLoopProfitable(), llvm::IVUsers::print(), and PrintLoopInfo().
Test whether the given SCEV has Op as a direct or indirect operand.
Definition at line 13865 of file ScalarEvolution.cpp.
References llvm::SCEVExprContains().
Return true if there exists a point in the program at which both A and B could be operands to the same instruction.
SCEV expressions are generally assumed to correspond to instructions which could exists in IR. In general, this requires that there exists a use point in the program where all operands dominate the use.
Example: loop { if loop { v1 = load @global1; } else loop { v2 = load @global2; } } No SCEV with operand V1, and v2 can exist in this program.
For a valid use point to exist, the defining scope of one operand must dominate the other.
Definition at line 4452 of file ScalarEvolution.cpp.
References A, B, and llvm::DominatorTree::dominates().
Referenced by canComputePointerDiff().
bool ScalarEvolution::invalidate | ( | Function & | F, |
const PreservedAnalyses & | PA, | ||
FunctionAnalysisManager::Invalidator & | Inv | ||
) |
Definition at line 14302 of file ScalarEvolution.cpp.
References F, llvm::PreservedAnalyses::getChecker(), and llvm::AnalysisManager< IRUnitT, ExtraArgTs >::Invalidator::invalidate().
Determine if the SCEV can be evaluated at loop's entry.
It is true if it doesn't depend on a SCEVUnknown of an instruction which is dominated by the header of loop L.
Definition at line 2532 of file ScalarEvolution.cpp.
References llvm::LoopBase< BlockT, LoopT >::getHeader(), isLoopInvariant(), and properlyDominates().
Referenced by llvm::cannotBeMaxInLoop(), llvm::cannotBeMinInLoop(), getAddExpr(), getMulExpr(), llvm::hasProcessableCondition(), llvm::isKnownNegativeInLoop(), llvm::isKnownNonNegativeInLoop(), isKnownViaInduction(), isLoopEntryGuardedByCond(), isSafeDecreasingBound(), and isSafeIncreasingBound().
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCount or zero.
Definition at line 8344 of file ScalarEvolution.cpp.
Referenced by PrintLoopInfo(), tryToUnrollLoop(), and llvm::UnrollLoop().
bool ScalarEvolution::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.
Definition at line 11478 of file ScalarEvolution.cpp.
References assert(), llvm::AssumptionCache::assumptions(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::BasicBlock::front(), llvm::BranchInst::getCondition(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopPredecessor(), llvm::CmpInst::getNonStrictPredicate(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::BranchInst::getSuccessor(), llvm::CmpInst::ICMP_NE, llvm::DominatorTree::isReachableFromEntry(), llvm::BranchInst::isUnconditional(), LHS, P, RHS, llvm::verifyFunction(), and VerifyIR.
Referenced by evaluatePredicateAt(), isKnownPredicateAt(), and isLoopEntryGuardedByCond().
Test if the given expression is known to be negative.
Definition at line 10821 of file ScalarEvolution.cpp.
References getSignedRangeMax(), and llvm::APInt::isNegative().
Referenced by llvm::SCEVExpander::generateOverflowCheck(), getSignedOverflowLimitForStep(), getZeroExtendExprImpl(), isOneDimensionalArray(), and isSafeDecreasingBound().
Test if the given expression is known to be non-negative.
Definition at line 10829 of file ScalarEvolution.cpp.
References getSignedRangeMin(), and llvm::APInt::isNegative().
Referenced by detectShiftUntilZeroIdiom(), getGEPExpr(), getLoopInvariantPredicate(), getMinusSCEV(), getSignExtendExprImpl(), and StrengthenNoWrapFlags().
Test if the given expression is known to be non-positive.
Definition at line 10833 of file ScalarEvolution.cpp.
References getSignedRangeMax(), and llvm::APInt::isStrictlyPositive().
Test if the given expression is known to be non-zero.
Definition at line 10837 of file ScalarEvolution.cpp.
References getUnsignedRangeMin().
Referenced by breakBackedgeIfNotTaken().
bool ScalarEvolution::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 of the recurrency LHS.
Definition at line 10953 of file ScalarEvolution.cpp.
References isLoopBackedgeGuardedByCond(), isLoopEntryGuardedByCond(), LHS, and RHS.
Referenced by getZeroExtendExprImpl().
Test if the given expression is known to be positive.
Definition at line 10825 of file ScalarEvolution.cpp.
References getSignedRangeMin(), and llvm::APInt::isStrictlyPositive().
Referenced by llvm::SCEVExpander::generateOverflowCheck(), getLoopInvariantPredicate(), getPreStartForExtend(), getSignedOverflowLimitForStep(), and isSafeDependenceDistance().
bool ScalarEvolution::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, and RHS.
Definition at line 10904 of file ScalarEvolution.cpp.
References isKnownViaInduction(), LHS, RHS, and SimplifyICmpOperands().
Referenced by llvm::calculateUpperBound(), countToEliminateCompares(), evaluatePredicate(), isKnownPredicateAt(), IsKnownPredicateViaAddRecStart(), normalizePredicate(), and llvm::VPlanTransforms::optimizeForVFAndUF().
bool ScalarEvolution::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, and RHS in the given Context.
Definition at line 10929 of file ScalarEvolution.cpp.
References llvm::Instruction::getParent(), isBasicBlockEntryGuardedByCond(), isKnownPredicate(), LHS, and RHS.
Referenced by canOverlap(), createReplacement(), getLoopInvariantExitCondDuringFirstIterationsImpl(), getLoopInvariantPredicate(), and willNotOverflow().
bool ScalarEvolution::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 LHS and RHS.
To do this we use the following list of steps:
Definition at line 10853 of file ScalarEvolution.cpp.
References assert(), llvm::SmallPtrSetImpl< PtrType >::begin(), llvm::DominatorTree::dominates(), llvm::SmallPtrSetImplBase::empty(), llvm::SmallPtrSetImpl< PtrType >::end(), getCouldNotCompute(), isAvailableAtLoopEntry(), isLoopBackedgeGuardedByCond(), isLoopEntryGuardedByCond(), LHS, RHS, and SplitIntoInitAndPostInc().
Referenced by isKnownPredicate().
bool ScalarEvolution::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.
isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
This is used to eliminate casts.
This is used to to eliminate casts.
Definition at line 11373 of file ScalarEvolution.cpp.
References assert(), llvm::AssumptionCache::assumptions(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, getAddRecExpr(), llvm::BranchInst::getCondition(), getCouldNotCompute(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), getOne(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::SCEV::getType(), getZero(), llvm::CmpInst::ICMP_ULT, llvm::BranchInst::isConditional(), llvm::DominatorTree::isReachableFromEntry(), llvm::BasicBlockEdge::isSingleEdge(), LHS, RHS, llvm::verifyFunction(), and VerifyIR.
Referenced by getLoopInvariantExitCondDuringFirstIterationsImpl(), getLoopInvariantPredicate(), getZeroExtendExprImpl(), isKnownOnEveryIteration(), and isKnownViaInduction().
bool ScalarEvolution::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.
This is used to help avoid max expressions in loop trip counts, and to eliminate casts.
Definition at line 11569 of file ScalarEvolution.cpp.
References assert(), llvm::LoopBase< BlockT, LoopT >::getHeader(), isAvailableAtLoopEntry(), isBasicBlockEntryGuardedByCond(), LHS, and RHS.
Referenced by llvm::cannotBeMaxInLoop(), llvm::cannotBeMinInLoop(), llvm::findSplitCandidate(), getPreStartForExtend(), getTripCount(), llvm::isKnownNegativeInLoop(), llvm::isKnownNonNegativeInLoop(), isKnownOnEveryIteration(), isKnownViaInduction(), isSafeDecreasingBound(), and isSafeIncreasingBound().
Return true if the value of the given SCEV is unchanging in the specified loop.
Definition at line 13775 of file ScalarEvolution.cpp.
References getLoopDisposition(), and LoopInvariant.
Referenced by llvm::RecurrenceDescriptor::AddReductionVar(), canTailPredicateLoop(), computeUnrollAndJamCount(), CreateStepValue(), createWidenInductionRecipes(), findForkedPointer(), genLoopLimit(), getAddRecExpr(), getAddressAccessSCEV(), getConstantMaxTripCountFromArray(), getLoopInvariantExitCondDuringFirstIterationsImpl(), getLoopInvariantPredicate(), hasComputableBounds(), llvm::RuntimePointerChecking::insert(), llvm::Loop::isAuxiliaryInductionVariable(), isAvailableAtLoopEntry(), llvm::isDereferenceableAndAlignedInLoop(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), llvm::InductionDescriptor::isInductionPHI(), isNoWrap(), isOneDimensionalArray(), llvm::LoopAccessInfo::isUniform(), mayUsePostIncMode(), print(), llvm::rewriteLoopExitValues(), SimplifyICmpOperands(), llvm::stripGetElementPtr(), llvm::VPRecipeBuilder::tryToCreateWidenRecipe(), and llvm::VPlanTransforms::VPInstructionsToVPRecipes().
Test if values of the given type are analyzable within the SCEV framework.
This primarily includes integer types, and it can optionally include pointer types if the ScalarEvolution class has access to target-specific information.
Definition at line 4420 of file ScalarEvolution.cpp.
References llvm::Type::isIntOrPtrTy().
Referenced by llvm::IVUsers::AddUsersIfInteresting(), canFoldTermCondOfLoop(), DbgGatherSalvagableDVI(), findForkedPointer(), findIVOperand(), forgetBlockAndLoopDispositions(), getAnyExtendExpr(), getEffectiveSCEVType(), GetInductionVariable(), getSCEV(), getSignExtendExpr(), getSignExtendExprImpl(), getTruncateExpr(), getTypeSizeInBits(), getZeroExtendExpr(), getZeroExtendExprImpl(), isExistingPhi(), isHighCostExpansion(), isLoopCounter(), llvm::isProcessableCondBI(), isSimpleIVUser(), llvm::LoopAccessInfo::isUniform(), print(), llvm::PredicatedScalarEvolution::print(), llvm::SCEVExpander::replaceCongruentIVs(), llvm::rewriteLoopExitValues(), and llvm::splitLoopBound().
Return true if the loop has no abnormal exits.
That is, if the loop is not infinite, it must exit through an explicit edge in the CFG. (As opposed to either a) throwing out of the function or b) entering a well defined infinite loop in some callee.)
Definition at line 1291 of file ScalarEvolution.h.
Referenced by llvm::UnrollRuntimeLoopRemainder().
Return true if this loop is finite by assumption.
That is, to be infinite, it must also be undefined.
Definition at line 7389 of file ScalarEvolution.cpp.
References llvm::isFinite(), and llvm::isMustProgress().
|
inlinestatic |
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name space.
Definition at line 472 of file ScalarEvolution.h.
Referenced by getAddExpr(), getAddRecExpr(), getMulExpr(), getPreStartForExtend(), hasFlags(), llvm::SCEVExpander::hoistIVInc(), and StrengthenNoWrapFlags().
void ScalarEvolution::print | ( | raw_ostream & | OS | ) | const |
Definition at line 13595 of file ScalarEvolution.cpp.
References ClassifyExpressions, llvm::depth_first(), getLoopDisposition(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), getSCEV(), getSCEVAtScope(), getSignedRange(), getUnsignedRange(), I, instructions, isLoopInvariant(), isSCEVable(), loopDispositionToStr(), llvm::SCEV::print(), llvm::ConstantRange::print(), llvm::Value::printAsOperand(), and PrintLoopInfo().
Referenced by llvm::ScalarEvolutionWrapperPass::print().
bool ScalarEvolution::properlyDominates | ( | const SCEV * | S, |
const BasicBlock * | BB | ||
) |
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
Definition at line 13861 of file ScalarEvolution.cpp.
References getBlockDisposition(), and ProperlyDominatesBlock.
Referenced by DoInitialMatch(), isAvailableAtLoopEntry(), llvm::SCEVExpander::isSafeToExpandAt(), and SimplifyICmpOperands().
Notify this ScalarEvolution that User
directly uses SCEVs in Ops
.
Definition at line 14708 of file ScalarEvolution.cpp.
Referenced by getLosslessPtrToIntExpr(), getMinMaxExpr(), getSequentialMinMaxExpr(), getSignExtendExprImpl(), getTruncateExpr(), getUDivExpr(), and getZeroExtendExprImpl().
Compute an expression equivalent to S - getPointerBase(S).
Definition at line 4612 of file ScalarEvolution.cpp.
References llvm::Add, assert(), llvm::SCEV::FlagAnyWrap, getAddExpr(), getAddRecExpr(), getZero(), P, and removePointerBase().
Referenced by getMinusSCEV(), and removePointerBase().
const SCEV * ScalarEvolution::rewriteUsingPredicate | ( | const SCEV * | S, |
const Loop * | L, | ||
const SCEVPredicate & | A | ||
) |
Re-writes the SCEV according to the Predicates in A
.
Definition at line 14552 of file ScalarEvolution.cpp.
Referenced by llvm::PredicatedScalarEvolution::getSCEV().
|
inlinestatic |
Definition at line 476 of file ScalarEvolution.h.
Referenced by getAddExpr(), llvm::SCEVWrapPredicate::getImpliedFlags(), getStrengthenedNoWrapFlagsFromBinOp(), llvm::SCEVWrapPredicate::isAlwaysTrue(), llvm::SCEVAddRecExpr::setNoWrapFlags(), and StrengthenNoWrapFlags().
void ScalarEvolution::setNoWrapFlags | ( | SCEVAddRecExpr * | AddRec, |
SCEV::NoWrapFlags | Flags | ||
) |
Update no-wrap flags of an AddRec.
This may drop the cached info about this AddRec (such as range info) in case if new flags may potentially sharpen it.
Definition at line 6397 of file ScalarEvolution.cpp.
References llvm::SCEVNAryExpr::getNoWrapFlags(), and llvm::SCEVAddRecExpr::setNoWrapFlags().
Referenced by getPreStartForExtend(), getSignExtendExprImpl(), and getZeroExtendExprImpl().
bool ScalarEvolution::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.
Return true iff any changes were made. If the operands are provably equal or unequal, LHS and RHS are set to the same value and Pred is set to either ICMP_EQ or ICMP_NE. ControllingFiniteLoop is set if this comparison controls the exit of a loop known to have a finite number of iterations.
Definition at line 10617 of file ScalarEvolution.cpp.
References assert(), llvm::Depth, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, getAddExpr(), getConstant(), getContext(), llvm::ConstantRange::getEquivalentICmp(), llvm::ConstantInt::getFalse(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::ConstantExpr::getICmp(), llvm::SCEVAddRecExpr::getLoop(), getSignedRangeMax(), getSignedRangeMin(), llvm::CmpInst::getSwappedPredicate(), llvm::Value::getType(), getUnsignedRangeMax(), getUnsignedRangeMin(), HasSameValue(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::ConstantRange::isEmptySet(), llvm::ICmpInst::isEquality(), llvm::CmpInst::isFalseWhenEqual(), llvm::ConstantRange::isFullSet(), isLoopInvariant(), llvm::Constant::isNullValue(), llvm::CmpInst::isTrueWhenEqual(), LHS, llvm::ConstantRange::makeExactICmpRegion(), properlyDominates(), RA, RHS, SimplifyICmpOperands(), and std::swap().
Referenced by isKnownPredicate(), and SimplifyICmpOperands().
std::pair< const SCEV *, const SCEV * > ScalarEvolution::SplitIntoInitAndPostInc | ( | const Loop * | L, |
const SCEV * | S | ||
) |
Splits SCEV expression S
into two SCEVs.
One of them is obtained from S
by substitution of all AddRec sub-expression related to loop L
with initial value of that SCEV. The second is obtained from S
by substitution of all AddRec sub-expressions related to loop L
with post increment of this AddRec in the loop L
. In both cases all other AddRec sub-expressions (not related to L
) remain the same. If the S
contains non-invariant unknown SCEV the function returns CouldNotCompute SCEV in both values of std::pair. For example, for SCEV S={0, +, 1}<L1> + {0, +, 1}<L2> and loop L=L1 the function returns pair: first = {0, +, 1}<L2> second = {1, +, 1}<L1> + {0, +, 1}<L2> We can see that for the first AddRec sub-expression it was replaced with 0 (initial value) for the first element and to {1, +, 1}<L1> (post increment value) for the second one. In both cases AddRec expression related to L2 remains the same.
Definition at line 10842 of file ScalarEvolution.cpp.
References assert(), getCouldNotCompute(), and PostInc.
Referenced by isKnownViaInduction().
void ScalarEvolution::verify | ( | ) | const |
Definition at line 14026 of file ScalarEvolution.cpp.
References llvm::SmallVectorImpl< T >::append(), llvm::append_range(), assert(), llvm::LoopBase< BlockT, LoopT >::begin(), llvm::LoopInfoBase< BlockT, LoopT >::begin(), llvm::SmallPtrSetImpl< PtrType >::contains(), containsUndefs(), llvm::dbgs(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::LoopBase< BlockT, LoopT >::end(), llvm::LoopInfoBase< BlockT, LoopT >::end(), F, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), getBackedgeTakenCount(), getBlockDisposition(), getConstant(), getCouldNotCompute(), llvm::SCEVAddRecExpr::getLoop(), getLoopDisposition(), getMinusSCEV(), llvm::Value::getName(), getSCEV(), getTypeSizeInBits(), getUnknown(), llvm::SCEVUnknown::getValue(), getZeroExtendExpr(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::is_contained(), llvm::SCEV::isZero(), loopDispositionToStr(), llvm::SCEV::operands(), llvm::SmallVectorImpl< T >::pop_back_val(), and VerifySCEVStrict.
Referenced by llvm::FunctionToLoopPassAdaptor::run(), llvm::UnrollAndJamLoop(), and llvm::ScalarEvolutionWrapperPass::verifyAnalysis().
bool ScalarEvolution::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
)? If CtxI
is specified, the no-overflow fact should be true in the context of this instruction.
Definition at line 2342 of file ScalarEvolution.cpp.
References A, B, llvm::CallingConv::C, llvm::SCEV::FlagAnyWrap, llvm::IntegerType::get(), getAddExpr(), getConstant(), llvm::APInt::getMaxValue(), getMinusSCEV(), getMulExpr(), llvm::APInt::getSignedMaxValue(), getSignExtendExpr(), llvm::Value::getType(), getZeroExtendExpr(), llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_ULE, isKnownPredicateAt(), LHS, llvm_unreachable, Operation, RHS, and Signed.
Referenced by getStrengthenedNoWrapFlagsFromBinOp().
|
friend |
Definition at line 453 of file ScalarEvolution.h.
|
friend |
Definition at line 1351 of file ScalarEvolution.h.
|
friend |
Definition at line 1352 of file ScalarEvolution.h.
|
friend |
Definition at line 1353 of file ScalarEvolution.h.
Referenced by getUnknown().