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 #include "llvm/IR/ValueHandle.h"
  28
  29 namespace llvm {
  30
  31 class AssumptionCache;
  32 class BasicBlock;
  33 class CmpInst;
  34 class DataLayout;
  35 class DemandedBits;
  36 class DominatorTree;
  37 class Function;
  38 class InsertElementInst;
  39 class InsertValueInst;
  40 class Instruction;
  41 class LoopInfo;
  42 class OptimizationRemarkEmitter;
  43 class PHINode;
  44 class ScalarEvolution;
  45 class StoreInst;
  46 class TargetLibraryInfo;
  47 class TargetTransformInfo;
  48 class Value;
  49
  50 /// A private "module" namespace for types and utilities used by this pass.
  51 /// These are implementation details and should not be used by clients.
  52 namespace slpvectorizer {
  53
  54 class BoUpSLP;
  55
  56 } // end namespace slpvectorizer
  57
  58 extern cl::opt<bool> RunSLPVectorization;
  59
  60 struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> {
  61   using StoreList = SmallVector<StoreInst *, 8>;
  62   using StoreListMap = MapVector<Value *, StoreList>;
  63   using WeakTrackingVHList = SmallVector<WeakTrackingVH, 8>;
  64   using WeakTrackingVHListMap = MapVector<Value *, WeakTrackingVHList>;
  65
  66   ScalarEvolution *SE = nullptr;
  67   TargetTransformInfo *TTI = nullptr;
  68   TargetLibraryInfo *TLI = nullptr;
  69   AliasAnalysis *AA = nullptr;
  70   LoopInfo *LI = nullptr;
  71   DominatorTree *DT = nullptr;
  72   AssumptionCache *AC = nullptr;
  73   DemandedBits *DB = nullptr;
  74   const DataLayout *DL = nullptr;
  75
  76 public:
  77   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
  78
  79   // Glue for old PM.
  80   bool runImpl(Function &F, ScalarEvolution *SE_, TargetTransformInfo *TTI_,
  81                TargetLibraryInfo *TLI_, AliasAnalysis *AA_, LoopInfo *LI_,
  82                DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_,
  83                OptimizationRemarkEmitter *ORE_);
  84
  85 private:
  86   /// Collect store and getelementptr instructions and organize them
  87   /// according to the underlying object of their pointer operands. We sort the
  88   /// instructions by their underlying objects to reduce the cost of
  89   /// consecutive access queries.
  90   ///
  91   /// TODO: We can further reduce this cost if we flush the chain creation
  92   ///       every time we run into a memory barrier.
  93   void collectSeedInstructions(BasicBlock *BB);
  94
  95   /// Try to vectorize a chain that starts at two arithmetic instrs.
  96   bool tryToVectorizePair(Value *A, Value *B, slpvectorizer::BoUpSLP &R);
  97
  98   /// Try to vectorize a list of operands.
  99   /// \param UserCost Cost of the user operations of \p VL if they may affect
 100   /// the cost of the vectorization.
 101   /// \returns true if a value was vectorized.
 102   bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
 103                           int UserCost = 0, bool AllowReorder = false);
 104
 105   /// Try to vectorize a chain that may start at the operands of \p I.
 106   bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R);
 107
 108   /// Vectorize the store instructions collected in Stores.
 109   bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R);
 110
 111   /// Vectorize the index computations of the getelementptr instructions
 112   /// collected in GEPs.
 113   bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
 114
 115   /// Try to find horizontal reduction or otherwise vectorize a chain of binary
 116   /// operators.
 117   bool vectorizeRootInstruction(PHINode *P, Value *V, BasicBlock *BB,
 118                                 slpvectorizer::BoUpSLP &R,
 119                                 TargetTransformInfo *TTI);
 120
 121   /// Try to vectorize trees that start at insertvalue instructions.
 122   bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB,
 123                                 slpvectorizer::BoUpSLP &R);
 124
 125   /// Try to vectorize trees that start at insertelement instructions.
 126   bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB,
 127                                   slpvectorizer::BoUpSLP &R);
 128
 129   /// Try to vectorize trees that start at compare instructions.
 130   bool vectorizeCmpInst(CmpInst *CI, BasicBlock *BB, slpvectorizer::BoUpSLP &R);
 131
 132   /// Tries to vectorize constructs started from CmpInst, InsertValueInst or
 133   /// InsertElementInst instructions.
 134   bool vectorizeSimpleInstructions(SmallVectorImpl<WeakVH> &Instructions,
 135                                    BasicBlock *BB, slpvectorizer::BoUpSLP &R);
 136
 137   /// Scan the basic block and look for patterns that are likely to start
 138   /// a vectorization chain.
 139   bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
 140
 141   bool vectorizeStoreChain(ArrayRef<Value *> Chain, slpvectorizer::BoUpSLP &R,
 142                            unsigned VecRegSize);
 143
 144   bool vectorizeStores(ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R);
 145
 146   /// The store instructions in a basic block organized by base pointer.
 147   StoreListMap Stores;
 148
 149   /// The getelementptr instructions in a basic block organized by base pointer.
 150   WeakTrackingVHListMap GEPs;
 151 };
 152
 153 } // end namespace llvm
 154
 155 #endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H