From 9adc5680a8bf87c8867136f10390b4b2ec9b8aa6 Mon Sep 17 00:00:00 2001 From: hubicka Date: Tue, 6 Apr 2010 15:18:18 +0000 Subject: [PATCH] PR tree-optimization/42906 * tree-ssa-dce.c (mark_control_dependent_edges_necessary): Add IGNORE_SELF argument; set visited_control_parents for fully processed BBs. (find_obviously_necessary_stmts): Update call of mark_control_dependent_edges_necessary. (propagate_necessity): Likewise; handle PHI edges more curefully. * gcc.dg/tree-ssa/dce-1.c: New testcase. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@158004 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 10 +++ gcc/testsuite/ChangeLog | 5 ++ gcc/testsuite/gcc.dg/tree-ssa/dce-1.c | 19 ++++++ gcc/tree-ssa-dce.c | 113 ++++++++++++++++++++++++++++++---- 4 files changed, 135 insertions(+), 12 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/dce-1.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 77af22cc503..a05b59588d4 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,13 @@ +2010-04-06 Jan Hubicka * config/i386/i386.md: Remove comment about 'e' and 'E' diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index e6fc3c04e87..22f893424f6 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2010-04-06 Jan Hubicka PR fortran/43178 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/dce-1.c b/gcc/testsuite/gcc.dg/tree-ssa/dce-1.c new file mode 100644 index 00000000000..12612e54680 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/dce-1.c @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-cddce1" } */ +int foo (int b, int j) +{ + if (b) + { + int i; + for (i = 0; i<1000; ++i) + ; + j = 0; + } + return j; +} +/* Check that empty loop is eliminated in this case. We should no longer have + the exit condition after the loop. */ +/* { dg-final { scan-tree-dump-not "999" "cddce1"} } */ +/* { dg-final { scan-tree-dump-not "1000" "cddce1"} } */ +/* { dg-final { cleanup-tree-dump "cddce1" } } */ + diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c index f54511c5741..a1f1c710df7 100644 --- a/gcc/tree-ssa-dce.c +++ b/gcc/tree-ssa-dce.c @@ -373,12 +373,15 @@ mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive) /* Make corresponding control dependent edges necessary. We only have to do this once for each basic block, so we clear the bitmap - after we're done. */ + after we're done. + + When IGNORE_SELF it true, ignore BB from the list of control dependences. */ static void -mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el) +mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el, bool ignore_self) { bitmap_iterator bi; unsigned edge_number; + bool skipped = false; gcc_assert (bb != EXIT_BLOCK_PTR); @@ -390,6 +393,12 @@ mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el) gimple stmt; basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number); + if (ignore_self && cd_bb == bb) + { + skipped = true; + continue; + } + if (TEST_BIT (last_stmt_necessary, cd_bb->index)) continue; SET_BIT (last_stmt_necessary, cd_bb->index); @@ -399,6 +408,8 @@ mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el) if (stmt && is_ctrl_stmt (stmt)) mark_stmt_necessary (stmt, true); } + if (!skipped) + SET_BIT (visited_control_parents, bb->index); } @@ -459,7 +470,7 @@ find_obviously_necessary_stmts (struct edge_list *el) if (dump_file) fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n", e->src->index, e->dest->index); - mark_control_dependent_edges_necessary (e->dest, el); + mark_control_dependent_edges_necessary (e->dest, el, false); } } @@ -468,7 +479,7 @@ find_obviously_necessary_stmts (struct edge_list *el) { if (dump_file) fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num); - mark_control_dependent_edges_necessary (loop->latch, el); + mark_control_dependent_edges_necessary (loop->latch, el, false); } scev_finalize (); } @@ -653,10 +664,7 @@ propagate_necessity (struct edge_list *el) basic_block bb = gimple_bb (stmt); if (bb != ENTRY_BLOCK_PTR && ! TEST_BIT (visited_control_parents, bb->index)) - { - SET_BIT (visited_control_parents, bb->index); - mark_control_dependent_edges_necessary (bb, el); - } + mark_control_dependent_edges_necessary (bb, el, false); } if (gimple_code (stmt) == GIMPLE_PHI @@ -679,17 +687,98 @@ propagate_necessity (struct edge_list *el) mark_operand_necessary (arg); } + /* For PHI operands it matters from where the control flow arrives + to the BB. Consider the following example: + + a=exp1; + b=exp2; + if (test) + ; + else + ; + c=PHI(a,b) + + We need to mark control dependence of the empty basic blocks, since they + contains computation of PHI operands. + + Doing so is too restrictive in the case the predecestor block is in + the loop. Consider: + + if (b) + { + int i; + for (i = 0; i<1000; ++i) + ; + j = 0; + } + return j; + + There is PHI for J in the BB containing return statement. + In this case the control dependence of predecestor block (that is + within the empty loop) also contains the block determining number + of iterations of the block that would prevent removing of empty + loop in this case. + + This scenario can be avoided by splitting critical edges. + To save the critical edge splitting pass we identify how the control + dependence would look like if the edge was split. + + Consider the modified CFG created from current CFG by splitting + edge B->C. In the postdominance tree of modified CFG, C' is + always child of C. There are two cases how chlids of C' can look + like: + + 1) C' is leaf + + In this case the only basic block C' is control dependent on is B. + + 2) C' has single child that is B + + In this case control dependence of C' is same as control + dependence of B in original CFG except for block B itself. + (since C' postdominate B in modified CFG) + + Now how to decide what case happens? There are two basic options: + + a) C postdominate B. Then C immediately postdominate B and + case 2 happens iff there is no other way from B to C except + the edge B->C. + + There is other way from B to C iff there is succesor of B that + is not postdominated by B. Testing this condition is somewhat + expensive, because we need to iterate all succesors of B. + We are safe to assume that this does not happen: we will mark B + as needed when processing the other path from B to C that is + conrol dependent on B and marking control dependencies of B + itself is harmless because they will be processed anyway after + processing control statement in B. + + b) C does not postdominate B. Always case 1 happens since there is + path from C to exit that does not go through B and thus also C'. */ + if (aggressive && !degenerate_phi_p (stmt)) { for (k = 0; k < gimple_phi_num_args (stmt); k++) { basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src; - if (arg_bb != ENTRY_BLOCK_PTR - && ! TEST_BIT (visited_control_parents, arg_bb->index)) + + if (gimple_bb (stmt) + != get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb)) { - SET_BIT (visited_control_parents, arg_bb->index); - mark_control_dependent_edges_necessary (arg_bb, el); + if (!TEST_BIT (last_stmt_necessary, arg_bb->index)) + { + gimple stmt2; + SET_BIT (last_stmt_necessary, arg_bb->index); + SET_BIT (bb_contains_live_stmts, arg_bb->index); + + stmt2 = last_stmt (arg_bb); + if (stmt2 && is_ctrl_stmt (stmt2)) + mark_stmt_necessary (stmt2, true); + } } + else if (arg_bb != ENTRY_BLOCK_PTR + && ! TEST_BIT (visited_control_parents, arg_bb->index)) + mark_control_dependent_edges_necessary (arg_bb, el, true); } } } -- 2.11.0