2005-07-12 Daniel Berlin <dberlin@dberlin.org>

	* tree-optimize.c (init_tree_optimization_passes): Add
	pass_eliminate_useless_stores pass.
	* tree-pass.h (pass_eliminate_useless_stores): New pass structure.
	* tree-ssa-pre.c (is_copy_stmt): New function.
	(follow_copies_till_vuse): Ditto.
	(do_eustores): Ditto.
	(gate_eustores): Ditto.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@102112 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 132 insertions, 0 deletions

diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index fbfda11cebe..67bc6d4dd58 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -2722,3 +2722,135 @@ struct tree_opt_pass pass_fre =
   TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
   0					/* letter */
 };
+
+/* Return true if T is a copy statement between two ssa names.  */
+
+static bool
+is_copy_stmt (tree t)
+{  
+  if (!t || TREE_CODE (t) != MODIFY_EXPR)
+    return false;
+  if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME 
+      && TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME)
+    return true;
+  return false;
+}
+
+/* Starting from START, walk copy statements till we hit a statement with a
+   VUSE or a non-copy statement.  */
+
+static tree 
+follow_copies_till_vuse (tree start)
+{
+  if (is_copy_stmt (start) && ZERO_SSA_OPERANDS (start, SSA_OP_VIRTUAL_USES))
+    {
+      tree rhs, defstmt;
+
+      rhs = TREE_OPERAND (start, 1);
+      defstmt = SSA_NAME_DEF_STMT (rhs);
+      return follow_copies_till_vuse (defstmt);
+    }
+  return start;
+}
+
+/* Gate and execute functions for eliminate useless stores.	
+   The goal here is to recognize the pattern *x = ... *x, and eliminate the
+   store because the value hasn't changed.  Store copy/const prop won't
+   do this because making *more* loads (IE propagating *x) is not a win, so it
+   ignores them.  
+   This pass is currently geared completely towards static variable store
+   elimination.  */
+
+static void
+do_eustores (void)
+{
+  basic_block bb;
+  /* For each basic block
+       For each statement (STMT) in the block
+         if STMT is a stores of the pattern *x = y
+           follow the chain of definitions for y, until we hit a non-copy
+	   statement or a statement with a vuse. 
+	     if the statement we arrive at is a vuse of the operand we killed,
+	     accessed through the same memory operation, then we have a
+	     useless store (because it is *x = ... = *x).  */
+	  
+  FOR_EACH_BB (bb)
+    {
+      block_stmt_iterator bsi;
+
+      for (bsi = bsi_start (bb);
+	   !bsi_end_p (bsi);)
+	{
+	  tree stmt = bsi_stmt (bsi);
+	  tree startat;
+	  tree kill;	  
+	  tree found;
+	  	  
+	  if (NUM_SSA_OPERANDS (stmt, SSA_OP_VMUSTDEF) != 1
+	      || TREE_CODE (stmt) != MODIFY_EXPR
+	      || TREE_CODE (TREE_OPERAND (stmt, 1)) != SSA_NAME)
+	    {
+	      bsi_next (&bsi);
+	      continue;
+	    }
+
+	  kill = MUSTDEF_KILL (MUSTDEF_OPS (stmt)); 
+	  startat = TREE_OPERAND (stmt, 1);
+	  startat = SSA_NAME_DEF_STMT (startat);
+	  found = follow_copies_till_vuse (startat);
+
+	  if (found && TREE_CODE (found) == MODIFY_EXPR)
+	    {	   
+
+	      /* We want exactly one virtual use, and it should match up with
+		 the use being killed.  */
+
+	      if (NUM_SSA_OPERANDS (found, SSA_OP_VUSE) != 1
+		  || VUSE_OP (VUSE_OPS (found)) != kill
+		  || !operand_equal_p (TREE_OPERAND (found, 1), 
+				       TREE_OPERAND (stmt, 0), 0))
+		{
+		  bsi_next (&bsi);
+		  continue;
+		}
+
+	      if (dump_file)
+		{
+		  fprintf (dump_file, "Eliminating useless store ");
+		  print_generic_stmt (dump_file, stmt, 0);
+		}
+	      mark_sym_for_renaming (TREE_OPERAND (stmt, 0));
+	      bsi_remove (&bsi);
+	    }
+	  else
+	    {
+	      bsi_next (&bsi);
+	      continue;
+	    }
+	}
+    }
+}
+
+static bool
+gate_eustores(void)
+{
+  return flag_unit_at_a_time != 0;
+}
+
+struct tree_opt_pass pass_eliminate_useless_stores =
+{
+  "eustores",				/* name */
+  gate_eustores,				/* gate */
+  do_eustores,				/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  0,				/* tv_id */
+  PROP_cfg | PROP_ssa | PROP_alias,	/* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  TODO_update_ssa | TODO_dump_func 
+  | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
+  0					/* letter */
+};