Home | History | Annotate | Download | only in Vectorize 
      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<WeakVH, 8> WeakVHList;
     44   typedef MapVector<Value *, WeakVHList> WeakVHListMap;
     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   /// \brief Scan the basic block and look for patterns that are likely to start
     96   /// a vectorization chain.
     97   bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
     98 
     99   bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold,
    100                            slpvectorizer::BoUpSLP &R, unsigned VecRegSize);
    101 
    102   bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold,
    103                        slpvectorizer::BoUpSLP &R);
    104 
    105   /// The store instructions in a basic block organized by base pointer.
    106   StoreListMap Stores;
    107 
    108   /// The getelementptr instructions in a basic block organized by base pointer.
    109   WeakVHListMap GEPs;
    110 };
    111 }
    112 
    113 #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H
    114