This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Fix PR42717
> On Sat, 16 Jan 2010, Richard Guenther wrote:
>
> >
> > This fixes PR42717 where we run into issues with the PHI updating
> > of CDDCE dead region (aka dead control statement) removal.
> >
> > The core issue with the PR in question is that we pick the wrong
> > edge to copy PHI args from as the existing dominance check is
> > not strict enough to identify an edge from the dead region.
> > Fixing this opens up a can of worms.
> >
> > First we do not, even less so
> > after lxo came along, remove dead control statements in dominator
> > order. This means we do not remove the most dominating dead
> > control statement first but may start in the middle of a dead
> > region. That is at least inefficient but also leads to problems
> > with the proposed fix as we do not have dominator information
> > updated as we redirect edges (and it's non-trivial to do so).
> >
> > Second, the optimization of threading to the next _live_
> > post-dominator doesn't work as we come along totally unrelated
> > PHIs and the choice which edge to copy PHI args from is more
> > or less not solvable in general.
> >
> > Third with the patch we need to avoid visiting blocks in regions
> > we cut off again. The simple approach would be to delete them,
> > but that comes in the way of debug statements. Ugh. So I
> > have to re-compute block reachability after each region "removal".
>
> This is an easier variant - fixing 2) is the only thing required
> as in that case the PHI arg updating gets trivial.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu. Honza, what
> was the reason for threading to the next _live_ postdom?
That was what textbook says ;)
Originally code was simply not updating CFG in non-trivial cases. This
does not work, since we remove the conditional and then we eneded up
chosing random edge out of the block often turning finite loops into
infinite.
I guess if you replace every dead conditional by edge to post dominator,
then the dead regions will turn into acyclic blocks so later jump
threading will cure rest of updates?
As for orignial algorithm, I believe problem there was that we looked
for BB dominating the edge assumign that it is the block having control
dependency. It is possible to construct valid CFG where there are
multiple blocks dominating the edge, but only one of them is CD block.
It is always the lowest one in the chain. I will try to thinking about
this bit more, but I don't see problem with your code and I guess it is
overall easier.
Honza
>
> Thanks,
> Richard.
>
> compile.exp=pr40676.c
> execute.exp=20010129-1.c
> dg.exp=pr33673.c
>
> 2010-01-19 Richard Guenther <rguenther@suse.de>
>
> PR tree-optimization/42717
> * tree-ssa-dce.c (get_live_post_dom): Remove.
> (forward_edge_to_pdom): Take an arbitrary edge to copy
> degenerate PHI args from.
> (remove_dead_stmt): Use the first post-dominator even if it
> does not contain live statements as redirection destination.
>
> * gcc.c-torture/compile/pr42717.c: New testcase.
>
> Index: gcc/testsuite/gcc.c-torture/compile/pr42717.c
> ===================================================================
> *** /dev/null 1970-01-01 00:00:00.000000000 +0000
> --- gcc/testsuite/gcc.c-torture/compile/pr42717.c 2010-01-15 23:18:15.000000000 +0100
> ***************
> *** 0 ****
> --- 1,30 ----
> + static signed char
> + foo (signed char si1, unsigned char si2)
> + {
> + return (si1 ^ si2) & (-si2 ^ si2) ? : si1 - si2;
> + }
> +
> + struct S0
> + {
> + };
> +
> + unsigned char g_21;
> +
> + struct S0 g_34;
> +
> + void
> + bar (unsigned char p_20)
> + {
> + unsigned char *l_22 = &g_21;
> + unsigned char l_23 = 0;
> + struct S0 *l = &g_34;
> + goto lbl_42;
> + for (; l_23; l_23 = foo (l_23, 1))
> + {
> + for (p_20 = 0; 0; p_20 = foo (p_20, 1))
> + lbl_42:;
> + (l == &g_34) ? 0 : "";
> + lbl_85:*l_22 = p_20;
> + }
> + goto lbl_85;
> + }
> Index: gcc/tree-ssa-dce.c
> ===================================================================
> *** gcc/tree-ssa-dce.c (revision 156035)
> --- gcc/tree-ssa-dce.c (working copy)
> *************** remove_dead_phis (basic_block bb)
> *** 917,943 ****
> return something_changed;
> }
>
> - /* Find first live post dominator of BB. */
> -
> - static basic_block
> - get_live_post_dom (basic_block bb)
> - {
> - basic_block post_dom_bb;
> -
> -
> - /* The post dominance info has to be up-to-date. */
> - gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK);
> -
> - /* Get the immediate post dominator of bb. */
> - post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
> - /* And look for first live one. */
> - while (post_dom_bb != EXIT_BLOCK_PTR
> - && !TEST_BIT (bb_contains_live_stmts, post_dom_bb->index))
> - post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, post_dom_bb);
> -
> - return post_dom_bb;
> - }
> -
> /* Forward edge E to respective POST_DOM_BB and update PHIs. */
>
> static edge
> --- 917,922 ----
> *************** forward_edge_to_pdom (edge e, basic_bloc
> *** 961,970 ****
> if (!gimple_seq_empty_p (phi_nodes (post_dom_bb)))
> {
> /* We are sure that for every live PHI we are seeing control dependent BB.
> ! This means that we can look up the end of control dependent path leading
> ! to the PHI itself. */
> FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
> ! if (e2 != e && dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->src))
> break;
> for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
> {
> --- 940,948 ----
> if (!gimple_seq_empty_p (phi_nodes (post_dom_bb)))
> {
> /* We are sure that for every live PHI we are seeing control dependent BB.
> ! This means that we can pick any edge to duplicate PHI args from. */
> FOR_EACH_EDGE (e2, ei, post_dom_bb->preds)
> ! if (e2 != e)
> break;
> for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);)
> {
> *************** forward_edge_to_pdom (edge e, basic_bloc
> *** 972,1011 ****
> tree op;
> source_location locus;
>
> ! /* Dead PHI do not imply control dependency. */
> ! if (!gimple_plf (phi, STMT_NECESSARY)
> ! && is_gimple_reg (gimple_phi_result (phi)))
> ! {
> ! gsi_next (&gsi);
> ! continue;
> ! }
> ! if (gimple_phi_arg_def (phi, e->dest_idx))
> ! {
> ! gsi_next (&gsi);
> ! continue;
> ! }
> !
> ! /* We didn't find edge to update. This can happen for PHIs on virtuals
> ! since there is no control dependency relation on them. We are lost
> ! here and must force renaming of the symbol. */
> if (!is_gimple_reg (gimple_phi_result (phi)))
> {
> mark_virtual_phi_result_for_renaming (phi);
> remove_phi_node (&gsi, true);
> continue;
> }
> ! if (!e2)
> ! {
> ! op = gimple_phi_arg_def (phi, e->dest_idx == 0 ? 1 : 0);
> ! locus = gimple_phi_arg_location (phi, e->dest_idx == 0 ? 1 : 0);
> ! }
> ! else
> {
> ! op = gimple_phi_arg_def (phi, e2->dest_idx);
> ! locus = gimple_phi_arg_location (phi, e2->dest_idx);
> }
> add_phi_arg (phi, op, e, locus);
> ! gcc_assert (e2 || degenerate_phi_p (phi));
> gsi_next (&gsi);
> }
> }
> --- 950,976 ----
> tree op;
> source_location locus;
>
> ! /* PHIs for virtuals have no control dependency relation on them.
> ! We are lost here and must force renaming of the symbol. */
> if (!is_gimple_reg (gimple_phi_result (phi)))
> {
> mark_virtual_phi_result_for_renaming (phi);
> remove_phi_node (&gsi, true);
> continue;
> }
> !
> ! /* Dead PHI do not imply control dependency. */
> ! if (!gimple_plf (phi, STMT_NECESSARY))
> {
> ! gsi_next (&gsi);
> ! continue;
> }
> +
> + op = gimple_phi_arg_def (phi, e2->dest_idx);
> + locus = gimple_phi_arg_location (phi, e2->dest_idx);
> add_phi_arg (phi, op, e, locus);
> ! /* The resulting PHI if not dead can only be degenerate. */
> ! gcc_assert (degenerate_phi_p (phi));
> gsi_next (&gsi);
> }
> }
> *************** remove_dead_stmt (gimple_stmt_iterator *
> *** 1041,1047 ****
> edge e, e2;
> edge_iterator ei;
>
> ! post_dom_bb = get_live_post_dom (bb);
>
> e = find_edge (bb, post_dom_bb);
>
> --- 1006,1012 ----
> edge e, e2;
> edge_iterator ei;
>
> ! post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
>
> e = find_edge (bb, post_dom_bb);
>