Record leader nodes in the SLP graph (PR92516)

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Record leader nodes in the SLP graph (PR92516)

Richard Sandiford-9
If stmt analysis failed for an SLP node, r278246 tried building the
node from scalars instead.  By that point we've already processed child
nodes (usually successfully) and might have made some of them the lead
nodes for their stmt list.  This is why we couldn't free the child nodes
when deciding to build from scalars:

  /* Don't remove and free the child nodes here, since they could be
     referenced by other structures.  The analysis and scheduling phases
     (need to) ignore child nodes of anything that isn't vect_internal_def.  */

The problem in this PR is that we (correctly) don't process the unused
child nodes again during the scheduling phase, which means that those
nodes won't become the leader again.  So some other node with same stmts
becomes the leader instead.  However, any internal-def child nodes of
this new leader won't have been processed during the analysis phase,
because we also (correctly) skip child nodes of non-leader nodes.

We talked on IRC about fixing this by sharing nodes between SLP
instances, so that it becomes a "proper" graph.  But that seems
like it could throw up some problems too, so I wanted to fix the
PR in a less invasive way first.

This patch therefore records the leader nodes during the analysis
phase and reuses that choice during scheduling.  When scheduling
a non-leader node, we first try to schedule the leader node and
then reuse its vector stmts.  At the moment, doing this means we
need to know the leader node's SLP instance, so the patch records
that in the SLP node too.

While there, I noticed that the two-operation handling returned
early without restoring the original def types.  That's really
an independent bug fix.

Tested on aarch64-linux-gnu and x86_64-linux-gnu.  OK to install?

Richard


2019-11-16  Richard Sandiford  <[hidden email]>

gcc/
        PR tree-optimization/92516
        * tree-vectorizer.h (_slp_tree::leader): New member variable.
        (_slp_tree::leader_instance): Likewise.
        * tree-vect-slp.c (vect_create_new_slp_node): Initialize them.
        (vect_slp_analyze_node_operations): When deferring to an existing
        leader, record that leader in the SLP node.
        (vect_slp_analyze_operations): When committing to keeping an
        SLP instance, record that leaders in it are themselves leaderless.
        Also record the SLP instance we should use to vectorize them.
        (vect_schedule_slp_instance): Remove the bst_map parameter.
        If the node has a leader, vectorize that first and reuse
        its vector stmts.  Restore stmt def types for two-operation SLP.
        (vect_schedule_slp): Update call accordingly, removing the bst_map.

gcc/testsuite/
        * g++.dg/vect/slp-pr92516.cc: New test.

