[gcc(refs/users/marxin/heads/slp-ebb-v2)] Version one.

[gcc(refs/users/marxin/heads/slp-ebb-v2)] Version one.

[Martin Liska]

https://gcc.gnu.org/g:7bde8676fc39d9a0c676e9238d41b845af42df0f

commit 7bde8676fc39d9a0c676e9238d41b845af42df0f
Author: Martin Liska <mliska@suse.cz>
Date:   Wed Sep 23 15:58:25 2020 +0200

    Version one.

Diff:
---
 gcc/tree-vect-patterns.c |   2 +
 gcc/tree-vect-slp.c      | 134 ++++++++++++++++++++++++++++++-----------------
 gcc/tree-vectorizer.c    |  20 ++++---
 gcc/tree-vectorizer.h    |  68 +++++++++++++++++++-----
 4 files changed, 150 insertions(+), 74 deletions(-)

diff --git a/gcc/tree-vect-patterns.c b/gcc/tree-vect-patterns.c
index d626c5f7362..09e75437d39 100644
--- a/gcc/tree-vect-patterns.c
+++ b/gcc/tree-vect-patterns.c
@@ -5125,6 +5125,8 @@ vect_determine_precisions (vec_info *vinfo)
       bb_vec_info bb_vinfo = as_a <bb_vec_info> (vinfo);
       for (gimple *stmt : bb_vinfo->reverse_region_stmts ())
 	{
+	  if (stmt == NULL)
+	    continue;
 	  stmt_vec_info stmt_info = vinfo->lookup_stmt (stmt);
 	  if (stmt_info && STMT_VINFO_VECTORIZABLE (stmt_info))
 	    vect_determine_stmt_precisions (vinfo, stmt_info);
diff --git a/gcc/tree-vect-slp.c b/gcc/tree-vect-slp.c
index e0614fb472f..07459d8c168 100644
--- a/gcc/tree-vect-slp.c
+++ b/gcc/tree-vect-slp.c
@@ -45,7 +45,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple-fold.h"
 #include "internal-fn.h"
 #include "dump-context.h"
-
+#include "cfganal.h"
 
 static bool vectorizable_slp_permutation (vec_info *, gimple_stmt_iterator *,
 					  slp_tree, stmt_vector_for_cost *);
@@ -2727,26 +2727,22 @@ vect_detect_hybrid_slp (loop_vec_info loop_vinfo)
 }
 
 
-/* Initialize a bb_vec_info struct for the statements between
-   REGION_BEGIN_IN (inclusive) and REGION_END_IN (exclusive).  */
+/* Initialize a bb_vec_info struct for the statements in BBS basic blocks.  */
 
