Bottom Up SLP Vectorizer. More...

Classes
struct	EdgeInfo
	This structure holds any data we need about the edges being traversed during buildTree_rec(). More...

class	LookAheadHeuristics
	A helper class used for scoring candidates for two consecutive lanes. More...

class	ShuffleInstructionBuilder
	Merges shuffle masks and emits final shuffle instruction, if required. More...

class	VLOperands
	A helper data structure to hold the operands of a vector of instructions. More...

Public Types
using	ValueList = SmallVector< Value *, 8 >

using	InstrList = SmallVector< Instruction *, 16 >

using	ValueSet = SmallPtrSet< Value *, 16 >

using	StoreList = SmallVector< StoreInst *, 8 >

using	ExtraValueToDebugLocsMap = MapVector< Value , SmallVector< Instruction , 2 > >

using	OrdersType = SmallVector< unsigned, 4 >

Public Member Functions
	BoUpSLP (Function Func, ScalarEvolution Se, TargetTransformInfo Tti, TargetLibraryInfo TLi, AAResults Aa, LoopInfo Li, DominatorTree Dt, AssumptionCache AC, DemandedBits DB, const DataLayout DL, OptimizationRemarkEmitter *ORE)

Value *	vectorizeTree ()
	Vectorize the tree that starts with the elements in `VL`.

Value *	vectorizeTree (ExtraValueToDebugLocsMap &ExternallyUsedValues, Instruction *ReductionRoot=nullptr)
	Vectorize the tree but with the list of externally used values `ExternallyUsedValues`.

InstructionCost	getSpillCost () const

InstructionCost	getTreeCost (ArrayRef< Value * > VectorizedVals=std::nullopt)

void	buildTree (ArrayRef< Value * > Roots, const SmallDenseSet< Value * > &UserIgnoreLst)
	Construct a vectorizable tree that starts at `Roots`, ignoring users for the purpose of scheduling and extraction in the `UserIgnoreLst`.

void	buildTree (ArrayRef< Value * > Roots)
	Construct a vectorizable tree that starts at `Roots`.

bool	isVectorizedFirstNode () const
	Checks if the very first tree node is going to be vectorized.

Instruction *	getFirstNodeMainOp () const
	Returns the main instruction for the very first node.

bool	doesRootHaveInTreeUses () const
	Returns whether the root node has in-tree uses.

void	buildExternalUses (const ExtraValueToDebugLocsMap &ExternallyUsedValues={})
	Builds external uses of the vectorized scalars, i.e.

void	deleteTree ()
	Clear the internal data structures that are created by 'buildTree'.

unsigned	getTreeSize () const

void	optimizeGatherSequence ()
	Perform LICM and CSE on the newly generated gather sequences.

std::optional< OrdersType >	findReusedOrderedScalars (const TreeEntry &TE)
	Checks if the specified gather tree entry `TE` can be represented as a shuffled vector entry + (possibly) permutation with other gathers.

std::optional< OrdersType >	findPartiallyOrderedLoads (const TreeEntry &TE)
	Sort loads into increasing pointers offsets to allow greater clustering.

std::optional< OrdersType >	getReorderingData (const TreeEntry &TE, bool TopToBottom)
	Gets reordering data for the given tree entry.

void	reorderTopToBottom ()
	Reorders the current graph to the most profitable order starting from the root node to the leaf nodes.

void	reorderBottomToTop (bool IgnoreReorder=false)
	Reorders the current graph to the most profitable order starting from leaves to the root.

unsigned	getVectorElementSize (Value *V)

void	computeMinimumValueSizes ()
	Compute the minimum type sizes required to represent the entries in a vectorizable tree.

unsigned	getMaxVecRegSize () const

unsigned	getMinVecRegSize () const

unsigned	getMinVF (unsigned Sz) const

unsigned	getMaximumVF (unsigned ElemWidth, unsigned Opcode) const

unsigned	canMapToVector (Type *T, const DataLayout &DL) const
	Check if homogeneous aggregate is isomorphic to some VectorType.

bool	isTreeTinyAndNotFullyVectorizable (bool ForReduction=false) const

bool	isLoadCombineReductionCandidate (RecurKind RdxKind) const
	Assume that a legal-sized 'or'-reduction of shifted/zexted loaded values can be load combined in the backend.

