LLVM 20.0.0git
SLPVectorizer.h
Go to the documentation of this file.
1//===- SLPVectorizer.h ------------------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8// This pass implements the Bottom Up SLP vectorizer. It detects consecutive
9// stores that can be put together into vector-stores. Next, it attempts to
10// construct vectorizable tree using the use-def chains. If a profitable tree
11// was found, the SLP vectorizer performs vectorization on the tree.
12//
13// The pass is inspired by the work described in the paper:
14// "Loop-Aware SLP in GCC" by Ira Rosen, Dorit Nuzman, Ayal Zaks.
15//
16//===----------------------------------------------------------------------===//
17
18#ifndef LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
19#define LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
20
21#include "llvm/ADT/ArrayRef.h"
22#include "llvm/ADT/MapVector.h"
23#include "llvm/ADT/SetVector.h"
25#include "llvm/IR/PassManager.h"
26
27namespace llvm {
28
29class AAResults;
30class AssumptionCache;
31class BasicBlock;
32class DataLayout;
33class DemandedBits;
34class DominatorTree;
35class Function;
36class GetElementPtrInst;
37class InsertElementInst;
38class InsertValueInst;
39class Instruction;
40class LoopInfo;
41class OptimizationRemarkEmitter;
42class PHINode;
43class ScalarEvolution;
44class StoreInst;
45class TargetLibraryInfo;
46class TargetTransformInfo;
47class Value;
48class WeakTrackingVH;
49
50/// A private "module" namespace for types and utilities used by this pass.
51/// These are implementation details and should not be used by clients.
52namespace slpvectorizer {
53
54class BoUpSLP;
55
56} // end namespace slpvectorizer
57
58struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> {
64
65 ScalarEvolution *SE = nullptr;
68 AAResults *AA = nullptr;
69 LoopInfo *LI = nullptr;
70 DominatorTree *DT = nullptr;
71 AssumptionCache *AC = nullptr;
72 DemandedBits *DB = nullptr;
73 const DataLayout *DL = nullptr;
74
75public:
77
78 // Glue for old PM.
80 TargetLibraryInfo *TLI_, AAResults *AA_, LoopInfo *LI_,
83
84private:
85 /// Collect store and getelementptr instructions and organize them
86 /// according to the underlying object of their pointer operands. We sort the
87 /// instructions by their underlying objects to reduce the cost of
88 /// consecutive access queries.
89 ///
90 /// TODO: We can further reduce this cost if we flush the chain creation
91 /// every time we run into a memory barrier.
92 void collectSeedInstructions(BasicBlock *BB);
93
94 /// Try to vectorize a list of operands.
95 /// \param MaxVFOnly Vectorize only using maximal allowed register size.
96 /// \returns true if a value was vectorized.
97 bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
98 bool MaxVFOnly = false);
99
100 /// Try to vectorize a chain that may start at the operands of \p I.
101 bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R);
102
103 /// Try to vectorize chains that may start at the operands of
104 /// instructions in \p Insts.
105 bool tryToVectorize(ArrayRef<WeakTrackingVH> Insts,
107
108 /// Vectorize the store instructions collected in Stores.
109 bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R);
110
111 /// Vectorize the index computations of the getelementptr instructions
112 /// collected in GEPs.
113 bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
114
115 /// Try to find horizontal reduction or otherwise, collect instructions
116 /// for postponed vectorization attempts.
117 /// \a P if not null designates phi node the reduction is fed into
118 /// (with reduction operators \a Root or one of its operands, in a basic block
119 /// \a BB).
120 /// \returns true if a horizontal reduction was matched and reduced.
121 /// \returns false if \a V is null or not an instruction,
122 /// or a horizontal reduction was not matched or not possible.
123 bool vectorizeHorReduction(PHINode *P, Instruction *Root, BasicBlock *BB,
126 SmallVectorImpl<WeakTrackingVH> &PostponedInsts);
127
128 /// Make an attempt to vectorize reduction and then try to vectorize
129 /// postponed binary operations.
130 /// \returns true on any successfull vectorization.
131 bool vectorizeRootInstruction(PHINode *P, Instruction *Root, BasicBlock *BB,
134
135 /// Try to vectorize trees that start at insertvalue instructions.
136 bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB,
137 slpvectorizer::BoUpSLP &R, bool MaxVFOnly);
138
139 /// Try to vectorize trees that start at insertelement instructions.
140 bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB,
141 slpvectorizer::BoUpSLP &R, bool MaxVFOnly);
142
143 /// Tries to vectorize \p CmpInts. \Returns true on success.
144 template <typename ItT>
145 bool vectorizeCmpInsts(iterator_range<ItT> CmpInsts, BasicBlock *BB,
147
148 /// Tries to vectorize constructs started from InsertValueInst or
149 /// InsertElementInst instructions.
150 bool vectorizeInserts(InstSetVector &Instructions, BasicBlock *BB,
152
153 /// Scan the basic block and look for patterns that are likely to start
154 /// a vectorization chain.
155 bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
156
157 std::optional<bool> vectorizeStoreChain(ArrayRef<Value *> Chain,
159 unsigned Idx, unsigned MinVF,
160 unsigned &Size);
161
162 bool vectorizeStores(
164 DenseSet<std::tuple<Value *, Value *, Value *, Value *, unsigned>>
165 &Visited);
166
167 /// The store instructions in a basic block organized by base pointer.
168 StoreListMap Stores;
169
170 /// The getelementptr instructions in a basic block organized by base pointer.
171 GEPListMap GEPs;
172};
173
174} // end namespace llvm
175
176#endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
uint64_t Size
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file implements a map that provides insertion order iteration.
#define P(N)
This header defines various interfaces for pass management in LLVM.
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:63
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
This instruction inserts a single (scalar) element into a VectorType value.
This instruction inserts a struct field of array element value into an aggregate value.
The optimization diagnostic interface.
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
The main scalar evolution driver.
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:587
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
Provides information about what library functions are available for the current target.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
A range adaptor for a pair of iterators.
Bottom Up SLP Vectorizer.
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:69
ScalarEvolution * SE
Definition: SLPVectorizer.h:65
AssumptionCache * AC
Definition: SLPVectorizer.h:71
DominatorTree * DT
Definition: SLPVectorizer.h:70
TargetLibraryInfo * TLI
Definition: SLPVectorizer.h:67
const DataLayout * DL
Definition: SLPVectorizer.h:73
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
bool runImpl(Function &F, ScalarEvolution *SE_, TargetTransformInfo *TTI_, TargetLibraryInfo *TLI_, AAResults *AA_, LoopInfo *LI_, DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_, OptimizationRemarkEmitter *ORE_)