[PATCH] Do not substitute and fold dead statements (but DCE them)

[Richard Guenther]

This patch makes the SSA propagator substitution and folding routine
not substitute into dead statements but instead DCEs them.  To be
efficient the basic-block walk is done from the end of the basic-block
to the start.

This should help reduce the amount of useless folding and substituting
we do in the face of copy chains during early optimization as well as
reduce the work of further stmt walks.

Two testcases need adjustment, as if we are folding a COND_EXPR that
ends the basic-block to a constant, the defining stmts of the COND_EXPR
operators get dead and we don't do the folding on it that was scanned
for, or, in the other case, an extra basic block is removed because
it only contained dead stmts.

The backward walk could be improved by also walking the CFG in the
optimal order, but I don't know if it is worth it as it would require
up-to-date dominator information.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

Ok for mainline?

Thanks,
Richard.

2008-03-20  Richard Guenther  <rguenther@suse.de>

	* tree-ssa-propagate.c (substitute_and_fold): Substitute
	statements in a basic-block with a backward walk.  Do not
	substitute into dead statements but instead remove those.

	* gcc.dg/fold-compare-2.c: Adjust testcase.
	* gcc.dg/tree-ssa/pr21086.c: Likewise.

Index: tree-ssa-propagate.c
===================================================================
--- tree-ssa-propagate.c	(revision 133342)
+++ tree-ssa-propagate.c	(working copy)
@@ -1211,10 +1211,12 @@ substitute_and_fold (prop_value_t *prop_
 	for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 	  replace_phi_args_in (phi, prop_value);
 
-      for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
+      /* Propagate known values into stmts.  Do a backward walk to expose
+	 more trivially deletable stmts.  */
+      for (i = bsi_last (bb); !bsi_end_p (i);)
 	{
           bool replaced_address, did_replace;
-	  tree prev_stmt = NULL;
+	  tree call, prev_stmt = NULL;
 	  tree stmt = bsi_stmt (i);
 
 	  /* Ignore ASSERT_EXPRs.  They are used by VRP to generate
@@ -1222,7 +1224,33 @@ substitute_and_fold (prop_value_t *prop_
 	     afterwards.  */
 	  if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 	      && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ASSERT_EXPR)
-	    continue;
+	    {
+	      bsi_prev (&i);
+	      continue;
+	    }
+
+	  /* No point propagating into a stmt whose result is not used,
+	     but instead we might be able to remove a trivially dead stmt.  */
+	  if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
+	      && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
+	      && !stmt_ann (stmt)->has_volatile_ops
+	      && has_zero_uses (GIMPLE_STMT_OPERAND (stmt, 0))
+	      && !tree_could_throw_p (stmt)
+	      && (!(call = get_call_expr_in (stmt))
+		  || !TREE_SIDE_EFFECTS (call)))
+	    {
+	      if (dump_file && dump_flags & TDF_DETAILS)
+		{
+		  fprintf (dump_file, "Removing dead stmt ");
+		  print_generic_expr (dump_file, stmt, 0);
+		  fprintf (dump_file, "\n");
+		}
+	      bsi_remove (&i, true);
+	      release_defs (stmt);
+	      if (!bsi_end_p (i))
+	        bsi_prev (&i);
+	      continue;
+	    }
 
 	  /* Record the state of the statement before replacements.  */
 	  push_stmt_changes (bsi_stmt_ptr (i));
@@ -1298,6 +1326,8 @@ substitute_and_fold (prop_value_t *prop_
 	     statement.  */
 	  if (use_ranges_p)
 	    simplify_stmt_using_ranges (stmt);
+
+	  bsi_prev (&i);
 	}
     }
 
Index: testsuite/gcc.dg/fold-compare-2.c
===================================================================
*** testsuite/gcc.dg/fold-compare-2.c	(revision 133367)
--- testsuite/gcc.dg/fold-compare-2.c	(working copy)
*************** main(void)
*** 15,20 ****
    return 0;
  }
  
! /* { dg-final { scan-tree-dump-times "Removing basic block" 1 "vrp1" } } */
  /* { dg-final { cleanup-tree-dump "vrp\[1-2\]" } } */
  
--- 15,20 ----
    return 0;
  }
  
! /* { dg-final { scan-tree-dump-times "Removing basic block" 2 "vrp1" } } */
  /* { dg-final { cleanup-tree-dump "vrp\[1-2\]" } } */
  
Index: testsuite/gcc.dg/tree-ssa/pr21086.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/pr21086.c	(revision 133367)
--- testsuite/gcc.dg/tree-ssa/pr21086.c	(working copy)
*************** foo (int *p)
*** 15,19 ****
      return 0;
  }
  
! /* { dg-final { scan-tree-dump-times "Folding predicate " 2 "vrp1" } } */
  /* { dg-final { cleanup-tree-dump "vrp1" } } */
--- 15,20 ----
      return 0;
  }
  
! /* { dg-final { scan-tree-dump-times "Folding predicate " 1 "vrp1" } } */
! /* { dg-final { scan-tree-dump-not "b_. =" "vrp1" } } */
  /* { dg-final { cleanup-tree-dump "vrp1" } } */