bool	isLoadCombineCandidate () const
	Assume that a vector of stores of bitwise-or/shifted/zexted loaded values can be load combined in the backend.

OptimizationRemarkEmitter *	getORE ()

std::optional< int >	findBestRootPair (ArrayRef< std::pair< Value , Value > > Candidates, int Limit=LookAheadHeuristics::ScoreFail)
	Evaluate each pair in `Candidates` and return index into `Candidates` for a pair which have highest score deemed to have best chance to form root of profitable tree to vectorize.

bool	isDeleted (Instruction *I) const
	Checks if the instruction is marked for deletion.

void	eraseInstruction (Instruction *I)
	Removes an instruction from its block and eventually deletes it.

bool	isAnalyzedReductionRoot (Instruction *I) const
	Checks if the instruction was already analyzed for being possible reduction root.

void	analyzedReductionRoot (Instruction *I)
	Register given instruction as already analyzed for being possible reduction root.

bool	areAnalyzedReductionVals (ArrayRef< Value * > VL) const
	Checks if the provided list of reduced values was checked already for vectorization.

void	analyzedReductionVals (ArrayRef< Value * > VL)
	Adds the list of reduced values to list of already checked values for the vectorization.

void	clearReductionData ()
	Clear the list of the analyzed reduction root instructions.

bool	isAnyGathered (const SmallDenseSet< Value * > &Vals) const
	Checks if the given value is gathered in one of the nodes.

bool	isVectorized (Value *V) const
	Check if the value is vectorized in the tree.

	~BoUpSLP ()

Friends
struct	GraphTraits< BoUpSLP * >

struct	DOTGraphTraits< BoUpSLP * >

raw_ostream &	operator<< (raw_ostream &os, const BoUpSLP::ScheduleData &SD)

Detailed Description

Bottom Up SLP Vectorizer.

Definition at line 1080 of file SLPVectorizer.cpp.

Member Typedef Documentation

◆ ExtraValueToDebugLocsMap

using llvm::slpvectorizer::BoUpSLP::ExtraValueToDebugLocsMap = MapVector<Value *, SmallVector<Instruction *, 2> >

Definition at line 1090 of file SLPVectorizer.cpp.

◆ InstrList

using llvm::slpvectorizer::BoUpSLP::InstrList = SmallVector<Instruction *, 16>

Definition at line 1087 of file SLPVectorizer.cpp.

◆ OrdersType

using llvm::slpvectorizer::BoUpSLP::OrdersType = SmallVector<unsigned, 4>

Definition at line 1092 of file SLPVectorizer.cpp.

◆ StoreList

using llvm::slpvectorizer::BoUpSLP::StoreList = SmallVector<StoreInst *, 8>

Definition at line 1089 of file SLPVectorizer.cpp.

◆ ValueList

using llvm::slpvectorizer::BoUpSLP::ValueList = SmallVector<Value *, 8>

Definition at line 1086 of file SLPVectorizer.cpp.

◆ ValueSet

using llvm::slpvectorizer::BoUpSLP::ValueSet = SmallPtrSet<Value *, 16>

Definition at line 1088 of file SLPVectorizer.cpp.

Constructor & Destructor Documentation

◆ BoUpSLP()

llvm::slpvectorizer::BoUpSLP::BoUpSLP	(	Function *	Func,
		ScalarEvolution *	Se,
		TargetTransformInfo *	Tti,
		TargetLibraryInfo *	TLi,
		AAResults *	Aa,
		LoopInfo *	Li,
		DominatorTree *	Dt,
		AssumptionCache *	AC,
		DemandedBits *	DB,
		const DataLayout *	DL,
		OptimizationRemarkEmitter *	ORE
	)

inline

Definition at line 1094 of file SLPVectorizer.cpp.

References llvm::CodeMetrics::collectEphemeralValues(), F, llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::getFixedValue(), llvm::TargetTransformInfo::getMinVectorRegisterBitWidth(), llvm::TargetTransformInfo::getRegisterBitWidth(), MaxVectorRegSizeOption, MinVectorRegSizeOption, and llvm::TargetTransformInfo::RGK_FixedWidthVector.

◆ ~BoUpSLP()

BoUpSLP::~BoUpSLP ( )

Definition at line 3683 of file SLPVectorizer.cpp.

