Re: [PR64164] drop copyrename, integrate into expand

[Jeff Law <law@redhat.com>]

On 03/28/2015 01:21 PM, Alexandre Oliva wrote:
> On Mar 27, 2015, Alexandre Oliva <aoliva@redhat.com> wrote:
>
>> This patch reworks the out-of-ssa expander to enable coalescing of SSA
>> partitions that don't share the same base name.  This is done only when
>> optimizing.
>
>> The test we use to tell whether two partitions can be merged no longer
>> demands them to have the same base variable when optimizing, so they
>> become eligible for coalescing, as they would after copyrename.  We then
>> compute the partitioning we'd get if all coalescible partitions were
>> coalesced, using this partition assignment to assign base vars numbers.
>> These base var numbers are then used to identify conflicts, which used
>> to be based on shared base vars or base types.
>
>> We now propagate base var names during coalescing proper, only towards
>> the leader variable.  I'm no longer sure this is still needed, but
>> something about handling variables and results led me this way and I
>> didn't revisit it.  I might rework that with a later patch, or a later
>> revision of this patch; it would require other means to identify
>> partitions holding result_decls during merging, or allow that and deal
>> with param and result decls in a different way during expand proper.
>
>> I had to fix two lingering bugs in order for the whole thing to work: we
>> perform conflict detection after abnormal coalescing, but we computed
>> live ranges involving only the partition leaders, so conflicts with
>> other names already coalesced wouldn't be detected.
>
> This early abnormal coalescing was only present for a few days in the
> trunk, and I was lucky enough to start working on a tree that had it.
> It turns out that the fix for it was thus rendered unnecessary, so I
> dropped it.  It was the fix for it, that didn't cover the live range
> check, that caused the two ICEs I saw in the regressions tests.  Since
> the ultimate cause of the problem is gone, and the change that
> introduced the check failures, both problems went *poof* after I updated
> the tree, resolved the conflicts and dropped the redundant code.
>
>> The other problem was that we didn't track default defs for parms as
>> live at entry, so they might end up coalesced.
>
> I improved this a little bit, using the bitmap of partitions containing
> default params to check that we only process function-entry defs for
> them, rather than for all param decls in case they end up in other
> partitions.
>
>> I guess none of these problems would have been exercised in practice,
>> because we wouldn't even consider merging ssa names associated with
>> different variables.
>
>> In the end, I verified that this fixed the codegen regression in the
>> PR64164 testcase, that failed to merge two partitions that could in
>> theory be merged, but that wasn't even considered due to differences in
>> the SSA var names.
>
>> I'd agree that disregarding the var names and dropping 4 passes is too
>> much of a change to fix this one problem, but...  it's something we
>> should have long tackled, and it gets this and other jobs done, so...
>
> Regstrapped on x86_64-linux-gnu native and on i686-pc-linux-gnu native
> on x86_64, so without lto plugin.  The only regression is in
> gcc.dg/guality/pr54200.c, that explicitly disables VTA.  When
> optimization is enabled, the different coalescing we perform now causes
> VTA-less variable tracking to lose track of variable "z".  This
> regression in non-VTA var-tracking is expected and, as richi put it in
> PR 64164, I guess we don't care about that, do we? :-)
>
> The other guality regressions I mentioned in my other email turned out
> not to be regressions, but preexisting failures that somehow did not
> make to the test_summary of my earlier pristine build.
>
> Is this ok to install?
>
>
> for  gcc/ChangeLog
>
> 	PR rtl-optimization/64164
> 	* Makefile.in (OBJS): Drop tree-ssa-copyrename.o.
> 	* tree-ssa-copyrename.c: Removed.
> 	* opts.c (default_options_table): Drop -ftree-copyrename.
> 	* passes.def: Drop all occurrences of pass_rename_ssa_copies.
> 	* common.opt (ftree-copyrename): Ignore.
> 	(ftree-coalesce-vars, ftree-coalesce-inlined-vars): Likewise.
> 	* doc/invoke.texi: Remove the ignored options above.
> 	* gimple-expr.c (gimple_can_coalesce_p): Allow coalescing
> 	across base variables when optimizing.
> 	* tree-ssa-coalesce.c (build_ssa_conflict_graph): Add
> 	param_defaults argument.  Process PARM_DECLs's default defs at
> 	the entry point.
> 	(attempt_coalesce): Add param_defaults argument, and
> 	track the presence of default defs for params in each
> 	partition.  Propagate base var to leader on merge, preferring
> 	parms and results, named vars, ignored vars, and then anon
> 	vars.  Refuse to merge a RESULT_DECL partition with a default
> 	PARM_DECL one.
> 	(coalesce_partitions): Add param_defaults argument,
> 	and pass it to attempt_coalesce.
> 	(dump_part_var_map): New.
> 	(compute_optimized_partition_bases): New, called by...
> 	(coalesce_ssa_name): ... when optimizing, disabling
> 	partition_view_bitmap's base assignment.  Pass local
> 	param_defaults to coalescer functions.
> 	* tree-ssa-live.c (var_map_base_init): Note use only when not
> 	optimizing.
> ---
>   gcc/Makefile.in           |    1
>   gcc/common.opt            |   12 +
>   gcc/doc/invoke.texi       |   29 ---
>   gcc/gimple-expr.c         |    7 -
>   gcc/opts.c                |    1
>   gcc/passes.def            |    5
>   gcc/tree-ssa-coalesce.c   |  342 ++++++++++++++++++++++++++++++-
>   gcc/tree-ssa-copyrename.c |  499 ---------------------------------------------
>   gcc/tree-ssa-live.c       |    5
>   9 files changed, 347 insertions(+), 554 deletions(-)
>   delete mode 100644 gcc/tree-ssa-copyrename.c
>
> diff --git a/gcc/gimple-expr.c b/gcc/gimple-expr.c
> index efc93b7..62ae577 100644
> --- a/gcc/gimple-expr.c
> +++ b/gcc/gimple-expr.c
> @@ -399,13 +399,14 @@ copy_var_decl (tree var, tree name, tree type)
>   bool
>   gimple_can_coalesce_p (tree name1, tree name2)
>   {
> -  /* First check the SSA_NAME's associated DECL.  We only want to
> -     coalesce if they have the same DECL or both have no associated DECL.  */
> +  /* First check the SSA_NAME's associated DECL.  Without
> +     optimization, we only want to coalesce if they have the same DECL
> +     or both have no associated DECL.  */
>     tree var1 = SSA_NAME_VAR (name1);
>     tree var2 = SSA_NAME_VAR (name2);
>     var1 = (var1 && (!VAR_P (var1) || !DECL_IGNORED_P (var1))) ? var1 : NULL_TREE;
>     var2 = (var2 && (!VAR_P (var2) || !DECL_IGNORED_P (var2))) ? var2 : NULL_TREE;
> -  if (var1 != var2)
> +  if (var1 != var2 && !optimize)
>       return false;
So when when the base variables are different and we are optimizing, 
this allows coalescing, right?

What I don't see is a corresponding change to var_map_base_init to 
ensure we build a conflict graph which includes objects when 
SSA_NAME_VARs are not the same.  I see a vague reference in 
var_map_base_init's header comment that refers us to coalesce_ssa_name.

It appears that compute_optimized_partition_bases handles this by 
creating a partitions of things that are related by copies/phis 
regardless of their underlying named object, type, etc.  Right?





> index 1d598b2..f8fd0ef 100644
> --- a/gcc/passes.def
> +++ b/gcc/passes.def
[ ... ]
Hard to argue with removing a pass that gets called 5 times!


> @@ -890,6 +900,36 @@ build_ssa_conflict_graph (tree_live_info_p liveinfo)
>   	    live_track_process_def (live, result, graph);
>   	}
>
> +      /* Pretend there are defs for params' default defs at the start
> +	 of the (post-)entry block.  We run after abnormal coalescing,
> +	 so we can't assume the leader variable is the default
> +	 definition, but because of SSA_NAME_VAR adjustments in
> +	 attempt_coalesce, we can assume that if there is any
> +	 PARM_DECL in the partition, it will be the leader's
> +	 SSA_NAME_VAR.  */
So the issue here is you want to iterate over the objects live at the 
entry block, which would include any SSA_NAMEs which result from 
PARM_DECLs.  I don't guess there's an easier way to do that other than 
iterating over everything live in that initial block?

