#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 *	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 *AllocTy)
const SCEV *	getAlignOfExpr (Type *AllocTy)
const SCEV *	getOffsetOfExpr (StructType *STy, unsigned FieldNo)
const SCEV *	getOffsetOfExpr (Type CTy, Constant 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)
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
Static Public Member Functions
static SCEV::NoWrapFlags	maskFlags (SCEV::NoWrapFlags Flags, int Mask)
static SCEV::NoWrapFlags	setFlags (SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
static SCEV::NoWrapFlags	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 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 6613 of file ScalarEvolution.cpp.

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

Member Function Documentation

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

Definition at line 199 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 6925 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 4117 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(), llvm::ARM_PROC::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 4156 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 1458 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), AddOne(), llvm::FoldingSetNodeID::AddPointer(), llvm::BumpPtrAllocator::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::SCEVCastExpr::getType(), getType(), llvm::SCEV::getType(), getTypeSizeInBits(), GroupByComplexity(), llvm::ARM_PROC::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 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(), and llvm::SCEVRewriter::visitAddExpr().

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

Definition at line 581 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 588 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 2243 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::SCEVRewriter::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 2261 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::BumpPtrAllocator::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(), getType(), llvm::ARM_PROC::I, ID, llvm::FoldingSetImpl::InsertNode(), llvm::FoldingSetNodeID::Intern(), isKnownNonNegative(), isLoopInvariant(), maskFlags(), llvm::SmallVectorTemplateBase< T, isPodLike >::pop_back(), llvm::scAddRecExpr, setFlags(), llvm::SCEVAddRecExpr::setNoWrapFlags(), llvm::SmallVectorTemplateCommon< T, typename >::size(), 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 619 of file ScalarEvolution.h.

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

const SCEV * ScalarEvolution::getAlignOfExpr ( Type * AllocTy )

getAlignOfExpr - Return an expression for alignof on the given type.

Definition at line 2606 of file ScalarEvolution.cpp.

References llvm::CallingConv::C, llvm::ConstantFoldConstantExpression(), llvm::ConstantExpr::getAlignOf(), getEffectiveSCEVType(), getSCEV(), getTruncateOrZeroExtend(), and llvm::PointerType::getUnqual().

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

References llvm::SCEV::FlagNW, getAddRecExpr(), getEffectiveSCEVType(), getSignExtendExpr(), getTruncateOrNoop(), llvm::SCEV::getType(), getTypeSizeInBits(), getZeroExtendExpr(), llvm::ARM_PROC::I, 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 4017 of file ScalarEvolution.cpp.

Referenced by canExpandBackedgeTakenCount(), getLoopBackedgeTakenCounts(), 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 6850 of file ScalarEvolution.cpp.

References DoesNotDominateBlock, and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::insert().

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(), 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 2714 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 2700 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(), getAlignOfExpr(), 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 4002 of file ScalarEvolution.cpp.

Referenced by getSmallConstantTripCount(), and getSmallConstantTripMultiple().

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

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::insert(), and LoopVariant.

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 4024 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 3195 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 2762 of file ScalarEvolution.cpp.

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

