LLVM  10.0.0svn
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 > >
 

Public Member Functions

 BoUpSLP (Function *Func, ScalarEvolution *Se, TargetTransformInfo *Tti, TargetLibraryInfo *TLi, AliasAnalysis *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...
 
int getSpillCost () const
 
int getTreeCost ()
 
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 buildTree (ArrayRef< Value *> Roots, ExtraValueToDebugLocsMap &ExternallyUsedValues, ArrayRef< Value *> UserIgnoreLst=None)
 Construct a vectorizable tree that starts at Roots, ignoring users for the purpose of scheduling and extraction in the UserIgnoreLst taking into account (anf updating it, if required) list of externally used values stored in ExternallyUsedValues. 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< ArrayRef< unsigned > > bestOrder () const
 
unsigned getVectorElementSize (Value *V) const
 
void computeMinimumValueSizes ()
 Compute the minimum type sizes required to represent the entries in a vectorizable tree. More...
 
unsigned getMaxVecRegSize () const
 
unsigned getMinVecRegSize () const
 
unsigned canMapToVector (Type *T, const DataLayout &DL) const
 Check if ArrayType or StructType is isomorphic to some VectorType. More...
 
bool isTreeTinyAndNotFullyVectorizable () const
 
bool isLoadCombineReductionCandidate (unsigned ReductionOpcode) const
 Assume that a legal-sized 'or'-reduction of 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 490 of file SLPVectorizer.cpp.

Member Typedef Documentation

◆ ExtraValueToDebugLocsMap

Definition at line 500 of file SLPVectorizer.cpp.

◆ InstrList

Definition at line 496 of file SLPVectorizer.cpp.

◆ StoreList

Definition at line 498 of file SLPVectorizer.cpp.

◆ ValueList

Definition at line 495 of file SLPVectorizer.cpp.

◆ ValueSet

Definition at line 497 of file SLPVectorizer.cpp.

Constructor & Destructor Documentation

◆ BoUpSLP()

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

◆ ~BoUpSLP()

BoUpSLP::~BoUpSLP ( )

Member Function Documentation

◆ bestOrder()

Optional<ArrayRef<unsigned> > llvm::slpvectorizer::BoUpSLP::bestOrder ( ) const
inline
Returns
The best order of instructions for vectorization.

Definition at line 577 of file SLPVectorizer.cpp.

References llvm::computeMinimumValueSizes(), I, llvm::makeArrayRef(), and None.

◆ buildTree() [1/2]

void llvm::slpvectorizer::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.

◆ buildTree() [2/2]

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

Construct a vectorizable tree that starts at Roots, ignoring users for the purpose of scheduling and extraction in the UserIgnoreLst taking into account (anf updating it, if required) list of externally used values stored in ExternallyUsedValues.

◆ canMapToVector()

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

Check if ArrayType or StructType is isomorphic to some VectorType.

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

Definition at line 2808 of file SLPVectorizer.cpp.

References llvm::MCID::Add, llvm::all_of(), allConstant(), allSameBlock(), allSameType(), llvm::CallBase::arg_operands(), llvm::AMDGPU::HSAMD::Kernel::Key::Args, assert(), llvm::SmallVectorImpl< T >::assign(), llvm::MCID::Call, llvm::SmallVectorImpl< T >::clear(), llvm::dbgs(), llvm::dyn_cast(), llvm::numbers::e, E, llvm::MipsISD::Ext, F(), llvm::IntegerType::get(), llvm::VectorType::get(), getAlignment(), llvm::CallBase::getArgOperand(), llvm::Module::getDataLayout(), getExtractIndex(), llvm::Type::getInt1Ty(), llvm::Instruction::getModule(), llvm::CallBase::getNumArgOperands(), llvm::SequentialType::getNumElements(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), getSameOpcode(), llvm::Value::getType(), llvm::DataLayout::getTypeStoreSizeInBits(), llvm::Optional< T >::getValue(), llvm::getVectorIntrinsicIDForCall(), llvm::Value::hasNUses(), llvm::Value::hasOneUse(), llvm::Optional< T >::hasValue(), I, llvm::Instruction::isBinaryOp(), llvm::Instruction::isCast(), isShuffle(), llvm::LoadInst::isSimple(), isSplat(), isValidElementType(), LLVM_DEBUG, llvm_unreachable, llvm::SPII::Load, N, llvm::TargetTransformInfo::OK_AnyValue, llvm::TargetTransformInfo::OK_NonUniformConstantValue, llvm::TargetTransformInfo::OK_UniformConstantValue, op, llvm::TargetTransformInfo::OP_None, llvm::TargetTransformInfo::OP_PowerOf2, Operands, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::MCID::Select, SI, llvm::ArrayRef< T >::size(), llvm::TargetTransformInfo::SK_Broadcast, llvm::TargetTransformInfo::SK_PermuteSingleSrc, llvm::TargetTransformInfo::SK_Select, llvm::ARM_MB::ST, llvm::SPII::Store, T, llvm::TargetTransformInfo::TCK_RecipThroughput, llvm::Instruction::user_back(), llvm::Value::user_begin(), llvm::Value::user_end(), and llvm::Value::users().

◆ computeMinimumValueSizes()

void BoUpSLP::computeMinimumValueSizes ( )

◆ deleteTree()

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

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

Definition at line 557 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 2091 of file SLPVectorizer.cpp.

References llvm::MCID::Add, allConstant(), allSameBlock(), allSameType(), assert(), llvm::SmallVectorImpl< T >::assign(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::MCID::Call, llvm::SmallVectorImpl< T >::clear(), llvm::dbgs(), llvm::Depth, llvm::dyn_cast(), llvm::numbers::e, E, llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorBase::empty(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::end(), llvm::lltok::equal, eraseInstruction(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::find(), llvm::find(), llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::CallBase::getArgOperand(), llvm::CallBase::getBundleOperandsEndIndex(), llvm::CallBase::getBundleOperandsStartIndex(), llvm::CallBase::getCalledFunction(), llvm::CallBase::getNumArgOperands(), llvm::User::getOperand(), llvm::BasicBlock::getParent(), llvm::PPC::getPredicate(), llvm::CmpInst::getPredicate(), getSameOpcode(), llvm::CmpInst::getSwappedPredicate(), llvm::Value::getType(), llvm::getVectorIntrinsicIDForCall(), llvm::CallBase::hasIdenticalOperandBundleSchema(), llvm::CallBase::hasOperandBundles(), llvm::hasVectorInstrinsicScalarOpd(), I, llvm::tgtok::Int, InTreeUserNeedToExtract(), llvm::is_contained(), isCommutative(), llvm::isConsecutiveAccess(), llvm::isPowerOf2_32(), isSplat(), llvm::Instruction::isTerminator(), llvm::isTriviallyVectorizable(), isValidElementType(), llvm::AArch64CC::LE, llvm::Left, LLVM_DEBUG, llvm::SPII::Load, None, llvm::User::op_begin(), Operands, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), RecursionMaxDepth, llvm::Right, llvm::NVPTX::PTXLdStInstCode::Scalar, llvm::MCID::Select, SI, Size, llvm::SmallVectorBase::size(), llvm::sortPtrAccesses(), llvm::SPII::Store, std::swap(), TE, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace(), and llvm::Value::users().

◆ getMaxVecRegSize()

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

Definition at line 603 of file SLPVectorizer.cpp.

◆ getMinVecRegSize()

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

Definition at line 608 of file SLPVectorizer.cpp.

◆ getORE()

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

Definition at line 630 of file SLPVectorizer.cpp.

◆ getSpillCost()

int BoUpSLP::getSpillCost ( ) const

◆ getTreeCost()

int BoUpSLP::getTreeCost ( )

◆ getTreeSize()

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

Definition at line 571 of file SLPVectorizer.cpp.

◆ getVectorElementSize()

unsigned BoUpSLP::getVectorElementSize ( Value V) const
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 4923 of file SLPVectorizer.cpp.

References llvm::SmallPtrSetImpl< PtrType >::count(), llvm::SmallVectorBase::empty(), llvm::Value::getType(), llvm::DataLayout::getTypeSizeInBits(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::User::operands(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), and llvm::SPII::Store.

◆ isDeleted()

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

◆ isLoadCombineReductionCandidate()

bool BoUpSLP::isLoadCombineReductionCandidate ( unsigned  ReductionOpcode) 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 3296 of file SLPVectorizer.cpp.

References Context, llvm::dbgs(), llvm::IntegerType::get(), llvm::Value::getContext(), llvm::Type::getIntegerBitWidth(), llvm::Type::getPointerElementType(), llvm::Value::getType(), LLVM_DEBUG, llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_Load(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExt(), and llvm::PatternMatch::match().

◆ isTreeTinyAndNotFullyVectorizable()

bool BoUpSLP::isTreeTinyAndNotFullyVectorizable ( ) const
Returns
True if the VectorizableTree is both tiny and not fully vectorizable. We do not vectorize such trees.

Definition at line 3333 of file SLPVectorizer.cpp.

References assert(), and MinTreeSize.

◆ optimizeGatherSequence()

void BoUpSLP::optimizeGatherSequence ( )

◆ vectorizeTree() [1/2]

Value * BoUpSLP::vectorizeTree ( )

Vectorize the tree that starts with the elements in VL.

Returns the vectorized root.

Definition at line 4234 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 1679 of file SLPVectorizer.cpp.

◆ GraphTraits< BoUpSLP *>

friend struct GraphTraits< BoUpSLP * >
friend

Definition at line 1678 of file SLPVectorizer.cpp.

◆ operator<<

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

Definition at line 1671 of file SLPVectorizer.cpp.


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