[PR,tree-optimization/67955] Exploit PTA in DSE

So I was going through the various DSE related bugs as stumbled across 
67955.

The basic issue in 67955 is that DSE is too simplistic when trying to 
determine if two writes hit the same memory address.  There are cases 
were PTA analysis can get us that information.

The unfortunate problem is that PTA can generate a single points-to set 
for pointers to different elements in the same array.  So we can only 
exploit a special case.  Namely when we get a PTA singleton and the size 
of the store is the same size of the pointed-to object.

That doesn't happen in a bootstrap, but it does happen for the testcase 
in the BZ as well as a handful of tests in the testsuite -- Tom reported 
6 unique tests where it triggered, I ran my own tests where two more 
were spit out.  Not huge.  But the cost is low.

All that I've done with Tom's patch is update the call into the PTA 
system.  It's very clearly Tom's work.

Bootstrapped and regression tested on x86_64-linux-gnu.  Installing on 
the trunk.

jeff
commit cfc96cf6c8ea2c6e638123a93663964f6d78fb10
Author: law <law@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Tue Dec 6 23:18:17 2016 +0000

    	PR tree-optimization/67955
    	* tree-ssa-alias.c (same_addr_size_stores_p): New function.
    	(stmt_kills_ref_p): Use it.
    
    	PR tree-optimization/67955
    	* gcc.dg/tree-ssa/dse-points-to.c: New test.
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@243325 138bc75d-0d04-0410-961f-82ee72b054a4

On Wed, Dec 7, 2016 at 12:18 AM, Jeff Law <law@redhat.com> wrote:
>
>
> So I was going through the various DSE related bugs as stumbled across
> 67955.
>
> The basic issue in 67955 is that DSE is too simplistic when trying to
> determine if two writes hit the same memory address.  There are cases were
> PTA analysis can get us that information.
>
> The unfortunate problem is that PTA can generate a single points-to set for
> pointers to different elements in the same array.  So we can only exploit a
> special case.  Namely when we get a PTA singleton and the size of the store
> is the same size of the pointed-to object.
>
> That doesn't happen in a bootstrap, but it does happen for the testcase in
> the BZ as well as a handful of tests in the testsuite -- Tom reported 6
> unique tests where it triggered, I ran my own tests where two more were spit
> out.  Not huge.  But the cost is low.
>
> All that I've done with Tom's patch is update the call into the PTA system.
> It's very clearly Tom's work.
>
> Bootstrapped and regression tested on x86_64-linux-gnu.  Installing on the
> trunk.

Just double-checked it doesn't break

int foo (int *p, int b)
{
  int *q;
  int i = 1;
  if (b)
    q = &i;
  else
    q = (void *)0;
  *q = 2;
  return i;
}

with -fexceptions -fnon-call-exceptions.  More comments below.

