Re: Improve uncprop and coalescing

[Jeff Law <law@redhat.com>]

On 06/07/13 03:14, Richard Biener wrote:
>
>
>> +/* Given SSA_NAMEs NAME1 and NAME2, return true if they are candidates for
>> +   coalescing together, false otherwise.
>> +
>> +   This must stay consistent with the code in tree-ssa-live.c which
>> +   sets up base values in the var map.  */
>> +
>> +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.
>> */
>> +  if (SSA_NAME_VAR (name1) != SSA_NAME_VAR (name2))
>> +    return false;
>> +
>> +  /* Now check the types.  If the types are the same, then we should
>> +     try to coalesce V1 and V2.  */
>> +  tree t1 = TREE_TYPE (name1);
>> +  tree t2 = TREE_TYPE (name2);
>> +  if (t1 == t2)
>> +    return true;
>> +
>> +  /* If the types are not the same, check for a canonical type match.  This
>> +     (for example) allows coalescing when the types are fundamentally the
>> +     same, but just have different names.  */
>> +  if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2))
>
> Please use types_compatible_p (t1, t2) here, that's the correct API to use
> here.
No it isn't.  types_compatible_p is far too permissive in this context 
without more surgery to tree-ssa-live.c.

So let's take two objects, P1 and P2 which are pointers to types T1 and 
T2 where T1 != T2.  Assume P1 and P2 are somehow connected by a copy or 
PHI node and that they are anonymously named objects.

types_compatible_p will return true for (T1, T2) unless T1 or T2 is a 
pointer to a function.  So if we used types_compatible_p we will try to 
coalesce P1 and P2 (which is seemingly a good thing).

Now in tree-ssa-live.c::var_map_base_init we have:

   /* Build the base variable list, and point partitions at their bases.  */
   for (x = 0; x < num_part; x++)
     {
       ...
       if (SSA_NAME_VAR (var))
         m->base.from = SSA_NAME_VAR (var);
       else
         /* This restricts what anonymous SSA names we can coalesce
            as it restricts the sets we compute conflicts for.
            Using TREE_TYPE to generate sets is the easies as
            type equivalency also holds for SSA names with the same
            underlying decl.  */
         m->base.from = TREE_TYPE (var);
       ...
     }

The way we set up base.from in var_map_base_init imposes requirements on 
what objects can be added to the coalescing lists.  We can only allow 
coalescing of objects with the same underlying SSA_NAME_VAR or anonymous 
objects with the same underlying TREE_TYPE (as the code is written 
today).  That's a side effect of restricting the sets we compute 
conflicts for.  If we don't compute the conflicts, then we'll assume P1 
and P2 don't conflict and happily coalesce them, regardless of whether 
or not they actually do conflict.

To use types_compatible_p to drive decisions in tree-ssa-coalesce.c, 
ISTM we'd have to change this code from tree-ssa-live.c to put all 
anonymous objects with a compatible type in the same hash entry.  I 
don't see a good way to do that without iterating over the hash table 
entries looking for a compatible match or completely reimplementing the 
hash.

By first checking if an anonymous variable's type has an underlying 
canonical type and using that instead to key decisions in 
var_map_base_init, we can allow more objects onto the coalescing lists 
in tree-ssa-coalesce.c.  In particular we can allow two anonymous 
objects where both have an underlying TYPE_CANONICAL that is the same.

>
>
> if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2)
>      && types_compatible_p (t1, t2))
>
> because looking at useless_type_conversion_p it looks like pointer types
> with different address-spaces may have the same canonical type.  A comment
> on why we check both, refering to var_map_base_init should also be added.
>
> Ok with that change.
Seems to make sense.  Though we still have a point of contention around 
whether or not we can use types_compatible_p to drive decisions in 
tree-ssa-coalesce.c.  I'm pretty sure we can't without some significant 
surgery in tree-ssa-live.c.

Jeff