References assert(), llvm::dbgs(), llvm::SmallVectorImpl< T >::emplace_back(), F, I, llvm::RecursivelyDeleteTriviallyDeadInstructions(), llvm::verifyFunction(), and llvm::wouldInstructionBeTriviallyDead().

Member Function Documentation

◆ analyzedReductionRoot()

void llvm::slpvectorizer::BoUpSLP::analyzedReductionRoot ( Instruction * I )

inline

Register given instruction as already analyzed for being possible reduction root.

Definition at line 2352 of file SLPVectorizer.cpp.

References I.

◆ analyzedReductionVals()

void llvm::slpvectorizer::BoUpSLP::analyzedReductionVals ( ArrayRef< Value * > VL )

inline

Adds the list of reduced values to list of already checked values for the vectorization.

Definition at line 2362 of file SLPVectorizer.cpp.

References llvm::hash_value(), and llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert().

◆ areAnalyzedReductionVals()

bool llvm::slpvectorizer::BoUpSLP::areAnalyzedReductionVals ( ArrayRef< Value * > VL ) const

inline

Checks if the provided list of reduced values was checked already for vectorization.

Definition at line 2357 of file SLPVectorizer.cpp.

References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), and llvm::hash_value().

◆ buildExternalUses()

void BoUpSLP::buildExternalUses ( const ExtraValueToDebugLocsMap & ExternallyUsedValues = {} )

Builds external uses of the vectorized scalars, i.e.

the list of vectorized scalars to be extracted, their lanes and their scalar users. ExternallyUsedValues contains additional list of external uses to handle vectorization of reductions.

Definition at line 4820 of file SLPVectorizer.cpp.

