2005-03-01 Daniel Berlin <dberlin@dberlin.org>

	* Makefile.in (tree-ssa-sink.o): New.
	(OBJS-common): Add tree-ssa-sink.o.
	* common.opt: Add -ftree-sink
	* opts.c (decode_options): flag_tree_sink is set at O1 or higher.
	* timevar.def (TV_TREE_SINK): new timevar.
	* tree-flow.h (is_hidden_global_store): Prototype.
	* tree-optimize.c (init_tree_optimization_passes): Add
	pass_sink_code.
	* tree-pass.h (pass_sink_code): New.
	* tree-ssa-dce.c (mark_stmt_if_obviously_necessary): Move checking
	for non-obvious global store store to is_hidden_global_store, and
	call that new function.
	* tree-ssa-sink.c: New file.
	* doc/invoke.texi: Document -fdump-tree-sink and -ftree-sink.
	* doc/passes.texi: Document forward store motion.
	* testsuite/gcc.dg/tree-ssa/ssa-sink-1.c: New test
	* testsuite/gcc.dg/tree-ssa/ssa-sink-2.c: New test
	* testsuite/gcc.dg/tree-ssa/ssa-sink-3.c: New test
	* testsuite/gcc.dg/tree-ssa/ssa-sink-4.c: New test


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

15 files changed, 114 insertions, 75 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index a28f1bf7c40..03f63c8e90b 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,25 @@
+2005-03-01  Daniel Berlin <dberlin@dberlin.org>
+
+	* Makefile.in (tree-ssa-sink.o): New.
+	(OBJS-common): Add tree-ssa-sink.o.
+	* common.opt: Add -ftree-sink
+	* opts.c (decode_options): flag_tree_sink is set at O1 or higher.
+	* timevar.def (TV_TREE_SINK): new timevar.
+	* tree-flow.h (is_hidden_global_store): Prototype.
+	* tree-optimize.c (init_tree_optimization_passes): Add
+	pass_sink_code.
+	* tree-pass.h (pass_sink_code): New.
+	* tree-ssa-dce.c (mark_stmt_if_obviously_necessary): Move checking
+	for non-obvious global store store to is_hidden_global_store, and
+	call that new function.
+	* tree-ssa-sink.c: New file.
+	* doc/invoke.texi: Document -fdump-tree-sink and -ftree-sink.
+	* doc/passes.texi: Document forward store motion.
+	* testsuite/gcc.dg/tree-ssa/ssa-sink-1.c: New test
+	* testsuite/gcc.dg/tree-ssa/ssa-sink-2.c: New test
+	* testsuite/gcc.dg/tree-ssa/ssa-sink-3.c: New test
+	* testsuite/gcc.dg/tree-ssa/ssa-sink-4.c: New test
+
 2005-03-01  Per Bothner  <per@bothner.com>
 
 	* diagnostic.c (diagnostic_build_prefix): If USE_MAPPED_LOCATION
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 22f68338af3..2083750b4ef 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -935,7 +935,7 @@ OBJS-common = \
  varasm.o varray.o vec.o version.o vmsdbgout.o xcoffout.o alloc-pool.o	   \
  et-forest.o cfghooks.o bt-load.o pretty-print.o $(GGC) web.o passes.o	   \
  rtl-profile.o tree-profile.o rtlhooks.o cfgexpand.o lambda-mat.o          \
- lambda-trans.o	lambda-code.o tree-loop-linear.o
+ lambda-trans.o	lambda-code.o tree-loop-linear.o tree-ssa-sink.o
 
 OBJS-md = $(out_object_file)
 OBJS-archive = $(EXTRA_OBJS) $(host_hook_obj) tree-inline.o		   \
@@ -1673,6 +1673,10 @@ tree-cfg.o : tree-cfg.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
 tree-tailcall.o : tree-tailcall.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
    $(RTL_H) $(TREE_H) $(TM_P_H) function.h $(TM_H) coretypes.h \
    $(TREE_DUMP_H) diagnostic.h except.h tree-pass.h $(FLAGS_H) langhooks.h
