class BoUpSLP

Declaration

class BoUpSLP { /* full declaration omitted */ };

Description

Bottom Up SLP Vectorizer.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:839

Member Variables

private TreeEntry::VecTreeTy VectorizableTree

-- Vectorization State -- Holds all of the tree entries.

private SmallDenseMap< llvm::Value*, llvm::slpvectorizer::BoUpSLP::TreeEntry*> ScalarToTreeEntry

Maps a specific scalar to its tree entry.

private SmallDenseMap<llvm::Value*, unsigned int> InstrElementSize

Maps a value to the proposed vectorizable size.

private llvm::slpvectorizer::BoUpSLP::ValueSet MustGather

A list of scalars that we found that we need to keep as scalars.

private DenseMap< llvm::slpvectorizer::BoUpSLP::AliasCacheKey, Optional<bool>> AliasCache

Cache for alias results. TODO: consider moving this to the AliasAnalysis itself.

private llvm::BatchAAResults BatchAA

private DenseSet<llvm::Instruction*> DeletedInstructions

Temporary store for deleted instructions. Instructions will be deleted eventually when the BoUpSLP is destructed. The deferral is required to ensure that there are no incorrect collisions in the AliasCache, which can happen if a new instruction is allocated at the same address as a previously deleted instruction.

private SmallPtrSet<llvm::Instruction*, 16> AnalyzedReductionsRoots

Set of the instruction, being analyzed already for reductions.

private DenseSet<size_t> AnalyzedReductionVals

Set of hashes for the list of reduction values already being analyzed.

private llvm::slpvectorizer::BoUpSLP::UserList ExternalUses

A list of values that need to extracted out of the tree. This list holds pairs of (Internal Scalar : External User). External User can be nullptr, it means that this Internal Scalar will be used later, after vectorization.

private SmallPtrSet<const llvm::Value*, 32> EphValues

Values used only by @llvm.assume calls.

private SetVector<llvm::Instruction*> GatherShuffleSeq

Holds all of the instructions that we gathered.

private SetVector<llvm::BasicBlock*> CSEBlocks

A list of blocks that we are going to CSE.

private MapVector<llvm::BasicBlock*, std::unique_ptr<BlockScheduling>> BlocksSchedules

Attaches the BlockScheduling structures to basic blocks.

private const SmallDenseSet<llvm::Value*>* UserIgnoreList = nullptr

List of users to ignore during scheduling and that don't need extracting.

private llvm::Function* F

private llvm::ScalarEvolution* SE

private llvm::TargetTransformInfo* TTI

private llvm::TargetLibraryInfo* TLI

private llvm::LoopInfo* LI

private llvm::DominatorTree* DT

private llvm::AssumptionCache* AC

private llvm::DemandedBits* DB

private const llvm::DataLayout* DL

private llvm::OptimizationRemarkEmitter* ORE

private unsigned int MaxVecRegSize

private unsigned int MinVecRegSize

private IRBuilder<> Builder

Instruction builder to construct the vectorized tree.

private MapVector<llvm::Value*, std::pair<uint64_t, bool>> MinBWs

A map of scalar integer values to the smallest bit width with which they can legally be represented. The values map to (width, signed) pairs, where "width" indicates the minimum bit width and "signed" is True if the value must be signed-extended, rather than zero-extended, back to its original width.

Method Overview

