[PATCH][GRAPHITE] Fix PR79483

[PATCH][GRAPHITE] Fix PR79483

[Richard Biener]

When the order of visiting dominator children in domwalk changed
GRAPHITE falls foul of relying on a particular order BBs are visited
when computing the original schedule from the vector of pbbs.

The following restores an order that I believe might work.

In the end the original schedule should probably be computed
not relying on the order of pbbs in the pbb array but by
visiting the SESE region in an edge walk that "works"
(build_original_schedule).  We seem to lack a BB -> pbb mapping
though.

So the patch somewhat feels like a hack - not fixing the real
problem in the design of build_original_schedule, but it seems
to work ...

Boostrapped and tested on x86_64-unknown-linux-gnu, ok?

Thanks,
Richard.

2017-06-07  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/79483
	* graphite-scop-detection.c (order): New global.
	(get_order): Compute bb to order mapping that satisfies code
	generation constraints.
	(cmp_pbbs): New helper.
	(build_scops): Start domwalk at entry block, sort generated
	pbbs.

	* gcc.dg/graphite/pr79483.c: New testcase.

Index: gcc/graphite-scop-detection.c
===================================================================
--- gcc/graphite-scop-detection.c	(revision 248914)
+++ gcc/graphite-scop-detection.c	(working copy)
@@ -1999,6 +1999,46 @@ gather_bbs::after_dom_children (basic_bl
     }
 }
 
+
+/* Compute sth like an execution order, dominator order with first executing
+   edges that stay inside the current loop, delaying processing exit edges.  */
+
+static vec<unsigned> order;
+
+static void
+get_order (scop_p scop, basic_block bb, vec<unsigned> *order, unsigned *dfs_num)
+{
+  if (! bb_in_sese_p (bb, scop->scop_info->region))
+    return;
+
+  (*order)[bb->index] = (*dfs_num)++;
+  for (basic_block son = first_dom_son (CDI_DOMINATORS, bb);
+       son;
+       son = next_dom_son (CDI_DOMINATORS, son))
+    if (flow_bb_inside_loop_p (bb->loop_father, son))
+      get_order (scop, son, order, dfs_num);
+  for (basic_block son = first_dom_son (CDI_DOMINATORS, bb);
+       son;
+       son = next_dom_son (CDI_DOMINATORS, son))
+    if (! flow_bb_inside_loop_p (bb->loop_father, son))
+      get_order (scop, son, order, dfs_num);
+}
+
+/* Helper for qsort, sorting after order above.  */
+
+static int
+cmp_pbbs (const void *pa, const void *pb)
+{
+  poly_bb_p bb1 = *((const poly_bb_p *)pa);
+  poly_bb_p bb2 = *((const poly_bb_p *)pb);
+  if (order[bb1->black_box->bb->index] < order[bb2->black_box->bb->index])
+    return -1;
+  else if (order[bb1->black_box->bb->index] > order[bb2->black_box->bb->index])
+    return 1;
+  else
+    return 0;
+}
+
 /* Find Static Control Parts (SCoP) in the current function and pushes
    them to SCOPS.  */
 
@@ -2022,7 +2062,18 @@ build_scops (vec<scop_p> *scops)
       scop_p scop = new_scop (s->entry, s->exit);
 
       /* Record all basic blocks and their conditions in REGION.  */
-      gather_bbs (CDI_DOMINATORS, scop).walk (cfun->cfg->x_entry_block_ptr);
+      gather_bbs (CDI_DOMINATORS, scop).walk (s->entry->dest);
+
+      /* domwalk does not fulfil our code-generations constraints on the
+         order of pbb which is to produce sth like execution order, delaying
+	 exection of loop exit edges.  So compute such order and sort after
+	 that.  */
+      order.create (last_basic_block_for_fn (cfun));
+      order.quick_grow (last_basic_block_for_fn (cfun));
+      unsigned dfs_num = 0;
+      get_order (scop, s->entry->dest, &order, &dfs_num);
+      scop->pbbs.qsort (cmp_pbbs);
+      order.release ();
 
       build_alias_set (scop);
 
Index: gcc/testsuite/gcc.dg/graphite/pr79483.c
===================================================================
--- gcc/testsuite/gcc.dg/graphite/pr79483.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/graphite/pr79483.c	(working copy)
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgraphite-identity" } */
+
+int *a;
+extern int b[];
+int c;
+void d ()
+{
+  double e[2][3] = {0.0, 0.0, 1.0};
+  for (int f = 0; f < 2; ++f)
+    for (int g = 0; g < 6; ++g)
+      b[0] = a[g] * e[f][2];
+  c = b[0];
+}

Re: [PATCH][GRAPHITE] Fix PR79483

[Sebastian Pop]

