Patchwork Improve uncprop and coalescing

login
register
mail settings
Submitter Jeff Law
Date June 7, 2013, 6:07 a.m.
Message ID <51B178BA.1000802@redhat.com>
Download mbox | patch
Permalink /patch/249600/
State New
Headers show

Comments

Jeff Law - June 7, 2013, 6:07 a.m.
I stumbled over this while looking at regressions triggered when moving 
certain branch-cost driven transformations from fold-const.c to a later 
point in the pipeline.

The coalescing we do as part of the out-of-ssa process restricts itself 
to only coalescing when the types of the underlying objects are the 
same.  Where same is currently defined as pointer equality on the type.

So if we have a copy or PHI node where the source & dest have 
equivalent, but different types we will not currently coalesce the 
source and destination.

We also have a pass which un-propagates certain equivalences appearing 
as PHI args  when the equivalence is derived from conditionals.  This 
un-propagation pass is primarily meant to improve coalescing and 
ultimately eliminate silly constant initializations and useless copies. 
  That pass also used pointer equality of types when determining if 
unpropagation was profitable.

Rather than using strict pointer equality, we can do better by looking 
at TYPE_CANONICAL when it's available.  Thus objects of the following 
two types (T1 & T2) become candidates for coalescing if they are tied 
together by a copy or PHI node.

typedef int t1;
typedef int t2;


This typically eliminates necessary copies and constant initializations, 
which is good.  The only regression I saw when reviewing the generated 
code & dumps was a case where we got different register allocation on 
one path which in turn inhibited a tail merging opportunity.



Bootstrapped and regression tested on x86_64-linux-gnu.  OK for the trunk?
* gimple.h (gimple_can_coalesce_p): Prototype.
	* tree-ssa-coalesce.c (gimple_can_coalesce_p): New function.
	(create_outofssa_var_map, coalesce_partitions): Use it.
	* tree-ssa-uncprop.c (uncprop_into_successor_phis): Similarly. 
	* tree-ssa-live.c (var_map_base_init): Use TYPE_CANONICAL
	if it's available.

	* gcc.dg/tree-ssa/coalesce-1.c: New test.
Steven Bosscher - June 7, 2013, 8:30 a.m.
On Fri, Jun 7, 2013 at 8:07 AM, Jeff Law wrote:
> Rather than using strict pointer equality, we can do better by looking at
> TYPE_CANONICAL when it's available.  Thus objects of the following two types
> (T1 & T2) become candidates for coalescing if they are tied together by a
> copy or PHI node.
>
> typedef int t1;
> typedef int t2;
>
>
> This typically eliminates necessary copies and constant initializations,
> which is good.

Hmm...  Can't you use types_compatible_p?