• public BoUpSLP(llvm::Function * Func, llvm::ScalarEvolution * Se, llvm::TargetTransformInfo * Tti, llvm::TargetLibraryInfo * TLi, llvm::AAResults * Aa, llvm::LoopInfo * Li, llvm::DominatorTree * Dt, llvm::AssumptionCache * AC, llvm::DemandedBits * DB, const llvm::DataLayout * DL, llvm::OptimizationRemarkEmitter * ORE)
• private bool CanFormVector(const SmallVector<llvm::StoreInst *, 4> & StoresVec, llvm::slpvectorizer::BoUpSLP::OrdersType & ReorderIndices) const
• public void analyzedReductionRoot(llvm::Instruction * I)
• public void analyzedReductionVals(ArrayRef<llvm::Value *> VL)
• private bool areAllUsersVectorized(llvm::Instruction * I, ArrayRef<llvm::Value *> VectorizedVals) const
• public bool areAnalyzedReductionVals(ArrayRef<llvm::Value *> VL)
• public void buildExternalUses(const llvm::slpvectorizer::BoUpSLP::ExtraValueToDebugLocsMap & ExternallyUsedValues = {})
• public void buildTree(ArrayRef<llvm::Value *> Roots, const SmallDenseSet<llvm::Value *> & UserIgnoreLst)
• public void buildTree(ArrayRef<llvm::Value *> Roots)
• private void buildTree_rec(ArrayRef<llvm::Value *> Roots, unsigned int Depth, const llvm::slpvectorizer::BoUpSLP::EdgeInfo & EI)
• public unsigned int canMapToVector(llvm::Type * T, const llvm::DataLayout & DL) const
• private bool canReorderOperands(llvm::slpvectorizer::BoUpSLP::TreeEntry * UserTE, SmallVectorImpl<std::pair<unsigned int, TreeEntry *>> & Edges, ArrayRef<llvm::slpvectorizer::BoUpSLP::TreeEntry *> ReorderableGathers, SmallVectorImpl<llvm::slpvectorizer::BoUpSLP::TreeEntry *> & GatherOps)
• private bool canReuseExtract(ArrayRef<llvm::Value *> VL, llvm::Value * OpValue, SmallVectorImpl<unsigned int> & CurrentOrder) const
• public void clearReductionData()
• private DenseMap<llvm::Value *, SmallVector<llvm::StoreInst *, 4>> collectUserStores(const BoUpSLP::TreeEntry * TE) const
• public void computeMinimumValueSizes()
• private llvm::Value * createBuildVector(ArrayRef<llvm::Value *> VL)
• public void deleteTree()
• private void dumpTreeCosts(const llvm::slpvectorizer::BoUpSLP::TreeEntry * E, llvm::InstructionCost ReuseShuffleCost, llvm::InstructionCost VecCost, llvm::InstructionCost ScalarCost) const
• private void dumpVectorizableTree() const
• public void eraseInstruction(llvm::Instruction * I)
• public Optional<int> findBestRootPair(ArrayRef<std::pair<Value *, Value *>> Candidates, int Limit = LookAheadHeuristics::ScoreFail)
• private SmallVector<llvm::slpvectorizer::BoUpSLP::OrdersType, 1> findExternalStoreUsersReorderIndices(llvm::slpvectorizer::BoUpSLP::TreeEntry * TE) const
• public Optional<llvm::slpvectorizer::BoUpSLP::OrdersType> findPartiallyOrderedLoads(const llvm::slpvectorizer::BoUpSLP::TreeEntry & TE)
• public Optional<llvm::slpvectorizer::BoUpSLP::OrdersType> findReusedOrderedScalars(const llvm::slpvectorizer::BoUpSLP::TreeEntry & TE)
• private llvm::Value * gather(ArrayRef<llvm::Value *> VL)
• private llvm::InstructionCost getEntryCost(const llvm::slpvectorizer::BoUpSLP::TreeEntry * E, ArrayRef<llvm::Value *> VectorizedVals)
• private llvm::InstructionCost getGatherCost(ArrayRef<llvm::Value *> VL) const
• private llvm::InstructionCost getGatherCost(llvm::FixedVectorType * Ty, const llvm::APInt & ShuffledIndices, bool NeedToShuffle) const
• public unsigned int getMaxVecRegSize() const
• public unsigned int getMaximumVF(unsigned int ElemWidth, unsigned int Opcode) const
• public unsigned int getMinVF(unsigned int Sz) const
• public unsigned int getMinVecRegSize() const
• public llvm::OptimizationRemarkEmitter * getORE()
• public Optional<llvm::slpvectorizer::BoUpSLP::OrdersType> getReorderingData(const llvm::slpvectorizer::BoUpSLP::TreeEntry & TE, bool TopToBottom)
• public llvm::InstructionCost getSpillCost() const
• public llvm::InstructionCost getTreeCost(ArrayRef<llvm::Value *> VectorizedVals = None)
• private const llvm::slpvectorizer::BoUpSLP::TreeEntry * getTreeEntry(llvm::Value * V) const
• private llvm::slpvectorizer::BoUpSLP::TreeEntry * getTreeEntry(llvm::Value * V)
• public unsigned int getTreeSize() const
• public unsigned int getVectorElementSize(llvm::Value * V)
• private llvm::slpvectorizer::BoUpSLP::TreeEntry * getVectorizedOperand(llvm::slpvectorizer::BoUpSLP::TreeEntry * UserTE, unsigned int OpIdx)
• private const llvm::slpvectorizer::BoUpSLP::TreeEntry * getVectorizedOperand(const llvm::slpvectorizer::BoUpSLP::TreeEntry * UserTE, unsigned int OpIdx) const
• private bool isAliased(const llvm::MemoryLocation & Loc1, llvm::Instruction * Inst1, llvm::Instruction * Inst2)
• public bool isAnalyzedReductionRoot(llvm::Instruction * I) const
• public bool isAnyGathered(const SmallDenseSet<llvm::Value *> & Vals) const
• public bool isDeleted(llvm::Instruction * I) const
• private bool isFullyVectorizableTinyTree(bool ForReduction) const
• private Optional<TargetTransformInfo::ShuffleKind> isGatherShuffledEntry(const llvm::slpvectorizer::BoUpSLP::TreeEntry * TE, SmallVectorImpl<int> & Mask, SmallVectorImpl<const llvm::slpvectorizer::BoUpSLP::TreeEntry *> & Entries)
• public bool isLoadCombineCandidate() const
• public bool isLoadCombineReductionCandidate(llvm::RecurKind RdxKind) const
• public bool isTreeTinyAndNotFullyVectorizable(bool ForReduction = false) const
• private llvm::slpvectorizer::BoUpSLP::TreeEntry * newTreeEntry(ArrayRef<llvm::Value *> VL, TreeEntry::EntryState EntryState, Optional<llvm::slpvectorizer::BoUpSLP::ScheduleData *> Bundle, const (anonymous namespace)::InstructionsState & S, const llvm::slpvectorizer::BoUpSLP::EdgeInfo & UserTreeIdx, ArrayRef<int> ReuseShuffleIndices = None, ArrayRef<unsigned int> ReorderIndices = None)
• private llvm::slpvectorizer::BoUpSLP::TreeEntry * newTreeEntry(ArrayRef<llvm::Value *> VL, Optional<llvm::slpvectorizer::BoUpSLP::ScheduleData *> Bundle, const (anonymous namespace)::InstructionsState & S, const llvm::slpvectorizer::BoUpSLP::EdgeInfo & UserTreeIdx, ArrayRef<int> ReuseShuffleIndices = None, ArrayRef<unsigned int> ReorderIndices = None)
• public void optimizeGatherSequence()
• public void reorderBottomToTop(bool IgnoreReorder = false)
• private static void reorderInputsAccordingToOpcode(ArrayRef<llvm::Value *> VL, SmallVectorImpl<llvm::Value *> & Left, SmallVectorImpl<llvm::Value *> & Right, const llvm::DataLayout & DL, llvm::ScalarEvolution & SE, const llvm::slpvectorizer::BoUpSLP & R)
• public void reorderTopToBottom()
• private void scheduleBlock(llvm::slpvectorizer::BoUpSLP::BlockScheduling * BS)
• private void setInsertPointAfterBundle(const llvm::slpvectorizer::BoUpSLP::TreeEntry * E)
• private llvm::Value * vectorizeTree(ArrayRef<llvm::Value *> VL)
• private llvm::Value * vectorizeTree(llvm::slpvectorizer::BoUpSLP::TreeEntry * E)
• public llvm::Value * vectorizeTree(llvm::slpvectorizer::BoUpSLP::ExtraValueToDebugLocsMap & ExternallyUsedValues)
• public llvm::Value * vectorizeTree()
• public ~BoUpSLP()

