#include <ScalarEvolution.h>

Inheritance diagram for llvm::ScalarEvolution:

Collaboration diagram for llvm::ScalarEvolution:

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

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

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)

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

virtual bool	runOnFunction (Function &F)

virtual void	releaseMemory ()

virtual void	getAnalysisUsage (AnalysisUsage &AU) const

virtual void	print (raw_ostream &OS, const Module *=0) const

virtual void	verifyAnalysis () const

Public Member Functions inherited from llvm::FunctionPass
	FunctionPass (char &pid)

Pass *	createPrinterPass (raw_ostream &O, const std::string &Banner) const
	createPrinterPass - Get a function printer pass. More...

virtual void	assignPassManager (PMStack &PMS, PassManagerType T)

virtual PassManagerType	getPotentialPassManagerType () const
	Return what kind of Pass Manager can manage this pass. More...

Public Member Functions inherited from llvm::Pass
	Pass (PassKind K, char &pid)

virtual	~Pass ()

PassKind	getPassKind () const

virtual const char *	getPassName () const

AnalysisID	getPassID () const
	getPassID - Return the PassID number that corresponds to this pass. More...

virtual bool	doInitialization (Module &)

virtual bool	doFinalization (Module &)

void	dump () const

virtual void	preparePassManager (PMStack &)
	Check if available pass managers are suitable for this pass or not. More...

void	setResolver (AnalysisResolver *AR)

AnalysisResolver *	getResolver () const

virtual void *	getAdjustedAnalysisPointer (AnalysisID ID)

virtual ImmutablePass *	getAsImmutablePass ()

virtual PMDataManager *	getAsPMDataManager ()

virtual void	dumpPassStructure (unsigned Offset=0)

template<typename AnalysisType >
AnalysisType *	getAnalysisIfAvailable () const

bool	mustPreserveAnalysisID (char &AID) const

template<typename AnalysisType >
AnalysisType &	getAnalysis () const

template<typename AnalysisType >
AnalysisType &	getAnalysis (Function &F)

template<typename AnalysisType >
AnalysisType &	getAnalysisID (AnalysisID PI) const

template<typename AnalysisType >
AnalysisType &	getAnalysisID (AnalysisID PI, Function &F)

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 Member Functions inherited from llvm::Pass
static const PassInfo *	lookupPassInfo (const void *TI)

static const PassInfo *	lookupPassInfo (StringRef Arg)

static Pass *	createPass (AnalysisID ID)

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 172 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 184 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 176 of file ScalarEvolution.h.

Constructor & Destructor Documentation

ScalarEvolution::ScalarEvolution ( )

Definition at line 7262 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
	)

inlinestatic

Definition at line 201 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 7588 of file ScalarEvolution.cpp.

References DominatesBlock, and getBlockDisposition().

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.

Definition at line 4162 of file ScalarEvolution.cpp.

References llvm::LoopBase< N, M >::begin(), llvm::SmallVectorBase::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::end(), llvm::LoopBase< N, M >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::find_as(), I, llvm::SmallPtrSet< PtrType, SmallSize >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), PushDefUseChildren(), and PushLoopPHIs().

Referenced by llvm::UnrollLoop(), and llvm::UnrollRuntimeLoopProlog().

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 4201 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::SmallPtrSet< PtrType, SmallSize >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), and PushDefUseChildren().

Referenced by deleteDeadInstruction().

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

