Re: Record missing equivalence

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

On Thu, Mar 21, 2013 at 5:43 AM, Jeff Law <law@redhat.com> wrote:
>
> This was something I spotted while looking at why certain redundant
> conditionals were not eliminated.  In particular this affects the compiler's
> ability to eliminate a variety of gimple checking tests.
>
> Consider an equality comparison
>
> if (a == 10)
>   true arm
> else
>   else arm
>
> We obviously want to record an equivalence so that we can replace uses of
> "a" in the true arm with "10".
>
> Now consider if "a" was set by a widening type conversion.
>
>
> a = (int) z;  /* Assume Z is a narrower type */
> if (a == 10)
>   true arm
> else
>   else arm
>
> We'd really like to also record an equivalence for "z" in the true arm so
> that uses of "z" can be replaced with "10".  We restrict this to widening
> conversions where the constant is equal in both the original and widened
> type.
>
> That's precisely what this patch does.  When we're going to record an
> equivalence from an equality comparison between an SSA_NAME and a constant,
> we look to see if the SSA_NAME was set from widening conversion and verify
> the constant is the same in both the original and widened type.  When true,
> we record the additional equivalence.
>
> As I mentioned, this ultimately allows us to discover more redundant
> conditionals for gimple checking and eliminate them.
>
> The included testcase is drastically simplified and merely tests for whether
> or not we record & propagate the additional equivalence.  It does not show
> the eliminated tests.
>
> Bootstrapped and regression tested on x86_64-unknown-linux-gnu. Installed on
> the trunk.
>
>
> commit 4c7d3ee54cf7035b247c685a68968d0a60b01601
> Author: Jeff Law <law@redhat.com>
> Date:   Wed Mar 20 22:39:13 2013 -0600
>
>         * tree-ssa-dom.c (record_equivalences_from_incoming_edge): Record
>         addititional equivalences for equality comparisons between an
> SSA_NAME
>         and a constant where the SSA_NAME was set from a widening
> conversion.
>
>         * g++.dg/tree-ssa/ssa-dom.C: New test.
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 5ecdc8f..5f93edd 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,9 @@
> +2013-03-20  Jeff Law  <law@redhat.com>
> +
> +       * tree-ssa-dom.c (record_equivalences_from_incoming_edge): Record
> +       addititional equivalences for equality comparisons between an
> SSA_NAME
> +       and a constant where the SSA_NAME was set from a widening
> conversion.
> +
>  2013-03-20  Walter Lee  <walt@tilera.com>
>
>         * config/tilegx/sync.md (atomic_test_and_set): New pattern.
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index 93d02bb..99a366d 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,8 @@
> +2013-03-20  Jeff Law  <law@redhat.com>
> +
> +       * g++.dg/tree-ssa/ssa-dom.C: New test.
> +
> +
>  2013-03-20  Michael Meissner  <meissner@linux.vnet.ibm.com>
>
>         * gcc.target/powerpc/mmfpgpr.c: New test.
> diff --git a/gcc/testsuite/g++.dg/tree-ssa/ssa-dom.C
> b/gcc/testsuite/g++.dg/tree-ssa/ssa-dom.C
> new file mode 100644
> index 0000000..5f63865
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/tree-ssa/ssa-dom.C
> @@ -0,0 +1,104 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-dom1" } */
> +
> +typedef long unsigned int size_t;
> +extern void abort (void) __attribute__ ((__noreturn__));
> +union tree_node;
> +typedef union tree_node *tree;
> +union gimple_statement_d;
> +typedef union gimple_statement_d *gimple;
> +typedef const union gimple_statement_d *const_gimple;
> +
> +enum gimple_code
> +{
> +  GIMPLE_RETURN = 10,
> +};
> +
> +
> +
> +
> +
> +struct gimple_statement_base
> +{
> +
> +
> +  enum gimple_code code:8;
> +};
> +
> +
> +enum gimple_statement_structure_enum
> +{
> +  xyz
> +};
> +
> +
> +
> +
> +
> +
> +union gimple_statement_d
> +{
> +  struct gimple_statement_base gsbase;
> +};
> +
> +
> +
> +
> +
> +extern size_t const gimple_ops_offset_[];
> +
> +
> +extern enum gimple_statement_structure_enum const gss_for_code_[];
> +
> +
> +static inline enum gimple_code
> +gimple_code (const_gimple g)
> +{
> +  return g->gsbase.code;
> +}
> +
> +
> +
> +
> +static inline enum gimple_statement_structure_enum
> +gss_for_code (enum gimple_code code)
> +{
> +  return gss_for_code_[code];
> +}
> +
> +
> +
> +
> +static inline enum gimple_statement_structure_enum
> +gimple_statement_structure (gimple gs)
> +{
> +  return gss_for_code (gimple_code (gs));
> +}
> +
> +
> +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 void
> +gimple_set_op (gimple gs, unsigned i, tree op)
> +{
> +  gimple_ops (gs)[i] = op;
> +}
> +
> +void
> +gimple_return_set_retval (gimple gs, tree retval)
> +{
> +  const_gimple __gs = (gs);
> +  if (gimple_code (__gs) != (GIMPLE_RETURN))
> +    abort ();
> +  gimple_set_op (gs, 0, retval);
> +}
> +/* { dg-final { scan-tree-dump-times "gss_for_code_.10." 1 "dom1"} } */
> +/* { dg-final { cleanup-tree-dump "dom1" } } */
> +
> diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
> index e8b1551..57b814c 100644
> --- a/gcc/tree-ssa-dom.c
> +++ b/gcc/tree-ssa-dom.c
> @@ -1135,6 +1135,33 @@ record_equivalences_from_incoming_edge (basic_block
> bb)
>           if (lhs)
>             record_equality (lhs, rhs);
>
> +         /* If LHS is an SSA_NAME and RHS is a constant and LHS was set
> +            via a widening type conversion, then we may be able to record
> +            additional equivalences.  */
> +         if (lhs
> +             && TREE_CODE (lhs) == SSA_NAME
> +             && is_gimple_constant (rhs))
> +           {
> +             gimple defstmt = SSA_NAME_DEF_STMT (lhs);
> +
> +             if (defstmt
> +                 && is_gimple_assign (defstmt)
> +                 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (defstmt)))
> +               {
> +                 tree old_rhs = gimple_assign_rhs1 (defstmt);
> +                 tree newval = fold_convert (TREE_TYPE (old_rhs), rhs);

You want to delay that folding and creating of a new tree node until after ...

> +
> +                 /* If this was a widening conversion and if RHS is
> converted
> +                    to the type of OLD_RHS and has the same value, then we
> +                    can record an equivalence between OLD_RHS and the
> +                    converted representation of RHS.  */
> +                 if ((TYPE_PRECISION (TREE_TYPE (lhs))
> +                      > TYPE_PRECISION (TREE_TYPE (old_rhs)))

... this check.

> +                     && operand_equal_p (rhs, newval, 0))

If you'd restricted yourself to handling INTEGER_CSTs then using
int_fits_type_p (rhs, TREE_TYPE (lhs)) would have been enough to check.

And operand_equal_p will never return for non-equal typed non-INTEGER_CSTs
anyway ...

Richard.

> +                   record_equality (old_rhs, newval);
> +               }
> +           }
> +
>           for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i)
>             record_cond (eq);
>         }
>