Methods

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

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:852

Parameters

llvm::Function* Func

llvm::ScalarEvolution* Se

llvm::TargetTransformInfo* Tti

llvm::TargetLibraryInfo* TLi

llvm::AAResults* Aa

llvm::LoopInfo* Li

llvm::DominatorTree* Dt

llvm::AssumptionCache* AC

llvm::DemandedBits* DB

const llvm::DataLayout* DL

llvm::OptimizationRemarkEmitter* ORE

¶bool CanFormVector(
    const SmallVector<llvm::StoreInst*, 4>&
        StoresVec,
    llvm::slpvectorizer::BoUpSLP::OrdersType&
        ReorderIndices) const

Description

Helper for `findExternalStoreUsersReorderIndices()`. It checks if the stores in \p StoresVec can for a vector instruction. If so it returns true and populates \p ReorderIndices with the shuffle indices of the the stores when compared to the sorted vector.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2204

Parameters

const SmallVector<llvm::StoreInst*, 4>& StoresVec

llvm::slpvectorizer::BoUpSLP::OrdersType& ReorderIndices

¶void analyzedReductionRoot(llvm::Instruction* I)

Description

Register given instruction as already analyzed for being possible reduction root.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2061

Parameters

llvm::Instruction* I

¶void analyzedReductionVals(
    ArrayRef<llvm::Value*> VL)