-_bb_vec_info::_bb_vec_info (gimple_stmt_iterator region_begin_in,
-			    gimple_stmt_iterator region_end_in,
+_bb_vec_info::_bb_vec_info (vec<basic_block> _bbs,
 			    vec_info_shared *shared)
   : vec_info (vec_info::bb, init_cost (NULL), shared),
-    bb (gsi_bb (region_begin_in)),
-    region_begin (region_begin_in),
-    region_end (region_end_in)
+  bbs (_bbs)
 {
   for (gimple *stmt : this->region_stmts ())
     {
+      if (stmt == NULL)
+	continue;
       gimple_set_uid (stmt, 0);
       if (is_gimple_debug (stmt))
 	continue;
       add_stmt (stmt);
     }
-
-  bb->aux = this;
 }
 
 
@@ -2756,10 +2752,9 @@ _bb_vec_info::_bb_vec_info (gimple_stmt_iterator region_begin_in,
 _bb_vec_info::~_bb_vec_info ()
 {
   for (gimple *stmt : this->region_stmts ())
-    /* Reset region marker.  */
-    gimple_set_uid (stmt, -1);
-
-  bb->aux = NULL;
+    if (stmt != NULL)
+      /* Reset region marker.  */
+      gimple_set_uid (stmt, -1);
 }
 
 /* Subroutine of vect_slp_analyze_node_operations.  Handle the root of NODE,
@@ -3462,6 +3457,8 @@ vect_slp_check_for_constructors (bb_vec_info bb_vinfo)
 {
   for (gimple *stmt : bb_vinfo->region_stmts ())
     {
+      if (stmt == NULL)
+	continue;
       gassign *assign = dyn_cast<gassign *> (stmt);
       if (!assign || gimple_assign_rhs_code (assign) != CONSTRUCTOR)
 	continue;
@@ -3601,14 +3598,12 @@ vect_slp_analyze_bb_1 (bb_vec_info bb_vinfo, int n_stmts, bool &fatal,
   return true;
 }
 
-/* Subroutine of vect_slp_bb.  Try to vectorize the statements between
-   REGION_BEGIN (inclusive) and REGION_END (exclusive), returning true
-   on success.  The region has N_STMTS statements and has the datarefs
-   given by DATAREFS.  */
+/* Subroutine of vect_slp_bb.  Try to vectorize the statements for all
+   basic blocks in BBS, returning true on success.
+   The region has N_STMTS statements and has the datarefs given by DATAREFS.  */
 
 static bool
-vect_slp_region (gimple_stmt_iterator region_begin,
-		 gimple_stmt_iterator region_end,
+vect_slp_region (vec<basic_block> bbs,
 		 vec<data_reference_p> datarefs,
 		 vec<int> *dataref_groups,
 		 unsigned int n_stmts)
@@ -3628,7 +3623,7 @@ vect_slp_region (gimple_stmt_iterator region_begin,
     {
       bool vectorized = false;
       bool fatal = false;
-      bb_vinfo = new _bb_vec_info (region_begin, region_end, &shared);
+      bb_vinfo = new _bb_vec_info (bbs, &shared);
 
       bool first_time_p = shared.datarefs.is_empty ();
       BB_VINFO_DATAREFS (bb_vinfo) = datarefs;
@@ -3753,50 +3748,91 @@ vect_slp_region (gimple_stmt_iterator region_begin,
     }
 }
 
-/* Main entry for the BB vectorizer.  Analyze and transform BB, returns
-   true if anything in the basic-block was vectorized.  */
 
-bool
-vect_slp_bb (basic_block bb)
+static bool
+vect_slp_bbs (vec<basic_block> bbs)
 {
   vec<data_reference_p> datarefs = vNULL;
   vec<int> dataref_groups = vNULL;
   int insns = 0;
   int current_group = 0;
-  gimple_stmt_iterator region_begin = gsi_start_nondebug_after_labels_bb (bb);
-  gimple_stmt_iterator region_end = gsi_last_bb (bb);
-  if (!gsi_end_p (region_end))
-    gsi_next (&region_end);
 
-  for (gimple_stmt_iterator gsi = gsi_after_labels (bb); !gsi_end_p (gsi);
-       gsi_next (&gsi))
+  for (unsigned i = 0; i < bbs.length (); i++)
     {
-      gimple *stmt = gsi_stmt (gsi);
-      if (is_gimple_debug (stmt))
-	continue;
+      basic_block bb = bbs[i];
+      for (gimple_stmt_iterator gsi = gsi_after_labels (bb); !gsi_end_p (gsi);
+	   gsi_next (&gsi))
+	{
+	  gimple *stmt = gsi_stmt (gsi);
+	  if (is_gimple_debug (stmt))
+	    continue;
 
-      insns++;
+	  insns++;
 
-      if (gimple_location (stmt) != UNKNOWN_LOCATION)
-	vect_location = stmt;
+	  if (gimple_location (stmt) != UNKNOWN_LOCATION)
+	    vect_location = stmt;
 
-      if (!vect_find_stmt_data_reference (NULL, stmt, &datarefs,
-					  &dataref_groups, current_group))
-	++current_group;
+	  if (!vect_find_stmt_data_reference (NULL, stmt, &datarefs,
+					      &dataref_groups, current_group))
+	    ++current_group;
 
-      if (insns > param_slp_max_insns_in_bb)
-	{
-	  if (dump_enabled_p ())
-	    dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
-			     "not vectorized: too many instructions in "
-			     "basic block.\n");
+	  if (insns > param_slp_max_insns_in_bb)
+	    {
+	      if (dump_enabled_p ())
+		dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+				 "not vectorized: too many instructions in "
+				 "basic block.\n");
+	    }
 	}
     }
 
-  return vect_slp_region (region_begin, region_end, datarefs,
-			  &dataref_groups, insns);
+  return vect_slp_region (bbs, datarefs, &dataref_groups, insns);
 }
 
+/* Main entry for the BB vectorizer.  Analyze and transform BB, returns
+   true if anything in the basic-block was vectorized.  */
+
+bool
+vect_slp_bb (basic_block bb)
+{
+  auto_vec<basic_block> bbs;
+  bbs.safe_push (bb);
+
+  return vect_slp_bbs (bbs);
+}
+
+/* Main entry for the BB vectorizer.  Analyze and transform BB, returns
+   true if anything in the basic-block was vectorized.  */
+
+bool
+vect_slp_function ()
+{
+  bool r = false;
+  int *rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
+  unsigned n = pre_and_rev_post_order_compute_fn (cfun, NULL, rpo, false);
+
+  auto_vec<basic_block> ebb;
+  for (unsigned i = 0; i < n; i++)
+    {
+      basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
+      gphi_iterator phi = gsi_start_phis (bb);
+      if (gsi_end_p (phi))
+	ebb.safe_push (bb);
+      else if (!ebb.is_empty ())
+	{
+	  r |= vect_slp_bbs (ebb);
+	  ebb.truncate (0);
+	  ebb.quick_push (bb);
+	}
+    }
+
+  if (!ebb.is_empty ())
+    r |= vect_slp_bbs (ebb);
+
+  free (rpo);
+
+  return r;
+}
 
 /* Build a variable-length vector in which the elements in ELTS are repeated
    to a fill NRESULTS vectors of type VECTOR_TYPE.  Store the vectors in
@@ -4673,7 +4709,7 @@ vect_schedule_slp_instance (vec_info *vinfo,
 	       we do not insert before the region boundary.  */
 	    if (SLP_TREE_SCALAR_OPS (child).is_empty ()
 		&& !vinfo->lookup_def (SLP_TREE_VEC_DEFS (child)[0]))
-	      last_stmt = gsi_stmt (as_a <bb_vec_info> (vinfo)->region_begin);
+	      last_stmt = gsi_stmt (as_a <bb_vec_info> (vinfo)->region_begin ());
 	    else
 	      {
 		unsigned j;
diff --git a/gcc/tree-vectorizer.c b/gcc/tree-vectorizer.c
index 37e36f556e5..658bd19bbc9 100644
--- a/gcc/tree-vectorizer.c
+++ b/gcc/tree-vectorizer.c
@@ -605,11 +605,11 @@ vec_info::remove_stmt (stmt_vec_info stmt_info)
   set_vinfo_for_stmt (stmt_info->stmt, NULL);
   unlink_stmt_vdef (stmt_info->stmt);
   gimple_stmt_iterator si = gsi_for_stmt (stmt_info->stmt);
-  gimple_stmt_iterator *psi = &si;
+  gimple_stmt_iterator psi = si;
   if (bb_vec_info bb_vinfo = dyn_cast <bb_vec_info> (this))
-    if (gsi_stmt (bb_vinfo->region_begin) == stmt_info->stmt)
-      psi = &bb_vinfo->region_begin;
-  gsi_remove (psi, true);
+    if (gsi_stmt (bb_vinfo->region_begin ()) == stmt_info->stmt)
+      psi = bb_vinfo->region_begin ();
+  gsi_remove (&psi, true);
   release_defs (stmt_info->stmt);
   free_stmt_vec_info (stmt_info);
 }
@@ -653,7 +653,7 @@ vec_info::insert_seq_on_entry (stmt_vec_info context, gimple_seq seq)
   else
     {
       bb_vec_info bb_vinfo = as_a <bb_vec_info> (this);
-      gimple_stmt_iterator gsi_region_begin = bb_vinfo->region_begin;
+      gimple_stmt_iterator gsi_region_begin = bb_vinfo->region_begin ();
       gsi_insert_seq_before (&gsi_region_begin, seq, GSI_SAME_STMT);
     }
 }
@@ -1428,12 +1428,10 @@ pass_slp_vectorize::execute (function *fun)
 	}
     }
 
