[PATCH] Fix PR42717

[PATCH] Fix PR42717

[Richard Guenther]

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".

At least the following patch bootstraps and tests successfully
on x86_64-unknown-linux-gnu.  In the set of

compile.exp=pr40676.c
execute.exp=20010129-1.c
dg.exp=pr33673.c

you'll find interesting CFGs that I broke while working on
this 5th revision of the patch...

Comments?

Thanks.
Richard.

2010-01-15  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/42717
	* tree-ssa-dce.c (get_live_post_dom): Remove.
	(forward_edge_to_pdom): Fix detection of path to pdom.
	(remove_dead_stmt): Use the first post-dominator even if it
	does not contain live statements as redirection destination.
	Re-compute block reachability after making a region dead.
	(eliminate_unnecessary_stmts): Remove dead regions in
	dominator order.  Compute block reachability.

	* 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.orig	2010-01-15 23:17:56.000000000 +0100
--- gcc/tree-ssa-dce.c	2010-01-16 13:16:51.000000000 +0100
*************** 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 (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,953 ----
    if (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
! 	    /* From a dead region.  */
!  	    && !TEST_BIT (bb_contains_live_stmts, e2->src->index)
! 	    /* Dominated by the control stmt, thus the correct dead region.  */
! 	    && dominated_by_p (CDI_DOMINATORS, e2->src, e->src))
  	  break;
        for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (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);
  
--- 1024,1034 ----
        edge e, e2;
        edge_iterator ei;
  
!       if (!(bb->flags & BB_REACHABLE))
! 	return;
! 
!       /* Get the immediate post dominator of bb.  */
!       post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
  
        e = find_edge (bb, post_dom_bb);
  
*************** remove_dead_stmt (gimple_stmt_iterator *
*** 1075,1080 ****
--- 1062,1070 ----
  	  }
  	else
  	  ei_next (&ei);
+ 
+       /* Re-compute block reachability.  */
+       find_unreachable_blocks ();
      }
  
    unlink_stmt_vdef (stmt);
*************** eliminate_unnecessary_stmts (void)
*** 1094,1099 ****
--- 1084,1090 ----
    gimple stmt;
    tree call;
    VEC (basic_block, heap) *h;
+   unsigned i;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "\nEliminating unnecessary statements:\n");
*************** eliminate_unnecessary_stmts (void)
*** 1125,1130 ****
--- 1116,1143 ----
    gcc_assert (dom_info_available_p (CDI_DOMINATORS));
    h = get_all_dominated_blocks (CDI_DOMINATORS, single_succ (ENTRY_BLOCK_PTR));
  
+   /* Find unreachable blocks.  */
+   find_unreachable_blocks ();
+ 
+   /* First remove regions controlled by dead control statements.
+      It is necessary to do this in dominator order to first visit
+      the most dominating control statement of such regions.  */
+   for (i = 0; VEC_iterate (basic_block, h, i, bb); ++i)
+     {
+       gimple_stmt_iterator gsi;
+ 
+       gsi = gsi_last_bb (bb);
+       if (gsi_end_p (gsi))
+ 	continue;
+ 
+       /* If the control stmt in a block is dead, remove the controlled
+ 	 region.  */
+       stmt = gsi_stmt (gsi);
+       if (is_ctrl_stmt (stmt)
+ 	  && !gimple_plf (stmt, STMT_NECESSARY))
+ 	remove_dead_stmt (&gsi, bb);
+     }
+ 
    while (VEC_length (basic_block, h))
      {
        bb = VEC_pop (basic_block, h);

Re: [PATCH] Fix PR42717

[Richard Guenther]

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?

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);
  

Re: [PATCH] Fix PR42717

[Jan Hubicka]

> 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);
>   

Re: [PATCH] Fix PR42717

[Richard Guenther]

On Wed, 20 Jan 2010, Jan Hubicka wrote:

> > 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?

I think cfg-cleanup will take care of whatever is left to do.

> 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.

Indeed.

Thus, committed.

Richard.

> 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);
> >   
> 
> 

-- 
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex

Re: [PATCH] Fix PR42717

[H.J. Lu]

On Wed, Jan 20, 2010 at 4:26 AM, Richard Guenther <rguenther@suse.de> wrote:
> On Wed, 20 Jan 2010, Jan Hubicka wrote:
>
>> > 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?
>
> I think cfg-cleanup will take care of whatever is left to do.
>
>> 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.
>
> Indeed.
>
> Thus, committed.
>

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43367


-- 
H.J.