llvm::ScalarEvolution Class Reference

The main scalar evolution driver. More...

#include "llvm/Analysis/ScalarEvolution.h"

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...

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. More...
uint64_t	getTypeSizeInBits (Type *Ty) const
	Return the size in bits of the specified type, for which isSCEVable must return true. More...
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. More...
Type *	getWiderType (Type *Ty1, Type *Ty2) const
bool	containsAddRecurrence (const SCEV *S)
	Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr. More...
void	eraseValueFromMap (Value *V)
	Erase Value from ValueExprMap and ExprValueMap. More...
const SCEV *	getSCEV (Value *V)
	Return a SCEV expression for the full generality of the specified expression. More...
const SCEV *	getConstant (ConstantInt *V)
const SCEV *	getConstant (const APInt &Val)
const SCEV *	getConstant (Type *Ty, uint64_t V, bool isSigned=false)
const SCEV *	getTruncateExpr (const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV *	getZeroExtendExpr (const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV *	getSignExtendExpr (const SCEV *Op, Type *Ty, unsigned Depth=0)
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. More...
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. More...
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. More...
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. More...
const SCEV *	getUDivExactExpr (const SCEV *LHS, const SCEV *RHS)
	Get a canonical unsigned division expression, or something simpler if possible. More...
const SCEV *	getURemExpr (const SCEV *LHS, const SCEV *RHS)
	Represents an unsigned remainder expression based on unsigned division. More...
const SCEV *	getAddRecExpr (const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
	Get an add recurrence expression for the specified loop. More...
const SCEV *	getAddRecExpr (SmallVectorImpl< const SCEV *> &Operands, const Loop *L, SCEV::NoWrapFlags Flags)
	Get an add recurrence expression for the specified loop. More...
const SCEV *	getAddRecExpr (const SmallVectorImpl< const SCEV *> &Operands, const Loop *L, SCEV::NoWrapFlags Flags)
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. More...
const SCEV *	getGEPExpr (GEPOperator *GEP, const SmallVectorImpl< const SCEV *> &IndexExprs)
	Returns an expression for a GEP. More...
const SCEV *	getMinMaxExpr (unsigned 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)
const SCEV *	getUMinExpr (SmallVectorImpl< const SCEV *> &Operands)
const SCEV *	getUnknown (Value *V)
const SCEV *	getCouldNotCompute ()
const SCEV *	getZero (Type *Ty)
	Return a SCEV for the constant 0 of a specific type. More...
const SCEV *	getOne (Type *Ty)
	Return a SCEV for the constant 1 of a specific type. More...
const SCEV *	getSizeOfExpr (Type *IntTy, Type *AllocTy)
	Return an expression for sizeof AllocTy that is type IntTy. More...
const SCEV *	getOffsetOfExpr (Type *IntTy, StructType *STy, unsigned FieldNo)
	Return an expression for offsetof on the given field with type IntTy. More...
const SCEV *	getNegativeSCEV (const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
	Return the SCEV object corresponding to -V. More...
const SCEV *	getNotSCEV (const SCEV *V)
	Return the SCEV object corresponding to ~V. More...
const SCEV *	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. More...
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. More...
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. More...
const SCEV *	getNoopOrZeroExtend (const SCEV *V, Type *Ty)
	Return a SCEV corresponding to a conversion of the input value to the specified type. More...
const SCEV *	getNoopOrSignExtend (const SCEV *V, Type *Ty)
	Return a SCEV corresponding to a conversion of the input value to the specified type. More...
const SCEV *	getNoopOrAnyExtend (const SCEV *V, Type *Ty)
	Return a SCEV corresponding to a conversion of the input value to the specified type. More...
const SCEV *	getTruncateOrNoop (const SCEV *V, Type *Ty)
	Return a SCEV corresponding to a conversion of the input value to the specified type. More...
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. More...
const SCEV *	getUMinFromMismatchedTypes (const SCEV *LHS, const SCEV *RHS)
	Promote the operands to the wider of the types using zero-extension, and then perform a umin operation with them. More...
const SCEV *	getUMinFromMismatchedTypes (SmallVectorImpl< const SCEV *> &Ops)
	Promote the operands to the wider of the types using zero-extension, and then perform a umin operation with them. More...
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. More...
const SCEV *	getSCEVAtScope (const SCEV *S, const Loop *L)
	Return a SCEV expression for the specified value at the specified scope in the program. More...
const SCEV *	getSCEVAtScope (Value *V, const Loop *L)
	This is a convenience function which does getSCEVAtScope(getSCEV(V), L). More...
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. More...
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. More...
unsigned	getSmallConstantTripCount (const Loop *L)
	Returns the maximum trip count of the loop if it is a single-exit loop and we can compute a small maximum for that loop. More...
unsigned	getSmallConstantTripCount (const Loop *L, BasicBlock *ExitingBlock)
	Returns the maximum trip count of this loop as a normal unsigned value. More...
unsigned	getSmallConstantMaxTripCount (const Loop *L)
	Returns the upper bound of the loop trip count as a normal unsigned value. More...
unsigned	getSmallConstantTripMultiple (const Loop *L)
	Returns the largest constant divisor of the trip count of the loop if it is a single-exit loop and we can compute a small maximum for that loop. More...
unsigned	getSmallConstantTripMultiple (const Loop *L, BasicBlock *ExitingBlock)
	Returns the largest constant divisor of the trip count of this loop as a normal unsigned value, if possible. More...
const SCEV *	getExitCount (const Loop *L, BasicBlock *ExitingBlock)
	Return the number of times the backedge executes before the given exit would be taken; if not exactly computable, return SCEVCouldNotCompute. More...
const SCEV *	getBackedgeTakenCount (const Loop *L)
	If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCouldNotCompute object. More...
const SCEV *	getPredicatedBackedgeTakenCount (const Loop *L, SCEVUnionPredicate &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. More...
const SCEV *	getConstantMaxBackedgeTakenCount (const Loop *L)
	When successful, this returns a SCEVConstant that is greater than or equal to (i.e. More...
bool	isBackedgeTakenCountMaxOrZero (const Loop *L)
	Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCount or zero. More...
bool	hasLoopInvariantBackedgeTakenCount (const Loop *L)
	Return true if the specified loop has an analyzable loop-invariant backedge-taken count. More...
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. More...
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. More...
void	forgetLoopDispositions (const Loop *L)
	Called when the client has changed the disposition of values in this loop. More...
uint32_t	GetMinTrailingZeros (const SCEV *S)
	Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration). More...
ConstantRange	getUnsignedRange (const SCEV *S)
	Determine the unsigned range for a particular SCEV. More...
APInt	getUnsignedRangeMin (const SCEV *S)
	Determine the min of the unsigned range for a particular SCEV. More...
APInt	getUnsignedRangeMax (const SCEV *S)
	Determine the max of the unsigned range for a particular SCEV. More...
ConstantRange	getSignedRange (const SCEV *S)
	Determine the signed range for a particular SCEV. More...
APInt	getSignedRangeMin (const SCEV *S)
	Determine the min of the signed range for a particular SCEV. More...
APInt	getSignedRangeMax (const SCEV *S)
	Determine the max of the signed range for a particular SCEV. More...
bool	isKnownNegative (const SCEV *S)
	Test if the given expression is known to be negative. More...
bool	isKnownPositive (const SCEV *S)
	Test if the given expression is known to be positive. More...
bool	isKnownNonNegative (const SCEV *S)
	Test if the given expression is known to be non-negative. More...
bool	isKnownNonPositive (const SCEV *S)
	Test if the given expression is known to be non-positive. More...
bool	isKnownNonZero (const SCEV *S)
	Test if the given expression is known to be non-zero. More...
std::pair< const SCEV *, const SCEV * >	SplitIntoInitAndPostInc (const Loop *L, const SCEV *S)
	Splits SCEV expression S into two SCEVs. More...
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. More...
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. More...
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. More...
bool	isMonotonicPredicate (const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred, bool &Increasing)
	Return true if, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing. More...
bool	isLoopInvariantPredicate (ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, ICmpInst::Predicate &InvariantPred, const SCEV *&InvariantLHS, const SCEV *&InvariantRHS)
	Return true if the result of the predicate LHS Pred RHS is loop invariant with respect to L. More...
bool	SimplifyICmpOperands (ICmpInst::Predicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0)
	Simplify LHS and RHS in a comparison with predicate Pred. More...
LoopDisposition	getLoopDisposition (const SCEV *S, const Loop *L)
	Return the "disposition" of the given SCEV with respect to the given loop. More...
bool	isLoopInvariant (const SCEV *S, const Loop *L)
	Return true if the value of the given SCEV is unchanging in the specified loop. More...
bool	isAvailableAtLoopEntry (const SCEV *S, const Loop *L)
	Determine if the SCEV can be evaluated at loop's entry. More...
bool	hasComputableLoopEvolution (const SCEV *S, const Loop *L)
	Return true if the given SCEV changes value in a known way in the specified loop. More...
BlockDisposition	getBlockDisposition (const SCEV *S, const BasicBlock *BB)
	Return the "disposition" of the given SCEV with respect to the given block. More...
bool	dominates (const SCEV *S, const BasicBlock *BB)
	Return true if elements that makes up the given SCEV dominate the specified basic block. More...
bool	properlyDominates (const SCEV *S, const BasicBlock *BB)
	Return true if elements that makes up the given SCEV properly dominate the specified basic block. More...
bool	hasOperand (const SCEV *S, const SCEV *Op) const
	Test whether the given SCEV has Op as a direct or indirect operand. More...
const SCEV *	getElementSize (Instruction *Inst)
	Return the size of an element read or written by Inst. More...
void	findArrayDimensions (SmallVectorImpl< const SCEV *> &Terms, SmallVectorImpl< const SCEV *> &Sizes, const SCEV *ElementSize)
	Compute the array dimensions Sizes from the set of Terms extracted from the memory access function of this SCEVAddRecExpr (second step of delinearization). More...
void	print (raw_ostream &OS) const
void	verify () const
bool	invalidate (Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
void	collectParametricTerms (const SCEV *Expr, SmallVectorImpl< const SCEV *> &Terms)
	Collect parametric terms occurring in step expressions (first step of delinearization). More...
void	computeAccessFunctions (const SCEV *Expr, SmallVectorImpl< const SCEV *> &Subscripts, SmallVectorImpl< const SCEV *> &Sizes)
	Return in Subscripts the access functions for each dimension in Sizes (third step of delinearization). More...
void	delinearize (const SCEV *Expr, SmallVectorImpl< const SCEV *> &Subscripts, SmallVectorImpl< const SCEV *> &Sizes, const SCEV *ElementSize)
	Split this SCEVAddRecExpr into two vectors of SCEVs representing the subscripts and sizes of an array access. More...
const DataLayout &	getDataLayout () const
	Return the DataLayout associated with the module this SCEV instance is operating on. More...
const SCEVPredicate *	getEqualPredicate (const SCEV *LHS, const SCEV *RHS)
const SCEVPredicate *	getWrapPredicate (const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
const SCEV *	rewriteUsingPredicate (const SCEV *S, const Loop *L, SCEVUnionPredicate &A)
	Re-writes the SCEV according to the Predicates in A. More...
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. More...

Static Public Member Functions
static LLVM_NODISCARD SCEV::NoWrapFlags	maskFlags (SCEV::NoWrapFlags Flags, int Mask)
	Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name space. More...
static LLVM_NODISCARD SCEV::NoWrapFlags	setFlags (SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
static LLVM_NODISCARD SCEV::NoWrapFlags	clearFlags (SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)

Friends
class	ScalarEvolutionsTest
class	SCEVCallbackVH
class	SCEVExpander
class	SCEVUnknown

Detailed Description

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 470 of file ScalarEvolution.h.

Member Enumeration Documentation

BlockDisposition

enum llvm::ScalarEvolution::BlockDisposition

An enum describing the relationship between a SCEV and a basic block.

Enumerator
DoesNotDominateBlock	The SCEV does not dominate the block.
DominatesBlock	The SCEV dominates the block.
ProperlyDominatesBlock	The SCEV properly dominates the block.

Definition at line 482 of file ScalarEvolution.h.

LoopDisposition

enum llvm::ScalarEvolution::LoopDisposition

An enum describing the relationship between a SCEV and a loop.

Enumerator
LoopVariant	The SCEV is loop-variant (unknown).
LoopInvariant	The SCEV is loop-invariant.
LoopComputable	The SCEV varies predictably with the loop.

Definition at line 475 of file ScalarEvolution.h.

Constructor & Destructor Documentation

ScalarEvolution() [1/2]

ScalarEvolution::ScalarEvolution	(	Function &	F,
		TargetLibraryInfo &	TLI,
		AssumptionCache &	AC,
		DominatorTree &	DT,
		LoopInfo &	LI
	)

Definition at line 11383 of file ScalarEvolution.cpp.

References llvm::Module::getFunction(), llvm::Intrinsic::getName(), and llvm::GlobalValue::getParent().

Referenced by llvm::ScalarEvolutionAnalysis::run(), and llvm::ScalarEvolutionWrapperPass::runOnFunction().

ScalarEvolution() [2/2]

ScalarEvolution::ScalarEvolution

(

ScalarEvolution &&

Arg

)

Definition at line 11404 of file ScalarEvolution.cpp.

References Arg.

~ScalarEvolution()

ScalarEvolution::~ScalarEvolution

(

)

Definition at line 11432 of file ScalarEvolution.cpp.

References assert(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear().

Member Function Documentation

clearFlags()

static LLVM_NODISCARD SCEV::NoWrapFlags llvm::ScalarEvolution::clearFlags ( SCEV::NoWrapFlags  Flags, SCEV::NoWrapFlags  OffFlags  )

inlinestatic

Definition at line 499 of file ScalarEvolution.h.

References Arg, and F().

Referenced by PickMostRelevantLoop().

collectParametricTerms()

void ScalarEvolution::collectParametricTerms	(	const SCEV *	Expr,
		SmallVectorImpl< const SCEV *> &	Terms
	)

Collect parametric terms occurring in step expressions (first step of delinearization).

Find parametric terms in this SCEVAddRecExpr.

We first for parameters in two places: 1) The strides of AddRec expressions. 2) Unknowns that are multiplied with AddRec expressions.

Definition at line 11009 of file ScalarEvolution.cpp.

References llvm::dbgs(), LLVM_DEBUG, and llvm::visitAll().

computeAccessFunctions()

void ScalarEvolution::computeAccessFunctions	(	const SCEV *	Expr,
		SmallVectorImpl< const SCEV *> &	Subscripts,
		SmallVectorImpl< const SCEV *> &	Sizes
	)

Return in Subscripts the access functions for each dimension in Sizes (third step of delinearization).

Definition at line 11193 of file ScalarEvolution.cpp.

References llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::dbgs(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::SCEVAddRecExpr::isAffine(), LLVM_DEBUG, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::reverse(), and llvm::SmallVectorBase::size().

containsAddRecurrence()

bool ScalarEvolution::containsAddRecurrence

(

const SCEV *

S

)

Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.

The result will be cached in HasRecMap.

Definition at line 3811 of file ScalarEvolution.cpp.

References I, and llvm::SCEVExprContains().

convertSCEVToAddRecWithPredicates()

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 12204 of file ScalarEvolution.cpp.

References llvm::dyn_cast(), llvm::SmallPtrSetImpl< PtrType >::insert(), P, and rewrite().

Referenced by llvm::PredicatedScalarEvolution::getAsAddRec().

createAddRecFromPHIWithCasts()

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 4895 of file ScalarEvolution.cpp.

References assert(), llvm::SCEVUnknown::getValue(), I, isIntegerLoopHeaderPHI(), and llvm::None.

Referenced by getWrapPredicate().

delinearize()

void ScalarEvolution::delinearize	(	const SCEV *	Expr,
		SmallVectorImpl< const SCEV *> &	Subscripts,
		SmallVectorImpl< const SCEV *> &	Sizes,
		const SCEV *	ElementSize
	)

Split this SCEVAddRecExpr into two vectors of SCEVs representing the subscripts and sizes of an array access.

Splits the SCEV into two vectors of SCEVs representing the subscripts and sizes of an array access.

The delinearization is a 3 step process: the first two steps compute the sizes of each subscript and the third step computes the access functions for the delinearized array:

1. Find the terms in the step functions
2. Compute the array size
3. Compute the access function: divide the SCEV by the array size starting with the innermost dimensions found in step 2. The Quotient is the SCEV to be divided in the next step of the recursion. The Remainder is the subscript of the innermost dimension. Loop over all array dimensions computed in step 2.

To compute a uniform array size for several memory accesses to the same object, one can collect in step 1 all the step terms for all the memory accesses, and compute in step 2 a unique array shape. This guarantees that the array shape will be the same across all memory accesses.

FIXME: We could derive the result of steps 1 and 2 from a description of the array shape given in metadata.

Example:

A[][n][m]

for i for j for k A[j+k][2i][5i] =

The initial SCEV:

A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k]

1. Find the different terms in the step functions: -> [2*m, 5, n*m, n*m]
2. Compute the array size: sort and unique them -> [n*m, 2*m, 5] find the GCD of all the terms = 1 divide by the GCD and erase constant terms -> [n*m, 2*m] GCD = m divide by GCD -> [n, 2] remove constant terms -> [n] size of the array is A[unknown][n][m]
3. Compute the access function a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k The remainder is the subscript of the innermost array dimension: [5i].

b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k The Remainder is the subscript of the next array dimension: [2i].

The subscript of the outermost dimension is the Quotient: [j+k].

Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i].

Returns the remainder of the delinearization that is the offset start of the array. The SCEV->delinearize algorithm computes the multiples of SCEV coefficients: that is a pattern matching of sub expressions in the stride and base of a SCEV corresponding to the computation of a GCD (greatest common divisor) of base and stride. When SCEV->delinearize fails, it returns the SCEV unchanged.

For example: when analyzing the memory access A[i][j][k] in this loop nest

void foo(long n, long m, long o, double A[n][m][o]) {

for (long i = 0; i < n; i++) for (long j = 0; j < m; j++) for (long k = 0; k < o; k++) A[i][j][k] = 1.0; }

the delinearization input is the following AddRec SCEV:

AddRec: {{{A,+,(8 * m * o)}<for.i>,+,(8 * o)}<for.j>,+,8}<for.k>

From this SCEV, we are able to say that the base offset of the access is A because it appears as an offset that does not divide any of the strides in the loops:

CHECK: Base offset: A

and then SCEV->delinearize determines the size of some of the dimensions of the array as these are the multiples by which the strides are happening:

CHECK: ArrayDecl[UnknownSize][m][o] with elements of sizeof(double) bytes.

Note that the outermost dimension remains of UnknownSize because there are no strides that would help identifying the size of the last dimension: when the array has been statically allocated, one could compute the size of that dimension by dividing the overall size of the array by the size of the known dimensions: m * o * 8.

Finally delinearize provides the access functions for the array reference that does correspond to A[i][j][k] of the above C testcase:

CHECK: ArrayRef[{0,+,1}<for.i>][{0,+,1}<for.j>][{0,+,1}<for.k>]

The testcases are checking the output of a function pass: DelinearizationPass that walks through all loads and stores of a function asking for the SCEV of the memory access with respect to all enclosing loops, calling SCEV->delinearize on that and printing the results.

Definition at line 11299 of file ScalarEvolution.cpp.

References assert(), llvm::dbgs(), llvm::SmallVectorBase::empty(), eraseValueFromMap(), llvm::SmallVectorImpl< T >::insert(), LLVM_DEBUG, llvm::Value::user_begin(), and llvm::Value::user_end().

Referenced by llvm::IndexedReference::computeRefCost().

dominates()

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 11818 of file ScalarEvolution.cpp.

References DominatesBlock, and getBlockDisposition().

Referenced by llvm::SCEVExpander::expandUnionPredicate(), and llvm::isSafeToExpandAt().

eraseValueFromMap()

void ScalarEvolution::eraseValueFromMap

(

Value *

V

)

Erase Value from ValueExprMap and ExprValueMap.

ValueExprMap.erase(V) cannot be used separately. eraseValueFromMap should be used to remove V from ValueExprMap and ExprValueMap at the same time.

Definition at line 3859 of file ScalarEvolution.cpp.

References I, and splitAddExpr().

Referenced by delinearize().

findArrayDimensions()

void ScalarEvolution::findArrayDimensions	(	SmallVectorImpl< const SCEV *> &	Terms,
		SmallVectorImpl< const SCEV *> &	Sizes,
		const SCEV *	ElementSize
	)

Compute the array dimensions Sizes from the set of Terms extracted from the memory access function of this SCEVAddRecExpr (second step of delinearization).

Definition at line 11130 of file ScalarEvolution.cpp.

References llvm::array_pod_sort(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorImpl< T >::clear(), containsParameters(), llvm::dbgs(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::SmallVectorImpl< T >::erase(), findArrayDimensionsRec(), llvm::SCEV::isZero(), LLVM_DEBUG, numberOfTerms(), llvm::SmallVectorTemplateBase< T >::push_back(), removeConstantFactors(), llvm::SmallVectorBase::size(), and llvm::sort().

forgetAllLoops()

void ScalarEvolution::forgetAllLoops

(

)

Definition at line 6760 of file ScalarEvolution.cpp.

Referenced by llvm::UnrollLoop().

forgetLoop()

void ScalarEvolution::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.

This call is potentially expensive for large loop bodies.

Definition at line 6782 of file ScalarEvolution.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorBase::empty(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), PushDefUseChildren(), and PushLoopPHIs().

Referenced by createFFSIntrinsic(), llvm::formLCSSA(), separateNestedLoop(), llvm::UnrollAndJamLoop(), unswitchNontrivialInvariants(), unswitchTrivialBranch(), unswitchTrivialSwitch(), and llvm::InnerLoopVectorizer::updateAnalysis().

forgetLoopDispositions()

void llvm::ScalarEvolution::forgetLoopDispositions ( const Loop *  L )

inline

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 821 of file ScalarEvolution.h.

Referenced by llvm::createLICMPass(), isLoopDead(), and sinkLoopInvariantInstructions().

forgetTopmostLoop()

void ScalarEvolution::forgetTopmostLoop

(

const Loop *

L

)

Definition at line 6848 of file ScalarEvolution.cpp.

References llvm::LoopBase< BlockT, LoopT >::getParentLoop().

Referenced by getInnermostLoopFor(), llvm::peelLoop(), simplifyLoopCFG(), llvm::UnrollLoop(), llvm::UnrollRuntimeLoopRemainder(), unswitchNontrivialInvariants(), unswitchTrivialBranch(), and unswitchTrivialSwitch().

forgetValue()

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 6854 of file ScalarEvolution.cpp.

References llvm::SCEVUnionPredicate::add(), llvm::any_of(), assert(), llvm::ArrayRef< T >::begin(), clear(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::DominatorTree::dominates(), llvm::dyn_cast(), llvm::numbers::e, E, llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorBase::empty(), llvm::ArrayRef< T >::end(), llvm::find(), llvm::SwitchInst::findCaseDest(), llvm::SwitchInst::getCondition(), getCouldNotCompute(), llvm::SwitchInst::getDefaultDest(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::LoopBase< BlockT, LoopT >::getExitingBlocks(), llvm::CmpInst::getInversePredicate(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::CmpInst::getSwappedPredicate(), llvm::BasicBlock::getTerminator(), getUMinFromMismatchedTypes(), hasOperand(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULT, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::ConstantRange::makeExactICmpRegion(), llvm::None, P, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), PushDefUseChildren(), llvm::MipsISD::Ret, llvm::X86ISD::SBB, SI, llvm::SmallVectorBase::size(), llvm::ArrayRef< T >::size(), llvm::successors(), std::swap(), and llvm::transform().

getAddExpr() [1/3]

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 2406 of file ScalarEvolution.cpp.

References llvm::MCID::Add, llvm::FoldingSetNodeID::AddInteger(), llvm::AddOne(), AddOpsInlineThreshold, llvm::FoldingSetNodeID::AddPointer(), llvm::SmallVectorImpl< T >::append(), assert(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::ArrayRef< T >::begin(), C, llvm::SmallVectorImpl< T >::clear(), CollectAddOperandsWithScales(), llvm::SmallVectorTemplateCommon< T >::data(), llvm::numbers::e, llvm::SmallVectorBase::empty(), llvm::ArrayRef< T >::end(), llvm::SmallVectorImpl< T >::erase(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVCastExpr::getType(), GroupByComplexity(), hasHugeExpression(), llvm::FoldingSetNodeID::Intern(), MaxArithDepth, llvm::RISCVFenceField::O, llvm::SCEVCastExpr::Op, llvm::SCEVNAryExpr::op_begin(), llvm::SCEVNAryExpr::op_end(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::scAddExpr, llvm::scAddRecExpr, llvm::scMulExpr, llvm::SCEVCommutativeExpr::setNoWrapFlags(), llvm::SCEVAddRecExpr::setNoWrapFlags(), llvm::SmallVectorBase::size(), llvm::ArrayRef< T >::size(), StrengthenNoWrapFlags(), llvm::SCEVCastExpr::Ty, and llvm::APInt::ult().

Referenced by canBeCheaplyTransformed(), canFoldIVIncExpr(), computeTripCount(), countToEliminateCompares(), createFFSIntrinsic(), DoInitialMatch(), llvm::SCEVAddRecExpr::evaluateAtIteration(), expandBounds(), ExposePointerBase(), ExtractImmediate(), ExtractSymbol(), FactorOutConstant(), genLoopLimit(), getNumBytes(), llvm::SCEVAddRecExpr::getPostIncExpr(), hasHugeExpression(), llvm::RuntimePointerChecking::insert(), llvm::isConsecutiveAccess(), llvm::ARMTTIImpl::isHardwareLoopProfitable(), IsIncrementNSW(), IsIncrementNUW(), mayUsePostIncMode(), SimplifyAddOperands(), llvm::UnrollRuntimeLoopRemainder(), llvm::SCEVRewriteVisitor< SCEVLoopAddRecRewriter >::visitAddExpr(), and willNotOverflow().

getAddExpr() [2/3]

const SCEV* llvm::ScalarEvolution::getAddExpr ( const SCEV *  LHS, const SCEV *  RHS, SCEV::NoWrapFlags  Flags = SCEV::FlagAnyWrap, unsigned  Depth = 0  )

inline

Definition at line 549 of file ScalarEvolution.h.

References llvm::Depth.

getAddExpr() [3/3]

const SCEV* llvm::ScalarEvolution::getAddExpr ( const SCEV *  Op0, const SCEV *  Op1, const SCEV *  Op2, SCEV::NoWrapFlags  Flags = SCEV::FlagAnyWrap, unsigned  Depth = 0  )

inline

Definition at line 555 of file ScalarEvolution.h.

References llvm::Depth, and llvm::SCEV::FlagAnyWrap.

getAddRecExpr() [1/3]

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 3392 of file ScalarEvolution.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::SCEV::FlagNW, Operands, and llvm::SmallVectorTemplateBase< T >::push_back().

Referenced by DoInitialMatch(), ExposePointerBase(), ExtractImmediate(), ExtractSymbol(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), llvm::SCEVAddRecExpr::getPostIncExpr(), llvm::SCEVAddRecExpr::getStepRecurrence(), getWrapPredicate(), hasHugeExpression(), and llvm::SCEVRewriteVisitor< SCEVLoopAddRecRewriter >::visitAddRecExpr().

getAddRecExpr() [2/3]

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 3410 of file ScalarEvolution.cpp.

References llvm::all_of(), assert(), llvm::SmallVectorTemplateCommon< T >::back(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::numbers::e, llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNW, llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), llvm::SCEVCastExpr::getType(), llvm::SCEVCastExpr::Op, llvm::SmallVectorTemplateBase< T >::pop_back(), llvm::scAddRecExpr, llvm::SmallVectorBase::size(), and StrengthenNoWrapFlags().

getAddRecExpr() [3/3]

const SCEV* llvm::ScalarEvolution::getAddRecExpr ( const SmallVectorImpl< const SCEV *> &  Operands, const Loop *  L, SCEV::NoWrapFlags  Flags  )

inline

Definition at line 583 of file ScalarEvolution.h.

References llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorTemplateCommon< T >::end(), and GEP.

getAnyExtendExpr()

const SCEV * ScalarEvolution::getAnyExtendExpr	(	const SCEV *	Op,
		Type *	Ty
	)

getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the given type.

Definition at line 2197 of file ScalarEvolution.cpp.

References assert(), llvm::SCEV::FlagNW, llvm::SCEV::getType(), llvm::SmallVectorTemplateBase< T >::push_back(), and llvm::PPCISD::SC.

Referenced by mayUsePostIncMode().

getBackedgeTakenCount()

const SCEV * ScalarEvolution::getBackedgeTakenCount

(

const Loop *

L

)

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 6616 of file ScalarEvolution.cpp.

Referenced by computeTripCount(), deleteDeadInstruction(), getInductionVariable(), hasLoopInvariantBackedgeTakenCount(), llvm::ARMTTIImpl::isHardwareLoopProfitable(), llvm::IVUsers::print(), PrintLoopInfo(), and verify().

getBlockDisposition()

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 11734 of file ScalarEvolution.cpp.

References D, DoesNotDominateBlock, llvm::DominatorTree::dominates(), DominatesBlock, llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::SCEVUDivExpr::getLHS(), llvm::SCEVAddRecExpr::getLoop(), llvm::Instruction::getParent(), llvm::SCEVUDivExpr::getRHS(), llvm::SCEV::getSCEVType(), llvm::ARM_MB::LD, LLVM_FALLTHROUGH, llvm_unreachable, llvm::make_range(), llvm::SCEVNAryExpr::operands(), llvm::DominatorTreeBase< NodeT, IsPostDom >::properlyDominates(), ProperlyDominatesBlock, llvm::scAddExpr, llvm::scAddRecExpr, llvm::scConstant, llvm::scCouldNotCompute, llvm::scMulExpr, llvm::scSignExtend, llvm::scSMaxExpr, llvm::scSMinExpr, llvm::scTruncate, llvm::scUDivExpr, llvm::scUMaxExpr, llvm::scUMinExpr, llvm::scUnknown, and llvm::scZeroExtend.

Referenced by dominates(), and properlyDominates().

getConstant() [1/3]

const SCEV * ScalarEvolution::getConstant

(

ConstantInt *

V

)

Definition at line 420 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::FoldingSetNodeID::Intern(), and llvm::scConstant.

Referenced by BinomialCoefficient(), llvm::cannotBeMaxInLoop(), llvm::cannotBeMinInLoop(), llvm::IndexedReference::computeRefCost(), countToEliminateCompares(), createFFSIntrinsic(), DoInitialMatch(), EvaluateConstantChrecAtConstant(), ExposePointerBase(), ExtractImmediate(), ExtractSymbol(), FactorOutConstant(), getExactSDiv(), getNumBytes(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), getSignedOverflowLimitForStep(), getUnsignedOverflowLimitForStep(), hasHugeExpression(), llvm::RuntimePointerChecking::insert(), llvm::isConsecutiveAccess(), llvm::InductionDescriptor::isInductionPHI(), isSafeDependenceDistance(), mayUsePostIncMode(), SimplifyAddOperands(), SolveLinEquationWithOverflow(), llvm::UnrolledInstAnalyzer::UnrolledInstAnalyzer(), llvm::UnrollRuntimeLoopRemainder(), and verify().

getConstant() [2/3]

const SCEV * ScalarEvolution::getConstant

(

const APInt &

Val

)

Definition at line 431 of file ScalarEvolution.cpp.

References llvm::ConstantInt::get().

getConstant() [3/3]

const SCEV * ScalarEvolution::getConstant	(	Type *	Ty,
		uint64_t	V,
		bool	isSigned = false
	)

Definition at line 436 of file ScalarEvolution.cpp.

References llvm::ConstantInt::get().

getConstantMaxBackedgeTakenCount()

const SCEV * ScalarEvolution::getConstantMaxBackedgeTakenCount

(

const Loop *

L

)

When successful, this returns a SCEVConstant that is greater than or equal to (i.e.

Similar to getBackedgeTakenCount, except return the least SCEV value that is known never to be less than the actual backedge taken count.

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 6622 of file ScalarEvolution.cpp.

Referenced by deleteLoopIfDead(), getMaxBackedgeTakenCount(), mustBeFiniteCountedLoop(), and PrintLoopInfo().

getContext()

LLVMContext& llvm::ScalarEvolution::getContext ( ) const

inline

Definition at line 508 of file ScalarEvolution.h.

References llvm::Depth, llvm::SCEV::FlagAnyWrap, llvm::Function::getContext(), and llvm::getWiderType().

Referenced by BinomialCoefficient(), createFFSIntrinsic(), FactorOutConstant(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), isAddRecSExtable(), isAddSExtable(), isMulSExtable(), llvm::SCEVExpander::setChainedPhi(), SolveQuadraticAddRecExact(), and SolveQuadraticAddRecRange().

getCouldNotCompute()

const SCEV * ScalarEvolution::getCouldNotCompute

(

)

Definition at line 3798 of file ScalarEvolution.cpp.

References llvm::dyn_cast(), llvm::SCEVUnknown::getValue(), and llvm::SCEVExprContains().

Referenced by BinomialCoefficient(), createFFSIntrinsic(), forgetValue(), getInductionVariable(), getMaxBackedgeTakenCount(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), mustBeFiniteCountedLoop(), PushDefUseChildren(), SolveLinEquationWithOverflow(), and verify().

getDataLayout()

const DataLayout& llvm::ScalarEvolution::getDataLayout ( ) const

inline

Return the DataLayout associated with the module this SCEV instance is operating on.

Definition at line 1085 of file ScalarEvolution.h.

References A, llvm::Module::getDataLayout(), and llvm::GlobalValue::getParent().

Referenced by llvm::simplifyLoopIVs().

getEffectiveSCEVType()

Type * ScalarEvolution::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.

For pointer types, this is the pointer-sized integer type.

Definition at line 3783 of file ScalarEvolution.cpp.

References assert(), llvm::Type::isIntegerTy(), and llvm::Type::isPointerTy().

Referenced by llvm::SCEVAAResult::alias(), canBeCheaplyTransformed(), canFoldIVIncExpr(), DoInitialMatch(), genLoopLimit(), isExistingPhi(), mayUsePostIncMode(), and visitIVCast().

getElementSize()

const SCEV * ScalarEvolution::getElementSize

(

Instruction *

Inst

)

Return the size of an element read or written by Inst.

Definition at line 11117 of file ScalarEvolution.cpp.

References llvm::PointerType::getUnqual(), llvm::SPII::Load, llvm::SPII::Store, and llvm::SCEVCastExpr::Ty.

Referenced by llvm::IndexedReference::computeRefCost().

getEqualPredicate()

const SCEVPredicate * ScalarEvolution::getEqualPredicate	(	const SCEV *	LHS,
		const SCEV *	RHS
	)

Definition at line 12047 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), assert(), llvm::SCEV::getType(), llvm::FoldingSetNodeID::Intern(), and llvm::SCEVPredicate::P_Equal.

Referenced by llvm::replaceSymbolicStrideSCEV().

getExitCount()

const SCEV * ScalarEvolution::getExitCount	(	const Loop *	L,
		BasicBlock *	ExitingBlock
	)

Return the number of times the backedge executes before the given exit would be taken; if not exactly computable, return SCEVCouldNotCompute.

Get the expression for the number of loop iterations for which this loop is guaranteed not to exit via ExitingBlock.

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.

Otherwise return SCEVCouldNotCompute.

Definition at line 6605 of file ScalarEvolution.cpp.

Referenced by createFFSIntrinsic(), getMaxBackedgeTakenCount(), llvm::hasIterationCountInvariantInParent(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), mustBeFiniteCountedLoop(), PrintLoopInfo(), and llvm::UnrollRuntimeLoopRemainder().

getGEPExpr()

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 3486 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::numbers::e, llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::ArrayType::get(), llvm::GEPOperator::getPointerOperand(), llvm::GEPOperator::getSourceElementType(), llvm::SCEV::getType(), llvm::ConstantInt::getZExtValue(), llvm::GEPOperator::isInBounds(), and llvm::ArrayRef< T >::size().

getLoopDisposition()

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 11627 of file ScalarEvolution.cpp.

References assert(), llvm::LoopBase< BlockT, LoopT >::contains(), D, llvm::DominatorTree::dominates(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::SCEVUDivExpr::getLHS(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVUDivExpr::getRHS(), llvm::SCEV::getSCEVType(), isLoopInvariant(), llvm::ARM_MB::LD, llvm_unreachable, LoopComputable, LoopInvariant, LoopVariant, llvm::make_range(), llvm::SCEVNAryExpr::operands(), llvm::scAddExpr, llvm::scAddRecExpr, llvm::scConstant, llvm::scCouldNotCompute, llvm::scMulExpr, llvm::scSignExtend, llvm::scSMaxExpr, llvm::scSMinExpr, llvm::scTruncate, llvm::scUDivExpr, llvm::scUMaxExpr, llvm::scUMinExpr, llvm::scUnknown, and llvm::scZeroExtend.

Referenced by hasComputableLoopEvolution(), llvm::hasIterationCountInvariantInParent(), isLoopInvariant(), and print().

getMinMaxExpr()

const SCEV * ScalarEvolution::getMinMaxExpr	(	unsigned	Kind,
		SmallVectorImpl< const SCEV *> &	Operands
	)

Definition at line 3549 of file ScalarEvolution.cpp.

References llvm::SmallVectorImpl< T >::append(), assert(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::numbers::e, llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::SmallVectorImpl< T >::erase(), llvm::ConstantInt::get(), llvm::SCEV::getSCEVType(), llvm::SCEVCastExpr::getType(), GroupByComplexity(), llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_ULE, llvm::FoldingSetNodeID::Intern(), llvm_unreachable, llvm::RISCVFenceField::O, llvm::SCEVNAryExpr::op_begin(), llvm::SCEVNAryExpr::op_end(), llvm::scSMaxExpr, llvm::scSMinExpr, llvm::scUMaxExpr, llvm::scUMinExpr, llvm::SmallVectorBase::size(), llvm::APIntOps::smax(), llvm::APIntOps::smin(), llvm::APIntOps::umax(), and llvm::APIntOps::umin().

GetMinTrailingZeros()

uint32_t ScalarEvolution::GetMinTrailingZeros

(

const SCEV *

S

)

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 5513 of file ScalarEvolution.cpp.

References assert().

Referenced by extractConstantWithoutWrapping(), and SolveLinEquationWithOverflow().

getMinusSCEV()

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.

Definition at line 4004 of file ScalarEvolution.cpp.

References llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::getType(), and llvm::isKnownNonNegative().

Referenced by llvm::LoopAccessInfo::addRuntimeChecks(), llvm::SCEVAAResult::alias(), BinomialCoefficient(), canFoldIVIncExpr(), llvm::IndexedReference::computeRefCost(), getExprBase(), getMinFromExprs(), getNewAlignment(), hasHugeExpression(), llvm::IndexedReference::hasSpacialReuse(), llvm::isConsecutiveAccess(), isProfitableChain(), isSafeDependenceDistance(), PushDefUseChildren(), llvm::IRCEPass::run(), llvm::sortPtrAccesses(), tryToVectorizeHorReductionOrInstOperands(), verify(), and willNotOverflow().

getMulExpr() [1/3]

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 2907 of file ScalarEvolution.cpp.

References llvm::MCID::Add, llvm::SmallVectorImpl< T >::append(), assert(), llvm::SmallVectorTemplateCommon< T >::begin(), Choose(), containsConstantInAddMulChain(), llvm::dyn_cast(), llvm::numbers::e, llvm::SmallVectorBase::empty(), llvm::SmallVectorImpl< T >::erase(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, llvm::ConstantInt::get(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), llvm::SCEVCastExpr::getType(), llvm::SCEVNAryExpr::getType(), GroupByComplexity(), hasHugeExpression(), llvm::SCEV::isAllOnesValue(), isHugeExpression(), llvm::max(), MaxAddRecSize, MaxArithDepth, MulOpsInlineThreshold, Operands, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SmallVectorImpl< T >::reserve(), llvm::scAddRecExpr, llvm::scMulExpr, llvm::SmallVectorBase::size(), StrengthenNoWrapFlags(), llvm::SCEVCastExpr::Ty, and umul_ov().

Referenced by BinomialCoefficient(), CollectAddOperandsWithScales(), CollectSubexprs(), llvm::IndexedReference::computeRefCost(), containsUndefs(), createFFSIntrinsic(), DoInitialMatch(), llvm::SCEVAddRecExpr::evaluateAtIteration(), FactorOutConstant(), findArrayDimensionsRec(), getExactSDiv(), getNumBytes(), hasHugeExpression(), isSafeDependenceDistance(), mayUsePostIncMode(), removeConstantFactors(), SolveLinEquationWithOverflow(), llvm::SCEVRewriteVisitor< SCEVLoopAddRecRewriter >::visitMulExpr(), and willNotOverflow().

getMulExpr() [2/3]

const SCEV* llvm::ScalarEvolution::getMulExpr ( const SCEV *  LHS, const SCEV *  RHS, SCEV::NoWrapFlags  Flags = SCEV::FlagAnyWrap, unsigned  Depth = 0  )

inline

Definition at line 564 of file ScalarEvolution.h.

References llvm::Depth.

getMulExpr() [3/3]

const SCEV* llvm::ScalarEvolution::getMulExpr ( const SCEV *  Op0, const SCEV *  Op1, const SCEV *  Op2, SCEV::NoWrapFlags  Flags = SCEV::FlagAnyWrap, unsigned  Depth = 0  )

inline

Definition at line 570 of file ScalarEvolution.h.

References llvm::Depth.

getNegativeSCEV()

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 3946 of file ScalarEvolution.cpp.

References llvm::Constant::getAllOnesValue(), llvm::ConstantExpr::getNeg(), llvm::SCEV::getType(), llvm::SCEVCastExpr::Ty, and llvm::AArch64CC::VC.

Referenced by canBeCheaplyTransformed(), getNumBytes(), and isSafeDependenceDistance().

getNoopOrAnyExtend()

const SCEV * ScalarEvolution::getNoopOrAnyExtend	(	const SCEV *	V,
		Type *	Ty
	)

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 4092 of file ScalarEvolution.cpp.

References assert(), llvm::SCEV::getType(), and llvm::Type::isIntOrPtrTy().

getNoopOrSignExtend()

const SCEV * ScalarEvolution::getNoopOrSignExtend	(	const SCEV *	V,
		Type *	Ty
	)

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 4080 of file ScalarEvolution.cpp.

References assert(), llvm::SCEV::getType(), and llvm::Type::isIntOrPtrTy().

Referenced by llvm::LoopAccessInfo::addRuntimeChecks(), canFoldIVIncExpr(), getNewAlignment(), isSafeDependenceDistance(), and NoopOrExtend().

getNoopOrZeroExtend()

const SCEV * ScalarEvolution::getNoopOrZeroExtend	(	const SCEV *	V,
		Type *	Ty
	)

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 4068 of file ScalarEvolution.cpp.

References assert(), llvm::SCEV::getType(), and llvm::Type::isIntOrPtrTy().

Referenced by createFFSIntrinsic(), and NoopOrExtend().

getNotSCEV()

const SCEV * ScalarEvolution::getNotSCEV

(

const SCEV *

V

)

Return the SCEV object corresponding to ~V.

Return a SCEV corresponding to ~V = -1-V.

Definition at line 3974 of file ScalarEvolution.cpp.

References llvm::Constant::getAllOnesValue(), llvm::ConstantExpr::getNot(), llvm::SCEV::getType(), MatchNotExpr(), llvm::SCEVMinMaxExpr::negate(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SCEVCastExpr::Ty, and llvm::AArch64CC::VC.

getOffsetOfExpr()

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 3726 of file ScalarEvolution.cpp.

getOne()

const SCEV* llvm::ScalarEvolution::getOne ( Type *  Ty )

inline

Return a SCEV for the constant 1 of a specific type.

Definition at line 620 of file ScalarEvolution.h.

References llvm::Depth, and llvm::SCEV::FlagAnyWrap.

Referenced by computeTripCount(), createFFSIntrinsic(), expandBounds(), genLoopLimit(), getNumBytes(), hasHugeExpression(), llvm::ARMTTIImpl::isHardwareLoopProfitable(), and llvm::replaceSymbolicStrideSCEV().

getPointerBase()

const SCEV * ScalarEvolution::getPointerBase

(

const SCEV *

V

)

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 4158 of file ScalarEvolution.cpp.

References llvm::SCEV::getType(), and llvm::Type::isPointerTy().

Referenced by llvm::IndexedReference::computeRefCost().

getPredicatedBackedgeTakenCount()

const SCEV * ScalarEvolution::getPredicatedBackedgeTakenCount	(	const Loop *	L,
		SCEVUnionPredicate &	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 6611 of file ScalarEvolution.cpp.

Referenced by llvm::PredicatedScalarEvolution::getBackedgeTakenCount(), and PrintLoopInfo().

getSCEV()

const SCEV * ScalarEvolution::getSCEV

(

Value *

V

)

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 3899 of file ScalarEvolution.cpp.

References assert(), llvm::Value::getType(), I, SCEVLostPoisonFlags(), and splitAddExpr().

Referenced by llvm::SCEVAAResult::alias(), canFoldIVIncExpr(), llvm::IndexedReference::computeRefCost(), countToEliminateCompares(), DoInitialMatch(), expandBounds(), findIVOperand(), genLoopLimit(), llvm::PredicatedScalarEvolution::getAsAddRec(), llvm::Loop::LoopBounds::getBounds(), getBoundsCheckCond(), getExprBase(), getFalkorUnrollingPreferences(), getInductionVariable(), getMemSetPatternValue(), getNewAlignment(), llvm::PredicatedScalarEvolution::getSCEV(), llvm::getStrideFromPointer(), llvm::isConsecutiveAccess(), llvm::isDereferenceableAndAlignedInLoop(), isExistingPhi(), isHighCostExpansion(), llvm::InductionDescriptor::isInductionPHI(), isLoopCounter(), isProfitableChain(), isSimpleIVUser(), llvm::LoopAccessInfo::isUniform(), mayUsePostIncMode(), print(), llvm::PredicatedScalarEvolution::print(), PushDefUseChildren(), llvm::replaceSymbolicStrideSCEV(), llvm::IRCEPass::run(), llvm::sortPtrAccesses(), llvm::stripGetElementPtr(), and tryToVectorizeHorReductionOrInstOperands().

getSCEVAtScope() [1/2]

const SCEV * ScalarEvolution::getSCEVAtScope	(	const SCEV *	S,
		const Loop *	L
	)

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 8007 of file ScalarEvolution.cpp.

References C, llvm::AArch64CC::LS, and llvm::reverse().

Referenced by llvm::IndexedReference::computeRefCost(), computeUnrollAndJamCount(), createFFSIntrinsic(), isInteresting(), and print().

getSCEVAtScope() [2/2]

const SCEV * ScalarEvolution::getSCEVAtScope	(	Value *	V,
		const Loop *	L
	)

This is a convenience function which does getSCEVAtScope(getSCEV(V), L).

Definition at line 8356 of file ScalarEvolution.cpp.

getSignedRange()

ConstantRange llvm::ScalarEvolution::getSignedRange ( const SCEV *  S )

inline

Determine the signed range for a particular SCEV.

NOTE: This returns a copy of the reference returned by getRangeRef.

Definition at line 847 of file ScalarEvolution.h.

Referenced by print(), and StrengthenNoWrapFlags().

getSignedRangeMax()

APInt llvm::ScalarEvolution::getSignedRangeMax ( const SCEV *  S )

inline

Determine the max of the signed range for a particular SCEV.

Definition at line 857 of file ScalarEvolution.h.

References llvm::Depth, llvm::isKnownNegative(), llvm::isKnownNonNegative(), llvm::isKnownNonZero(), llvm::isKnownPositive(), llvm::SCEV::print(), and llvm::verify().

Referenced by getSignedOverflowLimitForStep().

getSignedRangeMin()

APInt llvm::ScalarEvolution::getSignedRangeMin ( const SCEV *  S )

inline

Determine the min of the signed range for a particular SCEV.

Definition at line 852 of file ScalarEvolution.h.

Referenced by getSignedOverflowLimitForStep().

getSignExtendExpr()

const SCEV * ScalarEvolution::getSignExtendExpr	(	const SCEV *	Op,
		Type *	Ty,
		unsigned	Depth = 0
	)

Definition at line 1944 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), assert(), C, llvm::ConstantRange::contains(), D, llvm::Depth, extractConstantWithoutWrapping(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, llvm::IntegerType::get(), llvm::ConstantExpr::getSExt(), getSignedOverflowLimitForStep(), llvm::SCEV::getType(), llvm::FoldingSetNodeID::Intern(), llvm::isKnownNonNegative(), MaxCastDepth, llvm::SCEVCastExpr::Op, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::PPCISD::SC, llvm::scSignExtend, llvm::ConstantRange::sextOrTrunc(), llvm::ConstantRange::signExtend(), llvm::ARM_MB::ST, llvm::ConstantRange::truncate(), llvm::SCEVCastExpr::Ty, and X.

Referenced by getUnsignedOverflowLimitForStep(), getWrapPredicate(), isAddRecSExtable(), isAddSExtable(), IsIncrementNSW(), isMulSExtable(), llvm::SCEVRewriteVisitor< SCEVLoopAddRecRewriter >::visitSignExtendExpr(), and willNotOverflow().

getSizeOfExpr()

const SCEV * ScalarEvolution::getSizeOfExpr	(	Type *	IntTy,
		Type *	AllocTy
	)

Return an expression for sizeof AllocTy that is type IntTy.

Definition at line 3719 of file ScalarEvolution.cpp.

Referenced by genLoopLimit().

getSmallConstantMaxTripCount()

unsigned ScalarEvolution::getSmallConstantMaxTripCount

(

const Loop *

L

)

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 6544 of file ScalarEvolution.cpp.

References llvm::dyn_cast(), and getConstantTripCount().

Referenced by getSmallBestKnownTC(), llvm::HexagonTTIImpl::getUnrollingPreferences(), and tryToUnrollLoop().

getSmallConstantTripCount() [1/2]

unsigned ScalarEvolution::getSmallConstantTripCount

(

const Loop *

L

)

Returns the maximum trip count of the loop if it is a single-exit loop and we can compute a small maximum for that loop.

Implemented in terms of the getSmallConstantTripCount overload with the single exiting block passed to it. See that routine for details.

Definition at line 6526 of file ScalarEvolution.cpp.

References llvm::LoopBase< BlockT, LoopT >::getExitingBlock().

Referenced by llvm::CacheCost::CacheCost(), llvm::LoopVectorizationCostModel::computeMaxVF(), getSmallBestKnownTC(), llvm::HexagonTTIImpl::getUnrollingPreferences(), llvm::isDereferenceableAndAlignedInLoop(), llvm::PPCTTIImpl::isHardwareLoopProfitable(), llvm::LoopVectorizationCostModel::selectInterleaveCount(), tryToUnrollAndJamLoop(), tryToUnrollLoop(), and llvm::UnrollLoop().

getSmallConstantTripCount() [2/2]

unsigned ScalarEvolution::getSmallConstantTripCount	(	const Loop *	L,
		BasicBlock *	ExitingBlock
	)

Returns the maximum trip count of this loop as a normal unsigned value.

Returns 0 if the trip count is unknown or not constant. This "trip count" assumes that control exits via ExitingBlock. More precisely, it is the number of times that control may 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 6534 of file ScalarEvolution.cpp.

References assert(), llvm::dyn_cast(), getConstantTripCount(), and llvm::LoopBase< BlockT, LoopT >::isLoopExiting().

getSmallConstantTripMultiple() [1/2]

unsigned ScalarEvolution::getSmallConstantTripMultiple

(

const Loop *

L

)

Returns the largest constant divisor of the trip count of the loop if it is a single-exit loop and we can compute a small maximum for that loop.

Implemented in terms of the getSmallConstantTripMultiple overload with the single exiting block passed to it. See that routine for details.

Definition at line 6550 of file ScalarEvolution.cpp.

References llvm::LoopBase< BlockT, LoopT >::getExitingBlock().

Referenced by PrintLoopInfo(), tryToUnrollAndJamLoop(), tryToUnrollLoop(), and llvm::UnrollLoop().

getSmallConstantTripMultiple() [2/2]

unsigned ScalarEvolution::getSmallConstantTripMultiple	(	const Loop *	L,
		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 6571 of file ScalarEvolution.cpp.

References assert(), llvm::dyn_cast(), llvm::APInt::getActiveBits(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), llvm::ConstantInt::getZExtValue(), and llvm::LoopBase< BlockT, LoopT >::isLoopExiting().

getSMaxExpr() [1/2]

const SCEV * ScalarEvolution::getSMaxExpr	(	const SCEV *	LHS,
		const SCEV *	RHS
	)

Definition at line 3681 of file ScalarEvolution.cpp.

Referenced by IntersectSignedRange(), and llvm::SCEVRewriteVisitor< SCEVLoopAddRecRewriter >::visitSMaxExpr().

getSMaxExpr() [2/2]

const SCEV * ScalarEvolution::getSMaxExpr

(

SmallVectorImpl< const SCEV *> &

Operands

)

Definition at line 3686 of file ScalarEvolution.cpp.

References llvm::scSMaxExpr.

getSMinExpr() [1/2]

const SCEV * ScalarEvolution::getSMinExpr	(	const SCEV *	LHS,
		const SCEV *	RHS
	)

Definition at line 3699 of file ScalarEvolution.cpp.

Referenced by IntersectSignedRange(), and llvm::SCEVRewriteVisitor< SCEVLoopAddRecRewriter >::visitSMinExpr().

getSMinExpr() [2/2]

const SCEV * ScalarEvolution::getSMinExpr

(

SmallVectorImpl< const SCEV *> &

Operands

)

Definition at line 3705 of file ScalarEvolution.cpp.

References llvm::scSMinExpr.

getTruncateExpr()

const SCEV * ScalarEvolution::getTruncateExpr	(	const SCEV *	Op,
		Type *	Ty,
		unsigned	Depth = 0
	)

Definition at line 1254 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), assert(), llvm::numbers::e, llvm::SCEV::FlagAnyWrap, llvm::ConstantExpr::getTrunc(), llvm::SCEV::getType(), llvm::FoldingSetNodeID::Intern(), llvm_unreachable, MaxCastDepth, llvm::SCEVCastExpr::Op, Operands, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::PPCISD::SC, llvm::scTruncate, llvm::ARM_MB::ST, and llvm::SCEVCastExpr::Ty.

Referenced by generateLoopLatchCheck(), genLoopLimit(), and llvm::SCEVRewriteVisitor< SCEVLoopAddRecRewriter >::visitTruncateExpr().

getTruncateOrNoop()

const SCEV * ScalarEvolution::getTruncateOrNoop	(	const SCEV *	V,
		Type *	Ty
	)

Return a SCEV corresponding to a conversion of the input value to the specified type.

The conversion must not be widening.

Definition at line 4104 of file ScalarEvolution.cpp.

References assert(), llvm::SCEV::getType(), and llvm::Type::isIntOrPtrTy().

Referenced by canBeCheaplyTransformed().

getTruncateOrSignExtend()

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 4055 of file ScalarEvolution.cpp.

References assert(), llvm::SCEV::getType(), and llvm::Type::isIntOrPtrTy().

getTruncateOrZeroExtend()

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 4043 of file ScalarEvolution.cpp.

References assert(), llvm::SCEV::getType(), and llvm::Type::isIntOrPtrTy().

Referenced by BinomialCoefficient(), genLoopLimit(), and getNumBytes().

getTypeSizeInBits()

uint64_t ScalarEvolution::getTypeSizeInBits

(

Type *

Ty

)

const

Return the size in bits of the specified type, for which isSCEVable must return true.

Definition at line 3773 of file ScalarEvolution.cpp.

References assert(), and llvm::Type::isPointerTy().

Referenced by llvm::SCEVAAResult::alias(), BinomialCoefficient(), canFoldIVIncExpr(), createFFSIntrinsic(), FindLoopCounter(), genLoopLimit(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), getRangeForAffineARHelper(), getSignedOverflowLimitForStep(), getUnsignedOverflowLimitForStep(), isAddRecSExtable(), isAddSExtable(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), isMulSExtable(), isSimpleCastedPHI(), mayUsePostIncMode(), SolveLinEquationWithOverflow(), SolveQuadraticAddRecRange(), verify(), and visitIVCast().

getUDivExactExpr()

const SCEV * ScalarEvolution::getUDivExactExpr	(	const SCEV *	LHS,
		const SCEV *	RHS
	)

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 3337 of file ScalarEvolution.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::dyn_cast(), llvm::numbers::e, gcd(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), llvm::SCEVNAryExpr::hasNoUnsignedWrap(), llvm::APInt::isIntN(), llvm::SCEVNAryExpr::op_begin(), llvm::SCEVNAryExpr::op_end(), Operands, and llvm::SmallVectorTemplateBase< T >::push_back().

Referenced by llvm::IndexedReference::computeRefCost(), and SolveLinEquationWithOverflow().

getUDivExpr()

const SCEV * ScalarEvolution::getUDivExpr	(	const SCEV *	LHS,
		const SCEV *	RHS
	)

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 3187 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), assert(), llvm::SmallVectorImpl< T >::clear(), llvm::dyn_cast(), llvm::numbers::e, llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNW, llvm::IntegerType::get(), llvm::SCEV::getType(), llvm::ConstantExpr::getUDiv(), llvm::FoldingSetNodeID::Intern(), llvm::SCEVCastExpr::Op, Operands, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::scUDivExpr, llvm::SmallVectorBase::size(), llvm::SCEVCastExpr::Ty, llvm::APInt::umul_ov(), and llvm::APInt::urem().

Referenced by BinomialCoefficient(), llvm::IndexedReference::computeRefCost(), and llvm::SCEVRewriteVisitor< SCEVLoopAddRecRewriter >::visitUDivExpr().

getUMaxExpr() [1/2]

const SCEV * ScalarEvolution::getUMaxExpr	(	const SCEV *	LHS,
		const SCEV *	RHS
	)

Definition at line 3690 of file ScalarEvolution.cpp.

Referenced by llvm::RuntimePointerChecking::insert(), IntersectUnsignedRange(), and llvm::SCEVRewriteVisitor< SCEVLoopAddRecRewriter >::visitUMaxExpr().

getUMaxExpr() [2/2]

const SCEV * ScalarEvolution::getUMaxExpr

(

SmallVectorImpl< const SCEV *> &

Operands

)

Definition at line 3695 of file ScalarEvolution.cpp.

References llvm::scUMaxExpr.

getUMaxFromMismatchedTypes()

const SCEV * ScalarEvolution::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.

Definition at line 4115 of file ScalarEvolution.cpp.

References llvm::SCEV::getType().

getUMinExpr() [1/2]

const SCEV * ScalarEvolution::getUMinExpr	(	const SCEV *	LHS,
		const SCEV *	RHS
	)

Definition at line 3709 of file ScalarEvolution.cpp.

Referenced by llvm::RuntimePointerChecking::insert(), IntersectUnsignedRange(), and llvm::SCEVRewriteVisitor< SCEVLoopAddRecRewriter >::visitUMinExpr().

getUMinExpr() [2/2]

const SCEV * ScalarEvolution::getUMinExpr

(

SmallVectorImpl< const SCEV *> &

Operands

)

Definition at line 3715 of file ScalarEvolution.cpp.

References llvm::scUMinExpr.

getUMinFromMismatchedTypes() [1/2]

const SCEV * ScalarEvolution::getUMinFromMismatchedTypes	(	const SCEV *	LHS,
		const SCEV *	RHS
	)

Promote the operands to the wider of the types using zero-extension, and then perform a umin operation with them.

Definition at line 4128 of file ScalarEvolution.cpp.

Referenced by forgetValue(), and getMaxBackedgeTakenCount().

getUMinFromMismatchedTypes() [2/2]

const SCEV * ScalarEvolution::getUMinFromMismatchedTypes

(

SmallVectorImpl< const SCEV *> &

Ops

)

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 4134 of file ScalarEvolution.cpp.

References assert(), llvm::SmallVectorBase::empty(), llvm::SCEV::getType(), llvm::getWiderType(), llvm::SmallVectorTemplateBase< T >::push_back(), and llvm::SmallVectorBase::size().

getUnknown()

const SCEV * ScalarEvolution::getUnknown

(

Value *

V

)

Definition at line 3736 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), assert(), llvm::FoldingSetNodeID::Intern(), and llvm::scUnknown.

Referenced by canFoldIVIncExpr(), llvm::InductionDescriptor::isFPInductionPHI(), mayUsePostIncMode(), and verify().

getUnsignedRange()

ConstantRange llvm::ScalarEvolution::getUnsignedRange ( const SCEV *  S )

inline

Determine the unsigned range for a particular SCEV.

NOTE: This returns a copy of the reference returned by getRangeRef.

Definition at line 831 of file ScalarEvolution.h.

Referenced by llvm::SCEVAAResult::alias(), getBoundsCheckCond(), mustBeFiniteCountedLoop(), print(), and StrengthenNoWrapFlags().

getUnsignedRangeMax()

APInt llvm::ScalarEvolution::getUnsignedRangeMax ( const SCEV *  S )

inline

Determine the max of the unsigned range for a particular SCEV.

Definition at line 841 of file ScalarEvolution.h.

Referenced by getUnsignedOverflowLimitForStep(), and llvm::ARMTTIImpl::isHardwareLoopProfitable().

getUnsignedRangeMin()

APInt llvm::ScalarEvolution::getUnsignedRangeMin ( const SCEV *  S )

inline

Determine the min of the unsigned range for a particular SCEV.

Definition at line 836 of file ScalarEvolution.h.

getURemExpr()

const SCEV * ScalarEvolution::getURemExpr	(	const SCEV *	LHS,
		const SCEV *	RHS
	)

Represents an unsigned remainder expression based on unsigned division.

Definition at line 3158 of file ScalarEvolution.cpp.

References assert(), llvm::SCEV::FlagNUW, llvm::IntegerType::get(), llvm::SCEV::getType(), and llvm::MipsISD::Mult.

Referenced by getNewAlignmentDiff().

getWiderType()

Type * ScalarEvolution::getWiderType	(	Type *	Ty1,
		Type *	Ty2
	)		const

Definition at line 3794 of file ScalarEvolution.cpp.

References T1.

getWrapPredicate()

const SCEVPredicate * ScalarEvolution::getWrapPredicate	(	const SCEVAddRecExpr *	AR,
		SCEVWrapPredicate::IncrementWrapFlags	AddedFlags
	)

Definition at line 12065 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), createAddRecFromPHIWithCasts(), llvm::dyn_cast(), getAddRecExpr(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVCastExpr::getOperand(), llvm::SCEVUnionPredicate::getPredicatesForExpr(), getSignExtendExpr(), llvm::SCEVCastExpr::getType(), llvm::SCEVUnknown::getValue(), getWrapPredicate(), getZeroExtendExpr(), llvm::SCEVUnionPredicate::implies(), llvm::SCEVWrapPredicate::IncrementNSSW, llvm::SCEVWrapPredicate::IncrementNUSW, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::FoldingSetNodeID::Intern(), P, llvm::SCEVPredicate::P_Wrap, rewrite(), and Rewriter.

Referenced by getWrapPredicate(), and llvm::PredicatedScalarEvolution::setNoOverflow().

getZero()

const SCEV* llvm::ScalarEvolution::getZero ( Type *  Ty )

inline

Return a SCEV for the constant 0 of a specific type.

Definition at line 617 of file ScalarEvolution.h.

Referenced by llvm::SCEVAddRecExpr::getNumIterationsInRange(), hasHugeExpression(), llvm::isKnownNegativeInLoop(), and llvm::isKnownNonNegativeInLoop().

getZeroExtendExpr()

const SCEV * ScalarEvolution::getZeroExtendExpr	(	const SCEV *	Op,
		Type *	Ty,
		unsigned	Depth = 0
	)

Definition at line 1638 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), assert(), C, llvm::ConstantRange::contains(), D, llvm::Depth, extractConstantWithoutWrapping(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, llvm::IntegerType::get(), llvm::APInt::getMaxValue(), llvm::APInt::getMinValue(), llvm::SCEV::getType(), llvm::ConstantExpr::getZExt(), llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULT, llvm::FoldingSetNodeID::Intern(), llvm::isKnownNegative(), llvm::isKnownPositive(), MaxCastDepth, N, llvm::SCEVCastExpr::Op, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::PPCISD::SC, llvm::scZeroExtend, llvm::ARM_MB::ST, llvm::ConstantRange::truncate(), llvm::SCEVCastExpr::Ty, X, llvm::ConstantRange::zeroExtend(), and llvm::ConstantRange::zextOrTrunc().

Referenced by llvm::LoopAccessInfo::addRuntimeChecks(), genLoopLimit(), getNumBytes(), getUnsignedOverflowLimitForStep(), getWrapPredicate(), IsIncrementNUW(), isSafeDependenceDistance(), verify(), llvm::SCEVRewriteVisitor< SCEVLoopAddRecRewriter >::visitZeroExtendExpr(), and willNotOverflow().

hasComputableLoopEvolution()

bool ScalarEvolution::hasComputableLoopEvolution	(	const SCEV *	S,
		const Loop *	L
	)

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 11729 of file ScalarEvolution.cpp.

References getLoopDisposition(), and LoopComputable.

Referenced by canFoldIVIncExpr(), getSetupCost(), and mayUsePostIncMode().

hasLoopInvariantBackedgeTakenCount()

bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount

(

const Loop *

L

)

Return true if the specified loop has an analyzable loop-invariant backedge-taken count.

Definition at line 11460 of file ScalarEvolution.cpp.

References getBackedgeTakenCount().

Referenced by deleteDeadInstruction(), llvm::ARMTTIImpl::isHardwareLoopProfitable(), llvm::IVUsers::print(), and PrintLoopInfo().

hasOperand()

bool ScalarEvolution::hasOperand	(	const SCEV *	S,
		const SCEV *	Op
	)		const

Test whether the given SCEV has Op as a direct or indirect operand.

Definition at line 11826 of file ScalarEvolution.cpp.

References E, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), F, llvm::SCEVAddRecExpr::getLoop(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SCEVExprContains(), llvm::visitAll(), and X.

Referenced by forgetValue().

invalidate()

bool ScalarEvolution::invalidate	(	Function &	F,
		const PreservedAnalyses &	PA,
		FunctionAnalysisManager::Invalidator &	Inv
	)

Definition at line 11974 of file ScalarEvolution.cpp.

References llvm::PreservedAnalyses::getChecker(), and llvm::AnalysisManager< IRUnitT, ExtraArgTs >::Invalidator::invalidate().

isAvailableAtLoopEntry()

bool ScalarEvolution::isAvailableAtLoopEntry	(	const SCEV *	S,
		const Loop *	L
	)

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 2401 of file ScalarEvolution.cpp.

References llvm::LoopBase< BlockT, LoopT >::getHeader().

Referenced by llvm::cannotBeMaxInLoop(), llvm::cannotBeMinInLoop(), createFFSIntrinsic(), llvm::isKnownNegativeInLoop(), and llvm::isKnownNonNegativeInLoop().

isBackedgeTakenCountMaxOrZero()

bool ScalarEvolution::isBackedgeTakenCountMaxOrZero

(

const Loop *

L

)

Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCount or zero.

Definition at line 6626 of file ScalarEvolution.cpp.

Referenced by PrintLoopInfo(), and tryToUnrollLoop().

isKnownNegative()

bool ScalarEvolution::isKnownNegative

(

const SCEV *

S

)

Test if the given expression is known to be negative.

Definition at line 9074 of file ScalarEvolution.cpp.

Referenced by getSignedOverflowLimitForStep().

isKnownNonNegative()

bool ScalarEvolution::isKnownNonNegative

(

const SCEV *

S

)

Test if the given expression is known to be non-negative.

Definition at line 9082 of file ScalarEvolution.cpp.

Referenced by StrengthenNoWrapFlags().

isKnownNonPositive()

bool ScalarEvolution::isKnownNonPositive

(

const SCEV *

S

)

Test if the given expression is known to be non-positive.

Definition at line 9086 of file ScalarEvolution.cpp.

isKnownNonZero()

bool ScalarEvolution::isKnownNonZero

(

const SCEV *

S

)

Test if the given expression is known to be non-zero.

Definition at line 9090 of file ScalarEvolution.cpp.

References llvm::isKnownNegative(), and llvm::isKnownPositive().

isKnownOnEveryIteration()

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 9170 of file ScalarEvolution.cpp.

References llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVAddRecExpr::getPostIncExpr(), and llvm::SCEVAddRecExpr::getStart().

isKnownPositive()

bool ScalarEvolution::isKnownPositive

(

const SCEV *

S

)

Test if the given expression is known to be positive.

Definition at line 9078 of file ScalarEvolution.cpp.

Referenced by llvm::LoopAccessInfo::addRuntimeChecks(), getSignedOverflowLimitForStep(), and isSafeDependenceDistance().

isKnownPredicate()

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 9155 of file ScalarEvolution.cpp.

Referenced by llvm::IndexedReference::computeRefCost(), countToEliminateCompares(), IsKnownPredicateViaAddRecStart(), and normalizePredicate().

isKnownViaInduction()

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:

1. Collect set S all loops on which either LHS or RHS depend.
2. If S is non-empty a. Let PD be the element of S which is dominated by all other elements. b. Let E(LHS) be value of LHS on entry of PD. To get E(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their entry values. Define E(RHS) in the same way. c. Let B(LHS) be value of L on backedge of PD. To get B(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their backedge values. Define B(RHS) in the same way. d. Note that E(LHS) and E(RHS) are automatically available on entry of PD, so we can assert on that. e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) && isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))

Definition at line 9106 of file ScalarEvolution.cpp.

References assert(), llvm::SmallPtrSetImplBase::empty(), and llvm::LoopBase< BlockT, LoopT >::getHeader().

isLoopBackedgeGuardedByCond()

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 9435 of file ScalarEvolution.cpp.

References assert(), llvm::dbgs(), llvm::dyn_cast(), llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, llvm::BranchInst::getCondition(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::DomTreeNodeBase< NodeT >::getIDom(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::SCEV::getType(), llvm::CmpInst::ICMP_ULT, llvm::BranchInst::isConditional(), llvm::BasicBlockEdge::isSingleEdge(), llvm::SCEVCastExpr::Ty, llvm::verifyFunction(), and VerifyIR.

isLoopEntryGuardedByCond()

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 9545 of file ScalarEvolution.cpp.

References assert(), C, llvm::dbgs(), llvm::Depth, llvm::dyn_cast(), llvm::SCEVConstant::getAPInt(), llvm::BranchInst::getCondition(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::CmpInst::getInversePredicate(), llvm::SCEVAddRecExpr::getLoop(), llvm::LoopBase< BlockT, LoopT >::getLoopPredecessor(), llvm::CmpInst::getNonStrictPredicate(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::SCEVAddRecExpr::getPostIncExpr(), llvm::APInt::getSignedMinValue(), llvm::CmpInst::getSignedPredicate(), llvm::SCEVAddRecExpr::getStart(), llvm::BranchInst::getSuccessor(), llvm::CmpInst::getSwappedPredicate(), llvm::SCEV::getType(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULT, llvm::CmpInst::isFalseWhenEqual(), isImpliedCondOperands(), llvm::isKnownNonNegative(), llvm::APInt::isMinValue(), llvm::CmpInst::isSigned(), llvm::CmpInst::isTrueWhenEqual(), llvm::BranchInst::isUnconditional(), llvm::CmpInst::isUnsigned(), llvm::CodeGenOpt::Less, LLVM_FALLTHROUGH, llvm::make_scope_exit(), llvm::None, llvm::predecessors(), std::swap(), llvm::verifyFunction(), and VerifyIR.

Referenced by llvm::cannotBeMaxInLoop(), llvm::cannotBeMinInLoop(), getNumBytes(), llvm::isKnownNegativeInLoop(), and llvm::isKnownNonNegativeInLoop().

isLoopInvariant()

bool ScalarEvolution::isLoopInvariant	(	const SCEV *	S,
		const Loop *	L
	)

Return true if the value of the given SCEV is unchanging in the specified loop.

Definition at line 11725 of file ScalarEvolution.cpp.

References getLoopDisposition(), and LoopInvariant.

Referenced by canFoldIVIncExpr(), llvm::IndexedReference::computeRefCost(), computeUnrollAndJamCount(), expandBounds(), genLoopLimit(), getLoopDisposition(), getSetupCost(), hasComputableBounds(), llvm::RuntimePointerChecking::insert(), llvm::Loop::isAuxiliaryInductionVariable(), llvm::isDereferenceableAndAlignedInLoop(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), llvm::InductionDescriptor::isInductionPHI(), isNoWrap(), isProfitableChain(), llvm::LoopAccessInfo::isUniform(), mayUsePostIncMode(), print(), PushDefUseChildren(), llvm::stripGetElementPtr(), llvm::InnerLoopVectorizer::widenInstruction(), and llvm::InnerLoopVectorizer::widenIntOrFpInduction().

isLoopInvariantPredicate()

bool ScalarEvolution::isLoopInvariantPredicate	(	ICmpInst::Predicate	Pred,
		const SCEV *	LHS,
		const SCEV *	RHS,
		const Loop *	L,
		ICmpInst::Predicate &	InvariantPred,
		const SCEV *&	InvariantLHS,
		const SCEV *&	InvariantRHS
	)

Return true if the result of the predicate LHS Pred RHS is loop invariant with respect to L.

Set InvariantPred, InvariantLHS and InvariantLHS so that InvariantLHS InvariantPred InvariantRHS is the loop invariant form of LHS Pred RHS.

Definition at line 9254 of file ScalarEvolution.cpp.

References llvm::any_of(), C, llvm::ConstantRange::contains(), llvm::dyn_cast(), llvm::SCEV::FlagNSW, llvm::CmpInst::getInversePredicate(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVAddRecExpr::getStart(), llvm::CmpInst::getSwappedPredicate(), llvm::SCEV::getType(), 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_ULT, llvm::isKnownNonNegative(), llvm::isKnownNonZero(), llvm::APInt::isNegative(), llvm::APInt::isNonNegative(), llvm::CmpInst::isSigned(), llvm::APInt::isStrictlyPositive(), llvm::CmpInst::isTrueWhenEqual(), LLVM_FALLTHROUGH, llvm::PatternMatch::m_Value(), llvm::ConstantRange::makeSatisfyingICmpRegion(), llvm::PatternMatch::match(), P, std::swap(), and X.

isMonotonicPredicate()

bool ScalarEvolution::isMonotonicPredicate	(	const SCEVAddRecExpr *	LHS,
		ICmpInst::Predicate	Pred,
		bool &	Increasing
	)

Return true if, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing.

In the former case set Increasing to true and in the latter case set Increasing to false.

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.

Definition at line 9178 of file ScalarEvolution.cpp.

References assert(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::CmpInst::getSwappedPredicate(), llvm::SCEVNAryExpr::hasNoSignedWrap(), llvm::SCEVNAryExpr::hasNoUnsignedWrap(), 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::isKnownNonNegative(), and llvm_unreachable.

Referenced by countToEliminateCompares().

isSCEVable()

bool ScalarEvolution::isSCEVable

(

Type *

Ty

)

const

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 3766 of file ScalarEvolution.cpp.

References llvm::Type::isIntOrPtrTy().

Referenced by canFoldIVIncExpr(), llvm::IndexedReference::computeRefCost(), findIVOperand(), isExistingPhi(), isHighCostExpansion(), isLoopCounter(), isProfitableChain(), isSimpleIVUser(), llvm::LoopAccessInfo::isUniform(), print(), llvm::PredicatedScalarEvolution::print(), and llvm::InnerLoopVectorizer::widenIntOrFpInduction().

maskFlags()

static LLVM_NODISCARD SCEV::NoWrapFlags llvm::ScalarEvolution::maskFlags ( SCEV::NoWrapFlags  Flags, int  Mask  )

inlinestatic

Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name space.

Definition at line 490 of file ScalarEvolution.h.

References llvm::BitmaskEnumDetail::Mask().

Referenced by StrengthenNoWrapFlags().

print()

void ScalarEvolution::print

(

raw_ostream &

OS

)

const

Definition at line 11538 of file ScalarEvolution.cpp.

References llvm::depth_first(), getLoopDisposition(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), getSCEV(), getSCEVAtScope(), getSignedRange(), llvm::Value::getType(), getUnsignedRange(), llvm::instructions(), isLoopInvariant(), isSCEVable(), loopDispositionToStr(), llvm::SCEV::print(), llvm::ConstantRange::print(), llvm::Value::printAsOperand(), and PrintLoopInfo().

Referenced by llvm::ScalarEvolutionPrinterPass::run().

properlyDominates()

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 11822 of file ScalarEvolution.cpp.

References getBlockDisposition(), and ProperlyDominatesBlock.

Referenced by DoInitialMatch(), llvm::isSafeToExpandAt(), and mayUsePostIncMode().

rewriteUsingPredicate()

const SCEV * ScalarEvolution::rewriteUsingPredicate	(	const SCEV *	S,
		const Loop *	L,
		SCEVUnionPredicate &	A
	)

Re-writes the SCEV according to the Predicates in A.

Definition at line 12199 of file ScalarEvolution.cpp.

References rewrite().

Referenced by llvm::PredicatedScalarEvolution::getSCEV(), and llvm::PredicatedScalarEvolution::getUnionPredicate().

setFlags()

static LLVM_NODISCARD SCEV::NoWrapFlags llvm::ScalarEvolution::setFlags ( SCEV::NoWrapFlags  Flags, SCEV::NoWrapFlags  OnFlags  )

inlinestatic

Definition at line 494 of file ScalarEvolution.h.

References LLVM_NODISCARD.

Referenced by llvm::SCEVWrapPredicate::getImpliedFlags(), getRangeForAffineARHelper(), llvm::SCEVWrapPredicate::isAlwaysTrue(), PushDefUseChildren(), llvm::SCEVAddRecExpr::setNoWrapFlags(), and StrengthenNoWrapFlags().

SimplifyICmpOperands()

bool ScalarEvolution::SimplifyICmpOperands	(	ICmpInst::Predicate &	Pred,
		const SCEV *&	LHS,
		const SCEV *&	RHS,
		unsigned	Depth = 0
	)

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.

Definition at line 8877 of file ScalarEvolution.cpp.

References assert(), llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::ConstantRange::getEquivalentICmp(), llvm::ConstantInt::getFalse(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::ConstantExpr::getICmp(), llvm::SCEVAddRecExpr::getLoop(), llvm::CmpInst::getSwappedPredicate(), llvm::SCEV::getType(), 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(), llvm::APInt::isMaxSignedValue(), llvm::APInt::isMaxValue(), llvm::APInt::isMinSignedValue(), llvm::APInt::isMinValue(), llvm::CmpInst::isTrueWhenEqual(), llvm::ConstantRange::makeExactICmpRegion(), RA, and std::swap().

SplitIntoInitAndPostInc()

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 9095 of file ScalarEvolution.cpp.

References rewrite().

verify()

void ScalarEvolution::verify

(

)

const

Definition at line 11901 of file ScalarEvolution.cpp.

References llvm::LoopBase< BlockT, LoopT >::begin(), containsUndefs(), llvm::dbgs(), llvm::LoopBase< BlockT, LoopT >::end(), F, llvm::SCEVConstant::getAPInt(), getBackedgeTakenCount(), getConstant(), getCouldNotCompute(), getMinusSCEV(), getTypeSizeInBits(), getUnknown(), llvm::SCEVUnknown::getValue(), getZeroExtendExpr(), llvm::SCEV::isZero(), and VerifySCEVStrict.

Friends And Related Function Documentation

ScalarEvolutionsTest

friend class ScalarEvolutionsTest

friend

Definition at line 471 of file ScalarEvolution.h.

SCEVCallbackVH

friend class SCEVCallbackVH

friend

Definition at line 1117 of file ScalarEvolution.h.

SCEVExpander

friend class SCEVExpander

friend

Definition at line 1118 of file ScalarEvolution.h.

SCEVUnknown

friend class SCEVUnknown

friend

Definition at line 1119 of file ScalarEvolution.h.

---

The documentation for this class was generated from the following files:

• include/llvm/Analysis/ScalarEvolution.h
• lib/Analysis/ScalarEvolution.cpp