-  FOR_EACH_BB_FN (bb, fun)
-    {
-      if (vect_slp_bb (bb))
-	if (dump_enabled_p ())
-	  dump_printf_loc (MSG_NOTE, vect_location, "basic block vectorized\n");
-    }
+  if (vect_slp_function ())
+    // TODO: change to function vectorized
+    if (dump_enabled_p ())
+      dump_printf_loc (MSG_NOTE, vect_location, "basic block vectorized\n");
 
   if (!in_loop_pipeline)
     {
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 37b091558fd..0d1cf8cb3f9 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -832,12 +832,18 @@ public:
 
   struct const_iterator
   {
-    const_iterator (gimple_stmt_iterator _gsi) : gsi (_gsi) {}
+    const_iterator (gimple_stmt_iterator _gsi, vec<basic_block> _bbs)
+      : gsi (_gsi), bbs (_bbs), bb_index (1) {}
 
     const const_iterator &
     operator++ ()
     {
-      gsi_next (&gsi); return *this;
+      if (!gsi_end_p (gsi))
+	gsi_next (&gsi);
+      while (gsi_end_p (gsi) && bb_index < (int)bbs.length ())
+	gsi = gsi_start_nondebug_after_labels_bb (bbs[bb_index++]);
+
+      return *this;
     }
 
     gimple *operator* () const { return gsi_stmt (gsi); }
@@ -845,7 +851,8 @@ public:
     bool
     operator== (const const_iterator &other) const
     {
-      return gsi_stmt (gsi) == gsi_stmt (other.gsi);
+      return (gsi_stmt (gsi) == gsi_stmt (other.gsi)
+	      && gsi_bb (gsi) == gsi_bb (other.gsi));
     }
 
     bool
@@ -855,18 +862,33 @@ public:
     }
 
     gimple_stmt_iterator gsi;
+    vec<basic_block> bbs;
+    int bb_index;
   };
 
   /* GIMPLE statement iterator going from region_end to region_begin.  */
 
   struct const_reverse_iterator
   {
-    const_reverse_iterator (gimple_stmt_iterator _gsi) : gsi (_gsi) {}
+    const_reverse_iterator (gimple_stmt_iterator _gsi, vec<basic_block> _bbs)
+      : gsi (_gsi), bbs (_bbs)
+    {
+      bb_index = bbs.length () - 1;
+    }
 
     const const_reverse_iterator &
     operator++ ()
     {
-      gsi_prev (&gsi); return *this;
+      if (!gsi_end_p (gsi))
+	gsi_prev (&gsi);
+      while (gsi_end_p (gsi) && bb_index >= 0)
+	{
+	  gsi = gsi_last_bb (bbs[bb_index--]);
+	  if (!gsi_end_p (gsi))
+	    gsi_prev (&gsi);
+	}
+
+      return *this;
     }
 
     gimple *operator* () const { return gsi_stmt (gsi); }
@@ -874,7 +896,8 @@ public:
     bool
     operator== (const const_reverse_iterator &other) const
     {
-      return gsi_stmt (gsi) == gsi_stmt (other.gsi);
+      return (gsi_stmt (gsi) == gsi_stmt (other.gsi)
+	      && gsi_bb (gsi) == gsi_bb (other.gsi));
     }
 
     bool
@@ -884,17 +907,35 @@ public:
     }
 
     gimple_stmt_iterator gsi;
