From 26993e95b9e5d4c79ee6c9b16307046383590748 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Mon, 25 Sep 2017 13:19:16 +0000 Subject: [PATCH] cfgloop.h (sort_sibling_loops): Declare. 2017-09-25 Richard Biener * 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 --- gcc/ChangeLog | 8 ++++++++ gcc/cfgloop.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++ gcc/cfgloop.h | 1 + gcc/graphite.c | 1 + 4 files changed, 62 insertions(+) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b6dd97832f6..f4060b103bf 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +2017-09-25 Richard Biener + + * 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 * target.def (vec_perm_const_ok): Change sel parameter to diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index a1e778b8586..6911426787b 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 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 fcf366745df..0b164e97b1f 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 a5a31c2c074..7e6ba5078ec 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); -- 2.30.2