References llvm::FoldingSetNodeID::AddInteger(), AddOne(), llvm::FoldingSetNodeID::AddPointer(), llvm::BumpPtrAllocator::Allocate(), llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::CallingConv::C, llvm::SmallVectorImpl< T >::clear(), CollectAddOperandsWithScales(), llvm::SmallVectorTemplateCommon< T >::data(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::SmallVectorImpl< T >::erase(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT >, KeyT, ValueT, KeyInfoT >::find(), 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::FoldingSetNodeID::Intern(), isKnownNonNegative(), isLoopInvariant(), maskFlags(), llvm::SCEVNAryExpr::op_begin(), llvm::SCEVNAryExpr::op_end(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::scAddExpr, llvm::scAddRecExpr, llvm::scMulExpr, setFlags(), llvm::SCEVCommutativeExpr::setNoWrapFlags(), and llvm::SmallVectorTemplateCommon< T >::size().

Referenced by llvm::SCEVAddRecExpr::delinearize(), 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 582 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 589 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 2246 of file ScalarEvolution.cpp.

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

Referenced by llvm::SCEVAddRecExpr::delinearize(), 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 2264 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::BumpPtrAllocator::Allocate(), llvm::SmallVectorTemplateCommon< T >::back(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::LoopBase< N, M >::contains(), llvm::DominatorTree::dominates(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, getAddRecExpr(), getEffectiveSCEVType(), llvm::LoopBase< N, M >::getHeader(), llvm::LoopBase< N, M >::getLoopDepth(), llvm::Intrinsic::getType(), I, ID, llvm::FoldingSetNodeID::Intern(), isKnownNonNegative(), isLoopInvariant(), llvm::SCEV::isZero(), maskFlags(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::pop_back(), llvm::scAddRecExpr, setFlags(), llvm::SCEVAddRecExpr::setNoWrapFlags(), and llvm::SmallVectorTemplateCommon< T >::size().

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

inline

Definition at line 620 of file ScalarEvolution.h.

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

void ScalarEvolution::getAnalysisUsage ( AnalysisUsage & ) const

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

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

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

Referenced by canExpandBackedgeTakenCount(), getLoopBackedgeTakenCounts(), getSmallConstantTripCount(), getSmallConstantTripMultiple(), hasLoopInvariantBackedgeTakenCount(), 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 7506 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(), ID, llvm::FoldingSetNodeID::Intern(), and llvm::scConstant.

Referenced by BinomialCoefficient(), llvm::SCEVAddRecExpr::delinearize(), 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(), getUDivExpr(), getUMaxExpr(), getZeroExtendExpr(), isHighCostExpansion(), SimplifyAddOperands(), SimplifyICmpOperands(), SolveLinEquationWithOverflow(), SolveQuadraticEquation(), SplitAddRecs(), and llvm::UnrollRuntimeLoopProlog().

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

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

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

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

Definition at line 4047 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 7400 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 4069 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 3231 of file ScalarEvolution.cpp.

References llvm::ARM_PROC::A, llvm::CallingConv::C, llvm::ComputeMaskedBits(), 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 2790 of file ScalarEvolution.cpp.

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

Referenced by BinomialCoefficient(), llvm::SCEVAddRecExpr::delinearize(), 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 1864 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::BumpPtrAllocator::Allocate(), llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorTemplateCommon< T >::begin(), Choose(), clearFlags(), llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::SmallVectorImpl< T >::erase(), 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::FoldingSetNodeID::Intern(), isKnownNonNegative(), isLoopInvariant(), maskFlags(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::SmallVectorImpl< T >::reserve(), llvm::scAddRecExpr, llvm::scMulExpr, setFlags(), llvm::SCEVCommutativeExpr::setNoWrapFlags(), llvm::SmallVectorTemplateCommon< T >::size(), and umul_ov().

Referenced by BinomialCoefficient(), CollectAddOperandsWithScales(), CollectSubexprs(), llvm::SCEVAddRecExpr::delinearize(), DoInitialMatch(), llvm::SCEVAddRecExpr::evaluateAtIteration(), FactorOutConstant(), getAddExpr(), getExactSDiv(), getMulExpr(), getNegativeSCEV(), getSignExtendExpr(), getTruncateExpr(), getUDivExpr(), getZeroExtendExpr(), 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 599 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 607 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 2765 of file ScalarEvolution.cpp.

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

Referenced by 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 2872 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 2855 of file ScalarEvolution.cpp.

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

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

References llvm::Constant::getAllOnesValue(), getConstant(), getEffectiveSCEVType(), getMinusSCEV(), llvm::ConstantExpr::getNot(), llvm::SCEV::getType(), and llvm::A64CC::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 2609 of file ScalarEvolution.cpp.

References llvm::CallingConv::C, 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 2935 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 2742 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(), getOffsetOfExpr(), getSCEVAtScope(), getSizeOfExpr(), llvm::DependenceAnalysis::getSplitIteration(), hasComputableBounds(), isExistingPhi(), isHighCostExpansion(), isLikelyComplexAddressComputation(), isProfitableChain(), isSimpleIVUser(), isStridedPtr(), print(), and llvm::SCEVExpander::replaceCongruentIVs().

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 5060 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 5373 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 3450 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::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::FoldingSetNodeID::Intern(), isKnownNonNegative(), isLoopBackedgeGuardedByCond(), isLoopEntryGuardedByCond(), isSCEVable(), llvm::PPCISD::SC, llvm::scSignExtend, llvm::ConstantRange::sextOrTrunc(), llvm::ConstantRange::signExtend(), llvm::A64DB::ST, and llvm::ConstantRange::truncate().

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

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

Referenced by genLoopLimit().

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 3986 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 4015 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 2373 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 2581 of file ScalarEvolution.cpp.

References getNotSCEV(), and getSMaxExpr().

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

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

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

Referenced by 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 2822 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 2806 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 2666 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(), and isMulSExtable().

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

References llvm::ARM_PROC::A, llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::SmallVectorImpl< T >::clear(), llvm::dyn_cast(), 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::FoldingSetNodeID::Intern(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::scUDivExpr, llvm::SmallVectorTemplateCommon< T >::size(), and llvm::APInt::urem().

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

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

Definition at line 2477 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 2902 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 2587 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 2918 of file ScalarEvolution.cpp.

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

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

Definition at line 2629 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), ID, 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 3309 of file ScalarEvolution.cpp.

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

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

Definition at line 901 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::ConstantRange::contains(), 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::FoldingSetNodeID::Intern(), isKnownNegative(), isKnownPositive(), isLoopBackedgeGuardedByCond(), isLoopEntryGuardedByCond(), isSCEVable(), N, llvm::PPCISD::SC, llvm::scZeroExtend, llvm::A64DB::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 7501 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 7313 of file ScalarEvolution.cpp.

References getBackedgeTakenCount().

Referenced by 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 7613 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 5971 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 5979 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 5983 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 5987 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 5975 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 5991 of file ScalarEvolution.cpp.

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

References llvm::dyn_cast(), llvm::BranchInst::getCondition(), llvm::LoopBase< N, M >::getHeader(), llvm::LoopBase< N, M >::getLoopLatch(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), and llvm::BranchInst::isUnconditional().

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

References llvm::dyn_cast(), llvm::BranchInst::getCondition(), llvm::LoopBase< N, M >::getHeader(), llvm::LoopBase< N, M >::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 7497 of file ScalarEvolution.cpp.

References getLoopDisposition(), and LoopInvariant.

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

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 2659 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
	)

inlinestatic

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

Definition at line 193 of file ScalarEvolution.h.

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

void ScalarEvolution::print	(	raw_ostream &	O,
		const Module *	M = `0`
	)		const

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

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

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

References getBlockDisposition(), and ProperlyDominatesBlock.

Referenced by DoInitialMatch(), and SimplifyICmpOperands().

void ScalarEvolution::releaseMemory ( )

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

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::clear(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT >, KeyT, ValueT, KeyInfoT >::clear(), llvm::DenseSet< ValueT, ValueInfoT >::empty(), I, and llvm::BumpPtrAllocator::Reset().

Referenced by verifyAnalysis().

bool ScalarEvolution::runOnFunction ( Function & F )

virtual

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

Implements llvm::FunctionPass.

Definition at line 7267 of file ScalarEvolution.cpp.

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

inlinestatic

Definition at line 197 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 5694 of file ScalarEvolution.cpp.

Referenced by isKnownPredicate().

void ScalarEvolution::verifyAnalysis ( ) const

virtual

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

Reimplemented from llvm::Pass.

Definition at line 7671 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< N, M >::rbegin(), releaseMemory(), llvm::LoopBase< N, M >::rend(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::size(), and VerifySCEV.

Friends And Related Function Documentation

friend class SCEVCallbackVH

friend

Definition at line 216 of file ScalarEvolution.h.

Referenced by getSCEV().

friend class SCEVExpander

friend

Definition at line 217 of file ScalarEvolution.h.

friend class SCEVUnknown

friend

Definition at line 218 of file ScalarEvolution.h.

Referenced by getUnknown().

Member Data Documentation

scalar Scalar Evolution true char ScalarEvolution::ID = 0

static

Definition at line 548 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:

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