xref: /openbsd-src/gnu/llvm/llvm/include/llvm/Transforms/Vectorize/SLPVectorizer.h (revision d415bd752c734aee168c4ee86ff32e8cc249eb16)
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 CmpInst;
33 class DemandedBits;
34 class DominatorTree;
35 class Function;
36 class GetElementPtrInst;
37 class InsertElementInst;
38 class InsertValueInst;
39 class Instruction;
40 class LoopInfo;
41 class OptimizationRemarkEmitter;
42 class PHINode;
43 class ScalarEvolution;
44 class StoreInst;
45 class TargetLibraryInfo;
46 class TargetTransformInfo;
47 class Value;
48 class 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.
52 namespace slpvectorizer {
53 
54 class BoUpSLP;
55 
56 } // end namespace slpvectorizer
57 
58 struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> {
59   using StoreList = SmallVector<StoreInst *, 8>;
60   using StoreListMap = MapVector<Value *, StoreList>;
61   using GEPList = SmallVector<GetElementPtrInst *, 8>;
62   using GEPListMap = MapVector<Value *, GEPList>;
63   using InstSetVector = SmallSetVector<Instruction *, 8>;
64 
65   ScalarEvolution *SE = nullptr;
66   TargetTransformInfo *TTI = nullptr;
67   TargetLibraryInfo *TLI = 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 
75 public:
76   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
77 
78   // Glue for old PM.
79   bool runImpl(Function &F, ScalarEvolution *SE_, TargetTransformInfo *TTI_,
80                TargetLibraryInfo *TLI_, AAResults *AA_, LoopInfo *LI_,
81                DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_,
82                OptimizationRemarkEmitter *ORE_);
83 
84 private:
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 chain that starts at two arithmetic instrs.
95   bool tryToVectorizePair(Value *A, Value *B, slpvectorizer::BoUpSLP &R);
96 
97   /// Try to vectorize a list of operands.
98   /// \param LimitForRegisterSize Vectorize only using maximal allowed register
99   /// size.
100   /// \returns true if a value was vectorized.
101   bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
102                           bool LimitForRegisterSize = false);
103 
104   /// Try to vectorize a chain that may start at the operands of \p I.
105   bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R);
106 
107   /// Try to vectorize chains that may start at the operands of
108   /// instructions in \p Insts.
109   bool tryToVectorize(ArrayRef<WeakTrackingVH> Insts,
110                       slpvectorizer::BoUpSLP &R);
111 
112   /// Vectorize the store instructions collected in Stores.
113   bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R);
114 
115   /// Vectorize the index computations of the getelementptr instructions
116   /// collected in GEPs.
117   bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
118 
119   /// Try to find horizontal reduction or otherwise, collect instructions
120   /// for postponed vectorization attempts.
121   /// \a P if not null designates phi node the reduction is fed into
122   /// (with reduction operators \a V or one of its operands, in a basic block
123   /// \a BB).
124   /// \returns true if a horizontal reduction was matched and reduced.
125   /// \returns false if \a V is null or not an instruction,
126   /// or a horizontal reduction was not matched or not possible.
127   bool vectorizeHorReduction(PHINode *P, Value *V, BasicBlock *BB,
128                              slpvectorizer::BoUpSLP &R,
129                              TargetTransformInfo *TTI,
130                              SmallVectorImpl<WeakTrackingVH> &PostponedInsts);
131 
132   /// Make an attempt to vectorize reduction and then try to vectorize
133   /// postponed binary operations.
134   /// \returns true on any successfull vectorization.
135   bool vectorizeRootInstruction(PHINode *P, Value *V, BasicBlock *BB,
136                                 slpvectorizer::BoUpSLP &R,
137                                 TargetTransformInfo *TTI);
138 
139   /// Try to vectorize trees that start at insertvalue instructions.
140   bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB,
141                                 slpvectorizer::BoUpSLP &R);
142 
143   /// Try to vectorize trees that start at insertelement instructions.
144   bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB,
145                                   slpvectorizer::BoUpSLP &R);
146 
147   /// Tries to vectorize constructs started from CmpInst, InsertValueInst or
148   /// InsertElementInst instructions.
149   bool vectorizeSimpleInstructions(InstSetVector &Instructions, BasicBlock *BB,
150                                    slpvectorizer::BoUpSLP &R,
151                                    bool AtTerminator);
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   bool vectorizeStoreChain(ArrayRef<Value *> Chain, slpvectorizer::BoUpSLP &R,
158                            unsigned Idx, unsigned MinVF);
159 
160   bool vectorizeStores(ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R);
161 
162   /// The store instructions in a basic block organized by base pointer.
163   StoreListMap Stores;
164 
165   /// The getelementptr instructions in a basic block organized by base pointer.
166   GEPListMap GEPs;
167 };
168 
169 } // end namespace llvm
170 
171 #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
172