Message ID | 20121022193516.GG1752@tucnak.redhat.com |
---|---|
State | New |
Headers | show |
On Mon, Oct 22, 2012 at 9:35 PM, Jakub Jelinek <jakub@redhat.com> wrote: > Hi! > > On the following testcase we have two endless loops before cddce2: > > Sender_signal (int Connect) > { > int State; > unsigned int occurrence; > > <bb 2>: > if (Connect_6(D) != 0) > goto <bb 8>; > else > goto <bb 7>; > > <bb 3>: > # occurrence_8 = PHI <0(7), occurrence_12(4)> > occurrence_12 = occurrence_8 + 1; > __builtin_printf ("Sender_Signal occurrence %u\n", occurrence_12); > > <bb 4>: > goto <bb 3>; > > <bb 5>: > > <bb 6>: > goto <bb 5>; > > <bb 7>: > goto <bb 3>; > > <bb 8>: > goto <bb 5>; > > } > > The problem are the two empty bbs on the path from the conditional > at the end of bb2 and the endless loops (i.e. bb7 and bb8). > In presence of infinite loops dominance.c adds fake edges to exit pretty > arbitrarily (it uses FOR_EACH_BB_REVERSE and for unconnected bbs > computes post-dominance and adds fake edges to exit), so with the above > testcases both bb7 and bb8 have exit block as immediate post-dominator, > so find_control_dependence stops at those bb's when starting from the > 2->7 resp. 2->8 edges. bb7/bb8 don't have a control stmt at the end, > so mark_last_stmt_necessary doesn't mark any stmt as necessary in them > and thus if (Connect_6(D) != 0) GIMPLE_COND is never marked as necessary > and the whole endless loop with printfs in it is removed. I'm not sure I'm following this alright, but AFAICT bb7 and bb8 are control-dependent on the "if" in bb2. To preserve the infinite-loop semantics the control parent of the infinite loop must be inherently preserved (because empty infinite loops can't mark any feeding statements). So shouldn't the code in find_obviously_necessary_stmts that handles infinite loops mark the last statement of control parents necessary? Ciao! Steven
On Mon, Oct 22, 2012 at 09:48:16PM +0200, Steven Bosscher wrote: > On Mon, Oct 22, 2012 at 9:35 PM, Jakub Jelinek <jakub@redhat.com> wrote: > > On the following testcase we have two endless loops before cddce2: > > > > Sender_signal (int Connect) > > { > > int State; > > unsigned int occurrence; > > > > <bb 2>: > > if (Connect_6(D) != 0) > > goto <bb 8>; > > else > > goto <bb 7>; > > > > <bb 3>: > > # occurrence_8 = PHI <0(7), occurrence_12(4)> > > occurrence_12 = occurrence_8 + 1; > > __builtin_printf ("Sender_Signal occurrence %u\n", occurrence_12); > > > > <bb 4>: > > goto <bb 3>; > > > > <bb 5>: > > > > <bb 6>: > > goto <bb 5>; > > > > <bb 7>: > > goto <bb 3>; > > > > <bb 8>: > > goto <bb 5>; > > > > } > > > > The problem are the two empty bbs on the path from the conditional > > at the end of bb2 and the endless loops (i.e. bb7 and bb8). > > In presence of infinite loops dominance.c adds fake edges to exit pretty > > arbitrarily (it uses FOR_EACH_BB_REVERSE and for unconnected bbs > > computes post-dominance and adds fake edges to exit), so with the above > > testcases both bb7 and bb8 have exit block as immediate post-dominator, > > so find_control_dependence stops at those bb's when starting from the > > 2->7 resp. 2->8 edges. bb7/bb8 don't have a control stmt at the end, > > so mark_last_stmt_necessary doesn't mark any stmt as necessary in them > > and thus if (Connect_6(D) != 0) GIMPLE_COND is never marked as necessary > > and the whole endless loop with printfs in it is removed. > > I'm not sure I'm following this alright, but AFAICT bb7 and bb8 are > control-dependent on the "if" in bb2. To preserve the infinite-loop > semantics the control parent of the infinite loop must be inherently > preserved (because empty infinite loops can't mark any feeding > statements). So shouldn't the code in find_obviously_necessary_stmts > that handles infinite loops mark the last statement of control parents > necessary? If bb7 and bb8 aren't there and bb2 branches directly to bb3 and bb5, then things work correctly, find_control_dependence then says that the 2->3 edge is control parent of bb3 and bb4 (bb3 immediate post-dominator is bb4, bb4 is immediately post-dominated through fake edge by exit) and similarly 2->5 edge is control parent of bb5 and bb6. Then find_obviously_necessary_stmts does: FOR_EACH_LOOP (li, loop, 0) if (!finite_loop_p (loop)) { if (dump_file) fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num); mark_control_dependent_edges_necessary (loop->latch, el, false); } and that marks the control stmt in bb2 as necessary, because edge 2->3 is in bb3 and bb4 bitmap and edge 2->5 is in bb5 and bb6 control dependence bitmap. The problem with bb7/bb8 is that because they have fake edges to exit too, find_control_dependence stops at them, thus 2->7 is considered control parent of bb7 and 2->8 control parent of bb8, and 7->3 is considered control parent of bb3 and bb4 and 8->5 of bb5 and bb6. Thus, mark_control_dependent_edges_necessary called on say the bb4 latch calls marks_last_stmt_necessary on bb7, but, there is no last stmt in that bb, nothing to mark necessary and it silently stops there. What my patch does is change it so that in that case it doesn't stop there, but recurses. Jakub
On Mon, Oct 22, 2012 at 9:58 PM, Jakub Jelinek <jakub@redhat.com> wrote: > On Mon, Oct 22, 2012 at 09:48:16PM +0200, Steven Bosscher wrote: >> On Mon, Oct 22, 2012 at 9:35 PM, Jakub Jelinek <jakub@redhat.com> wrote: >> > On the following testcase we have two endless loops before cddce2: >> > >> > Sender_signal (int Connect) >> > { >> > int State; >> > unsigned int occurrence; >> > >> > <bb 2>: >> > if (Connect_6(D) != 0) >> > goto <bb 8>; >> > else >> > goto <bb 7>; >> > >> > <bb 3>: >> > # occurrence_8 = PHI <0(7), occurrence_12(4)> >> > occurrence_12 = occurrence_8 + 1; >> > __builtin_printf ("Sender_Signal occurrence %u\n", occurrence_12); >> > >> > <bb 4>: >> > goto <bb 3>; >> > >> > <bb 5>: >> > >> > <bb 6>: >> > goto <bb 5>; >> > >> > <bb 7>: >> > goto <bb 3>; >> > >> > <bb 8>: >> > goto <bb 5>; >> > >> > } >> > >> > The problem are the two empty bbs on the path from the conditional >> > at the end of bb2 and the endless loops (i.e. bb7 and bb8). >> > In presence of infinite loops dominance.c adds fake edges to exit pretty >> > arbitrarily (it uses FOR_EACH_BB_REVERSE and for unconnected bbs >> > computes post-dominance and adds fake edges to exit), so with the above >> > testcases both bb7 and bb8 have exit block as immediate post-dominator, >> > so find_control_dependence stops at those bb's when starting from the >> > 2->7 resp. 2->8 edges. bb7/bb8 don't have a control stmt at the end, >> > so mark_last_stmt_necessary doesn't mark any stmt as necessary in them >> > and thus if (Connect_6(D) != 0) GIMPLE_COND is never marked as necessary >> > and the whole endless loop with printfs in it is removed. >> >> I'm not sure I'm following this alright, but AFAICT bb7 and bb8 are >> control-dependent on the "if" in bb2. To preserve the infinite-loop >> semantics the control parent of the infinite loop must be inherently >> preserved (because empty infinite loops can't mark any feeding >> statements). So shouldn't the code in find_obviously_necessary_stmts >> that handles infinite loops mark the last statement of control parents >> necessary? > > If bb7 and bb8 aren't there and bb2 branches directly to bb3 and bb5, > then things work correctly, find_control_dependence then says that > the 2->3 edge is control parent of bb3 and bb4 (bb3 immediate post-dominator > is bb4, bb4 is immediately post-dominated through fake edge by exit) and > similarly 2->5 edge is control parent of bb5 and bb6. Then > find_obviously_necessary_stmts does: > FOR_EACH_LOOP (li, loop, 0) > if (!finite_loop_p (loop)) > { > if (dump_file) > fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num); > mark_control_dependent_edges_necessary (loop->latch, el, false); > } > and that marks the control stmt in bb2 as necessary, because edge 2->3 is > in bb3 and bb4 bitmap and edge 2->5 is in bb5 and bb6 control dependence > bitmap. The problem with bb7/bb8 is that because they have fake edges to > exit too, find_control_dependence stops at them, thus 2->7 is considered > control parent of bb7 and 2->8 control parent of bb8, and 7->3 is considered > control parent of bb3 and bb4 and 8->5 of bb5 and bb6. Thus, > mark_control_dependent_edges_necessary called on say the bb4 latch calls > marks_last_stmt_necessary on bb7, but, there is no last stmt in that bb, > nothing to mark necessary and it silently stops there. > > What my patch does is change it so that in that case it doesn't stop there, > but recurses. I understand what your patch does, but I don't understand why it is correct. Why are there fake edges from bb7 and bb8 to exit when both are reverse-reachable from exit via the infinite loops? The infinite loops should be connected to exit, and bb7 and bb8 should be found by the DFS from the really dead ends in the cfg. Ciao! Steven
On Mon, Oct 22, 2012 at 10:27:52PM +0200, Steven Bosscher wrote: > I understand what your patch does, but I don't understand why it is correct. > > Why are there fake edges from bb7 and bb8 to exit when both are > reverse-reachable from exit via the infinite loops? The infinite loops > should be connected to exit, and bb7 and bb8 should be found by the > DFS from the really dead ends in the cfg. See what dominance.c does: if (saw_unconnected) { FOR_EACH_BB_REVERSE (b) { if (di->dfs_order[b->index]) continue; bitmap_set_bit (di->fake_exit_edge, b->index); di->dfs_order[b->index] = di->dfsnum; di->dfs_to_bb[di->dfsnum] = b; di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block]; di->dfsnum++; calc_dfs_tree_nonrec (di, b, reverse); } } bb7/bb8 (i.e. all bbs that are always in the end followed by infinite loops) as well as all the bbs on the infinite loops are processed the above way, they have no real path to exit, so aren't processed on the first iteration, they aren't processed even after adding fake edges from zero successor bbs. calc_dfs_tree then picks pretty much random bbs (one with highest index), adds fake edge to it, walks it, then goes on with other bbs that are still unconnected. dominance.c doesn't use cfgloop.h (can it? Isn't it used before loops are computed, perhaps after loops destroyed, etc.), so there is no guarantee that loop->latch of endless loop will have the fake edge added and no other bb before it. As 7 and 8 are bigger than 4 or 6, the above loop starts with bb 8, finds that its predecessor has already been searched and stops there, similarly for 7, then goes on with 6 with another fake edge to exit. Jakub
--- gcc/tree-ssa-dce.c.jj 2012-08-15 10:55:33.000000000 +0200 +++ gcc/tree-ssa-dce.c 2012-10-22 16:50:03.011497546 +0200 @@ -381,7 +381,7 @@ mark_stmt_if_obviously_necessary (gimple /* Mark the last statement of BB as necessary. */ -static void +static bool mark_last_stmt_necessary (basic_block bb) { gimple stmt = last_stmt (bb); @@ -391,7 +391,11 @@ mark_last_stmt_necessary (basic_block bb /* We actually mark the statement only if it is a control statement. */ if (stmt && is_ctrl_stmt (stmt)) - mark_stmt_necessary (stmt, true); + { + mark_stmt_necessary (stmt, true); + return true; + } + return false; } @@ -423,8 +427,18 @@ mark_control_dependent_edges_necessary ( continue; } - if (!TEST_BIT (last_stmt_necessary, cd_bb->index)) - mark_last_stmt_necessary (cd_bb); + if (!TEST_BIT (last_stmt_necessary, cd_bb->index) + && !mark_last_stmt_necessary (cd_bb)) + { + /* In presence of infinite loops, some bbs on a path + to an infinite loop might not end with a control stmt, + but due to a fake edge to exit stop find_control_dependence. + Recurse for those. */ + if (get_immediate_dominator (CDI_POST_DOMINATORS, cd_bb) + == EXIT_BLOCK_PTR + && single_succ_p (cd_bb)) + mark_control_dependent_edges_necessary (cd_bb, el, false); + } } if (!skipped) --- gcc/testsuite/gcc.dg/torture/pr55018.c.jj 2012-10-22 16:53:56.623083723 +0200 +++ gcc/testsuite/gcc.dg/torture/pr55018.c 2012-10-22 16:54:21.278934668 +0200 @@ -0,0 +1,22 @@ +/* PR tree-optimization/55018 */ +/* { dg-do compile } */ +/* { dg-options "-fdump-tree-optimized" } */ + +void +foo (int x) +{ + unsigned int a = 0; + int b = 3; + if (x) + b = 0; +lab: + if (x) + goto lab; + a++; + if (b != 2) + __builtin_printf ("%u", a); + goto lab; +} + +/* { dg-final { scan-tree-dump "printf" "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */