LLVM 22.0.0git
Classes | Public Types | Public Member Functions | Static 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 buildTreeRec(). 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 ,
  CompressVectorize
}
 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 = SmallDenseSet< Value *, 4 >
 
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, Instruction *ReductionRoot=nullptr, ArrayRef< std::tuple< Value *, unsigned, bool > > VectorValuesAndScales={})
 Vectorize the tree but with the list of externally used values ExternallyUsedValues.
 
InstructionCost getSpillCost ()
 
InstructionCost getTreeCost (ArrayRef< Value * > VectorizedVals={}, InstructionCost ReductionCost=TTI::TCC_Free)
 
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.
 
ArrayRef< Value * > getRootNodeScalars () const
 Return the scalars of the root node.
 
std::optional< std::pair< Type *, bool > > getRootNodeTypeWithNoCast () const
 Returns the type/is-signed info for the root node in the graph without casting.
 
bool isSignedMinBitwidthRootNode () const
 Checks if the root graph node can be emitted with narrower bitwidth at codegen and returns it signedness, if so.
 
FixedVectorType * getReductionType () const
 Returns reduction type after minbitdth analysis.
 
void buildExternalUses (const ExtraValueToDebugLocsMap &ExternallyUsedValues={})
 Builds external uses of the vectorized scalars, i.e.
 
void transformNodes ()
 Transforms graph nodes to target specific representations, if profitable.
 
void deleteTree ()
 Clear the internal data structures that are created by 'buildTree'.
 
unsigned getTreeSize () const
 
unsigned getCanonicalGraphSize () const
 Returns the base graph size, before any transformations.
 
void optimizeGatherSequence ()
 Perform LICM and CSE on the newly generated gather sequences.
 
std::optional< OrdersType > findReusedOrderedScalars (const TreeEntry &TE, bool TopToBottom, bool IgnoreReorder)
 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, bool IgnoreReorder)
 Gets reordering data for the given tree entry.
 
bool isProfitableToReorder () const
 Checks if it is profitable to reorder the current tree.
 
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 isTreeNotExtendable () const
 Checks if the graph and all its subgraphs cannot be better vectorized.
 
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 (ArrayRef< Value * > Stores) 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, unsigned *BestVF=nullptr, bool TryRecursiveCheck=true) const
 Checks if the given array of loads can be represented as a vectorized, scatter or just simple gather.
 
template<typename T >
void registerNonVectorizableLoads (ArrayRef< T * > VL)
 Registers non-vectorizable sequence of loads.
 
template<typename T >
bool areKnownNonVectorizableLoads (ArrayRef< T * > VL) const
 Checks if the given loads sequence is known as not vectorizable.
 
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.
 
template<typename T >
void removeInstructionsAndOperands (ArrayRef< T * > DeadVals, ArrayRef< std::tuple< Value *, unsigned, bool > > VectorValuesAndScales)
 Remove instructions from the parent function and clear the operands of DeadVals instructions, marking for deletion trivially dead operands.
 
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 isGathered (const Value *V) const
 Checks if the given value is gathered in one of the nodes.
 
bool isNotScheduled (const Value *V) const
 Checks if the specified value was not schedule.
 
bool isVectorized (const Value *V) const
 Check if the value is vectorized in the tree.
 
 ~BoUpSLP ()
 

Static Public Member Functions

static bool isIdentityOrder (ArrayRef< unsigned > Order)
 Does this non-empty order represent an identity order? Identity should be represented as an empty order, so this is used to decide if we can canonicalize a computed order.
 

Friends

struct DenseMapInfo< EdgeInfo >
 
struct GraphTraits< BoUpSLP * >
 
struct DOTGraphTraits< BoUpSLP * >
 
raw_ostream & operator<< (raw_ostream &OS, const BoUpSLP::ScheduleEntity &SE)
 
raw_ostream & operator<< (raw_ostream &OS, const BoUpSLP::ScheduleData &SD)
 
