Line data Source code
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 5852 : 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
|
