Handle structural equality of pointers in same_type_for_tbaa_p

Message ID 20190610122911.rf55ug3l466bcynh@kam.mff.cuni.cz
State New
Headers show
Series
  • Handle structural equality of pointers in same_type_for_tbaa_p
Related show

Commit Message

Jan Hubicka June 10, 2019, 12:29 p.m.
Hi,
this is kind of minimal patch to handle pointers in access paths.
I do not include logic for arrays nor attempt to deal better with incomparable
pointers (such as pointers to two different incomplete record types).

A lazy way would be to simply compare alias sets, but I want to handle more
because our rules for globbing pointers are not transitive. For example void *
is equivalent to pointer to any incomplete type.  But we can still say that
pointer to record is different from pointer to function which helps in practice 
since propagating pointers to functions is rather important.

Alias sets of pointer to record and pointer to function are both same as void *
because we have no way to distinguish multiple pointers of same kind and we
special case only void * alias set.  Here we can work bit better without much
of extra hassle and we also catch most of cases (since most accesses are to
types w/o pointers which we disambiguate this way).

Number of disambiguations on tramp3d via access path grows from 1000 to 

Alias oracle query stats:
  refs_may_alias_p: 3025065 disambiguations, 3321073 queries
  ref_maybe_used_by_call_p: 7118 disambiguations, 3050683 queries
  call_may_clobber_ref_p: 817 disambiguations, 817 queries
  aliasing_component_ref_p: 8703 disambiguations, 24495 queries
  TBAA oracle: 1429175 disambiguations 2934191 queries
               552425 are in alias set 0
               573848 queries asked about the same object
               0 queries asked about the same alias set
               0 access volatile
               257310 are dependent in the DAG
               121433 are aritificially in conflict with void *

So about 8x more.

lto-bootstrapped/regtested x86_64 with all languages, OK?

	* gcc.dg/lto/alias-access-path-3_0.c: New testcase.
	* tree-ssa-alias.c (same_type_for_tbaa): Look into pointed-to types
	to test structural equivalence of pointer types.

Comments

Richard Biener June 11, 2019, 12:07 p.m. | #1
On Mon, 10 Jun 2019, Jan Hubicka wrote:

> Hi,

> this is kind of minimal patch to handle pointers in access paths.

> I do not include logic for arrays nor attempt to deal better with incomparable

> pointers (such as pointers to two different incomplete record types).

> 

> A lazy way would be to simply compare alias sets, but I want to handle more

> because our rules for globbing pointers are not transitive. For example void *

> is equivalent to pointer to any incomplete type.  But we can still say that

> pointer to record is different from pointer to function which helps in practice 

> since propagating pointers to functions is rather important.

> 

> Alias sets of pointer to record and pointer to function are both same as void *

> because we have no way to distinguish multiple pointers of same kind and we

> special case only void * alias set.  Here we can work bit better without much

> of extra hassle and we also catch most of cases (since most accesses are to

> types w/o pointers which we disambiguate this way).

> 

> Number of disambiguations on tramp3d via access path grows from 1000 to 

> 

> Alias oracle query stats:

>   refs_may_alias_p: 3025065 disambiguations, 3321073 queries

>   ref_maybe_used_by_call_p: 7118 disambiguations, 3050683 queries

>   call_may_clobber_ref_p: 817 disambiguations, 817 queries

>   aliasing_component_ref_p: 8703 disambiguations, 24495 queries

>   TBAA oracle: 1429175 disambiguations 2934191 queries

>                552425 are in alias set 0

>                573848 queries asked about the same object

>                0 queries asked about the same alias set

>                0 access volatile

>                257310 are dependent in the DAG

>                121433 are aritificially in conflict with void *

> 

> So about 8x more.

> 

> lto-bootstrapped/regtested x86_64 with all languages, OK?


So the important thing is that during matching the paths
aptr->a and *bptr we return false for
same_type_for_tbaa (int *, struct a *), correct?  But if
we can do that then the alias sets should not conflict in
the first place and we shouldn't need any path-based disambiguation
here.

