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