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/MapVector.h"
23#include "llvm/Analysis/AliasAnalysis.h"
24#include "llvm/Analysis/AssumptionCache.h"
25#include "llvm/Analysis/DemandedBits.h"
26#include "llvm/Analysis/LoopInfo.h"
27#include "llvm/Analysis/ScalarEvolution.h"
28#include "llvm/Analysis/TargetTransformInfo.h"
29#include "llvm/IR/Function.h"
30#include "llvm/IR/PassManager.h"
31
32namespace llvm {
33
34/// A private "module" namespace for types and utilities used by this pass.
35/// These are implementation details and should not be used by clients.
36namespace slpvectorizer {
37class BoUpSLP;
38}
39
40struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> {
41  typedef SmallVector<StoreInst *, 8> StoreList;
42  typedef MapVector<Value *, StoreList> StoreListMap;
43  typedef SmallVector<WeakVH, 8> WeakVHList;
44  typedef MapVector<Value *, WeakVHList> WeakVHListMap;
45
46  ScalarEvolution *SE = nullptr;
47  TargetTransformInfo *TTI = nullptr;
48  TargetLibraryInfo *TLI = nullptr;
49  AliasAnalysis *AA = nullptr;
50  LoopInfo *LI = nullptr;
51  DominatorTree *DT = nullptr;
52  AssumptionCache *AC = nullptr;
53  DemandedBits *DB = nullptr;
54  const DataLayout *DL = nullptr;
55
56public:
57  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
58
59  // Glue for old PM.
60  bool runImpl(Function &F, ScalarEvolution *SE_, TargetTransformInfo *TTI_,
61               TargetLibraryInfo *TLI_, AliasAnalysis *AA_, LoopInfo *LI_,
62               DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_);
63
64private:
65  /// \brief Collect store and getelementptr instructions and organize them
66  /// according to the underlying object of their pointer operands. We sort the
67  /// instructions by their underlying objects to reduce the cost of
68  /// consecutive access queries.
69  ///
70  /// TODO: We can further reduce this cost if we flush the chain creation
71  ///       every time we run into a memory barrier.
72  void collectSeedInstructions(BasicBlock *BB);
73
74  /// \brief Try to vectorize a chain that starts at two arithmetic instrs.
75  bool tryToVectorizePair(Value *A, Value *B, slpvectorizer::BoUpSLP &R);
76
77  /// \brief Try to vectorize a list of operands.
78  /// \@param BuildVector A list of users to ignore for the purpose of
79  ///                     scheduling and that don't need extracting.
80  /// \returns true if a value was vectorized.
81  bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
82                          ArrayRef<Value *> BuildVector = None,
83                          bool allowReorder = false);
84
85  /// \brief Try to vectorize a chain that may start at the operands of \V;
86  bool tryToVectorize(BinaryOperator *V, slpvectorizer::BoUpSLP &R);
87
88  /// \brief Vectorize the store instructions collected in Stores.
89  bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R);
90
91  /// \brief Vectorize the index computations of the getelementptr instructions
92  /// collected in GEPs.
93  bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
94
95  /// \brief Scan the basic block and look for patterns that are likely to start
96  /// a vectorization chain.
97  bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
98
99  bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold,
100                           slpvectorizer::BoUpSLP &R, unsigned VecRegSize);
101
102  bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold,
103                       slpvectorizer::BoUpSLP &R);
104
105  /// The store instructions in a basic block organized by base pointer.
106  StoreListMap Stores;
107
108  /// The getelementptr instructions in a basic block organized by base pointer.
109  WeakVHListMap GEPs;
110};
111}
112
113#endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
114