Update SSA_NAME manager to use two lists

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.

On Wed, Sep 30, 2015 at 11:44:38AM -0600, Jeff Law wrote:
> +/* 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);
> +    }

Isn't it faster to just do:
  vec_safe_splice (FREE_SSANAMES (cfun), FREE_SSANAMES_QUEUE (cfun));
  vec_safe_truncate (FREE_SSANAMES_QUEUE (cfun));
or so?  I mean, rather than reallocating the vector perhaps many times
grow it just once to the exact size, and memcpy there the data.

	Jakub

On 09/30/2015 12:46 PM, Jakub Jelinek wrote:
> On Wed, Sep 30, 2015 at 11:44:38AM -0600, Jeff Law wrote:
>> +/* 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);
>> +    }
>
> Isn't it faster to just do:
>    vec_safe_splice (FREE_SSANAMES (cfun), FREE_SSANAMES_QUEUE (cfun));
>    vec_safe_truncate (FREE_SSANAMES_QUEUE (cfun));
> or so?  I mean, rather than reallocating the vector perhaps many times
> grow it just once to the exact size, and memcpy there the data.
Probably.

I'm pondering a bit of refactoring in there, I'll look at fixing this 
while I'm in there.

jeff

On Wed, Sep 30, 2015 at 7:44 PM, Jeff Law <law@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
>

On 10/01/2015 04:00 AM, Richard Biener wrote:

>
> 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.
I can speculate there's pathological cases where it'd be useful, but 
that in the general case it'll be small.  It's easy enough to do some 
testing around this.

I'm also still pondering whether or not to have the code simply adapt 
itself to the conditions.   Essentially allowing immediate recycling up 
until the point where we release an SSA_NAME after removing an edge. 
At that point it'd switch to deferred mode until the next time the 
pending list is flushed.

We'd have to arrange to get notified of edge removals, obviously.  I'm 
also still pondering the long term safety issues of that scheme as well 
as the implementation & testing details.


>>
>> @@ -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).
There's some TLC that needs to happen in pass_release_ssa_names -- it 
knows far too much about the underlying details of name management.  All 
that code really belongs in the name manager itself and the pass should 
just issue the call into the name manager to release & pack the data. 
That's one of the refactorings I mentioned in my reply to Jakub.

Essentially this should be driven by the name manager and occur at 
points where it's safe and likely profitable.  Safe points occur between 
passes.  Profitability can likely be estimated cheaply within the 
manager itself since it has a good handle on what's in the free lists vs 
the overall size of the name table.

The other area ripe for refactoring and extension are the verification 
bits.  I was torn whether or not to tackle that first or as a follow-up. 
  I ultimately chose the latter.

Jeff

On 10/01/2015 04:00 AM, Richard Biener wrote:

> 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.
As I suspected, the effect of doing this is small.  Just under 1% 
increase in reused SSA_NAMEs (using an older version of GCC as input 
test files).

And just for future reference, the recycled vs allocated ratio is just 
under 40%.




>>
>> @@ -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).
Interestingly enough, flushing the pending freelist in execute_todo 
results in marginally fewer holes being found (and it's very marginal -- 
.04%).  Presumably that's because we actually do a better job at 
recycling and thus there's fewer holes to be found when 
pass_release_ssa_names eventually gets called.


Anyway, I'll spin that up.  Hopefully it'll complete before the day is over.

jeff