[gcc(refs/users/marxin/heads/slp-function-v7)] SLP: vectorize entire function.

[Martin Liska <marxin@gcc.gnu.org>]

https://gcc.gnu.org/g:24f3a28f9f63ee02413b03f02144352fe1691d37

commit 24f3a28f9f63ee02413b03f02144352fe1691d37
Author: Martin Liska <mliska@suse.cz>
Date:   Thu Jun 11 13:25:40 2020 +0200

    SLP: vectorize entire function.

Diff:
---
 gcc/tree-vect-data-refs.c |  30 +++++++---
 gcc/tree-vect-loop.c      |   5 +-
 gcc/tree-vect-slp.c       | 150 +++++++++++++++++++++++++++++++++++++---------
 gcc/tree-vect-stmts.c     |   5 +-
 gcc/tree-vectorizer.c     |  18 +++++-
 gcc/tree-vectorizer.h     |  26 ++++++--
 6 files changed, 186 insertions(+), 48 deletions(-)

diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c
index eb8288e7a85..92ad181addb 100644
--- a/gcc/tree-vect-data-refs.c
+++ b/gcc/tree-vect-data-refs.c
@@ -2853,10 +2853,10 @@ dr_group_sort_cmp (const void *dra_, const void *drb_)
     return 0;
 
   /* DRs in different loops never belong to the same group.  */
