lib/Transforms/Vectorize/VecUtils.h

   1 //===- VecUtils.h - Vectorization Utilities -------------------------------===//
   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 //
  10 // This family of classes and functions manipulate vectors and chains of
  11 // vectors.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_TRANSFORMS_VECTORIZE_VECUTILS_H
  16 #define LLVM_TRANSFORMS_VECTORIZE_VECUTILS_H
  17
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/SetVector.h"
  20 #include "llvm/ADT/SmallPtrSet.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/Analysis/AliasAnalysis.h"
  23 #include "llvm/IR/IRBuilder.h"
  24 #include <vector>
  25
  26 namespace llvm {
  27
  28 class BasicBlock;
  29 class Instruction;
  30 class Type;
  31 class VectorType;
  32 class StoreInst;
  33 class Value;
  34 class ScalarEvolution;
  35 class DataLayout;
  36 class TargetTransformInfo;
  37 class AliasAnalysis;
  38 class Loop;
  39
  40 /// Bottom Up SLP vectorization utility class.
  41 struct BoUpSLP {
  42   typedef SmallVector<Value *, 8> ValueList;
  43   typedef SmallVector<Instruction *, 16> InstrList;
  44   typedef SmallPtrSet<Value *, 16> ValueSet;
  45   typedef SmallVector<StoreInst *, 8> StoreList;
  46   static const int max_cost = 1 << 20;
  47
  48   // \brief C'tor.
  49   BoUpSLP(BasicBlock *Bb, ScalarEvolution *Se, DataLayout *Dl,
  50           TargetTransformInfo *Tti, AliasAnalysis *Aa, Loop *Lp);
  51
  52   /// \brief Take the pointer operand from the Load/Store instruction.
  53   /// \returns NULL if this is not a valid Load/Store instruction.
  54   static Value *getPointerOperand(Value *I);
  55
  56   /// \brief Take the address space operand from the Load/Store instruction.
  57   /// \returns -1 if this is not a valid Load/Store instruction.
  58   static unsigned getAddressSpaceOperand(Value *I);
  59
  60   /// \returns true if the memory operations A and B are consecutive.
  61   bool isConsecutiveAccess(Value *A, Value *B);
  62
  63   /// \brief Vectorize the tree that starts with the elements in \p VL.
  64   /// \returns the vectorized value.
  65   Value *vectorizeTree(ArrayRef<Value *> VL, int VF);
  66
  67   /// \returns the vectorization cost of the subtree that starts at \p VL.
  68   /// A negative number means that this is profitable.
  69   int getTreeCost(ArrayRef<Value *> VL);
  70
  71   /// \returns the scalarization cost for this list of values. Assuming that
  72   /// this subtree gets vectorized, we may need to extract the values from the
  73   /// roots. This method calculates the cost of extracting the values.
  74   int getScalarizationCost(ArrayRef<Value *> VL);
  75
  76   /// \brief Attempts to order and vectorize a sequence of stores. This
  77   /// function does a quadratic scan of the given stores.
  78   /// \returns true if the basic block was modified.
  79   bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold);
  80
  81   /// \brief Vectorize a group of scalars into a vector tree.
  82   /// \returns the vectorized value.
  83   Value *vectorizeArith(ArrayRef<Value *> Operands);
  84
  85   /// \returns the list of new instructions that were added in order to collect
  86   /// scalars into vectors. This list can be used to further optimize the gather
  87   /// sequences.
  88   InstrList &getGatherSeqInstructions() { return GatherInstructions; }
  89
  90 private:
  91   /// \brief This method contains the recursive part of getTreeCost.
  92   int getTreeCost_rec(ArrayRef<Value *> VL, unsigned Depth);
  93
  94   /// \brief This recursive method looks for vectorization hazards such as
  95   /// values that are used by multiple users and checks that values are used
  96   /// by only one vector lane. It updates the variables LaneMap, MultiUserVals.
  97   void getTreeUses_rec(ArrayRef<Value *> VL, unsigned Depth);
  98
  99   /// \brief This method contains the recursive part of vectorizeTree.
 100   Value *vectorizeTree_rec(ArrayRef<Value *> VL, int VF);
 101
 102   /// \brief Number all of the instructions in the block.
 103   void numberInstructions();
 104
 105   ///  \brief Vectorize a sorted sequence of stores.
 106   bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold);
 107
 108   /// \returns the scalarization cost for this type. Scalarization in this
 109   /// context means the creation of vectors from a group of scalars.
 110   int getScalarizationCost(Type *Ty);
 111
 112   /// \returns the AA location that is being access by the instruction.
 113   AliasAnalysis::Location getLocation(Instruction *I);
 114
 115   /// \brief Checks if it is possible to sink an instruction from
 116   /// \p Src to \p Dst.
 117   /// \returns the pointer to the barrier instruction if we can't sink.
 118   Value *isUnsafeToSink(Instruction *Src, Instruction *Dst);
 119
 120   /// \returns the index of the last instrucion in the BB from \p VL.
 121   /// Only consider the first \p VF elements.
 122   int getLastIndex(ArrayRef<Value *> VL, unsigned VF);
 123
 124   /// \returns the index of the first User of \p VL.
 125   /// Only consider the first \p VF elements.
 126   int getFirstUserIndex(ArrayRef<Value *> VL, unsigned VF);
 127
 128   /// \returns the instruction \p I or \p J that appears last in the BB .
 129   int getLastIndex(Instruction *I, Instruction *J);
 130
 131   /// \returns the insertion point for \p Index.
 132   Instruction *getInsertionPoint(unsigned Index);
 133
 134   /// \returns a vector from a collection of scalars in \p VL.
 135   Value *Scalarize(ArrayRef<Value *> VL, VectorType *Ty);
 136
 137 private:
 138   /// Maps instructions to numbers and back.
 139   SmallDenseMap<Value *, int> InstrIdx;
 140   /// Maps integers to Instructions.
 141   std::vector<Instruction *> InstrVec;
 142
 143   // -- containers that are used during getTreeCost -- //
 144
 145   /// Contains values that must be scalarized because they are used
 146   /// by multiple lanes, or by users outside the tree.
 147   /// NOTICE: The vectorization methods also use this set.
 148   ValueSet MustScalarize;
 149
 150   /// Contains values that have users outside of the vectorized graph.
 151   /// We need to generate extract instructions for these values.
 152   /// NOTICE: The vectorization methods also use this set.
 153   SetVector<Value *> MustExtract;
 154
 155   /// Contains a list of values that are used outside the current tree. This
 156   /// set must be reset between runs.
 157   SetVector<Value *> MultiUserVals;
 158   /// Maps values in the tree to the vector lanes that uses them. This map must
 159   /// be reset between runs of getCost.
 160   std::map<Value *, int> LaneMap;
 161   /// A list of instructions to ignore while sinking
 162   /// memory instructions. This map must be reset between runs of getCost.
 163   ValueSet MemBarrierIgnoreList;
 164
 165   // -- Containers that are used during vectorizeTree -- //
 166
 167   /// Maps between the first scalar to the vector. This map must be reset
 168   /// between runs.
 169   DenseMap<Value *, Value *> VectorizedValues;
 170
 171   // -- Containers that are used after vectorization by the caller -- //
 172
 173   /// A list of instructions that are used when gathering scalars into vectors.
 174   /// In many cases these instructions can be hoisted outside of the BB.
 175   /// Iterating over this list is faster than calling LICM.
 176   /// Notice: We insert NULL ptrs to separate between the different gather
 177   /// sequences.
 178   InstrList GatherInstructions;
 179
 180   /// Instruction builder to construct the vectorized tree.
 181   IRBuilder<> Builder;
 182
 183   // Analysis and block reference.
 184   BasicBlock *BB;
 185   ScalarEvolution *SE;
 186   DataLayout *DL;
 187   TargetTransformInfo *TTI;
 188   AliasAnalysis *AA;
 189   Loop *L;
 190 };
 191
 192 } // end of namespace
 193
 194 #endif // LLVM_TRANSFORMS_VECTORIZE_VECUTILS_H