[tree-ssa] Copy propagation [patch]
Diego Novillo
dnovillo@redhat.com
Sat Mar 1 00:24:00 GMT 2003
I finally found time to adapt aldyh's copy propagation pass
(http://gcc.gnu.org/ml/gcc-patches/2002-11/msg01529.html). Not
surprisingly, this patch looks quite different from the original.
The original implementation was done before we rewrote the base
infrastructure.
This is arguably one of the simplest optimization passes in SSA.
All it does is traverse the flowgraph looking for variable loads.
For every variable X_i, it checks its unique reaching definition.
If the definition is of the form X_i = Y_j, it replaces X_i with
Y_j.
As Aldy pointed out, copy propagation can make two different
versions of the same variable live at the same time. For
instance,
tmp_1 = y_1;
if (...)
y_2 = ...
z_3 = tmp_1;
Copy propagation will change the last assignment to 'z_3 = y_1'.
Since we do not yet have a real SSA->normal pass, when the
program is converted to normal form, GCC generates the following:
tmp = y;
if (...)
y = ...
z = y;
The pass is obviously not enabled by default. My intention is to
use it to debug the SSA->normal pass that I'll be implementing
next (unless somebody beats me to it. Hi Jeff :).
Diego.
2003-02-28 Aldy Hernandez <aldyh@redhat.com>
Diego Novillo <dnovillo@redhat.com>
* Makefile.in (OBJS): Add tree-ssa-copyprop.o.
(tree-ssa-copyprop.o): New rule.
(tree-ssa-ccp.o): Add dependency on $(TREE_SIMPLE_H).
* timevar.def (TV_TREE_COPYPROP): New timevar.
* flags.h (flag_tree_copyprop): Declare.
* toplev.c (flag_tree_copyprop): Define.
(f_options): Add -ftree-copyprop.
* tree.h (tree_dump_index): Add TDI_copyprop.
* tree-dump.c (dump_files): Add entry for -fdump-tree-copyprop.
* doc/invoke.texi: Document -ftree-copyprop and -fdump-tree-copyprop.
* tree-ssa-copyprop.c: New file.
* tree-flow.h (tree_ssa_copyprop): Declare.
* tree-optimize.c (optimize_function_tree): Call it.
* tree-dfa.c (add_vuse): Make extern. Update all users.
* tree-ssa.c (mark_def_sites): VUSEs are stored in a varray of trees.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.75
diff -d -u -p -r1.903.2.75 Makefile.in
--- Makefile.in 23 Feb 2003 22:02:51 -0000 1.903.2.75
+++ Makefile.in 28 Feb 2003 22:16:53 -0000
@@ -785,7 +785,7 @@ C_OBJS = c-parse.o c-lang.o $(C_AND_OBJC
OBJS = tree-cfg.o tree-dfa.o tree-ssa.o tree-optimize.o tree-simple.o \
tree-alias-type.o gimplify.o tree-nomudflap.o tree-pretty-print.o \
tree-alias-common.o tree-ssa-ccp.o tree-browser.o @ANDER@ tree-ssa-dce.o \
- tree-ssa-pre.o \
+ tree-ssa-pre.o tree-ssa-copyprop.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o \
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o \
@@ -1652,7 +1652,10 @@ ssa-ccp.o : ssa-ccp.c $(CONFIG_H) system
errors.h $(GGC_H) df.h function.h
tree-ssa-ccp.o : tree-ssa-ccp.c $(CONFIG_H) system.h errors.h $(TREE_H) \
$(RTL_H) $(TM_P_H) $(TREE_FLOW_H) diagnostic.h tree-inline.h \
- $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H)
+ $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_SIMPLE_H)
+tree-ssa-copyprop.o : tree-ssa-copyprop.c $(CONFIG_H) system.h errors.h \
+ $(TREE_H) $(RTL_H) $(TM_P_H) $(TREE_FLOW_H) diagnostic.h $(TIMEVAR_H) \
+ $(TREE_DUMP_H) coretypes.h $(TREE_SIMPLE_H) $(TM_H)
df.o : df.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
insn-config.h $(RECOG_H) function.h $(REGS_H) $(OBSTACK_H) hard-reg-set.h \
$(BASIC_BLOCK_H) df.h $(FIBHEAP_H)
Index: flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.86.2.19
diff -d -u -p -r1.86.2.19 flags.h
--- flags.h 26 Feb 2003 16:26:03 -0000 1.86.2.19
+++ flags.h 28 Feb 2003 22:16:53 -0000
@@ -666,6 +666,9 @@ extern int flag_tree_cp;
/* Enable SSA-CCP on trees. */
extern int flag_tree_ccp;
+/* Enable SSA-Copy Propagation on trees. */
+extern int flag_tree_copyprop;
+
/* Enable SSA-DCE on trees. */
extern int flag_tree_dce;
Index: timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.14.2.9
diff -d -u -p -r1.14.2.9 timevar.def
--- timevar.def 3 Feb 2003 17:08:43 -0000 1.14.2.9
+++ timevar.def 28 Feb 2003 22:16:53 -0000
@@ -64,6 +64,7 @@ DEFTIMEVAR (TV_TREE_SSA_OTHER , "tr
DEFTIMEVAR (TV_TREE_DFA , "tree dataflow analysis")
DEFTIMEVAR (TV_TREE_CCP , "tree CCP")
DEFTIMEVAR (TV_TREE_PRE , "tree PRE")
+DEFTIMEVAR (TV_TREE_COPYPROP , "tree COPYPROP")
DEFTIMEVAR (TV_TREE_DCE , "tree DCE")
DEFTIMEVAR (TV_DOM_FRONTIERS , "dominance frontiers")
DEFTIMEVAR (TV_OVERLOAD , "overload resolution")
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.654.2.45
diff -d -u -p -r1.654.2.45 toplev.c
--- toplev.c 26 Feb 2003 16:26:03 -0000 1.654.2.45
+++ toplev.c 28 Feb 2003 22:16:53 -0000
@@ -908,6 +908,9 @@ int flag_tree_ccp = 0;
/* Enable SSA-CP on trees. */
int flag_tree_cp = 0;
+/* Enable SSA-Copy propagation on trees. */
+int flag_tree_copyprop;
+
/* Enable SSA-DCE on trees. */
int flag_tree_dce = 0;
@@ -1235,8 +1238,8 @@ static const lang_independent_options f_
N_("Enable SSA-PRE optimization on trees") },
{ "tree-ccp", &flag_tree_ccp, 1,
N_("Enable SSA-CCP optimization on trees") },
- { "tree-cp", &flag_tree_cp, 1,
- N_("Enable SSA-CP optimization on trees") },
+ { "tree-copyprop", &flag_tree_copyprop, 1,
+ N_("Enable SSA copy propagation optimization on trees") },
{ "tree-dce", &flag_tree_dce, 1,
N_("Enable SSA dead code elimination optimization on trees") }
};
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.84
diff -d -u -p -r1.1.4.84 tree-dfa.c
--- tree-dfa.c 28 Feb 2003 04:36:56 -0000 1.1.4.84
+++ tree-dfa.c 28 Feb 2003 22:16:53 -0000
@@ -104,7 +104,6 @@ static bool may_access_global_mem_p PAR
static void set_def PARAMS ((tree *, tree));
static void add_use PARAMS ((tree *, tree));
static void add_vdef PARAMS ((tree, tree, voperands_t));
-static void add_vuse PARAMS ((tree, tree, voperands_t));
static void add_stmt_operand PARAMS ((tree *, tree, int, int,
voperands_t));
static void add_immediate_use PARAMS ((tree, tree));
@@ -385,7 +384,7 @@ get_expr_operands (stmt, expr_p, is_def,
/* Add all the arguments to the function. If the function will not
clobber any local variable, check if it may dereference a local
pointer. If so, add a VUSE for the dereferenced pointer. This is
- to address the following problem: Supose that function 'foo' is
+ to address the following problem: Suppose that function 'foo' is
constant but receives a pointer to a local variable:
int foo (int *x)
@@ -751,7 +750,7 @@ add_vdef (var, stmt, prev_vops)
existing VUSE will be added to STMT. This is done to preserve the
SSA numbering of virtual operands. */
-static void
+void
add_vuse (var, stmt, prev_vops)
tree var;
tree stmt;
Index: tree-dump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dump.c,v
retrieving revision 1.6.2.23
diff -d -u -p -r1.6.2.23 tree-dump.c
--- tree-dump.c 23 Feb 2003 22:03:06 -0000 1.6.2.23
+++ tree-dump.c 28 Feb 2003 22:16:53 -0000
@@ -686,6 +686,7 @@ static struct dump_file_info dump_files[
{".ssa", "dump-tree-ssa", 0, 0},
{".ccp", "dump-tree-ccp", 0, 0},
{".pre", "dump-tree-pre", 0, 0},
+ {".copyprop", "dump-tree-copyprop", 0, 0},
{".dce", "dump-tree-dce", 0, 0},
{".optimized", "dump-tree-optimized", 0, 0},
{".xml", "dump-call-graph", 0, 0},
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.59
diff -d -u -p -r1.1.4.59 tree-flow.h
--- tree-flow.h 25 Feb 2003 13:28:24 -0000 1.1.4.59
+++ tree-flow.h 28 Feb 2003 22:16:53 -0000
@@ -378,6 +378,7 @@ extern tree copy_stmt PARAMS ((tree));
extern void dump_alias_info PARAMS ((FILE *));
extern void debug_alias_info PARAMS ((void));
extern tree get_virtual_var PARAMS ((tree));
+extern void add_vuse PARAMS ((tree, tree, voperands_t));
/* Flags used when computing reaching definitions and reached uses. */
#define TDFA_USE_OPS 1 << 0
@@ -405,6 +406,9 @@ void tree_ssa_ccp PARAMS ((tree));
/* In tree-ssa-dce.c */
void tree_ssa_dce PARAMS ((tree));
+
+/* In tree-ssa-copyprop.c */
+void tree_ssa_copyprop PARAMS ((tree));
#include "tree-flow-inline.h"
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-optimize.c,v
retrieving revision 1.1.4.32
diff -d -u -p -r1.1.4.32 tree-optimize.c
--- tree-optimize.c 23 Feb 2003 22:03:06 -0000 1.1.4.32
+++ tree-optimize.c 28 Feb 2003 22:16:53 -0000
@@ -78,6 +78,9 @@ optimize_function_tree (fndecl)
if (flag_tree_ccp)
tree_ssa_ccp (fndecl);
+ if (flag_tree_copyprop)
+ tree_ssa_copyprop (fndecl);
+
if (flag_tree_dce)
tree_ssa_dce (fndecl);
}
Index: tree-ssa-copyprop.c
===================================================================
RCS file: tree-ssa-copyprop.c
diff -N tree-ssa-copyprop.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tree-ssa-copyprop.c 28 Feb 2003 22:16:53 -0000
@@ -0,0 +1,237 @@
+/* SSA-Copy propagation for the GNU compiler.
+ Copyright (C) 2003 Free Software Foundation, Inc.
+ Contributed by Aldy Hernandez <aldy@quesejoda.com>
+ and Diego Novillo <dnovillo@redhat.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 2, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "errors.h"
+#include "ggc.h"
+#include "tree.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "timevar.h"
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-simple.h"
+#include "tree-dump.h"
+
+/* Local variables. */
+static FILE *dump_file;
+static int dump_flags;
+
+/* Local functions. */
+static void copyprop_stmt PARAMS ((tree));
+static void copyprop_phi PARAMS ((tree));
+static inline tree get_original PARAMS ((tree, tree *));
+
+
+/* Main entry point to the copy propagator. The algorithm is a simple
+ linear scan of the flowgraph. For every variable X_i used in the
+ function, it retrieves its unique reaching definition. If X_i's
+ definition is a copy (i.e., X_i = Y_j), then X_i is replaced with Y_j. */
+
+void
+tree_ssa_copyprop (fndecl)
+ tree fndecl;
+{
+ basic_block bb;
+
+ timevar_push (TV_TREE_COPYPROP);
+ dump_file = dump_begin (TDI_copyprop, &dump_flags);
+
+ /* Traverse every block in the flowgraph propagating copies in each
+ statement. */
+ FOR_EACH_BB (bb)
+ {
+ block_stmt_iterator si;
+ tree phi;
+
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ copyprop_phi (phi);
+
+ for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+ copyprop_stmt (bsi_stmt (si));
+ }
+
+ if (dump_file)
+ {
+ dump_end (TDI_copyprop, dump_file);
+ dump_function (TDI_copyprop, fndecl);
+ }
+
+ timevar_pop (TV_TREE_COPYPROP);
+}
+
+
+/* Propagate copies in statement STMT. If operand X_i in STMT is defined
+ by a statement of the form X_i = Y_j, replace the use of X_i with Y_j. */
+
+static void
+copyprop_stmt (stmt)
+ tree stmt;
+{
+ varray_type uses;
+ size_t i;
+ bool modified;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\nPropagating in statement: ");
+ print_generic_expr (dump_file, stmt, TDF_SLIM);
+ fprintf (dump_file, "\n");
+ }
+
+ get_stmt_operands (stmt);
+ modified = false;
+
+ /* Propagate real uses. */
+ uses = use_ops (stmt);
+ for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)
+ {
+ tree vuse;
+ tree *use_p = (tree *) VARRAY_GENERIC_PTR (uses, i);
+ tree orig = get_original (*use_p, &vuse);
+
+ if (orig)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\tReplacing ");
+ print_generic_expr (dump_file, *use_p, 0);
+ fprintf (dump_file, " with ");
+ print_generic_expr (dump_file, orig, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ *use_p = orig;
+ if (vuse)
+ add_vuse (vuse, stmt, NULL);
+ modified = true;
+ }
+ }
+
+ if (modified)
+ modify_stmt (stmt);
+}
+
+
+/* Propagate copies inside PHI node PHI. If argument X_i of PHI comes from
+ a definition of the form X_i = Y_j, replace it with Y_j. */
+
+static void
+copyprop_phi (phi)
+ tree phi;
+{
+ int i;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\nPropagating in PHI node: ");
+ print_generic_expr (dump_file, phi, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ {
+ tree vuse;
+ tree arg = PHI_ARG_DEF (phi, i);
+ tree orig = get_original (arg, &vuse);
+
+ if (orig)
+ {
+ if (dump_file && dump_flags & TDF_DETAILS)
+ {
+ fprintf (dump_file, "\tReplacing ");
+ print_generic_expr (dump_file, arg, 0);
+ fprintf (dump_file, " with ");
+ print_generic_expr (dump_file, orig, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ PHI_ARG_DEF (phi, i) = orig;
+ }
+ }
+}
+
+
+/* If the unique definition for VAR comes from an assignment of the form
+ VAR = ORIG, return ORIG. Otherwise, return NULL. If ORIG is an
+ INDIRECT_REF variable, *VUSE_P will contain the SSA name of ORIG's base
+ pointer. */
+
+static inline tree
+get_original (var, vuse_p)
+ tree var;
+ tree *vuse_p;
+{
+ tree def_stmt;
+
+ def_stmt = SSA_NAME_DEF_STMT (var);
+ *vuse_p = NULL_TREE;
+
+ /* FIXME. Pointers are not yet propagated. To do this, we need to
+ rewrite every pointer dereference from *VAR to *ORIG and re-scan all
+ the VDEFs and VUSEs for statements that dereference *VAR. */
+ if (POINTER_TYPE_P (TREE_TYPE (var)))
+ return NULL_TREE;
+
+ /* If VAR is not the LHS of its defining statement, it means that VAR is
+ defined by a VDEF node. This implies aliasing or structure updates.
+ For instance,
+
+ # a_2 = VDEF <a_1>
+ a.b = tmp_3;
+ return a_2;
+
+ If we allow tmp_3 to propagate into the 'return' statement, we would
+ be changing the return type of the function. */
+ if (TREE_CODE (def_stmt) == MODIFY_EXPR
+ && TREE_OPERAND (def_stmt, 0) == var
+ && TREE_CODE (TREE_OPERAND (def_stmt, 1)) == SSA_NAME)
+ {
+ tree orig = TREE_OPERAND (def_stmt, 1);
+
+ /* If the original variable is an INDIRECT_REF, then DEF_STMT will
+ contain a virtual use of the variable's base pointer. We also
+ need to copy that. */
+ if (TREE_CODE (SSA_NAME_VAR (orig)) == INDIRECT_REF)
+ {
+ size_t i;
+ varray_type vuses = vuse_ops (def_stmt);
+ tree base_ptr = TREE_OPERAND (SSA_NAME_VAR (orig), 0);
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (vuses); i++)
+ if (base_ptr == SSA_NAME_VAR (VARRAY_TREE (vuses, i)))
+ {
+ *vuse_p = VARRAY_TREE (vuses, i);
+ break;
+ }
+ }
+
+ return orig;
+ }
+
+ return NULL_TREE;
+}
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.54
diff -d -u -p -r1.1.4.54 tree-ssa.c
--- tree-ssa.c 26 Feb 2003 16:26:03 -0000 1.1.4.54
+++ tree-ssa.c 28 Feb 2003 22:16:53 -0000
@@ -382,7 +382,7 @@ mark_def_sites (idom, globals)
ops = vuse_ops (stmt);
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
- tree use = VARRAY_GENERIC_PTR (ops, i);
+ tree use = VARRAY_TREE (ops, i);
int uid = var_ann (use)->uid;
if (! TEST_BIT (kills, uid))
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.50
diff -d -u -p -r1.342.2.50 tree.h
--- tree.h 27 Feb 2003 18:30:02 -0000 1.342.2.50
+++ tree.h 28 Feb 2003 22:16:54 -0000
@@ -3489,6 +3489,8 @@ enum tree_dump_index
function. */
TDI_pre, /* dump SSA PRE information for each
function. */
+ TDI_copyprop, /* dump SSA Copy propagation information for
+ each function. */
TDI_dce, /* dump SSA DCE information for each
function. */
TDI_optimized, /* dump each function after optimizing it. */
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.152.2.35
diff -d -u -p -r1.152.2.35 invoke.texi
--- doc/invoke.texi 23 Feb 2003 22:03:32 -0000 1.152.2.35
+++ doc/invoke.texi 28 Feb 2003 22:16:55 -0000
@@ -300,7 +300,7 @@ in the following sections.
-fstrength-reduce -fstrict-aliasing -ftracer -fthread-jumps @gol
-funit-at-a-time -funroll-all-loops -funroll-loops -funswitch-loops @gol
-fdisable-simple -funroll-all-loops -funroll-loops @gol
--ftree-pre -ftree-ccp -ftree-dce -fdisable-tree-ssa @gol
+-ftree-pre -ftree-ccp -ftree-dce -ftree-copyprop -fdisable-tree-ssa @gol
--param @var{name}=@var{value}
-O -O0 -O1 -O2 -O3 -Os}
@@ -3363,6 +3363,11 @@ Dump each function before and after CCP.
Dump trees after partial redundancy elimination. The file name is made
by appending @file{.pre} to the source file name.
+@item copyprop
+@opindex fdump-tree-copyprop
+Dum trees after copy propagation pass. The file name is made by
+appending @file{.copyprop} to the source file name.
+
@item dce
@opindex fdump-tree-dce
Dump each function before and after DCE. The file name is made by appending
@@ -4034,6 +4039,10 @@ This option is only useful when debuggin
@item -ftree-pre
Perform Partial Redundancy Elimination (PRE) on trees. @emph{Note:} This
feature is under development and should not be used in this version of GCC.
+
+@item -ftree-copyprop
+Perform copy propagation on trees. @emph{Note:} This feature is under
+development and should not be used in this version of GCC.
@item -ftree-ccp
Perform sparse conditional constant propagation (CCP) on trees.
More information about the Gcc-patches
mailing list