LLVM  14.0.0git
Classes | Public Types | Public Member Functions | Friends | List of all members
llvm::slpvectorizer::BoUpSLP Class Reference

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  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)
 
ValuevectorizeTree ()
 Vectorize the tree that starts with the elements in VL. More...
 
ValuevectorizeTree (ExtraValueToDebugLocsMap &ExternallyUsedValues)
 Vectorize the tree but with the list of externally used values ExternallyUsedValues. More...
 
InstructionCost getSpillCost () const
 
InstructionCost getTreeCost (ArrayRef< Value * > VectorizedVals=None)
 
void buildTree (ArrayRef< Value * > Roots, ArrayRef< Value * > UserIgnoreLst=None)
 Construct a vectorizable tree that starts at Roots, ignoring users for the purpose of scheduling and extraction in the UserIgnoreLst. More...
 
void buildExternalUses (const ExtraValueToDebugLocsMap &ExternallyUsedValues={})
 Builds external uses of the vectorized scalars, i.e. More...
 
void deleteTree ()
 Clear the internal data structures that are created by 'buildTree'. More...
 
unsigned getTreeSize () const
 
void optimizeGatherSequence ()
 Perform LICM and CSE on the newly generated gather sequences. More...
 
Optional< OrdersTypefindReusedOrderedScalars (const TreeEntry &TE)
 Checks if the specified gather tree entry TE can be represented as a shuffled vector entry + (possibly) permutation with other gathers. More...
 
Optional< OrdersTypegetReorderingData (const TreeEntry &TE, bool TopToBottom)
 Gets reordering data for the given tree entry. More...
 
void reorderTopToBottom ()
 Reorders the current graph to the most profitable order starting from the root node to the leaf nodes. More...
 
void reorderBottomToTop (bool IgnoreReorder=false)
 Reorders the current graph to the most profitable order starting from leaves to the root. More...
 
unsigned getVectorElementSize (Value *V)
 
void computeMinimumValueSizes ()
 Compute the minimum type sizes required to represent the entries in a vectorizable tree. More...
 
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. More...
 
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. More...
 
bool isLoadCombineCandidate () const
 Assume that a vector of stores of bitwise-or/shifted/zexted loaded values can be load combined in the backend. More...
 
OptimizationRemarkEmittergetORE ()
 
bool isDeleted (Instruction *I) const
 Checks if the instruction is marked for deletion. More...
 
void eraseInstructions (ArrayRef< Value * > AV)
 Marks values operands for later deletion by replacing them with Undefs. More...
 
 ~BoUpSLP ()
 

Friends

struct GraphTraits< BoUpSLP * >
 
struct DOTGraphTraits< BoUpSLP * >
 
raw_ostreamoperator<< (raw_ostream &os, const BoUpSLP::ScheduleData &SD)
 

Detailed Description

Bottom Up SLP Vectorizer.

Definition at line 721 of file SLPVectorizer.cpp.

Member Typedef Documentation

◆ ExtraValueToDebugLocsMap

Definition at line 731 of file SLPVectorizer.cpp.

◆ InstrList

Definition at line 727 of file SLPVectorizer.cpp.

◆ OrdersType

Definition at line 732 of file SLPVectorizer.cpp.

◆ StoreList

Definition at line 729 of file SLPVectorizer.cpp.

◆ ValueList

Definition at line 726 of file SLPVectorizer.cpp.

◆ ValueSet

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

◆ ~BoUpSLP()

BoUpSLP::~BoUpSLP ( )

Member Function Documentation

◆ 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 3433 of file SLPVectorizer.cpp.

◆ buildTree()

void BoUpSLP::buildTree ( ArrayRef< Value * >  Roots,
ArrayRef< Value * >  UserIgnoreLst = None 
)

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

Definition at line 3493 of file SLPVectorizer.cpp.

References allSameType().

◆ 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 4381 of file SLPVectorizer.cpp.

References DL, get, isValidElementType(), N, llvm::ARM_MB::ST, and T.

◆ computeMinimumValueSizes()