+    vec<basic_block> bbs;
+    int bb_index;
   };
 
-  _bb_vec_info (gimple_stmt_iterator, gimple_stmt_iterator, vec_info_shared *);
+  _bb_vec_info (vec<basic_block> bbs, vec_info_shared *);
   ~_bb_vec_info ();
 
+  // TODO
+  gimple_stmt_iterator region_begin ()
+  {
+    return gsi_start_nondebug_after_labels_bb (bbs[0]);
+  }
+
+  // TODO
+  gimple_stmt_iterator region_end ()
+  {
+    gimple_stmt_iterator gsi = gsi_last_bb (bbs[bbs.length () - 1]);
+    if (!gsi_end_p (gsi))
+      gsi_next (&gsi);
+    return gsi;
+  }
+
   /* Returns iterator_range for range-based loop.  */
 
   iterator_range<const_iterator>
   region_stmts ()
   {
-    return iterator_range<const_iterator> (region_begin, region_end);
+    return iterator_range<const_iterator> (const_iterator (region_begin (), bbs),
+					   const_iterator (region_end (), bbs));
   }
 
   /* Returns iterator_range for range-based loop in a reverse order.  */
@@ -902,19 +943,17 @@ public:
   iterator_range<const_reverse_iterator>
   reverse_region_stmts ()
   {
-    const_reverse_iterator begin = region_end;
+    const_reverse_iterator begin (region_end (), bbs);
     if (*begin == NULL)
-      begin = const_reverse_iterator (gsi_last_bb (gsi_bb (region_end)));
+      begin = const_reverse_iterator (gsi_last_bb (gsi_bb (region_end ())), bbs);
     else
       ++begin;
 
-    const_reverse_iterator end = region_begin;
+    const_reverse_iterator end (region_begin (), bbs);
     return iterator_range<const_reverse_iterator> (begin, ++end);
   }
 
-  basic_block bb;
-  gimple_stmt_iterator region_begin;
-  gimple_stmt_iterator region_end;
+  vec<basic_block> bbs;
 } *bb_vec_info;
 
 #define BB_VINFO_BB(B)               (B)->bb
@@ -2035,6 +2074,7 @@ extern void vect_get_slp_defs (slp_tree, vec<tree> *);
 extern void vect_get_slp_defs (vec_info *, slp_tree, vec<vec<tree> > *,
 			       unsigned n = -1U);
 extern bool vect_slp_bb (basic_block);
+extern bool vect_slp_function ();
 extern stmt_vec_info vect_find_last_scalar_stmt_in_slp (slp_tree);
 extern stmt_vec_info vect_find_first_scalar_stmt_in_slp (slp_tree);
 extern bool is_simple_and_all_uses_invariant (stmt_vec_info, loop_vec_info);