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 32 namespace 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. 36 namespace slpvectorizer { 37 class BoUpSLP; 38 } 39 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; 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 56 public: 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 64 private: 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