+tree-ssa-sink.o : tree-ssa-sink.c $(TREE_FLOW_H) $(CONFIG_H) \
+   $(SYSTEM_H) $(TREE_H) $(TM_P_H) $(EXPR_H) \
+   $(GGC_H) output.h diagnostic.h errors.h toplev.h $(TIMEVAR_H) \
+   $(TM_H) coretypes.h $(TREE_DUMP_H) tree-pass.h $(FLAGS_H)
 tree-nested.o: tree-nested.c $(CONFIG_H) $(SYSTEM_H) $(TM_H) $(TREE_H) \
    $(RTL_H) $(TM_P_H) function.h tree-dump.h tree-inline.h tree-iterator.h \
    tree-gimple.h $(CGRAPH_H) $(EXPR_H) langhooks.h $(GGC_H) gt-tree-nested.h
diff --git a/gcc/common.opt b/gcc/common.opt
index f94643d509e..b10c0e998e5 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -872,6 +872,10 @@ ftree-pre
 Common Report Var(flag_tree_pre)
 Enable SSA-PRE optimization on trees
 
+ftree-sink
+Common Report Var(flag_tree_sink)
+Enable SSA code sinking on trees
+
 ftree-sra
 Common Report Var(flag_tree_sra)
 Perform scalar replacement of aggregates
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 8cf5ed9493f..891b38445f7 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -264,6 +264,7 @@ Objective-C and Objective-C++ Dialects}.
 -fdump-tree-forwprop@r{[}-@var{n}@r{]} @gol
 -fdump-tree-copyrename@r{[}-@var{n}@r{]} @gol
 -fdump-tree-nrv -fdump-tree-vect @gol
+-fdump-tree-sink @gol
 -fdump-tree-sra@r{[}-@var{n}@r{]} @gol
 -fdump-tree-fre@r{[}-@var{n}@r{]} @gol
 -ftree-vectorizer-verbose=@var{n} @gol
@@ -319,7 +320,7 @@ Objective-C and Objective-C++ Dialects}.
 -fvariable-expansion-in-unroller @gol
 -ftree-pre  -ftree-ccp  -ftree-dce -ftree-loop-optimize @gol
 -ftree-loop-linear -ftree-loop-im -ftree-loop-ivcanon -fivopts @gol
--ftree-dominator-opts -ftree-dse -ftree-copyrename @gol
+-ftree-dominator-opts -ftree-dse -ftree-copyrename -ftree-sink @gol
 -ftree-ch -ftree-sra -ftree-ter -ftree-lrs -ftree-fre -ftree-vectorize @gol
 --param @var{name}=@var{value}
 -O  -O0  -O1  -O2  -O3  -Os}
@@ -3843,6 +3844,11 @@ made by appending @file{.mudflap} to the source file name.
 Dump each function after performing scalar replacement of aggregates.  The
 file name is made by appending @file{.sra} to the source file name.
 
+@item sink
+@opindex fdump-tree-sink
+Dump each function after performing code sinking.  The file name is made
+by appending @file{.sink} to the source file name. 
+
 @item dom
 @opindex fdump-tree-dom
 Dump each function after applying dominator tree optimizations.  The file
@@ -4679,6 +4685,10 @@ that are computed on all paths leading to the redundant computation.
 This analysis faster than PRE, though it exposes fewer redundancies.
 This flag is enabled by default at @option{-O} and higher.
 
+@item -ftree-sink
+Perform forward store motion  on trees.  This flag is
+enabled by default at @option{-O} and higher.
+
 @item -ftree-ccp
 Perform sparse conditional constant propagation (CCP) on trees.  This flag
 is enabled by default at @option{-O} and higher.
diff --git a/gcc/doc/passes.texi b/gcc/doc/passes.texi
index af11f725a43..fd4e323d90a 100644
--- a/gcc/doc/passes.texi
+++ b/gcc/doc/passes.texi
@@ -350,6 +350,12 @@ in @file{tree-ssa-dse.c} and is described by @code{pass_dse}.
 This pass transforms tail recursion into a loop.  It is located in
 @file{tree-tailcall.c} and is described by @code{pass_tail_recursion}.
 
