From aae6da83564549a6f8700407df50cdd52d411727 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Mon, 13 May 2019 11:22:21 +0000 Subject: [PATCH] re PR tree-optimization/90316 (large compile time increase in opt / alias stmt walking for Go example) 2019-05-13 Richard Biener PR tree-optimization/90316 * tree-ssa-pre.c (insert_aux): Fold into ... (insert): ... this function. Use a RPO walk to reduce the number of required iterations. From-SVN: r271124 --- gcc/ChangeLog | 7 +++ gcc/tree-ssa-pre.c | 120 ++++++++++++++++++++------------------------- 2 files changed, 61 insertions(+), 66 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index f599fc2c06a..42448f5ef85 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2019-05-13 Richard Biener + + PR tree-optimization/90316 + * tree-ssa-pre.c (insert_aux): Fold into ... + (insert): ... this function. Use a RPO walk to reduce the + number of required iterations. + 2019-05-13 Martin Liska PR tree-optimization/90416 diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index 09335faa6a9..469199fa213 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -3601,92 +3601,80 @@ do_hoist_insertion (basic_block block) return new_stuff; } -/* Do a dominator walk on the control flow graph, and insert computations - of values as necessary for PRE and hoisting. */ - -static bool -insert_aux (basic_block block, bool do_pre, bool do_hoist) -{ - basic_block son; - bool new_stuff = false; - - if (block) - { - basic_block dom; - dom = get_immediate_dominator (CDI_DOMINATORS, block); - if (dom) - { - unsigned i; - bitmap_iterator bi; - bitmap_set_t newset; - - /* First, update the AVAIL_OUT set with anything we may have - inserted higher up in the dominator tree. */ - newset = NEW_SETS (dom); - if (newset) - { - /* Note that we need to value_replace both NEW_SETS, and - AVAIL_OUT. For both the case of NEW_SETS, the value may be - represented by some non-simple expression here that we want - to replace it with. */ - FOR_EACH_EXPR_ID_IN_SET (newset, i, bi) - { - pre_expr expr = expression_for_id (i); - bitmap_value_replace_in_set (NEW_SETS (block), expr); - bitmap_value_replace_in_set (AVAIL_OUT (block), expr); - } - } - - /* Insert expressions for partial redundancies. */ - if (do_pre && !single_pred_p (block)) - { - new_stuff |= do_pre_regular_insertion (block, dom); - if (do_partial_partial) - new_stuff |= do_pre_partial_partial_insertion (block, dom); - } - - /* Insert expressions for hoisting. */ - if (do_hoist && EDGE_COUNT (block->succs) >= 2) - new_stuff |= do_hoist_insertion (block); - } - } - for (son = first_dom_son (CDI_DOMINATORS, block); - son; - son = next_dom_son (CDI_DOMINATORS, son)) - { - new_stuff |= insert_aux (son, do_pre, do_hoist); - } - - return new_stuff; -} - /* Perform insertion of partially redundant and hoistable values. */ static void insert (void) { - bool new_stuff = true; basic_block bb; - int num_iterations = 0; FOR_ALL_BB_FN (bb, cfun) NEW_SETS (bb) = bitmap_set_new (); - while (new_stuff) + int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); + int rpo_num = pre_and_rev_post_order_compute (NULL, rpo, false); + + int num_iterations = 0; + bool changed; + do { num_iterations++; if (dump_file && dump_flags & TDF_DETAILS) fprintf (dump_file, "Starting insert iteration %d\n", num_iterations); - new_stuff = insert_aux (ENTRY_BLOCK_PTR_FOR_FN (cfun), flag_tree_pre, - flag_code_hoisting); + + changed = false; + for (int idx = 0; idx < rpo_num; ++idx) + { + basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[idx]); + basic_block dom = get_immediate_dominator (CDI_DOMINATORS, block); + if (dom) + { + unsigned i; + bitmap_iterator bi; + bitmap_set_t newset; + + /* First, update the AVAIL_OUT set with anything we may have + inserted higher up in the dominator tree. */ + newset = NEW_SETS (dom); + if (newset) + { + /* Note that we need to value_replace both NEW_SETS, and + AVAIL_OUT. For both the case of NEW_SETS, the value may be + represented by some non-simple expression here that we want + to replace it with. */ + FOR_EACH_EXPR_ID_IN_SET (newset, i, bi) + { + pre_expr expr = expression_for_id (i); + bitmap_value_replace_in_set (NEW_SETS (block), expr); + bitmap_value_replace_in_set (AVAIL_OUT (block), expr); + } + } + + /* Insert expressions for partial redundancies. */ + if (flag_tree_pre && !single_pred_p (block)) + { + changed |= do_pre_regular_insertion (block, dom); + if (do_partial_partial) + changed |= do_pre_partial_partial_insertion (block, dom); + } + + /* Insert expressions for hoisting. */ + if (flag_code_hoisting && EDGE_COUNT (block->succs) >= 2) + changed |= do_hoist_insertion (block); + } + } /* Clear the NEW sets before the next iteration. We have already - fully propagated its contents. */ - if (new_stuff) + fully propagated its contents. */ + if (changed) FOR_ALL_BB_FN (bb, cfun) bitmap_set_free (NEW_SETS (bb)); } + while (changed); + statistics_histogram_event (cfun, "insert iterations", num_iterations); + + free (rpo); } -- 2.30.2