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