]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - contrib/llvm-project/llvm/include/llvm/Transforms/Vectorize/SLPVectorizer.h
Merge ^/head r364082 through r364250.
[FreeBSD/FreeBSD.git] / contrib / llvm-project / llvm / include / llvm / Transforms / Vectorize / SLPVectorizer.h
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/None.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/Analysis/AliasAnalysis.h"
26 #include "llvm/IR/PassManager.h"
27
28 namespace llvm {
29
30 class AssumptionCache;
31 class BasicBlock;
32 class CmpInst;
33 class DataLayout;
34 class DemandedBits;
35 class DominatorTree;
36 class Function;
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
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
63   ScalarEvolution *SE = nullptr;
64   TargetTransformInfo *TTI = nullptr;
65   TargetLibraryInfo *TLI = nullptr;
66   AliasAnalysis *AA = nullptr;
67   LoopInfo *LI = nullptr;
68   DominatorTree *DT = nullptr;
69   AssumptionCache *AC = nullptr;
70   DemandedBits *DB = nullptr;
71   const DataLayout *DL = nullptr;
72
73 public:
74   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
75
76   // Glue for old PM.
77   bool runImpl(Function &F, ScalarEvolution *SE_, TargetTransformInfo *TTI_,
78                TargetLibraryInfo *TLI_, AliasAnalysis *AA_, LoopInfo *LI_,
79                DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_,
80                OptimizationRemarkEmitter *ORE_);
81
82 private:
83   /// Collect store and getelementptr instructions and organize them
84   /// according to the underlying object of their pointer operands. We sort the
85   /// instructions by their underlying objects to reduce the cost of
86   /// consecutive access queries.
87   ///
88   /// TODO: We can further reduce this cost if we flush the chain creation
89   ///       every time we run into a memory barrier.
90   void collectSeedInstructions(BasicBlock *BB);
91
92   /// Try to vectorize a chain that starts at two arithmetic instrs.
93   bool tryToVectorizePair(Value *A, Value *B, slpvectorizer::BoUpSLP &R);
94
95   /// Try to vectorize a list of operands.
96   /// When \p InsertUses is provided and its entries are non-zero
97   /// then users of \p VL are known to be InsertElement instructions
98   /// each associated with same VL entry index. Their cost is then
99   /// used to adjust cost of the vectorization assuming instcombine pass
100   /// then optimizes ExtractElement-InsertElement sequence.
101   /// \returns true if a value was vectorized.
102   bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
103                           bool AllowReorder = false,
104                           ArrayRef<Value *> InsertUses = None);
105
106   /// Try to vectorize a chain that may start at the operands of \p I.
107   bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R);
108
109   /// Vectorize the store instructions collected in Stores.
110   bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R);
111
112   /// Vectorize the index computations of the getelementptr instructions
113   /// collected in GEPs.
114   bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
115
116   /// Try to find horizontal reduction or otherwise vectorize a chain of binary
117   /// operators.
118   bool vectorizeRootInstruction(PHINode *P, Value *V, BasicBlock *BB,
119                                 slpvectorizer::BoUpSLP &R,
120                                 TargetTransformInfo *TTI);
121
122   /// Try to vectorize trees that start at insertvalue instructions.
123   bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB,
124                                 slpvectorizer::BoUpSLP &R);
125
126   /// Try to vectorize trees that start at insertelement instructions.
127   bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB,
128                                   slpvectorizer::BoUpSLP &R);
129
130   /// Try to vectorize trees that start at compare instructions.
131   bool vectorizeCmpInst(CmpInst *CI, BasicBlock *BB, slpvectorizer::BoUpSLP &R);
132
133   /// Tries to vectorize constructs started from CmpInst, InsertValueInst or
134   /// InsertElementInst instructions.
135   bool vectorizeSimpleInstructions(SmallVectorImpl<Instruction *> &Instructions,
136                                    BasicBlock *BB, slpvectorizer::BoUpSLP &R);
137
138   /// Scan the basic block and look for patterns that are likely to start
139   /// a vectorization chain.
140   bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
141
142   bool vectorizeStoreChain(ArrayRef<Value *> Chain, slpvectorizer::BoUpSLP &R,
143                            unsigned Idx);
144
145   bool vectorizeStores(ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R);
146
147   /// The store instructions in a basic block organized by base pointer.
148   StoreListMap Stores;
149
150   /// The getelementptr instructions in a basic block organized by base pointer.
151   GEPListMap GEPs;
152 };
153
154 } // end namespace llvm
155
156 #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H