On Wed, Sep 30, 2015 at 7:44 PM, Jeff Law <l...@redhat.com> wrote:
>
> 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 ();
> +
Apart from what Jakub said - this keeps the list non-recycled for example
after DCE if that doesnt call cleanup_cfg. Likewise after passes that call
cleanup_cfg manually. It also doesn't get called after IPA transform
passes (which would require calling on each function).
To at least catch those passes returning 0 (do nothing) I'd place the
call into execute_todo instead, unconditionally on flags.
> /* 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 ();
which would make this redundant as well. I suppose it would be
interesting to see some before/after
statistics of the release_ssa_names pass. I expect the number of
holes removed to increase, hopefully
not too much (esp. important for analysis passes using sbitmaps of SSA names).
> 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
>
