include/llvm/Transforms/Vectorize/SLPVectorizer.h

   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/Analysis/AliasAnalysis.h"
  26 #include "llvm/IR/PassManager.h"
  27
  28 namespace llvm {
  29
  30 class AssumptionCache;
  31 class BasicBlock;
  32 class CmpInst;
  33 class DataLayout;
  34 class DemandedBits;
  35 class DominatorTree;
  36 class Function;
  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
  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.
  51 namespace slpvectorizer {
  52
  53 class BoUpSLP;
  54
  55 } // end namespace slpvectorizer
  56
  57 extern cl::opt<bool> RunSLPVectorization;
  58
  59 struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> {
  60   using StoreList = SmallVector<StoreInst *, 8>;
  61   using StoreListMap = MapVector<Value *, StoreList>;
  62   using GEPList = SmallVector<GetElementPtrInst *, 8>;
  63   using GEPListMap = MapVector<Value *, GEPList>;
  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   /// 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 chain that starts at two arithmetic instrs.
  95   bool tryToVectorizePair(Value *A, Value *B, slpvectorizer::BoUpSLP &R);
  96
  97   /// Try to vectorize a list of operands.
  98   /// \param UserCost Cost of the user operations of \p VL if they may affect
  99   /// the cost of the vectorization.
 100   /// \returns true if a value was vectorized.
 101   bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
 102                           int UserCost = 0, bool AllowReorder = false);
 103
 104   /// Try to vectorize a chain that may start at the operands of \p I.
 105   bool tryToVectorize(Instruction *I, 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 vectorize a chain of binary
 115   /// operators.
 116   bool vectorizeRootInstruction(PHINode *P, Value *V, BasicBlock *BB,
 117                                 slpvectorizer::BoUpSLP &R,
 118                                 TargetTransformInfo *TTI);
 119
 120   /// Try to vectorize trees that start at insertvalue instructions.
 121   bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB,
 122                                 slpvectorizer::BoUpSLP &R);
 123
 124   /// Try to vectorize trees that start at insertelement instructions.
 125   bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB,
 126                                   slpvectorizer::BoUpSLP &R);
 127
 128   /// Try to vectorize trees that start at compare instructions.
 129   bool vectorizeCmpInst(CmpInst *CI, BasicBlock *BB, slpvectorizer::BoUpSLP &R);
 130
 131   /// Tries to vectorize constructs started from CmpInst, InsertValueInst or
 132   /// InsertElementInst instructions.
 133   bool vectorizeSimpleInstructions(SmallVectorImpl<Instruction *> &Instructions,
 134                                    BasicBlock *BB, slpvectorizer::BoUpSLP &R);
 135
 136   /// Scan the basic block and look for patterns that are likely to start
 137   /// a vectorization chain.
 138   bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
 139
 140   bool vectorizeStoreChain(ArrayRef<Value *> Chain, slpvectorizer::BoUpSLP &R,
 141                            unsigned VecRegSize);
 142
 143   bool vectorizeStores(ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R);
 144
 145   /// The store instructions in a basic block organized by base pointer.
 146   StoreListMap Stores;
 147
 148   /// The getelementptr instructions in a basic block organized by base pointer.
 149   GEPListMap GEPs;
 150 };
 151
 152 } // end namespace llvm
 153
 154 #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H