#include <ScalarEvolution.h>

Inheritance diagram for llvm::ScalarEvolution:

Collaboration diagram for llvm::ScalarEvolution:

Classes
class	BackedgeTakenInfo
struct	ExitLimit
struct	ExitNotTakenInfo
class	SCEVCallbackVH
Public Types
enum	LoopDisposition { LoopVariant, LoopInvariant, LoopComputable }
enum	BlockDisposition { DoesNotDominateBlock, DominatesBlock, ProperlyDominatesBlock }
Public Member Functions
	ScalarEvolution ()
LLVMContext &	getContext () const
bool	isSCEVable (Type *Ty) const
uint64_t	getTypeSizeInBits (Type *Ty) const
Type *	getEffectiveSCEVType (Type *Ty) const
const SCEV *	getSCEV (Value *V)
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)
const SCEV *	getZeroExtendExpr (const SCEV Op, Type Ty)
const SCEV *	getSignExtendExpr (const SCEV Op, Type Ty)
const SCEV *	getAnyExtendExpr (const SCEV Op, Type Ty)
const SCEV *	getAddExpr (SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
const SCEV *	getAddExpr (const SCEV LHS, const SCEV RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
const SCEV *	getAddExpr (const SCEV Op0, const SCEV Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
const SCEV *	getMulExpr (SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
const SCEV *	getMulExpr (const SCEV LHS, const SCEV RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
const SCEV *	getMulExpr (const SCEV Op0, const SCEV Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
const SCEV *	getUDivExpr (const SCEV LHS, const SCEV RHS)
const SCEV *	getUDivExactExpr (const SCEV LHS, const SCEV RHS)
const SCEV *	getAddRecExpr (const SCEV Start, const SCEV Step, const Loop *L, SCEV::NoWrapFlags Flags)
const SCEV *	getAddRecExpr (SmallVectorImpl< const SCEV * > &Operands, const Loop *L, SCEV::NoWrapFlags Flags)
const SCEV *	getAddRecExpr (const SmallVectorImpl< const SCEV * > &Operands, const Loop *L, SCEV::NoWrapFlags Flags)
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 *	getUMinExpr (const SCEV LHS, const SCEV RHS)
const SCEV *	getUnknown (Value *V)
const SCEV *	getCouldNotCompute ()
const SCEV *	getSizeOfExpr (Type IntTy, Type AllocTy)
const SCEV *	getOffsetOfExpr (Type IntTy, StructType STy, unsigned FieldNo)
const SCEV *	getNegativeSCEV (const SCEV *V)
const SCEV *	getNotSCEV (const SCEV *V)
	getNotSCEV - Return a SCEV corresponding to ~V = -1-V
const SCEV *	getMinusSCEV (const SCEV LHS, const SCEV RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
	getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
const SCEV *	getTruncateOrZeroExtend (const SCEV V, Type Ty)
const SCEV *	getTruncateOrSignExtend (const SCEV V, Type Ty)
const SCEV *	getNoopOrZeroExtend (const SCEV V, Type Ty)
const SCEV *	getNoopOrSignExtend (const SCEV V, Type Ty)
const SCEV *	getNoopOrAnyExtend (const SCEV V, Type Ty)
const SCEV *	getTruncateOrNoop (const SCEV V, Type Ty)
const SCEV *	getUMaxFromMismatchedTypes (const SCEV LHS, const SCEV RHS)
const SCEV *	getUMinFromMismatchedTypes (const SCEV LHS, const SCEV RHS)
const SCEV *	getPointerBase (const SCEV *V)
const SCEV *	getSCEVAtScope (const SCEV S, const Loop L)
const SCEV *	getSCEVAtScope (Value V, const Loop L)
bool	isLoopEntryGuardedByCond (const Loop L, ICmpInst::Predicate Pred, const SCEV LHS, const SCEV *RHS)
bool	isLoopBackedgeGuardedByCond (const Loop L, ICmpInst::Predicate Pred, const SCEV LHS, const SCEV *RHS)
unsigned	getSmallConstantTripCount (Loop L, BasicBlock ExitingBlock)
unsigned	getSmallConstantTripMultiple (Loop L, BasicBlock ExitingBlock)
const SCEV *	getExitCount (Loop L, BasicBlock ExitingBlock)
const SCEV *	getBackedgeTakenCount (const Loop *L)
const SCEV *	getMaxBackedgeTakenCount (const Loop *L)
bool	hasLoopInvariantBackedgeTakenCount (const Loop *L)
void	forgetLoop (const Loop *L)
void	forgetValue (Value *V)
void	forgetLoopDispositions (const Loop *L)
	Called when the client has changed the disposition of values in this loop.
uint32_t	GetMinTrailingZeros (const SCEV *S)
ConstantRange	getUnsignedRange (const SCEV *S)
ConstantRange	getSignedRange (const SCEV *S)
bool	isKnownNegative (const SCEV *S)
bool	isKnownPositive (const SCEV *S)
bool	isKnownNonNegative (const SCEV *S)
bool	isKnownNonPositive (const SCEV *S)
bool	isKnownNonZero (const SCEV *S)
bool	isKnownPredicate (ICmpInst::Predicate Pred, const SCEV LHS, const SCEV RHS)
bool	SimplifyICmpOperands (ICmpInst::Predicate &Pred, const SCEV &LHS, const SCEV &RHS, unsigned Depth=0)
LoopDisposition	getLoopDisposition (const SCEV S, const Loop L)
bool	isLoopInvariant (const SCEV S, const Loop L)
bool	hasComputableLoopEvolution (const SCEV S, const Loop L)
BlockDisposition	getBlockDisposition (const SCEV S, const BasicBlock BB)
bool	dominates (const SCEV S, const BasicBlock BB)
bool	properlyDominates (const SCEV S, const BasicBlock BB)
bool	hasOperand (const SCEV S, const SCEV Op) const
const SCEV *	getElementSize (Instruction *Inst)
	Return the size of an element read or written by Inst.
void	findArrayDimensions (SmallVectorImpl< const SCEV * > &Terms, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize) const
bool	runOnFunction (Function &F) override
void	releaseMemory () override
void	getAnalysisUsage (AnalysisUsage &AU) const override
void	print (raw_ostream &OS, const Module *=nullptr) const override
void	verifyAnalysis () const override
Static Public Member Functions
static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT	maskFlags (SCEV::NoWrapFlags Flags, int Mask)
static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT	setFlags (SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT	clearFlags (SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
Static Public Attributes
static char	ID = 0
Friends
class	SCEVCallbackVH
class	SCEVExpander
class	SCEVUnknown

Detailed Description

ScalarEvolution - This class is 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 173 of file ScalarEvolution.h.

Member Enumeration Documentation

enum llvm::ScalarEvolution::BlockDisposition

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

enum llvm::ScalarEvolution::LoopDisposition

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

Constructor & Destructor Documentation

ScalarEvolution::ScalarEvolution ( )

Definition at line 7649 of file ScalarEvolution.cpp.

References llvm::PassRegistry::getPassRegistry(), and llvm::initializeScalarEvolutionPass().

Member Function Documentation

static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT llvm::ScalarEvolution::clearFlags	(	SCEV::NoWrapFlags	Flags,
		SCEV::NoWrapFlags	OffFlags
	)		`[inline, static]`

Definition at line 202 of file ScalarEvolution.h.

Referenced by getMulExpr().

bool ScalarEvolution::dominates	(	const SCEV *	S,
		const BasicBlock *	BB
	)

dominates - Return true if elements that makes up the given SCEV dominate the specified basic block.

Definition at line 7978 of file ScalarEvolution.cpp.

References DominatesBlock, and getBlockDisposition().

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

Compute the array dimensions Sizes from the set of Terms extracted from the memory access function of this SCEVAddRecExpr.

Second step of delinearization: compute the array dimensions Sizes from the set of Terms extracted from the memory access function of this SCEVAddRec.

Definition at line 7394 of file ScalarEvolution.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorImpl< T >::clear(), containsParameters(), llvm::dbgs(), DEBUG, llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::SmallVectorImpl< T >::erase(), findArrayDimensionsRec(), numberOfTerms(), llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), removeConstantFactors(), and llvm::SmallVectorTemplateCommon< T, typename >::size().

Referenced by llvm::SCEVAddRecExpr::delinearize().

void ScalarEvolution::forgetLoop ( const Loop * L )

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

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

Definition at line 4267 of file ScalarEvolution.cpp.

References llvm::LoopBase< BlockT, LoopT >::begin(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT >, KeyT, ValueT, KeyInfoT >::clear(), llvm::SmallVectorBase::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::end(), llvm::LoopBase< BlockT, LoopT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::find(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::find_as(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), PushDefUseChildren(), and PushLoopPHIs().

Referenced by llvm::formLCSSA(), separateNestedLoop(), simplifyOneLoop(), llvm::UnrollLoop(), and llvm::UnrollRuntimeLoopProlog().

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

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

Referenced by simplifyOneLoop().

void ScalarEvolution::forgetValue ( Value * V )

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

References llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::find_as(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), and PushDefUseChildren().

Referenced by deleteDeadInstruction(), and simplifyOneLoop().

const SCEV * ScalarEvolution::getAddExpr	(	SmallVectorImpl< const SCEV * > &	Ops,
		SCEV::NoWrapFlags	Flags = `SCEV::FlagAnyWrap`
	)

getAddExpr - Get a canonical add expression, or something simpler if possible.

Definition at line 1493 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::AddOne(), llvm::FoldingSetNodeID::AddPointer(), llvm::BumpPtrAllocatorImpl< AllocatorT, SlabSize, SizeThreshold >::Allocate(), llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::CallingConv::C, llvm::SmallVectorImpl< T >::clear(), CollectAddOperandsWithScales(), llvm::SmallVectorTemplateCommon< T, typename >::data(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::SmallVectorImpl< T >::erase(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT >, KeyT, ValueT, KeyInfoT >::find(), llvm::FoldingSet< T >::FindNodeOrInsertPos(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, getAddRecExpr(), getAnyExtendExpr(), getConstant(), getEffectiveSCEVType(), llvm::SCEVAddRecExpr::getLoop(), getMulExpr(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVCastExpr::getOperand(), llvm::SCEVNAryExpr::getOperand(), llvm::SCEVAddRecExpr::getStart(), getTruncateExpr(), llvm::Intrinsic::getType(), llvm::SCEVCastExpr::getType(), llvm::SCEV::getType(), getTypeSizeInBits(), GroupByComplexity(), I, ID, llvm::FoldingSetImpl::InsertNode(), llvm::FoldingSetNodeID::Intern(), isKnownNonNegative(), isLoopInvariant(), maskFlags(), llvm::SCEVNAryExpr::op_begin(), llvm::SCEVNAryExpr::op_end(), llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), llvm::scAddExpr, llvm::scAddRecExpr, llvm::scMulExpr, setFlags(), llvm::SCEVCommutativeExpr::setNoWrapFlags(), llvm::SmallVectorTemplateCommon< T, typename >::size(), and llvm::Trunc.

Referenced by canBeCheaplyTransformed(), llvm::SCEVAddRecExpr::evaluateAtIteration(), ExposePointerBase(), ExtractImmediate(), ExtractSymbol(), FactorOutConstant(), genLoopLimit(), getAddExpr(), getExactSDiv(), getMinusSCEV(), getMulExpr(), llvm::SCEVAddRecExpr::getPostIncExpr(), getPreStartForSignExtend(), getSignExtendAddRecStart(), getSignExtendExpr(), getSmallConstantTripMultiple(), getTruncateExpr(), getUDivExpr(), getZeroExtendExpr(), SimplifyAddOperands(), SimplifyICmpOperands(), llvm::UnrollRuntimeLoopProlog(), llvm::SCEVParameterRewriter::visitAddExpr(), and llvm::SCEVApplyRewriter::visitAddExpr().

const SCEV* llvm::ScalarEvolution::getAddExpr	(	const SCEV *	LHS,
		const SCEV *	RHS,
		SCEV::NoWrapFlags	Flags = `SCEV::FlagAnyWrap`
	)		`[inline]`

Definition at line 604 of file ScalarEvolution.h.

References getAddExpr(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

const SCEV* llvm::ScalarEvolution::getAddExpr	(	const SCEV *	Op0,
		const SCEV *	Op1,
		const SCEV *	Op2,
		SCEV::NoWrapFlags	Flags = `SCEV::FlagAnyWrap`
	)		`[inline]`

Definition at line 611 of file ScalarEvolution.h.

References getAddExpr(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

const SCEV * ScalarEvolution::getAddRecExpr	(	const SCEV *	Start,
		const SCEV *	Step,
		const Loop *	L,
		SCEV::NoWrapFlags	Flags
	)

getAddRecExpr - Get an add recurrence expression for the specified loop. Simplify the expression as much as possible.

Definition at line 2344 of file ScalarEvolution.cpp.

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

Referenced by DoInitialMatch(), ExposePointerBase(), ExtractImmediate(), ExtractSymbol(), FactorOutConstant(), getAddExpr(), getAddRecExpr(), getAnyExtendExpr(), getMulExpr(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), llvm::SCEVExpander::getOrInsertCanonicalInductionVariable(), getPreStartForSignExtend(), getSignExtendExpr(), llvm::SCEVAddRecExpr::getStepRecurrence(), getTruncateExpr(), getUDivExpr(), getZeroExtendExpr(), SplitAddRecs(), llvm::SCEVParameterRewriter::visitAddRecExpr(), and llvm::SCEVApplyRewriter::visitAddRecExpr().

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

getAddRecExpr - Get an add recurrence expression for the specified loop. Simplify the expression as much as possible.

Definition at line 2362 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::BumpPtrAllocatorImpl< AllocatorT, SlabSize, SizeThreshold >::Allocate(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::DominatorTree::dominates(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::FoldingSet< T >::FindNodeOrInsertPos(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, getAddRecExpr(), getEffectiveSCEVType(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), llvm::Intrinsic::getType(), I, ID, llvm::FoldingSetImpl::InsertNode(), llvm::FoldingSetNodeID::Intern(), isKnownNonNegative(), isLoopInvariant(), llvm::SCEV::isZero(), maskFlags(), llvm::SmallVectorTemplateBase< T, isPodLike >::pop_back(), llvm::scAddRecExpr, setFlags(), llvm::SCEVAddRecExpr::setNoWrapFlags(), llvm::SmallVectorTemplateCommon< T >::size(), and llvm::SmallVectorTemplateCommon< T, typename >::size().

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

Definition at line 643 of file ScalarEvolution.h.

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

void ScalarEvolution::getAnalysisUsage ( AnalysisUsage & ) const [override, virtual]

getAnalysisUsage - This function should be overriden by passes that need analysis information to do their job. If a pass specifies that it uses a particular analysis result to this function, it can then use the getAnalysis<AnalysisType>() function, below.

Reimplemented from llvm::Pass.

Definition at line 7696 of file ScalarEvolution.cpp.

References llvm::AnalysisUsage::addRequired(), llvm::AnalysisUsage::addRequiredTransitive(), and llvm::AnalysisUsage::setPreservesAll().

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

References llvm::SCEV::FlagNW, getAddRecExpr(), getEffectiveSCEVType(), getSignExtendExpr(), getTruncateOrNoop(), llvm::SCEV::getType(), getTypeSizeInBits(), getZeroExtendExpr(), isSCEVable(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::PPCISD::SC, and llvm::SExt.

Referenced by getAddExpr(), and getNoopOrAnyExtend().

const SCEV * ScalarEvolution::getBackedgeTakenCount ( const Loop * L )

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

Referenced by canExpandBackedgeTakenCount(), getLoopBackedgeTakenCounts(), getSmallConstantTripCount(), getSmallConstantTripMultiple(), hasLoopInvariantBackedgeTakenCount(), llvm::IVUsers::print(), PrintLoopInfo(), and llvm::UnrollRuntimeLoopProlog().

ScalarEvolution::BlockDisposition ScalarEvolution::getBlockDisposition	(	const SCEV *	S,
		const BasicBlock *	BB
	)

getLoopDisposition - Return the "disposition" of the given SCEV with respect to the given block.

Definition at line 7897 of file ScalarEvolution.cpp.

References DoesNotDominateBlock, llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), and llvm::SmallVectorTemplateCommon< T >::size().

Referenced by dominates(), and properlyDominates().

const SCEV * ScalarEvolution::getConstant ( ConstantInt * V )

Definition at line 314 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::FoldingSet< T >::FindNodeOrInsertPos(), ID, llvm::FoldingSetImpl::InsertNode(), llvm::FoldingSetNodeID::Intern(), and llvm::scConstant.

Referenced by BinomialCoefficient(), DoInitialMatch(), EvaluateConstantChrecAtConstant(), ExposePointerBase(), ExtractImmediate(), ExtractSymbol(), FactorOutConstant(), getAddExpr(), getConstant(), getExactSDiv(), getMinusSCEV(), getMulExpr(), getNegativeSCEV(), getNotSCEV(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), getOffsetOfExpr(), llvm::SCEVExpander::getOrInsertCanonicalInductionVariable(), getOverflowLimitForStep(), getSignExtendExpr(), getSizeOfExpr(), getSmallConstantTripMultiple(), getSMaxExpr(), getTruncateExpr(), getUDivExactExpr(), getUDivExpr(), getUMaxExpr(), getZeroExtendExpr(), isHighCostExpansion(), SimplifyAddOperands(), SimplifyICmpOperands(), SolveLinEquationWithOverflow(), SolveQuadraticEquation(), SplitAddRecs(), llvm::UnrollRuntimeLoopProlog(), and llvm::SCEVParameterRewriter::visitUnknown().

const SCEV * ScalarEvolution::getConstant ( const APInt & Val )

Definition at line 325 of file ScalarEvolution.cpp.

References llvm::ConstantInt::get(), getConstant(), and getContext().

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

Definition at line 330 of file ScalarEvolution.cpp.

References llvm::ConstantInt::get(), getConstant(), and getEffectiveSCEVType().

LLVMContext& llvm::ScalarEvolution::getContext ( ) const [inline]

const SCEV * ScalarEvolution::getCouldNotCompute ( )

Definition at line 2802 of file ScalarEvolution.cpp.

Referenced by BinomialCoefficient(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), getSmallConstantTripMultiple(), SolveLinEquationWithOverflow(), and SolveQuadraticEquation().

Type * ScalarEvolution::getEffectiveSCEVType ( Type * Ty ) const

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

References getContext(), llvm::Type::getInt64Ty(), llvm::DataLayout::getIntPtrType(), llvm::Type::isIntegerTy(), llvm::Type::isPointerTy(), and isSCEVable().

Referenced by canBeCheaplyTransformed(), DoInitialMatch(), genLoopLimit(), getAddExpr(), getAddRecExpr(), getAnyExtendExpr(), getConstant(), getElementSize(), getMulExpr(), getNegativeSCEV(), getNotSCEV(), getOffsetOfExpr(), getSignExtendExpr(), getSizeOfExpr(), getSMaxExpr(), getTruncateExpr(), getUDivExpr(), getUMaxExpr(), getZeroExtendExpr(), isExistingPhi(), and visitIVCast().

const SCEV * ScalarEvolution::getElementSize ( Instruction * Inst )

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

Definition at line 7379 of file ScalarEvolution.cpp.

References getEffectiveSCEVType(), getSizeOfExpr(), llvm::PointerType::getUnqual(), llvm::SPII::Load, and llvm::SPII::Store.

Referenced by llvm::DependenceAnalysis::depends(), and llvm::DependenceAnalysis::getSplitIteration().

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

Definition at line 4152 of file ScalarEvolution.cpp.

ScalarEvolution::LoopDisposition ScalarEvolution::getLoopDisposition	(	const SCEV *	S,
		const Loop *	L
	)

getLoopDisposition - Return the "disposition" of the given SCEV with respect to the given loop.

Definition at line 7791 of file ScalarEvolution.cpp.

References LoopVariant, llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), and llvm::SmallVectorTemplateCommon< T >::size().

Referenced by hasComputableLoopEvolution(), and isLoopInvariant().

const SCEV * ScalarEvolution::getMaxBackedgeTakenCount ( const Loop * L )

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

Definition at line 4174 of file ScalarEvolution.cpp.

Referenced by getSignedRange(), getSignExtendExpr(), getUnsignedRange(), getZeroExtendExpr(), and PrintLoopInfo().

uint32_t ScalarEvolution::GetMinTrailingZeros ( const SCEV * S )

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

References llvm::ARM_PROC::A, llvm::CallingConv::C, llvm::computeKnownBits(), and getTypeSizeInBits().

Referenced by getSignedRange(), and getUnsignedRange().

const SCEV * ScalarEvolution::getMinusSCEV	(	const SCEV *	LHS,
		const SCEV *	RHS,
		SCEV::NoWrapFlags	Flags = `SCEV::FlagAnyWrap`
	)

getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1.

Definition at line 2888 of file ScalarEvolution.cpp.

References llvm::SCEV::FlagNUW, getAddExpr(), getConstant(), getNegativeSCEV(), llvm::SCEV::getType(), and maskFlags().

Referenced by BinomialCoefficient(), getNewAlignment(), getNewAlignmentDiff(), getNotSCEV(), and isHighCostExpansion().

const SCEV * ScalarEvolution::getMulExpr	(	SmallVectorImpl< const SCEV * > &	Ops,
		SCEV::NoWrapFlags	Flags = `SCEV::FlagAnyWrap`
	)

getMulExpr - Get a canonical multiply expression, or something simpler if possible.

Definition at line 1896 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::BumpPtrAllocatorImpl< AllocatorT, SlabSize, SizeThreshold >::Allocate(), llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), Choose(), clearFlags(), llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::SmallVectorImpl< T >::erase(), llvm::FoldingSet< T >::FindNodeOrInsertPos(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, llvm::ConstantInt::get(), getAddExpr(), getAddRecExpr(), getConstant(), getContext(), getEffectiveSCEVType(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), llvm::Intrinsic::getType(), llvm::SCEVNAryExpr::getType(), getTypeSizeInBits(), GroupByComplexity(), I, ID, llvm::FoldingSetImpl::InsertNode(), llvm::FoldingSetNodeID::Intern(), isKnownNonNegative(), isLoopInvariant(), maskFlags(), llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::SmallVectorImpl< T >::reserve(), llvm::scAddRecExpr, llvm::scMulExpr, setFlags(), llvm::SCEVCommutativeExpr::setNoWrapFlags(), llvm::SmallVectorTemplateCommon< T, typename >::size(), and umul_ov().

Referenced by BinomialCoefficient(), CollectAddOperandsWithScales(), CollectSubexprs(), DoInitialMatch(), llvm::SCEVAddRecExpr::evaluateAtIteration(), FactorOutConstant(), findArrayDimensionsRec(), getAddExpr(), getExactSDiv(), getMulExpr(), getNegativeSCEV(), getNewAlignmentDiff(), getSignExtendExpr(), getTruncateExpr(), getUDivExactExpr(), getUDivExpr(), getZeroExtendExpr(), removeConstantFactors(), llvm::SCEVParameterRewriter::visitMulExpr(), and llvm::SCEVApplyRewriter::visitMulExpr().

const SCEV* llvm::ScalarEvolution::getMulExpr	(	const SCEV *	LHS,
		const SCEV *	RHS,
		SCEV::NoWrapFlags	Flags = `SCEV::FlagAnyWrap`
	)		`[inline]`

Definition at line 621 of file ScalarEvolution.h.

References getMulExpr(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

const SCEV* llvm::ScalarEvolution::getMulExpr	(	const SCEV *	Op0,
		const SCEV *	Op1,
		const SCEV *	Op2,
		SCEV::NoWrapFlags	Flags = `SCEV::FlagAnyWrap`
	)		`[inline]`

Definition at line 629 of file ScalarEvolution.h.

References getMulExpr(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

const SCEV * ScalarEvolution::getNegativeSCEV ( const SCEV * V )

getNegativeSCEV - Return the SCEV object corresponding to -V.

getNegativeSCEV - Return a SCEV corresponding to -V = -1*V

Definition at line 2863 of file ScalarEvolution.cpp.

References llvm::Constant::getAllOnesValue(), getConstant(), getEffectiveSCEVType(), getMulExpr(), llvm::ConstantExpr::getNeg(), llvm::SCEV::getType(), and llvm::AArch64CC::VC.

Referenced by canBeCheaplyTransformed(), getMinusSCEV(), and llvm::SCEVAddRecExpr::getNumIterationsInRange().

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

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

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

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

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

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

Referenced by getNewAlignment().

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

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

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

Referenced by getSignedRange(), getUMaxFromMismatchedTypes(), getUMinFromMismatchedTypes(), and getUnsignedRange().

const SCEV * ScalarEvolution::getNotSCEV ( const SCEV * V )

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

getNotSCEV - Return the SCEV object corresponding to ~V.

Definition at line 2875 of file ScalarEvolution.cpp.

References llvm::Constant::getAllOnesValue(), getConstant(), getEffectiveSCEVType(), getMinusSCEV(), llvm::ConstantExpr::getNot(), llvm::SCEV::getType(), and llvm::AArch64CC::VC.

Referenced by getSMinExpr(), and getUMinExpr().

const SCEV * ScalarEvolution::getOffsetOfExpr	(	Type *	IntTy,
		StructType *	STy,
		unsigned	FieldNo
	)

getOffsetOfExpr - Return an expression for offsetof on the given field with type IntTy

Definition at line 2707 of file ScalarEvolution.cpp.

References llvm::CallingConv::C, llvm::WinEH::CE, llvm::ConstantFoldConstantExpression(), getConstant(), getEffectiveSCEVType(), llvm::StructLayout::getElementOffset(), llvm::ConstantExpr::getOffsetOf(), getSCEV(), llvm::DataLayout::getStructLayout(), getTruncateOrZeroExtend(), and llvm::PointerType::getUnqual().

const SCEV * ScalarEvolution::getPointerBase ( const SCEV * V )

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

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

const SCEV * ScalarEvolution::getSCEV ( Value * V )

getSCEV - Return a SCEV expression for the full generality of the specified expression.

getSCEV - Return an existing SCEV if it exists, otherwise analyze the expression and create a new one.

Definition at line 2840 of file ScalarEvolution.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::find_as(), llvm::Value::getType(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::insert(), isSCEVable(), and SCEVCallbackVH.

Referenced by llvm::IVUsers::AddUsersImpl(), llvm::DependenceAnalysis::depends(), DoInitialMatch(), findIVOperand(), FindLoopCounter(), genLoopLimit(), getNewAlignment(), getOffsetOfExpr(), llvm::IVUsers::getReplacementExpr(), getSCEVAtScope(), getSizeOfExpr(), llvm::DependenceAnalysis::getSplitIteration(), getStrideFromPointer(), isExistingPhi(), isHighCostExpansion(), isLikelyComplexAddressComputation(), isProfitableChain(), isSimpleIVUser(), print(), llvm::SCEVExpander::replaceCongruentIVs(), replaceSymbolicStrideSCEV(), and stripGetElementPtr().

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

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

References llvm::CallingConv::C, llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), and llvm::SmallVectorTemplateCommon< T >::size().

Referenced by getSCEVAtScope(), isInteresting(), and print().

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

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

Definition at line 5557 of file ScalarEvolution.cpp.

References getSCEV(), and getSCEVAtScope().

ConstantRange ScalarEvolution::getSignedRange ( const SCEV * S )

getSignedRange - Determine the signed range for a particular SCEV.

Definition at line 3547 of file ScalarEvolution.cpp.

Referenced by getOverflowLimitForStep(), getSignExtendExpr(), getUnsignedRange(), getZeroExtendExpr(), isKnownNegative(), isKnownNonNegative(), isKnownNonPositive(), isKnownPositive(), and SimplifyICmpOperands().

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

Definition at line 1159 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::ConstantRange::contains(), llvm::dyn_cast(), llvm::FoldingSet< T >::FindNodeOrInsertPos(), llvm::SCEV::FlagNSW, llvm::IntegerType::get(), getAddExpr(), getAddRecExpr(), getConstant(), getContext(), getEffectiveSCEVType(), getMaxBackedgeTakenCount(), getMulExpr(), getOverflowLimitForStep(), llvm::ConstantExpr::getSExt(), getSignedRange(), getSignExtendAddRecStart(), getTruncateOrSignExtend(), getTruncateOrZeroExtend(), llvm::SCEV::getType(), getTypeSizeInBits(), getZeroExtendExpr(), ID, llvm::FoldingSetImpl::InsertNode(), llvm::FoldingSetNodeID::Intern(), isKnownNonNegative(), isLoopBackedgeGuardedByCond(), isLoopEntryGuardedByCond(), llvm::APInt::isPowerOf2(), isSCEVable(), llvm::APInt::isStrictlyPositive(), llvm::PPCISD::SC, llvm::scSignExtend, llvm::ConstantRange::sextOrTrunc(), llvm::ConstantRange::signExtend(), llvm::AArch64DB::ST, llvm::ConstantRange::truncate(), and llvm::APInt::ugt().

Referenced by getAnyExtendExpr(), getNoopOrSignExtend(), getPreStartForSignExtend(), getSignExtendAddRecStart(), getTruncateOrSignExtend(), getZeroExtendExpr(), isAddRecSExtable(), isAddSExtable(), isMulSExtable(), llvm::SCEVParameterRewriter::visitSignExtendExpr(), and llvm::SCEVApplyRewriter::visitSignExtendExpr().

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

getSizeOfExpr - Return an expression for sizeof AllocTy that is type IntTy

Definition at line 2691 of file ScalarEvolution.cpp.

References llvm::CallingConv::C, llvm::WinEH::CE, llvm::ConstantFoldConstantExpression(), getConstant(), getEffectiveSCEVType(), getSCEV(), llvm::ConstantExpr::getSizeOf(), getTruncateOrZeroExtend(), llvm::DataLayout::getTypeAllocSize(), and llvm::PointerType::getUnqual().

Referenced by genLoopLimit(), and getElementSize().

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

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

getSmallConstantTripCount - Returns the maximum trip count of this loop as a normal unsigned value. Returns 0 if the trip count is unknown or not constant. Will also return 0 if the maximum trip count is very large (>= 2^32).

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 because the loop may exit prematurely via another branch.

FIXME: We conservatively call getBackedgeTakenCount(L) instead of getExitCount(L, ExitingBlock) to compute a safe trip count considering all loop exits. getExitCount() may return an exact count for this branch assuming no-signed-wrap. The number of well-defined iterations may actually be higher than this trip count if this exit test is skipped and the loop exits via a different branch. Ideally, getExitCount() would know whether it depends on a NSW assumption, and we would only fall back to a conservative trip count in that case.

Definition at line 4091 of file ScalarEvolution.cpp.

References llvm::dyn_cast(), llvm::APInt::getActiveBits(), getBackedgeTakenCount(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), and llvm::ConstantInt::getZExtValue().

unsigned ScalarEvolution::getSmallConstantTripMultiple	(	Loop *	L,
		BasicBlock *	ExitingBlock
	)

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

getSmallConstantTripMultiple - 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!).

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

References llvm::dyn_cast(), llvm::APInt::getActiveBits(), getAddExpr(), getBackedgeTakenCount(), getConstant(), getCouldNotCompute(), llvm::SCEV::getType(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), and llvm::ConstantInt::getZExtValue().

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

Definition at line 2471 of file ScalarEvolution.cpp.

References llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

Referenced by getSMaxExpr(), getSMinExpr(), llvm::SCEVParameterRewriter::visitSMaxExpr(), and llvm::SCEVApplyRewriter::visitSMaxExpr().

const SCEV * ScalarEvolution::getSMaxExpr ( SmallVectorImpl< const SCEV * > & Operands )

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

Definition at line 2679 of file ScalarEvolution.cpp.

References getNotSCEV(), and getSMaxExpr().

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

Definition at line 823 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::FoldingSet< T >::FindNodeOrInsertPos(), llvm::SCEV::FlagAnyWrap, getAddExpr(), getAddRecExpr(), getConstant(), getEffectiveSCEVType(), getMulExpr(), llvm::ConstantExpr::getTrunc(), getTruncateOrSignExtend(), getTruncateOrZeroExtend(), llvm::SCEV::getType(), getTypeSizeInBits(), ID, llvm::FoldingSetImpl::InsertNode(), llvm::FoldingSetNodeID::Intern(), isSCEVable(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::PPCISD::SC, llvm::scTruncate, and llvm::AArch64DB::ST.

Referenced by genLoopLimit(), getAddExpr(), getTruncateOrNoop(), getTruncateOrSignExtend(), getTruncateOrZeroExtend(), llvm::SCEVExpander::replaceCongruentIVs(), llvm::SCEVParameterRewriter::visitTruncateExpr(), and llvm::SCEVApplyRewriter::visitTruncateExpr().

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

getTruncateOrNoop - Return a SCEV corresponding to a conversion of the input value to the specified type. The conversion must not be widening.

Definition at line 2985 of file ScalarEvolution.cpp.

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

Referenced by canBeCheaplyTransformed(), getAnyExtendExpr(), and llvm::SCEVExpander::replaceCongruentIVs().

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

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

References getSignExtendExpr(), getTruncateExpr(), llvm::SCEV::getType(), getTypeSizeInBits(), llvm::Type::isIntegerTy(), and llvm::Type::isPointerTy().

Referenced by getSignExtendExpr(), and getTruncateExpr().

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

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

References getTruncateExpr(), llvm::SCEV::getType(), getTypeSizeInBits(), getZeroExtendExpr(), llvm::Type::isIntegerTy(), and llvm::Type::isPointerTy().

Referenced by BinomialCoefficient(), genLoopLimit(), getOffsetOfExpr(), getSignExtendExpr(), getSizeOfExpr(), getTruncateExpr(), and getZeroExtendExpr().

uint64_t ScalarEvolution::getTypeSizeInBits ( Type * Ty ) const

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

Definition at line 2764 of file ScalarEvolution.cpp.

References llvm::Type::getPrimitiveSizeInBits(), llvm::DataLayout::getTypeSizeInBits(), llvm::Type::isIntegerTy(), llvm::Type::isPointerTy(), and isSCEVable().

Referenced by llvm::IVUsers::AddUsersImpl(), BinomialCoefficient(), FindLoopCounter(), genLoopLimit(), getAddExpr(), getAnyExtendExpr(), GetMinTrailingZeros(), getMulExpr(), getNoopOrAnyExtend(), getNoopOrSignExtend(), getNoopOrZeroExtend(), llvm::SCEVAddRecExpr::getNumIterationsInRange(), getOverflowLimitForStep(), getPreStartForSignExtend(), getSignedRange(), getSignExtendExpr(), getTruncateExpr(), getTruncateOrNoop(), getTruncateOrSignExtend(), getTruncateOrZeroExtend(), getUDivExpr(), getUMaxFromMismatchedTypes(), getUMinFromMismatchedTypes(), getUnsignedRange(), getZeroExtendExpr(), isAddRecSExtable(), isAddSExtable(), isMulSExtable(), and visitIVCast().

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

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

References llvm::SmallVectorImpl< T >::append(), llvm::dyn_cast(), gcd(), getConstant(), getMulExpr(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), getUDivExpr(), llvm::APInt::isIntN(), llvm::SCEVNAryExpr::op_begin(), llvm::SCEVNAryExpr::op_end(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

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

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

References llvm::ARM_PROC::A, llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::SmallVectorImpl< T >::clear(), llvm::dyn_cast(), llvm::FoldingSet< T >::FindNodeOrInsertPos(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNW, llvm::IntegerType::get(), getAddExpr(), getAddRecExpr(), getConstant(), getContext(), getEffectiveSCEVType(), getMulExpr(), llvm::SCEV::getType(), getTypeSizeInBits(), llvm::ConstantExpr::getUDiv(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), getZeroExtendExpr(), ID, llvm::FoldingSetImpl::InsertNode(), llvm::FoldingSetNodeID::Intern(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::scUDivExpr, llvm::SmallVectorTemplateCommon< T >::size(), and llvm::APInt::urem().

Referenced by BinomialCoefficient(), getNewAlignmentDiff(), getUDivExactExpr(), llvm::SCEVParameterRewriter::visitUDivExpr(), and llvm::SCEVApplyRewriter::visitUDivExpr().

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

Definition at line 2575 of file ScalarEvolution.cpp.

References llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

Referenced by getUMaxExpr(), getUMaxFromMismatchedTypes(), getUMinExpr(), llvm::SCEVParameterRewriter::visitUMaxExpr(), and llvm::SCEVApplyRewriter::visitUMaxExpr().

const SCEV * ScalarEvolution::getUMaxExpr ( SmallVectorImpl< const SCEV * > & Operands )

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

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

Definition at line 3000 of file ScalarEvolution.cpp.

References getNoopOrZeroExtend(), llvm::SCEV::getType(), getTypeSizeInBits(), getUMaxExpr(), and getZeroExtendExpr().

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

Definition at line 2685 of file ScalarEvolution.cpp.

References getNotSCEV(), and getUMaxExpr().

Referenced by getUMinFromMismatchedTypes().

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

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

Definition at line 3016 of file ScalarEvolution.cpp.

References getNoopOrZeroExtend(), llvm::SCEV::getType(), getTypeSizeInBits(), getUMinExpr(), and getZeroExtendExpr().

const SCEV * ScalarEvolution::getUnknown ( Value * V )

Definition at line 2727 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::FoldingSet< T >::FindNodeOrInsertPos(), ID, llvm::FoldingSetImpl::InsertNode(), llvm::FoldingSetNodeID::Intern(), SCEVUnknown, and llvm::scUnknown.

Referenced by llvm::SCEVParameterRewriter::visitUnknown().

ConstantRange ScalarEvolution::getUnsignedRange ( const SCEV * S )

getUnsignedRange - Determine the unsigned range for a particular SCEV.

Definition at line 3406 of file ScalarEvolution.cpp.

Referenced by getSignedRange(), getZeroExtendExpr(), and SimplifyICmpOperands().

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

Definition at line 902 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::ConstantRange::contains(), llvm::FoldingSet< T >::FindNodeOrInsertPos(), llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, llvm::IntegerType::get(), getAddExpr(), getAddRecExpr(), getConstant(), getContext(), getEffectiveSCEVType(), getMaxBackedgeTakenCount(), llvm::APInt::getMaxValue(), llvm::APInt::getMinValue(), getMulExpr(), getSignedRange(), getSignExtendExpr(), getTruncateOrZeroExtend(), llvm::SCEV::getType(), getTypeSizeInBits(), getUnsignedRange(), llvm::ConstantExpr::getZExt(), llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULT, ID, llvm::FoldingSetImpl::InsertNode(), llvm::FoldingSetNodeID::Intern(), isKnownNegative(), isKnownPositive(), isLoopBackedgeGuardedByCond(), isLoopEntryGuardedByCond(), isSCEVable(), N, llvm::PPCISD::SC, llvm::scZeroExtend, llvm::AArch64DB::ST, llvm::ConstantRange::truncate(), llvm::ConstantRange::zeroExtend(), and llvm::ConstantRange::zextOrTrunc().

Referenced by getAnyExtendExpr(), getNoopOrZeroExtend(), getSignExtendExpr(), getTruncateOrZeroExtend(), getUDivExpr(), getUMaxFromMismatchedTypes(), getUMinFromMismatchedTypes(), llvm::SCEVParameterRewriter::visitZeroExtendExpr(), and llvm::SCEVApplyRewriter::visitZeroExtendExpr().

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

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

References getLoopDisposition(), and LoopComputable.

bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount ( const Loop * L )

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

Definition at line 7704 of file ScalarEvolution.cpp.

References getBackedgeTakenCount().

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

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

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

Definition at line 8003 of file ScalarEvolution.cpp.

References llvm::visitAll().

bool ScalarEvolution::isKnownNegative ( const SCEV * S )

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

Definition at line 6169 of file ScalarEvolution.cpp.

References llvm::ConstantRange::getSignedMax(), getSignedRange(), and llvm::APInt::isNegative().

Referenced by getOverflowLimitForStep(), getZeroExtendExpr(), and isKnownNonZero().

bool ScalarEvolution::isKnownNonNegative ( const SCEV * S )

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

Definition at line 6177 of file ScalarEvolution.cpp.

References llvm::ConstantRange::getSignedMin(), getSignedRange(), and llvm::APInt::isNegative().

Referenced by getAddExpr(), getAddRecExpr(), getMulExpr(), getSignedRange(), and getSignExtendExpr().

bool ScalarEvolution::isKnownNonPositive ( const SCEV * S )

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

Definition at line 6181 of file ScalarEvolution.cpp.

References llvm::ConstantRange::getSignedMax(), getSignedRange(), and llvm::APInt::isStrictlyPositive().

Referenced by getSignedRange().

bool ScalarEvolution::isKnownNonZero ( const SCEV * S )

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

Definition at line 6185 of file ScalarEvolution.cpp.

References isKnownNegative(), and isKnownPositive().

bool ScalarEvolution::isKnownPositive ( const SCEV * S )

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

Definition at line 6173 of file ScalarEvolution.cpp.

References llvm::ConstantRange::getSignedMin(), getSignedRange(), and llvm::APInt::isStrictlyPositive().

Referenced by getOverflowLimitForStep(), getZeroExtendExpr(), and isKnownNonZero().

bool ScalarEvolution::isKnownPredicate	(	ICmpInst::Predicate	Pred,
		const SCEV *	LHS,
		const SCEV *	RHS
	)

isKnownPredicate - Test if the given expression is known to satisfy the condition described by Pred, LHS, and RHS.

Definition at line 6189 of file ScalarEvolution.cpp.

References llvm::dyn_cast(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVAddRecExpr::getPostIncExpr(), llvm::SCEVAddRecExpr::getStart(), isLoopBackedgeGuardedByCond(), isLoopEntryGuardedByCond(), and SimplifyICmpOperands().

Referenced by getSMaxExpr(), and getUMaxExpr().

bool ScalarEvolution::isLoopBackedgeGuardedByCond	(	const Loop *	L,
		ICmpInst::Predicate	Pred,
		const SCEV *	LHS,
		const SCEV *	RHS
	)

isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is protected by a conditional between LHS and RHS. This is used to to eliminate casts.

Definition at line 6303 of file ScalarEvolution.cpp.

References llvm::DominatorTree::dominates(), llvm::dyn_cast(), llvm::BranchInst::getCondition(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), and llvm::BranchInst::isConditional().

Referenced by getSignExtendExpr(), getZeroExtendExpr(), and isKnownPredicate().

bool ScalarEvolution::isLoopEntryGuardedByCond	(	const Loop *	L,
		ICmpInst::Predicate	Pred,
		const SCEV *	LHS,
		const SCEV *	RHS
	)

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

References llvm::DominatorTree::dominates(), llvm::dyn_cast(), llvm::BranchInst::getCondition(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopPredecessor(), llvm::BranchInst::getSuccessor(), and llvm::BranchInst::isUnconditional().

Referenced by getPreStartForSignExtend(), getSignExtendExpr(), getZeroExtendExpr(), and isKnownPredicate().

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

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

Definition at line 7888 of file ScalarEvolution.cpp.

References getLoopDisposition(), and LoopInvariant.

Referenced by genLoopLimit(), getAddExpr(), getAddRecExpr(), getMulExpr(), isLikelyComplexAddressComputation(), print(), SimplifyICmpOperands(), and stripGetElementPtr().

bool ScalarEvolution::isSCEVable ( Type * Ty ) const

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

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

Referenced by llvm::IVUsers::AddUsersImpl(), findIVOperand(), FindLoopCounter(), getAnyExtendExpr(), getEffectiveSCEVType(), getSCEV(), getSignExtendExpr(), getTruncateExpr(), getTypeSizeInBits(), getZeroExtendExpr(), isExistingPhi(), isHighCostExpansion(), isSimpleIVUser(), print(), and llvm::SCEVExpander::replaceCongruentIVs().

static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT llvm::ScalarEvolution::maskFlags	(	SCEV::NoWrapFlags	Flags,
		int	Mask
	)		`[inline, static]`

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

Definition at line 194 of file ScalarEvolution.h.

Referenced by getAddExpr(), getAddRecExpr(), getMinusSCEV(), and getMulExpr().

void ScalarEvolution::print	(	raw_ostream &	O,
		const Module *	M = `nullptr`
	)		const `[override, virtual]`

print - Print out the internal state of the pass. This is called by Analyze to print out the contents of an analysis. Otherwise it is not necessary to implement this method. Beware that the module pointer MAY be null. This automatically forwards to a virtual function that does not provide the Module* in case the analysis doesn't need it it can just be ignored.

Reimplemented from llvm::Pass.

Definition at line 7743 of file ScalarEvolution.cpp.

References llvm::LoopBase< BlockT, LoopT >::begin(), llvm::LoopBase< BlockT, LoopT >::end(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), getSCEV(), getSCEVAtScope(), I, llvm::inst_begin(), llvm::inst_end(), isLoopInvariant(), isSCEVable(), llvm::SCEV::print(), and PrintLoopInfo().

bool ScalarEvolution::properlyDominates	(	const SCEV *	S,
		const BasicBlock *	BB
	)

properlyDominates - Return true if elements that makes up the given SCEV properly dominate the specified basic block.

Definition at line 7982 of file ScalarEvolution.cpp.

References getBlockDisposition(), and ProperlyDominatesBlock.

Referenced by DoInitialMatch(), and SimplifyICmpOperands().

void ScalarEvolution::releaseMemory ( ) [override, virtual]

releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memory when it is no longer needed. The default behavior of passes is to hold onto memory for the entire duration of their lifetime (which is the entire compile time). For pipelined passes, this is not a big deal because that memory gets recycled every time the pass is invoked on another program unit. For IP passes, it is more important to free memory when it is unused.

Optionally implement this function to release pass memory when it is no longer used.

Reimplemented from llvm::Pass.

Definition at line 7666 of file ScalarEvolution.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::begin(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT >, KeyT, ValueT, KeyInfoT >::clear(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::clear(), llvm::FoldingSetImpl::clear(), llvm::DenseSet< ValueT, ValueInfoT >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::end(), I, and llvm::BumpPtrAllocatorImpl< AllocatorT, SlabSize, SizeThreshold >::Reset().

Referenced by verifyAnalysis().

bool ScalarEvolution::runOnFunction ( Function & F ) [override, virtual]

runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.

Implements llvm::FunctionPass.

Definition at line 7655 of file ScalarEvolution.cpp.

References llvm::DataLayoutPass::getDataLayout().

static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT llvm::ScalarEvolution::setFlags	(	SCEV::NoWrapFlags	Flags,
		SCEV::NoWrapFlags	OnFlags
	)		`[inline, static]`

Definition at line 198 of file ScalarEvolution.h.

Referenced by getAddExpr(), getAddRecExpr(), getMulExpr(), and llvm::SCEVAddRecExpr::setNoWrapFlags().

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

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

SimplifyICmpOperands - Simplify LHS and RHS in a comparison with predicate Pred. Return true iff any changes were made.

Definition at line 5892 of file ScalarEvolution.cpp.

Referenced by isKnownPredicate().

void ScalarEvolution::verifyAnalysis ( ) const [override, virtual]

verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis information.

Reimplemented from llvm::Pass.

Definition at line 8061 of file ScalarEvolution.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::begin(), llvm::dbgs(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::end(), getLoopBackedgeTakenCounts(), I, llvm::LoopBase< BlockT, LoopT >::rbegin(), releaseMemory(), llvm::LoopBase< BlockT, LoopT >::rend(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::size(), and VerifySCEV.

Friends And Related Function Documentation

friend class SCEVCallbackVH [friend]

Definition at line 217 of file ScalarEvolution.h.

Referenced by getSCEV().

friend class SCEVExpander [friend]

Definition at line 218 of file ScalarEvolution.h.

friend class SCEVUnknown [friend]

Definition at line 219 of file ScalarEvolution.h.

Referenced by getUnknown().

Member Data Documentation

scalar Scalar Evolution true char ScalarEvolution::ID = 0 [static]

Definition at line 570 of file ScalarEvolution.h.

Referenced by getAddExpr(), getAddRecExpr(), getConstant(), getMulExpr(), getSignExtendExpr(), getSMaxExpr(), getTruncateExpr(), getUDivExpr(), getUMaxExpr(), getUnknown(), and getZeroExtendExpr().

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

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Friends

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation