Re: Improve uncprop and coalescing

[Richard Biener <richard dot guenther at gmail dot com>]

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" } } */
> +
>