Description

Adds the list of reduced values to list of already checked values for the vectorization.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2071

Parameters

ArrayRef<llvm::Value*> VL

¶bool areAllUsersVectorized(
    llvm::Instruction* I,
    ArrayRef<llvm::Value*> VectorizedVals) const

Description

Checks if all users of \p I are the part of the vectorization tree.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2123

Parameters

llvm::Instruction* I

ArrayRef<llvm::Value*> VectorizedVals

¶bool areAnalyzedReductionVals(
    ArrayRef<llvm::Value*> VL)

Description

Checks if the provided list of reduced values was checked already for vectorization.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2066

Parameters

ArrayRef<llvm::Value*> VL

¶void buildExternalUses(
    const llvm::slpvectorizer::BoUpSLP::
        ExtraValueToDebugLocsMap&
            ExternallyUsedValues = {})

Description

Builds external uses of the vectorized scalars, i.e. the list of vectorized scalars to be extracted, their lanes and their scalar users. \p ExternallyUsedValues contains additional list of external uses to handle vectorization of reductions.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:908

Parameters

const llvm::slpvectorizer::BoUpSLP:: ExtraValueToDebugLocsMap& ExternallyUsedValues = {}

¶void buildTree(ArrayRef<llvm::Value*> Roots,
               const SmallDenseSet<llvm::Value*>&
                   UserIgnoreLst)

Description

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

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:897

Parameters

ArrayRef<llvm::Value*> Roots

const SmallDenseSet<llvm::Value*>& UserIgnoreLst

¶void buildTree(ArrayRef<llvm::Value*> Roots)

Description

Construct a vectorizable tree that starts at \p Roots.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:901

Parameters

ArrayRef<llvm::Value*> Roots

¶void buildTree_rec(
    ArrayRef<llvm::Value*> Roots,
    unsigned int Depth,
    const llvm::slpvectorizer::BoUpSLP::EdgeInfo&
        EI)

Description

This is the recursive part of buildTree.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2131

Parameters

ArrayRef<llvm::Value*> Roots

unsigned int Depth

const llvm::slpvectorizer::BoUpSLP::EdgeInfo& EI

¶unsigned int canMapToVector(
    llvm::Type* T,
    const llvm::DataLayout& DL) const

Description

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.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:1000

Parameters

llvm::Type* T

const llvm::DataLayout& DL

Returns

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

¶bool canReorderOperands(
    llvm::slpvectorizer::BoUpSLP::TreeEntry*
        UserTE,
    SmallVectorImpl<std::pair<unsigned int,
                              TreeEntry*>>& Edges,
    ArrayRef<
        llvm::slpvectorizer::BoUpSLP::TreeEntry*>
        ReorderableGathers,
    SmallVectorImpl<
        llvm::slpvectorizer::BoUpSLP::TreeEntry*>&
        GatherOps)

Description

Check if the operands on the edges \p Edges of the \p UserTE allows reordering (i.e. the operands can be reordered because they have only one user and reordarable).

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2095