> jeff
>
> commit cfc96cf6c8ea2c6e638123a93663964f6d78fb10
> Author: law <law@138bc75d-0d04-0410-961f-82ee72b054a4>
> Date:   Tue Dec 6 23:18:17 2016 +0000
>
>         PR tree-optimization/67955
>         * tree-ssa-alias.c (same_addr_size_stores_p): New function.
>         (stmt_kills_ref_p): Use it.
>
>         PR tree-optimization/67955
>         * gcc.dg/tree-ssa/dse-points-to.c: New test.
>
>     git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@243325
> 138bc75d-0d04-0410-961f-82ee72b054a4
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 61eeea3..797b711 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,9 @@
> +2016-12-06  Tom de Vries  <tom@codesourcery.com>
> +
> +       PR tree-optimization/67955
> +       * tree-ssa-alias.c (same_addr_size_stores_p): New function.
> +       (stmt_kills_ref_p): Use it.
> +
>  2016-12-06  Eric Botcazou  <ebotcazou@adacore.com>
>
>         PR middle-end/78700
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index 5adcdd2..6090a96 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,8 @@
> +2016-12-06  Tom de Vries  <tom@codesourcery.com>
> +
> +       PR tree-optimization/67955
> +       * gcc.dg/tree-ssa/dse-points-to.c: New test.
> +
>  2016-12-06  Michael Meissner  <meissner@linux.vnet.ibm.com>
>
>         PR target/78658
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/dse-points-to.c
> b/gcc/testsuite/gcc.dg/tree-ssa/dse-points-to.c
> new file mode 100644
> index 0000000..8003556
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/dse-points-to.c
> @@ -0,0 +1,15 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fno-tree-ccp -fno-tree-forwprop -fno-tree-fre
> -fno-tree-vrp" } */
> +/* { dg-additional-options "-fdump-tree-dse1-details" } */
> +
> +int
> +f ()
> +{
> +  int a;
> +  int *p = &a;
> +  *p = 1;
> +  a = 2;
> +  return a;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Deleted dead store.*p_1" 1 "dse1"} }
> */
> diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
> index 10f1677..37b581d 100644
> --- a/gcc/tree-ssa-alias.c
> +++ b/gcc/tree-ssa-alias.c
> @@ -2316,6 +2316,78 @@ stmt_may_clobber_ref_p (gimple *stmt, tree ref)
>    return stmt_may_clobber_ref_p_1 (stmt, &r);
>  }
>
> +/* Return true if store1 and store2 described by corresponding tuples
> +   <BASE, OFFSET, SIZE, MAX_SIZE> have the same size and store to the same
> +   address.  */
> +
> +static bool
> +same_addr_size_stores_p (tree base1, HOST_WIDE_INT offset1, HOST_WIDE_INT
> size1,
> +                        HOST_WIDE_INT max_size1,
> +                        tree base2, HOST_WIDE_INT offset2, HOST_WIDE_INT
> size2,
> +                        HOST_WIDE_INT max_size2)
> +{
> +  /* For now, just handle VAR_DECL.  */

PARAM and RESULT_DECL (aka SSA_VAR_P) should be safe.

> +  bool base1_obj_p = VAR_P (base1);
> +  bool base2_obj_p = VAR_P (base2);
> +
> +  /* We need one object.  */
> +  if (base1_obj_p == base2_obj_p)
> +    return false;
> +  tree obj = base1_obj_p ? base1 : base2;
> +
> +  /* And we need one MEM_REF.  */
> +  bool base1_memref_p = TREE_CODE (base1) == MEM_REF;
> +  bool base2_memref_p = TREE_CODE (base2) == MEM_REF;
> +  if (base1_memref_p == base2_memref_p)
> +    return false;
> +  tree memref = base1_memref_p ? base1 : base2;
> +
> +  /* Sizes need to be valid.  */
> +  if (max_size1 == -1 || max_size2 == -1
> +      || size1 == -1 || size2 == -1)
> +    return false;
> +
> +  /* Max_size needs to match size.  */
> +  if (max_size1 != size1
> +      || max_size2 != size2)
> +    return false;
> +
> +  /* Sizes need to match.  */
> +  if (size1 != size2)
> +    return false;
> +
> +  /* Offsets need to be 0.  */
> +  if (offset1 != 0
> +      || offset2 != 0)
> +    return false;

These two checks should be done first IMHO.

> +  /* Check that memref is a store to pointer with singleton points-to info.
> */
> +  if (!tree_int_cst_equal (TREE_OPERAND (memref, 1), integer_zero_node))

integer_zerop

> +    return false;
> +  tree ptr = TREE_OPERAND (memref, 0);
> +  if (TREE_CODE (ptr) != SSA_NAME)
> +    return false;
> +  struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
> +  unsigned int pt_uid;
> +  if (pi == NULL
> +      || !pt_solution_singleton_or_null_p (&pi->pt, &pt_uid))
> +    return false;
> +
> +  /* Check that ptr points relative to obj.  */
> +  unsigned int obj_uid = (DECL_PT_UID_SET_P (obj)
> +                         ? DECL_PT_UID (obj)
> +                         : DECL_UID (obj));

Just use DECL_PT_UID.

> +  if (obj_uid != pt_uid)
> +    return false;
> +
> +  /* Check that the object size is the same as the store size.  That
> ensures us
> +     that ptr points to the start of obj.  */
> +  if (!tree_fits_shwi_p (DECL_SIZE (obj)))
> +    return false;
> +  HOST_WIDE_INT obj_size = tree_to_shwi (DECL_SIZE (obj));
> +  return obj_size == size1;
> +}
> +
>  /* If STMT kills the memory reference REF return true, otherwise
>     return false.  */
>
> @@ -2393,6 +2465,11 @@ stmt_kills_ref_p (gimple *stmt, ao_ref *ref)
>          so base == ref->base does not always hold.  */
>        if (base != ref->base)
>         {
> +         /* Try using points-to info.  */
> +         if (same_addr_size_stores_p (base, offset, size, max_size,
> ref->base,
> +                                      ref->offset, ref->size,
> ref->max_size))
> +           return true;
> +
>           /* If both base and ref->base are MEM_REFs, only compare the
>              first operand, and if the second operand isn't equal constant,
>              try to add the offsets into offset and ref_offset.  */
>

On 12/09/2016 01:28 AM, Richard Biener wrote:
> On Wed, Dec 7, 2016 at 12:18 AM, Jeff Law <law@redhat.com> wrote:
>>
>>
>> So I was going through the various DSE related bugs as stumbled across
>> 67955.
>>
>> The basic issue in 67955 is that DSE is too simplistic when trying to
>> determine if two writes hit the same memory address.  There are cases were
>> PTA analysis can get us that information.
>>
>> The unfortunate problem is that PTA can generate a single points-to set for
>> pointers to different elements in the same array.  So we can only exploit a
>> special case.  Namely when we get a PTA singleton and the size of the store
>> is the same size of the pointed-to object.
>>
>> That doesn't happen in a bootstrap, but it does happen for the testcase in
>> the BZ as well as a handful of tests in the testsuite -- Tom reported 6
>> unique tests where it triggered, I ran my own tests where two more were spit
>> out.  Not huge.  But the cost is low.
>>
>> All that I've done with Tom's patch is update the call into the PTA system.
>> It's very clearly Tom's work.
>>
>> Bootstrapped and regression tested on x86_64-linux-gnu.  Installing on the
>> trunk.
>
> Just double-checked it doesn't break
>
> int foo (int *p, int b)
> {
>   int *q;
>   int i = 1;
>   if (b)
>     q = &i;
>   else
>     q = (void *)0;
>   *q = 2;
>   return i;
> }
Right.  ISTM this shouldn't have a singleton points-to set and thus 
shouldn't change behavior.    But looking at things more closely, it 
looks like points-to-null is distinct from the points-to variables.  ie, 
we want to know if its a singleton and ! null.  Thus we have to check
pt_solution_singleton_or_null_p (pi->pt, &pt_uid) && !pi->pt->null

I think it's working for you because the path isolation code splits off 
the NULL dereference path.  Adding 
-fno-isolate-erroneous-paths-dereference to the switches shows DSE2, 
incorrectly IMHO, removing the i = 1 store.

Thoughts?


>
> with -fexceptions -fnon-call-exceptions.  More comments below.
>
>> jeff
>>
>> commit cfc96cf6c8ea2c6e638123a93663964f6d78fb10
>> Author: law <law@138bc75d-0d04-0410-961f-82ee72b054a4>
>> Date:   Tue Dec 6 23:18:17 2016 +0000
>>
>>         PR tree-optimization/67955
>>         * tree-ssa-alias.c (same_addr_size_stores_p): New function.
>>         (stmt_kills_ref_p): Use it.
>>
>>         PR tree-optimization/67955
>>         * gcc.dg/tree-ssa/dse-points-to.c: New test.
>>
>>     git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@243325
>> 138bc75d-0d04-0410-961f-82ee72b054a4
>>
>> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
>> index 61eeea3..797b711 100644
>> --- a/gcc/ChangeLog
>> +++ b/gcc/ChangeLog
>> @@ -1,3 +1,9 @@
>> +2016-12-06  Tom de Vries  <tom@codesourcery.com>
>> +
>> +       PR tree-optimization/67955
>> +       * tree-ssa-alias.c (same_addr_size_stores_p): New function.
>> +       (stmt_kills_ref_p): Use it.
>> +
>>  2016-12-06  Eric Botcazou  <ebotcazou@adacore.com>
>>
>>         PR middle-end/78700
>> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
>> index 5adcdd2..6090a96 100644
>> --- a/gcc/testsuite/ChangeLog
>> +++ b/gcc/testsuite/ChangeLog
>> @@ -1,3 +1,8 @@
>> +2016-12-06  Tom de Vries  <tom@codesourcery.com>
>> +
>> +       PR tree-optimization/67955
>> +       * gcc.dg/tree-ssa/dse-points-to.c: New test.
>> +
>>  2016-12-06  Michael Meissner  <meissner@linux.vnet.ibm.com>
>>
>>         PR target/78658
>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/dse-points-to.c
>> b/gcc/testsuite/gcc.dg/tree-ssa/dse-points-to.c
>> new file mode 100644
>> index 0000000..8003556
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/dse-points-to.c
>> @@ -0,0 +1,15 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fno-tree-ccp -fno-tree-forwprop -fno-tree-fre
>> -fno-tree-vrp" } */
>> +/* { dg-additional-options "-fdump-tree-dse1-details" } */
>> +
>> +int
>> +f ()
>> +{
>> +  int a;
>> +  int *p = &a;
>> +  *p = 1;
>> +  a = 2;
>> +  return a;
>> +}
>> +
>> +/* { dg-final { scan-tree-dump-times "Deleted dead store.*p_1" 1 "dse1"} }
>> */
>> diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
>> index 10f1677..37b581d 100644
>> --- a/gcc/tree-ssa-alias.c
>> +++ b/gcc/tree-ssa-alias.c
>> @@ -2316,6 +2316,78 @@ stmt_may_clobber_ref_p (gimple *stmt, tree ref)
>>    return stmt_may_clobber_ref_p_1 (stmt, &r);
>>  }
>>
>> +/* Return true if store1 and store2 described by corresponding tuples
>> +   <BASE, OFFSET, SIZE, MAX_SIZE> have the same size and store to the same
>> +   address.  */
>> +
>> +static bool
>> +same_addr_size_stores_p (tree base1, HOST_WIDE_INT offset1, HOST_WIDE_INT
>> size1,
>> +                        HOST_WIDE_INT max_size1,
>> +                        tree base2, HOST_WIDE_INT offset2, HOST_WIDE_INT
>> size2,
>> +                        HOST_WIDE_INT max_size2)
>> +{
>> +  /* For now, just handle VAR_DECL.  */
>
> PARAM and RESULT_DECL (aka SSA_VAR_P) should be safe.
Agreed & fixed.

>
>> +  bool base1_obj_p = VAR_P (base1);
>> +  bool base2_obj_p = VAR_P (base2);
>> +
>> +  /* We need one object.  */
>> +  if (base1_obj_p == base2_obj_p)
>> +    return false;
>> +  tree obj = base1_obj_p ? base1 : base2;
>> +
>> +  /* And we need one MEM_REF.  */
>> +  bool base1_memref_p = TREE_CODE (base1) == MEM_REF;
>> +  bool base2_memref_p = TREE_CODE (base2) == MEM_REF;
>> +  if (base1_memref_p == base2_memref_p)
>> +    return false;
>> +  tree memref = base1_memref_p ? base1 : base2;
>> +
>> +  /* Sizes need to be valid.  */
>> +  if (max_size1 == -1 || max_size2 == -1
>> +      || size1 == -1 || size2 == -1)
>> +    return false;
>> +
>> +  /* Max_size needs to match size.  */
>> +  if (max_size1 != size1
>> +      || max_size2 != size2)
>> +    return false;
>> +
>> +  /* Sizes need to match.  */
>> +  if (size1 != size2)
>> +    return false;
>> +
>> +  /* Offsets need to be 0.  */
>> +  if (offset1 != 0
>> +      || offset2 != 0)
>> +    return false;
>
> These two checks should be done first IMHO.
Sure.  Changed.
>
>> +  /* Check that memref is a store to pointer with singleton points-to info.
>> */
>> +  if (!tree_int_cst_equal (TREE_OPERAND (memref, 1), integer_zero_node))
>
> integer_zerop
Agreed & fixed.


>
>> +    return false;
>> +  tree ptr = TREE_OPERAND (memref, 0);
>> +  if (TREE_CODE (ptr) != SSA_NAME)
>> +    return false;
>> +  struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
>> +  unsigned int pt_uid;
>> +  if (pi == NULL
>> +      || !pt_solution_singleton_or_null_p (&pi->pt, &pt_uid))
>> +    return false;
>> +
>> +  /* Check that ptr points relative to obj.  */
>> +  unsigned int obj_uid = (DECL_PT_UID_SET_P (obj)
>> +                         ? DECL_PT_UID (obj)
>> +                         : DECL_UID (obj));
>
> Just use DECL_PT_UID.
OK.  I wasn't as sure about this one.  AFAICT this is meant to deal with 
canonicalization of the PD uid of aliases to their final target. 
Presumably when we have a singleton set, we don't have aliases and this 
doesn't apply.  So fixed.

jeff