raw_ostream & operator<< (raw_ostream &OS, const BoUpSLP::ScheduleBundle &Bundle)
 
raw_ostream & operator<< (raw_ostream &OS, const BoUpSLP::ScheduleCopyableData &SD)
 

Detailed Description

Bottom Up SLP Vectorizer.

Definition at line 1910 of file SLPVectorizer.cpp.

Member Typedef Documentation

◆ ExtraValueToDebugLocsMap

using llvm::slpvectorizer::BoUpSLP::ExtraValueToDebugLocsMap = SmallDenseSet<Value *, 4>

Definition at line 1933 of file SLPVectorizer.cpp.

◆ InstrList

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

Definition at line 1930 of file SLPVectorizer.cpp.

◆ OrdersType

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

Definition at line 1934 of file SLPVectorizer.cpp.

◆ StoreList

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

Definition at line 1932 of file SLPVectorizer.cpp.

◆ ValueList

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

Definition at line 1929 of file SLPVectorizer.cpp.

◆ ValueSet

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

Definition at line 1931 of file SLPVectorizer.cpp.

Member Enumeration Documentation

◆ LoadsState

enum class llvm::slpvectorizer::BoUpSLP::LoadsState
strong

Tracks the state we can represent the loads in the given sequence.

Enumerator
Gather 
Vectorize 
ScatterVectorize 
StridedVectorize 
CompressVectorize 

Definition at line 1921 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 1936 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 6004 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 3533 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 3543 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 3538 of file SLPVectorizer.cpp.

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

◆ areKnownNonVectorizableLoads()

template<typename T >
bool llvm::slpvectorizer::BoUpSLP::areKnownNonVectorizableLoads ( ArrayRef< T * >  VL) const
inline

Checks if the given loads sequence is known as not vectorizable.

Definition at line 2238 of file SLPVectorizer.cpp.

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

Referenced by canVectorizeLoads().

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