Parameters

llvm::slpvectorizer::BoUpSLP::TreeEntry* UserTE

SmallVectorImpl< std::pair<unsigned int, TreeEntry*>>& Edges

ArrayRef<llvm::slpvectorizer::BoUpSLP::TreeEntry*> ReorderableGathers

List of all gather nodes that require reordering (e.g., gather of extractlements or partially vectorizable loads).

SmallVectorImpl< llvm::slpvectorizer::BoUpSLP::TreeEntry*>& GatherOps

List of gather operand nodes for \p UserTE that require reordering, subset of \p NonVectorized.

¶bool canReuseExtract(
    ArrayRef<llvm::Value*> VL,
    llvm::Value* OpValue,
    SmallVectorImpl<unsigned int>& CurrentOrder)
    const

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2139

Parameters

ArrayRef<llvm::Value*> VL

llvm::Value* OpValue

SmallVectorImpl<unsigned int>& CurrentOrder

Returns

true if the ExtractElement/ExtractValue instructions in \p VL can be vectorized to use the original vector (or aggregate "bitcast" to a vector) and sets \p CurrentOrder to the identity permutation; otherwise returns false, setting \p CurrentOrder to either an empty vector or a non-identity permutation that allows to reuse extract instructions.

¶void clearReductionData()

Description

Clear the list of the analyzed reduction root instructions.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2075

¶DenseMap<llvm::Value*,
         SmallVector<llvm::StoreInst*, 4>>
collectUserStores(
    const BoUpSLP::TreeEntry* TE) const

Description

Helper for `findExternalStoreUsersReorderIndices()`. It iterates over the users of \p TE and collects the stores. It returns the map from the store pointers to the collected stores.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2198

Parameters

const BoUpSLP::TreeEntry* TE

¶void computeMinimumValueSizes()

Description

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

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:972

¶llvm::Value* createBuildVector(
    ArrayRef<llvm::Value*> VL)

Description

Create a new vector from a list of scalar values. Produces a sequence which exploits values reused across lanes, and arranges the inserts for ease of later optimization.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2151

Parameters

ArrayRef<llvm::Value*> VL

¶void deleteTree()

Description

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

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:911

¶void dumpTreeCosts(
    const llvm::slpvectorizer::BoUpSLP::TreeEntry*
        E,
    llvm::InstructionCost ReuseShuffleCost,
    llvm::InstructionCost VecCost,
    llvm::InstructionCost ScalarCost) const

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2497

Parameters

const llvm::slpvectorizer::BoUpSLP::TreeEntry* E

llvm::InstructionCost ReuseShuffleCost

llvm::InstructionCost VecCost

llvm::InstructionCost ScalarCost

¶void dumpVectorizableTree() const

Description

Debug printer.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2591

¶void eraseInstruction(llvm::Instruction* I)

Description

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.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2050

Parameters

llvm::Instruction* I

¶Optional<int> findBestRootPair(
    ArrayRef<std::pair<Value*, Value*>>
        Candidates,
    int Limit = LookAheadHeuristics::ScoreFail)

Description

Evaluate each pair in \p Candidates and return index into \p Candidates for a pair which have highest score deemed to have best chance to form root of profitable tree to vectorize. Return None if no candidate scored above the LookAheadHeuristics::ScoreFail.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2025

Parameters

ArrayRef<std::pair<Value*, Value*>> Candidates

int Limit = LookAheadHeuristics::ScoreFail

Lower limit of the cost, considered to be good enough score.

¶SmallVector<
    llvm::slpvectorizer::BoUpSLP::OrdersType,
    1>
findExternalStoreUsersReorderIndices(
    llvm::slpvectorizer::BoUpSLP::TreeEntry* TE)
    const

Description

Iterates through the users of \p TE, looking for scalar stores that can be potentially vectorized in a future SLP-tree. If found, it keeps track of their order and builds an order index vector for each store bundle. It returns all these order vectors found. We run this after the tree has formed, otherwise we may come across user instructions that are not yet in the tree.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2214

Parameters

llvm::slpvectorizer::BoUpSLP::TreeEntry* TE