References assert(), llvm::dbgs(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::end(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::find(), InTreeUserNeedToExtract(), isDeleted(), and LLVM_DEBUG.

◆ buildTree() [1/2]

void BoUpSLP::buildTree ( ArrayRef< Value * > Roots )

Construct a vectorizable tree that starts at Roots.

Definition at line 5034 of file SLPVectorizer.cpp.

References allSameType(), and deleteTree().

◆ buildTree() [2/2]

void BoUpSLP::buildTree	(	ArrayRef< Value * >	Roots,
		const SmallDenseSet< Value * > &	UserIgnoreLst
	)

Construct a vectorizable tree that starts at Roots, ignoring users for the purpose of scheduling and extraction in the UserIgnoreLst.

Definition at line 5025 of file SLPVectorizer.cpp.

References allSameType(), and deleteTree().

◆ canMapToVector()

unsigned BoUpSLP::canMapToVector	(	Type *	T,
		const DataLayout &	DL
	)		const

Check if homogeneous aggregate is isomorphic to some VectorType.

Accepts homogeneous multidimensional aggregate of scalars/vectors like {[4 x i16], [4 x i16]}, { <2 x float>, <2 x float> }, {{{i16, i16}, {i16, i16}}, {{i16, i16}, {i16, i16}}} and so on.

Returns: number of elements in vector if isomorphism exists, 0 otherwise.

Definition at line 6137 of file SLPVectorizer.cpp.

References DL, llvm::FixedVectorType::get(), isValidElementType(), and N.

◆ clearReductionData()

void llvm::slpvectorizer::BoUpSLP::clearReductionData ( )

inline

Clear the list of the analyzed reduction root instructions.

Definition at line 2366 of file SLPVectorizer.cpp.

References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::clear().

◆ computeMinimumValueSizes()

void BoUpSLP::computeMinimumValueSizes ( )

Compute the minimum type sizes required to represent the entries in a vectorizable tree.

Definition at line 11696 of file SLPVectorizer.cpp.

References llvm::all_of(), llvm::bit_ceil(), collectValuesToDemote(), llvm::computeKnownBits(), llvm::ComputeNumSignBits(), llvm::SmallPtrSetImpl< PtrType >::count(), DL, llvm::SmallPtrSetImplBase::empty(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallPtrSetImpl< PtrType >::erase(), llvm::DemandedBits::getDemandedBits(), getType(), llvm::Value::hasOneUse(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::KnownBits::isNonNegative(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::Value::user_begin().

◆ deleteTree()

void llvm::slpvectorizer::BoUpSLP::deleteTree ( )

inline

Clear the internal data structures that are created by 'buildTree'.

Definition at line 1172 of file SLPVectorizer.cpp.

References llvm::SetVector< T, Vector, Set >::clear(), llvm::SmallPtrSetImplBase::clear(), and llvm::SmallVectorImpl< T >::clear().

Referenced by buildTree().

◆ doesRootHaveInTreeUses()

bool llvm::slpvectorizer::BoUpSLP::doesRootHaveInTreeUses ( ) const

inline

Returns whether the root node has in-tree uses.

Definition at line 1159 of file SLPVectorizer.cpp.

References llvm::SmallVectorBase< Size_T >::empty(), and llvm::SmallVectorTemplateCommon< T, typename >::front().

◆ eraseInstruction()

void llvm::slpvectorizer::BoUpSLP::eraseInstruction ( Instruction * I )

inline

Removes an instruction from its block and eventually deletes it.

It's like Instruction::eraseFromParent() except that the actual deletion is delayed until BoUpSLP is destructed.

Definition at line 2341 of file SLPVectorizer.cpp.

References I.

Referenced by optimizeGatherSequence(), and vectorizeTree().

◆ findBestRootPair()

std::optional< int > llvm::slpvectorizer::BoUpSLP::findBestRootPair	(	ArrayRef< std::pair< Value , Value > >	Candidates,
		int	Limit = `LookAheadHeuristics::ScoreFail`
	)

inline

Evaluate each pair in Candidates and return index into Candidates for a pair which have highest score deemed to have best chance to form root of profitable tree to vectorize.

Return std::nullopt if no candidate scored above the LookAheadHeuristics::ScoreFail.

Parameters

Limit Lower limit of the cost, considered to be good enough score.

Definition at line 2316 of file SLPVectorizer.cpp.

References llvm::slpvectorizer::BoUpSLP::LookAheadHeuristics::getScoreAtLevelRec(), I, and RootLookAheadMaxDepth.

◆ findPartiallyOrderedLoads()

std::optional< BoUpSLP::OrdersType > BoUpSLP::findPartiallyOrderedLoads ( const TreeEntry & TE )

Sort loads into increasing pointers offsets to allow greater clustering.

Definition at line 3985 of file SLPVectorizer.cpp.

References assert(), clusterSortPtrAccesses(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallVectorImpl< T >::reserve().

Referenced by getReorderingData().

◆ findReusedOrderedScalars()

std::optional< BoUpSLP::OrdersType > BoUpSLP::findReusedOrderedScalars ( const TreeEntry & TE )

Checks if the specified gather tree entry TE can be represented as a shuffled vector entry + (possibly) permutation with other gathers.

It implements the checks only for possibly ordered scalars (Loads, ExtractElement, ExtractValue), which can be part of the graph.

Definition at line 3749 of file SLPVectorizer.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallBitVector::count(), llvm::find(), I, llvm::SmallBitVector::reset(), llvm::SmallBitVector::set(), and llvm::SmallBitVector::test().

Referenced by getReorderingData().

◆ getFirstNodeMainOp()

Instruction * llvm::slpvectorizer::BoUpSLP::getFirstNodeMainOp ( ) const

inline

Returns the main instruction for the very first node.

Definition at line 1153 of file SLPVectorizer.cpp.

References assert(), llvm::SmallVectorBase< Size_T >::empty(), and llvm::SmallVectorTemplateCommon< T, typename >::front().

◆ getMaximumVF()

unsigned llvm::slpvectorizer::BoUpSLP::getMaximumVF	(	unsigned	ElemWidth,
		unsigned	Opcode
	)		const

inline

Definition at line 1254 of file SLPVectorizer.cpp.

References llvm::TargetTransformInfo::getMaximumVF(), and MaxVFOption.

◆ getMaxVecRegSize()

unsigned llvm::slpvectorizer::BoUpSLP::getMaxVecRegSize ( ) const

inline

Definition at line 1241 of file SLPVectorizer.cpp.

◆ getMinVecRegSize()

unsigned llvm::slpvectorizer::BoUpSLP::getMinVecRegSize ( ) const

inline

Definition at line 1246 of file SLPVectorizer.cpp.

Referenced by getMinVF().

◆ getMinVF()

unsigned llvm::slpvectorizer::BoUpSLP::getMinVF ( unsigned Sz ) const

inline

Definition at line 1250 of file SLPVectorizer.cpp.

References getMinVecRegSize().

◆ getORE()

OptimizationRemarkEmitter * llvm::slpvectorizer::BoUpSLP::getORE ( )

inline

Definition at line 1290 of file SLPVectorizer.cpp.

◆ getReorderingData()

std::optional< BoUpSLP::OrdersType > BoUpSLP::getReorderingData	(	const TreeEntry &	TE,
		bool	TopToBottom
	)

Gets reordering data for the given tree entry.

If the entry is vectorized

just return ReorderIndices, otherwise check if the scalars can be reordered and return the most optimal order.
Returns
std::nullopt if ordering is not important, empty order, if identity order is important, or the actual order.

Parameters

TopToBottom If true, include the order of vectorized stores and insertelement nodes, otherwise skip them.

Definition at line 4054 of file SLPVectorizer.cpp.

References llvm::all_of(), allConstant(), allSameType(), llvm::any_of(), areTwoInsertFromSameBuildVector(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::UndefValue::classof(), llvm::count_if(), llvm::Data, llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::enumerate(), llvm::find(), llvm::find_if(), findPartiallyOrderedLoads(), findReusedOrderedScalars(), fixupOrderingIndices(), llvm::FixedVectorType::get(), llvm::PoisonValue::get(), getExtractIndex(), getInsertIndex(), llvm::User::getOperand(), llvm::TargetTransformInfo::getShuffleCost(), llvm::TargetTransformInfo::getVectorInstrCost(), llvm::Value::hasOneUse(), I, Idx, llvm::inversePermutation(), llvm::ShuffleVectorInst::isOneUseSingleSourceMask(), isSplat(), reorderOrder(), llvm::TargetTransformInfo::SK_PermuteSingleSrc, llvm::ArrayRef< T >::slice(), llvm::stable_sort(), llvm::TargetTransformInfo::TCK_RecipThroughput, llvm::transform(), llvm::UndefMaskElem, and llvm::Value::user_begin().

Referenced by reorderBottomToTop(), and reorderTopToBottom().

◆ getSpillCost()

InstructionCost BoUpSLP::getSpillCost ( ) const

Returns: the cost incurred by unwanted spills and fills, caused by holding live values over call sites.

Definition at line 7874 of file SLPVectorizer.cpp.

References A, assert(), B, Cost, llvm::dbgs(), llvm::SmallPtrSetImpl< PtrType >::erase(), llvm::FixedVectorType::get(), llvm::TargetTransformInfo::getCallInstrCost(), llvm::TargetTransformInfo::getCostOfKeepingLiveOverCall(), llvm::TargetTransformInfo::getIntrinsicInstrCost(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::Instruction::getParent(), llvm::ilist_iterator< OptionsT, IsReverse, IsConst >::getReverse(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, llvm::User::operands(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::BasicBlock::rend(), llvm::SmallPtrSetImplBase::size(), llvm::sort(), llvm::TargetTransformInfo::TCK_RecipThroughput, and X.

Referenced by getTreeCost().

◆ getTreeCost()

InstructionCost BoUpSLP::getTreeCost ( ArrayRef< Value * > VectorizedVals = std::nullopt )

Returns: the vectorization cost of the subtree that starts at VL. A negative number means that this is profitable.

Definition at line 8143 of file SLPVectorizer.cpp.

References llvm::all_of(), llvm::any_of(), areTwoInsertFromSameBuildVector(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::sampleprof::Base, llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::CallingConv::C, Cost, CostKind, llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::dump(), E, llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorTemplateCommon< T, typename >::end(), F, llvm::find_if(), llvm::IntegerType::get(), llvm::FixedVectorType::get(), llvm::TargetTransformInfo::getExtractWithExtendCost(), getInsertIndex(), llvm::TargetTransformInfo::getScalarizationOverhead(), llvm::TargetTransformInfo::getShuffleCost(), getSpillCost(), llvm::InsertElementInst::getType(), llvm::TargetTransformInfo::getVectorInstrCost(), llvm::APInt::getZero(), I, Idx, llvm::SmallPtrSetImpl< PtrType >::insert(), isFirstInsertElement(), llvm::ShuffleVectorInst::isIdentityMask(), LLVM_DEBUG, OS, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorBase< Size_T >::size(), llvm::TargetTransformInfo::SK_PermuteSingleSrc, llvm::TargetTransformInfo::SK_PermuteTwoSrc, llvm::TargetTransformInfo::TCK_RecipThroughput, llvm::UndefMaskElem, llvm::Vector, llvm::ViewGraph(), and ViewSLPTree.

◆ getTreeSize()

unsigned llvm::slpvectorizer::BoUpSLP::getTreeSize ( ) const

inline

Definition at line 1188 of file SLPVectorizer.cpp.

References llvm::SmallVectorBase< Size_T >::size().

◆ getVectorElementSize()

unsigned BoUpSLP::getVectorElementSize ( Value * V )

Returns: The vector element size in bits to use when vectorizing the expression tree ending at V. If V is a store, the size is the width of the stored value. Otherwise, the size is the width of the largest loaded value reaching V. This method is used by the vectorizer to calculate vectorization factors.

Definition at line 11548 of file SLPVectorizer.cpp.

References DL, E, llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::User::getOperand(), getVectorElementSize(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), and llvm::SmallVectorImpl< T >::pop_back_val().

Referenced by getVectorElementSize().

◆ isAnalyzedReductionRoot()

bool llvm::slpvectorizer::BoUpSLP::isAnalyzedReductionRoot ( Instruction * I ) const

inline

Checks if the instruction was already analyzed for being possible reduction root.

Definition at line 2347 of file SLPVectorizer.cpp.

References I.

◆ isAnyGathered()

bool llvm::slpvectorizer::BoUpSLP::isAnyGathered ( const SmallDenseSet< Value * > & Vals ) const

inline

Checks if the given value is gathered in one of the nodes.

Definition at line 2371 of file SLPVectorizer.cpp.

References llvm::any_of(), and llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains().

◆ isDeleted()

bool llvm::slpvectorizer::BoUpSLP::isDeleted ( Instruction * I ) const

inline

Checks if the instruction is marked for deletion.

Definition at line 2336 of file SLPVectorizer.cpp.

References I.

Referenced by buildExternalUses(), and optimizeGatherSequence().

◆ isLoadCombineCandidate()

bool BoUpSLP::isLoadCombineCandidate ( ) const

Assume that a vector of stores of bitwise-or/shifted/zexted loaded values can be load combined in the backend.

Load combining may not be allowed in the IR optimizer, so we do not want to alter the pattern. For example, partially transforming a scalar bswap() pattern into vector code is effectively impossible for the backend to undo. TODO: If load combining is allowed in the IR optimizer, this analysis may not be necessary.

Definition at line 7832 of file SLPVectorizer.cpp.

References isLoadCombineCandidateImpl(), llvm::PatternMatch::m_Store(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and X.

◆ isLoadCombineReductionCandidate()

bool BoUpSLP::isLoadCombineReductionCandidate ( RecurKind RdxKind ) const

Assume that a legal-sized 'or'-reduction of shifted/zexted loaded values can be load combined in the backend.

Load combining may not be allowed in the IR optimizer, so we do not want to alter the pattern. For example, partially transforming a scalar bswap() pattern into vector code is effectively impossible for the backend to undo. TODO: If load combining is allowed in the IR optimizer, this analysis may not be necessary.

Definition at line 7822 of file SLPVectorizer.cpp.

References isLoadCombineCandidateImpl(), and llvm::Or.

◆ isTreeTinyAndNotFullyVectorizable()

bool BoUpSLP::isTreeTinyAndNotFullyVectorizable ( bool ForReduction = false ) const

Returns: True if the VectorizableTree is both tiny and not fully vectorizable. We do not vectorize such trees.

Definition at line 7845 of file SLPVectorizer.cpp.

References allConstant(), assert(), isSplat(), and MinTreeSize.

◆ isVectorized()

bool llvm::slpvectorizer::BoUpSLP::isVectorized ( Value * V ) const

inline

Check if the value is vectorized in the tree.

Definition at line 2376 of file SLPVectorizer.cpp.

◆ isVectorizedFirstNode()

bool llvm::slpvectorizer::BoUpSLP::isVectorizedFirstNode ( ) const

inline

Checks if the very first tree node is going to be vectorized.

Definition at line 1147 of file SLPVectorizer.cpp.

References llvm::SmallVectorBase< Size_T >::empty(), and llvm::SmallVectorTemplateCommon< T, typename >::front().

◆ optimizeGatherSequence()

void BoUpSLP::optimizeGatherSequence ( )

Perform LICM and CSE on the newly generated gather sequences.

Definition at line 10822 of file SLPVectorizer.cpp.

References A, llvm::any_of(), assert(), llvm::SmallVectorImpl< T >::assign(), B, llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::dbgs(), llvm::DominatorTree::dominates(), E, llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), eraseInstruction(), llvm::FixedVectorType::get(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::TargetTransformInfo::getNumberOfParts(), llvm::BasicBlock::getTerminator(), I, llvm::SetVector< T, Vector, Set >::insert(), llvm::is_contained(), isDeleted(), llvm::DominatorTree::isReachableFromEntry(), LLVM_DEBUG, llvm::make_early_inc_range(), N, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorImpl< T >::reserve(), SI, llvm::ArrayRef< T >::size(), llvm::SetVector< T, Vector, Set >::size(), llvm::SmallVectorBase< Size_T >::size(), llvm::sort(), and llvm::UndefMaskElem.

◆ reorderBottomToTop()

void BoUpSLP::reorderBottomToTop ( bool IgnoreReorder = false )

Reorders the current graph to the most profitable order starting from leaves to the root.

It allows to rotate small subgraphs and reduce the number of reshuffles if the leaf nodes use the same order. In this case we can merge the orders and just shuffle user node instead of shuffling its operands. Plus, even the leaf nodes have different orders, it allows to sink reordering in the graph closer to the root node and merge it later during analysis.

Definition at line 4569 of file SLPVectorizer.cpp.

References llvm::all_of(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallPtrSetImplBase::clear(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::count_if(), llvm::Data, llvm::drop_begin(), E, llvm::slpvectorizer::BoUpSLP::EdgeInfo::EdgeIdx, llvm::ArrayRef< T >::empty(), llvm::SetVector< T, Vector, Set >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), fixupOrderingIndices(), llvm::for_each(), llvm::ArrayRef< T >::front(), getReorderingData(), I, Idx, if(), llvm::SetVector< T, Vector, Set >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::inversePermutation(), P, llvm::SmallVectorTemplateBase< T, bool >::push_back(), reorderOrder(), reorderReuses(), llvm::reorderScalars(), llvm::ArrayRef< T >::size(), llvm::sort(), llvm::transform(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace(), llvm::UndefMaskElem, Users, and llvm::slpvectorizer::BoUpSLP::EdgeInfo::UserTE.

◆ reorderTopToBottom()

void BoUpSLP::reorderTopToBottom ( )

Reorders the current graph to the most profitable order starting from the root node to the leaf nodes.

The best order is chosen only from the nodes of the same size (vectorization factor). Smaller nodes are considered parts of subgraph with smaller VF and they are reordered independently. We can make it because we still need to extend smaller nodes to the wider VF and we can merge reordering shuffles with the widening shuffles.

Definition at line 4281 of file SLPVectorizer.cpp.

References addMask(), llvm::all_of(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::drop_begin(), E, llvm::ArrayRef< T >::empty(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), fixupOrderingIndices(), llvm::for_each(), llvm::ArrayRef< T >::front(), llvm::FixedVectorType::get(), getReorderingData(), I, Idx, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::inversePermutation(), llvm::isa(), llvm::TargetTransformInfo::isLegalAltInstr(), RecursionMaxDepth, reorderOrder(), llvm::reorderScalars(), llvm::SmallBitVector::set(), llvm::ArrayRef< T >::size(), llvm::transform(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace(), and llvm::UndefMaskElem.

◆ vectorizeTree() [1/2]

Value * BoUpSLP::vectorizeTree ( )

Vectorize the tree that starts with the elements in VL.

Returns the vectorized root.

Definition at line 10371 of file SLPVectorizer.cpp.

References vectorizeTree().

Referenced by vectorizeTree().

◆ vectorizeTree() [2/2]

Value * BoUpSLP::vectorizeTree	(	ExtraValueToDebugLocsMap &	ExternallyUsedValues,
		Instruction *	ReductionRoot = `nullptr`
	)

Vectorize the tree but with the list of externally used values ExternallyUsedValues.

Values in this MapVector can be replaced but the generated extractvalue instructions.

Definition at line 10387 of file SLPVectorizer.cpp.

References llvm::slpvectorizer::BoUpSLP::ShuffleInstructionBuilder::add(), llvm::any_of(), areTwoInsertFromSameBuildVector(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::ArrayRef< T >::back(), llvm::sampleprof::Base, llvm::SmallVectorTemplateCommon< T, typename >::begin(), Builder, llvm::Instruction::comesBefore(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::count(), llvm::Data, llvm::dbgs(), E, llvm::SmallVectorImpl< T >::emplace_back(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::end(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::erase(), eraseInstruction(), F, llvm::slpvectorizer::BoUpSLP::ShuffleInstructionBuilder::finalize(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::find(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::find_if(), llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::ArrayRef< T >::front(), llvm::get(), llvm::IntegerType::get(), llvm::FixedVectorType::get(), llvm::PoisonValue::get(), llvm::SetVector< T, Vector, Set >::getArrayRef(), getInsertIndex(), llvm::User::getOperand(), llvm::BasicBlock::getParent(), llvm::Instruction::getParent(), llvm::Value::getType(), I, Idx, llvm::SetVector< T, Vector, Set >::insert(), llvm::is_contained(), isFirstInsertElement(), LLVM_DEBUG, llvm::Instruction::moveAfter(), PHI, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorTemplateCommon< T, typename >::rbegin(), llvm::SmallVectorTemplateCommon< T, typename >::rend(), llvm::Value::replaceAllUsesWith(), llvm::User::replaceUsesOfWith(), llvm::reverse(), llvm::SmallVectorBase< Size_T >::size(), llvm::sort(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace(), llvm::UndefMaskElem, llvm::User::User(), llvm::Vector, and vectorizeTree().

Friends And Related Function Documentation

◆ DOTGraphTraits< BoUpSLP * >

friend struct DOTGraphTraits< BoUpSLP * >

friend

Definition at line 3201 of file SLPVectorizer.cpp.

◆ GraphTraits< BoUpSLP * >

friend struct GraphTraits< BoUpSLP * >

friend

Definition at line 3201 of file SLPVectorizer.cpp.

◆ operator<<

raw_ostream & operator<<	(	raw_ostream &	os,
		const BoUpSLP::ScheduleData &	SD
	)

friend

Definition at line 3201 of file SLPVectorizer.cpp.

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

lib/Transforms/Vectorize/SLPVectorizer.cpp

Classes

Public Types

Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ ExtraValueToDebugLocsMap

◆ InstrList

◆ OrdersType

◆ StoreList

◆ ValueList

◆ ValueSet

Constructor & Destructor Documentation

◆ BoUpSLP()

◆ ~BoUpSLP()

Member Function Documentation

◆ analyzedReductionRoot()

◆ analyzedReductionVals()

◆ areAnalyzedReductionVals()

◆ buildExternalUses()

◆ buildTree() [1/2]

◆ buildTree() [2/2]

◆ canMapToVector()

◆ clearReductionData()

◆ computeMinimumValueSizes()

◆ deleteTree()

◆ doesRootHaveInTreeUses()

◆ eraseInstruction()

◆ findBestRootPair()

◆ findPartiallyOrderedLoads()

◆ findReusedOrderedScalars()

◆ getFirstNodeMainOp()

◆ getMaximumVF()

◆ getMaxVecRegSize()

◆ getMinVecRegSize()

◆ getMinVF()

◆ getORE()

◆ getReorderingData()

◆ getSpillCost()

◆ getTreeCost()

◆ getTreeSize()

◆ getVectorElementSize()

◆ isAnalyzedReductionRoot()

◆ isAnyGathered()

◆ isDeleted()

◆ isLoadCombineCandidate()

◆ isLoadCombineReductionCandidate()

◆ isTreeTinyAndNotFullyVectorizable()

◆ isVectorized()

◆ isVectorizedFirstNode()

◆ optimizeGatherSequence()

◆ reorderBottomToTop()

◆ reorderTopToBottom()

◆ vectorizeTree() [1/2]

◆ vectorizeTree() [2/2]

Friends And Related Function Documentation

◆ DOTGraphTraits< BoUpSLP * >

◆ GraphTraits< BoUpSLP * >

◆ operator<<