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 27namespace llvm { 28 29class AAResults; 30class AssumptionCache; 31class BasicBlock; 32class DemandedBits; 33class DominatorTree; 34class Function; 35class GetElementPtrInst; 36class InsertElementInst; 37class InsertValueInst; 38class Instruction; 39class LoopInfo; 40class OptimizationRemarkEmitter; 41class PHINode; 42class ScalarEvolution; 43class StoreInst; 44class TargetLibraryInfo; 45class TargetTransformInfo; 46class Value; 47class WeakTrackingVH; 48 49/// A private "module" namespace for types and utilities used by this pass. 50/// These are implementation details and should not be used by clients. 51namespace slpvectorizer { 52 53class BoUpSLP; 54 55} // end namespace slpvectorizer 56 57struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> { 58 using StoreList = SmallVector<StoreInst *, 8>; 59 using StoreListMap = MapVector<Value *, StoreList>; 60 using GEPList = SmallVector<GetElementPtrInst *, 8>; 61 using GEPListMap = MapVector<Value *, GEPList>; 62 using InstSetVector = SmallSetVector<Instruction *, 8>; 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 74public: 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 83private: 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 list of operands. 94 /// \param MaxVFOnly Vectorize only using maximal allowed register size. 95 /// \returns true if a value was vectorized. 96 bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R, 97 bool MaxVFOnly = false); 98 99 /// Try to vectorize a chain that may start at the operands of \p I. 100 bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R); 101 102 /// Try to vectorize chains that may start at the operands of 103 /// instructions in \p Insts. 104 bool tryToVectorize(ArrayRef<WeakTrackingVH> Insts, 105 slpvectorizer::BoUpSLP &R); 106 107 /// Vectorize the store instructions collected in Stores. 108 bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R); 109 110 /// Vectorize the index computations of the getelementptr instructions 111 /// collected in GEPs. 112 bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R); 113 114 /// Try to find horizontal reduction or otherwise, collect instructions 115 /// for postponed vectorization attempts. 116 /// \a P if not null designates phi node the reduction is fed into 117 /// (with reduction operators \a Root or one of its operands, in a basic block 118 /// \a BB). 119 /// \returns true if a horizontal reduction was matched and reduced. 120 /// \returns false if \a V is null or not an instruction, 121 /// or a horizontal reduction was not matched or not possible. 122 bool vectorizeHorReduction(PHINode *P, Instruction *Root, BasicBlock *BB, 123 slpvectorizer::BoUpSLP &R, 124 TargetTransformInfo *TTI, 125 SmallVectorImpl<WeakTrackingVH> &PostponedInsts); 126 127 /// Make an attempt to vectorize reduction and then try to vectorize 128 /// postponed binary operations. 129 /// \returns true on any successfull vectorization. 130 bool vectorizeRootInstruction(PHINode *P, Instruction *Root, BasicBlock *BB, 131 slpvectorizer::BoUpSLP &R, 132 TargetTransformInfo *TTI); 133 134 /// Try to vectorize trees that start at insertvalue instructions. 135 bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB, 136 slpvectorizer::BoUpSLP &R); 137 138 /// Try to vectorize trees that start at insertelement instructions. 139 bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB, 140 slpvectorizer::BoUpSLP &R); 141 142 /// Tries to vectorize \p CmpInts. \Returns true on success. 143 template <typename ItT> 144 bool vectorizeCmpInsts(iterator_range<ItT> CmpInsts, BasicBlock *BB, 145 slpvectorizer::BoUpSLP &R); 146 147 /// Tries to vectorize constructs started from InsertValueInst or 148 /// InsertElementInst instructions. 149 bool vectorizeInserts(InstSetVector &Instructions, BasicBlock *BB, 150 slpvectorizer::BoUpSLP &R); 151 152 /// Scan the basic block and look for patterns that are likely to start 153 /// a vectorization chain. 154 bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R); 155 156 bool vectorizeStoreChain(ArrayRef<Value *> Chain, slpvectorizer::BoUpSLP &R, 157 unsigned Idx, unsigned MinVF); 158 159 bool vectorizeStores(ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R); 160 161 /// The store instructions in a basic block organized by base pointer. 162 StoreListMap Stores; 163 164 /// The getelementptr instructions in a basic block organized by base pointer. 165 GEPListMap GEPs; 166}; 167 168} // end namespace llvm 169 170#endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H 171