Transforms/Vectorize/SLPVectorizer.h

0001 //===- SLPVectorizer.h ------------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 // This pass implements the Bottom Up SLP vectorizer. It detects consecutive
0009 // stores that can be put together into vector-stores. Next, it attempts to
0010 // construct vectorizable tree using the use-def chains. If a profitable tree
0011 // was found, the SLP vectorizer performs vectorization on the tree.
0012 //
0013 // The pass is inspired by the work described in the paper:
0014 //  "Loop-Aware SLP in GCC" by Ira Rosen, Dorit Nuzman, Ayal Zaks.
0015 //
0016 //===----------------------------------------------------------------------===//
0017
0018 #ifndef LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
0019 #define LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
0020
0021 #include "llvm/ADT/ArrayRef.h"
0022 #include "llvm/ADT/MapVector.h"
0023 #include "llvm/ADT/SetVector.h"
0024 #include "llvm/ADT/SmallVector.h"
0025 #include "llvm/IR/PassManager.h"
0026
0027 namespace llvm {
0028
0029 class AAResults;
0030 class AssumptionCache;
0031 class BasicBlock;
0032 class DataLayout;
0033 class DemandedBits;
0034 class DominatorTree;
0035 class Function;
0036 class GetElementPtrInst;
0037 class InsertElementInst;
0038 class InsertValueInst;
0039 class Instruction;
0040 class LoopInfo;
0041 class OptimizationRemarkEmitter;
0042 class PHINode;
0043 class ScalarEvolution;
0044 class StoreInst;
0045 class TargetLibraryInfo;
0046 class TargetTransformInfo;
0047 class Value;
0048 class WeakTrackingVH;
0049
0050 /// A private "module" namespace for types and utilities used by this pass.
0051 /// These are implementation details and should not be used by clients.
0052 namespace slpvectorizer {
0053
0054 class BoUpSLP;
0055
0056 } // end namespace slpvectorizer
0057
0058 struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> {
0059   using StoreList = SmallVector<StoreInst *, 8>;
0060   using StoreListMap = MapVector<Value *, StoreList>;
0061   using GEPList = SmallVector<GetElementPtrInst *, 8>;
0062   using GEPListMap = MapVector<Value *, GEPList>;
0063   using InstSetVector = SmallSetVector<Instruction *, 8>;
0064
0065   ScalarEvolution *SE = nullptr;
0066   TargetTransformInfo *TTI = nullptr;
0067   TargetLibraryInfo *TLI = nullptr;
0068   AAResults *AA = nullptr;
0069   LoopInfo *LI = nullptr;
0070   DominatorTree *DT = nullptr;
0071   AssumptionCache *AC = nullptr;
0072   DemandedBits *DB = nullptr;
0073   const DataLayout *DL = nullptr;
0074
0075 public:
0076   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
0077
0078   // Glue for old PM.
0079   bool runImpl(Function &F, ScalarEvolution *SE_, TargetTransformInfo *TTI_,
0080                TargetLibraryInfo *TLI_, AAResults *AA_, LoopInfo *LI_,
0081                DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_,
0082                OptimizationRemarkEmitter *ORE_);
0083
0084 private:
0085   /// Collect store and getelementptr instructions and organize them
0086   /// according to the underlying object of their pointer operands. We sort the
0087   /// instructions by their underlying objects to reduce the cost of
0088   /// consecutive access queries.
0089   ///
0090   /// TODO: We can further reduce this cost if we flush the chain creation
0091   ///       every time we run into a memory barrier.
0092   void collectSeedInstructions(BasicBlock *BB);
0093
0094   /// Try to vectorize a list of operands.
0095   /// \param MaxVFOnly Vectorize only using maximal allowed register size.
0096   /// \returns true if a value was vectorized.
0097   bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
0098                           bool MaxVFOnly = false);
0099
0100   /// Try to vectorize a chain that may start at the operands of \p I.
0101   bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R);
0102
0103   /// Try to vectorize chains that may start at the operands of
0104   /// instructions in \p Insts.
0105   bool tryToVectorize(ArrayRef<WeakTrackingVH> Insts,
0106                       slpvectorizer::BoUpSLP &R);
0107
0108   /// Vectorize the store instructions collected in Stores.
0109   bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R);
0110
0111   /// Vectorize the index computations of the getelementptr instructions
0112   /// collected in GEPs.
0113   bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
0114
0115   /// Try to find horizontal reduction or otherwise, collect instructions
0116   /// for postponed vectorization attempts.
0117   /// \a P if not null designates phi node the reduction is fed into
0118   /// (with reduction operators \a Root or one of its operands, in a basic block
0119   /// \a BB).
0120   /// \returns true if a horizontal reduction was matched and reduced.
0121   /// \returns false if \a V is null or not an instruction,
0122   /// or a horizontal reduction was not matched or not possible.
0123   bool vectorizeHorReduction(PHINode *P, Instruction *Root, BasicBlock *BB,
0124                              slpvectorizer::BoUpSLP &R,
0125                              SmallVectorImpl<WeakTrackingVH> &PostponedInsts);
0126
0127   /// Make an attempt to vectorize reduction and then try to vectorize
0128   /// postponed binary operations.
0129   /// \returns true on any successfull vectorization.
0130   bool vectorizeRootInstruction(PHINode *P, Instruction *Root, BasicBlock *BB,
0131                                 slpvectorizer::BoUpSLP &R);
0132
0133   /// Try to vectorize trees that start at insertvalue instructions.
0134   bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB,
0135                                 slpvectorizer::BoUpSLP &R, bool MaxVFOnly);
0136
0137   /// Try to vectorize trees that start at insertelement instructions.
0138   bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB,
0139                                   slpvectorizer::BoUpSLP &R, bool MaxVFOnly);
0140
0141   /// Tries to vectorize \p CmpInts. \Returns true on success.
0142   template <typename ItT>
0143   bool vectorizeCmpInsts(iterator_range<ItT> CmpInsts, BasicBlock *BB,
0144                          slpvectorizer::BoUpSLP &R);
0145
0146   /// Tries to vectorize constructs started from InsertValueInst or
0147   /// InsertElementInst instructions.
0148   bool vectorizeInserts(InstSetVector &Instructions, BasicBlock *BB,
0149                         slpvectorizer::BoUpSLP &R);
0150
0151   /// Scan the basic block and look for patterns that are likely to start
0152   /// a vectorization chain.
0153   bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
0154
0155   std::optional<bool> vectorizeStoreChain(ArrayRef<Value *> Chain,
0156                                           slpvectorizer::BoUpSLP &R,
0157                                           unsigned Idx, unsigned MinVF,
0158                                           unsigned &Size);
0159
0160   bool vectorizeStores(
0161       ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R,
0162       DenseSet<std::tuple<Value *, Value *, Value *, Value *, unsigned>>
0163           &Visited);
0164
0165   /// The store instructions in a basic block organized by base pointer.
0166   StoreListMap Stores;
0167
0168   /// The getelementptr instructions in a basic block organized by base pointer.
0169   GEPListMap GEPs;
0170 };
0171
0172 } // end namespace llvm
0173
0174 #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H