+@item Forward store motion
+
+This pass sinks stores and assignments down the flowgraph closer to it's
+use point.  The pass is located in @file{tree-ssa-sink.c} and is
+described by @code{pass_sink_code}
+
 @item Partial redundancy elimination
 
 This pass eliminates partially redundant computations, as well as
diff --git a/gcc/opts.c b/gcc/opts.c
index fcb8f6d5c1a..9ab16f0f562 100644
--- a/gcc/opts.c
+++ b/gcc/opts.c
@@ -501,6 +501,7 @@ decode_options (unsigned int argc, const char **argv)
       flag_tree_sra = 1;
       flag_tree_copyrename = 1;
       flag_tree_fre = 1;
+      flag_tree_sink = 1;
 
       if (!optimize_size)
 	{
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-1.c
new file mode 100644
index 00000000000..0bee06c87f0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-1.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -fdump-tree-sink-stats" } */
+int
+foo (int a, int b, int c)
+{
+  int x = a * b;
+  return c ? x : a;
+}
+/* We should sink the x = a * b calculation into the branch that returns x. */
+/* { dg-final { scan-tree-dump-times "Sunk statements:1" 1 "sink"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-2.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-2.c
new file mode 100644
index 00000000000..f8c4d13582b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-2.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -fdump-tree-sink-stats" } */
+int
+bar (int a, int b, int c)
+{
+  int y = a * b;
+  if (c)
+    y = 12;
+  return y;
+}
+/* We should sink the x = a * b calculation into the else branch  */
+/* { dg-final { scan-tree-dump-times "Sunk statements:1" 1 "sink"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-3.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-3.c
new file mode 100644
index 00000000000..d0052c945f4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-3.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -fdump-tree-sink-stats" } */
+extern void foo(int a);
+int
+main (int argc)
+{
+  int a;
+  a = argc + 1;
+  if (argc + 3)
+    {
+      foo (a);
+    }
+}
+/* We should sink the a = argc + 1 calculation into the if branch  */
+/* { dg-final { scan-tree-dump-times "Sunk statements:1" 1 "sink"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-4.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-4.c
new file mode 100644
index 00000000000..d7b4dd14dcf
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-4.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -fdump-tree-sink-stats" } */
+extern int foo (int *, int *);
+extern int foo2 (int);
+int
+main (int argc)
+{
+  int a, b, c;
+  b = argc + 1;
+  c = argc + 2;
+  a = b + c;
+  if (argc)
+    {
+      foo (&b, &c);
+      a = b + c;
+    }
+  foo2 (a);
+}
+/* We should sink the first a = b + c calculation into the else branch  */
+/* { dg-final { scan-tree-dump-times "Sunk statements:1" 1 "sink"} } */
diff --git a/gcc/timevar.def b/gcc/timevar.def
index e116f4bbfb2..3df7c25ed51 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -79,6 +79,7 @@ DEFTIMEVAR (TV_TREE_SPLIT_EDGES      , "tree split crit edges")
 DEFTIMEVAR (TV_TREE_PRE		     , "tree PRE")
 DEFTIMEVAR (TV_TREE_REDPHI	     , "tree remove redundant PHIs")
 DEFTIMEVAR (TV_TREE_FRE		     , "tree FRE")
+DEFTIMEVAR (TV_TREE_SINK             , "tree code sinking")
 DEFTIMEVAR (TV_TREE_PHIOPT	     , "tree linearize phis")
 DEFTIMEVAR (TV_TREE_FORWPROP	     , "tree forward propagate")
 DEFTIMEVAR (TV_TREE_DCE		     , "tree conservative DCE")
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index 80ad68680a8..82402c27a0f 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -736,6 +736,8 @@ tree vn_lookup (tree, vuse_optype);
 void vn_init (void);
 void vn_delete (void);
 
+/* In tree-ssa-sink.c  */
+bool is_hidden_global_store (tree);
 
 /* In tree-sra.c  */
 void insert_edge_copies (tree, basic_block);
diff --git a/gcc/tree-optimize.c b/gcc/tree-optimize.c
index f4ad9669ef4..f934c997594 100644
--- a/gcc/tree-optimize.c
+++ b/gcc/tree-optimize.c
@@ -384,6 +384,7 @@ init_tree_optimization_passes (void)
   NEXT_PASS (pass_may_alias);
   NEXT_PASS (pass_split_crit_edges);
   NEXT_PASS (pass_pre);
+  NEXT_PASS (pass_sink_code);
   NEXT_PASS (pass_loop);
   NEXT_PASS (pass_dominator);
   NEXT_PASS (pass_redundant_phi);
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index bf818091264..30c7dd29a16 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -164,6 +164,7 @@ extern struct tree_opt_pass pass_mark_used_blocks;
 extern struct tree_opt_pass pass_rename_ssa_copies;
 extern struct tree_opt_pass pass_expand;
 extern struct tree_opt_pass pass_rest_of_compilation;
+extern struct tree_opt_pass pass_sink_code;
 extern struct tree_opt_pass pass_fre;
 extern struct tree_opt_pass pass_linear_transform;
 
diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c
index 16b9d480a49..69408e8cd7d 100644
--- a/gcc/tree-ssa-dce.c
+++ b/gcc/tree-ssa-dce.c
@@ -277,8 +277,6 @@ mark_operand_necessary (tree op, bool phionly)
 static void
 mark_stmt_if_obviously_necessary (tree stmt, bool aggressive)
 {
-  v_may_def_optype v_may_defs;
-  v_must_def_optype v_must_defs;
   stmt_ann_t ann;
   tree op, def;
   ssa_op_iter iter;
@@ -368,78 +366,10 @@ mark_stmt_if_obviously_necessary (tree stmt, bool aggressive)
 	  return;
         }
     }