-  loop_p loopa = gimple_bb (DR_STMT (dra))->loop_father;
-  loop_p loopb = gimple_bb (DR_STMT (drb))->loop_father;
-  if (loopa != loopb)
-    return loopa->num < loopb->num ? -1 : 1;
+  int bb_index1 = gimple_bb (DR_STMT (dra))->index;
+  int bb_index2 = gimple_bb (DR_STMT (drb))->index;
+  if (bb_index1 != bb_index2)
+    return bb_index1 < bb_index2 ? -1 : 1;
 
   /* Ordering of DRs according to base.  */
   cmp = data_ref_compare_tree (DR_BASE_ADDRESS (dra),
@@ -2962,7 +2962,8 @@ can_group_stmts_p (stmt_vec_info stmt1_info, stmt_vec_info stmt2_info,
    FORNOW: handle only arrays and pointer accesses.  */
 
 opt_result
-vect_analyze_data_ref_accesses (vec_info *vinfo)
+vect_analyze_data_ref_accesses (vec_info *vinfo,
+				vec<int> *dataref_groups)
 {
   unsigned int i;
   vec<data_reference_p> datarefs = vinfo->shared->datarefs;
@@ -2984,6 +2985,7 @@ vect_analyze_data_ref_accesses (vec_info *vinfo)
   for (i = 0; i < datarefs_copy.length () - 1;)
     {
       data_reference_p dra = datarefs_copy[i];
+      int dra_group_id = dataref_groups ? (*dataref_groups)[i] : 0;
       dr_vec_info *dr_info_a = vinfo->lookup_dr (dra);
       stmt_vec_info stmtinfo_a = dr_info_a->stmt;
       stmt_vec_info lastinfo = NULL;
@@ -2996,6 +2998,7 @@ vect_analyze_data_ref_accesses (vec_info *vinfo)
       for (i = i + 1; i < datarefs_copy.length (); ++i)
 	{
 	  data_reference_p drb = datarefs_copy[i];
+	  int drb_group_id = dataref_groups ? (*dataref_groups)[i] : 0;
 	  dr_vec_info *dr_info_b = vinfo->lookup_dr (drb);
 	  stmt_vec_info stmtinfo_b = dr_info_b->stmt;
 	  if (!STMT_VINFO_VECTORIZABLE (stmtinfo_b)
@@ -3008,10 +3011,14 @@ vect_analyze_data_ref_accesses (vec_info *vinfo)
 	     matters we can push those to a worklist and re-iterate
 	     over them.  The we can just skip ahead to the next DR here.  */
 
-	  /* DRs in a different loop should not be put into the same
+	  /* DRs in a different BBs should not be put into the same
 	     interleaving group.  */
-	  if (gimple_bb (DR_STMT (dra))->loop_father
-	      != gimple_bb (DR_STMT (drb))->loop_father)
+	  int bb_index1 = gimple_bb (DR_STMT (dra))->index;
+	  int bb_index2 = gimple_bb (DR_STMT (drb))->index;
+	  if (bb_index1 != bb_index2)
+	    break;
+
+	  if (dra_group_id != drb_group_id)
 	    break;
 
 	  /* Check that the data-refs have same first location (except init)
@@ -4070,7 +4077,8 @@ vect_check_gather_scatter (stmt_vec_info stmt_info, loop_vec_info loop_vinfo,
 
 opt_result
 vect_find_stmt_data_reference (loop_p loop, gimple *stmt,
-			       vec<data_reference_p> *datarefs)
+			       vec<data_reference_p> *datarefs,
+			       vec<int> *dataref_groups, int group_id)
 {
   /* We can ignore clobbers for dataref analysis - they are removed during
      loop vectorization and BB vectorization checks dependences with a
@@ -4197,6 +4205,8 @@ vect_find_stmt_data_reference (loop_p loop, gimple *stmt,
 		      newdr->aux = (void *) (-1 - tree_to_uhwi (arg2));
 		      free_data_ref (dr);
 		      datarefs->safe_push (newdr);
+		      if (dataref_groups)
+			dataref_groups->safe_push (group_id);
 		      return opt_result::success ();
 		    }
 		}
@@ -4206,6 +4216,8 @@ vect_find_stmt_data_reference (loop_p loop, gimple *stmt,
     }
 
   datarefs->safe_push (dr);
+  if (dataref_groups)
+    dataref_groups->safe_push (group_id);
   return opt_result::success ();
 }
 
diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c
index 08c9f119626..348a7b2e767 100644
--- a/gcc/tree-vect-loop.c
+++ b/gcc/tree-vect-loop.c
@@ -1788,7 +1788,8 @@ vect_get_datarefs_in_loop (loop_p loop, basic_block *bbs,
 	if (is_gimple_debug (stmt))
 	  continue;
 	++(*n_stmts);
-	opt_result res = vect_find_stmt_data_reference (loop, stmt, datarefs);
+	opt_result res = vect_find_stmt_data_reference (loop, stmt, datarefs,
+							NULL, 0);
 	if (!res)
 	  {
 	    if (is_gimple_call (stmt) && loop->safelen)
@@ -2010,7 +2011,7 @@ vect_analyze_loop_2 (loop_vec_info loop_vinfo, bool &fatal, unsigned *n_stmts)
   /* Analyze the access patterns of the data-refs in the loop (consecutive,
      complex, etc.). FORNOW: Only handle consecutive access pattern.  */
 
-  ok = vect_analyze_data_ref_accesses (loop_vinfo);
+  ok = vect_analyze_data_ref_accesses (loop_vinfo, NULL);
   if (!ok)
     {
       if (dump_enabled_p ())
diff --git a/gcc/tree-vect-slp.c b/gcc/tree-vect-slp.c
index b2792c76ad2..5d16edfbab7 100644
--- a/gcc/tree-vect-slp.c
+++ b/gcc/tree-vect-slp.c
@@ -2636,8 +2636,6 @@ _bb_vec_info::_bb_vec_info (gimple_stmt_iterator region_begin_in,
 	continue;
       add_stmt (stmt);
     }
-
-  bb->aux = this;
 }
 
 
@@ -3127,7 +3125,8 @@ vect_slp_check_for_constructors (bb_vec_info bb_vinfo)
    region.  */
 
 static bool
-vect_slp_analyze_bb_1 (bb_vec_info bb_vinfo, int n_stmts, bool &fatal)
+vect_slp_analyze_bb_1 (bb_vec_info bb_vinfo, int n_stmts, bool &fatal,
+		       vec<int> *dataref_groups)
 {
   DUMP_VECT_SCOPE ("vect_slp_analyze_bb");
 
@@ -3158,7 +3157,7 @@ vect_slp_analyze_bb_1 (bb_vec_info bb_vinfo, int n_stmts, bool &fatal)
       return false;
     }
 
-  if (!vect_analyze_data_ref_accesses (bb_vinfo))
+  if (!vect_analyze_data_ref_accesses (bb_vinfo, dataref_groups))
     {
      if (dump_enabled_p ())
        dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
@@ -3267,10 +3266,11 @@ vect_slp_analyze_bb_1 (bb_vec_info bb_vinfo, int n_stmts, bool &fatal)
    given by DATAREFS.  */
 
 static bool
-vect_slp_bb_region (gimple_stmt_iterator region_begin,
-		    gimple_stmt_iterator region_end,
-		    vec<data_reference_p> datarefs,
-		    unsigned int n_stmts)
+vect_slp_region (gimple_stmt_iterator region_begin,
+		 gimple_stmt_iterator region_end,
+		 vec<data_reference_p> datarefs,
+		 vec<int> *dataref_groups,
+		 unsigned int n_stmts)
 {
   bb_vec_info bb_vinfo;
   auto_vector_modes vector_modes;
@@ -3297,7 +3297,7 @@ vect_slp_bb_region (gimple_stmt_iterator region_begin,
 	bb_vinfo->shared->check_datarefs ();
       bb_vinfo->vector_mode = next_vector_mode;
 
-      if (vect_slp_analyze_bb_1 (bb_vinfo, n_stmts, fatal)
+      if (vect_slp_analyze_bb_1 (bb_vinfo, n_stmts, fatal, dataref_groups)
 	  && dbg_cnt (vect_slp))
 	{
 	  if (dump_enabled_p ())
@@ -3417,7 +3417,7 @@ vect_slp_bb (basic_block bb)
 	  if (gimple_location (stmt) != UNKNOWN_LOCATION)
 	    vect_location = stmt;
 
-	  if (!vect_find_stmt_data_reference (NULL, stmt, &datarefs))
+	  if (!vect_find_stmt_data_reference (NULL, stmt, &datarefs, NULL, 0))
 	    break;
 	}
       if (gsi_end_p (region_begin))
@@ -3439,7 +3439,7 @@ vect_slp_bb (basic_block bb)
 			     "not vectorized: too many instructions in "
 			     "basic block.\n");
 	}
-      else if (vect_slp_bb_region (region_begin, region_end, datarefs, insns))
+      else if (vect_slp_region (region_begin, region_end, datarefs, NULL, insns))
 	any_vectorized = true;
 
       if (gsi_end_p (region_end))
@@ -3452,6 +3452,62 @@ vect_slp_bb (basic_block bb)
   return any_vectorized;
 }
 
+bool
+vect_slp_function ()
+{
+  basic_block bb;
+  vec_info_shared shared;
+  vec<data_reference_p> datarefs = vNULL;
+  vec<int> dataref_groups = vNULL;
+  bool any_vectorized = false;
+  int insns = 0;
+  gimple_stmt_iterator region_begin
+    = gsi_after_labels (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb);
+  // TODO
+  while (gsi_stmt (region_begin) == NULL)
+    {
+      basic_block next_bb = region_begin.bb->next_bb;
+      if (next_bb == NULL)
+	return false;
+      region_begin = gsi_after_labels (next_bb);
+    }
+
+  gimple_stmt_iterator region_end
+    = gsi_last_bb (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
+  if (!gsi_end_p (region_end))
+    gsi_next (&region_end);
+  int current_group = 0;
+
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      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++;
+
+	  if (gimple_location (stmt) != UNKNOWN_LOCATION)
+	    vect_location = stmt;
+
+	  if (!vect_find_stmt_data_reference (NULL, stmt, &datarefs,
+					      &dataref_groups, current_group))
+	    ++current_group;
+	}
+
+      ++current_group;
+    }
+
+  if (vect_slp_region (region_begin, region_end, datarefs, &dataref_groups,
+		       insns))
+    any_vectorized = true;
+
+  return any_vectorized;
+}
+
+
 
 /* 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
@@ -3620,7 +3676,7 @@ vect_create_constant_vectors (vec_info *vinfo, slp_tree op_node)
   constant_p = true;
   tree_vector_builder elts (vector_type, nunits, 1);
   elts.quick_grow (nunits);
-  stmt_vec_info insert_after = NULL;
+  gimple_stmt_iterator insert_before = gsi_none ();
   for (j = 0; j < number_of_copies; j++)
     {
       tree op;
@@ -3684,15 +3740,56 @@ vect_create_constant_vectors (vec_info *vinfo, slp_tree op_node)
 	     when a def is inside the analyzed region since we cannot
 	     simply insert at the BB start in this case.  */
 	  stmt_vec_info opdef;
-	  if (TREE_CODE (orig_op) == SSA_NAME
-	      && !SSA_NAME_IS_DEFAULT_DEF (orig_op)
-	      && is_a <bb_vec_info> (vinfo)
-	      && (opdef = vinfo->lookup_def (orig_op)))
+	  if (is_a <bb_vec_info> (vinfo))
 	    {
-	      if (!insert_after)
-		insert_after = opdef;
-	      else
-		insert_after = get_later_stmt (insert_after, opdef);
+	      gimple_stmt_iterator to_insert = gsi_none ();
+	      if (TREE_CODE (orig_op) == SSA_NAME)
+		{
+		  if (SSA_NAME_IS_DEFAULT_DEF (orig_op))
+		    to_insert = gsi_after_labels (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb);
+		  else if ((opdef = vinfo->lookup_def (orig_op)))
+		    {
+		      to_insert = gsi_for_stmt (opdef->stmt);
+		      gsi_next (&to_insert);
+		    }
+
+		  else
+		    {
+		      gimple *def = SSA_NAME_DEF_STMT (orig_op);
+		      if (is_a<gphi *> (def))
+			to_insert = gsi_after_labels (gimple_bb (def));
+		      else
+			{
+			  to_insert = gsi_for_stmt (def);
+			  gsi_next (&to_insert);
+			}
+		    }
+		}
+	      else if (CONSTANT_CLASS_P (orig_op)
+		       || TREE_CODE (orig_op) == ADDR_EXPR)
+		to_insert = gsi_after_labels (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb);
+
+	      if (gsi_bb (to_insert))
+		{
+		  if (gsi_bb (insert_before))
+		    {
+		      bool dom0 = vect_stmt_dominates_stmt_p (gsi_stmt (insert_before),
+							      gsi_bb (insert_before),
+							      gsi_stmt (to_insert),
+							      gsi_bb (to_insert));
+		      bool dom1 = vect_stmt_dominates_stmt_p (gsi_stmt (to_insert),
+							      gsi_bb (to_insert),
+							      gsi_stmt (insert_before),
+							      gsi_bb (insert_before));
+		      if (dom0 == dom1)
+			; // TODO
+		      else if (dom0)
+			insert_before = to_insert;
+
+		    }
+		  else
+		    insert_before = to_insert;
+		}
 	    }
 
           if (number_of_places_left_in_vector == 0)
@@ -3710,14 +3807,9 @@ vect_create_constant_vectors (vec_info *vinfo, slp_tree op_node)
 		  vec_cst = permute_results[number_of_vectors - j - 1];
 		}
 	      tree init;
-	      if (insert_after)
-		{
-		  gimple_stmt_iterator gsi = gsi_for_stmt (insert_after->stmt);
-		  /* vect_init_vector inserts before.  */
-		  gsi_next (&gsi);
-		  init = vect_init_vector (vinfo, NULL, vec_cst,
-					   vector_type, &gsi);
-		}
+	      if (gsi_bb (insert_before))
+		init = vect_init_vector (vinfo, NULL, vec_cst,
+					 vector_type, &insert_before);
 	      else
 		init = vect_init_vector (vinfo, NULL, vec_cst,
 					 vector_type, NULL);
@@ -3729,7 +3821,7 @@ vect_create_constant_vectors (vec_info *vinfo, slp_tree op_node)
 		  ctor_seq = NULL;
 		}
 	      voprnds.quick_push (init);
-	      insert_after = NULL;
+	      insert_before = gsi_none ();
               number_of_places_left_in_vector = nunits;
 	      constant_p = true;
 	      elts.new_vector (vector_type, nunits, 1);
diff --git a/gcc/tree-vect-stmts.c b/gcc/tree-vect-stmts.c
index edd28534cb0..815c73042c6 100644
--- a/gcc/tree-vect-stmts.c
+++ b/gcc/tree-vect-stmts.c
@@ -1334,8 +1334,9 @@ vect_init_vector_1 (vec_info *vinfo, stmt_vec_info stmt_vinfo, gimple *new_stmt,
       else
        {
           bb_vec_info bb_vinfo = dyn_cast <bb_vec_info> (vinfo);
-	  gimple_stmt_iterator gsi_region_begin = bb_vinfo->region_begin;
-	  gsi_insert_before (&gsi_region_begin, new_stmt, GSI_SAME_STMT);
+	  gimple_stmt_iterator gsi
+	    = gsi_after_labels (gsi_bb (bb_vinfo->region_begin));
+	  gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
        }
     }
 
diff --git a/gcc/tree-vectorizer.c b/gcc/tree-vectorizer.c
index 78d9da689c8..7fd5cdf7a8d 100644
--- a/gcc/tree-vectorizer.c
+++ b/gcc/tree-vectorizer.c
@@ -717,7 +717,16 @@ bool
 vect_stmt_dominates_stmt_p (gimple *s1, gimple *s2)
 {
   basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
+  return vect_stmt_dominates_stmt_p (s1, bb1, s2, bb2);
+}
+
+/* Returns true if S1 dominates S2.  Any of S1 and S2 can be null
+  and then basic blocks BB1 and BB2 are compared.  */
 
+bool
+vect_stmt_dominates_stmt_p (gimple *s1, basic_block bb1,
+			    gimple *s2, basic_block bb2)
+{
   /* If bb1 is NULL, it should be a GIMPLE_NOP def stmt of an (D)
      SSA_NAME.  Assume it lives at the beginning of function and
      thus dominates everything.  */
@@ -1379,12 +1388,17 @@ pass_slp_vectorize::execute (function *fun)
 	}
     }
 
-  FOR_EACH_BB_FN (bb, fun)
+  if (vect_slp_function ())
     {
+      // TODO: change to function vectorized
+      if (dump_enabled_p ())
+	dump_printf_loc (MSG_NOTE, vect_location, "basic block vectorized\n");
+    }
+  else
+    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 (!in_loop_pipeline)
     {
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index e4d132493ca..bb18e7b21ac 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -802,7 +802,17 @@ public:
     const const_iterator &
     operator++ ()
     {
-      gsi_next (&gsi); return *this;
+      basic_block bb = gimple_bb (gsi_stmt (gsi));
+      gsi_next (&gsi);
+      while (gsi_end_p (gsi))
+	{
+	  bb = bb->next_bb;
+	  if (bb == NULL)
+	    break;
+	  gsi = gsi_after_labels (bb);
+	}
+
+      return *this;
     }
 
     gimple *operator* () const { return gsi_stmt (gsi); }
@@ -831,7 +841,12 @@ public:
     const const_reverse_iterator &
     operator++ ()
     {
-      gsi_prev (&gsi); return *this;
+      basic_block bb = gimple_bb (gsi_stmt (gsi));
+      gsi_prev (&gsi);
+      while (gsi_end_p (gsi))
+	gsi = gsi_after_labels (bb->prev_bb);
+
+      return *this;
     }
 
     gimple *operator* () const { return gsi_stmt (gsi); }
@@ -1893,14 +1908,15 @@ extern opt_result vect_analyze_data_refs_alignment (loop_vec_info);
 extern opt_result vect_verify_datarefs_alignment (loop_vec_info);
 extern bool vect_slp_analyze_and_verify_instance_alignment (vec_info *,
 							    slp_instance);
-extern opt_result vect_analyze_data_ref_accesses (vec_info *);
+extern opt_result vect_analyze_data_ref_accesses (vec_info *, vec<int> *);
 extern opt_result vect_prune_runtime_alias_test_list (loop_vec_info);
 extern bool vect_gather_scatter_fn_p (vec_info *, bool, bool, tree, tree,
 				      tree, int, internal_fn *, tree *);
 extern bool vect_check_gather_scatter (stmt_vec_info, loop_vec_info,
 				       gather_scatter_info *);
 extern opt_result vect_find_stmt_data_reference (loop_p, gimple *,
-						 vec<data_reference_p> *);
+						 vec<data_reference_p> *,
+						 vec<int> *, int);
 extern opt_result vect_analyze_data_refs (vec_info *, poly_uint64 *, bool *);
 extern void vect_record_base_alignments (vec_info *);
 extern tree vect_create_data_ref_ptr (vec_info *,
@@ -2000,6 +2016,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);
@@ -2021,5 +2038,6 @@ unsigned vectorize_loops (void);
 void vect_free_loop_info_assumptions (class loop *);
 gimple *vect_loop_vectorized_call (class loop *, gcond **cond = NULL);
 bool vect_stmt_dominates_stmt_p (gimple *, gimple *);
+bool vect_stmt_dominates_stmt_p (gimple *, basic_block, gimple *, basic_block);
 
 #endif  /* GCC_TREE_VECTORIZER_H  */