SLPVectorizer: add support for vectorization of diamond shaped trees. We now perform a preliminary traversal of the graph to collect values with multiple users and check where the users came from.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179414 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 47 insertions, 11 deletions

diff --git a/lib/Transforms/Vectorize/VecUtils.h b/lib/Transforms/Vectorize/VecUtils.h
index b1c2b0c649..808fb10f9f 100644
--- a/lib/Transforms/Vectorize/VecUtils.h
+++ b/lib/Transforms/Vectorize/VecUtils.h
@@ -42,6 +42,14 @@ struct BoUpSLP  {
   BoUpSLP(BasicBlock *Bb, ScalarEvolution *Se, DataLayout *Dl,
          TargetTransformInfo *Tti, AliasAnalysis *Aa);
 
+  /// \brief Take the pointer operand from the Load/Store instruction.
+  /// \returns NULL if this is not a valid Load/Store instruction.
+  static Value *getPointerOperand(Value *I);
+
+  /// \brief Take the address space operand from the Load/Store instruction.
+  /// \returns -1 if this is not a valid Load/Store instruction.
+  static unsigned getAddressSpaceOperand(Value *I);
+
   /// \returns true if the memory operations A and B are consecutive.
   bool isConsecutiveAccess(Value *A, Value *B);
 
@@ -51,25 +59,31 @@ struct BoUpSLP  {
 
   /// \returns the vectorization cost of the subtree that starts at \p VL.
   /// A negative number means that this is profitable.
-  int getTreeRollCost(ValueList &VL, unsigned Depth);
-
-  /// \brief Take the pointer operand from the Load/Store instruction.
-  /// \returns NULL if this is not a valid Load/Store instruction.
-  static Value *getPointerOperand(Value *I);
-
-  /// \brief Take the address space operand from the Load/Store instruction.
-  /// \returns -1 if this is not a valid Load/Store instruction.
-  static unsigned getAddressSpaceOperand(Value *I);
+  int getTreeCost(ValueList &VL);
 
   /// \brief Attempts to order and vectorize a sequence of stores. This
   /// function does a quadratic scan of the given stores.
   /// \returns true if the basic block was modified.
   bool vectorizeStores(StoreList &Stores, int costThreshold);
 
+private:
+  /// \returns This method contains the recursive part of getTreeCost.
+  int getTreeCost_rec(ValueList &VL, unsigned Depth);
+
+  /// \returns This recursive method looks for vectorization hazards such as
+  /// values that are used by multiple users and checks that values are used
+  /// by only one vector lane. It updates the variables LaneMap, MultiUserVals.
+  void getTreeUses_rec(ValueList &VL, unsigned Depth);
+
+  /// \brief This method contains the recursive part of vectorizeTree.
+  Value *vectorizeTree_rec(ValueList &VL, int VF);
+
   /// \brief Number all of the instructions in the block.
   void numberInstructions();
 
-private:
+  ///  \brief Vectorize a sorted sequence of stores.
+  bool vectorizeStoreChain(ValueList &Chain, int CostThreshold);
+
   /// \returns the scalarization cost for this type. Scalarization in this
   /// context means the creation of vectors from a group of scalars.
   int getScalarizationCost(Type *Ty);
@@ -89,12 +103,34 @@ private:
   /// \returns a vector from a collection of scalars in \p VL.
   Value *Scalarize(ValueList &VL, VectorType *Ty);
 
+private:
   // Maps instructions to numbers and back.
   SmallDenseMap<Value*, int> InstrIdx;
+  // Maps integers to Instructions.
   std::vector<Instruction*> InstrVec;
+
+  // -- containers that are used during getTreeCost -- //
+
+  /// Contains values that must be scalarized because they are used
+  /// by multiple lanes, or by users outside the tree.
+  /// NOTICE: The vectorization methods also use this set.
+  ValueSet MustScalarize;
+  
+  // Contains a list of values that are used outside the current tree. This
+  // set must be reset between runs.
+  ValueSet MultiUserVals;
+  // Maps values in the tree to the vector lanes that uses them. This map must
+  // be reset between runs of getCost.
+  std::map<Value*, int> LaneMap;
   // A list of instructions to ignore while sinking
-  // memory instructions.
+  // memory instructions. This map must be reset between runs of getCost.
   SmallSet<Value*, 8> MemBarrierIgnoreList;
+
+  // -- containers that are used during vectorizeTree -- //
+  // Maps between the first scalar to the vector. This map must be reset between
+  // runs.
+  DenseMap<Value*, Value*> VectorizedValues;
+
   // Analysis and block reference.
   BasicBlock *BB;
   ScalarEvolution *SE;