-
-  /* Check virtual definitions.  If we get here, the only virtual
-     definitions we should see are those generated by assignment
-     statements.  */
-  v_may_defs = V_MAY_DEF_OPS (ann);
-  v_must_defs = V_MUST_DEF_OPS (ann);
-  if (NUM_V_MAY_DEFS (v_may_defs) > 0 || NUM_V_MUST_DEFS (v_must_defs) > 0)
+  if (is_hidden_global_store (stmt))
     {
-      tree lhs;
-
-      gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
-
-      /* Note that we must not check the individual virtual operands
-	 here.  In particular, if this is an aliased store, we could
-	 end up with something like the following (SSA notation
-	 redacted for brevity):
-
-	 	foo (int *p, int i)
-		{
-		  int x;
-		  p_1 = (i_2 > 3) ? &x : p_1;
-
-		  # x_4 = V_MAY_DEF <x_3>
-		  *p_1 = 5;
-
-		  return 2;
-		}
-
-	 Notice that the store to '*p_1' should be preserved, if we
-	 were to check the virtual definitions in that store, we would
-	 not mark it needed.  This is because 'x' is not a global
-	 variable.
-
-	 Therefore, we check the base address of the LHS.  If the
-	 address is a pointer, we check if its name tag or type tag is
-	 a global variable.  Otherwise, we check if the base variable
-	 is a global.  */
-      lhs = TREE_OPERAND (stmt, 0);
-      if (REFERENCE_CLASS_P (lhs))
-	lhs = get_base_address (lhs);
-
-      if (lhs == NULL_TREE)
-	{
-	  /* If LHS is NULL, it means that we couldn't get the base
-	     address of the reference.  In which case, we should not
-	     remove this store.  */
-	  mark_stmt_necessary (stmt, true);
-	}
-      else if (DECL_P (lhs))
-	{
-	  /* If the store is to a global symbol, we need to keep it.  */
-	  if (is_global_var (lhs))
-	    mark_stmt_necessary (stmt, true);
-	}
-      else if (INDIRECT_REF_P (lhs))
-	{
-	  tree ptr = TREE_OPERAND (lhs, 0);
-	  struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
-	  tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
-	  tree tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
-
-	  /* If either the name tag or the type tag for PTR is a
-	     global variable, then the store is necessary.  */
-	  if ((nmt && is_global_var (nmt))
-	      || (tmt && is_global_var (tmt)))
-	    {
-	      mark_stmt_necessary (stmt, true);
-	      return;
-	    }
-	}
-      else
-	gcc_unreachable ();
+      mark_stmt_necessary (stmt, true);
+      return;
     }
 
   return;