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" |
24 | #include "llvm/ADT/SmallVector.h" |
25 | #include "llvm/IR/PassManager.h" |
26 | |
27 | namespace llvm { |
28 | |
29 | class AAResults; |
30 | class AssumptionCache; |
31 | class BasicBlock; |
32 | class DemandedBits; |
33 | class DominatorTree; |
34 | class Function; |
35 | class GetElementPtrInst; |
36 | class InsertElementInst; |
37 | class InsertValueInst; |
38 | class Instruction; |
39 | class LoopInfo; |
40 | class ; |
41 | class PHINode; |
42 | class ScalarEvolution; |
43 | class StoreInst; |
44 | class TargetLibraryInfo; |
45 | class TargetTransformInfo; |
46 | class Value; |
47 | class WeakTrackingVH; |
48 | |
49 | /// A private "module" namespace for types and utilities used by this pass. |
50 | /// These are implementation details and should not be used by clients. |
51 | namespace slpvectorizer { |
52 | |
53 | class BoUpSLP; |
54 | |
55 | } // end namespace slpvectorizer |
56 | |
57 | struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> { |
58 | using StoreList = SmallVector<StoreInst *, 8>; |
59 | using StoreListMap = MapVector<Value *, StoreList>; |
60 | using GEPList = SmallVector<GetElementPtrInst *, 8>; |
61 | using GEPListMap = MapVector<Value *, GEPList>; |
62 | using InstSetVector = SmallSetVector<Instruction *, 8>; |
63 | |
64 | ScalarEvolution *SE = nullptr; |
65 | TargetTransformInfo *TTI = nullptr; |
66 | TargetLibraryInfo *TLI = nullptr; |
67 | AAResults *AA = nullptr; |
68 | LoopInfo *LI = nullptr; |
69 | DominatorTree *DT = nullptr; |
70 | AssumptionCache *AC = nullptr; |
71 | DemandedBits *DB = nullptr; |
72 | const DataLayout *DL = nullptr; |
73 | |
74 | public: |
75 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
76 | |
77 | // Glue for old PM. |
78 | bool runImpl(Function &F, ScalarEvolution *SE_, TargetTransformInfo *TTI_, |
79 | TargetLibraryInfo *TLI_, AAResults *AA_, LoopInfo *LI_, |
80 | DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_, |
81 | OptimizationRemarkEmitter *ORE_); |
82 | |
83 | private: |
84 | /// Collect store and getelementptr instructions and organize them |
85 | /// according to the underlying object of their pointer operands. We sort the |
86 | /// instructions by their underlying objects to reduce the cost of |
87 | /// consecutive access queries. |
88 | /// |
89 | /// TODO: We can further reduce this cost if we flush the chain creation |
90 | /// every time we run into a memory barrier. |
91 | void collectSeedInstructions(BasicBlock *BB); |
92 | |
93 | /// Try to vectorize a list of operands. |
94 | /// \param MaxVFOnly Vectorize only using maximal allowed register size. |
95 | /// \returns true if a value was vectorized. |
96 | bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R, |
97 | bool MaxVFOnly = false); |
98 | |
99 | /// Try to vectorize a chain that may start at the operands of \p I. |
100 | bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R); |
101 | |
102 | /// Try to vectorize chains that may start at the operands of |
103 | /// instructions in \p Insts. |
104 | bool tryToVectorize(ArrayRef<WeakTrackingVH> Insts, |
105 | slpvectorizer::BoUpSLP &R); |
106 | |
107 | /// Vectorize the store instructions collected in Stores. |
108 | bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R); |
109 | |
110 | /// Vectorize the index computations of the getelementptr instructions |
111 | /// collected in GEPs. |
112 | bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R); |
113 | |
114 | /// Try to find horizontal reduction or otherwise, collect instructions |
115 | /// for postponed vectorization attempts. |
116 | /// \a P if not null designates phi node the reduction is fed into |
117 | /// (with reduction operators \a Root or one of its operands, in a basic block |
118 | /// \a BB). |
119 | /// \returns true if a horizontal reduction was matched and reduced. |
120 | /// \returns false if \a V is null or not an instruction, |
121 | /// or a horizontal reduction was not matched or not possible. |
122 | bool vectorizeHorReduction(PHINode *P, Instruction *Root, BasicBlock *BB, |
123 | slpvectorizer::BoUpSLP &R, |
124 | TargetTransformInfo *TTI, |
125 | SmallVectorImpl<WeakTrackingVH> &PostponedInsts); |
126 | |
127 | /// Make an attempt to vectorize reduction and then try to vectorize |
128 | /// postponed binary operations. |
129 | /// \returns true on any successfull vectorization. |
130 | bool vectorizeRootInstruction(PHINode *P, Instruction *Root, BasicBlock *BB, |
131 | slpvectorizer::BoUpSLP &R, |
132 | TargetTransformInfo *TTI); |
133 | |
134 | /// Try to vectorize trees that start at insertvalue instructions. |
135 | bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB, |
136 | slpvectorizer::BoUpSLP &R); |
137 | |
138 | /// Try to vectorize trees that start at insertelement instructions. |
139 | bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB, |
140 | slpvectorizer::BoUpSLP &R); |
141 | |
142 | /// Tries to vectorize \p CmpInts. \Returns true on success. |
143 | template <typename ItT> |
144 | bool vectorizeCmpInsts(iterator_range<ItT> CmpInsts, BasicBlock *BB, |
145 | slpvectorizer::BoUpSLP &R); |
146 | |
147 | /// Tries to vectorize constructs started from InsertValueInst or |
148 | /// InsertElementInst instructions. |
149 | bool vectorizeInserts(InstSetVector &Instructions, BasicBlock *BB, |
150 | slpvectorizer::BoUpSLP &R); |
151 | |
152 | /// Scan the basic block and look for patterns that are likely to start |
153 | /// a vectorization chain. |
154 | bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R); |
155 | |
156 | bool vectorizeStoreChain(ArrayRef<Value *> Chain, slpvectorizer::BoUpSLP &R, |
157 | unsigned Idx, unsigned MinVF); |
158 | |
159 | bool vectorizeStores(ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R); |
160 | |
161 | /// The store instructions in a basic block organized by base pointer. |
162 | StoreListMap Stores; |
163 | |
164 | /// The getelementptr instructions in a basic block organized by base pointer. |
165 | GEPListMap GEPs; |
166 | }; |
167 | |
168 | } // end namespace llvm |
169 | |
170 | #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H |
171 | |