¶Optional<llvm::slpvectorizer::BoUpSLP::OrdersType>
findPartiallyOrderedLoads(
    const llvm::slpvectorizer::BoUpSLP::TreeEntry&
        TE)

Description

Sort loads into increasing pointers offsets to allow greater clustering.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:937

Parameters

const llvm::slpvectorizer::BoUpSLP::TreeEntry& TE

¶Optional<llvm::slpvectorizer::BoUpSLP::OrdersType>
findReusedOrderedScalars(
    const llvm::slpvectorizer::BoUpSLP::TreeEntry&
        TE)

Description

Checks if the specified gather tree entry \p 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.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:934

Parameters

const llvm::slpvectorizer::BoUpSLP::TreeEntry& TE

¶llvm::Value* gather(ArrayRef<llvm::Value*> VL)

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2179

Parameters

ArrayRef<llvm::Value*> VL

Returns

a vector from a collection of scalars in \p VL.

¶llvm::InstructionCost getEntryCost(
    const llvm::slpvectorizer::BoUpSLP::TreeEntry*
        E,
    ArrayRef<llvm::Value*> VectorizedVals)

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2127

Parameters

const llvm::slpvectorizer::BoUpSLP::TreeEntry* E

ArrayRef<llvm::Value*> VectorizedVals

Returns

the cost of the vectorizable entry.

¶llvm::InstructionCost getGatherCost(
    ArrayRef<llvm::Value*> VL) const

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2172

Parameters

ArrayRef<llvm::Value*> VL

Returns

the scalarization cost for this list of values. Assuming that this subtree gets vectorized, we may need to extract the values from the roots. This method calculates the cost of extracting the values.

¶llvm::InstructionCost getGatherCost(
    llvm::FixedVectorType* Ty,
    const llvm::APInt& ShuffledIndices,
    bool NeedToShuffle) const

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2157

Parameters

llvm::FixedVectorType* Ty

const llvm::APInt& ShuffledIndices

bool NeedToShuffle

Returns

the scalarization cost for this type. Scalarization in this context means the creation of vectors from a group of scalars. If \p NeedToShuffle is true, need to add a cost of reshuffling some of the vector elements.

¶unsigned int getMaxVecRegSize() const

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:975

¶unsigned int getMaximumVF(
    unsigned int ElemWidth,
    unsigned int Opcode) const

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:988

Parameters

unsigned int ElemWidth

unsigned int Opcode

¶unsigned int getMinVF(unsigned int Sz) const

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:984

Parameters

unsigned int Sz

¶unsigned int getMinVecRegSize() const

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:980

¶llvm::OptimizationRemarkEmitter* getORE()

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:1024

¶Optional<llvm::slpvectorizer::BoUpSLP::OrdersType>
getReorderingData(
    const llvm::slpvectorizer::BoUpSLP::TreeEntry&
        TE,
    bool TopToBottom)

Description

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.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:944

Parameters

const llvm::slpvectorizer::BoUpSLP::TreeEntry& TE

bool TopToBottom

If true, include the order of vectorized stores and insertelement nodes, otherwise skip them.

¶llvm::InstructionCost getSpillCost() const

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:889

Returns

the cost incurred by unwanted spills and fills, caused by holding live values over call sites.

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

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:893

Parameters

ArrayRef<llvm::Value*> VectorizedVals = None

Returns

the vectorization cost of the subtree that starts at \p VL. A negative number means that this is profitable.

¶const llvm::slpvectorizer::BoUpSLP::TreeEntry*
getTreeEntry(llvm::Value* V) const

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2601

Parameters

llvm::Value* V

¶llvm::slpvectorizer::BoUpSLP::TreeEntry*
getTreeEntry(llvm::Value* V)

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2599

Parameters

llvm::Value* V

¶unsigned int getTreeSize() const

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:925

¶unsigned int getVectorElementSize(llvm::Value* V)

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:968

Parameters

llvm::Value* V

Returns

The vector element size in bits to use when vectorizing the expression tree ending at \p 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.

¶llvm::slpvectorizer::BoUpSLP::TreeEntry*
getVectorizedOperand(
    llvm::slpvectorizer::BoUpSLP::TreeEntry*
        UserTE,
    unsigned int OpIdx)

