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/None.h" 24 #include "llvm/ADT/SmallVector.h" 25 #include "llvm/IR/PassManager.h" 26 27 namespace llvm { 28 29 class AAResults; 30 class AssumptionCache; 31 class BasicBlock; 32 class CmpInst; 33 class DataLayout; 34 class DemandedBits; 35 class DominatorTree; 36 class Function; 37 class GetElementPtrInst; 38 class InsertElementInst; 39 class InsertValueInst; 40 class Instruction; 41 class LoopInfo; 42 class OptimizationRemarkEmitter; 43 class PHINode; 44 class ScalarEvolution; 45 class StoreInst; 46 class TargetLibraryInfo; 47 class TargetTransformInfo; 48 class Value; 49 50 /// A private "module" namespace for types and utilities used by this pass. 51 /// These are implementation details and should not be used by clients. 52 namespace slpvectorizer { 53 54 class BoUpSLP; 55 56 } // end namespace slpvectorizer 57 58 struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> { 59 using StoreList = SmallVector<StoreInst *, 8>; 60 using StoreListMap = MapVector<Value *, StoreList>; 61 using GEPList = SmallVector<GetElementPtrInst *, 8>; 62 using GEPListMap = MapVector<Value *, GEPList>; 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 74 public: 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 83 private: 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 chain that starts at two arithmetic instrs. 94 bool tryToVectorizePair(Value *A, Value *B, slpvectorizer::BoUpSLP &R); 95 96 /// Try to vectorize a list of operands. 97 /// \returns true if a value was vectorized. 98 bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R, 99 bool AllowReorder = false); 100 101 /// Try to vectorize a chain that may start at the operands of \p I. 102 bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R); 103 104 /// Vectorize the store instructions collected in Stores. 105 bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R); 106 107 /// Vectorize the index computations of the getelementptr instructions 108 /// collected in GEPs. 109 bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R); 110 111 /// Try to find horizontal reduction or otherwise vectorize a chain of binary 112 /// operators. 113 bool vectorizeRootInstruction(PHINode *P, Value *V, BasicBlock *BB, 114 slpvectorizer::BoUpSLP &R, 115 TargetTransformInfo *TTI); 116 117 /// Try to vectorize trees that start at insertvalue instructions. 118 bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB, 119 slpvectorizer::BoUpSLP &R); 120 121 /// Try to vectorize trees that start at insertelement instructions. 122 bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB, 123 slpvectorizer::BoUpSLP &R); 124 125 /// Tries to vectorize constructs started from CmpInst, InsertValueInst or 126 /// InsertElementInst instructions. 127 bool vectorizeSimpleInstructions(SmallVectorImpl<Instruction *> &Instructions, 128 BasicBlock *BB, slpvectorizer::BoUpSLP &R, 129 bool AtTerminator); 130 131 /// Scan the basic block and look for patterns that are likely to start 132 /// a vectorization chain. 133 bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R); 134 135 bool vectorizeStoreChain(ArrayRef<Value *> Chain, slpvectorizer::BoUpSLP &R, 136 unsigned Idx); 137 138 bool vectorizeStores(ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R); 139 140 /// The store instructions in a basic block organized by base pointer. 141 StoreListMap Stores; 142 143 /// The getelementptr instructions in a basic block organized by base pointer. 144 GEPListMap GEPs; 145 }; 146 147 } // end namespace llvm 148 149 #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H 150