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

Jeff Law law@redhat.com
Wed Jan 4 18:55:00 GMT 2017


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



More information about the Gcc-patches mailing list