Index: gcc/tree-vectorizer.h
===================================================================
--- gcc/tree-vectorizer.h 2019-11-14 15:14:29.239572543 +0000
+++ gcc/tree-vectorizer.h 2019-11-16 08:22:50.620257693 +0000
@@ -128,6 +128,11 @@ struct _slp_tree {
   vec<unsigned> load_permutation;
   /* Vectorized stmt/s.  */
   vec<stmt_vec_info> vec_stmts;
+  /* If non-null, the leader node that provides the vectorized stmts.  */
+  _slp_tree *leader;
+  /* If the node is a leader node, this is the slp_instance to use when
+     vectorizing it.  */
+  class _slp_instance *leader_instance;
   /* Number of vector stmts that are created to replace the group of scalar
      stmts. It is calculated during the transformation phase as the number of
      scalar elements in one scalar iteration (GROUP_SIZE) multiplied by VF
Index: gcc/tree-vect-slp.c
===================================================================
--- gcc/tree-vect-slp.c 2019-11-14 15:33:43.503740636 +0000
+++ gcc/tree-vect-slp.c 2019-11-16 08:22:50.612257749 +0000
@@ -129,6 +129,8 @@ vect_create_new_slp_node (vec<stmt_vec_i
   SLP_TREE_LOAD_PERMUTATION (node) = vNULL;
   SLP_TREE_TWO_OPERATORS (node) = false;
   SLP_TREE_DEF_TYPE (node) = vect_internal_def;
+  node->leader = NULL;
+  node->leader_instance = NULL;
   node->refcnt = 1;
   node->max_nunits = 1;
 
@@ -155,6 +157,8 @@ vect_create_new_slp_node (vec<tree> ops)
   SLP_TREE_LOAD_PERMUTATION (node) = vNULL;
   SLP_TREE_TWO_OPERATORS (node) = false;
   SLP_TREE_DEF_TYPE (node) = vect_external_def;
+  node->leader = NULL;
+  node->leader_instance = NULL;
   node->refcnt = 1;
   node->max_nunits = 1;
 
@@ -2764,6 +2768,7 @@ vect_slp_analyze_node_operations (vec_in
   if ((leader = visited->get (SLP_TREE_SCALAR_STMTS (node)))
       || (leader = lvisited->get (SLP_TREE_SCALAR_STMTS (node))))
     {
+      node->leader = *leader;
       SLP_TREE_NUMBER_OF_VEC_STMTS (node)
  = SLP_TREE_NUMBER_OF_VEC_STMTS (*leader);
       /* Cope with cases in which we made a late decision to build the
@@ -2878,7 +2883,11 @@ vect_slp_analyze_operations (vec_info *v
  {
   for (scalar_stmts_to_slp_tree_map_t::iterator x = lvisited.begin();
        x != lvisited.end(); ++x)
-    visited->put ((*x).first.copy (), (*x).second);
+    {
+      visited->put ((*x).first.copy (), (*x).second);
+      (*x).second->leader = NULL;
+      (*x).second->leader_instance = instance;
+    }
   i++;
 
   add_stmt_costs (vinfo->target_cost_data, &cost_vec);
@@ -4046,8 +4055,7 @@ vect_transform_slp_perm_load (slp_tree n
 /* Vectorize SLP instance tree in postorder.  */
 
 static void
-vect_schedule_slp_instance (slp_tree node, slp_instance instance,
-    scalar_stmts_to_slp_tree_map_t *bst_map)
+vect_schedule_slp_instance (slp_tree node, slp_instance instance)
 {
   gimple_stmt_iterator si;
   stmt_vec_info stmt_info;
@@ -4066,15 +4074,18 @@ vect_schedule_slp_instance (slp_tree nod
 
   /* See if we have already vectorized the same set of stmts and reuse their
      vectorized stmts across instances.  */
-  if (slp_tree *leader = bst_map->get (SLP_TREE_SCALAR_STMTS (node)))
+  if (node->leader)
     {
-      SLP_TREE_VEC_STMTS (node).safe_splice (SLP_TREE_VEC_STMTS (*leader));
+      gcc_assert (!node->leader->leader);
+      vect_schedule_slp_instance (node->leader, node->leader->leader_instance);
+      SLP_TREE_VEC_STMTS (node).safe_splice
+ (SLP_TREE_VEC_STMTS (node->leader));
       return;
     }
+  gcc_assert (instance == node->leader_instance);
 
-  bst_map->put (SLP_TREE_SCALAR_STMTS (node).copy (), node);
   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
-    vect_schedule_slp_instance (child, instance, bst_map);
+    vect_schedule_slp_instance (child, instance);
 
   /* Push SLP node def-type to stmts.  */
   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
@@ -4107,6 +4118,7 @@ vect_schedule_slp_instance (slp_tree nod
 
   /* Handle two-operation SLP nodes by vectorizing the group with
      both operations and then performing a merge.  */
+  bool done_p = false;
   if (SLP_TREE_TWO_OPERATORS (node))
     {
       gassign *stmt = as_a <gassign *> (stmt_info->stmt);
@@ -4177,10 +4189,11 @@ vect_schedule_slp_instance (slp_tree nod
     }
   v0.release ();
   v1.release ();
-  return;
+  done_p = true;
  }
     }
-  vect_transform_stmt (stmt_info, &si, node, instance);
+  if (!done_p)
+    vect_transform_stmt (stmt_info, &si, node, instance);
 
   /* Restore stmt def-types.  */
   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
@@ -4294,14 +4307,12 @@ vect_schedule_slp (vec_info *vinfo)
   slp_instance instance;
   unsigned int i;
 
-  scalar_stmts_to_slp_tree_map_t *bst_map
-    = new scalar_stmts_to_slp_tree_map_t ();
   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 (node, instance, bst_map);
+      vect_schedule_slp_instance (node, instance);
 
       if (SLP_INSTANCE_ROOT_STMT (instance))
  vectorize_slp_instance_root_stmt (node, instance);
@@ -4310,7 +4321,6 @@ vect_schedule_slp (vec_info *vinfo)
  dump_printf_loc (MSG_NOTE, vect_location,
                          "vectorizing stmts using SLP.\n");
     }
-  delete bst_map;
 
   FOR_EACH_VEC_ELT (slp_instances, i, instance)
     {
Index: gcc/testsuite/g++.dg/vect/slp-pr92516.cc
===================================================================
--- /dev/null 2019-09-17 11:41:18.176664108 +0100
+++ gcc/testsuite/g++.dg/vect/slp-pr92516.cc 2019-11-16 08:22:50.612257749 +0000
@@ -0,0 +1,43 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target c++14 } */
+
+class a {
+public:
+  typedef int b;
+  operator b();
+};
+class c {
+public:
+  constexpr int m_fn1() const;
+  constexpr int d() const;
+  int e;
+  int f;
+};
+constexpr int c::m_fn1() const { return e; }
+constexpr int c::d() const { return f; }
+class g {
+public:
+  g();
+  constexpr void i(const c &) noexcept;
+  int j;
+  int k;
+  int l;
+  int m;
+};
+constexpr void g::i(const c &n) noexcept {
+  int v = l - j, h = m - k;
+  j = n.m_fn1() - v / 2;
+  k = n.d() - h / 2;
+  l = j + v;
+  m = k + h;
+}
+class o {
+  void m_fn4() const;
+  a p;
+} r;
+void o::m_fn4() const {
+  g q;
+  c t;
+  q.i(t);
+  r.p || 0;
+}
Reply | Threaded
Open this post in threaded view
|

Re: Record leader nodes in the SLP graph (PR92516)

Richard Biener
On Sat, 16 Nov 2019, Richard Sandiford wrote:

> If stmt analysis failed for an SLP node, r278246 tried building the
> node from scalars instead.  By that point we've already processed child
> nodes (usually successfully) and might have made some of them the lead
> nodes for their stmt list.  This is why we couldn't free the child nodes
> when deciding to build from scalars:
>
>   /* Don't remove and free the child nodes here, since they could be
>      referenced by other structures.  The analysis and scheduling phases
>      (need to) ignore child nodes of anything that isn't vect_internal_def.  */
>
> The problem in this PR is that we (correctly) don't process the unused
> child nodes again during the scheduling phase, which means that those
> nodes won't become the leader again.  So some other node with same stmts
> becomes the leader instead.  However, any internal-def child nodes of
> this new leader won't have been processed during the analysis phase,
> because we also (correctly) skip child nodes of non-leader nodes.
>
> We talked on IRC about fixing this by sharing nodes between SLP
> instances, so that it becomes a "proper" graph.  But that seems
> like it could throw up some problems too, so I wanted to fix the
> PR in a less invasive way first.
>
> This patch therefore records the leader nodes during the analysis
> phase and reuses that choice during scheduling.  When scheduling
> a non-leader node, we first try to schedule the leader node and
> then reuse its vector stmts.  At the moment, doing this means we
> need to know the leader node's SLP instance, so the patch records
> that in the SLP node too.
>
> While there, I noticed that the two-operation handling returned
> early without restoring the original def types.  That's really
> an independent bug fix.

Can you split that out please?

For the rest I prefer the following which I am now fully testing
on x86_64-unknown-linux-gnu (vect.exp testing went fine).  As
discussed on IRC this makes the SLP graph nodes shared between
SLP instances (which it has in fact been, just "virtual" via
all the leader computations).  So SLP instances are now just
the collection of entries into the directed SLP graph.

I'm also throwing this on a SPEC build test.

Richard.

2019-11-18  Richard Biener  <[hidden email]>

        PR tree-optimization/92516
        * tree-vect-slp.c (vect_analyze_slp_instance): Add bst_map
        argument, hoist bst_map creation/destruction to ...
        (vect_analyze_slp): ... here, forming a true graph with
        SLP instances being the entries.
        (vect_detect_hybrid_slp_stmts): Remove wrapper.
        (vect_detect_hybrid_slp): Use one visited set for all
        graph entries.
        (vect_slp_analyze_node_operations): Simplify visited/lvisited
        to hash-sets of slp_tree.
        (vect_slp_analyze_operations): Likewise.
        (vect_bb_slp_scalar_cost): Remove wrapper.
        (vect_bb_vectorization_profitable_p): Use one visited set for
        all graph entries.
        (vect_schedule_slp_instance): Elide bst_map use.
        (vect_schedule_slp): Likewise.

        * g++.dg/vect/slp-pr92516.cc: New testcase.

Index: gcc/tree-vect-slp.c
===================================================================
--- gcc/tree-vect-slp.c (revision 278389)
+++ gcc/tree-vect-slp.c (working copy)
@@ -2087,6 +2087,7 @@ calculate_unrolling_factor (poly_uint64
 
 static bool
 vect_analyze_slp_instance (vec_info *vinfo,
+   scalar_stmts_to_slp_tree_map_t *bst_map,
    stmt_vec_info stmt_info, unsigned max_tree_size)
 {
   slp_instance new_instance;
@@ -2194,19 +2195,11 @@ vect_analyze_slp_instance (vec_info *vin
   /* Build the tree for the SLP instance.  */
   bool *matches = XALLOCAVEC (bool, group_size);
   unsigned npermutes = 0;
-  scalar_stmts_to_slp_tree_map_t *bst_map
-    = new scalar_stmts_to_slp_tree_map_t ();
   poly_uint64 max_nunits = nunits;
   unsigned tree_size = 0;
   node = vect_build_slp_tree (vinfo, scalar_stmts, group_size,
       &max_nunits, matches, &npermutes,
       &tree_size, bst_map);
-  /* The map keeps a reference on SLP nodes built, release that.  */
-  for (scalar_stmts_to_slp_tree_map_t::iterator it = bst_map->begin ();
-       it != bst_map->end (); ++it)
-    if ((*it).second)
-      vect_free_slp_tree ((*it).second, false);
-  delete bst_map;
   if (node != NULL)
     {
       /* If this is a reduction chain with a conversion in front
@@ -2394,7 +2387,7 @@ vect_analyze_slp_instance (vec_info *vin
 
   stmt_vec_info rest = vect_split_slp_store_group (stmt_info,
    group1_size);
-  bool res = vect_analyze_slp_instance (vinfo, stmt_info,
+  bool res = vect_analyze_slp_instance (vinfo, bst_map, stmt_info,
  max_tree_size);
   /* If the first non-match was in the middle of a vector,
      skip the rest of that vector.  */
@@ -2405,7 +2398,8 @@ vect_analyze_slp_instance (vec_info *vin
  rest = vect_split_slp_store_group (rest, const_nunits);
     }
   if (i < group_size)
-    res |= vect_analyze_slp_instance (vinfo, rest, max_tree_size);
+    res |= vect_analyze_slp_instance (vinfo, bst_map,
+      rest, max_tree_size);
   return res;
  }
       /* Even though the first vector did not all match, we might be able to SLP
@@ -2427,9 +2421,12 @@ vect_analyze_slp (vec_info *vinfo, unsig
 
   DUMP_VECT_SCOPE ("vect_analyze_slp");
 
+  scalar_stmts_to_slp_tree_map_t *bst_map
+    = new scalar_stmts_to_slp_tree_map_t ();
+
   /* Find SLP sequences starting from groups of grouped stores.  */
   FOR_EACH_VEC_ELT (vinfo->grouped_stores, i, first_element)
-    vect_analyze_slp_instance (vinfo, first_element, max_tree_size);
+    vect_analyze_slp_instance (vinfo, bst_map, first_element, max_tree_size);
 
   if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo))
     {
@@ -2437,7 +2434,7 @@ vect_analyze_slp (vec_info *vinfo, unsig
  {
   /* Find SLP sequences starting from reduction chains.  */
   FOR_EACH_VEC_ELT (loop_vinfo->reduction_chains, i, first_element)
-    if (! vect_analyze_slp_instance (vinfo, first_element,
+    if (! vect_analyze_slp_instance (vinfo, bst_map, first_element,
      max_tree_size))
       {
  /* Dissolve reduction chain group.  */
@@ -2459,10 +2456,17 @@ vect_analyze_slp (vec_info *vinfo, unsig
 
       /* Find SLP sequences starting from groups of reductions.  */
       if (loop_vinfo->reductions.length () > 1)
- vect_analyze_slp_instance (vinfo, loop_vinfo->reductions[0],
+ vect_analyze_slp_instance (vinfo, bst_map, loop_vinfo->reductions[0],
    max_tree_size);
     }
 
+  /* The map keeps a reference on SLP nodes built, release that.  */
+  for (scalar_stmts_to_slp_tree_map_t::iterator it = bst_map->begin ();
+       it != bst_map->end (); ++it)
+    if ((*it).second)
+      vect_free_slp_tree ((*it).second, false);
+  delete bst_map;
+
   return opt_result::success ();
 }
 
@@ -2589,13 +2593,6 @@ vect_detect_hybrid_slp_stmts (slp_tree n
  vect_detect_hybrid_slp_stmts (child, i, stype, visited);
 }
 
-static void
-vect_detect_hybrid_slp_stmts (slp_tree node, unsigned i, slp_vect_type stype)
-{
-  hash_map<slp_tree, unsigned> visited;
-  vect_detect_hybrid_slp_stmts (node, i, stype, visited);
-}
-
 /* Helpers for vect_detect_hybrid_slp walking pattern stmt uses.  */
 
 static tree
@@ -2678,11 +2675,12 @@ vect_detect_hybrid_slp (loop_vec_info lo
   /* Then walk the SLP instance trees marking stmts with uses in
      non-SLP stmts as hybrid, also propagating hybrid down the
      SLP tree, collecting the above info on-the-fly.  */
+  hash_map<slp_tree, unsigned> visited;
   FOR_EACH_VEC_ELT (slp_instances, i, instance)
     {
       for (unsigned i = 0; i < SLP_INSTANCE_GROUP_SIZE (instance); ++i)
  vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance),
-      i, pure_slp);
+      i, pure_slp, visited);
     }
 }
 
@@ -2830,8 +2828,8 @@ vect_slp_convert_to_external (vec_info *
 static bool
 vect_slp_analyze_node_operations (vec_info *vinfo, slp_tree node,
   slp_instance node_instance,
-  scalar_stmts_to_slp_tree_map_t *visited,
-  scalar_stmts_to_slp_tree_map_t *lvisited,
+  hash_set<slp_tree> &visited,
+  hash_set<slp_tree> &lvisited,
   stmt_vector_for_cost *cost_vec)
 {
   int i, j;
@@ -2841,27 +2839,13 @@ vect_slp_analyze_node_operations (vec_in
     return true;
 
   /* If we already analyzed the exact same set of scalar stmts we're done.
-     We share the generated vector stmts for those.  */
-  slp_tree *leader;
-  if ((leader = visited->get (SLP_TREE_SCALAR_STMTS (node)))
-      || (leader = lvisited->get (SLP_TREE_SCALAR_STMTS (node))))
-    {
-      SLP_TREE_NUMBER_OF_VEC_STMTS (node)
- = SLP_TREE_NUMBER_OF_VEC_STMTS (*leader);
-      /* Cope with cases in which we made a late decision to build the
- node from scalars.  */
-      if (SLP_TREE_DEF_TYPE (*leader) == vect_external_def
-  && vect_slp_convert_to_external (vinfo, node, node_instance))
- ;
-      else
- gcc_assert (SLP_TREE_DEF_TYPE (node) == SLP_TREE_DEF_TYPE (*leader));
-      return true;
-    }
-
-  /* The SLP graph is acyclic so not caching whether we failed or succeeded
+     We share the generated vector stmts for those.
+     The SLP graph is acyclic so not caching whether we failed or succeeded
      doesn't result in any issue since we throw away the lvisited set
      when we fail.  */
-  lvisited->put (SLP_TREE_SCALAR_STMTS (node).copy (), node);
+  if (visited.contains (node)
+      || lvisited.add (node))
+    return true;
 
   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
     if (!vect_slp_analyze_node_operations (vinfo, child, node_instance,
@@ -2934,16 +2918,15 @@ vect_slp_analyze_operations (vec_info *v
 
   DUMP_VECT_SCOPE ("vect_slp_analyze_operations");
 
-  scalar_stmts_to_slp_tree_map_t *visited
-    = new scalar_stmts_to_slp_tree_map_t ();
+  hash_set<slp_tree> visited;
   for (i = 0; vinfo->slp_instances.iterate (i, &instance); )
     {
-      scalar_stmts_to_slp_tree_map_t lvisited;
+      hash_set<slp_tree> lvisited;
       stmt_vector_for_cost cost_vec;
       cost_vec.create (2);
       if (!vect_slp_analyze_node_operations (vinfo,
      SLP_INSTANCE_TREE (instance),
-     instance, visited, &lvisited,
+     instance, visited, lvisited,
      &cost_vec))
         {
   slp_tree node = SLP_INSTANCE_TREE (instance);
@@ -2958,16 +2941,15 @@ vect_slp_analyze_operations (vec_info *v
  }
       else
  {
-  for (scalar_stmts_to_slp_tree_map_t::iterator x = lvisited.begin();
+  for (hash_set<slp_tree>::iterator x = lvisited.begin();
        x != lvisited.end(); ++x)
-    visited->put ((*x).first.copy (), (*x).second);
+    visited.add (*x);
   i++;
 
   add_stmt_costs (vinfo->target_cost_data, &cost_vec);
   cost_vec.release ();
  }
     }
-  delete visited;
 
   return !vinfo->slp_instances.is_empty ();
 }
@@ -3058,15 +3040,6 @@ vect_bb_slp_scalar_cost (basic_block bb,
     }
 }
 
-static void
-vect_bb_slp_scalar_cost (basic_block bb,
- slp_tree node, vec<bool, va_heap> *life,
- stmt_vector_for_cost *cost_vec)
-{
-  hash_set<slp_tree> visited;
-  vect_bb_slp_scalar_cost (bb, node, life, cost_vec, visited);
-}
-
 /* Check if vectorization of the basic block is profitable.  */
 
 static bool
@@ -3081,13 +3054,14 @@ vect_bb_vectorization_profitable_p (bb_v
   /* Calculate scalar cost.  */
   stmt_vector_for_cost scalar_costs;
   scalar_costs.create (0);
+  hash_set<slp_tree> visited;
   FOR_EACH_VEC_ELT (slp_instances, i, instance)
     {
       auto_vec<bool, 20> life;
       life.safe_grow_cleared (SLP_INSTANCE_GROUP_SIZE (instance));
       vect_bb_slp_scalar_cost (BB_VINFO_BB (bb_vinfo),
        SLP_INSTANCE_TREE (instance),
-       &life, &scalar_costs);
+       &life, &scalar_costs, visited);
     }
   void *target_cost_data = init_cost (NULL);
   add_stmt_costs (target_cost_data, &scalar_costs);
@@ -4128,8 +4102,7 @@ vect_transform_slp_perm_load (slp_tree n
 /* Vectorize SLP instance tree in postorder.  */
 
 static void
-vect_schedule_slp_instance (slp_tree node, slp_instance instance,
-    scalar_stmts_to_slp_tree_map_t *bst_map)
+vect_schedule_slp_instance (slp_tree node, slp_instance instance)
 {
   gimple_stmt_iterator si;
   stmt_vec_info stmt_info;
@@ -4146,17 +4119,8 @@ vect_schedule_slp_instance (slp_tree nod
   if (SLP_TREE_VEC_STMTS (node).exists ())
     return;
 
-  /* See if we have already vectorized the same set of stmts and reuse their
-     vectorized stmts across instances.  */
-  if (slp_tree *leader = bst_map->get (SLP_TREE_SCALAR_STMTS (node)))
-    {
-      SLP_TREE_VEC_STMTS (node).safe_splice (SLP_TREE_VEC_STMTS (*leader));
-      return;
-    }
-
-  bst_map->put (SLP_TREE_SCALAR_STMTS (node).copy (), node);
   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
-    vect_schedule_slp_instance (child, instance, bst_map);
+    vect_schedule_slp_instance (child, instance);
 
   /* Push SLP node def-type to stmts.  */
   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
@@ -4376,14 +4340,12 @@ vect_schedule_slp (vec_info *vinfo)
   slp_instance instance;
   unsigned int i;
 
-  scalar_stmts_to_slp_tree_map_t *bst_map
-    = new scalar_stmts_to_slp_tree_map_t ();
   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 (node, instance, bst_map);
+      vect_schedule_slp_instance (node, instance);
 
       if (SLP_INSTANCE_ROOT_STMT (instance))
  vectorize_slp_instance_root_stmt (node, instance);
@@ -4392,7 +4354,6 @@ vect_schedule_slp (vec_info *vinfo)
  dump_printf_loc (MSG_NOTE, vect_location,
                          "vectorizing stmts using SLP.\n");
     }
-  delete bst_map;
 
   FOR_EACH_VEC_ELT (slp_instances, i, instance)
     {
Index: gcc/testsuite/g++.dg/vect/slp-pr92516.cc
===================================================================
--- gcc/testsuite/g++.dg/vect/slp-pr92516.cc (nonexistent)
+++ gcc/testsuite/g++.dg/vect/slp-pr92516.cc (working copy)
@@ -0,0 +1,43 @@
+// { dg-do compile }
+// { dg-require-effective-target c++14 }
+
+class a {
+public:
+  typedef int b;
+  operator b();
+};
+class c {
+public:
+  constexpr int m_fn1() const;
+  constexpr int d() const;
+  int e;
+  int f;
+};
+constexpr int c::m_fn1() const { return e; }
+constexpr int c::d() const { return f; }
+class g {
+public:
+  g();
+  constexpr void i(const c &) noexcept;
+  int j;
+  int k;
+  int l;
+  int m;
+};
+constexpr void g::i(const c &n) noexcept {
+  int v = l - j, h = m - k;
+  j = n.m_fn1() - v / 2;
+  k = n.d() - h / 2;
+  l = j + v;
+  m = k + h;
+}
+class o {
+  void m_fn4() const;
+  a p;
+} r;
+void o::m_fn4() const {
+  g q;
+  c t;
+  q.i(t);
+  r.p || 0;
+}
Reply | Threaded
Open this post in threaded view
|

Re: Record leader nodes in the SLP graph (PR92516)

Richard Biener
On Mon, 18 Nov 2019, Richard Biener wrote:

> On Sat, 16 Nov 2019, Richard Sandiford wrote:
>
> > If stmt analysis failed for an SLP node, r278246 tried building the
> > node from scalars instead.  By that point we've already processed child
> > nodes (usually successfully) and might have made some of them the lead
> > nodes for their stmt list.  This is why we couldn't free the child nodes
> > when deciding to build from scalars:
> >
> >   /* Don't remove and free the child nodes here, since they could be
> >      referenced by other structures.  The analysis and scheduling phases
> >      (need to) ignore child nodes of anything that isn't vect_internal_def.  */
> >
> > The problem in this PR is that we (correctly) don't process the unused
> > child nodes again during the scheduling phase, which means that those
> > nodes won't become the leader again.  So some other node with same stmts
> > becomes the leader instead.  However, any internal-def child nodes of
> > this new leader won't have been processed during the analysis phase,
> > because we also (correctly) skip child nodes of non-leader nodes.
> >
> > We talked on IRC about fixing this by sharing nodes between SLP
> > instances, so that it becomes a "proper" graph.  But that seems
> > like it could throw up some problems too, so I wanted to fix the
> > PR in a less invasive way first.
> >
> > This patch therefore records the leader nodes during the analysis
> > phase and reuses that choice during scheduling.  When scheduling
> > a non-leader node, we first try to schedule the leader node and
> > then reuse its vector stmts.  At the moment, doing this means we
> > need to know the leader node's SLP instance, so the patch records
> > that in the SLP node too.
> >
> > While there, I noticed that the two-operation handling returned
> > early without restoring the original def types.  That's really
> > an independent bug fix.
>
> Can you split that out please?
>
> For the rest I prefer the following which I am now fully testing
> on x86_64-unknown-linux-gnu (vect.exp testing went fine).  As
> discussed on IRC this makes the SLP graph nodes shared between
> SLP instances (which it has in fact been, just "virtual" via
> all the leader computations).  So SLP instances are now just
> the collection of entries into the directed SLP graph.
>
> I'm also throwing this on a SPEC build test.

Bootstrap & regtest went fine.  SPEC building reveals a latent
CTOR vectorization issue fixed by the pach below.

Re-testing the combined patch now.

Richard.

2019-11-18  Richard Biener  <[hidden email]>

        * tree-vect-slp.c (vect_analyze_slp_instance): When a CTOR
        was vectorized with just external refs fail.

        * gcc.dg/vect/vect-ctor-1.c: New testcase.

Index: gcc/tree-vect-slp.c
===================================================================
--- gcc/tree-vect-slp.c (revision 278389)
+++ gcc/tree-vect-slp.c (working copy)
@@ -2260,6 +2253,18 @@ vect_analyze_slp_instance (vec_info *vin
   matches[group_size / const_max_nunits * const_max_nunits] = false;
   vect_free_slp_tree (node, false);
  }
+      else if (constructor
+       && SLP_TREE_DEF_TYPE (node) != vect_internal_def)
+ {
+  /* CONSTRUCTOR vectorization relies on a vector stmt being
+     generated, that doesn't work for fully external ones.  */
+  if (dump_enabled_p ())
+    dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+     "Build SLP failed: CONSTRUCTOR of external "
+     "or constant elements\n");
+  vect_free_slp_tree (node, false);
+  return false;
+ }
       else
  {
   /* Create a new SLP instance.  */
Index: gcc/testsuite/gcc.dg/vect/vect-ctor-1.c
===================================================================
--- gcc/testsuite/gcc.dg/vect/vect-ctor-1.c (nonexistent)
+++ gcc/testsuite/gcc.dg/vect/vect-ctor-1.c (working copy)
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-O3" } */
+/* { dg-additional-options "-mavx2" { target { i?86-*-* x86_64-*-* } } } */
+
+typedef struct {
+    unsigned short mprr_2[5][16][16];
+} ImageParameters;
+int s[16][2];
+void intrapred_luma_16x16(ImageParameters *img, int s0)
+{
+  for (int j=0; j < 16; j++)
+    for (int i=0; i < 16; i++)
+      {
+ img->mprr_2[1 ][j][i]=s[j][1];
+ img->mprr_2[2 ][j][i]=s0;
+      }
+}
Reply | Threaded
Open this post in threaded view
|

Re: Record leader nodes in the SLP graph (PR92516)

Richard Sandiford-9
In reply to this post by Richard Biener
Richard Biener <[hidden email]> writes:

> On Sat, 16 Nov 2019, Richard Sandiford wrote:
>> If stmt analysis failed for an SLP node, r278246 tried building the
>> node from scalars instead.  By that point we've already processed child
>> nodes (usually successfully) and might have made some of them the lead
>> nodes for their stmt list.  This is why we couldn't free the child nodes
>> when deciding to build from scalars:
>>
>>   /* Don't remove and free the child nodes here, since they could be
>>      referenced by other structures.  The analysis and scheduling phases
>>      (need to) ignore child nodes of anything that isn't vect_internal_def.  */
>>
>> The problem in this PR is that we (correctly) don't process the unused
>> child nodes again during the scheduling phase, which means that those
>> nodes won't become the leader again.  So some other node with same stmts
>> becomes the leader instead.  However, any internal-def child nodes of
>> this new leader won't have been processed during the analysis phase,
>> because we also (correctly) skip child nodes of non-leader nodes.
>>
>> We talked on IRC about fixing this by sharing nodes between SLP
>> instances, so that it becomes a "proper" graph.  But that seems
>> like it could throw up some problems too, so I wanted to fix the
>> PR in a less invasive way first.
>>
>> This patch therefore records the leader nodes during the analysis
>> phase and reuses that choice during scheduling.  When scheduling
>> a non-leader node, we first try to schedule the leader node and
>> then reuse its vector stmts.  At the moment, doing this means we
>> need to know the leader node's SLP instance, so the patch records
>> that in the SLP node too.
>>
>> While there, I noticed that the two-operation handling returned
>> early without restoring the original def types.  That's really
>> an independent bug fix.
>
> Can you split that out please?

Sure, done as below.  Tested on aarch64-linux-gnu and x86_64-linux-gnu.
OK to install?

> For the rest I prefer the following which I am now fully testing
> on x86_64-unknown-linux-gnu (vect.exp testing went fine).  As
> discussed on IRC this makes the SLP graph nodes shared between
> SLP instances (which it has in fact been, just "virtual" via
> all the leader computations).  So SLP instances are now just
> the collection of entries into the directed SLP graph.

Looks great.  Obviously I chickened out too early :-)

Thanks,
Richard


2019-11-19  Richard Sandiford  <[hidden email]>

gcc/
        * tree-vect-slp.c (vect_schedule_slp_instance): Restore stmt
        def types for two-operation SLP.

Index: gcc/tree-vect-slp.c
===================================================================
--- gcc/tree-vect-slp.c 2019-11-20 09:48:57.145101295 +0000
+++ gcc/tree-vect-slp.c 2019-11-20 12:11:56.818216093 +0000
@@ -4165,6 +4165,7 @@ vect_schedule_slp_instance (slp_tree nod
 
   /* Handle two-operation SLP nodes by vectorizing the group with
      both operations and then performing a merge.  */
+  bool done_p = false;
   if (SLP_TREE_TWO_OPERATORS (node))
     {
       gassign *stmt = as_a <gassign *> (stmt_info->stmt);
@@ -4235,10 +4236,11 @@ vect_schedule_slp_instance (slp_tree nod
     }
   v0.release ();
   v1.release ();
-  return;
+  done_p = true;
  }
     }
-  vect_transform_stmt (stmt_info, &si, node, instance);
+  if (!done_p)
+    vect_transform_stmt (stmt_info, &si, node, instance);
 
   /* Restore stmt def-types.  */
   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
Reply | Threaded
Open this post in threaded view
|

Re: Record leader nodes in the SLP graph (PR92516)

Richard Biener
On Wed, 20 Nov 2019, Richard Sandiford wrote:

> Richard Biener <[hidden email]> writes:
> > On Sat, 16 Nov 2019, Richard Sandiford wrote:
> >> If stmt analysis failed for an SLP node, r278246 tried building the
> >> node from scalars instead.  By that point we've already processed child
> >> nodes (usually successfully) and might have made some of them the lead
> >> nodes for their stmt list.  This is why we couldn't free the child nodes
> >> when deciding to build from scalars:
> >>
> >>   /* Don't remove and free the child nodes here, since they could be
> >>      referenced by other structures.  The analysis and scheduling phases
> >>      (need to) ignore child nodes of anything that isn't vect_internal_def.  */
> >>
> >> The problem in this PR is that we (correctly) don't process the unused
> >> child nodes again during the scheduling phase, which means that those
> >> nodes won't become the leader again.  So some other node with same stmts
> >> becomes the leader instead.  However, any internal-def child nodes of
> >> this new leader won't have been processed during the analysis phase,
> >> because we also (correctly) skip child nodes of non-leader nodes.
> >>
> >> We talked on IRC about fixing this by sharing nodes between SLP
> >> instances, so that it becomes a "proper" graph.  But that seems
> >> like it could throw up some problems too, so I wanted to fix the
> >> PR in a less invasive way first.
> >>
> >> This patch therefore records the leader nodes during the analysis
> >> phase and reuses that choice during scheduling.  When scheduling
> >> a non-leader node, we first try to schedule the leader node and
> >> then reuse its vector stmts.  At the moment, doing this means we
> >> need to know the leader node's SLP instance, so the patch records
> >> that in the SLP node too.
> >>
> >> While there, I noticed that the two-operation handling returned
> >> early without restoring the original def types.  That's really
> >> an independent bug fix.
> >
> > Can you split that out please?
>
> Sure, done as below.  Tested on aarch64-linux-gnu and x86_64-linux-gnu.
> OK to install?
OK.

Thanks,
Richard.
 

> > For the rest I prefer the following which I am now fully testing
> > on x86_64-unknown-linux-gnu (vect.exp testing went fine).  As
> > discussed on IRC this makes the SLP graph nodes shared between
> > SLP instances (which it has in fact been, just "virtual" via
> > all the leader computations).  So SLP instances are now just
> > the collection of entries into the directed SLP graph.
>
> Looks great.  Obviously I chickened out too early :-)
>
> Thanks,
> Richard
>
>
> 2019-11-19  Richard Sandiford  <[hidden email]>
>
> gcc/
> * tree-vect-slp.c (vect_schedule_slp_instance): Restore stmt
> def types for two-operation SLP.
>
> Index: gcc/tree-vect-slp.c
> ===================================================================
> --- gcc/tree-vect-slp.c 2019-11-20 09:48:57.145101295 +0000
> +++ gcc/tree-vect-slp.c 2019-11-20 12:11:56.818216093 +0000
> @@ -4165,6 +4165,7 @@ vect_schedule_slp_instance (slp_tree nod
>  
>    /* Handle two-operation SLP nodes by vectorizing the group with
>       both operations and then performing a merge.  */
> +  bool done_p = false;
>    if (SLP_TREE_TWO_OPERATORS (node))
>      {
>        gassign *stmt = as_a <gassign *> (stmt_info->stmt);
> @@ -4235,10 +4236,11 @@ vect_schedule_slp_instance (slp_tree nod
>      }
>    v0.release ();
>    v1.release ();
> -  return;
> +  done_p = true;
>   }
>      }
> -  vect_transform_stmt (stmt_info, &si, node, instance);
> +  if (!done_p)
> +    vect_transform_stmt (stmt_info, &si, node, instance);
>  
>    /* Restore stmt def-types.  */
>    FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
>
--
Richard Biener <[hidden email]>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)