This class uses information about analyze scalars to rewrite expressions in canonical form. More...

#include "llvm/Analysis/ScalarEvolutionExpander.h"

Inheritance diagram for llvm::SCEVExpander:

Collaboration diagram for llvm::SCEVExpander:

Public Member Functions
	SCEVExpander (ScalarEvolution &se, const DataLayout &DL, const char *name)
	Construct a SCEVExpander in "canonical" mode. More...

	~SCEVExpander ()

void	setDebugType (const char *s)

void	clear ()
	Erase the contents of the InsertedExpressions map so that users trying to expand the same expression into multiple BasicBlocks or different places within the same BasicBlock can do so. More...

bool	isHighCostExpansion (const SCEV Expr, Loop L, const Instruction *At=nullptr)
	Return true for expressions that may incur non-trivial cost to evaluate at runtime. More...

PHINode *	getOrInsertCanonicalInductionVariable (const Loop L, Type Ty)
	This method returns the canonical induction variable of the specified type for the specified loop (inserting one if there is none). More...

Instruction *	getIVIncOperand (Instruction IncV, Instruction InsertPos, bool allowScale)
	Return the induction variable increment's IV operand. More...

bool	hoistIVInc (Instruction IncV, Instruction InsertPos)
	Utility for hoisting an IV increment. More...

unsigned	replaceCongruentIVs (Loop L, const DominatorTree DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetTransformInfo *TTI=nullptr)
	replace congruent phis with their most canonical representative. More...

Value *	expandCodeFor (const SCEV SH, Type Ty, Instruction *I)
	Insert code to directly compute the specified SCEV expression into the program. More...

Value *	expandCodeFor (const SCEV SH, Type Ty=nullptr)
	Insert code to directly compute the specified SCEV expression into the program. More...

Value *	expandCodeForPredicate (const SCEVPredicate Pred, Instruction Loc)
	Generates a code sequence that evaluates this predicate. More...

Value *	expandEqualPredicate (const SCEVEqualPredicate Pred, Instruction Loc)
	A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVEqualPredicate. More...

Value *	generateOverflowCheck (const SCEVAddRecExpr AR, Instruction Loc, bool Signed)
	Generates code that evaluates if the `AR` expression will overflow. More...

Value *	expandWrapPredicate (const SCEVWrapPredicate P, Instruction Loc)
	A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVWrapPredicate. More...

Value *	expandUnionPredicate (const SCEVUnionPredicate Pred, Instruction Loc)
	A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVUnionPredicate. More...

void	setIVIncInsertPos (const Loop L, Instruction Pos)
	Set the current IV increment loop and position. More...

void	setPostInc (const PostIncLoopSet &L)
	Enable post-inc expansion for addrecs referring to the given loops. More...

void	clearPostInc ()
	Disable all post-inc expansion. More...

void	disableCanonicalMode ()
	Disable the behavior of expanding expressions in canonical form rather than in a more literal form. More...

void	enableLSRMode ()

void	setInsertPoint (Instruction *IP)
	Set the current insertion point. More...

void	clearInsertPoint ()
	Clear the current insertion point. More...

bool	isInsertedInstruction (Instruction *I) const
	Return true if the specified instruction was inserted by the code rewriter. More...

void	setChainedPhi (PHINode *PN)

Value *	getExactExistingExpansion (const SCEV S, const Instruction At, Loop *L)
	Try to find existing LLVM IR value for S available at the point At. More...

Optional< ScalarEvolution::ValueOffsetPair >	getRelatedExistingExpansion (const SCEV S, const Instruction At, Loop *L)
	Try to find the ValueOffsetPair for S. More...

Public Member Functions inherited from llvm::SCEVVisitor< SCEVExpander, Value *>
Value *	visit (const SCEV *S)

Value *	visitCouldNotCompute (const SCEVCouldNotCompute *S)

Friends
struct	SCEVVisitor< SCEVExpander, Value *>

Detailed Description

This class uses information about analyze scalars to rewrite expressions in canonical form.

Clients should create an instance of this class when rewriting is needed, and destroy it when finished to allow the release of the associated memory.

Definition at line 46 of file ScalarEvolutionExpander.h.

Constructor & Destructor Documentation

◆ SCEVExpander()