Ciao!
Steven
Richard Guenther - June 7, 2013, 9:14 a.m.
On Fri, Jun 7, 2013 at 8:07 AM, Jeff Law <law@redhat.com> wrote:
>
> I stumbled over this while looking at regressions triggered when moving
> certain branch-cost driven transformations from fold-const.c to a later
> point in the pipeline.
>
> The coalescing we do as part of the out-of-ssa process restricts itself to
> only coalescing when the types of the underlying objects are the same.
> Where same is currently defined as pointer equality on the type.
>
> So if we have a copy or PHI node where the source & dest have equivalent,
> but different types we will not currently coalesce the source and
> destination.
>
> We also have a pass which un-propagates certain equivalences appearing as
> PHI args  when the equivalence is derived from conditionals.  This
> un-propagation pass is primarily meant to improve coalescing and ultimately
> eliminate silly constant initializations and useless copies.  That pass also
> used pointer equality of types when determining if unpropagation was
> profitable.
>
> Rather than using strict pointer equality, we can do better by looking at
> TYPE_CANONICAL when it's available.  Thus objects of the following two types
> (T1 & T2) become candidates for coalescing if they are tied together by a
> copy or PHI node.
>
> typedef int t1;
> typedef int t2;
>
>
> This typically eliminates necessary copies and constant initializations,
> which is good.  The only regression I saw when reviewing the generated code
> & dumps was a case where we got different register allocation on one path
> which in turn inhibited a tail merging opportunity.
>
>
>
> Bootstrapped and regression tested on x86_64-linux-gnu.  OK for the trunk?
>
>
>
>
>         * gimple.h (gimple_can_coalesce_p): Prototype.
>         * tree-ssa-coalesce.c (gimple_can_coalesce_p): New function.
>         (create_outofssa_var_map, coalesce_partitions): Use it.
>         * tree-ssa-uncprop.c (uncprop_into_successor_phis): Similarly.
>         * tree-ssa-live.c (var_map_base_init): Use TYPE_CANONICAL
>         if it's available.
>
>         * gcc.dg/tree-ssa/coalesce-1.c: New test.
>
>
> diff --git a/gcc/gimple.h b/gcc/gimple.h
> index b4de403..8ae07c9 100644
> --- a/gcc/gimple.h
> +++ b/gcc/gimple.h
> @@ -1101,6 +1101,9 @@ extern tree tree_ssa_strip_useless_type_conversions
> (tree);
>  extern bool useless_type_conversion_p (tree, tree);
>  extern bool types_compatible_p (tree, tree);
>
> +/* In tree-ssa-coalesce.c */
> +extern bool gimple_can_coalesce_p (tree, tree);
> +
>  /* Return the first node in GIMPLE sequence S.  */
>
>  static inline gimple_seq_node
> diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c
> index 354b5f1..42bea5d 100644
> --- a/gcc/tree-ssa-coalesce.c
> +++ b/gcc/tree-ssa-coalesce.c
> @@ -943,8 +943,7 @@ create_outofssa_var_map (coalesce_list_p cl, bitmap
> used_in_copy)
>                 continue;
>
>               register_ssa_partition (map, arg);
> -             if ((SSA_NAME_VAR (arg) == SSA_NAME_VAR (res)
> -                  && TREE_TYPE (arg) == TREE_TYPE (res))
> +             if (gimple_can_coalesce_p (arg, res)
>                   || (e->flags & EDGE_ABNORMAL))
>                 {
>                   saw_copy = true;
> @@ -985,8 +984,7 @@ create_outofssa_var_map (coalesce_list_p cl, bitmap
> used_in_copy)
>                 if (gimple_assign_copy_p (stmt)
>                      && TREE_CODE (lhs) == SSA_NAME
>                     && TREE_CODE (rhs1) == SSA_NAME
> -                   && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs1)
> -                   && TREE_TYPE (lhs) == TREE_TYPE (rhs1))
> +                   && gimple_can_coalesce_p (lhs, rhs1))
>                   {
>                     v1 = SSA_NAME_VERSION (lhs);
>                     v2 = SSA_NAME_VERSION (rhs1);
> @@ -1037,8 +1035,7 @@ create_outofssa_var_map (coalesce_list_p cl, bitmap
> used_in_copy)
>                     v1 = SSA_NAME_VERSION (outputs[match]);
>                     v2 = SSA_NAME_VERSION (input);
>
> -                   if (SSA_NAME_VAR (outputs[match]) == SSA_NAME_VAR
> (input)
> -                       && TREE_TYPE (outputs[match]) == TREE_TYPE (input))
> +                   if (gimple_can_coalesce_p (outputs[match], input))
>                       {
>                         cost = coalesce_cost (REG_BR_PROB_BASE,
>                                               optimize_bb_for_size_p (bb));
> @@ -1072,8 +1069,7 @@ create_outofssa_var_map (coalesce_list_p cl, bitmap
> used_in_copy)
>                 first = var;
>               else
>                 {
> -                 gcc_assert (SSA_NAME_VAR (var) == SSA_NAME_VAR (first)
> -                             && TREE_TYPE (var) == TREE_TYPE (first));
> +                 gcc_assert (gimple_can_coalesce_p (var, first));
>                   v1 = SSA_NAME_VERSION (first);
>                   v2 = SSA_NAME_VERSION (var);
>                   bitmap_set_bit (used_in_copy, v1);
> @@ -1210,8 +1206,7 @@ coalesce_partitions (var_map map, ssa_conflicts_p
> graph, coalesce_list_p cl,
>        var2 = ssa_name (y);
>
>        /* Assert the coalesces have the same base variable.  */
> -      gcc_assert (SSA_NAME_VAR (var1) == SSA_NAME_VAR (var2)
> -                 && TREE_TYPE (var1) == TREE_TYPE (var2));
> +      gcc_assert (gimple_can_coalesce_p (var1, var2));
>
>        if (debug)
>         fprintf (debug, "Coalesce list: ");
> @@ -1341,3 +1336,32 @@ coalesce_ssa_name (void)
>
>    return map;
>  }

Missing vertical space here

> +/* 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.

> +    return true;
> +
> +  return false;
> +}
> diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c
> index 83a52a0..a624d00 100644
> --- a/gcc/tree-ssa-live.c
> +++ b/gcc/tree-ssa-live.c
> @@ -111,8 +111,12 @@ var_map_base_init (var_map map)
>            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);
> +          underlying decl.
> +
> +          Check gimple_can_coalesce_p when changing this code.  */
> +       m->base.from = (TYPE_CANONICAL (TREE_TYPE (var))
> +                       ? TYPE_CANONICAL (TREE_TYPE (var))
> +                       : TREE_TYPE (var));

eh, but it's made complicated here ... so above do


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.

Thanks,
Richard.

>        /* If base variable hasn't been seen, set it up.  */
>        slot = tree_to_index.find_slot (m, INSERT);
>        if (!*slot)
> diff --git a/gcc/tree-ssa-uncprop.c b/gcc/tree-ssa-uncprop.c
> index 1fbc524..555485a 100644
> --- a/gcc/tree-ssa-uncprop.c
> +++ b/gcc/tree-ssa-uncprop.c
> @@ -474,12 +474,11 @@ uncprop_into_successor_phis (basic_block bb)
>           equiv_hash_elt an_equiv_elt;
>           equiv_hash_elt **slot;
>
> -         /* If the argument is not an invariant, and refers to the same
> -            underlying variable as the PHI result, then there's no
> -            point in un-propagating the argument.  */
> +         /* If the argument is not an invariant and can be potentially
> +            coalesced with the result, then there's no point in
> +            un-propagating the argument.  */
>           if (!is_gimple_min_invariant (arg)
> -             && (SSA_NAME_VAR (arg) == SSA_NAME_VAR (res)
> -                 && TREE_TYPE (arg) == TREE_TYPE (res)))
> +             && gimple_can_coalesce_p (arg, res))
>             continue;
>
>           /* Lookup this argument's value in the hash table.  */
> @@ -493,7 +492,7 @@ uncprop_into_successor_phis (basic_block bb)
>               int j;
>
>               /* Walk every equivalence with the same value.  If we find
> -                one with the same underlying variable as the PHI result,
> +                one that can potentially coalesce with the PHI rsult,
>                  then replace the value in the argument with its equivalent
>                  SSA_NAME.  Use the most recent equivalence as hopefully
>                  that results in shortest lifetimes.  */
> @@ -501,8 +500,7 @@ uncprop_into_successor_phis (basic_block bb)
>                 {
>                   tree equiv = elt->equivalences[j];
>
> -                 if (SSA_NAME_VAR (equiv) == SSA_NAME_VAR (res)
> -                     && TREE_TYPE (equiv) == TREE_TYPE (res))
> +                 if (gimple_can_coalesce_p (equiv, res))
>                     {
>                       SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
>                       break;
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/coalesce-1.c
> b/gcc/testsuite/gcc.dg/tree-ssa/coalesce-1.c
> new file mode 100644
> index 0000000..5cae9ae
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/coalesce-1.c
> @@ -0,0 +1,195 @@
> +/* { dg-do compile } */
> +
> +/* { dg-options "-O2 -fdump-rtl-expand-details" } */
> +
> +typedef long unsigned int size_t;
> +union tree_node;
> +typedef union tree_node *tree;
> +union gimple_statement_d;
> +typedef union gimple_statement_d *gimple;
> +typedef const union tree_node *const_tree;
> +typedef const union gimple_statement_d *const_gimple;
> +struct gimple_seq_d;
> +typedef struct gimple_seq_d *gimple_seq;
> +struct edge_def;
> +typedef struct edge_def *edge;
> +struct basic_block_def;
> +typedef struct basic_block_def *basic_block;
> +typedef const struct basic_block_def *const_basic_block;
> +struct tree_exp
> +{
> +  tree operands[1];
> +};
> +typedef struct ssa_use_operand_d
> +{
> +  tree *use;
> +} ssa_use_operand_t;
> +struct phi_arg_d
> +{
> +  struct ssa_use_operand_d imm_use;
> +};
> +union tree_node
> +{
> +  struct tree_exp exp;
> +};
> +struct function
> +{
> +};
> +extern struct function *cfun;
> +struct edge_def
> +{
> +  unsigned int dest_idx;
> +};
> +static __inline__ void
> +VEC_edge_must_be_pointer_type (void)
> +{
> +  (void) ((edge) 1 == (void *) 1);
> +} typedef struct VEC_edge_base
> +
> +{
> +  unsigned num;
> +  unsigned alloc;
> +  edge vec[1];
> +} VEC_edge_base;
> +typedef struct VEC_edge_none
> +{
> +  VEC_edge_base base;
> +} VEC_edge_none;
> +
> +static __inline__ edge
> +VEC_edge_base_index (const VEC_edge_base * vec_, unsigned ix_,
> +                    const char *file_, unsigned line_, const char
> *function_)
> +{
> +  return vec_->vec[ix_];
> +}
> +
> +typedef struct VEC_edge_gc
> +{
> +  VEC_edge_base base;
> +} VEC_edge_gc;
> +struct basic_block_def
> +{
> +  VEC_edge_gc *succs;
> +};
> +static __inline__ edge
> +single_succ_edge (const_basic_block bb)
> +{
> +  return (VEC_edge_base_index
> +         ((((bb)->succs) ? &((bb)->succs)->base : 0), (0),
> +          "/home/gcc/virgin-gcc/gcc/basic-block.h", 563, __FUNCTION__));
> +}
> +
> +edge find_edge (basic_block, basic_block);
> +typedef tree *def_operand_p;
> +typedef ssa_use_operand_t *use_operand_p;
> +struct gimple_seq_node_d;
> +typedef struct gimple_seq_node_d *gimple_seq_node;
> +struct gimple_seq_node_d
> +{
> +  gimple stmt;
> +};
> +typedef struct
> +{
> +  gimple_seq_node ptr;
> +  gimple_seq seq;
> +  basic_block bb;
> +} gimple_stmt_iterator;
> +struct gimple_statement_phi
> +{
> +  struct phi_arg_d args[1];
> +};
> +union gimple_statement_d
> +{
> +  struct gimple_statement_phi gimple_phi;
> +};
> +extern size_t const gimple_ops_offset_[];
> +static __inline__ tree *
> +gimple_ops (gimple gs)
> +{
> +  size_t off;
> +  off = gimple_ops_offset_[gimple_statement_structure (gs)];
> +  return (tree *) ((char *) gs + off);
> +}
> +
> +static __inline__ tree
> +gimple_op (const_gimple gs, unsigned i)
> +{
> +  return gimple_ops ((((union
> +                       {
> +                       const union gimple_statement_d * _q;
> +                       union gimple_statement_d * _nq;})
> (((gs))))._nq))[i];
> +}
> +
> +static __inline__ struct phi_arg_d *
> +gimple_phi_arg (gimple gs, unsigned index)
> +{
> +  return &(gs->gimple_phi.args[index]);
> +}
> +
> +static __inline__ tree
> +gimple_switch_label (const_gimple gs, unsigned index)
> +{
> +  return gimple_op (gs, index + 1);
> +}
> +
> +gimple_stmt_iterator gsi_start_phis (basic_block);
> +extern basic_block label_to_block_fn (struct function *, tree);
> +
> +static __inline__ tree
> +get_use_from_ptr (use_operand_p use)
> +{
> +  return *(use->use);
> +}
> +
> +static __inline__ use_operand_p
> +gimple_phi_arg_imm_use_ptr (gimple gs, int i)
> +{
> +  return &gimple_phi_arg (gs, i)->imm_use;
> +}
> +
> +struct switch_conv_info
> +{
> +  basic_block final_bb;
> +  basic_block switch_bb;
> +  const char *reason;
> +  tree *default_values;
> +};
> +static struct switch_conv_info info;
> +
> +static void
> +gather_default_values (tree default_case)
> +{
> +  gimple_stmt_iterator gsi;
> +  basic_block bb =
> +    (label_to_block_fn ((cfun + 0), default_case->exp.operands[2]));
> +  edge e;
> +  int i = 0;
> +  if (bb == info.final_bb)
> +    e = find_edge (info.switch_bb, bb);
> +  else
> +    e = single_succ_edge (bb);
> +  for (gsi = gsi_start_phis (info.final_bb);
> +       gsi_gsi_start_phis (info.final_bb); gsi_next (&gsi))
> +    {
> +      gimple phi = gsi.ptr->stmt;
> +      tree val = get_use_from_ptr (gimple_phi_arg_imm_use_ptr
> +                                  ((((phi))), (((e)->dest_idx))));
> +      info.default_values[i++] = val;
> +    }
> +}
> +
> +unsigned char
> +process_switch (gimple swtch)
> +{
> +  unsigned int i, branch_num = gimple_switch_num_labels (swtch);
> +  tree index_type;
> +  info.reason = "switch has no labels\n";
> +  gather_default_values (gimple_switch_label (swtch, 0));
> +}
> +
> +/* Verify that out-of-ssa coalescing did its job by verifying there are not
> +   any partition copies inserted.  */
> +
> +/* { dg-final { scan-rtl-dump-not "partition copy" "expand"} } */
> +/* { dg-final { cleanup-rtl-dump "expand" } } */
> +
>
Jeff Law - June 7, 2013, 12:50 p.m.
On 06/07/13 02:30, Steven Bosscher wrote:
> On Fri, Jun 7, 2013 at 8:07 AM, Jeff Law wrote:
>> Rather than using strict pointer equality, we can do better by looking at
>> TYPE_CANONICAL when it's available.  Thus objects of the following two types
>> (T1 & T2) become candidates for coalescing if they are tied together by a
>> copy or PHI node.
>>
>> typedef int t1;
>> typedef int t2;
>>
>>
>> This typically eliminates necessary copies and constant initializations,
>> which is good.
>
> Hmm...  Can't you use types_compatible_p?
No.  That was my first inclination.

jeff
Jeff Law - June 12, 2013, 4:44 a.m.
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
Jeff Law - June 12, 2013, 4:04 p.m.
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.
>
>> +    return true;
>> +
>> +  return false;
>> +}
>> diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c
>> index 83a52a0..a624d00 100644
>> --- a/gcc/tree-ssa-live.c
>> +++ b/gcc/tree-ssa-live.c
>> @@ -111,8 +111,12 @@ var_map_base_init (var_map map)
>>             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);
>> +          underlying decl.
>> +
>> +          Check gimple_can_coalesce_p when changing this code.  */
>> +       m->base.from = (TYPE_CANONICAL (TREE_TYPE (var))
>> +                       ? TYPE_CANONICAL (TREE_TYPE (var))
>> +                       : TREE_TYPE (var));
>
> eh, but it's made complicated here ... so above do
>
>
> 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.
Reading this again after a night of sleep, it appears you're agreeing 
that we can't just use types_compatible_p to drive what objects are put 
on the coalesce list.  The only code change you're asking for is to make 
sure we properly reject pointer types with different address spaces 
(which can be done via types_compatible_p).


Right?

jeff
Richard Guenther - Aug. 30, 2013, 9:50 a.m.
On Wed, Jun 12, 2013 at 6:04 PM, Jeff Law <law@redhat.com> wrote:
>
> 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.
>>
>>> +    return true;
>>> +
>>> +  return false;
>>> +}
>>> diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c
>>> index 83a52a0..a624d00 100644
>>> --- a/gcc/tree-ssa-live.c
>>> +++ b/gcc/tree-ssa-live.c
>>> @@ -111,8 +111,12 @@ var_map_base_init (var_map map)
>>>             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);
>>> +          underlying decl.
>>> +
>>> +          Check gimple_can_coalesce_p when changing this code.  */
>>> +       m->base.from = (TYPE_CANONICAL (TREE_TYPE (var))
>>> +                       ? TYPE_CANONICAL (TREE_TYPE (var))
>>> +                       : TREE_TYPE (var));
>>
>>
>> eh, but it's made complicated here ... so above do
>>
>>
>> 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.
>
> Reading this again after a night of sleep, it appears you're agreeing that
> we can't just use types_compatible_p to drive what objects are put on the
> coalesce list.  The only code change you're asking for is to make sure we
> properly reject pointer types with different address spaces (which can be
> done via types_compatible_p).
>
>
> Right?

