From 902510bd498acfc9e30636f8267b57027bc63254 Mon Sep 17 00:00:00 2001
From: Joel Hutton <Joel.Hutton@arm.com>
Date: Tue, 22 Oct 2019 10:05:19 +0100
Subject: [PATCH] SLP Vectorization: Vectorize vector constructors

---
 gcc/expr.c                            |   5 +-
 gcc/testsuite/gcc.dg/vect/bb-slp-40.c |  34 +++++
 gcc/testsuite/gcc.dg/vect/bb-slp-41.c |  61 +++++++++
 gcc/tree-vect-slp.c                   | 171 +++++++++++++++++++++++++-
 gcc/tree-vectorizer.h                 |   5 +
 5 files changed, 273 insertions(+), 3 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-40.c
 create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-41.c

diff --git a/gcc/expr.c b/gcc/expr.c
index 476c6865f20828fc68f455e70d4874eaabd9d08d..ea4705e47c7e8424cca5e19319ef21db415f496a 100644
--- a/gcc/expr.c
+++ b/gcc/expr.c
@@ -6825,7 +6825,10 @@ store_constructor (tree exp, rtx target, int cleared, poly_int64 size,
 	      {
 		unsigned int n = const_n_elts;
 
-		if (emode != eltmode)
+		if (emode != eltmode
+		    || (TREE_CODE (TREE_TYPE (exp)) == VECTOR_TYPE
+			&& TREE_CODE (TREE_TYPE (CONSTRUCTOR_ELT(exp, 0)->value))
+			   == VECTOR_TYPE))
 		  {
 		    n = CONSTRUCTOR_NELTS (exp);
 		    vec_vec_init_p = true;
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-40.c b/gcc/testsuite/gcc.dg/vect/bb-slp-40.c
new file mode 100644
index 0000000000000000000000000000000000000000..a1dd372184623f34f8f2825aa5da50dc70c98084
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-40.c
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-slp-all" } */
+/* { dg-require-effective-target vect_int } */
+
+char g_d[1024], g_s1[1024], g_s2[1024];
+void foo(void)
+{
+    char *d = g_d, *s1 = g_s1, *s2 = g_s2;
+
+    for ( int y = 0; y < 128; y++ )
+    {
+      d[0 ] = s1[0 ] + s2[0 ];
+      d[1 ] = s1[1 ] + s2[1 ];
+      d[2 ] = s1[2 ] + s2[2 ];
+      d[3 ] = s1[3 ] + s2[3 ];
+      d[4 ] = s1[4 ] + s2[4 ];
+      d[5 ] = s1[5 ] + s2[5 ];
+      d[6 ] = s1[6 ] + s2[6 ];
+      d[7 ] = s1[7 ] + s2[7 ];
+      d[8 ] = s1[8 ] + s2[8 ];
+      d[9 ] = s1[9 ] + s2[9 ];
+      d[10] = s1[10] + s2[10];
+      d[11] = s1[11] + s2[11];
+      d[12] = s1[12] + s2[12];
+      d[13] = s1[13] + s2[13];
+      d[14] = s1[14] + s2[14];
+      d[15] = s1[15] + s2[15];
+      d += 16;
+    }
+}
+
+/* See that we vectorize an SLP instance.  */
+/* { dg-final { scan-tree-dump-times "Found vectorizable constructor" 1 "slp1" } } */
+/* { dg-final { scan-tree-dump-times "vectorizing stmts using SLP" 1 "slp1" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-41.c b/gcc/testsuite/gcc.dg/vect/bb-slp-41.c
new file mode 100644
index 0000000000000000000000000000000000000000..618d1d0ef3f6da93b53df62296620d589ad2e21a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-41.c
@@ -0,0 +1,61 @@
+/* { dg-do run } */
+/* { dg-options "-O3 -fdump-tree-slp-all -fno-vect-cost-model" } */
+/* { dg-require-effective-target vect_int } */
+
+#define ARR_SIZE 1000
+
+void foo (int *a, int *b)
+{
+  int i;
+  for (i = 0; i < (ARR_SIZE - 2); ++i)
+    a[i] = b[0] + b[1] + b[i+1] + b[i+2];
+}
+
+void bar (int *a, int *b)
+{
+  int i;
+  for (i = 0; i < (ARR_SIZE - 2); ++i)
+  {
+    a[i] = b[0];
+  }
+  for (i = 0; i < (ARR_SIZE - 2); ++i)
+  {
+    a[i] = a[i] + b[1];
+  }
+  for (i = 0; i < (ARR_SIZE - 2); ++i)
+  {
+    a[i] = a[i] + b[i+1];
+  }
+  for (i = 0; i < (ARR_SIZE - 2); ++i)
+  {
+    a[i] = a[i] + b[i+2];
+  }
+}
+
+int main ()
+{
+  int a1[ARR_SIZE];
+  int a2[ARR_SIZE];
+  int b[ARR_SIZE];
+  int i;
+
+  for (i = 0; i < ARR_SIZE; i++)
+  {
+    a1[i] = 0;
+    a2[i] = 0;
+    b[i]  = i;
+  }
+
+  foo (a1, b);
+  bar (a2, b);
+
+  for (i = 0; i < ARR_SIZE; i++)
+    if (a1[i] != a2[i])
+      return 1;
+
+  return 0;
+
+}
+/* See that we vectorize an SLP instance.  */
+/* { dg-final { scan-tree-dump-times "Found vectorizable constructor" 4 "slp1" } } */
+/* { dg-final { scan-tree-dump-times "vectorizing stmts using SLP" 2 "slp1" } } */
diff --git a/gcc/tree-vect-slp.c b/gcc/tree-vect-slp.c
index e1061ede061751f5fd6c55edb56671a854e7456e..be7bb27899da06d22ddc4833b3e90a2f8c000177 100644
--- a/gcc/tree-vect-slp.c
+++ b/gcc/tree-vect-slp.c
@@ -1983,6 +1983,7 @@ vect_analyze_slp_instance (vec_info *vinfo,
   unsigned int i;
   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
   vec<stmt_vec_info> scalar_stmts;
+  bool constructor = false;
 
   if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
     {
@@ -1996,6 +1997,13 @@ vect_analyze_slp_instance (vec_info *vinfo,
       vectype = STMT_VINFO_VECTYPE (stmt_info);
       group_size = REDUC_GROUP_SIZE (stmt_info);
     }
+  else if (is_gimple_assign (stmt_info->stmt)
+	    && gimple_assign_rhs_code (stmt_info->stmt) == CONSTRUCTOR)
+    {
+      vectype = TREE_TYPE (gimple_assign_rhs1 (stmt_info->stmt));
+      group_size = CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt_info->stmt));
+      constructor = true;
+    }
   else
     {
       gcc_assert (is_a <loop_vec_info> (vinfo));
@@ -2042,6 +2050,25 @@ vect_analyze_slp_instance (vec_info *vinfo,
       STMT_VINFO_REDUC_DEF (vect_orig_stmt (stmt_info))
 	= STMT_VINFO_REDUC_DEF (vect_orig_stmt (scalar_stmts.last ()));
     }
+  else if (constructor)
+    {
+      tree rhs = gimple_assign_rhs1 (stmt_info->stmt);
+      tree val;
+      FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs), i, val)
+	{
+	  if (TREE_CODE (val) == SSA_NAME)
+	    {
+	      gimple* def = SSA_NAME_DEF_STMT (val);
+	      stmt_vec_info def_info = vinfo->lookup_stmt (def);
+	      /* Value is defined in another basic block.  */
+	      if (!def_info)
+		return false;
+	      scalar_stmts.safe_push (def_info);
+	    }
+	  else
+	    return false;
+	}
+    }
   else
     {
       /* Collect reduction statements.  */
@@ -2099,6 +2126,8 @@ vect_analyze_slp_instance (vec_info *vinfo,
 	  SLP_INSTANCE_GROUP_SIZE (new_instance) = group_size;
 	  SLP_INSTANCE_UNROLLING_FACTOR (new_instance) = unrolling_factor;
 	  SLP_INSTANCE_LOADS (new_instance) = vNULL;
+	  SLP_INSTANCE_ROOT_STMT (new_instance) = constructor ? stmt_info->stmt\
+						  : NULL;
 	  vect_gather_slp_loads (new_instance, node);
 	  if (dump_enabled_p ())
 	    dump_printf_loc (MSG_NOTE, vect_location,
@@ -2801,6 +2830,10 @@ vect_bb_slp_scalar_cost (basic_block bb,
 		stmt_vec_info use_stmt_info = vinfo->lookup_stmt (use_stmt);
 		if (!use_stmt_info || !PURE_SLP_STMT (use_stmt_info))
 		  {
+		    /* Check this is not a constructor that will be vectorized
+		       away.  */
+		    if (BB_VINFO_GROUPED_STORES (vinfo).contains (use_stmt_info))
+			continue;
 		    (*life)[i] = true;
 		    BREAK_FROM_IMM_USE_STMT (use_iter);
 		  }
@@ -2912,6 +2945,38 @@ vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo)
   return true;
 }
 
+/* Find any vectorizable constructors, and add them to the grouped_store
+   array.  */
+
+static void
+vect_slp_check_for_constructors (bb_vec_info bb_vinfo)
+{
+  gimple_stmt_iterator gsi;
+
+  for (gsi = bb_vinfo->region_begin;
+      gsi_stmt (gsi) != gsi_stmt (bb_vinfo->region_end); gsi_next (&gsi))
+    {
+      gimple *stmt = gsi_stmt (gsi);
+
+      if (is_gimple_assign (stmt)
+	  && gimple_assign_rhs_code (stmt) == CONSTRUCTOR
+	  && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
+	  && TREE_CODE (TREE_TYPE (gimple_assign_lhs (stmt))) == VECTOR_TYPE)
+	{
+	  tree rhs = gimple_assign_rhs1 (stmt);
+
+	  if (CONSTRUCTOR_NELTS (rhs) == 0)
+	    continue;
+
+	  if (dump_enabled_p ())
+	    dump_printf_loc (MSG_NOTE, vect_location,
+			     "Found vectorizable constructor: %G\n", stmt);
+	  stmt_vec_info stmt_info = bb_vinfo->lookup_stmt (stmt);
+	  BB_VINFO_GROUPED_STORES (bb_vinfo).safe_push (stmt_info);
+	}
+    }
+}
+
 /* Check if the region described by BB_VINFO can be vectorized, returning
    true if so.  When returning false, set FATAL to true if the same failure
    would prevent vectorization at other vector sizes, false if it is still
@@ -2959,6 +3024,8 @@ vect_slp_analyze_bb_1 (bb_vec_info bb_vinfo, int n_stmts, bool &fatal)
       return false;
     }
 
+  vect_slp_check_for_constructors (bb_vinfo);
+
   /* If there are no grouped stores in the region there is no need
      to continue with pattern recog as vect_analyze_slp will fail
      anyway.  */
@@ -4022,6 +4089,68 @@ vect_remove_slp_scalar_calls (slp_tree node)
   vect_remove_slp_scalar_calls (node, visited);
 }
 
+/* Vectorize the instance root.  Return success or failure.  */
+
+bool
+vectorize_slp_instance_root_stmt (slp_tree node, slp_instance instance)
+{
+
+  if (SLP_TREE_NUMBER_OF_VEC_STMTS (node) == 1)
+    {
+      stmt_vec_info child_stmt_info;
+      int j;
+      tree constructor;
+      constructor = gimple_assign_rhs1 (SLP_INSTANCE_ROOT_STMT (instance));
+
+      FOR_EACH_VEC_ELT (SLP_TREE_VEC_STMTS (node), j, child_stmt_info)
+	{
+	  tree vect_lhs = gimple_get_lhs (child_stmt_info->stmt);
+	  gassign *rstmt
+	    = gimple_build_assign (gimple_get_lhs (instance->root_stmt),
+		gimple_get_lhs (child_stmt_info->stmt));
+	  gimple_stmt_iterator rgsi = gsi_for_stmt (instance->root_stmt);
+	  if (TYPE_VECTOR_SUBPARTS (TREE_TYPE (vect_lhs)).is_constant ()
+	      && (CONSTRUCTOR_NELTS (constructor)
+		  == TYPE_VECTOR_SUBPARTS (TREE_TYPE (vect_lhs)).to_constant ()))
+	    {
+	      gsi_replace (&rgsi, rstmt, true);
+	      SLP_INSTANCE_ROOT_STMT (instance) = NULL;
+	    }
+	  break;
+	}
+    }
+  else if (SLP_TREE_NUMBER_OF_VEC_STMTS (node) > 1)
+    {
+      int nelts = SLP_TREE_NUMBER_OF_VEC_STMTS (node);
+      stmt_vec_info child_stmt_info;
+      int j;
+      vec<constructor_elt, va_gc> *v;
+      vec_alloc (v, nelts);
+      FOR_EACH_VEC_ELT (SLP_TREE_VEC_STMTS (node), j, child_stmt_info)
+	{
+	  CONSTRUCTOR_APPEND_ELT (v,
+				  NULL_TREE,
+				  gimple_get_lhs (child_stmt_info->stmt));
+	}
+      tree type = TREE_TYPE (gimple_assign_rhs1 (instance->root_stmt));
+      tree r_constructor = build_constructor (type, v);
+      gassign *rstmt
+	= gimple_build_assign (gimple_get_lhs (instance->root_stmt),
+	    r_constructor);
+      gimple_stmt_iterator rgsi = gsi_for_stmt (instance->root_stmt);
+      gsi_replace (&rgsi, rstmt, true);
+      SLP_INSTANCE_ROOT_STMT (instance) = NULL;
+    }
+  else
+    {
+      if (dump_enabled_p ())
+	dump_printf_loc (MSG_NOTE, vect_location,
+	    "vectorization of constructor failed.\n");
+      return false;
+    }
+  return true;
+}
+
 /* Generate vector code for all SLP instances in the loop/basic block.  */
 
 void
@@ -4036,9 +4165,20 @@ vect_schedule_slp (vec_info *vinfo)
   slp_instances = vinfo->slp_instances;
   FOR_EACH_VEC_ELT (slp_instances, i, instance)
     {
+      slp_tree node = SLP_INSTANCE_TREE (instance);
       /* Schedule the tree of INSTANCE.  */
-      vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance),
+      vect_schedule_slp_instance (node,
 				  instance, bst_map);
+
+      /* Vectorize the instance root.  */
+      if (instance->root == node && SLP_INSTANCE_ROOT_STMT (instance)
+	  && SLP_TREE_VEC_STMTS (node).exists ())
+	if (!vectorize_slp_instance_root_stmt (node, instance))
+	  {
+	    delete bst_map;
+	    return;
+	  }
+
       if (dump_enabled_p ())
 	dump_printf_loc (MSG_NOTE, vect_location,
                          "vectorizing stmts using SLP.\n");
@@ -4061,15 +4201,42 @@ vect_schedule_slp (vec_info *vinfo)
       if (is_a <loop_vec_info> (vinfo))
 	vect_remove_slp_scalar_calls (root);
 
+      auto_vec<stmt_vec_info> removed;
+
       for (j = 0; SLP_TREE_SCALAR_STMTS (root).iterate (j, &store_info)
                   && j < SLP_INSTANCE_GROUP_SIZE (instance); j++)
         {
 	  if (!STMT_VINFO_DATA_REF (store_info))
 	    break;
 
+	  if (removed.contains (store_info))
+	    continue;
+
 	  store_info = vect_orig_stmt (store_info);
+	  tree lhs = gimple_get_lhs (store_info->stmt);
+	  bool used = false;
+	  /* We must ensure we don't remove def stmts for ssa names used
+	     elsewhere.  */
+	  if (TREE_CODE (lhs) == SSA_NAME)
+	    {
+	      gimple *use_stmt;
+	      imm_use_iterator use_iter;
+
+	      FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, lhs)
+		{
+		  if (use_stmt != store_info->stmt)
+		  {
+		    used = true;
+		    BREAK_FROM_IMM_USE_STMT (use_iter);
+		  }
+		}
+	    }
+
 	  /* Free the attached stmt_vec_info and remove the stmt.  */
-	  vinfo->remove_stmt (store_info);
+
+	  if (!used)
+	    vinfo->remove_stmt (store_info);
+	  removed.safe_push (store_info);
         }
     }
 }
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 56be28b0cc5a77412f996e70636b08d5b615813e..9f8419e4208b7d438ace41892022f93ebcadd019 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -151,6 +151,10 @@ public:
   /* The root of SLP tree.  */
   slp_tree root;
 
+  /* For vector constructors, the constructor stmt that the SLP tree is built
+     from, NULL otherwise.  */
+  gimple *root_stmt;
+
   /* Size of groups of scalar stmts that will be replaced by SIMD stmt/s.  */
   unsigned int group_size;
 
@@ -170,6 +174,7 @@ public:
 #define SLP_INSTANCE_GROUP_SIZE(S)               (S)->group_size
 #define SLP_INSTANCE_UNROLLING_FACTOR(S)         (S)->unrolling_factor
 #define SLP_INSTANCE_LOADS(S)                    (S)->loads
+#define SLP_INSTANCE_ROOT_STMT(S)                (S)->root_stmt
 
 #define SLP_TREE_CHILDREN(S)                     (S)->children
 #define SLP_TREE_SCALAR_STMTS(S)                 (S)->stmts
-- 
2.17.1