So to me this is the wrong place to fix.

Richard.

> 	* gcc.dg/lto/alias-access-path-3_0.c: New testcase.

> 	* tree-ssa-alias.c (same_type_for_tbaa): Look into pointed-to types

> 	to test structural equivalence of pointer types.

> 

> Index: testsuite/gcc.dg/lto/alias-access-path-3_0.c

> ===================================================================

> --- testsuite/gcc.dg/lto/alias-access-path-3_0.c	(nonexistent)

> +++ testsuite/gcc.dg/lto/alias-access-path-3_0.c	(working copy)

> @@ -0,0 +1,37 @@

> +/* { dg-lto-do run } */

> +/* { dg-lto-options { { -O3 -flto -fno-early-inlining } } } */

> +#include <stdlib.h>

> +

> +/* We should disambiguate

> +     int *

> +   and

> +     struct a *

> +   despite the fact they get same alias set because struct a is incomplete.  */

> +

> +typedef int (*fnptr) ();

> +

> +__attribute__ ((used))

> +struct

> +{

> +  int *a;

> +} a, *aptr = &a;

> +

> +struct a **bptr;

> +

> +static void

> +inline_me_late (int argc)

> +{

> +  if (argc == -1)

> +    *bptr = (void *)(size_t)1;

> +}

> +

> +int

> +main (int argc)

> +{

> +  typeof (aptr) aptr2 = aptr;

> +  aptr2->a = 0;

> +  inline_me_late (argc);

> +  if (!__builtin_constant_p (aptr2->a == 0))

> +    __builtin_abort ();

> +  return 0;

> +}

> Index: tree-ssa-alias.c

> ===================================================================

> --- tree-ssa-alias.c	(revision 272037)

> +++ tree-ssa-alias.c	(working copy)

> @@ -791,10 +791,39 @@ same_type_for_tbaa (tree type1, tree typ

>    if (type1 == type2)

>      return 1;

>  

> +  /* For LTO we do not define canonical types of pointers.  Look into

> +     corresponding pointed-to-types.  To speed non-LTO checks,

> +     do not bother to do that if canonical types are defined though.  */

> +  while (POINTER_TYPE_P (type1) && POINTER_TYPE_P (type2)

> +	  && (TYPE_STRUCTURAL_EQUALITY_P (type1)

> +	      || TYPE_STRUCTURAL_EQUALITY_P (type2)))

> +    {

> +      type1 = TREE_TYPE (type1);

> +      type2 = TREE_TYPE (type2);

> +      /* As an extension, we consider void pointer TBAA compatible with all

> +	 other pointer types.  This is especially importnat in LTO where

> +	 non-C languages may want to bind to C pointers via void *.  */

> +      if (VOID_TYPE_P (type1) || VOID_TYPE_P (type2))

> +	return 1;

> +    }

> +

>    /* If we would have to do structural comparison bail out.  */

>    if (TYPE_STRUCTURAL_EQUALITY_P (type1)

>        || TYPE_STRUCTURAL_EQUALITY_P (type2))

> -    return -1;

> +    {

> +      /* If type1 and type2 are diferent kinds, return 0.

> +	 This is important espcially when we hit incomplete types or

> +	 function/method types after walking pointed-to types above.

> +

> +	 ??? As a special case we want to consider ARRAY_TYPE possibly

> +	 same as its base type to solve some issues with Fortran frontend.  */

> +      if (TREE_CODE (type1) != ARRAY_TYPE

> +	  && TREE_CODE (type2) != ARRAY_TYPE

> +	  && tree_code_for_canonical_type_merging (TREE_CODE (type1))

> +	     != tree_code_for_canonical_type_merging (TREE_CODE (type2)))

> +	return 0;

> +      return -1;

> +    }

>  

>    /* Compare the canonical types.  */

>    if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))

> 


