Record missing equivalence

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.

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);
>         }
>

On 03/21/2013 03:44 AM, Richard Biener wrote:
>> +
>> +             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 ...
[ ... ]
Can't hurt.


>
>> +                     && 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 ...
Right.  I guess it couldn't hurt to filter out anything not an 
INTEGER_CST earlier.  While it wouldn't change the ultimate result, it 
does make it clearer to the reader that this doesn't happen for 
non-integer types.

jeff