[PATCH][2/2] Improve DSE

[PATCH][2/2] Improve DSE

[Richard Biener]

This improves DSE by not stopping to look for a killing stmt at
the first may-alias but instead continue looking for a kill
(well, until we hit a may-use or run into limitations of the walker).

This fixes some embarrassing missing dead store eliminations
(it's also more expensive, but the walking is limited thus
it's O(1) anyway (haha)).

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Richard.

2014-06-04  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/60098
	* tree-ssa-dse.c (dse_possible_dead_store_p): Walk until
	we hit a kill.
	(dse_optimize_stmt): Simplify, now that we found a kill
	earlier.

	* gcc.dg/tree-ssa/ssa-dse-15.c: New testcase.

Index: gcc/tree-ssa-dse.c
===================================================================
*** gcc/tree-ssa-dse.c.orig	2014-05-06 16:15:43.030962178 +0200
--- gcc/tree-ssa-dse.c	2014-06-04 10:12:33.584954818 +0200
*************** dse_possible_dead_store_p (gimple stmt,
*** 198,207 ****
  	  break;
  	}
      }
!   /* We deliberately stop on clobbering statements and not only on
!      killing ones to make walking cheaper.  Otherwise we can just
!      continue walking until both stores have equal reference trees.  */
!   while (!stmt_may_clobber_ref_p (temp, gimple_assign_lhs (stmt)));
  
    *use_stmt = temp;
  
--- 198,205 ----
  	  break;
  	}
      }
!   /* Continue walking until we reach a kill.  */
!   while (!stmt_kills_ref_p (temp, gimple_assign_lhs (stmt)));
  
    *use_stmt = temp;
  
*************** dse_optimize_stmt (gimple_stmt_iterator
*** 248,304 ****
        if (!dse_possible_dead_store_p (stmt, &use_stmt))
  	return;
  
        /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
  	 another clobber stmt.  */
        if (gimple_clobber_p (stmt)
  	  && !gimple_clobber_p (use_stmt))
  	return;
  
!       /* If we have precisely one immediate use at this point and the
! 	 stores are to the same memory location or there is a chain of
! 	 virtual uses from stmt and the stmt which stores to that same
! 	 memory location, then we may have found redundant store.  */
!       if ((gimple_has_lhs (use_stmt)
! 	   && (operand_equal_p (gimple_assign_lhs (stmt),
! 				gimple_get_lhs (use_stmt), 0)))
! 	  || stmt_kills_ref_p (use_stmt, gimple_assign_lhs (stmt)))
! 	{
! 	  basic_block bb;
  
! 	  /* If use_stmt is or might be a nop assignment, e.g. for
! 	     struct { ... } S a, b, *p; ...
! 	     b = a; b = b;
! 	     or
! 	     b = a; b = *p; where p might be &b,
! 	     or
! 	     *p = a; *p = b; where p might be &b,
! 	     or
! 	     *p = *u; *p = *v; where p might be v, then USE_STMT
! 	     acts as a use as well as definition, so store in STMT
! 	     is not dead.  */
! 	  if (stmt != use_stmt
! 	      && ref_maybe_used_by_stmt_p (use_stmt, gimple_assign_lhs (stmt)))
! 	    return;
! 
! 	  if (dump_file && (dump_flags & TDF_DETAILS))
!             {
!               fprintf (dump_file, "  Deleted dead store '");
!               print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0);
!               fprintf (dump_file, "'\n");
!             }
! 
! 	  /* Then we need to fix the operand of the consuming stmt.  */
! 	  unlink_stmt_vdef (stmt);
! 
! 	  /* Remove the dead store.  */
! 	  bb = gimple_bb (stmt);
! 	  if (gsi_remove (gsi, true))
! 	    bitmap_set_bit (need_eh_cleanup, bb->index);
! 
! 	  /* And release any SSA_NAMEs set in this statement back to the
! 	     SSA_NAME manager.  */
! 	  release_defs (stmt);
  	}
      }
  }
  
--- 246,294 ----
        if (!dse_possible_dead_store_p (stmt, &use_stmt))
  	return;
  
+       /* Now we know that use_stmt kills the LHS of stmt.  */
+ 
        /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
  	 another clobber stmt.  */
        if (gimple_clobber_p (stmt)
  	  && !gimple_clobber_p (use_stmt))
  	return;
  
!       basic_block bb;
! 
!       /* If use_stmt is or might be a nop assignment, e.g. for
! 	   struct { ... } S a, b, *p; ...
! 	   b = a; b = b;
! 	 or
! 	   b = a; b = *p; where p might be &b,
! 	 or
!            *p = a; *p = b; where p might be &b,
! 	 or
!            *p = *u; *p = *v; where p might be v, then USE_STMT
!          acts as a use as well as definition, so store in STMT
!          is not dead.  */
!       if (stmt != use_stmt
! 	  && ref_maybe_used_by_stmt_p (use_stmt, gimple_assign_lhs (stmt)))
! 	return;
  
!       if (dump_file && (dump_flags & TDF_DETAILS))
! 	{
! 	  fprintf (dump_file, "  Deleted dead store '");
! 	  print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0);
! 	  fprintf (dump_file, "'\n");
  	}
+ 
+       /* Then we need to fix the operand of the consuming stmt.  */
+       unlink_stmt_vdef (stmt);
+ 
+       /* Remove the dead store.  */
+       bb = gimple_bb (stmt);
+       if (gsi_remove (gsi, true))
+ 	bitmap_set_bit (need_eh_cleanup, bb->index);
+ 
+       /* And release any SSA_NAMEs set in this statement back to the
+ 	 SSA_NAME manager.  */
+       release_defs (stmt);
      }
  }
  
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-15.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-15.c	2014-06-04 11:05:25.687736423 +0200
***************
*** 0 ****
--- 1,24 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-dse1-details" } */
+ 
+ void *foo (int *p)
+ {
+   void *q;
+   /* We should be able to DSE this store (p may point to errno).  */
+   *p = 0;
+   q = __builtin_malloc (4);
+   *p = 0;
+   return q;
+ }
+ 
+ int j;
+ void bar (int *i)
+ {
+   /* This store is dead as well.  */
+   j = 1;
+   *i = 0;
+   j = 2;
+ }
+ 
+ /* { dg-final { scan-tree-dump-times "Deleted dead store" 2 "dse1" } } */
+ /* { dg-final { cleanup-tree-dump "dse1" } } */