Yes, if I remember correctly after this long time ;)

Richard.

> jeff
>
>

Patch

diff --git a/gcc/gimple.h b/gcc/gimple.h
index b4de403..8ae07c9 100644
--- a/gcc/gimple.h
+++ b/gcc/gimple.h
@@ -1101,6 +1101,9 @@  extern tree tree_ssa_strip_useless_type_conversions (tree);
 extern bool useless_type_conversion_p (tree, tree);
 extern bool types_compatible_p (tree, tree);
 
+/* In tree-ssa-coalesce.c */
+extern bool gimple_can_coalesce_p (tree, tree);
+
 /* Return the first node in GIMPLE sequence S.  */
 
 static inline gimple_seq_node
diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c
index 354b5f1..42bea5d 100644
--- a/gcc/tree-ssa-coalesce.c
+++ b/gcc/tree-ssa-coalesce.c
@@ -943,8 +943,7 @@  create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
 		continue;
 
 	      register_ssa_partition (map, arg);
-	      if ((SSA_NAME_VAR (arg) == SSA_NAME_VAR (res)
-		   && TREE_TYPE (arg) == TREE_TYPE (res))
+	      if (gimple_can_coalesce_p (arg, res)
 		  || (e->flags & EDGE_ABNORMAL))
 		{
 		  saw_copy = true;
@@ -985,8 +984,7 @@  create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
 		if (gimple_assign_copy_p (stmt)
                     && TREE_CODE (lhs) == SSA_NAME
 		    && TREE_CODE (rhs1) == SSA_NAME
-		    && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs1)
-		    && TREE_TYPE (lhs) == TREE_TYPE (rhs1))
+		    && gimple_can_coalesce_p (lhs, rhs1))
 		  {
 		    v1 = SSA_NAME_VERSION (lhs);
 		    v2 = SSA_NAME_VERSION (rhs1);
@@ -1037,8 +1035,7 @@  create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
 		    v1 = SSA_NAME_VERSION (outputs[match]);
 		    v2 = SSA_NAME_VERSION (input);
 
-		    if (SSA_NAME_VAR (outputs[match]) == SSA_NAME_VAR (input)
-			&& TREE_TYPE (outputs[match]) == TREE_TYPE (input))
+		    if (gimple_can_coalesce_p (outputs[match], input))
 		      {
 			cost = coalesce_cost (REG_BR_PROB_BASE,
 					      optimize_bb_for_size_p (bb));
@@ -1072,8 +1069,7 @@  create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy)
 		first = var;
 	      else
 		{
-		  gcc_assert (SSA_NAME_VAR (var) == SSA_NAME_VAR (first)
-			      && TREE_TYPE (var) == TREE_TYPE (first));
+		  gcc_assert (gimple_can_coalesce_p (var, first));
 		  v1 = SSA_NAME_VERSION (first);
 		  v2 = SSA_NAME_VERSION (var);
 		  bitmap_set_bit (used_in_copy, v1);
@@ -1210,8 +1206,7 @@  coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
       var2 = ssa_name (y);
 
       /* Assert the coalesces have the same base variable.  */
-      gcc_assert (SSA_NAME_VAR (var1) == SSA_NAME_VAR (var2)
-		  && TREE_TYPE (var1) == TREE_TYPE (var2));
+      gcc_assert (gimple_can_coalesce_p (var1, var2));
 
       if (debug)
 	fprintf (debug, "Coalesce list: ");
@@ -1341,3 +1336,32 @@  coalesce_ssa_name (void)
 
   return map;
 }
+/* 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))
+    return true;
+
+  return false;
+}
diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c
index 83a52a0..a624d00 100644
--- a/gcc/tree-ssa-live.c
+++ b/gcc/tree-ssa-live.c
@@ -111,8 +111,12 @@  var_map_base_init (var_map map)
 	   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);
+	   underlying decl. 
+
+	   Check gimple_can_coalesce_p when changing this code.  */
+	m->base.from = (TYPE_CANONICAL (TREE_TYPE (var))
+			? TYPE_CANONICAL (TREE_TYPE (var))
+			: TREE_TYPE (var));
       /* If base variable hasn't been seen, set it up.  */
       slot = tree_to_index.find_slot (m, INSERT);
       if (!*slot)
diff --git a/gcc/tree-ssa-uncprop.c b/gcc/tree-ssa-uncprop.c
index 1fbc524..555485a 100644
--- a/gcc/tree-ssa-uncprop.c
+++ b/gcc/tree-ssa-uncprop.c
@@ -474,12 +474,11 @@  uncprop_into_successor_phis (basic_block bb)
 	  equiv_hash_elt an_equiv_elt;
 	  equiv_hash_elt **slot;
 
-	  /* If the argument is not an invariant, and refers to the same
-	     underlying variable as the PHI result, then there's no
-	     point in un-propagating the argument.  */
+	  /* If the argument is not an invariant and can be potentially
+	     coalesced with the result, then there's no point in
+	     un-propagating the argument.  */
 	  if (!is_gimple_min_invariant (arg)
-	      && (SSA_NAME_VAR (arg) == SSA_NAME_VAR (res)
-		  && TREE_TYPE (arg) == TREE_TYPE (res)))
+	      && gimple_can_coalesce_p (arg, res))
 	    continue;
 
 	  /* Lookup this argument's value in the hash table.  */
