LLVM  16.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/SetVector.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/IR/PassManager.h"
26 
27 namespace llvm {
28 
29 class AAResults;
30 class AssumptionCache;
31 class BasicBlock;
32 class CmpInst;
33 class DemandedBits;
34 class DominatorTree;
35 class Function;
36 class GetElementPtrInst;
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 class WeakTrackingVH;
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.
52 namespace slpvectorizer {
53 
54 class BoUpSLP;
55 
56 } // end namespace slpvectorizer
57 
58 struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> {
64 
65  ScalarEvolution *SE = nullptr;
67  TargetLibraryInfo *TLI = nullptr;
68  AAResults *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:
77 
78  // Glue for old PM.
80  TargetLibraryInfo *TLI_, AAResults *AA_, LoopInfo *LI_,
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 LimitForRegisterSize Vectorize only using maximal allowed register
99  /// size.
100  /// \returns true if a value was vectorized.
101  bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
102  bool LimitForRegisterSize = 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  /// Try to vectorize chains that may start at the operands of
108  /// instructions in \p Insts.
109  bool tryToVectorize(ArrayRef<WeakTrackingVH> Insts,
111 
112  /// Vectorize the store instructions collected in Stores.
113  bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R);
114 
115  /// Vectorize the index computations of the getelementptr instructions
116  /// collected in GEPs.
117  bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
118 
119  /// Try to find horizontal reduction or otherwise, collect instructions
120  /// for postponed vectorization attempts.
121  /// \a P if not null designates phi node the reduction is fed into
122  /// (with reduction operators \a V or one of its operands, in a basic block
123  /// \a BB).
124  /// \returns true if a horizontal reduction was matched and reduced.
125  /// \returns false if \a V is null or not an instruction,
126  /// or a horizontal reduction was not matched or not possible.
127  bool vectorizeHorReduction(PHINode *P, Value *V, BasicBlock *BB,
130  SmallVectorImpl<WeakTrackingVH> &PostponedInsts);
131 
132  /// Make an attempt to vectorize reduction and then try to vectorize
133  /// postponed binary operations.
134  /// \returns true on any successfull vectorization.
135  bool vectorizeRootInstruction(PHINode *P, Value *V, BasicBlock *BB,
138 
139  /// Try to vectorize trees that start at insertvalue instructions.
140  bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB,
142 
143  /// Try to vectorize trees that start at insertelement instructions.
144  bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB,
146 
147  /// Tries to vectorize constructs started from CmpInst, InsertValueInst or
148  /// InsertElementInst instructions.
149  bool vectorizeSimpleInstructions(InstSetVector &Instructions, BasicBlock *BB,
151  bool AtTerminator);
152 
153  /// Scan the basic block and look for patterns that are likely to start
154  /// a vectorization chain.
155  bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
156 
157  bool vectorizeStoreChain(ArrayRef<Value *> Chain, slpvectorizer::BoUpSLP &R,
158  unsigned Idx, unsigned MinVF);
159 
160  bool vectorizeStores(ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R);
161 
162  /// The store instructions in a basic block organized by base pointer.
163  StoreListMap Stores;
164 
165  /// The getelementptr instructions in a basic block organized by base pointer.
166  GEPListMap GEPs;
167 };
168 
169 } // end namespace llvm
170 
171 #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::SLPVectorizerPass::AC
AssumptionCache * AC
Definition: SLPVectorizer.h:71
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1181
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:172
MapVector.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
Instructions
Code Generation Notes for reduce the size of the ISel and reduce repetition in the implementation In a small number of this can cause even when no optimisation has taken place Instructions
Definition: MSA.txt:11
llvm::MapVector< Value *, StoreList >
llvm::SLPVectorizerPass
Definition: SLPVectorizer.h:58
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::SLPVectorizerPass::runImpl
bool runImpl(Function &F, ScalarEvolution *SE_, TargetTransformInfo *TTI_, TargetLibraryInfo *TLI_, AAResults *AA_, LoopInfo *LI_, DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_, OptimizationRemarkEmitter *ORE_)
Definition: SLPVectorizer.cpp:10195
llvm::AAResults
Definition: AliasAnalysis.h:518
llvm::SLPVectorizerPass::DL
const DataLayout * DL
Definition: SLPVectorizer.h:73
llvm::InsertElementInst
This instruction inserts a single (scalar) element into a VectorType value.
Definition: Instructions.h:1936
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:42
llvm::DemandedBits
Definition: DemandedBits.h:40
I
#define I(x, y, z)
Definition: MD5.cpp:58
ArrayRef.h
llvm::SLPVectorizerPass::LI
LoopInfo * LI
Definition: SLPVectorizer.h:69
llvm::SLPVectorizerPass::TLI
TargetLibraryInfo * TLI
Definition: SLPVectorizer.h:67
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LoopInfo
Definition: LoopInfo.h:1105
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::SLPVectorizerPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: SLPVectorizer.cpp:10175
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::SLPVectorizerPass::DB
DemandedBits * DB
Definition: SLPVectorizer.h:72
llvm::slpvectorizer::BoUpSLP
Bottom Up SLP Vectorizer.
Definition: SLPVectorizer.cpp:858
llvm::SLPVectorizerPass::SE
ScalarEvolution * SE
Definition: SLPVectorizer.h:65
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
PassManager.h
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:225
AA
SmallVector.h
llvm::PHINode
Definition: Instructions.h:2699
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::InsertValueInst
This instruction inserts a struct field of array element value into an aggregate value.
Definition: Instructions.h:2557
llvm::SLPVectorizerPass::DT
DominatorTree * DT
Definition: SLPVectorizer.h:70
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::codeview::PublicSymFlags::Function
@ Function
SetVector.h