contrib/llvm/include/llvm/Transforms/Vectorize/SLPVectorizer.h

   1 //===---- SLPVectorizer.h ---------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 // This pass implements the Bottom Up SLP vectorizer. It detects consecutive
  10 // stores that can be put together into vector-stores. Next, it attempts to
  11 // construct vectorizable tree using the use-def chains. If a profitable tree
  12 // was found, the SLP vectorizer performs vectorization on the tree.
  13 //
  14 // The pass is inspired by the work described in the paper:
  15 //  "Loop-Aware SLP in GCC" by Ira Rosen, Dorit Nuzman, Ayal Zaks.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #ifndef LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
  20 #define LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
  21
  22 #include "llvm/ADT/MapVector.h"
  23 #include "llvm/Analysis/AliasAnalysis.h"
  24 #include "llvm/Analysis/AssumptionCache.h"
  25 #include "llvm/Analysis/DemandedBits.h"
  26 #include "llvm/Analysis/LoopInfo.h"
  27 #include "llvm/Analysis/ScalarEvolution.h"
  28 #include "llvm/Analysis/TargetTransformInfo.h"
  29 #include "llvm/IR/Function.h"
  30 #include "llvm/IR/PassManager.h"
  31
  32 namespace llvm {
  33
  34 /// A private "module" namespace for types and utilities used by this pass.
  35 /// These are implementation details and should not be used by clients.
  36 namespace slpvectorizer {
  37 class BoUpSLP;
  38 }
  39
  40 struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> {
  41   typedef SmallVector<StoreInst *, 8> StoreList;
  42   typedef MapVector<Value *, StoreList> StoreListMap;
  43   typedef SmallVector<WeakTrackingVH, 8> WeakTrackingVHList;
  44   typedef MapVector<Value *, WeakTrackingVHList> WeakTrackingVHListMap;
  45
  46   ScalarEvolution *SE = nullptr;
  47   TargetTransformInfo *TTI = nullptr;
  48   TargetLibraryInfo *TLI = nullptr;
  49   AliasAnalysis *AA = nullptr;
  50   LoopInfo *LI = nullptr;
  51   DominatorTree *DT = nullptr;
  52   AssumptionCache *AC = nullptr;
  53   DemandedBits *DB = nullptr;
  54   const DataLayout *DL = nullptr;
  55
  56 public:
  57   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
  58
  59   // Glue for old PM.
  60   bool runImpl(Function &F, ScalarEvolution *SE_, TargetTransformInfo *TTI_,
  61                TargetLibraryInfo *TLI_, AliasAnalysis *AA_, LoopInfo *LI_,
  62                DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_);
  63
  64 private:
  65   /// \brief Collect store and getelementptr instructions and organize them
  66   /// according to the underlying object of their pointer operands. We sort the
  67   /// instructions by their underlying objects to reduce the cost of
  68   /// consecutive access queries.
  69   ///
  70   /// TODO: We can further reduce this cost if we flush the chain creation
  71   ///       every time we run into a memory barrier.
  72   void collectSeedInstructions(BasicBlock *BB);
  73
  74   /// \brief Try to vectorize a chain that starts at two arithmetic instrs.
  75   bool tryToVectorizePair(Value *A, Value *B, slpvectorizer::BoUpSLP &R);
  76
  77   /// \brief Try to vectorize a list of operands.
  78   /// \@param BuildVector A list of users to ignore for the purpose of
  79   ///                     scheduling and that don't need extracting.
  80   /// \returns true if a value was vectorized.
  81   bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
  82                           ArrayRef<Value *> BuildVector = None,
  83                           bool AllowReorder = false);
  84
  85   /// \brief Try to vectorize a chain that may start at the operands of \V;
  86   bool tryToVectorize(BinaryOperator *V, slpvectorizer::BoUpSLP &R);
  87
  88   /// \brief Vectorize the store instructions collected in Stores.
  89   bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R);
  90
  91   /// \brief Vectorize the index computations of the getelementptr instructions
  92   /// collected in GEPs.
  93   bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
  94
  95   /// Try to find horizontal reduction or otherwise vectorize a chain of binary
  96   /// operators.
  97   bool vectorizeRootInstruction(PHINode *P, Value *V, BasicBlock *BB,
  98                                 slpvectorizer::BoUpSLP &R,
  99                                 TargetTransformInfo *TTI);
 100
 101   /// \brief Scan the basic block and look for patterns that are likely to start
 102   /// a vectorization chain.
 103   bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
 104
 105   bool vectorizeStoreChain(ArrayRef<Value *> Chain, slpvectorizer::BoUpSLP &R,
 106                            unsigned VecRegSize);
 107
 108   bool vectorizeStores(ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R);
 109
 110   /// The store instructions in a basic block organized by base pointer.
 111   StoreListMap Stores;
 112
 113   /// The getelementptr instructions in a basic block organized by base pointer.
 114   WeakTrackingVHListMap GEPs;
 115 };
 116 }
 117
 118 #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H