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