The SSA_NAME manager currently has a single free list. As names are
released, they're put on the free list and recycled immediately.
This has led to several problems through the years -- in particular
removal of an edge may result in removal of a PHI when the target of the
edge is unreachable. This can result in released names being left in
the IL until *all* unreachable code is eliminated. Long term we'd like
to discover all the unreachable code exposed by a deleted edge earlier,
but that's further out.
Richi originally suggested using a two list implementation to avoid this
class of problems. Essentially released names are queued until it's
safe to start recycling them. I agreed, but didn't get around to doing
any of the implementation work.
Bernd recently took care of the implementation side. This patch is
mostly his. The only change of significance I made is the placement of
the call to flush the pending list. Bernd had it in the ssa updater, I
put it after cfg cleanups. The former does recycle better, but there's
nothing that inherently ensures there aren't unreachables in the CFG
during update_ssa (in practice it's not a problem because we typically
update dominators first, which requires a cleaned cfg).
I've got a follow-up which exploits this improved safety in DOM to
optimize things better in DOM rather than waiting for jump threading to
clean things up.
No additional tests in this patch as the only failure seen when I
twiddled things a little was already covered by existing tests.
Bootstrapped and regression tested on x86-linux-gnu, with and without
the follow-up patch to exploit the capability in DOM.
Installed on the trunk.
jeff
* gimple-ssa.h (gimple_df): Add free_ssanames_queue field.
* passes.c: Include tree-ssanames.h.
(execute_function_todo): Flush the pending free SSA_NAMEs after
eliminating unreachable basic blocks.
* tree-ssanames.c (FREE_SSANAMES_QUEUE): new.
(init_ssanames): Initialize FREE_SSANAMES_QUEUE.
(fini_ssanames): Finalize FREE_SSANAMES_QUEUE.
(flush_ssanames_freelist): New function.
(release_ssaname_fn): Put released names on the queue.
(pass_release_ssa_names::execute): Call flush_ssanames_freelist.
* tree-ssanames.h (flush_ssanames_freelist): Declare.
diff --git a/gcc/gimple-ssa.h b/gcc/gimple-ssa.h
index c89071e..39551da 100644
--- a/gcc/gimple-ssa.h
+++ b/gcc/gimple-ssa.h
@@ -90,6 +90,9 @@ struct GTY(()) gimple_df {
/* Free list of SSA_NAMEs. */
vec<tree, va_gc> *free_ssanames;
+ /* Queue of SSA_NAMEs to be freed at the next opportunity. */
+ vec<tree, va_gc> *free_ssanames_queue;
+
/* Hashtable holding definition for symbol. If this field is not NULL, it
means that the first reference to this variable in the function is a
USE or a VUSE. In those cases, the SSA renamer creates an SSA name
diff --git a/gcc/passes.c b/gcc/passes.c
index d06a293..5b41102 100644
--- a/gcc/passes.c
+++ b/gcc/passes.c
@@ -84,6 +84,7 @@ along with GCC; see the file COPYING3. If not see
#include "cfgrtl.h"
#include "tree-ssa-live.h" /* For remove_unused_locals. */
#include "tree-cfgcleanup.h"
+#include "tree-ssanames.h"
using namespace gcc;
@@ -1913,6 +1914,14 @@ execute_function_todo (function *fn, void *data)
{
cleanup_tree_cfg ();
+ /* Once unreachable nodes have been removed from the CFG,
+ there can't be any lingering references to released
+ SSA_NAMES (because there is no more unreachable code).
+
+ Thus, now is the time to flush the SSA_NAMEs freelist. */
+ if (fn->gimple_df)
+ flush_ssaname_freelist ();
+
/* When cleanup_tree_cfg merges consecutive blocks, it may
perform some simplistic propagation when removing single
valued PHI nodes. This propagation may, in turn, cause the
diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c
index 4199290..e029062 100644
--- a/gcc/tree-ssanames.c
+++ b/gcc/tree-ssanames.c
@@ -69,6 +69,7 @@ unsigned int ssa_name_nodes_reused;
unsigned int ssa_name_nodes_created;
#define FREE_SSANAMES(fun) (fun)->gimple_df->free_ssanames
+#define FREE_SSANAMES_QUEUE(fun) (fun)->gimple_df->free_ssanames_queue
/* Initialize management of SSA_NAMEs to default SIZE. If SIZE is
@@ -91,6 +92,7 @@ init_ssanames (struct function *fn, int size)
least 50 elements reserved in it. */
SSANAMES (fn)->quick_push (NULL_TREE);
FREE_SSANAMES (fn) = NULL;
+ FREE_SSANAMES_QUEUE (fn) = NULL;
fn->gimple_df->ssa_renaming_needed = 0;
fn->gimple_df->rename_vops = 0;
@@ -103,6 +105,7 @@ fini_ssanames (void)
{
vec_free (SSANAMES (cfun));
vec_free (FREE_SSANAMES (cfun));
+ vec_free (FREE_SSANAMES_QUEUE (cfun));
}
/* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */
@@ -114,6 +117,22 @@ ssanames_print_statistics (void)
fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
}
+/* Move all SSA_NAMEs from FREE_SSA_NAMES_QUEUE to FREE_SSA_NAMES.
+
+ We do not, but should have a mode to verify the state of the SSA_NAMEs
+ lists. In particular at this point every name must be in the IL,
+ on the free list or in the queue. Anything else is an error. */
+
+void
+flush_ssaname_freelist (void)
+{
+ while (!vec_safe_is_empty (FREE_SSANAMES_QUEUE (cfun)))
+ {
+ tree t = FREE_SSANAMES_QUEUE (cfun)->pop ();
+ vec_safe_push (FREE_SSANAMES (cfun), t);
+ }
+}
+
/* Return an SSA_NAME node for variable VAR defined in statement STMT
in function FN. STMT may be an empty statement for artificial
references (e.g., default definitions created when a variable is
@@ -348,8 +367,8 @@ release_ssa_name_fn (struct function *fn, tree var)
/* Note this SSA_NAME is now in the first list. */
SSA_NAME_IN_FREE_LIST (var) = 1;
- /* And finally put it on the free list. */
- vec_safe_push (FREE_SSANAMES (fn), var);
+ /* And finally queue it so that it will be put on the free list. */
+ vec_safe_push (FREE_SSANAMES_QUEUE (fn), var);
}
}
@@ -607,6 +626,7 @@ unsigned int
pass_release_ssa_names::execute (function *fun)
{
unsigned i, j;
+ flush_ssaname_freelist ();
int n = vec_safe_length (FREE_SSANAMES (fun));
/* Now release the freelist. */
diff --git a/gcc/tree-ssanames.h b/gcc/tree-ssanames.h
index 22ff609..ae9351e 100644
--- a/gcc/tree-ssanames.h
+++ b/gcc/tree-ssanames.h
@@ -97,6 +97,7 @@ extern void duplicate_ssa_name_range_info (tree, enum
value_range_type,
extern void reset_flow_sensitive_info (tree);
extern void release_defs (gimple *);
extern void replace_ssa_name_symbol (tree, tree);
+extern void flush_ssaname_freelist (void);
/* Return an SSA_NAME node for variable VAR defined in statement STMT
