LLVM 19.0.0git
|
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 | ShuffleCostEstimator |
Merges shuffle masks and emits final shuffle instruction, if required. 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 | |
enum class | LoadsState { Gather , Vectorize , ScatterVectorize , StridedVectorize } |
Tracks the state we can represent the loads in the given sequence. More... | |
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 (const ExtraValueToDebugLocsMap &ExternallyUsedValues, SmallVectorImpl< std::pair< Value *, Value * > > &ReplacedExternals, 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 | doesRootHaveInTreeUses () const |
Returns whether the root node has in-tree uses. | |
ArrayRef< Value * > | getRootNodeScalars () const |
Return the scalars of the root node. | |
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 |
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. | |
LoadsState | canVectorizeLoads (ArrayRef< Value * > VL, const Value *VL0, SmallVectorImpl< unsigned > &Order, SmallVectorImpl< Value * > &PointerOps, bool TryRecursiveCheck=true) const |
Checks if the given array of loads can be represented as a vectorized, scatter or just simple gather. | |
OptimizationRemarkEmitter * | getORE () |
std::optional< int > | findBestRootPair (ArrayRef< std::pair< Value *, Value * > > Candidates, int Limit=LookAheadHeuristics::ScoreFail) const |
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) |
Bottom Up SLP Vectorizer.
Definition at line 977 of file SLPVectorizer.cpp.
using llvm::slpvectorizer::BoUpSLP::ExtraValueToDebugLocsMap = MapVector<Value *, SmallVector<Instruction *, 2> > |
Definition at line 996 of file SLPVectorizer.cpp.
using llvm::slpvectorizer::BoUpSLP::InstrList = SmallVector<Instruction *, 16> |
Definition at line 993 of file SLPVectorizer.cpp.
Definition at line 998 of file SLPVectorizer.cpp.
using llvm::slpvectorizer::BoUpSLP::StoreList = SmallVector<StoreInst *, 8> |
Definition at line 995 of file SLPVectorizer.cpp.
using llvm::slpvectorizer::BoUpSLP::ValueList = SmallVector<Value *, 8> |
Definition at line 992 of file SLPVectorizer.cpp.
using llvm::slpvectorizer::BoUpSLP::ValueSet = SmallPtrSet<Value *, 16> |
Definition at line 994 of file SLPVectorizer.cpp.
|
strong |
Tracks the state we can represent the loads in the given sequence.
Enumerator | |
---|---|
Gather | |
Vectorize | |
ScatterVectorize | |
StridedVectorize |
Definition at line 985 of file SLPVectorizer.cpp.
|
inline |
Definition at line 1000 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 | ( | ) |
Definition at line 3766 of file SLPVectorizer.cpp.
References assert(), llvm::dbgs(), llvm::SmallVectorImpl< T >::emplace_back(), F, I, llvm::RecursivelyDeleteTriviallyDeadInstructions(), llvm::verifyFunction(), and llvm::wouldInstructionBeTriviallyDead().
|
inline |
Register given instruction as already analyzed for being possible reduction root.
Definition at line 2277 of file SLPVectorizer.cpp.
References I.
Adds the list of reduced values to list of already checked values for the vectorization.
Definition at line 2287 of file SLPVectorizer.cpp.
References llvm::hash_value(), and llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert().
Checks if the provided list of reduced values was checked already for vectorization.
Definition at line 2282 of file SLPVectorizer.cpp.
References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), and llvm::hash_value().
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 5431 of file SLPVectorizer.cpp.
References assert(), llvm::dbgs(), doesInTreeUserNeedToExtract(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::end(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::find(), isDeleted(), and LLVM_DEBUG.
Construct a vectorizable tree that starts at Roots
.
Definition at line 5644 of file SLPVectorizer.cpp.
References allSameType(), and deleteTree().
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 5635 of file SLPVectorizer.cpp.
References allSameType(), and deleteTree().
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.
Definition at line 6864 of file SLPVectorizer.cpp.
References DL, llvm::FixedVectorType::get(), isValidElementType(), N, and T.
BoUpSLP::LoadsState BoUpSLP::canVectorizeLoads | ( | ArrayRef< Value * > | VL, |
const Value * | VL0, | ||
SmallVectorImpl< unsigned > & | Order, | ||
SmallVectorImpl< Value * > & | PointerOps, | ||
bool | TryRecursiveCheck = true |
||
) | const |
Checks if the given array of loads can be represented as a vectorized, scatter or just simple gather.
VL | list of loads. |
VL0 | main load value. |
Order | returned order of load instructions. |
PointerOps | returned list of pointer operands. |
TryRecursiveCheck | used to check if long masked gather can be represented as a serie of loads/insert subvector, if profitable. |
Definition at line 4172 of file SLPVectorizer.cpp.
References llvm::all_of(), arePointersCompatible(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::bit_floor(), calculateRtStride(), canVectorizeLoads(), llvm::SmallVectorImpl< T >::clear(), CostKind, llvm::count_if(), DL, llvm::doesNotNeedToBeScheduled(), llvm::SmallVectorBase< Size_T >::empty(), End, llvm::enumerate(), llvm::TargetTransformInfo::forceScalarizeMaskedGather(), llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::ArrayRef< T >::front(), Gather, GEP, llvm::FixedVectorType::get(), llvm::TargetTransformInfo::getGatherScatterOpCost(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), getMaximumVF(), llvm::TargetTransformInfo::getMemoryOpCost(), getMinVF(), getParent(), llvm::getPointerOperand(), llvm::getPointersDiff(), llvm::TargetTransformInfo::getShuffleCost(), llvm::TargetTransformInfo::getStridedMemoryOpCost(), llvm::Value::getType(), I, Idx, llvm::SmallSet< T, N, C >::insert(), llvm::TargetTransformInfo::isLegalMaskedGather(), llvm::TargetTransformInfo::isLegalStridedLoadStore(), llvm::isPowerOf2_32(), isReverseOrder(), llvm::TargetTransformInfo::isTypeLegal(), llvm_unreachable, MaxProfitableLoadStride, MinProfitableStridedLoads, P, Ptr, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorImpl< T >::resize(), ScatterVectorize, llvm::ArrayRef< T >::size(), llvm::SmallSet< T, N, C >::size(), llvm::ArrayRef< T >::slice(), llvm::sortPtrAccesses(), StridedVectorize, llvm::TargetTransformInfo::TCK_RecipThroughput, and Vectorize.
Referenced by canVectorizeLoads().
|
inline |
Clear the list of the analyzed reduction root instructions.
Definition at line 2291 of file SLPVectorizer.cpp.
References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::clear().
void BoUpSLP::computeMinimumValueSizes | ( | ) |
Compute the minimum type sizes required to represent the entries in a vectorizable tree.
Definition at line 14227 of file SLPVectorizer.cpp.
References llvm::all_of(), llvm::any_of(), llvm::SmallVectorImpl< T >::append(), assert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::begin(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::ArrayRef< T >::begin(), llvm::bit_ceil(), llvm::Constant::classof(), llvm::SmallVectorImpl< T >::clear(), llvm::computeKnownBits(), llvm::ComputeNumSignBits(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), DL, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::empty(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::ArrayRef< T >::end(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::erase(), F, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::ArrayRef< T >::front(), llvm::IntegerType::get(), llvm::FixedVectorType::get(), llvm::DemandedBits::getDemandedBits(), llvm::TargetTransformInfo::getNumberOfParts(), getOpcode(), llvm::Value::getType(), getType(), I, Idx, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::isKnownNonNegative(), llvm::KnownBits::isNonNegative(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::size(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace(), and llvm::slpvectorizer::BoUpSLP::EdgeInfo::UserTE.
|
inline |
Clear the internal data structures that are created by 'buildTree'.
Definition at line 1077 of file SLPVectorizer.cpp.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::clear(), llvm::SetVector< T, Vector, Set, N >::clear(), llvm::SmallPtrSetImplBase::clear(), and llvm::SmallVectorImpl< T >::clear().
Referenced by buildTree().
|
inline |
Returns whether the root node has in-tree uses.
Definition at line 1058 of file SLPVectorizer.cpp.
References llvm::SmallVectorBase< Size_T >::empty(), and llvm::SmallVectorTemplateCommon< T, typename >::front().
|
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 2266 of file SLPVectorizer.cpp.
References I.
Referenced by optimizeGatherSequence(), and vectorizeTree().
|
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.
Limit | Lower limit of the cost, considered to be good enough score. |
Definition at line 2241 of file SLPVectorizer.cpp.
References llvm::slpvectorizer::BoUpSLP::LookAheadHeuristics::getScoreAtLevelRec(), I, and RootLookAheadMaxDepth.
std::optional< BoUpSLP::OrdersType > BoUpSLP::findPartiallyOrderedLoads | ( | const TreeEntry & | TE | ) |
Sort loads into increasing pointers offsets to allow greater clustering.
Definition at line 4450 of file SLPVectorizer.cpp.
References assert(), clusterSortPtrAccesses(), DL, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallVectorImpl< T >::reserve().
Referenced by getReorderingData().
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 3855 of file SLPVectorizer.cpp.
References llvm::SmallBitVector::all(), llvm::all_of(), llvm::SmallBitVector::any(), llvm::any_of(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::MutableArrayRef< T >::begin(), llvm::count_if(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::MutableArrayRef< T >::end(), llvm::find(), llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::FixedVectorType::get(), llvm::TargetTransformInfo::getNumberOfParts(), I, Idx, if(), isConstant(), isValidElementType(), llvm::PoisonMaskElem, llvm::SmallBitVector::set(), llvm::SmallVectorBase< Size_T >::size(), llvm::TargetTransformInfo::SK_PermuteSingleSrc, and llvm::SmallBitVector::test().
Referenced by getReorderingData().
|
inline |
Definition at line 1164 of file SLPVectorizer.cpp.
References llvm::TargetTransformInfo::getMaximumVF(), and MaxVFOption.
Referenced by canVectorizeLoads().
|
inline |
Definition at line 1151 of file SLPVectorizer.cpp.
|
inline |
Definition at line 1156 of file SLPVectorizer.cpp.
Referenced by getMinVF().
Definition at line 1160 of file SLPVectorizer.cpp.
References getMinVecRegSize().
Referenced by canVectorizeLoads().
|
inline |
Definition at line 1213 of file SLPVectorizer.cpp.
std::optional< BoUpSLP::OrdersType > BoUpSLP::getReorderingData | ( | const TreeEntry & | TE, |
bool | TopToBottom | ||
) |
Gets reordering data for the given tree entry.
If the entry is vectorized
TopToBottom | If true, include the order of vectorized stores and insertelement nodes, otherwise skip them. |
Definition at line 4522 of file SLPVectorizer.cpp.
References addMask(), llvm::all_of(), allConstant(), allSameType(), llvm::any_of(), areTwoInsertFromSameBuildVector(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::UndefValue::classof(), llvm::count_if(), llvm::Data, E, 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::TargetTransformInfo::getNumberOfParts(), llvm::Value::getNumUses(), llvm::User::getOperand(), llvm::TargetTransformInfo::getShuffleCost(), llvm::TargetTransformInfo::getVectorInstrCost(), I, Idx, llvm::inversePermutation(), llvm::ShuffleVectorInst::isOneUseSingleSourceMask(), isReverseOrder(), isSplat(), llvm::PoisonMaskElem, reorderOrder(), llvm::SmallBitVector::set(), llvm::SmallVectorBase< Size_T >::size(), llvm::TargetTransformInfo::SK_PermuteSingleSrc, llvm::ArrayRef< T >::slice(), llvm::stable_sort(), llvm::TargetTransformInfo::TCK_RecipThroughput, llvm::SmallBitVector::test(), llvm::transform(), and llvm::Value::user_begin().
Referenced by reorderBottomToTop(), and reorderTopToBottom().
Return the scalars of the root node.
Definition at line 1064 of file SLPVectorizer.cpp.
References assert(), llvm::SmallVectorBase< Size_T >::empty(), and llvm::SmallVectorTemplateCommon< T, typename >::front().
InstructionCost BoUpSLP::getSpillCost | ( | ) | const |
Definition at line 9306 of file SLPVectorizer.cpp.
References A, assert(), B, 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(), 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().
InstructionCost BoUpSLP::getTreeCost | ( | ArrayRef< Value * > | VectorizedVals = std::nullopt | ) |
VL
. A negative number means that this is profitable. Definition at line 9577 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, CostKind, llvm::SmallPtrSetImpl< PtrType >::count(), llvm::Data, llvm::dbgs(), DL, llvm::dump(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::ArrayRef< T >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::enumerate(), F, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::find_if(), llvm::IntegerType::get(), llvm::FixedVectorType::get(), llvm::TargetTransformInfo::getCastInstrCost(), llvm::Type::getContext(), llvm::TargetTransformInfo::getExtractWithExtendCost(), getInsertIndex(), llvm::TargetTransformInfo::getScalarizationOverhead(), getShuffleCost(), llvm::TargetTransformInfo::getShuffleCost(), getSpillCost(), llvm::InsertElementInst::getType(), llvm::TargetTransformInfo::getVectorInstrCost(), llvm::APInt::getZero(), I, Idx, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), isFirstInsertElement(), llvm::ShuffleVectorInst::isIdentityMask(), LLVM_DEBUG, llvm::TargetTransformInfo::None, OS, llvm::PoisonMaskElem, llvm::SmallVectorTemplateBase< T, bool >::push_back(), shortBundleName(), llvm::SmallVectorBase< Size_T >::size(), llvm::TargetTransformInfo::SK_PermuteSingleSrc, llvm::TargetTransformInfo::SK_PermuteTwoSrc, llvm::TargetTransformInfo::TCK_RecipThroughput, llvm::Vector, llvm::ViewGraph(), and ViewSLPTree.
|
inline |
Definition at line 1098 of file SLPVectorizer.cpp.
References llvm::SmallVectorBase< Size_T >::size().
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 13912 of file SLPVectorizer.cpp.
References DL, 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().
|
inline |
Checks if the instruction was already analyzed for being possible reduction root.
Definition at line 2272 of file SLPVectorizer.cpp.
References I.
|
inline |
Checks if the given value is gathered in one of the nodes.
Definition at line 2297 of file SLPVectorizer.cpp.
References llvm::any_of(), and llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains().
|
inline |
Checks if the instruction is marked for deletion.
Definition at line 2261 of file SLPVectorizer.cpp.
References I.
Referenced by buildExternalUses(), and optimizeGatherSequence().
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 9226 of file SLPVectorizer.cpp.
References isLoadCombineCandidateImpl(), llvm::PatternMatch::m_Store(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and X.
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 9216 of file SLPVectorizer.cpp.
References isLoadCombineCandidateImpl(), and llvm::Or.
Definition at line 9239 of file SLPVectorizer.cpp.
References llvm::all_of(), allConstant(), allSameBlock(), llvm::any_of(), llvm::count_if(), isSplat(), MinTreeSize, and SLPCostThreshold.
Check if the value is vectorized in the tree.
Definition at line 2302 of file SLPVectorizer.cpp.
void BoUpSLP::optimizeGatherSequence | ( | ) |
Perform LICM and CSE on the newly generated gather sequences.
Definition at line 13174 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(), 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::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::is_contained(), isDeleted(), llvm::DominatorTree::isReachableFromEntry(), LLVM_DEBUG, llvm::make_early_inc_range(), N, llvm::PoisonMaskElem, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorImpl< T >::reserve(), llvm::ArrayRef< T >::size(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::size(), llvm::SetVector< T, Vector, Set, N >::size(), llvm::SmallVectorBase< Size_T >::size(), and llvm::sort().
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 5152 of file SLPVectorizer.cpp.
References llvm::all_of(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallPtrSetImplBase::clear(), combineOrders(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::count(), llvm::count_if(), llvm::Data, llvm::drop_begin(), E, llvm::slpvectorizer::BoUpSLP::EdgeInfo::EdgeIdx, llvm::SetVector< T, Vector, Set, N >::empty(), fixupOrderingIndices(), Gather, getReorderingData(), I, Idx, llvm::SetVector< T, Vector, Set, N >::insert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::inversePermutation(), P, llvm::PoisonMaskElem, llvm::SmallVectorTemplateBase< T, bool >::push_back(), reorderOrder(), reorderReuses(), llvm::reorderScalars(), llvm::ArrayRef< T >::size(), llvm::sort(), llvm::transform(), Users, and llvm::slpvectorizer::BoUpSLP::EdgeInfo::UserTE.
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 4830 of file SLPVectorizer.cpp.
References addMask(), llvm::all_of(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), combineOrders(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), 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::FixedVectorType::get(), getReorderingData(), I, Idx, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::inversePermutation(), llvm::isa(), llvm::TargetTransformInfo::isLegalAltInstr(), llvm::PoisonMaskElem, RecursionMaxDepth, reorderOrder(), llvm::reorderScalars(), llvm::SmallBitVector::set(), llvm::ArrayRef< T >::size(), llvm::transform(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().
Value * BoUpSLP::vectorizeTree | ( | ) |
Vectorize the tree that starts with the elements in VL
.
Returns the vectorized root.
Definition at line 12645 of file SLPVectorizer.cpp.
References vectorizeTree().
Referenced by vectorizeTree().
Value * BoUpSLP::vectorizeTree | ( | const ExtraValueToDebugLocsMap & | ExternallyUsedValues, |
SmallVectorImpl< std::pair< Value *, Value * > > & | ReplacedExternals, | ||
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.
ReplacedExternals | containd list of replaced external values {scalar, replace} after emitting extractelement for external uses. |
Definition at line 12662 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(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear(), llvm::Instruction::comesBefore(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::count(), llvm::IRBuilderBase::CreateExtractElement(), llvm::IRBuilderBase::CreateIntCast(), llvm::Data, llvm::dbgs(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::BasicBlock::end(), eraseInstruction(), F, llvm::slpvectorizer::BoUpSLP::ShuffleInstructionBuilder::finalize(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::find_if(), llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::ArrayRef< T >::front(), llvm::get(), llvm::FixedVectorType::get(), llvm::PoisonValue::get(), llvm::SetVector< T, Vector, Set, N >::getArrayRef(), llvm::IRBuilderBase::GetInsertBlock(), getInsertIndex(), llvm::IRBuilderBase::GetInsertPoint(), llvm::IRBuilderBase::getInt32(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::User::getOperand(), llvm::BasicBlock::getParent(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::InsertElementInst::getType(), llvm::Value::getType(), I, Idx, llvm::SetVector< T, Vector, Set, N >::insert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::is_contained(), isFirstInsertElement(), llvm::Type::isIntOrIntVectorTy(), LLVM_DEBUG, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::Instruction::moveAfter(), PHI, llvm::PoisonMaskElem, 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::IRBuilderBase::SetCurrentDebugLocation(), llvm::IRBuilderBase::SetInsertPoint(), llvm::SmallVectorBase< Size_T >::size(), llvm::sort(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace(), llvm::User::User(), llvm::Vector, and vectorizeTree().
|
friend |
Definition at line 3272 of file SLPVectorizer.cpp.
|
friend |
Definition at line 3272 of file SLPVectorizer.cpp.
|
friend |
Definition at line 3272 of file SLPVectorizer.cpp.