-- 
Richard Biener <rguenther@suse.de>
SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany;
GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg)
Jan Hubicka June 11, 2019, 12:10 p.m. | #2
> So the important thing is that during matching the paths

> aptr->a and *bptr we return false for

> same_type_for_tbaa (int *, struct a *), correct?  But if

> we can do that then the alias sets should not conflict in

> the first place and we shouldn't need any path-based disambiguation

> here.

> 

> So to me this is the wrong place to fix.


The alias sets of int * conflict with alias set of struct a *
since that one is same as void * and we make void * to conflict
with all pointers.

However we also do not want to return -1 for things like
same_type_for_tbaa (int *, struct a)
which we do currently, since int * is TYPE_STRUCTURAL_EQUALITY 
and struct a is not.

Here you may declare struct a as
struct a {int *a;};
and alias sets will be in conflict even w/o void * globing.

Honza
Jan Hubicka June 11, 2019, 12:20 p.m. | #3
Hi,
here is testcase for that.

I think we need to get rid of most -1 return values to make access path
matching work.  Here we work out that stroing to *bptr
is not going to affect a since *bptr is a struct, but alias set
conflicts does not help.

This fails w/o patch sine struct b and int * compares as -1.

/* { dg-lto-do run } */
/* { dg-lto-options { { -O3 -flto -fno-early-inlining } } } */
#include <stdlib.h>

/* We should disambiguate
     int *
   and
     struct a *
   despite the fact they get same alias set because struct a is incomplete.  */

typedef int (*fnptr) ();

__attribute__ ((used))
int *a,**aptr=&a;

__attribute__ ((used))
struct b {int *a;} *bptr,b;

static void
inline_me_late (int argc)
{
  if (argc == -1)
    *bptr = b;
}

int
main (int argc)
{
  a = 0;
  inline_me_late (argc);
  if (!__builtin_constant_p (a == 0))
    __builtin_abort ();
  return 0;
}
Richard Biener June 11, 2019, 1:06 p.m. | #4
On Tue, 11 Jun 2019, Jan Hubicka wrote:

> > So the important thing is that during matching the paths

> > aptr->a and *bptr we return false for

> > same_type_for_tbaa (int *, struct a *), correct?  But if

> > we can do that then the alias sets should not conflict in

> > the first place and we shouldn't need any path-based disambiguation

> > here.

> > 

> > So to me this is the wrong place to fix.

> 

> The alias sets of int * conflict with alias set of struct a *

> since that one is same as void * and we make void * to conflict

> with all pointers.

> 

> However we also do not want to return -1 for things like

> same_type_for_tbaa (int *, struct a)

> which we do currently, since int * is TYPE_STRUCTURAL_EQUALITY 

> and struct a is not.


Yes, but that basically boils down to handling !AGGREGATE_TYPE_P
vs AGGREGATE_TYPE_P in a better way, not looking into pointed-to
types.

> Here you may declare struct a as

> struct a {int *a;};

> and alias sets will be in conflict even w/o void * globing.

> 

> Honza

> 


-- 
Richard Biener <rguenther@suse.de>
SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany;
GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg)
Jan Hubicka June 11, 2019, 1:56 p.m. | #5
> On Tue, 11 Jun 2019, Jan Hubicka wrote:

> 

> > > So the important thing is that during matching the paths

> > > aptr->a and *bptr we return false for

> > > same_type_for_tbaa (int *, struct a *), correct?  But if

> > > we can do that then the alias sets should not conflict in

> > > the first place and we shouldn't need any path-based disambiguation

> > > here.

> > > 

> > > So to me this is the wrong place to fix.

> > 

> > The alias sets of int * conflict with alias set of struct a *

> > since that one is same as void * and we make void * to conflict

> > with all pointers.

> > 

> > However we also do not want to return -1 for things like

> > same_type_for_tbaa (int *, struct a)

> > which we do currently, since int * is TYPE_STRUCTURAL_EQUALITY 

> > and struct a is not.

> 

> Yes, but that basically boils down to handling !AGGREGATE_TYPE_P

