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

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

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.  */
>