Description

Returns vectorized operand \p OpIdx of the node \p UserTE from the graph, if any. If it is not vectorized (gather node), returns nullptr.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2102

Parameters

llvm::slpvectorizer::BoUpSLP::TreeEntry* UserTE

unsigned int OpIdx

¶const llvm::slpvectorizer::BoUpSLP::TreeEntry*
getVectorizedOperand(
    const llvm::slpvectorizer::BoUpSLP::TreeEntry*
        UserTE,
    unsigned int OpIdx) const

Description

Returns vectorized operand \p OpIdx of the node \p UserTE from the graph, if any. If it is not vectorized (gather node), returns nullptr.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2116

Parameters

const llvm::slpvectorizer::BoUpSLP::TreeEntry* UserTE

unsigned int OpIdx

¶bool isAliased(const llvm::MemoryLocation& Loc1,
               llvm::Instruction* Inst1,
               llvm::Instruction* Inst2)

Description

Checks if two instructions may access the same memory. \p Loc1 is the location of \p Inst1. It is passed explicitly because it is invariant in the calling loop.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2634

Parameters

const llvm::MemoryLocation& Loc1

llvm::Instruction* Inst1

llvm::Instruction* Inst2

¶bool isAnalyzedReductionRoot(
    llvm::Instruction* I) const

Description

Checks if the instruction was already analyzed for being possible reduction root.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2056

Parameters

llvm::Instruction* I

¶bool isAnyGathered(
    const SmallDenseSet<llvm::Value*>& Vals) const

Description

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

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2080

Parameters

const SmallDenseSet<llvm::Value*>& Vals

¶bool isDeleted(llvm::Instruction* I) const

Description

Checks if the instruction is marked for deletion.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2045

Parameters

llvm::Instruction* I

¶bool isFullyVectorizableTinyTree(
    bool ForReduction) const

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2183

Parameters

bool ForReduction

Returns

whether the VectorizableTree is fully vectorizable and will be beneficial even the tree height is tiny.

¶Optional<TargetTransformInfo::ShuffleKind>
isGatherShuffledEntry(
    const llvm::slpvectorizer::BoUpSLP::TreeEntry*
        TE,
    SmallVectorImpl<int>& Mask,
    SmallVectorImpl<const llvm::slpvectorizer::
                        BoUpSLP::TreeEntry*>&
        Entries)

Description

Checks if the gathered \p VL can be represented as shuffle(s) of previous tree entries.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2166

Parameters

const llvm::slpvectorizer::BoUpSLP::TreeEntry* TE

SmallVectorImpl<int>& Mask

SmallVectorImpl<const llvm::slpvectorizer:: BoUpSLP::TreeEntry*>& Entries

Returns

ShuffleKind, if gathered values can be represented as shuffles of previous tree entries. \p Mask is filled with the shuffle mask.

¶bool isLoadCombineCandidate() const

Description

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.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:1022

¶bool isLoadCombineReductionCandidate(
    llvm::RecurKind RdxKind) const

Description

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.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:1013

Parameters

llvm::RecurKind RdxKind

¶bool isTreeTinyAndNotFullyVectorizable(
    bool ForReduction = false) const

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:1004

Parameters

bool ForReduction = false

Returns

True if the VectorizableTree is both tiny and not fully vectorizable. We do not vectorize such trees.

¶llvm::slpvectorizer::BoUpSLP::TreeEntry*
newTreeEntry(
    ArrayRef<llvm::Value*> VL,
    TreeEntry::EntryState EntryState,
    Optional<llvm::slpvectorizer::BoUpSLP::
                 ScheduleData*> Bundle,
    const(anonymous namespace)::InstructionsState&
        S,
    const llvm::slpvectorizer::BoUpSLP::EdgeInfo&
        UserTreeIdx,
    ArrayRef<int> ReuseShuffleIndices = None,
    ArrayRef<unsigned int> ReorderIndices = None)

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2522

Parameters

ArrayRef<llvm::Value*> VL

TreeEntry::EntryState EntryState

Optional< llvm::slpvectorizer::BoUpSLP::ScheduleData*> Bundle

