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

Bottom Up SLP Vectorizer. 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)
 
Value * vectorizeTree ()
 Vectorize the tree that starts with the elements in VL. More...
 
Value * vectorizeTree (ExtraValueToDebugLocsMap &ExternallyUsedValues)
 Vectorize the tree but with the list of externally used values ExternallyUsedValues. More...
 
int getSpillCost ()
 
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)
 
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 ()
 
OptimizationRemarkEmitter * getORE ()
 

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

Member Typedef Documentation

◆ ExtraValueToDebugLocsMap

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

Definition at line 483 of file SLPVectorizer.cpp.

◆ InstrList

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

Definition at line 479 of file SLPVectorizer.cpp.

◆ StoreList

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

Definition at line 481 of file SLPVectorizer.cpp.

◆ ValueList

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

Definition at line 478 of file SLPVectorizer.cpp.

◆ ValueSet

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

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

Definition at line 485 of file SLPVectorizer.cpp.

References llvm::CodeMetrics::collectEphemeralValues(), F(), MaxVectorRegSizeOption, MinVectorRegSizeOption, and llvm::None.

Member Function Documentation

◆ bestOrder()

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

Definition at line 560 of file SLPVectorizer.cpp.

References llvm::computeMinimumValueSizes(), I, llvm::makeArrayRef(), and llvm::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 1954 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(), 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(), 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, 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 ( )

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

Definition at line 4387 of file SLPVectorizer.cpp.

