LLVM  11.0.0git
SLPVectorizer.h
Go to the documentation of this file.
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"
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> {
62 
63  ScalarEvolution *SE = 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:
75 
76  // Glue for old PM.
78  TargetLibraryInfo *TLI_, AliasAnalysis *AA_, LoopInfo *LI_,
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,
120  TargetTransformInfo *TTI);
121 
122  /// Try to vectorize trees that start at insertvalue instructions.
123  bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB,
125 
126  /// Try to vectorize trees that start at insertelement instructions.
127  bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB,
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,
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
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:715
static bool runImpl(Function &F, TargetLibraryInfo &TLI, DominatorTree &DT)
This is the entry point for all transforms.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Various leaf nodes.
Definition: ISDOpcodes.h:64
The main scalar evolution driver.
A cache of @llvm.assume calls within a function.
F(f)
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:373
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
#define P(N)
This instruction inserts a single (scalar) element into a VectorType value.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
Provides information about what library functions are available for the current target.
#define I(x, y, z)
Definition: MD5.cpp:59
LLVM Value Representation.
Definition: Value.h:74
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
Bottom Up SLP Vectorizer.
The optimization diagnostic interface.
This instruction inserts a struct field of array element value into an aggregate value.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL