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/ArrayRef.h" 23 #include "llvm/ADT/MapVector.h" 24 #include "llvm/ADT/None.h" 25 #include "llvm/ADT/SmallVector.h" 26 #include "llvm/Analysis/AliasAnalysis.h" 27 #include "llvm/IR/PassManager.h" 28 #include "llvm/IR/ValueHandle.h" 29 30 namespace llvm { 31 32 class AssumptionCache; 33 class BasicBlock; 34 class CmpInst; 35 class DataLayout; 36 class DemandedBits; 37 class DominatorTree; 38 class Function; 39 class InsertElementInst; 40 class InsertValueInst; 41 class Instruction; 42 class LoopInfo; 43 class OptimizationRemarkEmitter; 44 class PHINode; 45 class ScalarEvolution; 46 class StoreInst; 47 class TargetLibraryInfo; 48 class TargetTransformInfo; 49 class Value; 50 51 /// A private "module" namespace for types and utilities used by this pass. 52 /// These are implementation details and should not be used by clients. 53 namespace slpvectorizer { 54 55 class BoUpSLP; 56 57 } // end namespace slpvectorizer 58 59 struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> { 60 using StoreList = SmallVector<StoreInst *, 8>; 61 using StoreListMap = MapVector<Value *, StoreList>; 62 using WeakTrackingVHList = SmallVector<WeakTrackingVH, 8>; 63 using WeakTrackingVHListMap = MapVector<Value *, WeakTrackingVHList>; 64 65 ScalarEvolution *SE = nullptr; 66 TargetTransformInfo *TTI = nullptr; 67 TargetLibraryInfo *TLI = nullptr; 68 AliasAnalysis *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: 76 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 77 78 // Glue for old PM. 79 bool runImpl(Function &F, ScalarEvolution *SE_, TargetTransformInfo *TTI_, 80 TargetLibraryInfo *TLI_, AliasAnalysis *AA_, LoopInfo *LI_, 81 DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_, 82 OptimizationRemarkEmitter *ORE_); 83 84 private: 85 /// \brief 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 /// \brief Try to vectorize a chain that starts at two arithmetic instrs. 95 bool tryToVectorizePair(Value *A, Value *B, slpvectorizer::BoUpSLP &R); 96 97 /// \brief Try to vectorize a list of operands. 98 /// \@param BuildVector A list of users to ignore for the purpose of 99 /// scheduling and that don't need extracting. 100 /// \returns true if a value was vectorized. 101 bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R, 102 ArrayRef<Value *> BuildVector = None, 103 bool AllowReorder = false); 104 105 /// \brief Try to vectorize a chain that may start at the operands of \p I. 106 bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R); 107 108 /// \brief Vectorize the store instructions collected in Stores. 109 bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R); 110 111 /// \brief Vectorize the index computations of the getelementptr instructions 112 /// collected in GEPs. 113 bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R); 114 115 /// Try to find horizontal reduction or otherwise vectorize a chain of binary 116 /// operators. 117 bool vectorizeRootInstruction(PHINode *P, Value *V, BasicBlock *BB, 118 slpvectorizer::BoUpSLP &R, 119 TargetTransformInfo *TTI); 120 121 /// Try to vectorize trees that start at insertvalue instructions. 122 bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB, 123 slpvectorizer::BoUpSLP &R); 124 125 /// Try to vectorize trees that start at insertelement instructions. 126 bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB, 127 slpvectorizer::BoUpSLP &R); 128 129 /// Try to vectorize trees that start at compare instructions. 130 bool vectorizeCmpInst(CmpInst *CI, BasicBlock *BB, slpvectorizer::BoUpSLP &R); 131 132 /// Tries to vectorize constructs started from CmpInst, InsertValueInst or 133 /// InsertElementInst instructions. 134 bool vectorizeSimpleInstructions(SmallVectorImpl<WeakVH> &Instructions, 135 BasicBlock *BB, slpvectorizer::BoUpSLP &R); 136 137 /// \brief Scan the basic block and look for patterns that are likely to start 138 /// a vectorization chain. 139 bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R); 140 141 bool vectorizeStoreChain(ArrayRef<Value *> Chain, slpvectorizer::BoUpSLP &R, 142 unsigned VecRegSize); 143 144 bool vectorizeStores(ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R); 145 146 /// The store instructions in a basic block organized by base pointer. 147 StoreListMap Stores; 148 149 /// The getelementptr instructions in a basic block organized by base pointer. 150 WeakTrackingVHListMap GEPs; 151 }; 152 153 } // end namespace llvm 154 155 #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H 156