References llvm::AnalysisUsage::addPreserved(), llvm::AnalysisUsage::addRequired(), llvm::all_of(), assert(), collectValuesToDemote(), llvm::computeKnownBits(), llvm::ComputeNumSignBits(), llvm::dyn_cast(), llvm::SmallVectorBase::empty(), F(), llvm::Pass::getAnalysisUsage(), llvm::PassRegistry::getPassRegistry(), llvm::Value::hasOneUse(), llvm::initializeSLPVectorizerPass(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::KnownBits::isNonNegative(), llvm::isPowerOf2_64(), llvm::BitmaskEnumDetail::Mask(), llvm::NextPowerOf2(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SLPVectorizerPass::runImpl(), runOnFunction(), llvm::NVPTX::PTXLdStInstCode::Scalar, llvm::AnalysisUsage::setPreservesCFG(), and llvm::Value::user_back().

◆ deleteTree()

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

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

Definition at line 540 of file SLPVectorizer.cpp.

◆ getMaxVecRegSize()

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

Definition at line 586 of file SLPVectorizer.cpp.

◆ getMinVecRegSize()

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

Definition at line 591 of file SLPVectorizer.cpp.

◆ getORE()

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

Definition at line 604 of file SLPVectorizer.cpp.

References assert(), llvm::ArrayRef< T >::begin(), llvm::Depth, llvm::User::dropAllReferences(), llvm::dump(), E, llvm::SmallVectorImpl< T >::emplace_back(), llvm::ArrayRef< T >::end(), llvm::lltok::equal, eraseInstruction(), getLocation(), llvm::Optional< T >::getValue(), llvm::Optional< T >::hasValue(), I, llvm::cl::init(), isSimple(), llvm::Left, llvm::None, llvm::MemoryLocation::Ptr, llvm::Instruction::removeFromParent(), llvm::Right, llvm::NVPTX::PTXLdStInstCode::Scalar, and llvm::ArrayRef< T >::size().

◆ getSpillCost()

int BoUpSLP::getSpillCost ( )
Returns
the cost incurred by unwanted spills and fills, caused by holding live values over call sites.

Definition at line 2461 of file SLPVectorizer.cpp.

References llvm::dbgs(), llvm::Value::dump(), llvm::dyn_cast(), llvm::SmallPtrSetImpl< PtrType >::erase(), llvm::VectorType::get(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::getParent(), llvm::ilist_iterator< OptionsT, IsReverse, IsConst >::getReverse(), llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, N, llvm::User::operands(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::BasicBlock::rbegin(), llvm::BasicBlock::rend(), llvm::SmallPtrSetImplBase::size(), and X.

◆ getTreeCost()

int BoUpSLP::getTreeCost ( )
Returns
the vectorization cost of the subtree that starts at VL. A negative number means that this is profitable.

Definition at line 2526 of file SLPVectorizer.cpp.

References llvm::any_of(), assert(), C, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::count(), llvm::dbgs(), E, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::empty(), F(), llvm::IntegerType::get(), llvm::VectorType::get(), llvm::User::getOperand(), I, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Instruction::isCommutative(), llvm::isConsecutiveAccess(), llvm::Left, LLVM_DEBUG, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::Right, SI, llvm::ArrayRef< T >::size(), llvm::TargetTransformInfo::SK_PermuteSingleSrc, std::swap(), ViewGraph(), and ViewSLPTree.

◆ getTreeSize()

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

Definition at line 554 of file SLPVectorizer.cpp.

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

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

◆ isTreeTinyAndNotFullyVectorizable()

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

Definition at line 2441 of file SLPVectorizer.cpp.

References assert(), and MinTreeSize.

◆ optimizeGatherSequence()

void BoUpSLP::optimizeGatherSequence ( )

Perform LICM and CSE on the newly generated gather sequences.

Definition at line 3728 of file SLPVectorizer.cpp.

References A, assert(), B, llvm::SmallVectorTemplateCommon< T >::begin(), llvm::BasicBlock::begin(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dbgs(), llvm::dyn_cast(), E, llvm::SmallVectorTemplateCommon< T >::end(), llvm::BasicBlock::end(), eraseInstruction(), llvm::ilist_node_impl< OptionsT >::getIterator(), getLocation(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::ilist_node_with_parent< NodeTy, ParentTy, Options >::getNextNode(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::ilist_iterator< OptionsT, IsReverse, IsConst >::getReverse(), llvm::BasicBlock::getTerminator(), I, llvm::tgtok::In, llvm::is_contained(), llvm::Instruction::isIdenticalTo(), isOneOf(), LLVM_DEBUG, llvm::make_unique(), llvm::Instruction::mayReadOrWriteMemory(), llvm::Instruction::moveBefore(), N, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::Value::replaceAllUsesWith(), llvm::SmallVectorImpl< T >::reserve(), and llvm::Intrinsic::sideeffect.

◆ vectorizeTree() [1/2]

Value * BoUpSLP::vectorizeTree ( )

Vectorize the tree that starts with the elements in VL.

Returns the vectorized root.

Definition at line 3569 of file SLPVectorizer.cpp.

◆ vectorizeTree() [2/2]

Value * BoUpSLP::vectorizeTree ( ExtraValueToDebugLocsMap &  ExternallyUsedValues)

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

References assert(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::count(), llvm::dbgs(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::erase(), eraseInstruction(), F(), llvm::IntegerType::get(), llvm::VectorType::get(), llvm::UndefValue::get(), getParent(), llvm::Value::getType(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::insert(), llvm::is_contained(), llvm::Type::isVoidTy(), llvm::AArch64CC::LE, LLVM_DEBUG, llvm::Value::replaceAllUsesWith(), llvm::User::replaceUsesOfWith(), llvm::NVPTX::PTXLdStInstCode::Scalar, second, llvm::RegState::Undef, llvm::User::User(), and llvm::Value::users().

Friends And Related Function Documentation

◆ DOTGraphTraits< BoUpSLP *>

friend struct DOTGraphTraits< BoUpSLP * >
friend

Definition at line 962 of file SLPVectorizer.cpp.

◆ GraphTraits< BoUpSLP *>

friend struct GraphTraits< BoUpSLP * >
friend

Definition at line 961 of file SLPVectorizer.cpp.

◆ operator<<

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

Definition at line 954 of file SLPVectorizer.cpp.

The documentation for this class was generated from the following file:
Generated on Sun Dec 20 2020 14:14:53 for LLVM by   doxygen 1.8.13