On Wed, Jun 7, 2017 at 4:46 AM, Richard Biener <rguenther@suse.de> wrote:
>
> When the order of visiting dominator children in domwalk changed
> GRAPHITE falls foul of relying on a particular order BBs are visited
> when computing the original schedule from the vector of pbbs.
>
> The following restores an order that I believe might work.
>
> In the end the original schedule should probably be computed
> not relying on the order of pbbs in the pbb array but by
> visiting the SESE region in an edge walk that "works"
> (build_original_schedule).  We seem to lack a BB -> pbb mapping
> though.
>
> So the patch somewhat feels like a hack - not fixing the real
> problem in the design of build_original_schedule, but it seems
> to work ...
>
> Boostrapped and tested on x86_64-unknown-linux-gnu, ok?
>
> Thanks,
> Richard.
>
> 2017-06-07  Richard Biener  <rguenther@suse.de>
>
>         PR tree-optimization/79483
>         * graphite-scop-detection.c (order): New global.
>         (get_order): Compute bb to order mapping that satisfies code
>         generation constraints.
>         (cmp_pbbs): New helper.
>         (build_scops): Start domwalk at entry block, sort generated
>         pbbs.

I think the change looks good.

Thanks,
Sebastian

>
>         * gcc.dg/graphite/pr79483.c: New testcase.
>
> Index: gcc/graphite-scop-detection.c
> ===================================================================
> --- gcc/graphite-scop-detection.c       (revision 248914)
> +++ gcc/graphite-scop-detection.c       (working copy)
> @@ -1999,6 +1999,46 @@ gather_bbs::after_dom_children (basic_bl
>      }
>  }
>
> +
> +/* Compute sth like an execution order, dominator order with first executing
> +   edges that stay inside the current loop, delaying processing exit edges.  */
> +
> +static vec<unsigned> order;
> +
> +static void
> +get_order (scop_p scop, basic_block bb, vec<unsigned> *order, unsigned *dfs_num)
> +{
> +  if (! bb_in_sese_p (bb, scop->scop_info->region))
> +    return;
> +
> +  (*order)[bb->index] = (*dfs_num)++;
> +  for (basic_block son = first_dom_son (CDI_DOMINATORS, bb);
> +       son;
> +       son = next_dom_son (CDI_DOMINATORS, son))
> +    if (flow_bb_inside_loop_p (bb->loop_father, son))
> +      get_order (scop, son, order, dfs_num);
> +  for (basic_block son = first_dom_son (CDI_DOMINATORS, bb);
> +       son;
> +       son = next_dom_son (CDI_DOMINATORS, son))
> +    if (! flow_bb_inside_loop_p (bb->loop_father, son))
> +      get_order (scop, son, order, dfs_num);
> +}
> +
> +/* Helper for qsort, sorting after order above.  */
> +
> +static int
> +cmp_pbbs (const void *pa, const void *pb)
> +{
> +  poly_bb_p bb1 = *((const poly_bb_p *)pa);
> +  poly_bb_p bb2 = *((const poly_bb_p *)pb);
> +  if (order[bb1->black_box->bb->index] < order[bb2->black_box->bb->index])
> +    return -1;
> +  else if (order[bb1->black_box->bb->index] > order[bb2->black_box->bb->index])
> +    return 1;
> +  else
> +    return 0;
> +}
> +
>  /* Find Static Control Parts (SCoP) in the current function and pushes
>     them to SCOPS.  */
>
> @@ -2022,7 +2062,18 @@ build_scops (vec<scop_p> *scops)
>        scop_p scop = new_scop (s->entry, s->exit);
>
>        /* Record all basic blocks and their conditions in REGION.  */
> -      gather_bbs (CDI_DOMINATORS, scop).walk (cfun->cfg->x_entry_block_ptr);
> +      gather_bbs (CDI_DOMINATORS, scop).walk (s->entry->dest);
> +
> +      /* domwalk does not fulfil our code-generations constraints on the
> +         order of pbb which is to produce sth like execution order, delaying
> +        exection of loop exit edges.  So compute such order and sort after
> +        that.  */
> +      order.create (last_basic_block_for_fn (cfun));
> +      order.quick_grow (last_basic_block_for_fn (cfun));
> +      unsigned dfs_num = 0;
> +      get_order (scop, s->entry->dest, &order, &dfs_num);
> +      scop->pbbs.qsort (cmp_pbbs);
> +      order.release ();
>
>        build_alias_set (scop);
>
> Index: gcc/testsuite/gcc.dg/graphite/pr79483.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/graphite/pr79483.c     (nonexistent)
> +++ gcc/testsuite/gcc.dg/graphite/pr79483.c     (working copy)
> @@ -0,0 +1,14 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fgraphite-identity" } */
> +
> +int *a;
> +extern int b[];
> +int c;
> +void d ()
> +{
> +  double e[2][3] = {0.0, 0.0, 1.0};
> +  for (int f = 0; f < 2; ++f)
> +    for (int g = 0; g < 6; ++g)
> +      b[0] = a[g] * e[f][2];
> +  c = b[0];
> +}