[tree-ssa] fold each statement
Jan Hubicka
jh@suse.cz
Wed Jan 7 22:14:00 GMT 2004
Hi,
this patch implements the folding pass done just after SSA rewrite. I tested
several other attempts to embedded folding in existing pass. It can't be fully
done in remove_useless_* because before SSA folding we miss come string
simplification; it can't be done as part of SSA rewrite as it needs PHI nodes
set up to do string builtins optimizations well and it is quite tricky to get
it as part of dom1 pass as it invalidate the SSA form in the case nonpure
function calls are elliminated.
The pass has small effect on overall compilation time. On checking enabled
compiler I measured 0.5sec (0%) on Gerald's testcase and on C component test
after bootstrap I even got a speedup (3m6sec to 3m2sec probably caused by noise
I would guess). On the Gerald's testcase 30000 statemets gets folded but the
result on final code is small.
However my major goal with this pass is to avoid ugly side cases of
noncanonical expressions leaking into insn stream and I would like to followup
with verify_stmts patch that ensure that statement is folded (I have this in my
tree for a while and have good experience with this sanity check modulo the
fact that if done after each pass it consume about 10% of compilation time
[tested together with grammar checker], so we need probably some way to tune
amount of sanity checking perhaps even via runtime flag one can use if
something goes wrong). This is also why I didn't included an switch to disable
it. I would like to keep canonicality of each statement a part of interface in
between tree-ssa passes.
Bootstrapped/regtested i686-pc-gnu-linux and x86_64-linux. OK?
2004-01-07 Jan Hubicka <jh@suse.cz>
* timevar.def (TV_TREE_FOLD): New.
* tree-dump.c (dump_files): Add fold pass; renumber
ssa passes.
* tree-fold.h (fold_each_stmt): Declare.
* tree-optimize.c (optimize_function_tree): Invoke fold pass;
renumber SSA passes.
* tree-ssa-ccp (fold_each_stmt): New.
* tree.h (tree_dump_index): Add fold pass; renumber ssa passes.
Index: timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.14.2.28
diff -c -3 -p -r1.14.2.28 timevar.def
*** timevar.def 13 Dec 2003 19:39:47 -0000 1.14.2.28
--- timevar.def 7 Jan 2004 18:33:49 -0000
*************** DEFTIMEVAR (TV_TREE_SSA_REWRITE_BLOCKS,
*** 71,76 ****
--- 71,77 ----
DEFTIMEVAR (TV_TREE_SSA_OTHER , "tree SSA other")
DEFTIMEVAR (TV_TREE_DFA , "tree dataflow analysis")
DEFTIMEVAR (TV_TREE_SSA_DOMINATOR_OPTS , "dominator optimization")
+ DEFTIMEVAR (TV_TREE_FOLD , "tree folding pass")
DEFTIMEVAR (TV_TREE_SRA , "tree SRA")
DEFTIMEVAR (TV_TREE_CCP , "tree CCP")
DEFTIMEVAR (TV_TREE_PRE , "tree PRE")
Index: tree-dump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dump.c,v
retrieving revision 1.6.2.61
diff -c -3 -p -r1.6.2.61 tree-dump.c
*** tree-dump.c 17 Dec 2003 19:53:01 -0000 1.6.2.61
--- tree-dump.c 7 Jan 2004 18:33:50 -0000
*************** static struct dump_file_info dump_files[
*** 661,680 ****
{".pta", "tree-pta", 0, 0},
{".alias", "tree-alias", 0, 0},
{".ssa1", "tree-ssa1", 0, 0},
! {".dom1", "tree-dom1", 0, 0},
{".ssa2", "tree-ssa2", 0, 0},
{".dce1", "tree-dce1", 0, 0},
{".loop", "tree-loop", 0, 0},
{".mustalias", "tree-mustalias", 0, 0},
! {".ssa3", "tree-ssa3", 0, 0},
{".tail1", "tree-tail1", 0, 0},
{".sra", "tree-sra", 0, 0},
- {".ssa4", "tree-ssa4", 0, 0},
- {".ccp", "tree-ccp", 0, 0},
{".ssa5", "tree-ssa5", 0, 0},
{".pre", "tree-pre", 0, 0},
{".dom2", "tree-dom2", 0, 0},
! {".ssa6", "tree-ssa6", 0, 0},
{".dce2", "tree-dce2", 0, 0},
{".tail2", "tree-tail2", 0, 0},
{".optimized", "tree-optimized", 0, 0},
--- 661,682 ----
{".pta", "tree-pta", 0, 0},
{".alias", "tree-alias", 0, 0},
{".ssa1", "tree-ssa1", 0, 0},
! {".fold", "tree-fold", 0, 0},
{".ssa2", "tree-ssa2", 0, 0},
+ {".dom1", "tree-dom1", 0, 0},
+ {".ssa3", "tree-ssa3", 0, 0},
{".dce1", "tree-dce1", 0, 0},
{".loop", "tree-loop", 0, 0},
{".mustalias", "tree-mustalias", 0, 0},
! {".ssa4", "tree-ssa4", 0, 0},
{".tail1", "tree-tail1", 0, 0},
{".sra", "tree-sra", 0, 0},
{".ssa5", "tree-ssa5", 0, 0},
+ {".ccp", "tree-ccp", 0, 0},
+ {".ssa6", "tree-ssa6", 0, 0},
{".pre", "tree-pre", 0, 0},
{".dom2", "tree-dom2", 0, 0},
! {".ssa7", "tree-ssa7", 0, 0},
{".dce2", "tree-dce2", 0, 0},
{".tail2", "tree-tail2", 0, 0},
{".optimized", "tree-optimized", 0, 0},
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.177
diff -c -3 -p -r1.1.4.177 tree-flow.h
*** tree-flow.h 26 Dec 2003 22:38:28 -0000 1.1.4.177
--- tree-flow.h 7 Jan 2004 18:33:50 -0000
*************** extern void tree_perform_ssapre (tree, e
*** 507,512 ****
--- 507,513 ----
/* In tree-ssa-ccp.c */
void tree_ssa_ccp (tree, bitmap, enum tree_dump_index);
bool fold_stmt (tree *);
+ void fold_each_stmt (tree, bitmap, enum tree_dump_index);
tree widen_bitfield (tree, tree, tree);
/* In tree-ssa-dom.c */
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.101
diff -c -3 -p -r1.1.4.101 tree-optimize.c
*** tree-optimize.c 4 Jan 2004 15:48:30 -0000 1.1.4.101
--- tree-optimize.c 7 Jan 2004 18:33:50 -0000
*************** optimize_function_tree (tree fndecl, tre
*** 101,114 ****
variables to be renamed. */
rewrite_into_ssa (fndecl, NULL, TDI_ssa_1);
- #ifdef ENABLE_CHECKING
- verify_ssa ();
- #endif
-
/* Set up VARS_TO_RENAME to allow passes to inform which variables
need to be renamed. */
vars_to_rename = BITMAP_XMALLOC ();
/* Perform dominator optimizations. */
if (flag_tree_dom)
{
--- 101,124 ----
variables to be renamed. */
rewrite_into_ssa (fndecl, NULL, TDI_ssa_1);
/* Set up VARS_TO_RENAME to allow passes to inform which variables
need to be renamed. */
vars_to_rename = BITMAP_XMALLOC ();
+ /* Rewrite to SSA form may introduce new oppurtunities for folding.
+ From now on each pass should preserve statements in the folded
+ form. */
+ fold_each_stmt (fndecl, vars_to_rename, TDI_fold);
+
+ /* If the dominator optimizations exposed new variables, we need
+ to repeat the SSA renaming process for those symbols. */
+ if (bitmap_first_set_bit (vars_to_rename) >= 0)
+ rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_2);
+
+ #ifdef ENABLE_CHECKING
+ verify_ssa ();
+ #endif
+
/* Perform dominator optimizations. */
if (flag_tree_dom)
{
*************** optimize_function_tree (tree fndecl, tre
*** 118,124 ****
/* If the dominator optimizations exposed new variables, we need
to repeat the SSA renaming process for those symbols. */
if (bitmap_first_set_bit (vars_to_rename) >= 0)
! rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_2);
#ifdef ENABLE_CHECKING
verify_ssa ();
--- 128,134 ----
/* If the dominator optimizations exposed new variables, we need
to repeat the SSA renaming process for those symbols. */
if (bitmap_first_set_bit (vars_to_rename) >= 0)
! rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_3);
#ifdef ENABLE_CHECKING
verify_ssa ();
*************** optimize_function_tree (tree fndecl, tre
*** 154,160 ****
/* Run the SSA pass again if we need to rename new variables. */
if (bitmap_first_set_bit (vars_to_rename) >= 0)
! rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_3);
ggc_collect ();
#ifdef ENABLE_CHECKING
--- 164,170 ----
/* Run the SSA pass again if we need to rename new variables. */
if (bitmap_first_set_bit (vars_to_rename) >= 0)
! rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_4);
ggc_collect ();
#ifdef ENABLE_CHECKING
*************** optimize_function_tree (tree fndecl, tre
*** 177,183 ****
/* Run the SSA pass again if we need to rename new variables. */
if (bitmap_first_set_bit (vars_to_rename) >= 0)
! rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_4);
ggc_collect ();
#ifdef ENABLE_CHECKING
--- 187,193 ----
/* Run the SSA pass again if we need to rename new variables. */
if (bitmap_first_set_bit (vars_to_rename) >= 0)
! rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_5);
ggc_collect ();
#ifdef ENABLE_CHECKING
*************** optimize_function_tree (tree fndecl, tre
*** 193,199 ****
/* Run the SSA pass again if we need to rename new variables. */
if (bitmap_first_set_bit (vars_to_rename) >= 0)
! rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_5);
ggc_collect ();
#ifdef ENABLE_CHECKING
--- 203,209 ----
/* Run the SSA pass again if we need to rename new variables. */
if (bitmap_first_set_bit (vars_to_rename) >= 0)
! rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_6);
ggc_collect ();
#ifdef ENABLE_CHECKING
*************** optimize_function_tree (tree fndecl, tre
*** 220,226 ****
/* Run the SSA pass again if we need to rename new variables. */
if (bitmap_first_set_bit (vars_to_rename) >= 0)
! rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_6);
#ifdef ENABLE_CHECKING
verify_ssa ();
--- 230,236 ----
/* Run the SSA pass again if we need to rename new variables. */
if (bitmap_first_set_bit (vars_to_rename) >= 0)
! rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_7);
#ifdef ENABLE_CHECKING
verify_ssa ();
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.129
diff -c -3 -p -r1.1.2.129 tree-ssa-ccp.c
*** tree-ssa-ccp.c 6 Jan 2004 05:06:22 -0000 1.1.2.129
--- tree-ssa-ccp.c 7 Jan 2004 18:33:50 -0000
*************** fold_stmt (tree *stmt_p)
*** 1922,1927 ****
--- 1922,1999 ----
return changed;
}
+ /* Fold each statement in the instruction chain. */
+ void
+ fold_each_stmt (tree fndecl ATTRIBUTE_UNUSED,
+ bitmap vars_to_rename,
+ enum tree_dump_index phase)
+ {
+ basic_block bb;
+ block_stmt_iterator si;
+ vdef_optype vdefs;
+ varray_type old_vdefs;
+ unsigned int i;
+
+ timevar_push (TV_TREE_FOLD);
+ /* Initialize debugging dumps. */
+ dump_file = dump_begin (phase, &dump_flags);
+ VARRAY_TREE_INIT (old_vdefs, 32, "virtual defs");
+
+ FOR_EACH_BB (bb) for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+ {
+ tree stmt = bsi_stmt (si);
+
+ get_stmt_operands (stmt);
+ vdefs = VDEF_OPS (stmt_ann (stmt));
+
+ /* Watch out for VDEFS that disappear. These need to be renamed. */
+ for (i = 0; i < NUM_VDEFS (vdefs); i++)
+ if (TREE_CODE (VDEF_RESULT (vdefs, i)) == SSA_NAME)
+ VARRAY_PUSH_TREE (old_vdefs, VDEF_RESULT (vdefs, i));
+
+ if (fold_stmt (bsi_stmt_ptr (si)))
+ {
+ tree def;
+ tree stmt = bsi_stmt (si);
+
+ modify_stmt (stmt);
+ get_stmt_operands (stmt);
+ vdefs = VDEF_OPS (stmt_ann (stmt));
+ if (dump_flags & TDF_DETAILS)
+ {
+ fprintf (dump_file, "Folded statement to :");
+ print_generic_stmt (dump_file, bsi_stmt (si), 0);
+ }
+ while (VARRAY_ACTIVE_SIZE (old_vdefs))
+ {
+ def = VARRAY_TOP_TREE (old_vdefs);
+ VARRAY_POP (old_vdefs);
+ for (i = 0; i < NUM_VDEFS (vdefs); i++)
+ if (def == VDEF_RESULT (vdefs, i))
+ break;
+ if (i == NUM_VDEFS (vdefs))
+ {
+ bitmap_set_bit (vars_to_rename,
+ var_ann (SSA_NAME_VAR (def))->uid);
+ if (dump_flags & TDF_DETAILS)
+ {
+ fprintf (dump_file, "Causing rename of :");
+ print_generic_stmt (dump_file, def, 0);
+ }
+ }
+ }
+ }
+ else
+ VARRAY_POP_ALL (old_vdefs);
+ }
+ if (dump_file)
+ {
+ dump_function_to_file (fndecl, dump_file, dump_flags);
+ dump_end (phase, dump_file);
+ }
+ timevar_pop (TV_TREE_FOLD);
+ }
+
/* Get the main expression from statement STMT. */
static tree
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.157
diff -c -3 -p -r1.342.2.157 tree.h
*** tree.h 6 Jan 2004 23:27:49 -0000 1.342.2.157
--- tree.h 7 Jan 2004 18:33:50 -0000
*************** enum tree_dump_index
*** 3580,3599 ****
/* Optimization passes. The ordering and numbering of these phases must
be the same as the one in optimize_function_tree. */
TDI_ssa_1,
! TDI_dom_1,
TDI_ssa_2,
TDI_dce_1,
TDI_loop,
TDI_mustalias,
! TDI_ssa_3,
TDI_tail1, /* dump after tail recursion elimination */
TDI_sra,
- TDI_ssa_4,
- TDI_ccp,
TDI_ssa_5,
TDI_pre,
TDI_dom_2,
! TDI_ssa_6,
TDI_dce_2,
TDI_tail2, /* dump after tail recursion/tail call */
TDI_optimized,
--- 3580,3601 ----
/* Optimization passes. The ordering and numbering of these phases must
be the same as the one in optimize_function_tree. */
TDI_ssa_1,
! TDI_fold,
TDI_ssa_2,
+ TDI_dom_1,
+ TDI_ssa_3,
TDI_dce_1,
TDI_loop,
TDI_mustalias,
! TDI_ssa_4,
TDI_tail1, /* dump after tail recursion elimination */
TDI_sra,
TDI_ssa_5,
+ TDI_ccp,
+ TDI_ssa_6,
TDI_pre,
TDI_dom_2,
! TDI_ssa_7,
TDI_dce_2,
TDI_tail2, /* dump after tail recursion/tail call */
TDI_optimized,
More information about the Gcc-patches
mailing list