const(anonymous namespace)::InstructionsState& S

const llvm::slpvectorizer::BoUpSLP::EdgeInfo& UserTreeIdx

ArrayRef<int> ReuseShuffleIndices = None

ArrayRef<unsigned int> ReorderIndices = None

¶llvm::slpvectorizer::BoUpSLP::TreeEntry*
newTreeEntry(
    ArrayRef<llvm::Value*> VL,
    Optional<llvm::slpvectorizer::BoUpSLP::
                 ScheduleData*> Bundle,
    const(anonymous namespace)::InstructionsState&
        S,
    const llvm::slpvectorizer::BoUpSLP::EdgeInfo&
        UserTreeIdx,
    ArrayRef<int> ReuseShuffleIndices = None,
    ArrayRef<unsigned int> ReorderIndices = None)

Description

Create a new VectorizableTree entry.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2511

Parameters

ArrayRef<llvm::Value*> VL

Optional< llvm::slpvectorizer::BoUpSLP::ScheduleData*> Bundle

const(anonymous namespace)::InstructionsState& S

const llvm::slpvectorizer::BoUpSLP::EdgeInfo& UserTreeIdx

ArrayRef<int> ReuseShuffleIndices = None

ArrayRef<unsigned int> ReorderIndices = None

¶void optimizeGatherSequence()

Description

Perform LICM and CSE on the newly generated gather sequences.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:928

¶void reorderBottomToTop(
    bool IgnoreReorder = false)

Description

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.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:961

Parameters

bool IgnoreReorder = false

¶static void reorderInputsAccordingToOpcode(
    ArrayRef<llvm::Value*> VL,
    SmallVectorImpl<llvm::Value*>& Left,
    SmallVectorImpl<llvm::Value*>& Right,
    const llvm::DataLayout& DL,
    llvm::ScalarEvolution& SE,
    const llvm::slpvectorizer::BoUpSLP& R)

Description

Reorder commutative or alt operands to get better probability of generating vectorized code.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2187

Parameters

ArrayRef<llvm::Value*> VL

SmallVectorImpl<llvm::Value*>& Left

SmallVectorImpl<llvm::Value*>& Right

const llvm::DataLayout& DL

llvm::ScalarEvolution& SE

const llvm::slpvectorizer::BoUpSLP& R

¶void reorderTopToBottom()

Description

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.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:952

¶void scheduleBlock(
    llvm::slpvectorizer::BoUpSLP::BlockScheduling*
        BS)

Description

Performs the "real" scheduling. Done before vectorization is actually performed in a basic block.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:3196

Parameters

llvm::slpvectorizer::BoUpSLP::BlockScheduling* BS

¶void setInsertPointAfterBundle(
    const llvm::slpvectorizer::BoUpSLP::TreeEntry*
        E)

Description

Set the Builder insert point to one after the last instruction in the bundle

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2176

Parameters

const llvm::slpvectorizer::BoUpSLP::TreeEntry* E

¶llvm::Value* vectorizeTree(
    ArrayRef<llvm::Value*> VL)

Description

Vectorize a single entry in the tree, starting in \p VL.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2146

Parameters

ArrayRef<llvm::Value*> VL

¶llvm::Value* vectorizeTree(
    llvm::slpvectorizer::BoUpSLP::TreeEntry* E)

Description

Vectorize a single entry in the tree.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2143

Parameters

llvm::slpvectorizer::BoUpSLP::TreeEntry* E

¶llvm::Value* vectorizeTree(
    llvm::slpvectorizer::BoUpSLP::
        ExtraValueToDebugLocsMap&
            ExternallyUsedValues)

Description

Vectorize the tree but with the list of externally used values \p ExternallyUsedValues. Values in this MapVector can be replaced but the generated extractvalue instructions.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:885

Parameters

llvm::slpvectorizer::BoUpSLP:: ExtraValueToDebugLocsMap& ExternallyUsedValues

¶llvm::Value* vectorizeTree()

Description

Vectorize the tree that starts with the elements in \p VL. Returns the vectorized root.

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:880

¶~BoUpSLP()

Declared at: llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:2084