[PATCH] Fix PR42717

[Richard Guenther <rguenther at suse dot de>]

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