re PR tree-optimization/79483 ([graphite] ICE: verify_ssa failed (error: definition in block 31 does not dominate use in block 28))

2017-06-09  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.

From-SVN: r249052

1 files changed, 52 insertions, 1 deletions

diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index 2b7604e2e73..e17d58a26fc 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -1999,6 +1999,46 @@ gather_bbs::after_dom_children (basic_block bb)
     }
 }
 
+
+/* 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);