SLP vectorize multiple BBs at once

This work from Martin Liska was motivated by gcc.dg/vect/bb-slp-22.c
which shows how poorly we currently BB vectorize code like

  a0 = in[0] + 23;
  a1 = in[1] + 142;
  a2 = in[2] + 2;
  a3 = in[3] + 31;

  if (x > y)
    {
      b[0] = a0;
      b[1] = a1;
      b[2] = a2;
      b[3] = a3;
    }
  else
    {
      out[0] = a0 * (x + 1);
      out[1] = a1 * (y + 1);
      out[2] = a2 * (x + 1);
      out[3] = a3 * (y + 1);
    }

namely by vectorizing the stores but not the common load (and add)
they are feeded with.

Thus with the following patch we change the BB vectorizer from
operating on a single basic-block at a time to consider somewhat
larger regions (but not the whole function yet because of issues
with vector size iteration).

I took the opportunity to remove the fancy region iterations again
now that we operate on BB granularity and in the end need to visit
PHI nodes as well.

2020-10-08  Martin Liska  <mliska@suse.cz>
	    Richard Biener  <rguenther@suse.de>

	* tree-vectorizer.h (_bb_vec_info::const_iterator): Remove.
	(_bb_vec_info::const_reverse_iterator): Likewise.
	(_bb_vec_info::region_stmts): Likewise.
	(_bb_vec_info::reverse_region_stmts): Likewise.
	(_bb_vec_info::_bb_vec_info): Adjust.
	(_bb_vec_info::bb): Remove.
	(_bb_vec_info::region_begin): Remove.
	(_bb_vec_info::region_end): Remove.
	(_bb_vec_info::bbs): New vector of BBs.
	(vect_slp_function): Declare.
	* tree-vect-patterns.c (vect_determine_precisions): Use
	regular stmt iteration.
	(vect_pattern_recog): Likewise.
	* tree-vect-slp.c: Include cfganal.h, tree-eh.h and tree-cfg.h.
	(vect_build_slp_tree_1): Properly refuse to vectorize
	volatile and throwing stmts.
	(vect_build_slp_tree_2): Pass group-size down to
	get_vectype_for_scalar_type.
	(_bb_vec_info::_bb_vec_info): Use regular stmt iteration,
	adjust for changed region specification.
	(_bb_vec_info::~_bb_vec_info): Likewise.
	(vect_slp_check_for_constructors): Likewise.
	(vect_slp_region): Likewise.
	(vect_slp_bbs): New worker operating on a vector of BBs.
	(vect_slp_bb): Wrap it.
	(vect_slp_function): New function splitting the function
	into multi-BB regions.
	(vect_create_constant_vectors): Handle the case of inserting
	after a throwing def.
	(vect_schedule_slp_instance): Adjust.
	* tree-vectorizer.c (vec_info::remove_stmt): Simplify again.
	(vec_info::insert_seq_on_entry): Adjust.
	(pass_slp_vectorize::execute): Also init PHIs.  Call
	vect_slp_function.

	* gcc.dg/vect/bb-slp-22.c: Adjust.
	* gfortran.dg/pr68627.f: Likewise.

1 files changed, 7 insertions, 86 deletions

diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 37b0915..38daa05 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -827,94 +827,14 @@ loop_vec_info_for_loop (class loop *loop)
 typedef class _bb_vec_info : public vec_info
 {
 public:
-
-  /* GIMPLE statement iterator going from region_begin to region_end.  */
-
-  struct const_iterator
-  {
-    const_iterator (gimple_stmt_iterator _gsi) : gsi (_gsi) {}
-
-    const const_iterator &
-    operator++ ()
-    {
-      gsi_next (&gsi); return *this;
-    }
-
-    gimple *operator* () const { return gsi_stmt (gsi); }
-
-    bool
-    operator== (const const_iterator &other) const
-    {
-      return gsi_stmt (gsi) == gsi_stmt (other.gsi);
-    }
-
-    bool
-    operator!= (const const_iterator &other) const
-    {
-      return !(*this == other);
-    }
-
-    gimple_stmt_iterator gsi;
-  };
-
-  /* GIMPLE statement iterator going from region_end to region_begin.  */
-
-  struct const_reverse_iterator
-  {
-    const_reverse_iterator (gimple_stmt_iterator _gsi) : gsi (_gsi) {}
-
-    const const_reverse_iterator &
-    operator++ ()
-    {
-      gsi_prev (&gsi); return *this;
-    }
-
-    gimple *operator* () const { return gsi_stmt (gsi); }
-
-    bool
-    operator== (const const_reverse_iterator &other) const
-    {
-      return gsi_stmt (gsi) == gsi_stmt (other.gsi);
-    }
-
-    bool
-    operator!= (const const_reverse_iterator &other) const
-    {
-      return !(*this == other);
-    }
-
-    gimple_stmt_iterator gsi;
-  };
-
-  _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 ();
 
-  /* Returns iterator_range for range-based loop.  */
-
-  iterator_range<const_iterator>
-  region_stmts ()
-  {
-    return iterator_range<const_iterator> (region_begin, region_end);
-  }
-
-  /* Returns iterator_range for range-based loop in a reverse order.  */
-
-  iterator_range<const_reverse_iterator>
-  reverse_region_stmts ()
-  {
-    const_reverse_iterator begin = region_end;
-    if (*begin == NULL)
-      begin = const_reverse_iterator (gsi_last_bb (gsi_bb (region_end)));
-    else
-      ++begin;
-
-    const_reverse_iterator end = region_begin;
-    return iterator_range<const_reverse_iterator> (begin, ++end);
-  }
-
-  basic_block bb;
-  gimple_stmt_iterator region_begin;
-  gimple_stmt_iterator region_end;
+  /* The region we are operating on.  bbs[0] is the entry, excluding
+     its PHI nodes.  In the future we might want to track an explicit
+     entry edge to cover bbs[0] PHI nodes and have a region entry
+     insert location.  */
+  vec<basic_block> bbs;
 } *bb_vec_info;
 
 #define BB_VINFO_BB(B)               (B)->bb
@@ -2035,6 +1955,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 (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);