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

4 files changed, 62 insertions, 0 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index b6dd978..f4060b1 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@
+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.
+
 2017-09-25  Richard Sandiford  <richard.sandifird@linaro.org>
 
 	* target.def (vec_perm_const_ok): Change sel parameter to
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
diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index fcf3667..0b164e9 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -333,6 +333,7 @@ bool mark_irreducible_loops (void);
 void release_recorded_exits (function *);
 void record_loop_exits (void);
 void rescan_loop_exit (edge, bool, bool);
+void sort_sibling_loops (function *);
 
 /* Loop data structure manipulation/querying.  */
 extern void flow_loop_tree_node_add (struct loop *, struct loop *);
diff --git a/gcc/graphite.c b/gcc/graphite.c
index a5a31c2..7e6ba50 100644
--- a/gcc/graphite.c
+++ b/gcc/graphite.c
@@ -419,6 +419,7 @@ graphite_transform_loops (void)
   isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
   the_isl_ctx = ctx;
 
+  sort_sibling_loops (cfun);
   canonicalize_loop_closed_ssa_form ();
 
   calculate_dominance_info (CDI_POST_DOMINATORS);