[patch] speedup update_ssa a bit
Steven Bosscher
stevenb@suse.de
Thu Sep 8 19:28:00 GMT 2005
Hi,
For some files we can spend a significant amount of time clearing
a few flags and SSA_NAME_AUX in update_ssa. The patch below buys
me 4.5% for gcc.i, for example. For all cc1-i files it gives me
almost 1%, which is not as much as what I'd hoped for, but small
bits help too.
Bootstrapped&tested on {i686,x86_64,ia64}-unknown-linux-gnu.
OK for mainline?
Gr.
Steven
* tree-flow.h (REGISTER_DEFS_IN_THIS_STMT, REWRITE_THIS_STMT): Moved
from tree-into-ssa.c to here.
* tree-into-ssa.c (stmts_to_clear_flags_on,
ssa_names_to_clear_aux_on): New VECs used as queues.
(set_rewrite_this_stmt, set_register_defs_in_this_stmt,
clear_into_ssa_flags, clear_ssa_name_aux): New functions.
(get_ssa_name_ann): Add 'name' to the ssa_names_to_clear_aux_on
queue if SSA_NAME_AUX has to be allocated for it.
(mark_def_sites, insert_phi_nodes_for, mark_def_interesting,
mark_use_interesting): Use set_rewrite_this_stmt
and set_register_defs_in_this_stmt to set REWRITE_THIS_STMT and
REGISTER_DEFS_IN_THIS_STMT.
(rewrite_into_ssa, update_ssa): Allocate stmts_to_clear_flags_on.
Free it at the end after using clear_into_ssa_flags.
(init_update_ssa): Allocate ssa_names_to_clear_aux_on.
(delete_update_ssa): Free it. Use clear_into_ssa_flags to clear
SSA_NAME_AUX on SSA names that have it.
* tree-ssa-dce.c (NECESSARY): Use TREE_VISITED instead of
TREE_ASM_WRITTEN.
* tree-ssa-pre.c (NECESSARY): Likewise.
* tree-ssa-propagate.h (DONT_SIMULATE_AGAIN): Add a comment that
it is up to the user of the propagation engine to clear this flag
where necessary.
* tree-ssa.c (verify_ssa): Verify that REWRITE_THIS_STMT and
REGISTER_DEFS_IN_THIS_STMT are clear on all PHI nodes and statements.
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.132
diff -u -3 -p -r2.132 tree-flow.h
--- tree-flow.h 13 Aug 2005 17:28:40 -0000 2.132
+++ tree-flow.h 8 Sep 2005 09:11:12 -0000
@@ -639,6 +639,27 @@ extern void walk_use_def_chains (tree, w
extern bool stmt_references_memory_p (tree);
/* In tree-into-ssa.c */
+
+/* Use TREE_ASM_WRITTEN to keep track of which statements we want to
+ rename. When renaming a subset of the variables, not all
+ statements will be processed. This is decided in mark_def_sites.
+
+ Passes are themselves responsible for having TREE_ASM_WRITTEN cleared
+ before calling update_ssa. */
+#define REWRITE_THIS_STMT(T) (T)->common.asm_written_flag
+
+/* Use the unsigned flag to keep track of which statements we want to
+ visit when marking new definition sites. This is slightly
+ different than REWRITE_THIS_STMT: it's used by update_ssa to
+ distinguish statements that need to have both uses and defs
+ processed from those that only need to have their defs processed.
+ Statements that define new SSA names only need to have their defs
+ registered, but they don't need to have their uses renamed.
+
+ Like above, passes are themselves responsible for having this flag
+ cleared before calling update_ssa. */
+#define REGISTER_DEFS_IN_THIS_STMT(T) (T)->common.unsigned_flag
+
void update_ssa (unsigned);
void delete_update_ssa (void);
void register_new_name_mapping (tree, tree);
Index: tree-into-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-into-ssa.c,v
retrieving revision 2.64
diff -u -3 -p -r2.64 tree-into-ssa.c
--- tree-into-ssa.c 28 Jul 2005 16:29:52 -0000 2.64
+++ tree-into-ssa.c 8 Sep 2005 09:11:13 -0000
@@ -211,22 +211,6 @@ enum rewrite_mode {
REWRITE_UPDATE
};
-
-/* Use TREE_VISITED to keep track of which statements we want to
- rename. When renaming a subset of the variables, not all
- statements will be processed. This is decided in mark_def_sites. */
-#define REWRITE_THIS_STMT(T) TREE_VISITED (T)
-
-/* Use the unsigned flag to keep track of which statements we want to
- visit when marking new definition sites. This is slightly
- different than REWRITE_THIS_STMT: it's used by update_ssa to
- distinguish statements that need to have both uses and defs
- processed from those that only need to have their defs processed.
- Statements that define new SSA names only need to have their defs
- registered, but they don't need to have their uses renamed. */
-#define REGISTER_DEFS_IN_THIS_STMT(T) (T)->common.unsigned_flag
-
-
/* Prototypes for debugging functions. */
extern void dump_tree_ssa (FILE *);
extern void debug_tree_ssa (void);
@@ -238,17 +222,89 @@ void debug_update_ssa (void);
void dump_names_replaced_by (FILE *, tree);
void debug_names_replaced_by (tree);
+
+/* This is a queue to keep stack of statements on which we need to clear
+ REWRITE_THIS_STMT and/or REGISTER_DEFS_IN_THIS_STMT. */
+static VEC(tree,heap) *stmts_to_clear_flags_on;
+
+/* This is a queue to keep track of SSA names that we have allocated an
+ annotation for. It is used to queue those SSA names so we can quickly
+ iterate over them to free the annotation, without iterating over all
+ SSA names. */
+static VEC(tree,heap) *ssa_names_to_clear_aux_on;
+
+/* Set REWRITE_THIS_STMT on STMT and queue STMT for clearing
+ REWRITIE_THIS_STMT if the flag was not already set. */
+
+static inline void
+set_rewrite_this_stmt (tree stmt)
+{
+ if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
+ {
+ VEC_reserve (tree, heap, stmts_to_clear_flags_on, -1);
+ VEC_quick_push (tree, stmts_to_clear_flags_on, stmt);
+ }
+ REWRITE_THIS_STMT (stmt) = 1;
+}
+
+/* Set REGISTER_DEFS_IN_THIS_STMT on STMT and queue STMT for clearing
+ REGISTER_DEFS_IN_THIS_STMT if the flag was not already set. */
+
+static inline void
+set_register_defs_in_this_stmt (tree stmt)
+{
+ if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
+ {
+ VEC_reserve (tree, heap, stmts_to_clear_flags_on, -1);
+ VEC_quick_push (tree, stmts_to_clear_flags_on, stmt);
+ }
+ REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
+}
+
+/* Clear REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT on all the
+ statements in stmts_to_clear_flags_on. */
+
+static inline void
+clear_into_ssa_flags (void)
+{
+ unsigned i;
+ tree stmt;
+
+ for (i = 0; VEC_iterate (tree, stmts_to_clear_flags_on, i, stmt); i++)
+ {
+ REWRITE_THIS_STMT (stmt) = 0;
+ REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
+ }
+}
+
/* Get the information associated with NAME. */
static inline struct ssa_name_info *
get_ssa_name_ann (tree name)
{
if (!SSA_NAME_AUX (name))
- SSA_NAME_AUX (name) = xcalloc (1, sizeof (struct ssa_name_info));
-
+ {
+ SSA_NAME_AUX (name) = xcalloc (1, sizeof (struct ssa_name_info));
+ VEC_reserve (tree, heap, ssa_names_to_clear_aux_on, -1);
+ VEC_quick_push (tree, ssa_names_to_clear_aux_on, name);
+ }
return SSA_NAME_AUX (name);
}
+/* Free SSA_NAME_AUX on all SSA names that we have allocated it for. */
+
+static inline void
+clear_ssa_name_aux (void)
+{
+ unsigned i;
+ tree name;
+
+ for (i = 0; VEC_iterate (tree, ssa_names_to_clear_aux_on, i, name); i++)
+ {
+ free (SSA_NAME_AUX (name));
+ SSA_NAME_AUX (name) = NULL;
+ }
+}
/* Gets phi_state field for VAR. */
@@ -297,7 +353,6 @@ set_current_def (tree var, tree def)
var_ann (var)->current_def = def;
}
-
/* Compute global livein information given the set of blockx where
an object is locally live at the start of the block (LIVEIN)
and the set of blocks where the object is defined (DEF_BLOCKS).
@@ -653,7 +708,7 @@ mark_def_sites (struct dom_walk_data *wa
gcc_assert (DECL_P (sym));
if (!bitmap_bit_p (kills, DECL_UID (sym)))
set_livein_block (sym, bb);
- REWRITE_THIS_STMT (stmt) = 1;
+ set_rewrite_this_stmt (stmt);
}
/* Note that virtual definitions are irrelevant for computing KILLS
@@ -667,8 +722,8 @@ mark_def_sites (struct dom_walk_data *wa
gcc_assert (DECL_P (sym));
set_livein_block (sym, bb);
set_def_block (sym, bb, false);
- REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
- REWRITE_THIS_STMT (stmt) = 1;
+ set_register_defs_in_this_stmt (stmt);
+ set_rewrite_this_stmt (stmt);
}
/* Now process the defs and must-defs made by this statement. */
@@ -677,7 +732,7 @@ mark_def_sites (struct dom_walk_data *wa
gcc_assert (DECL_P (def));
set_def_block (def, bb, false);
bitmap_set_bit (kills, DECL_UID (def));
- REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
+ set_register_defs_in_this_stmt (stmt);
}
/* If we found the statement interesting then also mark the block BB
@@ -845,8 +900,8 @@ insert_phi_nodes_for (tree var, bitmap p
}
/* Mark this PHI node as interesting for update_ssa. */
- REGISTER_DEFS_IN_THIS_STMT (phi) = 1;
- REWRITE_THIS_STMT (phi) = 1;
+ set_register_defs_in_this_stmt (phi);
+ set_rewrite_this_stmt (phi);
}
}
@@ -1739,6 +1794,10 @@ rewrite_into_ssa (void)
timevar_push (TV_TREE_SSA_OTHER);
+ /* Set up the queue of statements to clear the rewrite flags on. Start
+ with a large vector to avoid frequent re-allocations. */
+ stmts_to_clear_flags_on = VEC_alloc (tree, heap, 3 * n_basic_blocks);
+
/* Initialize operand data structures. */
init_ssa_operands ();
@@ -1772,6 +1831,14 @@ rewrite_into_ssa (void)
free (dfs);
sbitmap_free (interesting_blocks);
+ /* Clear the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags
+ for every statement and PHI node. Clearing it here, and keeping
+ it clear, allows us to assume in update_ssa that these flags are
+ cleared on entry, so that we don't have to do a walk over the
+ entire function to explicitly clear them. */
+ clear_into_ssa_flags ();
+ VEC_free (tree, heap, stmts_to_clear_flags_on);
+
timevar_pop (TV_TREE_SSA_OTHER);
in_ssa_p = true;
}
@@ -1802,7 +1869,7 @@ static void
mark_def_interesting (tree var, tree stmt, basic_block bb, bitmap blocks,
bool insert_phi_p)
{
- REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
+ set_register_defs_in_this_stmt (stmt);
bitmap_set_bit (blocks, bb->index);
if (insert_phi_p)
@@ -1834,7 +1901,7 @@ static inline void
mark_use_interesting (tree var, tree stmt, basic_block bb, bitmap blocks,
bool insert_phi_p)
{
- REWRITE_THIS_STMT (stmt) = 1;
+ set_rewrite_this_stmt (stmt);
bitmap_set_bit (blocks, bb->index);
/* If VAR has not been defined in BB, then it is live-on-entry
@@ -2166,6 +2233,8 @@ debug_update_ssa (void)
static void
init_update_ssa (void)
{
+ unsigned ssa_aux_queue_len;
+
/* Reserve more space than the current number of names. The calls to
add_new_name_mapping are typically done after creating new SSA
names, so we'll need to reallocate these arrays. */
@@ -2175,6 +2244,15 @@ init_update_ssa (void)
new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
sbitmap_zero (new_ssa_names);
+ /* When rewriting the whole function into SSA, it is silly to start with
+ a queue of length 'num_ssa_names' because it will be a zero-length
+ queue. So instead start with a reasonable estimate for the number of
+ SSA names in the program. The queue will grow when demanded anyway,
+ but it appears to be profitable to start with a large queue. */
+ ssa_aux_queue_len = num_ssa_names
+ ? num_ssa_names : (unsigned) (3 * n_basic_blocks);
+ ssa_names_to_clear_aux_on = VEC_alloc (tree, heap, ssa_aux_queue_len);
+
repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free);
need_to_initialize_update_ssa_p = false;
need_to_update_vops_p = false;
@@ -2190,9 +2268,6 @@ init_update_ssa (void)
void
delete_update_ssa (void)
{
- unsigned i;
- bitmap_iterator bi;
-
sbitmap_free (old_ssa_names);
old_ssa_names = NULL;
@@ -2207,23 +2282,20 @@ delete_update_ssa (void)
BITMAP_FREE (syms_to_rename);
BITMAP_FREE (update_ssa_stats.virtual_symbols);
+ /* Clear SSA_NAME_AUX on all SSA names that we have allocated an
+ annotation for. */
+ clear_ssa_name_aux ();
+ VEC_free (tree, heap, ssa_names_to_clear_aux_on);
+
if (names_to_release)
{
+ unsigned i;
+ bitmap_iterator bi;
+
EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
release_ssa_name (ssa_name (i));
BITMAP_FREE (names_to_release);
}
-
- for (i = 1; i < num_ssa_names; i++)
- {
- tree n = ssa_name (i);
-
- if (n)
- {
- free (SSA_NAME_AUX (n));
- SSA_NAME_AUX (n) = NULL;
- }
- }
}
@@ -2647,6 +2719,9 @@ update_ssa (unsigned update_flags)
htab_empty (repl_tbl);
}
+ /* Set up the queue of statements to clear the rewrite flags on. Start
+ with a large vector to avoid frequent re-allocations. */
+ stmts_to_clear_flags_on = VEC_alloc (tree, heap, 3 * n_basic_blocks);
insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
if (insert_phi_p)
@@ -2668,8 +2743,15 @@ update_ssa (unsigned update_flags)
blocks = BITMAP_ALLOC (NULL);
- /* Clear the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags
- for every statement and PHI node. */
+#ifdef ENABLE_CHECKING
+ /* The REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags should be
+ cleare for every statement and PHI node when update_ssa is called.
+
+ Also, we are going to use the operand cache API, such as SET_USE,
+ SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand cache for each
+ statement should therefore be up-to-date.
+
+ Make sure these conditions are satisfied. */
FOR_EACH_BB (bb)
{
block_stmt_iterator si;
@@ -2677,21 +2759,20 @@ update_ssa (unsigned update_flags)
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
- REWRITE_THIS_STMT (phi) = 0;
- REGISTER_DEFS_IN_THIS_STMT (phi) = 0;
+ gcc_assert (!REWRITE_THIS_STMT (phi)
+ && !REGISTER_DEFS_IN_THIS_STMT (phi));
}
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
tree stmt = bsi_stmt (si);
- /* We are going to use the operand cache API, such as
- SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST. The operand
- cache for each statement should be up-to-date. */
- gcc_assert (!stmt_modified_p (stmt));
- REWRITE_THIS_STMT (stmt) = 0;
- REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
+
+ gcc_assert (!stmt_modified_p (stmt)
+ && !REWRITE_THIS_STMT (stmt)
+ && !REGISTER_DEFS_IN_THIS_STMT (stmt));
}
}
+#endif
/* Heuristic to avoid massive slow downs when the replacement
mappings include lots of virtual names. */
@@ -2834,5 +2915,10 @@ done:
BITMAP_FREE (blocks);
delete_update_ssa ();
+ /* Clear the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags
+ for every statement and PHI node. */
+ clear_into_ssa_flags ();
+ VEC_free (tree, heap, stmts_to_clear_flags_on);
+
timevar_pop (TV_TREE_SSA_INCREMENTAL);
}
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dce.c,v
retrieving revision 2.48
diff -u -3 -p -r2.48 tree-ssa-dce.c
--- tree-ssa-dce.c 28 Jul 2005 16:29:54 -0000 2.48
+++ tree-ssa-dce.c 8 Sep 2005 09:11:13 -0000
@@ -219,7 +219,9 @@ find_pdom (basic_block block)
}
}
-#define NECESSARY(stmt) stmt->common.asm_written_flag
+/* Use the TREE_VISITED to mark statements necessary. We can't assume
+ anything about this flag being set or clear on entry of this pass. */
+#define NECESSARY(STMT) TREE_VISITED (STMT)
/* If STMT is not already marked necessary, mark it, and add it to the
worklist if ADD_TO_WORKLIST is true. */
Index: tree-ssa-pre.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-pre.c,v
retrieving revision 2.99
diff -u -3 -p -r2.99 tree-ssa-pre.c
--- tree-ssa-pre.c 6 Sep 2005 18:51:26 -0000 2.99
+++ tree-ssa-pre.c 8 Sep 2005 09:11:14 -0000
@@ -1475,7 +1475,9 @@ find_or_generate_expression (basic_block
return genop;
}
-#define NECESSARY(stmt) stmt->common.asm_written_flag
+/* Use the TREE_VISITED, like DCE and tree-ssa-propagate a.o. */
+#define NECESSARY(STMT) TREE_VISITED (STMT)
+
/* Create an expression in pieces, so that we can handle very complex
expressions that may be ANTIC, but not necessary GIMPLE.
BLOCK is the basic block the expression will be inserted into,
Index: tree-ssa-propagate.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-propagate.h,v
retrieving revision 2.5
diff -u -3 -p -r2.5 tree-ssa-propagate.h
--- tree-ssa-propagate.h 25 Jun 2005 02:01:47 -0000 2.5
+++ tree-ssa-propagate.h 8 Sep 2005 09:11:14 -0000
@@ -24,8 +24,11 @@ Boston, MA 02110-1301, USA. */
#define _TREE_SSA_PROPAGATE_H 1
/* Use the TREE_VISITED bitflag to mark statements and PHI nodes that
- have been deemed varying and should not be simulated again. */
-#define DONT_SIMULATE_AGAIN(T) TREE_VISITED (T)
+ have been deemed varying and should not be simulated again.
+ Passes using the propagation engine are responsible for setting and
+ clearing the flag before running the engine. Users of the engine
+ an not use TREE_VISITED themselves for marking statements and PHIs. */
+#define DONT_SIMULATE_AGAIN(STMT) TREE_VISITED (STMT)
/* Lattice values used for propagation purposes. Specific instances
of a propagation engine must return these values from the statement
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa.c,v
retrieving revision 2.106
diff -u -3 -p -r2.106 tree-ssa.c
--- tree-ssa.c 19 Jul 2005 20:20:40 -0000 2.106
+++ tree-ssa.c 8 Sep 2005 09:11:14 -0000
@@ -691,8 +691,26 @@ verify_ssa (bool check_modified_stmt)
/* Verify the arguments for every PHI node in the block. */
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
+ /* Some flags should always be cleared on a PHI node, to avoid
+ confusing update_ssa. */
+ if (REWRITE_THIS_STMT (phi))
+ {
+ error ("phi (%p) has REWRITE_THIS_STMT still set : ",
+ (void *)phi);
+ print_generic_stmt (stderr, phi, TDF_VOPS);
+ goto err;
+ }
+ if (REGISTER_DEFS_IN_THIS_STMT (phi))
+ {
+ error ("phi (%p) has REGISTER_DEFS_IN_THIS_STMT still set : ",
+ (void *)phi);
+ print_generic_stmt (stderr, phi, TDF_VOPS);
+ goto err;
+ }
+
if (verify_phi_args (phi, bb, definition_block))
goto err;
+
bitmap_set_bit (names_defined_in_bb,
SSA_NAME_VERSION (PHI_RESULT (phi)));
}
@@ -703,6 +721,23 @@ verify_ssa (bool check_modified_stmt)
tree stmt = bsi_stmt (bsi);
use_operand_p use_p;
+ /* Like with PHI nodes, some flags should always be cleared
+ on a statement, to avoid confusing update_ssa. */
+ if (REWRITE_THIS_STMT (stmt))
+ {
+ error ("stmt (%p) has REWRITE_THIS_STMT still set : ",
+ (void *)stmt);
+ print_generic_stmt (stderr, stmt, TDF_VOPS);
+ goto err;
+ }
+ if (REGISTER_DEFS_IN_THIS_STMT (stmt))
+ {
+ error ("stmt (%p) has REGISTER_DEFS_IN_THIS_STMT still set : ",
+ (void *)stmt);
+ print_generic_stmt (stderr, stmt, TDF_VOPS);
+ goto err;
+ }
+
if (check_modified_stmt && stmt_modified_p (stmt))
{
error ("stmt (%p) marked modified after optimization pass : ",
More information about the Gcc-patches
mailing list