llvm::SCEVExpander::SCEVExpander	(	ScalarEvolution &	se,
		const DataLayout &	DL,
		const char *	name
	)

inlineexplicit

Construct a SCEVExpander in "canonical" mode.

Definition at line 142 of file ScalarEvolutionExpander.h.

◆ ~SCEVExpander()

llvm::SCEVExpander::~SCEVExpander ( )

inline

Definition at line 152 of file ScalarEvolutionExpander.h.

References assert(), and llvm::SmallVectorBase::empty().

Member Function Documentation

◆ clear()

void llvm::SCEVExpander::clear ( )

inline

Erase the contents of the InsertedExpressions map so that users trying to expand the same expression into multiple BasicBlocks or different places within the same BasicBlock can do so.

Definition at line 164 of file ScalarEvolutionExpander.h.

References llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::clear(), and llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::clear().

Referenced by mayLoopAccessLocation(), and mayUsePostIncMode().

◆ clearInsertPoint()

void llvm::SCEVExpander::clearInsertPoint ( )

inline

Clear the current insertion point.

This is useful if the instruction that had been serving as the insertion point may have been deleted.

Definition at line 279 of file ScalarEvolutionExpander.h.

References llvm::IRBuilderBase::ClearInsertionPoint().

Referenced by ConvertToSInt().

◆ clearPostInc()

void llvm::SCEVExpander::clearPostInc ( )

inline

Disable all post-inc expansion.

Definition at line 253 of file ScalarEvolutionExpander.h.

References llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::clear(), and llvm::SmallPtrSetImplBase::clear().

Referenced by canFoldIVIncExpr(), and mayUsePostIncMode().

◆ disableCanonicalMode()

void llvm::SCEVExpander::disableCanonicalMode ( )

inline

Disable the behavior of expanding expressions in canonical form rather than in a more literal form.

Non-canonical mode is useful for late optimization passes.

Definition at line 264 of file ScalarEvolutionExpander.h.

Referenced by mayUsePostIncMode().

◆ enableLSRMode()

void llvm::SCEVExpander::enableLSRMode ( )

inline

Definition at line 266 of file ScalarEvolutionExpander.h.

Referenced by mayUsePostIncMode().

◆ expandCodeFor() [1/2]

Value * SCEVExpander::expandCodeFor	(	const SCEV *	SH,
		Type *	Ty,
		Instruction *	I
	)

Insert code to directly compute the specified SCEV expression into the program.

The inserted code is inserted into the specified block.

Definition at line 1679 of file ScalarEvolutionExpander.cpp.

Referenced by asmClobbersCTR(), canFoldIVIncExpr(), ConvertToSInt(), llvm::InnerLoopVectorizer::emitTransformedIndex(), expandBounds(), genLoopLimit(), llvm::InnerLoopVectorizer::getOrCreateTripCount(), isHighCostExpansion(), isIgnorableInst(), isLoadConditional(), mayLoopAccessLocation(), mayUsePostIncMode(), llvm::LoopPredicationPass::run(), truncateIVUse(), and llvm::UnrollRuntimeLoopRemainder().

◆ expandCodeFor() [2/2]

Value * SCEVExpander::expandCodeFor	(	const SCEV *	SH,
		Type *	Ty = `nullptr`
	)

Insert code to directly compute the specified SCEV expression into the program.

The inserted code is inserted into the SCEVExpander's current insertion point. If a type is specified, the result will be expanded to have that type, with a cast if necessary.

Definition at line 1685 of file ScalarEvolutionExpander.cpp.

