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/SetVector.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 DataLayout; 33 class DemandedBits; 34 class DominatorTree; 35 class Function; 36 class GetElementPtrInst; 37 class InsertElementInst; 38 class InsertValueInst; 39 class Instruction; 40 class LoopInfo; 41 class OptimizationRemarkEmitter; 42 class PHINode; 43 class ScalarEvolution; 44 class StoreInst; 45 class TargetLibraryInfo; 46 class TargetTransformInfo; 47 class Value; 48 class WeakTrackingVH; 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 using InstSetVector = SmallSetVector<Instruction *, 8>; 64 65 ScalarEvolution *SE = nullptr; 66 TargetTransformInfo *TTI = nullptr; 67 TargetLibraryInfo *TLI = nullptr; 68 AAResults *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_, AAResults *AA_, LoopInfo *LI_, 81 DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_, 82 OptimizationRemarkEmitter *ORE_); 83 84 private: 85 /// 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 /// Try to vectorize a list of operands. 95 /// \param MaxVFOnly Vectorize only using maximal allowed register size. 96 /// \returns true if a value was vectorized. 97 bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R, 98 bool MaxVFOnly = false); 99 100 /// Try to vectorize a chain that may start at the operands of \p I. 101 bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R); 102 103 /// Try to vectorize chains that may start at the operands of 104 /// instructions in \p Insts. 105 bool tryToVectorize(ArrayRef<WeakTrackingVH> Insts, 106 slpvectorizer::BoUpSLP &R); 107 108 /// Vectorize the store instructions collected in Stores. 109 bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R); 110 111 /// 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, collect instructions 116 /// for postponed vectorization attempts. 117 /// \a P if not null designates phi node the reduction is fed into 118 /// (with reduction operators \a Root or one of its operands, in a basic block 119 /// \a BB). 120 /// \returns true if a horizontal reduction was matched and reduced. 121 /// \returns false if \a V is null or not an instruction, 122 /// or a horizontal reduction was not matched or not possible. 123 bool vectorizeHorReduction(PHINode *P, Instruction *Root, BasicBlock *BB, 124 slpvectorizer::BoUpSLP &R, 125 TargetTransformInfo *TTI, 126 SmallVectorImpl<WeakTrackingVH> &PostponedInsts); 127 128 /// Make an attempt to vectorize reduction and then try to vectorize 129 /// postponed binary operations. 130 /// \returns true on any successfull vectorization. 131 bool vectorizeRootInstruction(PHINode *P, Instruction *Root, BasicBlock *BB, 132 slpvectorizer::BoUpSLP &R, 133 TargetTransformInfo *TTI); 134 135 /// Try to vectorize trees that start at insertvalue instructions. 136 bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB, 137 slpvectorizer::BoUpSLP &R, bool MaxVFOnly); 138 139 /// Try to vectorize trees that start at insertelement instructions. 140 bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB, 141 slpvectorizer::BoUpSLP &R, bool MaxVFOnly); 142 143 /// Tries to vectorize \p CmpInts. \Returns true on success. 144 template <typename ItT> 145 bool vectorizeCmpInsts(iterator_range<ItT> CmpInsts, BasicBlock *BB, 146 slpvectorizer::BoUpSLP &R); 147 148 /// Tries to vectorize constructs started from InsertValueInst or 149 /// InsertElementInst instructions. 150 bool vectorizeInserts(InstSetVector &Instructions, BasicBlock *BB, 151 slpvectorizer::BoUpSLP &R); 152 153 /// Scan the basic block and look for patterns that are likely to start 154 /// a vectorization chain. 155 bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R); 156 157 std::optional<bool> vectorizeStoreChain(ArrayRef<Value *> Chain, 158 slpvectorizer::BoUpSLP &R, 159 unsigned Idx, unsigned MinVF, 160 unsigned &Size); 161 162 bool vectorizeStores( 163 ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R, 164 DenseSet<std::tuple<Value *, Value *, Value *, Value *, unsigned>> 165 &Visited); 166 167 /// The store instructions in a basic block organized by base pointer. 168 StoreListMap Stores; 169 170 /// The getelementptr instructions in a basic block organized by base pointer. 171 GEPListMap GEPs; 172 }; 173 174 } // end namespace llvm 175 176 #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H 177