cfgloop.h (sort_sibling_loops): Declare.

2017-09-25  Richard Biener  <rguenther@suse.de>

	* cfgloop.h (sort_sibling_loops): Declare.
	* cfgloop.c (sort_sibling_loops_cmp): New helper.
	(sort_sibling_loops): New function sorting the sibling loop list
	in RPO order.
	* graphite.c (graphite_transform_loops): Sort sibling loops.

From-SVN: r253149

1 files changed, 52 insertions, 0 deletions

diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c
index a1e778b..6911426 100644
--- a/gcc/cfgloop.c
+++ b/gcc/cfgloop.c
@@ -521,6 +521,58 @@ flow_loops_find (struct loops *loops)
   return loops;
 }
 
+/* qsort helper for sort_sibling_loops.  */
+
+static int *sort_sibling_loops_cmp_rpo;
+static int
+sort_sibling_loops_cmp (const void *la_, const void *lb_)
+{
+  const struct loop *la = *(const struct loop * const *)la_;
+  const struct loop *lb = *(const struct loop * const *)lb_;
+  return (sort_sibling_loops_cmp_rpo[la->header->index]
+	  - sort_sibling_loops_cmp_rpo[lb->header->index]);
+}
+
+/* Sort sibling loops in RPO order.  */
+
+void
+sort_sibling_loops (function *fn)
+{
+  /* Match flow_loops_find in the order we sort sibling loops.  */
+  sort_sibling_loops_cmp_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
+  int *rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
+  pre_and_rev_post_order_compute_fn (fn, NULL, rc_order, false);
+  for (int i = 0; i < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; ++i)
+    sort_sibling_loops_cmp_rpo[rc_order[i]] = i;
+  free (rc_order);
+
+  auto_vec<loop_p, 3> siblings;
+  loop_p loop;
+  FOR_EACH_LOOP_FN (fn, loop, LI_INCLUDE_ROOT)
+    if (loop->inner && loop->inner->next)
+      {
+	loop_p sibling = loop->inner;
+	do
+	  {
+	    siblings.safe_push (sibling);
+	    sibling = sibling->next;
+	  }
+	while (sibling);
+	siblings.qsort (sort_sibling_loops_cmp);
+	loop_p *siblingp = &loop->inner;
+	for (unsigned i = 0; i < siblings.length (); ++i)
+	  {
+	    *siblingp = siblings[i];
+	    siblingp = &(*siblingp)->next;
+	  }
+	*siblingp = NULL;
+	siblings.truncate (0);
+      }
+
+  free (sort_sibling_loops_cmp_rpo);
+  sort_sibling_loops_cmp_rpo = NULL;
+}
+
 /* Ratio of frequencies of edges so that one of more latch edges is
    considered to belong to inner loop with same header.  */
 #define HEAVY_EDGE_RATIO 8