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
27namespace llvm {
28
29class AAResults;
30class AssumptionCache;
31class BasicBlock;
32class DemandedBits;
33class DominatorTree;
34class Function;
35class GetElementPtrInst;
36class InsertElementInst;
37class InsertValueInst;
38class Instruction;
39class LoopInfo;
40class OptimizationRemarkEmitter;
41class PHINode;
42class ScalarEvolution;
43class StoreInst;
44class TargetLibraryInfo;
45class TargetTransformInfo;
46class Value;
47class WeakTrackingVH;
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.
51namespace slpvectorizer {
52
53class BoUpSLP;
54
55} // end namespace slpvectorizer
56
57struct 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  using InstSetVector = SmallSetVector<Instruction *, 8>;
63
64  ScalarEvolution *SE = nullptr;
65  TargetTransformInfo *TTI = nullptr;
66  TargetLibraryInfo *TLI = nullptr;
67  AAResults *AA = nullptr;
68  LoopInfo *LI = nullptr;
69  DominatorTree *DT = nullptr;
70  AssumptionCache *AC = nullptr;
71  DemandedBits *DB = nullptr;
72  const DataLayout *DL = nullptr;
73
74public:
75  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
76
77  // Glue for old PM.
78  bool runImpl(Function &F, ScalarEvolution *SE_, TargetTransformInfo *TTI_,
79               TargetLibraryInfo *TLI_, AAResults *AA_, LoopInfo *LI_,
80               DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_,
81               OptimizationRemarkEmitter *ORE_);
82
83private:
84  /// Collect store and getelementptr instructions and organize them
85  /// according to the underlying object of their pointer operands. We sort the
86  /// instructions by their underlying objects to reduce the cost of
87  /// consecutive access queries.
88  ///
89  /// TODO: We can further reduce this cost if we flush the chain creation
90  ///       every time we run into a memory barrier.
91  void collectSeedInstructions(BasicBlock *BB);
92
93  /// Try to vectorize a list of operands.
94  /// \param MaxVFOnly Vectorize only using maximal allowed register size.
95  /// \returns true if a value was vectorized.
96  bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
97                          bool MaxVFOnly = false);
98
99  /// Try to vectorize a chain that may start at the operands of \p I.
100  bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R);
101
102  /// Try to vectorize chains that may start at the operands of
103  /// instructions in \p Insts.
104  bool tryToVectorize(ArrayRef<WeakTrackingVH> Insts,
105                      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, collect instructions
115  /// for postponed vectorization attempts.
116  /// \a P if not null designates phi node the reduction is fed into
117  /// (with reduction operators \a Root or one of its operands, in a basic block
118  /// \a BB).
119  /// \returns true if a horizontal reduction was matched and reduced.
120  /// \returns false if \a V is null or not an instruction,
121  /// or a horizontal reduction was not matched or not possible.
122  bool vectorizeHorReduction(PHINode *P, Instruction *Root, BasicBlock *BB,
123                             slpvectorizer::BoUpSLP &R,
124                             TargetTransformInfo *TTI,
125                             SmallVectorImpl<WeakTrackingVH> &PostponedInsts);
126
127  /// Make an attempt to vectorize reduction and then try to vectorize
128  /// postponed binary operations.
129  /// \returns true on any successfull vectorization.
130  bool vectorizeRootInstruction(PHINode *P, Instruction *Root, BasicBlock *BB,
131                                slpvectorizer::BoUpSLP &R,
132                                TargetTransformInfo *TTI);
133
134  /// Try to vectorize trees that start at insertvalue instructions.
135  bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB,
136                                slpvectorizer::BoUpSLP &R);
137
138  /// Try to vectorize trees that start at insertelement instructions.
139  bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB,
140                                  slpvectorizer::BoUpSLP &R);
141
142  /// Tries to vectorize \p CmpInts. \Returns true on success.
143  template <typename ItT>
144  bool vectorizeCmpInsts(iterator_range<ItT> CmpInsts, BasicBlock *BB,
145                         slpvectorizer::BoUpSLP &R);
146
147  /// Tries to vectorize constructs started from InsertValueInst or
148  /// InsertElementInst instructions.
149  bool vectorizeInserts(InstSetVector &Instructions, BasicBlock *BB,
150                        slpvectorizer::BoUpSLP &R);
151
152  /// Scan the basic block and look for patterns that are likely to start
153  /// a vectorization chain.
154  bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
155
156  bool vectorizeStoreChain(ArrayRef<Value *> Chain, slpvectorizer::BoUpSLP &R,
157                           unsigned Idx, unsigned MinVF);
158
159  bool vectorizeStores(ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R);
160
161  /// The store instructions in a basic block organized by base pointer.
162  StoreListMap Stores;
163
164  /// The getelementptr instructions in a basic block organized by base pointer.
165  GEPListMap GEPs;
166};
167
168} // end namespace llvm
169
170#endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
171