This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] copy-propagation pass
- From: Aldy Hernandez <aldyh at redhat dot com>
- To: dnovillo at redhat dot com, gcc-patches at gcc dot gnu dot org
- Date: Mon, 25 Nov 2002 10:25:13 -0800
- Subject: [tree-ssa] copy-propagation pass
Howdy all.
Here is a preliminary patch for copy-propagation on trees.
In talking with Diego, we have found one big problem, which is:
a = y;
y = z;
if (a)
blah;
Under the current infrastructure, we'd propagate a=y on if(a) which is
wrong because Y has been killed after the definition of A. I have a
hackaround that fails on:
orig_y = y;
while (blah) {
z = orig_y;
y = 5;
}
Diego has batted a few ideas about how to fix this (computing life
information, etc), which I'll take a look at early next week, but I
wanted to get something out there before the Thanksgiving thinggie.
Once this is fixed, and DCE is working in tandem, we should be able to
speed up the compiler-- I'm hoping considerably.
How does this look?
Aldy
2002-11-25 Aldy Hernandez <aldyh@redhat.com>
* doc/invoke.texi (Option Summary): Add -ftree-copyprop.
(Debugging Options): Document fdump-tree-copyprop.
(Optimize Options): Document ftree-copyprop.
* varray.h (VARRAY_N): New.
(VARRAY_N_TREE): New.
* tree-dump.c (dump_files): Add copyprop entry.
* tree.h (enum tree_dump_index): Add TDI_copyprop.
* tree-flow.h (tree_ssa_copy_propagation): New prototype.
* flags.h (flag_tree_copyprop): New extern.
* timevar.def: Add TV_TREE_COPYPROP.
* toplev.c (flag_tree_copyprop): New variable.
(f_options): Add tree copy propagation pass.
* tree-optimize.c (optimize_function_tree): Call
tree_ssa_copy_propagation.
* Makefile.in (OBJS): Add tree-ssa-copyprop.o.
(tree-ssa-copyprop.o): New dependency.
* tree-ssa-copyprop.c: New file.
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.152.2.23
diff -c -p -r1.152.2.23 invoke.texi
*** doc/invoke.texi 6 Nov 2002 12:21:30 -0000 1.152.2.23
--- doc/invoke.texi 25 Nov 2002 18:21:24 -0000
*************** in the following sections.
*** 298,304 ****
-fstrength-reduce -fstrict-aliasing -ftracer -fthread-jumps @gol
-ftrapv -funroll-all-loops -funroll-loops @gol
-fdisable-simple -funroll-all-loops -funroll-loops @gol
! -ftree-pre -ftree-ccp -ftree-dce @gol
--param @var{name}=@var{value}
-O -O0 -O1 -O2 -O3 -Os}
--- 298,304 ----
-fstrength-reduce -fstrict-aliasing -ftracer -fthread-jumps @gol
-ftrapv -funroll-all-loops -funroll-loops @gol
-fdisable-simple -funroll-all-loops -funroll-loops @gol
! -ftree-pre -ftree-ccp -ftree-dce -ftree-copyprop @gol
--param @var{name}=@var{value}
-O -O0 -O1 -O2 -O3 -Os}
*************** Dump each function before and after CCP.
*** 3292,3297 ****
--- 3292,3302 ----
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
*************** debugging the tree simplification pass i
*** 3959,3964 ****
--- 3964,3973 ----
@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. 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.
Index: varray.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/varray.h,v
retrieving revision 1.28
diff -c -p -r1.28 varray.h
*** varray.h 4 Jun 2002 07:08:18 -0000 1.28
--- varray.h 25 Nov 2002 18:21:25 -0000
*************** extern void varray_check_failed PARAMS (
*** 255,260 ****
--- 255,264 ----
#define VARRAY_TOP(VA, T) \
((VA)->data.T[(VA)->elements_used - 1])
+ /* Return element N of VA. */
+ #define VARRAY_N(VA, T, N) \
+ ((VA)->data.T[N])
+
#define VARRAY_CHAR(VA, N) VARRAY_CHECK (VA, N, c)
#define VARRAY_UCHAR(VA, N) VARRAY_CHECK (VA, N, uc)
#define VARRAY_SHORT(VA, N) VARRAY_CHECK (VA, N, s)
*************** extern void varray_check_failed PARAMS (
*** 317,321 ****
--- 321,328 ----
#define VARRAY_TOP_REG(VA) VARRAY_TOP (VA, reg)
#define VARRAY_TOP_CONST_EQUIV(VA) VARRAY_TOP (VA, const_equiv)
#define VARRAY_TOP_BB(VA) VARRAY_TOP (VA, bb)
+
+ /* Return element N of VA. */
+ #define VARRAY_N_TREE(VA, N) VARRAY_N (VA, tree, N)
#endif /* ! GCC_VARRAY_H */
Index: tree-dump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dump.c,v
retrieving revision 1.6.2.14
diff -c -p -r1.6.2.14 tree-dump.c
*** tree-dump.c 5 Nov 2002 23:50:38 -0000 1.6.2.14
--- tree-dump.c 25 Nov 2002 18:21:25 -0000
*************** static struct dump_file_info dump_files[
*** 668,673 ****
--- 668,674 ----
{".ccp", "dump-tree-ccp", 0, 0},
{".pre", "dump-tree-pre", 0, 0},
{".dce", "dump-tree-dce", 0, 0},
+ {".copyprop", "dump-tree-copyprop", 0, 0},
{".optimized", "dump-tree-optimized", 0, 0},
{".xml", "dump-call-graph", 0, 0},
{NULL, "dump-tree-all", 0, 0},
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.25
diff -c -p -r1.342.2.25 tree.h
*** tree.h 5 Nov 2002 23:50:39 -0000 1.342.2.25
--- tree.h 25 Nov 2002 18:21:28 -0000
*************** enum tree_dump_index
*** 3218,3223 ****
--- 3218,3225 ----
function. */
TDI_dce, /* dump SSA DCE information for each
function. */
+ TDI_copyprop, /* dump SSA Copy propagation information for
+ each function. */
TDI_optimized, /* dump each function after optimizing it. */
TDI_xml, /* dump function call graph. */
TDI_all, /* enable all the dumps above. */
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.36
diff -c -p -r1.1.4.36 tree-flow.h
*** tree-flow.h 13 Nov 2002 21:04:39 -0000 1.1.4.36
--- tree-flow.h 25 Nov 2002 18:21:28 -0000
*************** void tree_ssa_ccp PARAMS ((tree));
*** 739,744 ****
--- 739,747 ----
/* In tree-ssa-dce.c */
void tree_ssa_eliminate_dead_code PARAMS ((tree));
+ /* In tree-ssa-copyprop.c */
+ void tree_ssa_copy_propagation PARAMS ((tree));
+
#include "tree-flow-inline.h"
#endif /* _TREE_FLOW_H */
Index: flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.86.2.14
diff -c -p -r1.86.2.14 flags.h
*** flags.h 5 Nov 2002 23:50:37 -0000 1.86.2.14
--- flags.h 25 Nov 2002 18:21:29 -0000
*************** extern int flag_tree_pre;
*** 665,670 ****
--- 665,673 ----
/* 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.2
diff -c -p -r1.14.2.2 timevar.def
*** timevar.def 6 Nov 2002 22:22:34 -0000 1.14.2.2
--- timevar.def 25 Nov 2002 18:21:29 -0000
*************** DEFTIMEVAR (TV_TREE_PTA , "tree PT
*** 57,62 ****
--- 57,63 ----
DEFTIMEVAR (TV_TREE_SSA , "tree SSA building")
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_VARCONST , "varconst")
DEFTIMEVAR (TV_INTEGRATION , "integration")
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.654.2.32
diff -c -p -r1.654.2.32 toplev.c
*** toplev.c 13 Nov 2002 21:04:38 -0000 1.654.2.32
--- toplev.c 25 Nov 2002 18:21:33 -0000
*************** enum pta_type flag_tree_points_to = PTA_
*** 895,900 ****
--- 895,903 ----
/* Enable SSA-CCP on trees. */
int flag_tree_ccp = 0;
+ /* Enable SSA-Copy propagation on trees. */
+ int flag_tree_copyprop;
+
/* Enable SSA-DCE on trees. */
int flag_tree_dce = 0;
*************** static const lang_independent_options f_
*** 1214,1219 ****
--- 1217,1224 ----
N_("Enable SSA-PRE optimization on trees") },
{ "tree-ccp", &flag_tree_ccp, 1,
N_("Enable SSA-CCP 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-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-optimize.c,v
retrieving revision 1.1.4.21
diff -c -p -r1.1.4.21 tree-optimize.c
*** tree-optimize.c 8 Nov 2002 01:01:28 -0000 1.1.4.21
--- tree-optimize.c 25 Nov 2002 18:21:33 -0000
*************** optimize_function_tree (fndecl)
*** 87,92 ****
--- 87,97 ----
if (flag_tree_ccp)
tree_ssa_ccp (fndecl);
timevar_pop (TV_TREE_CCP);
+
+ timevar_push (TV_TREE_COPYPROP);
+ if (flag_tree_copyprop)
+ tree_ssa_copy_propagation (fndecl);
+ timevar_pop (TV_TREE_COPYPROP);
timevar_push (TV_TREE_DCE);
if (flag_tree_dce)
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.49
diff -c -p -r1.903.2.49 Makefile.in
*** Makefile.in 8 Nov 2002 01:01:27 -0000 1.903.2.49
--- Makefile.in 25 Nov 2002 18:21:36 -0000
*************** OBJS = alias.o bb-reorder.o bitmap.o bui
*** 757,763 ****
tree-optimize.o tree-simple.o simple-break-elim.o simple-goto-elim.o \
tree-dchain.o tree-ssa-pre.o tree-alias-type.o gimplify.o \
tree-alias-ecr.o tree-alias-common.o tree-alias-steen.o disjoint-set.o \
! tree-ssa-ccp.o tree-ssa-dce.o \
et-forest.o $(GGC) $(out_object_file) $(EXTRA_OBJS)
BACKEND = main.o libbackend.a
--- 757,763 ----
tree-optimize.o tree-simple.o simple-break-elim.o simple-goto-elim.o \
tree-dchain.o tree-ssa-pre.o tree-alias-type.o gimplify.o \
tree-alias-ecr.o tree-alias-common.o tree-alias-steen.o disjoint-set.o \
! tree-ssa-ccp.o tree-ssa-dce.o tree-ssa-copyprop.o \
et-forest.o $(GGC) $(out_object_file) $(EXTRA_OBJS)
BACKEND = main.o libbackend.a
*************** ssa-dce.o : ssa-dce.c $(CONFIG_H) $(SYST
*** 1563,1568 ****
--- 1563,1570 ----
$(BASIC_BLOCK_H) ssa.h insn-config.h $(RECOG_H) output.h
tree-ssa-dce.o : tree-ssa-dce.c $(CONFIG_H) system.h errors.h $(TREE_H) \
$(RTL_H) $(TM_P_H) $(TREE_FLOW_H) diagnostic.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
ssa-ccp.o : ssa-ccp.c $(CONFIG_H) system.h $(RTL_H) hard-reg-set.h \
$(BASIC_BLOCK_H) ssa.h insn-config.h $(RECOG_H) output.h \
errors.h $(GGC_H) df.h function.h
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 25 Nov 2002 18:21:36 -0000
***************
*** 0 ****
--- 1,247 ----
+ /* SSA-Constant propagation for the GNU compiler.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Contributed by Aldy Hernandez <aldy@quesejoda.com>
+
+ This file is part of GNU CC.
+
+ GNU CC 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.
+
+ GNU CC 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 GNU CC; 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 "errors.h"
+ #include "ggc.h"
+ #include "tree.h"
+
+ /* Headers are needed for basic-block.h. */
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "hard-reg-set.h"
+ #include "basic-block.h"
+
+ #include "diagnostic.h"
+ #include "tree-flow.h"
+ #include "tree-simple.h"
+
+ static FILE *dump_file;
+ static int dump_flags;
+
+ static void initialize PARAMS ((tree));
+ static void finalize PARAMS ((tree));
+ static void make_replacement PARAMS ((tree_ref, tree));
+
+ static void
+ make_replacement (ref, replacement)
+ tree_ref ref;
+ tree replacement;
+ {
+ tree var = ref_var (ref);
+ tree stmt = ref_stmt (ref);
+
+ /* Yeah, a lot of good it'll do to replace ourselves. */
+ if (var == replacement)
+ return;
+
+ replace_ref_in (stmt, ref, replacement);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "SSA-COPYPROP: Replacing ");
+ if (get_name (var))
+ fprintf (dump_file, "'%s' with ", get_name (var));
+ else
+ fprintf (dump_file, "<unnamed var %x> with ", (int) var);
+ if (get_name (replacement))
+ fprintf (dump_file, "%s\n", get_name (replacement));
+ else
+ fprintf (dump_file, "<unnamed var %x>\n", (int) replacement);
+ }
+ }
+
+ /* Main entry point. */
+
+ void
+ tree_ssa_copy_propagation (fndecl)
+ tree fndecl;
+ {
+ basic_block bb;
+ tree fnbody;
+ ref_list worklist, worklist_defs;
+ ref_list_iterator i;
+
+ fnbody = DECL_SAVED_TREE (fndecl);
+
+ worklist = create_ref_list ();
+ worklist_defs = create_ref_list ();
+
+ initialize (fndecl);
+
+ /* Save all the uses of variables. */
+ FOR_EACH_BB (bb)
+ {
+ if (bb_empty_p (bb))
+ continue;
+
+ for (i = rli_start (bb_refs (bb)); !rli_after_end (i); rli_step (&i))
+ {
+ tree_ref use;
+
+ use = rli_ref (i);
+
+ /* Save all definitions. */
+ if (ref_type (use) != V_USE)
+ {
+ add_ref_to_list_end (worklist_defs, use);
+ continue;
+ }
+
+ if (!is_pure_use (use))
+ continue;
+ /* Save all uses. */
+ add_ref_to_list_end (worklist, use);
+ }
+ }
+
+ for (i = rli_start (worklist); !rli_after_end (i); rli_step (&i))
+ {
+ tree_ref ref, rdef;
+ tree stmt, rhs;
+
+ ref = rli_ref (i);
+ rdef = imm_reaching_def (ref);
+ if (ref_type (ref) != V_USE || !rdef)
+ continue;
+
+ if (!is_killing_def (rdef, ref))
+ continue;
+
+ stmt = ref_stmt (rdef);
+ if (!stmt)
+ continue;
+ STRIP_WFL (stmt);
+
+ /* Get RHS of reaching definition. */
+ if (!is_simple_modify_expr (stmt)
+ || !is_simple_modify_expr (ref_stmt (ref)))
+ continue;
+ rhs = TREE_OPERAND (stmt, 1);
+
+ if (!DECL_P (rhs)
+ || TREE_TYPE (ref_var (ref)) != TREE_TYPE (ref_var (rdef)))
+ continue;
+
+ /* Go through all the definitions. If the above 'rdef' RHS was
+ killed, we can't propagate this copy.
+
+ All entire block needs to be fixed. We need to properly
+ calculate life info. For example, the block below
+ mis-propagates:
+
+ orig_y = y;
+ while (blah) {
+ z = orig_y;
+ y = 5;
+ }
+
+ */
+ {
+ ref_list_iterator i;
+ tree_ref ref_redefine;
+
+ for (i = rli_start (worklist_defs); !rli_after_end (i); rli_step (&i))
+ {
+ ref_redefine = rli_ref (i);
+ if (ref_var (ref_redefine) != rhs
+ || !ref_stmt (ref_redefine))
+ continue;
+
+ /* FIXME: Is this a good way to determine if RDEF
+ dominates REF_REDEFINE and REF_DEFINE dominates
+ REF??
+
+ What I want to know is if we have:
+
+ RDEF: a = b
+ DEF_REDEFINE: b = x
+ REF: d = a
+
+ */
+ if (ref_id (ref) > ref_id (ref_redefine)
+ && ref_id (ref_redefine) > ref_id (rdef))
+ goto no_replace;
+ }
+ }
+
+ /* Ignore anything that may alias. For example, in the code
+ below, z=y should not be propagated in c().
+
+ z = y;
+ y1 = &y;
+ b(y1);
+ c(z, y);
+
+ Ideally, we should check whether any of the members in the
+ alias set for the RDEF are changed, but I doubt it's worth
+ the trouble. ?? */
+ if (num_may_alias (rhs) > 0)
+ continue;
+
+ make_replacement (ref, rhs);
+ no_replace:
+ ;
+ }
+
+ finalize (fndecl);
+ }
+
+ static void
+ initialize (fndecl)
+ tree fndecl;
+ {
+ tree fnbody = DECL_SAVED_TREE (fndecl);
+
+ dump_file = dump_begin (TDI_copyprop, &dump_flags);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "%s() before SSA-COPYPROP\n", get_name (fndecl));
+
+ print_generic_stmt (dump_file, fnbody, dump_flags);
+
+ fprintf (dump_file, "\n\n");
+ }
+
+ }
+
+ static void
+ finalize (fndecl)
+ tree fndecl;
+ {
+ tree fnbody = DECL_SAVED_TREE (fndecl);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "%s() after SSA-COPYPROP\n", get_name (fndecl));
+
+ if (dump_flags & TDF_RAW)
+ dump_node (fnbody, TDF_SLIM | dump_flags, dump_file);
+ else
+ print_generic_stmt (dump_file, fnbody, dump_flags);
+
+ fprintf (dump_file, "\n");
+ dump_end (TDI_copyprop, dump_file);
+ dump_file = NULL;
+ }
+ }