This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH]: Code sinking


This patch was approved by Mark for 4.1 many months ago when we
discussed it for 4.0.
It is the code sinking patch, updated to the mainline (it does not
include the partial dead code elimination stuff, that will be submitted
as a followup).

I plan on committing it just as soon as mainline has a sane moment.

2004-12-03  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
Index: gcc/Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1449
diff -u -p -r1.1449 Makefile.in
--- gcc/Makefile.in	28 Feb 2005 13:25:38 -0000	1.1449
+++ gcc/Makefile.in	28 Feb 2005 21:10:41 -0000
@@ -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) $
 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
Index: gcc/common.opt
===================================================================
RCS file: /cvs/gcc/gcc/gcc/common.opt,v
retrieving revision 1.62
diff -u -p -r1.62 common.opt
--- gcc/common.opt	24 Feb 2005 09:24:13 -0000	1.62
+++ gcc/common.opt	28 Feb 2005 21:10:41 -0000
@@ -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
Index: gcc/opts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/opts.c,v
retrieving revision 1.94
diff -u -p -r1.94 opts.c
--- gcc/opts.c	24 Feb 2005 09:24:13 -0000	1.94
+++ gcc/opts.c	28 Feb 2005 21:10:41 -0000
@@ -501,6 +501,7 @@ decode_options (unsigned int argc, const
       flag_tree_sra = 1;
       flag_tree_copyrename = 1;
       flag_tree_fre = 1;
+      flag_tree_sink = 1;
 
       if (!optimize_size)
 	{
Index: gcc/timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.43
diff -u -p -r1.43 timevar.def
--- gcc/timevar.def	22 Jan 2005 12:53:21 -0000	1.43
+++ gcc/timevar.def	28 Feb 2005 21:10:41 -0000
@@ -79,6 +79,7 @@ DEFTIMEVAR (TV_TREE_SPLIT_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")
Index: gcc/tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.c,v
retrieving revision 2.12
diff -u -p -r2.12 tree-chrec.c
--- gcc/tree-chrec.c	9 Dec 2004 16:17:00 -0000	2.12
+++ gcc/tree-chrec.c	28 Feb 2005 21:10:42 -0000
@@ -388,13 +388,24 @@ chrec_fold_multiply (tree type, 
 static tree 
 tree_fold_factorial (tree f)
 {
+  int i, limit;
+  tree fact;
+
   if (tree_int_cst_sgn (f) <= 0)
     return integer_one_node;
-  else
-    return fold 
-      (build (MULT_EXPR, integer_type_node, f, 
-	      tree_fold_factorial (fold (build (MINUS_EXPR, integer_type_node, 
-						f, integer_one_node)))));
+
+  limit = tree_low_cst (f, 1);
+  fact = f;
+  for (i = limit; i > 1; i--)
+     {
+       tree itree = build_int_cst_type (integer_type_node, i);
+       fact = fold 
+	        (build (MULT_EXPR, integer_type_node, fact, 
+		        fold (
+			  build (MINUS_EXPR, integer_type_node, 
+				 itree, integer_one_node))));
+     }
+  return fact;
 }
 
 /* The binomial coefficient.  */
Index: gcc/tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.81
diff -u -p -r2.81 tree-flow.h
--- gcc/tree-flow.h	10 Feb 2005 00:32:44 -0000	2.81
+++ gcc/tree-flow.h	28 Feb 2005 21:10:42 -0000
@@ -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);
Index: gcc/tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.74
diff -u -p -r2.74 tree-optimize.c
--- gcc/tree-optimize.c	23 Feb 2005 05:08:23 -0000	2.74
+++ gcc/tree-optimize.c	28 Feb 2005 21:10:42 -0000
@@ -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);
Index: gcc/tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pass.h,v
retrieving revision 2.27
diff -u -p -r2.27 tree-pass.h
--- gcc/tree-pass.h	23 Feb 2005 05:08:23 -0000	2.27
+++ gcc/tree-pass.h	28 Feb 2005 21:10:42 -0000
@@ -164,6 +164,7 @@ extern struct tree_opt_pass pass_mark_us
 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;
 
Index: gcc/tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.72
diff -u -p -r2.72 tree-ssa-alias.c
--- gcc/tree-ssa-alias.c	26 Feb 2005 16:15:00 -0000	2.72
+++ gcc/tree-ssa-alias.c	28 Feb 2005 21:10:42 -0000
@@ -1645,7 +1645,6 @@ may_alias_p (tree ptr, HOST_WIDE_INT mem
       alias_stats.tbaa_resolved++;
       return false;
     }
-
   alias_stats.alias_mayalias++;
   return true;
 }
Index: gcc/tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dce.c,v
retrieving revision 2.32
diff -u -p -r2.32 tree-ssa-dce.c
--- gcc/tree-ssa-dce.c	17 Feb 2005 16:19:44 -0000	2.32
+++ gcc/tree-ssa-dce.c	28 Feb 2005 21:10:43 -0000
@@ -277,8 +277,6 @@ mark_operand_necessary (tree op, bool ph
 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 s
 	  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)
-    {
-      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 ();
+  if (is_hidden_global_store (stmt))
+    {
+      mark_stmt_necessary (stmt, true);
+      return;
     }
 
   return;
Index: gcc/doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.583
diff -u -p -r1.583 invoke.texi
--- gcc/doc/invoke.texi	24 Feb 2005 09:24:17 -0000	1.583
+++ gcc/doc/invoke.texi	28 Feb 2005 21:10:47 -0000
@@ -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
 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 t
 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.
Index: gcc/doc/passes.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/passes.texi,v
retrieving revision 1.50
diff -u -p -r1.50 passes.texi
--- gcc/doc/passes.texi	30 Jan 2005 15:36:08 -0000	1.50
+++ gcc/doc/passes.texi	28 Feb 2005 21:10:47 -0000
@@ -350,6 +350,12 @@ in @file{tree-ssa-dse.c} and is describe
 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
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-1.c
===================================================================
RCS file: gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-1.c
diff -N gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-1.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-1.c	28 Feb 2005 21:10:49 -0000
@@ -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"} } */
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-2.c
===================================================================
RCS file: gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-2.c
diff -N gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-2.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-2.c	28 Feb 2005 21:10:49 -0000
@@ -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"} } */
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-3.c
===================================================================
RCS file: gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-3.c
diff -N gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-3.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-3.c	28 Feb 2005 21:10:49 -0000
@@ -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"} } */
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-4.c
===================================================================
RCS file: gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-4.c
diff -N gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-4.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-4.c	28 Feb 2005 21:10:49 -0000
@@ -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"} } */

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]