This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH]: Code sinking
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 28 Feb 2005 16:28:08 -0500
- Subject: [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"} } */