1 //===- SLPVectorizer.h ------------------------------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 // This pass implements the Bottom Up SLP vectorizer. It detects consecutive
10 // stores that can be put together into vector-stores. Next, it attempts to
11 // construct vectorizable tree using the use-def chains. If a profitable tree
12 // was found, the SLP vectorizer performs vectorization on the tree.
13 //
14 // The pass is inspired by the work described in the paper:
15 //  "Loop-Aware SLP in GCC" by Ira Rosen, Dorit Nuzman, Ayal Zaks.
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #ifndef LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
20 #define LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
21 
22 #include "llvm/ADT/ArrayRef.h"
23 #include "llvm/ADT/MapVector.h"
24 #include "llvm/ADT/None.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/Analysis/AliasAnalysis.h"
27 #include "llvm/IR/PassManager.h"
28 #include "llvm/IR/ValueHandle.h"
29 
30 namespace llvm {
31 
32 class AssumptionCache;
33 class BasicBlock;
34 class CmpInst;
35 class DataLayout;
36 class DemandedBits;
37 class DominatorTree;
38 class Function;
39 class InsertElementInst;
40 class InsertValueInst;
41 class Instruction;
42 class LoopInfo;
43 class OptimizationRemarkEmitter;
44 class PHINode;
45 class ScalarEvolution;
46 class StoreInst;
47 class TargetLibraryInfo;
48 class TargetTransformInfo;
49 class Value;
50 
51 /// A private "module" namespace for types and utilities used by this pass.
52 /// These are implementation details and should not be used by clients.
53 namespace slpvectorizer {
54 
55 class BoUpSLP;
56 
57 } // end namespace slpvectorizer
58 
59 struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> {
60   using StoreList = SmallVector<StoreInst *, 8>;
61   using StoreListMap = MapVector<Value *, StoreList>;
62   using WeakTrackingVHList = SmallVector<WeakTrackingVH, 8>;
63   using WeakTrackingVHListMap = MapVector<Value *, WeakTrackingVHList>;
64 
65   ScalarEvolution *SE = nullptr;
66   TargetTransformInfo *TTI = nullptr;
67   TargetLibraryInfo *TLI = nullptr;
68   AliasAnalysis *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_, AliasAnalysis *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 UserCost Cost of the user operations of \p VL if they may affect
99   /// the cost of the vectorization.
100   /// \returns true if a value was vectorized.
101   bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
102                           int UserCost = 0, bool AllowReorder = 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   /// 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 vectorize a chain of binary
115   /// operators.
116   bool vectorizeRootInstruction(PHINode *P, Value *V, BasicBlock *BB,
117                                 slpvectorizer::BoUpSLP &R,
118                                 TargetTransformInfo *TTI);
119 
120   /// Try to vectorize trees that start at insertvalue instructions.
121   bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB,
122                                 slpvectorizer::BoUpSLP &R);
123 
124   /// Try to vectorize trees that start at insertelement instructions.
125   bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB,
126                                   slpvectorizer::BoUpSLP &R);
127 
128   /// Try to vectorize trees that start at compare instructions.
129   bool vectorizeCmpInst(CmpInst *CI, BasicBlock *BB, slpvectorizer::BoUpSLP &R);
130 
131   /// Tries to vectorize constructs started from CmpInst, InsertValueInst or
132   /// InsertElementInst instructions.
133   bool vectorizeSimpleInstructions(SmallVectorImpl<WeakVH> &Instructions,
134                                    BasicBlock *BB, slpvectorizer::BoUpSLP &R);
135 
136   /// Scan the basic block and look for patterns that are likely to start
137   /// a vectorization chain.
138   bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
139 
140   bool vectorizeStoreChain(ArrayRef<Value *> Chain, slpvectorizer::BoUpSLP &R,
141                            unsigned VecRegSize);
142 
143   bool vectorizeStores(ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R);
144 
145   /// The store instructions in a basic block organized by base pointer.
146   StoreListMap Stores;
147 
148   /// The getelementptr instructions in a basic block organized by base pointer.
149   WeakTrackingVHListMap GEPs;
150 };
151 
152 } // end namespace llvm
153 
154 #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
155