And the second second EXECUTE_IF_SET_IN_BITMAP iterates over everything 
in the partitions associated with the SSA_NAMES that are live at the the 
entry block, right?

I don't guess it'd be more efficient to walk over the SSA_NAMEs looking 
for anything marked as a default definition, then map that back to a 
partition since we'd have to look at every SSA_NAME whereas your code 
only looks at paritions that are live in the entry block, then looks at 
the elements in those partitions.

> @@ -1126,11 +1166,12 @@ create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
>
>   static inline bool
>   attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
> -		  FILE *debug)
> +		  bitmap param_defaults, FILE *debug)
[ ... ]
So the bulk of the changes into this routine are really about picking a 
good leader, which presumably is how we're able to get the desired 
effects on debuginfo that we used to get from tree-ssa-copyrename.c?


> @@ -1158,6 +1199,70 @@ attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
>       {
>         var1 = partition_to_var (map, p1);
>         var2 = partition_to_var (map, p2);
> +
> +      tree leader;
> +
> +      if (var1 == var2 || !SSA_NAME_VAR (var2)
> +	  || SSA_NAME_VAR (var1) == SSA_NAME_VAR (var2))
> +	{
> +	  leader = SSA_NAME_VAR (var1);
> +	  default_def = (leader && TREE_CODE (leader) == PARM_DECL
> +			 && (SSA_NAME_IS_DEFAULT_DEF (var1)
> +			     || bitmap_bit_p (param_defaults, p1)));
> +	}
So some comments about the various cases here might help.  I can sort 
them out if I read the code, but one could argue that a block comment on 
the rules for how to select the partition leader would be better.

Is the special casing of PARM_DECLs + RESULT_DECLs really a failing of 
not handling one or both properly when computing liveness information?

I'm not aware of an inherent reason why a PARM_DECL couldn't coalesce 
with a related RESULT_DECL if they are otherwise non-conflicting and 
related by a copy/phi.


> @@ -1272,6 +1415,178 @@ ssa_name_var_hash::equal (const value_type *n1, const compare_type *n2)
> +
> +/* Fill in MAP's partition_to_base_index, with one index for each
> +   partition of SSA names USED_IN_COPIES and related by CL
> +   coalesce possibilities.  */
> +
> +static void
> +compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
> +				   coalesce_list_p cl)
Presumably ordering of unioning of the partitions doesn't matter here as 
we're looking at coalesce possibilities rather than things we have 
actually coalesced?  Thus it's OK (?) to handle the names occurring in 
abnormal PHIs after those names that are associated by a copy.

This is all probably OK, but I want to make sure I understand what's 
happening before a final approval.

jeff