[PATCH] Implement redundant store elimination, fix PR38513

[Richard Guenther <rguenther at suse dot de>]

This implements redundant store elimination (just like postreload CSE 
does) from within FRE.  It triggers quite some time for C++ code and
also breaks the following testcases for now

FAIL: g++.dg/warn/Warray-bounds.C  (test for warnings, line 32)
FAIL: g++.dg/warn/Warray-bounds.C  (test for warnings, line 43)
FAIL: g++.dg/warn/Warray-bounds.C  (test for warnings, line 54)

FAIL: gcc.dg/Warray-bounds.c  (test for warnings, line 32)
FAIL: gcc.dg/Warray-bounds.c  (test for warnings, line 43)
FAIL: gcc.dg/Warray-bounds.c  (test for warnings, line 54)
FAIL: gcc.dg/vect/vect-35.c scan-tree-dump-times vect "vectorized 1 loops" 1
FAIL: gcc.dg/vect/vect-multitypes-16.c scan-tree-dump-times vect 
"vectorized 1 loops" 1
FAIL: gcc.dg/vect/vect-multitypes-17.c scan-tree-dump-times vect 
"vectorized 1 loops" 1
FAIL: gcc.dg/vect/vect-reduc-dot-u8b.c scan-tree-dump-times vect 
"vectorized 1 loops" 1
FAIL: gcc.dg/vect/slp-widen-mult-u8.c scan-tree-dump-times vect 
"vectorized 1 loops" 1
FAIL: gcc.dg/vect/wrapv-vect-reduc-dot-s8b.c scan-tree-dump-times vect 
"vectorized 1 loops" 1

because all of them test for something on redundant stores that are
now removed.  Before applying the patch I need to sort them out, but
I am just posting the patch now as it works and do that work later.

Otherwise bootstrapped and tested on x86_64-unknown-linux-gnu.

Thanks,
Richard.

2008-12-29  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/38513
	* tree-ssa-pre.c (eliminate): Remove redundant stores.

	* gcc.dg/tree-ssa/ssa-fre-18.c: New testcase.
	* gcc.dg/tree-ssa/ssa-dse-11.c: Adjust.

Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-18.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-18.c	(revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-18.c	(revision 0)
***************
*** 0 ****
--- 1,26 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-fre" } */
+ 
+ struct f {
+   float a;
+   float b;
+   float c;
+   float d;
+ };
+ 
+ struct f a;
+ 
+ void h(float, float, float, float);
+ 
+ void g(void)
+ {
+   float a1 = a.a, b = a.b, c = a.c, d = a.d;
+   a.a = a1;
+   a.b = b;
+   a.c = c;
+   a.d = d;
+   h(a1, b, c, d);
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "a\\\.? = " "fre" } } */
+ /* { dg-final { cleanup-tree-dump "fre" } } */
Index: gcc/tree-ssa-pre.c
===================================================================
*** gcc/tree-ssa-pre.c	(revision 142949)
--- gcc/tree-ssa-pre.c	(working copy)
*************** eliminate (void)
*** 3848,3854 ****
      {
        gimple_stmt_iterator i;
  
!       for (i = gsi_start_bb (b); !gsi_end_p (i); gsi_next (&i))
  	{
  	  gimple stmt = gsi_stmt (i);
  
--- 3848,3854 ----
      {
        gimple_stmt_iterator i;
  
!       for (i = gsi_start_bb (b); !gsi_end_p (i);)
  	{
  	  gimple stmt = gsi_stmt (i);
  
*************** eliminate (void)
*** 3906,3911 ****
--- 3906,3912 ----
  		  propagate_tree_value_into_stmt (&i, sprime);
  		  stmt = gsi_stmt (i);
  		  update_stmt (stmt);
+ 		  gsi_next (&i);
  		  continue;
  		}
  
*************** eliminate (void)
*** 3966,3971 ****
--- 3967,4014 ----
  		    }
  		}
  	    }
+ 	  /* If the statement is a scalar store, see if the expression
+ 	     has the same value number as its rhs.  If so, the store is
+ 	     dead.  */
+ 	  else if (gimple_assign_single_p (stmt)
+ 		   && !is_gimple_reg (gimple_assign_lhs (stmt))
+ 		   && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
+ 		       || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
+ 	    {
+ 	      tree rhs = gimple_assign_rhs1 (stmt);
+ 	      tree val;
+ 	      val = vn_reference_lookup (gimple_assign_lhs (stmt),
+ 					 shared_vuses_from_stmt (stmt),
+ 					 true, NULL);
+ 	      if (TREE_CODE (rhs) == SSA_NAME)
+ 		rhs = VN_INFO (rhs)->valnum;
+ 	      if (val
+ 		  && operand_equal_p (val, rhs, 0))
+ 		{
+ 		  def_operand_p def;
+ 		  use_operand_p use;
+ 		  vuse_vec_p usevec;
+ 		  ssa_op_iter oi;
+ 		  imm_use_iterator ui;
+ 		  gimple use_stmt;
+ 
+ 		  if (dump_file && (dump_flags & TDF_DETAILS))
+ 		    {
+ 		      fprintf (dump_file, "Deleted dead store ");
+ 		      print_gimple_stmt (dump_file, stmt, 0, 0);
+ 		    }
+ 
+ 		  /* Propagate all may-uses to the uses of their defs.  */
+ 		  FOR_EACH_SSA_VDEF_OPERAND (def, usevec, stmt, oi)
+ 		    FOR_EACH_IMM_USE_STMT (use_stmt, ui, DEF_FROM_PTR (def))
+ 		      FOR_EACH_IMM_USE_ON_STMT (use, ui)
+ 		        SET_USE (use, VUSE_ELEMENT_VAR (*usevec, 0));
+ 
+ 		  gsi_remove (&i, true);
+ 		  release_defs (stmt);
+ 		  continue;
+ 		}
+ 	    }
  	  /* Visit COND_EXPRs and fold the comparison with the
  	     available value-numbers.  */
  	  else if (gimple_code (stmt) == GIMPLE_COND)
*************** eliminate (void)
*** 3990,3995 ****
--- 4033,4040 ----
  		  todo = TODO_cleanup_cfg;
  		}
  	    }
+ 
+ 	  gsi_next (&i);
  	}
      }
  
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-11.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-11.c	(revision 142949)
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-11.c	(working copy)
*************** void foo(int *p)
*** 6,18 ****
  {
    while (1)
     {
!       *p = 0;
        *p = 0;
     }
  }
  void bar(int *p)
  {
!   *p = 0;
    *p = 0;
    abort ();
  }
--- 6,18 ----
  {
    while (1)
     {
!       *p = 1;
        *p = 0;
     }
  }
  void bar(int *p)
  {
!   *p = 1;
    *p = 0;
    abort ();
  }