From 3be57c5600901c958769daf63d88264249afee7c Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Wed, 5 Jul 2017 11:51:22 +0000 Subject: [PATCH] tree-loop-distribution.c (bb_top_order_index): New. * tree-loop-distribution.c (bb_top_order_index): New. (bb_top_order_index_size, bb_top_order_cmp): New. (stmts_from_loop): Use topological order. (pass_loop_distribution::execute): Compute and release topological order for basic blocks. From-SVN: r249985 --- gcc/ChangeLog | 8 +++++ gcc/tree-loop-distribution.c | 58 ++++++++++++++++++++++++++++++++---- 2 files changed, 60 insertions(+), 6 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 666159bc8e9..49bacf55c1f 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +2017-07-05 Bin Cheng + + * tree-loop-distribution.c (bb_top_order_index): New. + (bb_top_order_index_size, bb_top_order_cmp): New. + (stmts_from_loop): Use topological order. + (pass_loop_distribution::execute): Compute and release topological + order for basic blocks. + 2017-07-05 Bin Cheng * tree-loop-distribution.c (pass_loop_distribution::execute): Skip diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c index 9f0c801007c..887e8702589 100644 --- a/gcc/tree-loop-distribution.c +++ b/gcc/tree-loop-distribution.c @@ -373,16 +373,39 @@ create_rdg_vertices (struct graph *rdg, vec stmts, loop_p loop, return true; } -/* Initialize STMTS with all the statements of LOOP. The order in - which we discover statements is important as - generate_loops_for_partition is using the same traversal for - identifying statements in loop copies. */ +/* Array mapping basic block's index to its topological order. */ +static int *bb_top_order_index; +/* And size of the array. */ +static int bb_top_order_index_size; + +/* If X has a smaller topological sort number than Y, returns -1; + if greater, returns 1. */ + +static int +bb_top_order_cmp (const void *x, const void *y) +{ + basic_block bb1 = *(const basic_block *) x; + basic_block bb2 = *(const basic_block *) y; + + gcc_assert (bb1->index < bb_top_order_index_size + && bb2->index < bb_top_order_index_size); + gcc_assert (bb1 == bb2 + || bb_top_order_index[bb1->index] + != bb_top_order_index[bb2->index]); + + return (bb_top_order_index[bb1->index] - bb_top_order_index[bb2->index]); +} + +/* Initialize STMTS with all the statements of LOOP. We use topological + order to discover all statements. The order is important because + generate_loops_for_partition is using the same traversal for identifying + statements in loop copies. */ static void stmts_from_loop (struct loop *loop, vec *stmts) { unsigned int i; - basic_block *bbs = get_loop_body_in_dom_order (loop); + basic_block *bbs = get_loop_body_in_custom_order (loop, bb_top_order_cmp); for (i = 0; i < loop->num_nodes; i++) { @@ -1761,6 +1784,22 @@ pass_loop_distribution::execute (function *fun) if (number_of_loops (fun) <= 1) return 0; + /* Compute topological order for basic blocks. Topological order is + needed because data dependence is computed for data references in + lexicographical order. */ + if (bb_top_order_index == NULL) + { + int *rpo = XNEWVEC (int, last_basic_block_for_fn (cfun)); + + bb_top_order_index = XNEWVEC (int, last_basic_block_for_fn (cfun)); + bb_top_order_index_size + = pre_and_rev_post_order_compute_fn (cfun, NULL, rpo, true); + for (int i = 0; i < bb_top_order_index_size; i++) + bb_top_order_index[rpo[i]] = i; + + free (rpo); + } + FOR_ALL_BB_FN (bb, fun) { gimple_stmt_iterator gsi; @@ -1868,13 +1907,20 @@ out: if (cd) delete cd; + if (bb_top_order_index != NULL) + { + free (bb_top_order_index); + bb_top_order_index = NULL; + bb_top_order_index_size = 0; + } + if (changed) { /* Destroy loop bodies that could not be reused. Do this late as we otherwise can end up refering to stale data in control dependences. */ unsigned i; FOR_EACH_VEC_ELT (loops_to_be_destroyed, i, loop) - destroy_loop (loop); + destroy_loop (loop); /* Cached scalar evolutions now may refer to wrong or non-existing loops. */ -- 2.30.2