lib/Transforms/Vectorize/VecUtils.h

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