References llvm::all_of(), assert(), llvm::dbgs(), doesInTreeUserNeedToExtract(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::find(), llvm::SmallPtrSetImpl< PtrType >::insert(), isDeleted(), LLVM_DEBUG, llvm::none_of(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::size(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace(), and UsesLimit.

◆ buildTree() [1/2]

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

Construct a vectorizable tree that starts at Roots.

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

References allSameType(), and deleteTree().

◆ canMapToVector()

unsigned BoUpSLP::canMapToVector ( Type *  T) 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 11814 of file SLPVectorizer.cpp.

References DL, getWidenedType(), llvm::Type::isEmptyTy(), isValidElementType(), and N.

◆ canVectorizeLoads()

BoUpSLP::LoadsState BoUpSLP::canVectorizeLoads ( ArrayRef< Value * >  VL,
const Value *  VL0,
SmallVectorImpl< unsigned > &  Order,
SmallVectorImpl< Value * > &  PointerOps,
unsigned *  BestVF = nullptr,
bool  TryRecursiveCheck = true 
) const

Checks if the given array of loads can be represented as a vectorized, scatter or just simple gather.

Parameters
VLlist of loads.
VL0main load value.
Orderreturned order of load instructions.
PointerOpsreturned list of pointer operands.
BestVFreturn best vector factor, if recursive check found better vectorization sequences rather than masked gather.
TryRecursiveCheckused to check if long masked gather can be represented as a serie of loads/insert subvector, if profitable.

Definition at line 6839 of file SLPVectorizer.cpp.

References llvm::all_of(), llvm::any_of(), areKnownNonVectorizableLoads(), arePointersCompatible(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::ArrayRef< T >::begin(), llvm::CallingConv::C, calculateRtStride(), canVectorizeLoads(), llvm::SmallVectorImpl< T >::clear(), llvm::APInt::clearAllBits(), CompressVectorize, CostKind, llvm::count_if(), DL, llvm::doesNotNeedToBeScheduled(), llvm::SmallVectorBase< Size_T >::empty(), llvm::ArrayRef< T >::end(), End, llvm::enumerate(), llvm::TargetTransformInfo::forceScalarizeMaskedGather(), llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::ArrayRef< T >::front(), Gather, GEP, llvm::APInt::getAllOnes(), getFloorFullVectorNumberOfElements(), llvm::TargetTransformInfo::getGatherScatterOpCost(), getGEPCosts(), llvm::TargetTransformInfo::getInstructionCost(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::TargetTransformInfo::getMaskedMemoryOpCost(), llvm::TargetTransformInfo::getMemoryOpCost(), getMinVF(), llvm::APInt::getOneBitSet(), getParent(), llvm::getPointerOperand(), llvm::getPointersDiff(), getScalarizationOverhead(), getShuffleCost(), llvm::TargetTransformInfo::getStridedMemoryOpCost(), llvm::Value::getType(), llvm::getUnderlyingObject(), getWidenedType(), llvm::hasFullVectorsOrPowerOf2(), I, Idx, llvm::APInt::isAllOnes(), llvm::TargetTransformInfo::isLegalMaskedGather(), llvm::TargetTransformInfo::isLegalStridedLoadStore(), isMaskedLoadCompress(), isReverseOrder(), isStridedLoad(), llvm::TargetTransformInfo::isTypeLegal(), llvm::APInt::isZero(), MinProfitableStridedLoads, P, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorImpl< T >::resize(), ScatterVectorize, llvm::APInt::setAllBits(), llvm::APInt::setBits(), llvm::ArrayRef< T >::size(), llvm::SmallVectorBase< Size_T >::size(), llvm::TargetTransformInfo::SK_Broadcast, llvm::TargetTransformInfo::SK_InsertSubvector, llvm::TargetTransformInfo::SK_PermuteSingleSrc, llvm::ArrayRef< T >::slice(), SLPCostThreshold, llvm::sortPtrAccesses(), StridedVectorize, llvm::TargetTransformInfo::TCK_RecipThroughput, and Vectorize.

Referenced by canVectorizeLoads(), and getReorderingData().

◆ clearReductionData()

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

Clear the list of the analyzed reduction root instructions.

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

References llvm::all_of(), llvm::any_of(), assert(), llvm::bit_ceil(), llvm::SmallVectorImpl< T >::clear(), llvm::ComputeNumSignBits(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), DL, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), F, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::IntegerType::get(), llvm::DemandedBits::getDemandedBits(), llvm::getNumberOfParts(), getNumElements(), getOpcode(), llvm::Type::getScalarType(), llvm::Value::getType(), getWidenedType(), I, llvm::isGather(), llvm::none_of(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::size(), and UsesLimit.

◆ deleteTree()

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

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

Definition at line 2051 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().

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

References I.

Referenced by optimizeGatherSequence(), removeInstructionsAndOperands(), and vectorizeTree().

◆ findBestRootPair()

std::optional< int > llvm::slpvectorizer::BoUpSLP::findBestRootPair ( ArrayRef< std::pair< Value *, Value * > >  Candidates,
int  Limit = LookAheadHeuristics::ScoreFail 
) const
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
LimitLower limit of the cost, considered to be good enough score.

Definition at line 3411 of file SLPVectorizer.cpp.

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

Referenced by transformNodes().

◆ findPartiallyOrderedLoads()

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

Sort loads into increasing pointers offsets to allow greater clustering.

Definition at line 7262 of file SLPVectorizer.cpp.

References assert(), clusterSortPtrAccesses(), llvm::SetVector< T, Vector, Set, N >::contains(), DL, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallVectorImpl< T >::reserve().

Referenced by getReorderingData().

◆ findReusedOrderedScalars()

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

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.

Parameters
TopToBottomIf true, used for the whole tree rotation, false - for sub-tree rotations.
IgnoreReordertrue, if the order of the root node might be ignored.

Definition at line 6104 of file SLPVectorizer.cpp.

References llvm::SmallBitVector::all(), llvm::all_of(), llvm::SmallBitVector::any(), llvm::any_of(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::count(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::enumerate(), llvm::fill(), llvm::find(), llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::getNumberOfParts(), getNumElems(), getPartNumElems(), getWidenedType(), I, Idx, isConstant(), isValidElementType(), P, llvm::PoisonMaskElem, llvm::SmallBitVector::set(), llvm::SmallVectorBase< Size_T >::size(), llvm::TargetTransformInfo::SK_PermuteSingleSrc, and llvm::SmallBitVector::test().

Referenced by getReorderingData().

◆ getCanonicalGraphSize()

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

Returns the base graph size, before any transformations.

Definition at line 2084 of file SLPVectorizer.cpp.

Referenced by isTreeNotExtendable().

◆ getMaximumVF()

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

Definition at line 2173 of file SLPVectorizer.cpp.

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

◆ getMaxVecRegSize()

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

Definition at line 2160 of file SLPVectorizer.cpp.

◆ getMinVecRegSize()

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

Definition at line 2165 of file SLPVectorizer.cpp.

Referenced by getMinVF().

◆ getMinVF()

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

Definition at line 2169 of file SLPVectorizer.cpp.

References getMinVecRegSize().

Referenced by canVectorizeLoads().

◆ getORE()

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

Definition at line 2242 of file SLPVectorizer.cpp.

◆ getReductionType()

FixedVectorType * llvm::slpvectorizer::BoUpSLP::getReductionType ( ) const
inline

Returns reduction type after minbitdth analysis.

Definition at line 2024 of file SLPVectorizer.cpp.

References DL, llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::IntegerType::get(), and getWidenedType().

◆ getReorderingData()

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

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
    TopToBottomIf true, include the order of vectorized stores and insertelement nodes, otherwise skip them.
    IgnoreReordertrue, if the root node order can be ignored.

Definition at line 7344 of file SLPVectorizer.cpp.

References addMask(), llvm::all_of(), allConstant(), allSameType(), llvm::any_of(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), canVectorizeLoads(), llvm::Instruction::comesBefore(), CompressVectorize, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), llvm::count_if(), llvm::Data, llvm::divideCeil(), E, llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::enumerate(), llvm::find(), llvm::find_if_not(), findPartiallyOrderedLoads(), findReusedOrderedScalars(), fixupOrderingIndices(), llvm::PoisonValue::get(), getElementIndex(), getExtractIndex(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::getNumberOfParts(), llvm::Value::getNumUses(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), getParent(), getShuffleCost(), llvm::TargetTransformInfo::getVectorInstrCost(), getWidenedType(), I, Idx, II, llvm::inversePermutation(), isAlternateInstruction(), llvm::Instruction::isBinaryOp(), isConstant(), isIdentityOrder(), llvm::ShuffleVectorInst::isOneUseSingleSourceMask(), llvm::DominatorTree::isReachableFromEntry(), isReverseOrder(), isSplat(), llvm::PoisonMaskElem, reorderOrder(), llvm::SmallBitVector::set(), llvm::SmallVectorBase< Size_T >::size(), llvm::TargetTransformInfo::SK_PermuteSingleSrc, llvm::ArrayRef< T >::slice(), llvm::stable_sort(), StridedVectorize, llvm::TargetTransformInfo::TCK_RecipThroughput, llvm::SmallBitVector::test(), llvm::transform(), llvm::Value::use_empty(), llvm::Value::user_begin(), Vectorize, VectorizeNonPowerOf2, and llvm::zip().

Referenced by reorderBottomToTop(), and reorderTopToBottom().

◆ getRootNodeScalars()

ArrayRef< Value * > llvm::slpvectorizer::BoUpSLP::getRootNodeScalars ( ) const
inline

Return the scalars of the root node.

Definition at line 1993 of file SLPVectorizer.cpp.

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

◆ getRootNodeTypeWithNoCast()

std::optional< std::pair< Type *, bool > > llvm::slpvectorizer::BoUpSLP::getRootNodeTypeWithNoCast ( ) const
inline

Returns the type/is-signed info for the root node in the graph without casting.

Definition at line 2000 of file SLPVectorizer.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::SmallVectorTemplateCommon< T, typename >::front(), and llvm::IntegerType::get().

◆ getSpillCost()

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

Definition at line 15458 of file SLPVectorizer.cpp.

References allConstant(), llvm::SmallVectorImpl< T >::append(), assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::at(), BlockSize, Cleanup, llvm::Instruction::comesBefore(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), llvm::SmallPtrSetImpl< PtrType >::contains(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::First, llvm::IntegerType::get(), llvm::IntrinsicCostAttributes::getArgTypes(), llvm::TargetTransformInfo::getCallInstrCost(), llvm::Type::getContext(), llvm::TargetTransformInfo::getCostOfKeepingLiveOverCall(), llvm::BasicBlock::getFirstNonPHIOrDbgOrAlloca(), llvm::TargetTransformInfo::getIntrinsicInstrCost(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getTerminator(), getWidenedType(), I, II, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), isVectorized(), llvm::Type::isVectorTy(), llvm::Last, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::make_scope_exit(), Operands, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::pred_begin(), llvm::pred_end(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), ScheduleRegionSizeBudget, llvm::BasicBlock::size(), llvm::TargetTransformInfo::TCK_RecipThroughput, and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().

Referenced by getTreeCost().

◆ getTreeCost()

InstructionCost BoUpSLP::getTreeCost ( ArrayRef< Value * >  VectorizedVals = {},
InstructionCost  ReductionCost = TTI::TCC_Free 
)
Returns
the vectorization cost of the subtree that starts at VL. A negative number means that this is profitable.

Definition at line 15851 of file SLPVectorizer.cpp.

References llvm::all_of(), llvm::any_of(), areTwoInsertFromSameBuildVector(), assert(), llvm::sampleprof::Base, llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::CallingConv::C, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), CostKind, llvm::SmallPtrSetImpl< PtrType >::count(), llvm::count_if(), 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::SmallVectorTemplateCommon< T, typename >::front(), llvm::IntegerType::get(), llvm::TargetTransformInfo::getCastInstrCost(), llvm::Type::getContext(), getElementIndex(), getExtractWithExtendCost(), llvm::TargetTransformInfo::getInstructionCost(), llvm::FixedVectorType::getNumElements(), llvm::User::getOperand(), llvm::TargetTransformInfo::getScalarizationOverhead(), llvm::Type::getScalarType(), getShuffleCost(), getSpillCost(), llvm::InsertElementInst::getType(), getVectorInstrCost(), getWidenedType(), llvm::APInt::getZero(), llvm::has_single_bit(), I, Idx, II, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::is_contained(), isFirstInsertElement(), llvm::ShuffleVectorInst::isIdentityMask(), llvm::isKnownNonNegative(), llvm::DominatorTree::isReachableFromEntry(), isVectorized(), LLVM_DEBUG, llvm::TargetTransformInfo::None, llvm::none_of(), OS, P, llvm::PoisonMaskElem, llvm::SmallVectorTemplateBase< T, bool >::push_back(), shortBundleName(), llvm::SmallVectorBase< Size_T >::size(), llvm::TargetTransformInfo::SK_PermuteSingleSrc, llvm::TargetTransformInfo::SK_PermuteTwoSrc, SLPCostThreshold, SLPReVec, llvm::TargetTransformInfo::TCC_Basic, llvm::TargetTransformInfo::TCC_Free, llvm::TargetTransformInfo::TCK_RecipThroughput, UsesLimit, llvm::Vector, llvm::ViewGraph(), and ViewSLPTree.

◆ getTreeSize()

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

Definition at line 2081 of file SLPVectorizer.cpp.

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

Referenced by isTreeNotExtendable().

◆ 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 21584 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::IRBuilderBase::getInt1Ty(), getVectorElementSize(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), llvm::SmallVectorImpl< T >::pop_back_val(), and RecursionMaxDepth.

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 3528 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 3553 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 3431 of file SLPVectorizer.cpp.

References I.

Referenced by buildExternalUses(), and optimizeGatherSequence().

◆ isGathered()

bool llvm::slpvectorizer::BoUpSLP::isGathered ( const Value *  V) const
inline

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

Definition at line 3557 of file SLPVectorizer.cpp.

References llvm::SmallPtrSetImpl< PtrType >::contains().

◆ isIdentityOrder()

static bool llvm::slpvectorizer::BoUpSLP::isIdentityOrder ( ArrayRef< unsigned >  Order)
inlinestatic

Does this non-empty order represent an identity order? Identity should be represented as an empty order, so this is used to decide if we can canonicalize a computed order.

Undef elements (represented as size) are ignored.

Definition at line 2093 of file SLPVectorizer.cpp.

References llvm::all_of(), assert(), llvm::ArrayRef< T >::empty(), llvm::enumerate(), P, and llvm::ArrayRef< T >::size().

Referenced by getReorderingData(), reorderBottomToTop(), and reorderTopToBottom().

◆ isLoadCombineCandidate()

bool BoUpSLP::isLoadCombineCandidate ( ArrayRef< Value * >  Stores) 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 15235 of file SLPVectorizer.cpp.

References isLoadCombineCandidateImpl(), llvm::PatternMatch::m_Store(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::ArrayRef< T >::size(), 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 15225 of file SLPVectorizer.cpp.

References isLoadCombineCandidateImpl(), and llvm::Or.

◆ isNotScheduled()

bool llvm::slpvectorizer::BoUpSLP::isNotScheduled ( const Value *  V) const
inline

Checks if the specified value was not schedule.

Definition at line 3561 of file SLPVectorizer.cpp.

References llvm::SmallPtrSetImpl< PtrType >::contains().

◆ isProfitableToReorder()

bool BoUpSLP::isProfitableToReorder ( ) const

Checks if it is profitable to reorder the current tree.

If the tree does not contain many profitable reordable nodes, better to skip it to save compile time.

Definition at line 7765 of file SLPVectorizer.cpp.

References llvm::all_of(), llvm::any_of(), llvm::count_if(), llvm::Instruction::isBinaryOp(), isCommutative(), and llvm::none_of().

◆ isSignedMinBitwidthRootNode()

bool llvm::slpvectorizer::BoUpSLP::isSignedMinBitwidthRootNode ( ) const
inline

Checks if the root graph node can be emitted with narrower bitwidth at codegen and returns it signedness, if so.

Definition at line 2019 of file SLPVectorizer.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::at(), and llvm::SmallVectorTemplateCommon< T, typename >::front().

◆ isTreeNotExtendable()

bool BoUpSLP::isTreeNotExtendable ( ) const

Checks if the graph and all its subgraphs cannot be better vectorized.

It may happen, if all gather nodes are loads and they cannot be "clusterized". In this case even subgraphs cannot be vectorized more effectively than the base graph.

Definition at line 15424 of file SLPVectorizer.cpp.

References llvm::all_of(), allConstant(), allSameBlock(), llvm::count_if(), llvm::ArrayRef< T >::drop_front(), getCanonicalGraphSize(), getSameOpcode(), getTreeSize(), Idx, and isSplat().

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

References llvm::all_of(), allConstant(), allSameBlock(), llvm::any_of(), assert(), llvm::count_if(), llvm::SmallVectorBase< Size_T >::empty(), llvm::APInt::getAllOnes(), llvm::TargetTransformInfo::getScalarizationOverhead(), getWidenedType(), if(), isSplat(), MinTreeSize, llvm::none_of(), llvm::DebugCounter::shouldExecute(), llvm::SmallVectorBase< Size_T >::size(), SLPCostThreshold, and llvm::TargetTransformInfo::TCK_RecipThroughput.

◆ isVectorized()

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

Check if the value is vectorized in the tree.

Definition at line 3566 of file SLPVectorizer.cpp.

References assert().

Referenced by getSpillCost(), getTreeCost(), and vectorizeTree().

◆ optimizeGatherSequence()

void BoUpSLP::optimizeGatherSequence ( )

Perform LICM and CSE on the newly generated gather sequences.

Definition at line 20565 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::ilist_node_impl< OptionsT >::getIterator(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::getNumberOfParts(), llvm::BasicBlock::getTerminator(), getWidenedType(), 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().

◆ registerNonVectorizableLoads()

template<typename T >
void llvm::slpvectorizer::BoUpSLP::registerNonVectorizableLoads ( ArrayRef< T * >  VL)
inline

Registers non-vectorizable sequence of loads.

Definition at line 2232 of file SLPVectorizer.cpp.

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

◆ removeInstructionsAndOperands()

template<typename T >
void llvm::slpvectorizer::BoUpSLP::removeInstructionsAndOperands ( ArrayRef< T * >  DeadVals,
ArrayRef< std::tuple< Value *, unsigned, bool > >  VectorValuesAndScales 
)
inline

Remove instructions from the parent function and clear the operands of DeadVals instructions, marking for deletion trivially dead operands.

Definition at line 3443 of file SLPVectorizer.cpp.

References llvm::all_of(), assert(), llvm::SmallVectorBase< Size_T >::empty(), eraseInstruction(), llvm::ScalarEvolution::forgetValue(), I, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::isInstructionTriviallyDead(), llvm::none_of(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::salvageDebugInfo(), llvm::Value::use_empty(), and llvm::wouldInstructionBeTriviallyDead().

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

References llvm::all_of(), llvm::any_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::ArrayRef< T >::empty(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallPtrSetImpl< PtrType >::erase(), llvm::find_if_not(), fixupOrderingIndices(), Gather, getReorderingData(), llvm::getVectorIntrinsicIDForCall(), I, Idx, llvm::SetVector< T, Vector, Set, N >::insert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert_range(), llvm::inversePermutation(), isConstant(), isIdentityOrder(), llvm::isVectorIntrinsicWithScalarOpAtArg(), LHS, llvm::make_second_range(), llvm::Intrinsic::not_intrinsic, P, llvm::PoisonMaskElem, llvm::SmallVectorTemplateBase< T, bool >::push_back(), reorderOrder(), reorderReuses(), llvm::reorderScalars(), RHS, llvm::ArrayRef< T >::size(), llvm::SmallVectorBase< Size_T >::size(), llvm::SetVector< T, Vector, Set, N >::takeVector(), llvm::transform(), and Users.

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

References addMask(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), Cleanup, combineOrders(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), E, llvm::ArrayRef< T >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::empty(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), fixupOrderingIndices(), llvm::for_each(), getAltInstrMask(), getReorderingData(), getWidenedType(), I, Idx, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::inversePermutation(), llvm::isa(), isIdentityOrder(), llvm::make_scope_exit(), llvm::PoisonMaskElem, RecursionMaxDepth, reorderOrder(), llvm::reorderScalars(), llvm::ArrayRef< T >::size(), SLPReVec, llvm::transform(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().

◆ transformNodes()

void BoUpSLP::transformNodes ( )

Transforms graph nodes to target specific representations, if profitable.

Definition at line 12730 of file SLPVectorizer.cpp.

References llvm::all_of(), llvm::any_of(), CostKind, llvm::count_if(), llvm::SmallVectorImpl< T >::emplace_back(), findBestRootPair(), I, Idx, llvm::is_contained(), P, llvm::slpvectorizer::BoUpSLP::LookAheadHeuristics::ScoreSplatLoads, and llvm::TargetTransformInfo::TCK_RecipThroughput.

◆ vectorizeTree() [1/2]

Value * BoUpSLP::vectorizeTree ( )

Vectorize the tree that starts with the elements in VL.

Returns the vectorized root.

Definition at line 19892 of file SLPVectorizer.cpp.

References vectorizeTree().

Referenced by vectorizeTree().

◆ vectorizeTree() [2/2]

Value * BoUpSLP::vectorizeTree ( const ExtraValueToDebugLocsMap &  ExternallyUsedValues,
Instruction *  ReductionRoot = nullptr,
ArrayRef< std::tuple< Value *, unsigned, bool > >  VectorValuesAndScales = {} 
)

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

References llvm::all_of(), llvm::any_of(), areTwoInsertFromSameBuildVector(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::SmallPtrSetImpl< PtrType >::contains(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::count(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::IRBuilderBase::CreateExtractElement(), createExtractVector(), llvm::IRBuilderBase::CreateIntCast(), llvm::Data, llvm::dbgs(), DL, llvm::SmallVectorImpl< T >::emplace_back(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::BasicBlock::end(), eraseInstruction(), F, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::find_if(), llvm::get(), llvm::SetVector< T, Vector, Set, N >::getArrayRef(), getElementIndex(), llvm::IRBuilderBase::GetInsertBlock(), llvm::IRBuilderBase::GetInsertPoint(), llvm::IRBuilderBase::getInt32(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::FixedVectorType::getNumElements(), llvm::User::getOperand(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::InsertElementInst::getType(), llvm::Value::getType(), getWidenedType(), I, Idx, II, llvm::SetVector< T, Vector, Set, N >::insert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::is_contained(), llvm::Type::isIntOrIntVectorTy(), llvm::isKnownNonNegative(), isVectorized(), IV, LLVM_DEBUG, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::mayHaveNonDefUseDependency(), llvm::Instruction::moveAfter(), PHI, llvm::PoisonMaskElem, llvm::Value::replaceAllUsesWith(), llvm::User::replaceUsesOfWith(), llvm::IRBuilderBase::SetCurrentDebugLocation(), llvm::IRBuilderBase::SetInsertPoint(), llvm::SmallVectorBase< Size_T >::size(), SLPReVec, llvm::Value::takeName(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace(), llvm::User::User(), and vectorizeTree().

Friends And Related Function Documentation

◆ DenseMapInfo< EdgeInfo >

friend struct DenseMapInfo< EdgeInfo >
friend

Definition at line 2242 of file SLPVectorizer.cpp.

◆ DOTGraphTraits< BoUpSLP * >

friend struct DOTGraphTraits< BoUpSLP * >
friend

Definition at line 5109 of file SLPVectorizer.cpp.

◆ GraphTraits< BoUpSLP * >

friend struct GraphTraits< BoUpSLP * >
friend

Definition at line 5109 of file SLPVectorizer.cpp.

◆ operator<< [1/4]

raw_ostream & operator<< ( raw_ostream &  OS,
const BoUpSLP::ScheduleBundle &  Bundle 
)
friend

Definition at line 4986 of file SLPVectorizer.cpp.

◆ operator<< [2/4]

raw_ostream & operator<< ( raw_ostream &  OS,
const BoUpSLP::ScheduleCopyableData &  SD 
)
friend

Definition at line 5109 of file SLPVectorizer.cpp.

◆ operator<< [3/4]

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

Definition at line 4879 of file SLPVectorizer.cpp.

◆ operator<< [4/4]

raw_ostream & operator<< ( raw_ostream &  OS,
const BoUpSLP::ScheduleEntity &  SE 
)
friend

Definition at line 4718 of file SLPVectorizer.cpp.

The documentation for this class was generated from the following file:
Generated on Wed Sep 3 2025 18:36:59 for LLVM by doxygen 1.9.6