This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PR tree-optimization/67955] Exploit PTA in DSE
- From: Richard Biener <richard dot guenther at gmail dot com>
- To: Jeff Law <law at redhat dot com>
- Cc: gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Fri, 9 Dec 2016 09:28:14 +0100
- Subject: Re: [PR tree-optimization/67955] Exploit PTA in DSE
- Authentication-results: sourceware.org; auth=none
- References: <19387340-c3cf-118a-2041-2f466d96a91d@redhat.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. */
>