@@ -493,7 +492,7 @@  uncprop_into_successor_phis (basic_block bb)
 	      int j;
 
 	      /* Walk every equivalence with the same value.  If we find
-		 one with the same underlying variable as the PHI result,
+		 one that can potentially coalesce with the PHI rsult,
 		 then replace the value in the argument with its equivalent
 		 SSA_NAME.  Use the most recent equivalence as hopefully
 		 that results in shortest lifetimes.  */
@@ -501,8 +500,7 @@  uncprop_into_successor_phis (basic_block bb)
 		{
 		  tree equiv = elt->equivalences[j];
 
-		  if (SSA_NAME_VAR (equiv) == SSA_NAME_VAR (res)
-		      && TREE_TYPE (equiv) == TREE_TYPE (res))
+		  if (gimple_can_coalesce_p (equiv, res))
 		    {
 		      SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
 		      break;
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/coalesce-1.c b/gcc/testsuite/gcc.dg/tree-ssa/coalesce-1.c
new file mode 100644
index 0000000..5cae9ae
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/coalesce-1.c
@@ -0,0 +1,195 @@ 
+/* { dg-do compile } */
+
+/* { dg-options "-O2 -fdump-rtl-expand-details" } */
+
+typedef long unsigned int size_t;
+union tree_node;
+typedef union tree_node *tree;
+union gimple_statement_d;
+typedef union gimple_statement_d *gimple;
+typedef const union tree_node *const_tree;
+typedef const union gimple_statement_d *const_gimple;
+struct gimple_seq_d;
+typedef struct gimple_seq_d *gimple_seq;
+struct edge_def;
+typedef struct edge_def *edge;
+struct basic_block_def;
+typedef struct basic_block_def *basic_block;
+typedef const struct basic_block_def *const_basic_block;
+struct tree_exp
+{
+  tree operands[1];
+};
+typedef struct ssa_use_operand_d
+{
+  tree *use;
+} ssa_use_operand_t;
+struct phi_arg_d
+{
+  struct ssa_use_operand_d imm_use;
+};
+union tree_node
+{
+  struct tree_exp exp;
+};
+struct function
+{
+};
+extern struct function *cfun;
+struct edge_def
+{
+  unsigned int dest_idx;
+};
+static __inline__ void
+VEC_edge_must_be_pointer_type (void)
+{
+  (void) ((edge) 1 == (void *) 1);
+} typedef struct VEC_edge_base
+
+{
+  unsigned num;
+  unsigned alloc;
+  edge vec[1];
+} VEC_edge_base;
+typedef struct VEC_edge_none
+{
+  VEC_edge_base base;
+} VEC_edge_none;
+
+static __inline__ edge
+VEC_edge_base_index (const VEC_edge_base * vec_, unsigned ix_,
+		     const char *file_, unsigned line_, const char *function_)
+{
+  return vec_->vec[ix_];
+}
+
+typedef struct VEC_edge_gc
+{
+  VEC_edge_base base;
+} VEC_edge_gc;
+struct basic_block_def
+{
+  VEC_edge_gc *succs;
+};
+static __inline__ edge
+single_succ_edge (const_basic_block bb)
+{
+  return (VEC_edge_base_index
+	  ((((bb)->succs) ? &((bb)->succs)->base : 0), (0),
+	   "/home/gcc/virgin-gcc/gcc/basic-block.h", 563, __FUNCTION__));
+}
+
+edge find_edge (basic_block, basic_block);
+typedef tree *def_operand_p;
+typedef ssa_use_operand_t *use_operand_p;
+struct gimple_seq_node_d;
+typedef struct gimple_seq_node_d *gimple_seq_node;
+struct gimple_seq_node_d
+{
+  gimple stmt;
+};
+typedef struct
+{
+  gimple_seq_node ptr;
+  gimple_seq seq;
+  basic_block bb;
+} gimple_stmt_iterator;
+struct gimple_statement_phi
+{
+  struct phi_arg_d args[1];
+};
+union gimple_statement_d
+{
+  struct gimple_statement_phi gimple_phi;
+};
+extern size_t const gimple_ops_offset_[];
+static __inline__ tree *
+gimple_ops (gimple gs)
+{
+  size_t off;
+  off = gimple_ops_offset_[gimple_statement_structure (gs)];
+  return (tree *) ((char *) gs + off);
+}
+
+static __inline__ tree
+gimple_op (const_gimple gs, unsigned i)
+{
+  return gimple_ops ((((union
+			{
+			const union gimple_statement_d * _q;
+			union gimple_statement_d * _nq;}) (((gs))))._nq))[i];
+}
+
+static __inline__ struct phi_arg_d *
+gimple_phi_arg (gimple gs, unsigned index)
+{
+  return &(gs->gimple_phi.args[index]);
+}
+
+static __inline__ tree
+gimple_switch_label (const_gimple gs, unsigned index)
+{
+  return gimple_op (gs, index + 1);
+}
+
+gimple_stmt_iterator gsi_start_phis (basic_block);
+extern basic_block label_to_block_fn (struct function *, tree);
+
+static __inline__ tree
+get_use_from_ptr (use_operand_p use)
+{
+  return *(use->use);
+}
+
+static __inline__ use_operand_p
+gimple_phi_arg_imm_use_ptr (gimple gs, int i)
+{
+  return &gimple_phi_arg (gs, i)->imm_use;
+}
+
+struct switch_conv_info
+{
+  basic_block final_bb;
+  basic_block switch_bb;
+  const char *reason;
+  tree *default_values;
+};
+static struct switch_conv_info info;
+
+static void
+gather_default_values (tree default_case)
+{
+  gimple_stmt_iterator gsi;
+  basic_block bb =
+    (label_to_block_fn ((cfun + 0), default_case->exp.operands[2]));
+  edge e;
+  int i = 0;
+  if (bb == info.final_bb)
+    e = find_edge (info.switch_bb, bb);
+  else
+    e = single_succ_edge (bb);
+  for (gsi = gsi_start_phis (info.final_bb);
+       gsi_gsi_start_phis (info.final_bb); gsi_next (&gsi))
+    {
+      gimple phi = gsi.ptr->stmt;
+      tree val = get_use_from_ptr (gimple_phi_arg_imm_use_ptr
+				   ((((phi))), (((e)->dest_idx))));
+      info.default_values[i++] = val;
+    }
+}
+
+unsigned char
+process_switch (gimple swtch)
+{
+  unsigned int i, branch_num = gimple_switch_num_labels (swtch);
+  tree index_type;
+  info.reason = "switch has no labels\n";
+  gather_default_values (gimple_switch_label (swtch, 0));
+}
+
+/* Verify that out-of-ssa coalescing did its job by verifying there are not
+   any partition copies inserted.  */
+
+/* { dg-final { scan-rtl-dump-not "partition copy" "expand"} } */
+/* { dg-final { cleanup-rtl-dump "expand" } } */
+