Referenced by BinomialCoefficient(), getNotSCEV(), llvm::BoUpSLP::isConsecutiveAccess(), 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 1861 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::BumpPtrAllocator::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(), getType(), llvm::SCEVNAryExpr::getType(), getTypeSizeInBits(), GroupByComplexity(), llvm::ARM_PROC::I, ID, llvm::FoldingSetImpl::InsertNode(), llvm::FoldingSetNodeID::Intern(), isKnownNonNegative(), isLoopInvariant(), maskFlags(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::SmallVectorTemplateBase< T, isPodLike >::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(), getAddExpr(), getExactSDiv(), getMulExpr(), getNegativeSCEV(), getSignExtendExpr(), getTruncateExpr(), getUDivExpr(), getZeroExtendExpr(), and llvm::SCEVRewriter::visitMulExpr().

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

Definition at line 598 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 606 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 2737 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 2844 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 2827 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 2811 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 2749 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	(	StructType *	STy,
		unsigned	FieldNo
	)

getOffsetOfExpr - Return an expression for offsetof on the given field.

Definition at line 2615 of file ScalarEvolution.cpp.

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

const SCEV * ScalarEvolution::getOffsetOfExpr	(	Type *	CTy,
		Constant *	FieldNo
	)

getOffsetOfExpr - Return an expression for offsetof on the given field.

Definition at line 2632 of file ScalarEvolution.cpp.

References llvm::CallingConv::C, llvm::ConstantFoldConstantExpression(), getEffectiveSCEVType(), llvm::ConstantExpr::getOffsetOf(), getSCEV(), 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 2907 of file ScalarEvolution.cpp.

References llvm::SCEV::getType(), llvm::ARM_PROC::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 2720 of file ScalarEvolution.cpp.

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

Referenced by llvm::IVUsers::AddUsersImpl(), llvm::DependenceAnalysis::depends(), DoInitialMatch(), findIVOperand(), FindLoopCounter(), genLoopLimit(), getAlignOfExpr(), getOffsetOfExpr(), getSCEVAtScope(), getSizeOfExpr(), llvm::DependenceAnalysis::getSplitIteration(), llvm::BoUpSLP::isConsecutiveAccess(), isExistingPhi(), isHighCostExpansion(), isProfitableChain(), isSimpleIVUser(), 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 5009 of file ScalarEvolution.cpp.

References llvm::CallingConv::C, and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::insert().

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 5311 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 3414 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 1156 of file ScalarEvolution.cpp.

References llvm::FoldingSetNodeID::AddInteger(), llvm::FoldingSetNodeID::AddPointer(), llvm::ConstantRange::contains(), 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(), 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(), and llvm::SCEVRewriter::visitSignExtendExpr().

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

getSizeOfExpr - Return an expression for sizeof on the given type.

Definition at line 2590 of file ScalarEvolution.cpp.

References llvm::CallingConv::C, llvm::ConstantFoldConstantExpression(), getConstant(), getContext(), getEffectiveSCEVType(), llvm::DataLayout::getIntPtrType(), 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.

Definition at line 3941 of file ScalarEvolution.cpp.

References llvm::dyn_cast(), llvm::APInt::getActiveBits(), getExitCount(), 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 3970 of file ScalarEvolution.cpp.

References llvm::dyn_cast(), llvm::APInt::getActiveBits(), getAddExpr(), getConstant(), getCouldNotCompute(), getExitCount(), 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 2370 of file ScalarEvolution.cpp.

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

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

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

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

Definition at line 2578 of file ScalarEvolution.cpp.

References getNotSCEV(), and getSMaxExpr().

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

Definition at line 819 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::A64DB::ST.

Referenced by genLoopLimit(), getAddExpr(), getTruncateOrNoop(), getTruncateOrSignExtend(), getTruncateOrZeroExtend(), llvm::SCEVExpander::replaceCongruentIVs(), and llvm::SCEVRewriter::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 2859 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 2794 of file ScalarEvolution.cpp.

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

Referenced by genLoopLimit(), 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 2778 of file ScalarEvolution.cpp.

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

Referenced by BinomialCoefficient(), getAlignOfExpr(), 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 2679 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 2123 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(), and llvm::SCEVRewriter::visitUDivExpr().

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

Definition at line 2474 of file ScalarEvolution.cpp.

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

Referenced by getUMaxExpr(), getUMaxFromMismatchedTypes(), getUMinExpr(), and llvm::SCEVRewriter::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 2874 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 2584 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 2890 of file ScalarEvolution.cpp.

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

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

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

References llvm::ConstantRange::add(), llvm::CallingConv::C, llvm::ComputeMaskedBits(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::find(), llvm::SCEV::FlagNUW, getMaxBackedgeTakenCount(), llvm::APInt::getMaxValue(), GetMinTrailingZeros(), llvm::APInt::getMinValue(), getNoopOrZeroExtend(), llvm::User::getOperand(), getSignedRange(), llvm::SCEV::getType(), getTypeSizeInBits(), llvm::ConstantRange::getUnsignedMax(), llvm::ConstantRange::getUnsignedMin(), if(), llvm::APInt::isMinValue(), llvm::APIntOps::lshr(), llvm::ConstantRange::multiply(), llvm::SExt, llvm::ConstantRange::sextOrTrunc(), llvm::APIntOps::shl(), llvm::ConstantRange::signExtend(), llvm::ConstantRange::smax(), llvm::Trunc, llvm::ConstantRange::truncate(), llvm::ConstantRange::udiv(), llvm::ConstantRange::umax(), llvm::APIntOps::umax(), llvm::APIntOps::umin(), Y, llvm::ConstantRange::zeroExtend(), and llvm::ConstantRange::zextOrTrunc().

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

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

Definition at line 898 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::A64DB::ST, llvm::ConstantRange::truncate(), llvm::ConstantRange::zeroExtend(), and llvm::ConstantRange::zextOrTrunc().

Referenced by getAnyExtendExpr(), getNoopOrZeroExtend(), getSignExtendExpr(), getTruncateOrZeroExtend(), getUDivExpr(), getUMaxFromMismatchedTypes(), getUMinFromMismatchedTypes(), and llvm::SCEVRewriter::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 6845 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 6664 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 6950 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 5908 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 5916 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 5920 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 5924 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 5912 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 5928 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 6034 of file ScalarEvolution.cpp.

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

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

References getLoopDisposition(), and LoopInvariant.

Referenced by genLoopLimit(), getAddExpr(), getAddRecExpr(), getMulExpr(), 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 2672 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::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 192 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 6703 of file ScalarEvolution.cpp.

References llvm::LoopBase< BlockT, LoopT >::begin(), llvm::LoopBase< BlockT, LoopT >::end(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), getSCEV(), getSCEVAtScope(), llvm::ARM_PROC::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 6929 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 6627 of file ScalarEvolution.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::begin(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::clear(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT >, KeyT, ValueT, KeyInfoT >::clear(), llvm::FoldingSetImpl::clear(), llvm::DenseSet< ValueT, ValueInfoT >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::end(), llvm::ARM_PROC::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 6618 of file ScalarEvolution.cpp.

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

Definition at line 195 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 5631 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 7008 of file ScalarEvolution.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::begin(), llvm::dbgs(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::end(), getLoopBackedgeTakenCounts(), llvm::ARM_PROC::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 215 of file ScalarEvolution.h.

Referenced by getSCEV().

friend class SCEVExpander [friend]

Definition at line 216 of file ScalarEvolution.h.

friend class SCEVUnknown [friend]

Definition at line 217 of file ScalarEvolution.h.

Referenced by getUnknown().

Member Data Documentation

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

Definition at line 547 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