References assert(), contains(), D, expand(), llvm::BasicBlock::getFirstInsertionPt(), llvm::Instruction::getFunction(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::Type::getInt8PtrTy(), llvm::Type::getInt8Ty(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::Instruction::getParent(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::Type::getPointerElementType(), llvm::SCEV::getSCEVType(), llvm::ConstantInt::getSigned(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::PPCISD::SC, llvm::scConstant, and llvm::SCEVExprContains().

◆ expandCodeForPredicate()

Value * SCEVExpander::expandCodeForPredicate	(	const SCEVPredicate *	Pred,
		Instruction *	Loc
	)

Generates a code sequence that evaluates this predicate.

The inserted instructions will be at position Loc. The result will be of type i1 and will have a value of 0 when the predicate is false and 1 otherwise.

Definition at line 2122 of file ScalarEvolutionExpander.cpp.

References assert(), llvm::SCEVPredicate::getKind(), llvm_unreachable, llvm::SCEVPredicate::P_Equal, llvm::SCEVPredicate::P_Union, and llvm::SCEVPredicate::P_Wrap.

Referenced by isHighCostExpansion().

◆ expandEqualPredicate()

Value * SCEVExpander::expandEqualPredicate	(	const SCEVEqualPredicate *	Pred,
		Instruction *	Loc
	)

A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVEqualPredicate.

Definition at line 2138 of file ScalarEvolutionExpander.cpp.

References llvm::SCEVEqualPredicate::getLHS(), llvm::SCEVEqualPredicate::getRHS(), llvm::SCEV::getType(), and I.

Referenced by isHighCostExpansion().

◆ expandUnionPredicate()

Value * SCEVExpander::expandUnionPredicate	(	const SCEVUnionPredicate *	Pred,
		Instruction *	Loc
	)

A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVUnionPredicate.

Definition at line 2270 of file ScalarEvolutionExpander.cpp.

References Check(), D, llvm::ScalarEvolution::dominates(), llvm::dyn_cast(), llvm::IntegerType::get(), llvm::Value::getContext(), llvm::Constant::getNullValue(), llvm::SCEVUnionPredicate::getPredicates(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::isZero(), and llvm::PPCISD::SC.

Referenced by isHighCostExpansion().

◆ expandWrapPredicate()

Value * SCEVExpander::expandWrapPredicate	(	const SCEVWrapPredicate *	P,
		Instruction *	Loc
	)

A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVWrapPredicate.

Definition at line 2245 of file ScalarEvolutionExpander.cpp.

References llvm::Value::getContext(), llvm::SCEVWrapPredicate::getExpr(), llvm::ConstantInt::getFalse(), llvm::SCEVWrapPredicate::getFlags(), llvm::SCEVWrapPredicate::IncrementNSSW, and llvm::SCEVWrapPredicate::IncrementNUSW.

Referenced by isHighCostExpansion().

◆ generateOverflowCheck()

Value * SCEVExpander::generateOverflowCheck	(	const SCEVAddRecExpr *	AR,
		Instruction *	Loc,
		bool	Signed
	)

Generates code that evaluates if the AR expression will overflow.

Definition at line 2148 of file ScalarEvolutionExpander.cpp.

References assert(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVAddRecExpr::getStepRecurrence(), and llvm::SCEVAddRecExpr::isAffine().

Referenced by isHighCostExpansion().

◆ getExactExistingExpansion()

Value * SCEVExpander::getExactExistingExpansion	(	const SCEV *	S,
		const Instruction *	At,
		Loop *	L
	)

Try to find existing LLVM IR value for S available at the point At.

Definition at line 1996 of file ScalarEvolutionExpander.cpp.

References llvm::Optional< T >::getValue().

Referenced by setChainedPhi().

◆ getIVIncOperand()

Instruction * SCEVExpander::getIVIncOperand	(	Instruction *	IncV,
		Instruction *	InsertPos,
		bool	allowScale
	)

Return the induction variable increment's IV operand.

getIVIncOperand returns an induction variable increment's induction variable operand.

If allowScale is set, any type of GEP is allowed as long as the nonIV operands dominate InsertPos.

If allowScale is not set, ensure that a GEP increment conforms to one of the simple patterns generated by getAddRecExprPHILiterally and expandAddtoGEP. If the pattern isn't recognized, return NULL.

Definition at line 915 of file ScalarEvolutionExpander.cpp.

References llvm::MCID::Add, llvm::dyn_cast(), E, llvm::Type::getInt1PtrTy(), llvm::Type::getInt8PtrTy(), llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), I, llvm::User::op_begin(), and llvm::User::op_end().

Referenced by isHighCostExpansion().

◆ getOrInsertCanonicalInductionVariable()

PHINode * SCEVExpander::getOrInsertCanonicalInductionVariable	(	const Loop *	L,
		Type *	Ty
	)

This method returns the canonical induction variable of the specified type for the specified loop (inserting one if there is none).

getOrInsertCanonicalInductionVariable - This method returns the canonical induction variable of the specified type for the specified loop (inserting one if there is none).

A canonical induction variable starts at zero and steps by one on each iteration.

Definition at line 1837 of file ScalarEvolutionExpander.cpp.

References assert(), llvm::SCEV::FlagAnyWrap, llvm::BasicBlock::front(), llvm::LoopBase< BlockT, LoopT >::getHeader(), H, and llvm::Type::isIntegerTy().

Referenced by isHighCostExpansion().

◆ getRelatedExistingExpansion()

Optional< ScalarEvolution::ValueOffsetPair > SCEVExpander::getRelatedExistingExpansion	(	const SCEV *	S,
		const Instruction *	At,
		Loop *	L
	)

Try to find the ValueOffsetPair for S.

The function is mainly used to check whether S can be expanded cheaply. If this returns a non-None value, we know we can codegen the ValueOffsetPair into a suitable expansion identical with S so that S can be expanded cheaply.

L is a hint which tells in which loop to look for the suitable value. On success return value which is equivalent to the expanded S at point At. Return nullptr if value was not found.

Note that this function does not perform an exhaustive search. I.e if it didn't find any value it does not mean that there is no such value.

Definition at line 2006 of file ScalarEvolutionExpander.cpp.

References llvm::BasicBlock::back(), getBitWidth(), llvm::Module::getDataLayout(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::LoopBase< BlockT, LoopT >::getExitingBlocks(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::SCEV::getSCEVType(), llvm::SCEV::getType(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::DataLayout::isIllegalInteger(), llvm::PatternMatch::m_Br(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::match(), llvm::None, llvm::PPCISD::SC, llvm::scConstant, llvm::scSignExtend, llvm::scTruncate, llvm::scUnknown, and llvm::scZeroExtend.

Referenced by setChainedPhi().

◆ hoistIVInc()

bool SCEVExpander::hoistIVInc	(	Instruction *	IncV,
		Instruction *	InsertPos
	)

Utility for hoisting an IV increment.

hoistStep - Attempt to hoist a simple IV increment above InsertPos to make it available to other uses in this loop.

Recursively hoist any operands, until we reach a value that dominates InsertPos.

Definition at line 982 of file ScalarEvolutionExpander.cpp.

References llvm::DominatorTree::dominates(), E, llvm::PointerType::get(), llvm::PointerType::getAddressSpace(), llvm::Type::getInt1Ty(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, llvm::Type::isPointerTy(), llvm::Instruction::moveBefore(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SmallVectorTemplateCommon< T >::rbegin(), and llvm::SmallVectorTemplateCommon< T >::rend().

Referenced by isHighCostExpansion(), and truncateIVUse().

◆ isHighCostExpansion()

bool llvm::SCEVExpander::isHighCostExpansion	(	const SCEV *	Expr,
		Loop *	L,
		const Instruction *	At = `nullptr`
	)

inline

Return true for expressions that may incur non-trivial cost to evaluate at runtime.

At is an optional parameter which specifies point in code where user is going to expand this expression. Sometimes this knowledge can lead to a more accurate cost estimation.

Definition at line 177 of file ScalarEvolutionExpander.h.

References expandCodeFor(), expandCodeForPredicate(), expandEqualPredicate(), expandUnionPredicate(), expandWrapPredicate(), generateOverflowCheck(), getIVIncOperand(), getOrInsertCanonicalInductionVariable(), hoistIVInc(), I, P, replaceCongruentIVs(), and Signed.

Referenced by canExpandBackedgeTakenCount(), ConvertToSInt(), and llvm::UnrollRuntimeLoopRemainder().

◆ isInsertedInstruction()

bool llvm::SCEVExpander::isInsertedInstruction ( Instruction * I ) const

inline

Return true if the specified instruction was inserted by the code rewriter.

If so, the client should not modify the instruction.

Definition at line 285 of file ScalarEvolutionExpander.h.

References llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::count().

Referenced by mayUsePostIncMode().

◆ replaceCongruentIVs()

unsigned SCEVExpander::replaceCongruentIVs	(	Loop *	L,
		const DominatorTree *	DT,
		SmallVectorImpl< WeakTrackingVH > &	DeadInsts,
		const TargetTransformInfo *	TTI = `nullptr`
	)

replace congruent phis with their most canonical representative.

replaceCongruentIVs - Check for congruent phis in this loop header and replace them with their most canonical representative.

Return the number of phis eliminated.

This does not depend on any SCEVExpander state but should be used in the same context that SCEVExpander is used.

Definition at line 1861 of file ScalarEvolutionExpander.cpp.

References llvm::IRBuilder< T, Inserter >::CreateTruncOrBitCast(), llvm::dbgs(), DEBUG_WITH_TYPE, llvm::dyn_cast(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::BasicBlock::getFirstInsertionPt(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::ilist_node_with_parent< NodeTy, ParentTy, Options >::getNextNode(), llvm::Instruction::getParent(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::Type::isIntegerTy(), llvm::Type::isPointerTy(), llvm::TargetTransformInfo::isTruncateFree(), llvm::BasicBlock::phis(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::Value::replaceAllUsesWith(), llvm::IRBuilderBase::SetCurrentDebugLocation(), llvm::SimplifyInstruction(), SimplifyPHINode(), llvm::sort(), and std::swap().

Referenced by isHighCostExpansion(), and ReduceLoopStrength().

◆ setChainedPhi()

void llvm::SCEVExpander::setChainedPhi ( PHINode * PN )

inline

Definition at line 289 of file ScalarEvolutionExpander.h.

References expand(), llvm::ScalarEvolution::getContext(), getExactExistingExpansion(), getRelatedExistingExpansion(), llvm::SCEVConstant::getValue(), llvm::SCEVUnknown::getValue(), and llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::insert().

Referenced by mayUsePostIncMode().

◆ setDebugType()

void llvm::SCEVExpander::setDebugType ( const char * s )

inline

Definition at line 158 of file ScalarEvolutionExpander.h.

Referenced by mayUsePostIncMode(), and ReduceLoopStrength().

◆ setInsertPoint()

void llvm::SCEVExpander::setInsertPoint ( Instruction * IP )

inline

Set the current insertion point.

This is useful if multiple calls to expandCodeFor() are going to be made with the same insert point and the insert point may be moved during one of the expansions (e.g. if the insert point is not a block terminator).

Definition at line 272 of file ScalarEvolutionExpander.h.

References assert(), and llvm::IRBuilderBase::SetInsertPoint().

Referenced by mayUsePostIncMode().

◆ setIVIncInsertPos()

void llvm::SCEVExpander::setIVIncInsertPos	(	const Loop *	L,
		Instruction *	Pos
	)

inline

Set the current IV increment loop and position.

Definition at line 237 of file ScalarEvolutionExpander.h.

References assert().

Referenced by mayUsePostIncMode().

◆ setPostInc()

void llvm::SCEVExpander::setPostInc ( const PostIncLoopSet & L )

inline

Enable post-inc expansion for addrecs referring to the given loops.

Post-inc expansion is only supported in non-canonical mode.

Definition at line 246 of file ScalarEvolutionExpander.h.

References assert().

Referenced by mayUsePostIncMode().

Friends And Related Function Documentation

◆ SCEVVisitor< SCEVExpander, Value *>

friend struct SCEVVisitor< SCEVExpander, Value * >

friend

Definition at line 138 of file ScalarEvolutionExpander.h.

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

include/llvm/Analysis/ScalarEvolutionExpander.h
lib/Analysis/ScalarEvolutionExpander.cpp

Public Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

◆ SCEVExpander()

◆ ~SCEVExpander()

Member Function Documentation

◆ clear()

◆ clearInsertPoint()

◆ clearPostInc()

◆ disableCanonicalMode()

◆ enableLSRMode()

◆ expandCodeFor() [1/2]

◆ expandCodeFor() [2/2]

◆ expandCodeForPredicate()

◆ expandEqualPredicate()

◆ expandUnionPredicate()

◆ expandWrapPredicate()

◆ generateOverflowCheck()

◆ getExactExistingExpansion()

◆ getIVIncOperand()

◆ getOrInsertCanonicalInductionVariable()

◆ getRelatedExistingExpansion()

◆ hoistIVInc()

◆ isHighCostExpansion()

◆ isInsertedInstruction()

◆ replaceCongruentIVs()

◆ setChainedPhi()

◆ setDebugType()

◆ setInsertPoint()

◆ setIVIncInsertPos()

◆ setPostInc()

Friends And Related Function Documentation

◆ SCEVVisitor< SCEVExpander, Value *>