void BoUpSLP::computeMinimumValueSizes ( )

◆ deleteTree()

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

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

Definition at line 790 of file SLPVectorizer.cpp.

◆ eraseInstructions()

void BoUpSLP::eraseInstructions ( ArrayRef< Value * >  AV)

Marks values operands for later deletion by replacing them with Undefs.

Definition at line 2888 of file SLPVectorizer.cpp.

References eraseInstruction(), and I.

◆ findReusedOrderedScalars()

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 2934 of file SLPVectorizer.cpp.

References assert(), llvm::SmallVectorImpl< T >::clear(), llvm::SmallBitVector::count(), llvm::find(), I, None, llvm::SmallBitVector::reset(), llvm::SmallBitVector::set(), and llvm::SmallBitVector::test().

◆ getMaximumVF()

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

Definition at line 863 of file SLPVectorizer.cpp.

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

◆ getMaxVecRegSize()

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

Definition at line 850 of file SLPVectorizer.cpp.

◆ getMinVecRegSize()

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

Definition at line 855 of file SLPVectorizer.cpp.

◆ getMinVF()

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

Definition at line 859 of file SLPVectorizer.cpp.

References llvm::max().

◆ getORE()

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

Definition at line 899 of file SLPVectorizer.cpp.

◆ getReorderingData()

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.
    Parameters
    TopToBottomIf true, include the order of vectorized stores and insertelement nodes, otherwise skip them.

Definition at line 2999 of file SLPVectorizer.cpp.

References llvm::all_of(), allSameType(), llvm::any_of(), fixupOrderingIndices(), and None.

◆ getSpillCost()

InstructionCost BoUpSLP::getSpillCost ( ) const

◆ getTreeCost()

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

◆ getTreeSize()

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

Definition at line 803 of file SLPVectorizer.cpp.

◆ getVectorElementSize()

unsigned BoUpSLP::getVectorElementSize ( Value V)

◆ isDeleted()

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

Checks if the instruction is marked for deletion.

Definition at line 1785 of file SLPVectorizer.cpp.

References I.

◆ 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 5464 of file SLPVectorizer.cpp.

References isLoadCombineCandidateImpl(), llvm::PatternMatch::m_Store(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::NVPTX::PTXLdStInstCode::Scalar, 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 5454 of file SLPVectorizer.cpp.

References isLoadCombineCandidateImpl().

◆ 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 5477 of file SLPVectorizer.cpp.

References assert(), and MinTreeSize.

◆ optimizeGatherSequence()

void BoUpSLP::optimizeGatherSequence ( )

◆ 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 3201 of file SLPVectorizer.cpp.

References llvm::all_of(), llvm::any_of(), assert(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count(), llvm::count_if(), llvm::Data, llvm::drop_begin(), E, llvm::SetVector< T, Vector, Set >::empty(), llvm::ArrayRef< T >::end(), llvm::find_if(), llvm::for_each(), I, if(), llvm::SmallPtrSetImpl< PtrType >::insert(), 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 3043 of file SLPVectorizer.cpp.

References llvm::for_each(), if(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert(), and llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::try_emplace().

◆ vectorizeTree() [1/2]

Value * BoUpSLP::vectorizeTree ( )

Vectorize the tree that starts with the elements in VL.

Returns the vectorized root.

Definition at line 6905 of file SLPVectorizer.cpp.

◆ vectorizeTree() [2/2]

Value * BoUpSLP::vectorizeTree ( ExtraValueToDebugLocsMap ExternallyUsedValues)

Friends And Related Function Documentation

◆ DOTGraphTraits< BoUpSLP * >

friend struct DOTGraphTraits< BoUpSLP * >
friend

Definition at line 2468 of file SLPVectorizer.cpp.

◆ GraphTraits< BoUpSLP * >

friend struct GraphTraits< BoUpSLP * >
friend

Definition at line 2467 of file SLPVectorizer.cpp.

◆ operator<<

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

Definition at line 2460 of file SLPVectorizer.cpp.


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