From 26993e95b9e5d4c79ee6c9b16307046383590748 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Mon, 25 Sep 2017 13:19:16 +0000 Subject: 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/cfgloop.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 52 insertions(+) (limited to 'gcc/cfgloop.c') 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 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 -- cgit v1.1