> vs AGGREGATE_TYPE_P in a better way, not looking into pointed-to

> types.


OK, so your preferred vairant would be to make same_type_for_tbaa
to return 0 instead of -1 if one type is AGGREGATE_TYPE_P and other
!AGGREGATE_TYPE_P and extend alias set calculation to somewhat account
for the non-transitive rules for pointers TBAA?

What about arrays?

Honza
> 

> > Here you may declare struct a as

> > struct a {int *a;};

> > and alias sets will be in conflict even w/o void * globing.

> > 

> > Honza

> > 

> 

> -- 

> Richard Biener <rguenther@suse.de>

> SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany;

> GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg)

Patch

Index: testsuite/gcc.dg/lto/alias-access-path-3_0.c
===================================================================
--- testsuite/gcc.dg/lto/alias-access-path-3_0.c	(nonexistent)
+++ testsuite/gcc.dg/lto/alias-access-path-3_0.c	(working copy)
@@ -0,0 +1,37 @@ 
+/* { dg-lto-do run } */
+/* { dg-lto-options { { -O3 -flto -fno-early-inlining } } } */
+#include <stdlib.h>
+
+/* We should disambiguate
+     int *
+   and
+     struct a *
+   despite the fact they get same alias set because struct a is incomplete.  */
+
+typedef int (*fnptr) ();
+
+__attribute__ ((used))
+struct
+{
+  int *a;
+} a, *aptr = &a;
+
+struct a **bptr;
+
+static void
+inline_me_late (int argc)
+{
+  if (argc == -1)
+    *bptr = (void *)(size_t)1;
+}
+
+int
+main (int argc)
+{
+  typeof (aptr) aptr2 = aptr;
+  aptr2->a = 0;
+  inline_me_late (argc);
+  if (!__builtin_constant_p (aptr2->a == 0))
+    __builtin_abort ();
+  return 0;
+}
Index: tree-ssa-alias.c
===================================================================
--- tree-ssa-alias.c	(revision 272037)
+++ tree-ssa-alias.c	(working copy)
@@ -791,10 +791,39 @@  same_type_for_tbaa (tree type1, tree typ
   if (type1 == type2)
     return 1;
 
+  /* For LTO we do not define canonical types of pointers.  Look into
+     corresponding pointed-to-types.  To speed non-LTO checks,
+     do not bother to do that if canonical types are defined though.  */
+  while (POINTER_TYPE_P (type1) && POINTER_TYPE_P (type2)
+	  && (TYPE_STRUCTURAL_EQUALITY_P (type1)
+	      || TYPE_STRUCTURAL_EQUALITY_P (type2)))
+    {
+      type1 = TREE_TYPE (type1);
+      type2 = TREE_TYPE (type2);
+      /* As an extension, we consider void pointer TBAA compatible with all
+	 other pointer types.  This is especially importnat in LTO where
+	 non-C languages may want to bind to C pointers via void *.  */
+      if (VOID_TYPE_P (type1) || VOID_TYPE_P (type2))
+	return 1;
+    }
+
   /* If we would have to do structural comparison bail out.  */
   if (TYPE_STRUCTURAL_EQUALITY_P (type1)
       || TYPE_STRUCTURAL_EQUALITY_P (type2))
-    return -1;
+    {
+      /* If type1 and type2 are diferent kinds, return 0.
+	 This is important espcially when we hit incomplete types or
+	 function/method types after walking pointed-to types above.
+
+	 ??? As a special case we want to consider ARRAY_TYPE possibly
+	 same as its base type to solve some issues with Fortran frontend.  */
+      if (TREE_CODE (type1) != ARRAY_TYPE
+	  && TREE_CODE (type2) != ARRAY_TYPE
+	  && tree_code_for_canonical_type_merging (TREE_CODE (type1))
+	     != tree_code_for_canonical_type_merging (TREE_CODE (type2)))
+	return 0;
+      return -1;
+    }
 
   /* Compare the canonical types.  */
   if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))