PR middle-end 42906 (empty loops not removed when leaved via critical edge with PHI node attached)
Richard Guenther
richard.guenther@gmail.com
Sat Mar 27 19:14:00 GMT 2010
On Sat, Mar 27, 2010 at 6:37 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> the testcase in PR shows that we are no longer able to remove empty loops that
> have exit edge connected to basic block with multiple incomming edges and a PHI
> node. I guess it is not that incommon case (relative to frequency of empty
> loops in sane programs:) so this patch fixes it by making PHI control
> dependence more cureful.
>
> Bootstrapped/regtested x86_64-linux.
With the history of CDDCE bugs I'd like to defer this for stage1 (and
eventually backport it to fix the regression).
Thus, the patch is ok for stage1.
Thanks,
Richard.
> 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.
>
> Index: tree-ssa-dce.c
> ===================================================================
> --- tree-ssa-dce.c (revision 157705)
> +++ tree-ssa-dce.c (working copy)
> @@ -373,12 +373,15 @@ mark_stmt_if_obviously_necessary (gimple
>
> /* 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 (
> 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 (
> 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 e
> 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 e
> {
> 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 *e
> 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,85 @@ propagate_necessity (struct edge_list *e
> 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. In this case the control dependence of predecestor block
> + also contains the block determining number of iterations of the block
> + that would prevent removing of empty loops 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);
> }
> }
> }
> Index: testsuite/gcc.dg/tree-ssa/dce-1.c
> ===================================================================
> --- testsuite/gcc.dg/tree-ssa/dce-1.c (revision 0)
> +++ testsuite/gcc.dg/tree-ssa/dce-1.c (revision 0)
> @@ -0,0 +1,19 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O1 -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 "cddcd1" } } */
> +
>
More information about the Gcc-patches
mailing list