1 //===---- SLPVectorizer.h ---------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
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.
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.
17 //===----------------------------------------------------------------------===//
19 #ifndef LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
20 #define LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
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"
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.
36 namespace slpvectorizer {
40 struct 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;
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;
57 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
60 bool runImpl(Function &F, ScalarEvolution *SE_, TargetTransformInfo *TTI_,
61 TargetLibraryInfo *TLI_, AliasAnalysis *AA_, LoopInfo *LI_,
62 DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_);
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.
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);
74 /// \brief Try to vectorize a chain that starts at two arithmetic instrs.
75 bool tryToVectorizePair(Value *A, Value *B, slpvectorizer::BoUpSLP &R);
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);
85 /// \brief Try to vectorize a chain that may start at the operands of \V;
86 bool tryToVectorize(BinaryOperator *V, slpvectorizer::BoUpSLP &R);
88 /// \brief Vectorize the store instructions collected in Stores.
89 bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R);
91 /// \brief Vectorize the index computations of the getelementptr instructions
92 /// collected in GEPs.
93 bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
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);
99 bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold,
100 slpvectorizer::BoUpSLP &R, unsigned VecRegSize);
102 bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold,
103 slpvectorizer::BoUpSLP &R);
105 /// The store instructions in a basic block organized by base pointer.
108 /// The getelementptr instructions in a basic block organized by base pointer.
113 #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H