Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Jan Hubicka]

Hi,
this patch implements basic structura compare so same_type_for_tbaa does
not return -1 for all arrays, vectors and pointers with LTO.
The current TBAA stats for tramp3d are:

Alias oracle query stats:
  refs_may_alias_p: 3016393 disambiguations, 3316783 queries
  ref_maybe_used_by_call_p: 7112 disambiguations, 3041993 queries
  call_may_clobber_ref_p: 817 disambiguations, 817 queries
  aliasing_component_ref_p: 652 disambiguations, 19720 queries
  TBAA oracle: 1420658 disambiguations 2918622 queries
               552186 are in alias set 0
               569271 queries asked about the same object
               0 queries asked about the same alias set
               0 access volatile
               260166 are dependent in the DAG
               116341 are aritificially in conflict with void *

compared to:
Alias oracle query stats:
  refs_may_alias_p: 3013166 disambiguations, 3313523 queries
  ref_maybe_used_by_call_p: 7112 disambiguations, 3038766 queries
  call_may_clobber_ref_p: 817 disambiguations, 817 queries
  aliasing_component_ref_p: 124 disambiguations, 12414 queries
  TBAA oracle: 1417999 disambiguations 2914624 queries
               552182 are in alias set 0
               569275 queries asked about the same object
               0 queries asked about the same alias set
               0 access volatile
               258909 are dependent in the DAG
               116259 are aritificially in conflict with void *

so about 5 times increase of alias_components_refs_p disambiguations.


The basic idea is simple - pointers are same if points-to types are same
and similarly for arrays/vector.

I have noticed that a lot of -1s come from comparing void pointers to non-void
because void is structural type we consider incomparable with everyting.
I think for pointers it is OK to return either 0 or 1 and never care about
undecided cases that matters only in the middle of paths.
For this I track if we compare pointers and return this.

For arrays situation is slightly different - we can only disprove array
equivalence but we do not want to return 1 because we support partial overlaps
on them. The logic about arrays is bit sloppy: some users of
types_same_for_tbaa_p explicitly disallow them while others doesn't and there
are cases where the function returns 1 w/o LTO. We can also handle matches when
array is not the outer type of whole reference which is a common case.
I plan to clean it up incrementally.

lto-bootstrapped/regtested x86_64-linux, OK?

Honza

	* tree-ssa-alias.c (same_type_for_tbaa): Handle structural comparison
	of pointers, arrays and vectors.
Index: tree-ssa-alias.c
===================================================================
--- tree-ssa-alias.c	(revision 271292)
+++ tree-ssa-alias.c	(working copy)
@@ -745,21 +767,87 @@ same_type_for_tbaa (tree type1, tree typ
   type1 = TYPE_MAIN_VARIANT (type1);
   type2 = TYPE_MAIN_VARIANT (type2);
 
-  /* If we would have to do structural comparison bail out.  */
-  if (TYPE_STRUCTURAL_EQUALITY_P (type1)
-      || TYPE_STRUCTURAL_EQUALITY_P (type2))
-    return -1;
+  /* If same_type_for_tbaa returns true we make an assumption that pointers to
+     TYPE1 and TYPE2 can either point to same copy of the type or completely
+     different.
+
+     This is not necessarily true for arrays where overlap can be partial
+     as in gcc.dg/torture/alias-2.c.  So we can only prove that arrays are
+     disjoint becuase they are derived from different types but we can not
+     prove they are same.
+
+     On the other hand for pointers we can always consider them to be same
+     unless we can prove that pointed-to types are different.
+
+     So normally return values are
+       0  if types are known to be different
+       1  if types are same and there is no partial overlap
+       -1 otherwise.
+
+     However if comparing two pointers return values are
+       0  if pointed to types are known to be different
+       1  otherwise (because partial overlaps do not happen).
+
+     If comparing array or vector to other type return values are
+       0  if types array/vector are derived from are known to be different
+       -1 otherwise (to watch for partial overlaps).  */
+
+  bool in_ptr = false;
+  bool in_array = false;
+
+  if (type1 == type2)
+    return 1;
+
+  /* Do structural comparsion for types that have no canonical types in LTO.  */
+  while (TYPE_STRUCTURAL_EQUALITY_P (type1)
+	 || TYPE_STRUCTURAL_EQUALITY_P (type2))
+    {
+      /* Pointer types are same if they point to same types.  */
+      if (POINTER_TYPE_P (type1) && POINTER_TYPE_P (type2))
+	{
+	  type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
+	  type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
+	  if (!in_array)
+	    in_ptr = true;
+	}
+      /* Peel out arrays and vector to compare inner types.  */
+      else if ((TREE_CODE (type1) == ARRAY_TYPE
+	        || TREE_CODE (type1) == VECTOR_TYPE)
+	       && TYPE_STRUCTURAL_EQUALITY_P (type1))
+	{
+	  type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
+	  if (!in_ptr)
+	    in_array = true;
+	}
+      else if ((TREE_CODE (type2) == ARRAY_TYPE
+	        || TREE_CODE (type2) == VECTOR_TYPE)
+	       && TYPE_STRUCTURAL_EQUALITY_P (type2))
+	{
+	  type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
+	  if (!in_ptr)
+	    in_array = true;
+	}
+      else
+	{
+	  if (POINTER_TYPE_P (type1) != POINTER_TYPE_P (type2))
+	    return 0;
+	  return in_ptr ? 1 : -1;
+	}
+
+      if (type1 == type2)
+        return in_array ? -1 : 1;
+    }
 
   /* Compare the canonical types.  */
   if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
-    return 1;
+    return in_array ? -1 : 1;
 
   /* ??? Array types are not properly unified in all cases as we have
      spurious changes in the index types for example.  Removing this
      causes all sorts of problems with the Fortran frontend.  */
   if (TREE_CODE (type1) == ARRAY_TYPE
       && TREE_CODE (type2) == ARRAY_TYPE)
-    return -1;
+    return in_ptr ? 1 : -1;
 
   /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
      object of one of its constrained subtypes, e.g. when a function with an
@@ -770,7 +858,7 @@ same_type_for_tbaa (tree type1, tree typ
      not (e.g. type and subtypes can have different modes).  So, in the end,
      they are only guaranteed to have the same alias set.  */
   if (get_alias_set (type1) == get_alias_set (type2))
-    return -1;
+    return in_ptr ? 1 : -1;
 
   /* The types are known to be not equal.  */
   return 0;

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Richard Biener]

[-- Attachment #1: Type: text/plain, Size: 7975 bytes --]

On Fri, 24 May 2019, Jan Hubicka wrote:

> Hi,
> this patch implements basic structura compare so same_type_for_tbaa does
> not return -1 for all arrays, vectors and pointers with LTO.
> The current TBAA stats for tramp3d are:
> 
> Alias oracle query stats:
>   refs_may_alias_p: 3016393 disambiguations, 3316783 queries
>   ref_maybe_used_by_call_p: 7112 disambiguations, 3041993 queries
>   call_may_clobber_ref_p: 817 disambiguations, 817 queries
>   aliasing_component_ref_p: 652 disambiguations, 19720 queries
>   TBAA oracle: 1420658 disambiguations 2918622 queries
>                552186 are in alias set 0
>                569271 queries asked about the same object
>                0 queries asked about the same alias set
>                0 access volatile
>                260166 are dependent in the DAG
>                116341 are aritificially in conflict with void *
> 
> compared to:
> Alias oracle query stats:
>   refs_may_alias_p: 3013166 disambiguations, 3313523 queries
>   ref_maybe_used_by_call_p: 7112 disambiguations, 3038766 queries
>   call_may_clobber_ref_p: 817 disambiguations, 817 queries
>   aliasing_component_ref_p: 124 disambiguations, 12414 queries
>   TBAA oracle: 1417999 disambiguations 2914624 queries
>                552182 are in alias set 0
>                569275 queries asked about the same object
>                0 queries asked about the same alias set
>                0 access volatile
>                258909 are dependent in the DAG
>                116259 are aritificially in conflict with void *
> 
> so about 5 times increase of alias_components_refs_p disambiguations.

Note the number of queries also changes so it's "somewhat" comparing
apples and oranges (possibly the alias walk doesn't have to give up
and thus we walk more and do more queries).

> 
> The basic idea is simple - pointers are same if points-to types are same
> and similarly for arrays/vector.
> 
> I have noticed that a lot of -1s come from comparing void pointers to non-void
> because void is structural type we consider incomparable with everyting.
> I think for pointers it is OK to return either 0 or 1 and never care about
> undecided cases that matters only in the middle of paths.
> For this I track if we compare pointers and return this.
> 
> For arrays situation is slightly different - we can only disprove array
> equivalence but we do not want to return 1 because we support partial overlaps
> on them. The logic about arrays is bit sloppy: some users of
> types_same_for_tbaa_p explicitly disallow them while others doesn't and there
> are cases where the function returns 1 w/o LTO. We can also handle matches when
> array is not the outer type of whole reference which is a common case.
> I plan to clean it up incrementally.
> 
> lto-bootstrapped/regtested x86_64-linux, OK?
> 
> Honza
> 
> 	* tree-ssa-alias.c (same_type_for_tbaa): Handle structural comparison
> 	of pointers, arrays and vectors.
> Index: tree-ssa-alias.c
> ===================================================================
> --- tree-ssa-alias.c	(revision 271292)
> +++ tree-ssa-alias.c	(working copy)
> @@ -745,21 +767,87 @@ same_type_for_tbaa (tree type1, tree typ
>    type1 = TYPE_MAIN_VARIANT (type1);
>    type2 = TYPE_MAIN_VARIANT (type2);
>  
> -  /* If we would have to do structural comparison bail out.  */
> -  if (TYPE_STRUCTURAL_EQUALITY_P (type1)
> -      || TYPE_STRUCTURAL_EQUALITY_P (type2))
> -    return -1;
> +  /* If same_type_for_tbaa returns true we make an assumption that pointers to
> +     TYPE1 and TYPE2 can either point to same copy of the type or completely
> +     different.
> +
> +     This is not necessarily true for arrays where overlap can be partial
> +     as in gcc.dg/torture/alias-2.c.  So we can only prove that arrays are
> +     disjoint becuase they are derived from different types but we can not
> +     prove they are same.
> +
> +     On the other hand for pointers we can always consider them to be same
> +     unless we can prove that pointed-to types are different.

What about different address-spaces and/or pointer sizes?

> +     So normally return values are
> +       0  if types are known to be different
> +       1  if types are same and there is no partial overlap
> +       -1 otherwise.
> +
> +     However if comparing two pointers return values are
> +       0  if pointed to types are known to be different
> +       1  otherwise (because partial overlaps do not happen).

Doesn't this apply to all non-composite types?  (the "partial overlaps
do not happen"?)

> +     If comparing array or vector to other type return values are
> +       0  if types array/vector are derived from are known to be different
> +       -1 otherwise (to watch for partial overlaps).  */
> +
> +  bool in_ptr = false;
> +  bool in_array = false;
> +
> +  if (type1 == type2)
> +    return 1;
> +
> +  /* Do structural comparsion for types that have no canonical types in LTO.  */
> +  while (TYPE_STRUCTURAL_EQUALITY_P (type1)
> +	 || TYPE_STRUCTURAL_EQUALITY_P (type2))
> +    {
> +      /* Pointer types are same if they point to same types.  */
> +      if (POINTER_TYPE_P (type1) && POINTER_TYPE_P (type2))
> +	{
> +	  type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
> +	  type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
> +	  if (!in_array)
> +	    in_ptr = true;

Don't you run into unrelated types when visiting pointed-to types
here?  Why would we care for the pointed-to type anwyways?

That is, the loop should just handle composite types
and after it compare non-composite types with
types_compatible_p for example?  Maybe even do that change
independently.

> +	}
> +      /* Peel out arrays and vector to compare inner types.  */
> +      else if ((TREE_CODE (type1) == ARRAY_TYPE
> +	        || TREE_CODE (type1) == VECTOR_TYPE)
> +	       && TYPE_STRUCTURAL_EQUALITY_P (type1))
> +	{
> +	  type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
> +	  if (!in_ptr)
> +	    in_array = true;
> +	}
> +      else if ((TREE_CODE (type2) == ARRAY_TYPE
> +	        || TREE_CODE (type2) == VECTOR_TYPE)
> +	       && TYPE_STRUCTURAL_EQUALITY_P (type2))
> +	{
> +	  type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
> +	  if (!in_ptr)
> +	    in_array = true;
> +	}

I don't think it works like this, peeling arrays/vectors from
types individually instead of in lock-step?

I think for better testing coverage you want to force
TYPE_STRUCTURAL_EQUALITY on all types here - this shouldn't
make things invalid but otherwise these code-paths are not
tested very well.

> +      else
> +	{
> +	  if (POINTER_TYPE_P (type1) != POINTER_TYPE_P (type2))
> +	    return 0;
> +	  return in_ptr ? 1 : -1;
> +	}
> +
> +      if (type1 == type2)
> +        return in_array ? -1 : 1;
> +    }
>  
>    /* Compare the canonical types.  */
>    if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
> -    return 1;
> +    return in_array ? -1 : 1;
>  
>    /* ??? Array types are not properly unified in all cases as we have
>       spurious changes in the index types for example.  Removing this
>       causes all sorts of problems with the Fortran frontend.  */
>    if (TREE_CODE (type1) == ARRAY_TYPE
>        && TREE_CODE (type2) == ARRAY_TYPE)
> -    return -1;
> +    return in_ptr ? 1 : -1;
>  
>    /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
>       object of one of its constrained subtypes, e.g. when a function with an
> @@ -770,7 +858,7 @@ same_type_for_tbaa (tree type1, tree typ
>       not (e.g. type and subtypes can have different modes).  So, in the end,
>       they are only guaranteed to have the same alias set.  */
>    if (get_alias_set (type1) == get_alias_set (type2))
> -    return -1;
> +    return in_ptr ? 1 : -1;
>  
>    /* The types are known to be not equal.  */
>    return 0;
> 

-- 
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)

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Jan Hubicka]

> > so about 5 times increase of alias_components_refs_p disambiguations.
> 
> Note the number of queries also changes so it's "somewhat" comparing
> apples and oranges (possibly the alias walk doesn't have to give up
> and thus we walk more and do more queries).

Yep, I know. If you disambiguate you may increase number of queries
overall because oracles walks further or decrease because tings get
optimized out.

It is however relatively useful to check if patch is doing something :)

> > +  /* If same_type_for_tbaa returns true we make an assumption that pointers to
> > +     TYPE1 and TYPE2 can either point to same copy of the type or completely
> > +     different.
> > +
> > +     This is not necessarily true for arrays where overlap can be partial
> > +     as in gcc.dg/torture/alias-2.c.  So we can only prove that arrays are
> > +     disjoint becuase they are derived from different types but we can not
> > +     prove they are same.
> > +
> > +     On the other hand for pointers we can always consider them to be same
> > +     unless we can prove that pointed-to types are different.
> 
> What about different address-spaces and/or pointer sizes?
> 
> > +     So normally return values are
> > +       0  if types are known to be different
> > +       1  if types are same and there is no partial overlap
> > +       -1 otherwise.
> > +
> > +     However if comparing two pointers return values are
> > +       0  if pointed to types are known to be different
> > +       1  otherwise (because partial overlaps do not happen).
> 
> Doesn't this apply to all non-composite types?  (the "partial overlaps
> do not happen"?)

I think we should have TYPE_CANONICAL defined on those so the comparsion
should follow the usual way.
> 
> > +     If comparing array or vector to other type return values are
> > +       0  if types array/vector are derived from are known to be different
> > +       -1 otherwise (to watch for partial overlaps).  */
> > +
> > +  bool in_ptr = false;
> > +  bool in_array = false;
> > +
> > +  if (type1 == type2)
> > +    return 1;
> > +
> > +  /* Do structural comparsion for types that have no canonical types in LTO.  */
> > +  while (TYPE_STRUCTURAL_EQUALITY_P (type1)
> > +	 || TYPE_STRUCTURAL_EQUALITY_P (type2))
> > +    {
> > +      /* Pointer types are same if they point to same types.  */
> > +      if (POINTER_TYPE_P (type1) && POINTER_TYPE_P (type2))
> > +	{
> > +	  type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
> > +	  type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
> > +	  if (!in_array)
> > +	    in_ptr = true;
> 
> Don't you run into unrelated types when visiting pointed-to types
> here?  Why would we care for the pointed-to type anwyways?

What do you mean by unrelated type here?
> 
> That is, the loop should just handle composite types
> and after it compare non-composite types with
> types_compatible_p for example?  Maybe even do that change
> independently.

It would probably give more 1s and less 0s which would, in turn, make
aliasing_component_refs to apply range check (which will return 1)
instead of concluding that access paths are disjoint.

Why do you think this is better than looking up the pointed-to type
and comparing that one?
> 
> > +	}
> > +      /* Peel out arrays and vector to compare inner types.  */
> > +      else if ((TREE_CODE (type1) == ARRAY_TYPE
> > +	        || TREE_CODE (type1) == VECTOR_TYPE)
> > +	       && TYPE_STRUCTURAL_EQUALITY_P (type1))
> > +	{
> > +	  type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
> > +	  if (!in_ptr)
> > +	    in_array = true;
> > +	}
> > +      else if ((TREE_CODE (type2) == ARRAY_TYPE
> > +	        || TREE_CODE (type2) == VECTOR_TYPE)
> > +	       && TYPE_STRUCTURAL_EQUALITY_P (type2))
> > +	{
> > +	  type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
> > +	  if (!in_ptr)
> > +	    in_array = true;
> > +	}
> 
> I don't think it works like this, peeling arrays/vectors from
> types individually instead of in lock-step?

The intention here is behave similarly to get_alias_set and handle
declare arrays/vectors to be the same as the type they are derived from
+ dissabling the assumption about non-existence of partial overlaps.
> 
> I think for better testing coverage you want to force
> TYPE_STRUCTURAL_EQUALITY on all types here - this shouldn't
> make things invalid but otherwise these code-paths are not
> tested very well.

I played around with this on non-LTO builds bypasing the
TYPE_STRUCTURAL_EQUALITY check. For pointers it agreed with
the TYPE_CANONICAL check, for arrays I run into problems that
same_types_for_tbaa returns 1 because it first check TYPE_CANONICAL for
equality and ARRAY_TYPEs later. There is some code later to special case
this but not very systematic. Such as:

      /* But avoid treating arrays as "objects", instead assume they            
         can overlap by an exact multiple of their element size.  */            
     && TREE_CODE (TREE_TYPE (ptrtype1)) != ARRAY_TYPE)                        
  return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2);     

in indirect_refs_may_alias_p but similar logic is not in the access path
code nor in indirect_ref_may_alias_decl_p. I am 100% sure why - i can
see that in the middle of access path this can not happen, but I think
testcase can be constructed for arrays in decls.

This is why I decided to never consider arrays equivalent to each other
or to scalar and look into this later.

In non-LTO build we also have types with structural equality (such as
iostreams) and we now returns 1 when types_same_for_tbaa is called with
TYPE_MAIN_VARIANT (type1)==TYPE_MAIN_VARIANT (type2)

I will do some more testing.

Honza
> 
> > +      else
> > +	{
> > +	  if (POINTER_TYPE_P (type1) != POINTER_TYPE_P (type2))
> > +	    return 0;
> > +	  return in_ptr ? 1 : -1;
> > +	}
> > +
> > +      if (type1 == type2)
> > +        return in_array ? -1 : 1;
> > +    }
> >  
> >    /* Compare the canonical types.  */
> >    if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
> > -    return 1;
> > +    return in_array ? -1 : 1;
> >  
> >    /* ??? Array types are not properly unified in all cases as we have
> >       spurious changes in the index types for example.  Removing this
> >       causes all sorts of problems with the Fortran frontend.  */
> >    if (TREE_CODE (type1) == ARRAY_TYPE
> >        && TREE_CODE (type2) == ARRAY_TYPE)
> > -    return -1;
> > +    return in_ptr ? 1 : -1;
> >  
> >    /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
> >       object of one of its constrained subtypes, e.g. when a function with an
> > @@ -770,7 +858,7 @@ same_type_for_tbaa (tree type1, tree typ
> >       not (e.g. type and subtypes can have different modes).  So, in the end,
> >       they are only guaranteed to have the same alias set.  */
> >    if (get_alias_set (type1) == get_alias_set (type2))
> > -    return -1;
> > +    return in_ptr ? 1 : -1;
> >  
> >    /* The types are known to be not equal.  */
> >    return 0;
> > 
> 
> -- 
> 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)

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Richard Biener]

[-- Attachment #1: Type: text/plain, Size: 8702 bytes --]

On Fri, 24 May 2019, Jan Hubicka wrote:

> > > so about 5 times increase of alias_components_refs_p disambiguations.
> > 
> > Note the number of queries also changes so it's "somewhat" comparing
> > apples and oranges (possibly the alias walk doesn't have to give up
> > and thus we walk more and do more queries).
> 
> Yep, I know. If you disambiguate you may increase number of queries
> overall because oracles walks further or decrease because tings get
> optimized out.
> 
> It is however relatively useful to check if patch is doing something :)
> 
> > > +  /* If same_type_for_tbaa returns true we make an assumption that pointers to
> > > +     TYPE1 and TYPE2 can either point to same copy of the type or completely
> > > +     different.
> > > +
> > > +     This is not necessarily true for arrays where overlap can be partial
> > > +     as in gcc.dg/torture/alias-2.c.  So we can only prove that arrays are
> > > +     disjoint becuase they are derived from different types but we can not
> > > +     prove they are same.
> > > +
> > > +     On the other hand for pointers we can always consider them to be same
> > > +     unless we can prove that pointed-to types are different.
> > 
> > What about different address-spaces and/or pointer sizes?
> > 
> > > +     So normally return values are
> > > +       0  if types are known to be different
> > > +       1  if types are same and there is no partial overlap
> > > +       -1 otherwise.
> > > +
> > > +     However if comparing two pointers return values are
> > > +       0  if pointed to types are known to be different
> > > +       1  otherwise (because partial overlaps do not happen).
> > 
> > Doesn't this apply to all non-composite types?  (the "partial overlaps
> > do not happen"?)
> 
> I think we should have TYPE_CANONICAL defined on those so the comparsion
> should follow the usual way.
> > 
> > > +     If comparing array or vector to other type return values are
> > > +       0  if types array/vector are derived from are known to be different
> > > +       -1 otherwise (to watch for partial overlaps).  */
> > > +
> > > +  bool in_ptr = false;
> > > +  bool in_array = false;
> > > +
> > > +  if (type1 == type2)
> > > +    return 1;
> > > +
> > > +  /* Do structural comparsion for types that have no canonical types in LTO.  */
> > > +  while (TYPE_STRUCTURAL_EQUALITY_P (type1)
> > > +	 || TYPE_STRUCTURAL_EQUALITY_P (type2))
> > > +    {
> > > +      /* Pointer types are same if they point to same types.  */
> > > +      if (POINTER_TYPE_P (type1) && POINTER_TYPE_P (type2))
> > > +	{
> > > +	  type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
> > > +	  type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
> > > +	  if (!in_array)
> > > +	    in_ptr = true;
> > 
> > Don't you run into unrelated types when visiting pointed-to types
> > here?  Why would we care for the pointed-to type anwyways?
> 
> What do you mean by unrelated type here?
> > 
> > That is, the loop should just handle composite types
> > and after it compare non-composite types with
> > types_compatible_p for example?  Maybe even do that change
> > independently.
> 
> It would probably give more 1s and less 0s which would, in turn, make
> aliasing_component_refs to apply range check (which will return 1)
> instead of concluding that access paths are disjoint.
> 
> Why do you think this is better than looking up the pointed-to type
> and comparing that one?

The way you do it above seeing struct X ****p will end up comparing
'struct X' but that doesn't really have any say on whether we
can apply TBAA to the outermost pointer type which, if used as a base,
cannot be subsetted by components anyway.

So - why's anything besides treating all structurally equivalent
non-composite types as the same sensible here (and not waste of time)?

> > 
> > > +	}
> > > +      /* Peel out arrays and vector to compare inner types.  */
> > > +      else if ((TREE_CODE (type1) == ARRAY_TYPE
> > > +	        || TREE_CODE (type1) == VECTOR_TYPE)
> > > +	       && TYPE_STRUCTURAL_EQUALITY_P (type1))
> > > +	{
> > > +	  type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
> > > +	  if (!in_ptr)
> > > +	    in_array = true;
> > > +	}
> > > +      else if ((TREE_CODE (type2) == ARRAY_TYPE
> > > +	        || TREE_CODE (type2) == VECTOR_TYPE)
> > > +	       && TYPE_STRUCTURAL_EQUALITY_P (type2))
> > > +	{
> > > +	  type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
> > > +	  if (!in_ptr)
> > > +	    in_array = true;
> > > +	}
> > 
> > I don't think it works like this, peeling arrays/vectors from
> > types individually instead of in lock-step?
> 
> The intention here is behave similarly to get_alias_set and handle
> declare arrays/vectors to be the same as the type they are derived from
> + dissabling the assumption about non-existence of partial overlaps.

But this will cause us to use path based disambiguation for, say
a[i][j].b vs. (*p)[k].b, no?

I think we need to clarify what the comparison result of
same_type_for_tbaa means when it says "equivalent for the
purpose of TBAA".  I thought that for arrays, with the above
reasoning, we always have to say -1?

> > 
> > I think for better testing coverage you want to force
> > TYPE_STRUCTURAL_EQUALITY on all types here - this shouldn't
> > make things invalid but otherwise these code-paths are not
> > tested very well.
> 
> I played around with this on non-LTO builds bypasing the
> TYPE_STRUCTURAL_EQUALITY check. For pointers it agreed with
> the TYPE_CANONICAL check, for arrays I run into problems that
> same_types_for_tbaa returns 1 because it first check TYPE_CANONICAL for
> equality and ARRAY_TYPEs later. There is some code later to special case
> this but not very systematic. Such as:
> 
>       /* But avoid treating arrays as "objects", instead assume they            
>          can overlap by an exact multiple of their element size.  */            
>      && TREE_CODE (TREE_TYPE (ptrtype1)) != ARRAY_TYPE)                        
>   return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2);     
> 
> in indirect_refs_may_alias_p but similar logic is not in the access path
> code nor in indirect_ref_may_alias_decl_p. I am 100% sure why - i can
> see that in the middle of access path this can not happen, but I think
> testcase can be constructed for arrays in decls.
> 
> This is why I decided to never consider arrays equivalent to each other
> or to scalar and look into this later.
> 
> In non-LTO build we also have types with structural equality (such as
> iostreams) and we now returns 1 when types_same_for_tbaa is called with
> TYPE_MAIN_VARIANT (type1)==TYPE_MAIN_VARIANT (type2)
> 
> I will do some more testing.

I realize this is mostly my mess but if we try to "enhance" things
we need to make it clearer what we want...

Maybe even commonize more code paths (the path TBAA stuff is really
replicated in at least two places IIRC).

Richard.

> Honza
> > 
> > > +      else
> > > +	{
> > > +	  if (POINTER_TYPE_P (type1) != POINTER_TYPE_P (type2))
> > > +	    return 0;
> > > +	  return in_ptr ? 1 : -1;
> > > +	}
> > > +
> > > +      if (type1 == type2)
> > > +        return in_array ? -1 : 1;
> > > +    }
> > >  
> > >    /* Compare the canonical types.  */
> > >    if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
> > > -    return 1;
> > > +    return in_array ? -1 : 1;
> > >  
> > >    /* ??? Array types are not properly unified in all cases as we have
> > >       spurious changes in the index types for example.  Removing this
> > >       causes all sorts of problems with the Fortran frontend.  */
> > >    if (TREE_CODE (type1) == ARRAY_TYPE
> > >        && TREE_CODE (type2) == ARRAY_TYPE)
> > > -    return -1;
> > > +    return in_ptr ? 1 : -1;
> > >  
> > >    /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
> > >       object of one of its constrained subtypes, e.g. when a function with an
> > > @@ -770,7 +858,7 @@ same_type_for_tbaa (tree type1, tree typ
> > >       not (e.g. type and subtypes can have different modes).  So, in the end,
> > >       they are only guaranteed to have the same alias set.  */
> > >    if (get_alias_set (type1) == get_alias_set (type2))
> > > -    return -1;
> > > +    return in_ptr ? 1 : -1;
> > >  
> > >    /* The types are known to be not equal.  */
> > >    return 0;
> > > 
> > 
> > -- 
> > 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)
> 
> 

-- 
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)

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Jan Hubicka]

> The way you do it above seeing struct X ****p will end up comparing
> 'struct X' but that doesn't really have any say on whether we
> can apply TBAA to the outermost pointer type which, if used as a base,
> cannot be subsetted by components anyway.

We remove pointers in pairs so seeing
struct X ****p
struct Y ****q
we will end up saying that these pointers are same if struct X and Y are
same (which we will do by pointer type) or if we can not decide (one of
them is void).

Non-LTO code returns 0 in the second case, but I think that could be
considered unsafe when mixing K&R and ansi-C code.
> 
> So - why's anything besides treating all structurally equivalent
> non-composite types as the same sensible here (and not waste of time)?

I think you are right that with current implementation it should not
make difference.  I want eventually to disambiguate

struct foo {struct bar *a;} ptr1;
struct foobar **ptr2;

ptr1->a and *ptr2;

Here we will currently punt on comparing different pointer types.
With structural compare we will end up to base&offset because we would
consider struct foobar * and struct bar * as same types (they are both
incomplete in LTO now).

Same_types_for_tbaa does not need to form equivalences and if we unwind
pointers&arrays to types mathing odr_comparable_p (i.e. we have two
accesses originating from C++ code), we can disambiguate incompete
pointers based on mangled name of types they point to.  I have
incremental patch for that (which futher improves disambiguations to
about 8000).
> 
> I realize this is mostly my mess but if we try to "enhance" things
> we need to make it clearer what we want...
> 
> Maybe even commonize more code paths (the path TBAA stuff is really
> replicated in at least two places IIRC).

Yep, I am trying to understand what we need to do here and clean things
up.

I guess we could handle few independent issues
1) if it is safe to return 1 for types that compare as equivalent as
   pointers (currently we return -1 if canonical types are not defined).
   This seems to handle a most common case
2) decide what to do about pointers
3) decide what to do about arrays
4) decide what to do about ODR 
5) see how much we can merge with alias set & canonical type
computation.

I would propose first just add
 if (type1 == type2)
    reutrn 1;
and I will do bit deeper look at the pointers next and produce also some
testcases.

Honza
> 
> Richard.
> 
> > Honza
> > > 
> > > > +      else
> > > > +	{
> > > > +	  if (POINTER_TYPE_P (type1) != POINTER_TYPE_P (type2))
> > > > +	    return 0;
> > > > +	  return in_ptr ? 1 : -1;
> > > > +	}
> > > > +
> > > > +      if (type1 == type2)
> > > > +        return in_array ? -1 : 1;
> > > > +    }
> > > >  
> > > >    /* Compare the canonical types.  */
> > > >    if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
> > > > -    return 1;
> > > > +    return in_array ? -1 : 1;
> > > >  
> > > >    /* ??? Array types are not properly unified in all cases as we have
> > > >       spurious changes in the index types for example.  Removing this
> > > >       causes all sorts of problems with the Fortran frontend.  */
> > > >    if (TREE_CODE (type1) == ARRAY_TYPE
> > > >        && TREE_CODE (type2) == ARRAY_TYPE)
> > > > -    return -1;
> > > > +    return in_ptr ? 1 : -1;
> > > >  
> > > >    /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
> > > >       object of one of its constrained subtypes, e.g. when a function with an
> > > > @@ -770,7 +858,7 @@ same_type_for_tbaa (tree type1, tree typ
> > > >       not (e.g. type and subtypes can have different modes).  So, in the end,
> > > >       they are only guaranteed to have the same alias set.  */
> > > >    if (get_alias_set (type1) == get_alias_set (type2))
> > > > -    return -1;
> > > > +    return in_ptr ? 1 : -1;
> > > >  
> > > >    /* The types are known to be not equal.  */
> > > >    return 0;
> > > > 
> > > 
> > > -- 
> > > 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)
> > 
> > 
> 
> -- 
> 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)

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Richard Biener]

[-- Attachment #1: Type: text/plain, Size: 5489 bytes --]

On Mon, 27 May 2019, Jan Hubicka wrote:

> > The way you do it above seeing struct X ****p will end up comparing
> > 'struct X' but that doesn't really have any say on whether we
> > can apply TBAA to the outermost pointer type which, if used as a base,
> > cannot be subsetted by components anyway.
> 
> We remove pointers in pairs so seeing
> struct X ****p
> struct Y ****q
> we will end up saying that these pointers are same if struct X and Y are
> same (which we will do by pointer type) or if we can not decide (one of
> them is void).
> 
> Non-LTO code returns 0 in the second case, but I think that could be
> considered unsafe when mixing K&R and ansi-C code.
> > 
> > So - why's anything besides treating all structurally equivalent
> > non-composite types as the same sensible here (and not waste of time)?
> 
> I think you are right that with current implementation it should not
> make difference.  I want eventually to disambiguate
> 
> struct foo {struct bar *a;} ptr1;
> struct foobar **ptr2;
> 
> ptr1->a and *ptr2;
> 
> Here we will currently punt on comparing different pointer types.
> With structural compare we will end up to base&offset because we would
> consider struct foobar * and struct bar * as same types (they are both
> incomplete in LTO now).

But *ptr2 has no access 'path' so we shouldn't even consider it here.

That is, when the innermost reference (for *ptr2 that is a reference
to type foobar *) is of non-aggregate type there's no paths to
disambiguate.  That is same_types_for_tbaa shouldn't even be asked
for non-aggregate types...

> Same_types_for_tbaa does not need to form equivalences and if we unwind
> pointers&arrays to types mathing odr_comparable_p (i.e. we have two
> accesses originating from C++ code), we can disambiguate incompete
> pointers based on mangled name of types they point to.  I have
> incremental patch for that (which futher improves disambiguations to
> about 8000).
> > 
> > I realize this is mostly my mess but if we try to "enhance" things
> > we need to make it clearer what we want...
> > 
> > Maybe even commonize more code paths (the path TBAA stuff is really
> > replicated in at least two places IIRC).
> 
> Yep, I am trying to understand what we need to do here and clean things
> up.
> 
> I guess we could handle few independent issues
> 1) if it is safe to return 1 for types that compare as equivalent as
>    pointers (currently we return -1 if canonical types are not defined).
>    This seems to handle a most common case
> 2) decide what to do about pointers
> 3) decide what to do about arrays
> 4) decide what to do about ODR 
> 5) see how much we can merge with alias set & canonical type
> computation.
> 
> I would propose first just add
>  if (type1 == type2)
>     reutrn 1;

That works for me.

> and I will do bit deeper look at the pointers next and produce also some
> testcases.

Please also see if there are testcases that do anything meaningful
and FAIL after instead of

  /* Do access-path based disambiguation.  */
  if (ref1 && ref2
      && (handled_component_p (ref1) || handled_component_p (ref2)))

doing

  /* Do access-path based disambiguation.  */
  if (ref1 && ref2
      && (handled_component_p (ref1) && handled_component_p (ref2)))

Thanks.
Richard.

> 
> Honza
> > 
> > Richard.
> > 
> > > Honza
> > > > 
> > > > > +      else
> > > > > +	{
> > > > > +	  if (POINTER_TYPE_P (type1) != POINTER_TYPE_P (type2))
> > > > > +	    return 0;
> > > > > +	  return in_ptr ? 1 : -1;
> > > > > +	}
> > > > > +
> > > > > +      if (type1 == type2)
> > > > > +        return in_array ? -1 : 1;
> > > > > +    }
> > > > >  
> > > > >    /* Compare the canonical types.  */
> > > > >    if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
> > > > > -    return 1;
> > > > > +    return in_array ? -1 : 1;
> > > > >  
> > > > >    /* ??? Array types are not properly unified in all cases as we have
> > > > >       spurious changes in the index types for example.  Removing this
> > > > >       causes all sorts of problems with the Fortran frontend.  */
> > > > >    if (TREE_CODE (type1) == ARRAY_TYPE
> > > > >        && TREE_CODE (type2) == ARRAY_TYPE)
> > > > > -    return -1;
> > > > > +    return in_ptr ? 1 : -1;
> > > > >  
> > > > >    /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
> > > > >       object of one of its constrained subtypes, e.g. when a function with an
> > > > > @@ -770,7 +858,7 @@ same_type_for_tbaa (tree type1, tree typ
> > > > >       not (e.g. type and subtypes can have different modes).  So, in the end,
> > > > >       they are only guaranteed to have the same alias set.  */
> > > > >    if (get_alias_set (type1) == get_alias_set (type2))
> > > > > -    return -1;
> > > > > +    return in_ptr ? 1 : -1;
> > > > >  
> > > > >    /* The types are known to be not equal.  */
> > > > >    return 0;
> > > > > 
> > > > 
> > > > -- 
> > > > 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)
> > > 
> > > 
> > 
> > -- 
> > 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)
> 
> 

-- 
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)

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Jan Hubicka]

[-- Attachment #1: Type: text/plain, Size: 1385 bytes --]

> 
> Please also see if there are testcases that do anything meaningful
> and FAIL after instead of
> 
>   /* Do access-path based disambiguation.  */
>   if (ref1 && ref2
>       && (handled_component_p (ref1) || handled_component_p (ref2)))
> 
> doing
> 
>   /* Do access-path based disambiguation.  */
>   if (ref1 && ref2
>       && (handled_component_p (ref1) && handled_component_p (ref2)))
> 
On tramp3d we get quite few matches which are attached. If ref1 is
MEM_REF and ref2 has non-trivial access path then it seems we need:
 1) ref1 and ref2 to conflict (ref1 is a record or alias set 0)
 2) basetype2 to contain ref1 (so it conflicts too)
 3) if ref1 is a record than the access path may go into a type
    contained as field of ref1 but via path not containing ref1 itself.

I tried to construct testcase:

truct foo {int val;} *fooptr;
struct bar {struct foo foo; int val2;} *barptr;
int test()
{ 
  struct foo foo={0};
  barptr->val2 = 1;
  *fooptr=foo;
  return barptr->val2;
}

but we do not optimize it. I.e. optimized dump has:

test ()
{
  struct bar * barptr.0_1;
  struct foo * fooptr.1_2;
  int _6;

  <bb 2> [local count: 1073741824]:
  barptr.0_1 = barptr;
  barptr.0_1->val2 = 1;
  fooptr.1_2 = fooptr;
  MEM[(struct foo *)fooptr.1_2] = 0;
  _6 = barptr.0_1->val2;
  return _6;
}

I see no reason why we should not constant propagate the return value.

Honza

[-- Attachment #2: rep5-sametest2-fits6.gz --]
[-- Type: application/gzip, Size: 18106 bytes --]

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Richard Biener]

On Wed, May 29, 2019 at 3:21 PM Jan Hubicka <hubicka@ucw.cz> wrote:
>
> >
> > Please also see if there are testcases that do anything meaningful
> > and FAIL after instead of
> >
> >   /* Do access-path based disambiguation.  */
> >   if (ref1 && ref2
> >       && (handled_component_p (ref1) || handled_component_p (ref2)))
> >
> > doing
> >
> >   /* Do access-path based disambiguation.  */
> >   if (ref1 && ref2
> >       && (handled_component_p (ref1) && handled_component_p (ref2)))
> >
> On tramp3d we get quite few matches which are attached. If ref1 is
> MEM_REF and ref2 has non-trivial access path then it seems we need:
>  1) ref1 and ref2 to conflict (ref1 is a record or alias set 0)
>  2) basetype2 to contain ref1 (so it conflicts too)
>  3) if ref1 is a record than the access path may go into a type
>     contained as field of ref1 but via path not containing ref1 itself.
>
> I tried to construct testcase:
>
> truct foo {int val;} *fooptr;
> struct bar {struct foo foo; int val2;} *barptr;
> int test()
> {
>   struct foo foo={0};
>   barptr->val2 = 1;
>   *fooptr=foo;
>   return barptr->val2;
> }
>
> but we do not optimize it. I.e. optimized dump has:
>
> test ()
> {
>   struct bar * barptr.0_1;
>   struct foo * fooptr.1_2;
>   int _6;
>
>   <bb 2> [local count: 1073741824]:
>   barptr.0_1 = barptr;
>   barptr.0_1->val2 = 1;
>   fooptr.1_2 = fooptr;
>   MEM[(struct foo *)fooptr.1_2] = 0;
>   _6 = barptr.0_1->val2;
>   return _6;
> }
>
> I see no reason why we should not constant propagate the return value.

Indeed a good example.  Make it work and add it to the testsuite ;)
I would have said get_alias_set () on the ref type should already have
disambiguated 'int' (barptr->val2) from *fooptr (struct foo) but of course
they conflict because foo contains 'int'.

I guess it doesn't work because 'struct foo' isn't part of the other
path.  Here nonoverlapping_component_refs_of_decl_p would be
the vehicle to use (but IIRC that would also require a common
type in one of both paths).

Richard.

>
> Honza

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Jan Hubicka]

> > but we do not optimize it. I.e. optimized dump has:
> >
> > test ()
> > {
> >   struct bar * barptr.0_1;
> >   struct foo * fooptr.1_2;
> >   int _6;
> >
> >   <bb 2> [local count: 1073741824]:
> >   barptr.0_1 = barptr;
> >   barptr.0_1->val2 = 1;
> >   fooptr.1_2 = fooptr;
> >   MEM[(struct foo *)fooptr.1_2] = 0;
> >   _6 = barptr.0_1->val2;
> >   return _6;
> > }
> >
> > I see no reason why we should not constant propagate the return value.
> 
> Indeed a good example.  Make it work and add it to the testsuite ;)

I think Martin Jambor is working on it.  One needs -fno-tree-sra to
get this optimized :)
Othewise we punt on the check that both types in MEM_REF are the same.

Honza

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Martin Jambor]

Hi,

On Wed, May 29 2019, Jan Hubicka wrote:
>> > but we do not optimize it. I.e. optimized dump has:
>> >
>> > test ()
>> > {
>> >   struct bar * barptr.0_1;
>> >   struct foo * fooptr.1_2;
>> >   int _6;
>> >
>> >   <bb 2> [local count: 1073741824]:
>> >   barptr.0_1 = barptr;
>> >   barptr.0_1->val2 = 1;
>> >   fooptr.1_2 = fooptr;
>> >   MEM[(struct foo *)fooptr.1_2] = 0;
>> >   _6 = barptr.0_1->val2;
>> >   return _6;
>> > }
>> >
>> > I see no reason why we should not constant propagate the return value.
>> 
>> Indeed a good example.  Make it work and add it to the testsuite ;)
>
> I think Martin Jambor is working on it.  One needs -fno-tree-sra to
> get this optimized :)
> Othewise we punt on the check that both types in MEM_REF are the same.
>

I'd like to fix this with the following patch which passes bootstrap but
I have just found that it makes the following three tests fail:

 gcc.dg/tree-ssa/ssa-dse-26.c scan-tree-dump-times dse1 "Deleted dead store: x = " 1
 gcc.dg/tree-ssa/ssa-dse-26.c scan-tree-dump-times dse1 "Deleted dead store: y = " 1
 gnat.dg/opt39.adb scan-tree-dump-times optimized "MEM" 1

Hopefully all require only adjusting the testcase somehow, but it's
still something I need to look at tomorrow.  The patch can then be
incrementally improved to also work with one-element arrays which are
however indexed with an SSA_NAME.

As far as alias oracle statistics are concerned, the patch (on top of
r271763) improves from:

Alias oracle query stats:
  refs_may_alias_p: 3792598 disambiguations, 4181030 queries
  ref_maybe_used_by_call_p: 8291 disambiguations, 3829922 queries
  call_may_clobber_ref_p: 1092 disambiguations, 1092 queries
  aliasing_component_ref_p: 192 disambiguations, 18684 queries
  TBAA oracle: 1820750 disambiguations 3584527 queries
               778806 are in alias set 0
               723538 queries asked about the same object
               0 queries asked about the same alias set
               0 access volatile
               261267 are dependent in the DAG
               166 are aritificially in conflict with void *

to:

Alias oracle query stats:
  refs_may_alias_p: 3786679 disambiguations, 4174429 queries
  ref_maybe_used_by_call_p: 8285 disambiguations, 3824058 queries
  call_may_clobber_ref_p: 1092 disambiguations, 1092 queries
  aliasing_component_ref_p: 362 disambiguations, 19215 queries
  TBAA oracle: 1822975 disambiguations 3579314 queries
               775069 are in alias set 0
               727061 queries asked about the same object
               0 queries asked about the same alias set
               0 access volatile
               254043 are dependent in the DAG
               166 are aritificially in conflict with void *


Martin


Subject: [PATCH] Make SRA re-construct orginal memory accesses when easy

2019-05-30  Martin Jambor  <mjambor@suse.cz>

	* tree-sra.c (struct access): New field grp_same_access_path.
	(dump_access): Dump it.
	(build_reconstructed_reference): New function.
	(build_ref_for_model): Use it if possible.
	(path_comparable_for_same_access): New function.
	(same_access_path_p): Likewise.
	(sort_and_splice_var_accesses): Set the new flag.
	(analyze_access_subtree): Likewise.
	(propagate_subaccesses_across_link): Propagate zero value of the new
	flag down the access tree.

	testsuite/
	* gcc.dg/tree-ssa/alias-access-path-1.c: Remove -fno-tree-sra option.
---
 .../gcc.dg/tree-ssa/alias-access-path-1.c     |   2 +-
 gcc/tree-sra.c                                | 197 +++++++++++++++++-
 2 files changed, 190 insertions(+), 9 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
index 264f72aff0a..ba90b56fe5c 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-fre3 -fno-tree-sra" } */
+/* { dg-options "-O2 -fdump-tree-fre3" } */
 struct foo
 {
   int val;
diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c
index fd51a3d0323..dc2a776d66c 100644
--- a/gcc/tree-sra.c
+++ b/gcc/tree-sra.c
@@ -242,6 +242,10 @@ struct access
      access tree.  */
   unsigned grp_unscalarized_data : 1;
 
+  /* Set if all accesses in the group consist of the same chain of
+     COMPONENT_REFs and ARRAY_REFs.  */
+  unsigned grp_same_access_path : 1;
+
   /* Does this access and/or group contain a write access through a
      BIT_FIELD_REF?  */
   unsigned grp_partial_lhs : 1;
@@ -443,16 +447,18 @@ dump_access (FILE *f, struct access *access, bool grp)
 	     "grp_scalar_write = %d, grp_total_scalarization = %d, "
 	     "grp_hint = %d, grp_covered = %d, "
 	     "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
-	     "grp_partial_lhs = %d, grp_to_be_replaced = %d, "
-	     "grp_to_be_debug_replaced = %d, grp_maybe_modified = %d, "
+	     "grp_same_access_path = %d, grp_partial_lhs = %d, "
+	     "grp_to_be_replaced = %d, grp_to_be_debug_replaced = %d, "
+	     "grp_maybe_modified = %d, "
 	     "grp_not_necessarilly_dereferenced = %d\n",
 	     access->grp_read, access->grp_write, access->grp_assignment_read,
 	     access->grp_assignment_write, access->grp_scalar_read,
 	     access->grp_scalar_write, access->grp_total_scalarization,
 	     access->grp_hint, access->grp_covered,
 	     access->grp_unscalarizable_region, access->grp_unscalarized_data,
-	     access->grp_partial_lhs, access->grp_to_be_replaced,
-	     access->grp_to_be_debug_replaced, access->grp_maybe_modified,
+	     access->grp_same_access_path, access->grp_partial_lhs,
+	     access->grp_to_be_replaced, access->grp_to_be_debug_replaced,
+	     access->grp_maybe_modified,
 	     access->grp_not_necessarilly_dereferenced);
   else
     fprintf (f, ", write = %d, grp_total_scalarization = %d, "
@@ -1795,6 +1801,41 @@ build_ref_for_offset (location_t loc, tree base, poly_int64 offset,
   return mem_ref;
 }
 
+/* Construct and return a memory reference that is equal to a portion of
+   MODEL->expr but is based on BASE.  If this cannot be done, return NULL.  */
+
+static tree
+build_reconstructed_reference (location_t loc, tree base, struct access *model)
+{
+  auto_vec <tree, 8> model_comps;
+  tree expr = model->expr;
+  while (!types_compatible_p (TREE_TYPE (expr), TREE_TYPE (base)))
+    {
+      if (TREE_CODE (expr) != COMPONENT_REF
+	  && TREE_CODE (expr) != ARRAY_REF)
+	return NULL;
+      model_comps.safe_push (expr);
+      expr = TREE_OPERAND (expr, 0);
+    }
+
+  tree ref = unshare_expr (base);
+  while (!model_comps.is_empty ())
+    {
+      tree t = model_comps.pop ();
+      if (TREE_CODE (t) == COMPONENT_REF)
+	ref = build3_loc (loc, COMPONENT_REF, TREE_TYPE (t), ref,
+			  TREE_OPERAND (t, 1), TREE_OPERAND (t, 2));
+      else if (TREE_CODE (t) == ARRAY_REF)
+	ref = build4_loc (loc, ARRAY_REF, TREE_TYPE (t), ref,
+			  TREE_OPERAND (t, 1), TREE_OPERAND (t, 2),
+			  TREE_OPERAND (t, 3));
+      else
+	gcc_unreachable ();
+    }
+
+  return ref;
+}
+
 /* Construct a memory reference to a part of an aggregate BASE at the given
    OFFSET and of the same type as MODEL.  In case this is a reference to a
    bit-field, the function will replicate the last component_ref of model's
@@ -1822,9 +1863,19 @@ build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
 			      NULL_TREE);
     }
   else
-    return
-      build_ref_for_offset (loc, base, offset, model->reverse, model->type,
-			    gsi, insert_after);
+    {
+      tree res;
+      if (model->grp_same_access_path
+	  && offset <= model->offset
+	  && get_object_alignment (base) >= TYPE_ALIGN (TREE_TYPE (base))
+	  /* build_reconstructed_reference can still fail if we have already
+	     massaged BASE because of another type incompatibility.  */
+	  && (res = build_reconstructed_reference (loc, base, model)))
+	return res;
+      else
+	return build_ref_for_offset (loc, base, offset, model->reverse,
+				     model->type, gsi, insert_after);
+    }
 }
 
 /* Attempt to build a memory reference that we could but into a gimple
@@ -2076,6 +2127,121 @@ find_var_candidates (void)
   return ret;
 }
 
+/* Return true if EXP is a reference chain of COMPONENT_REFs and AREAY_REFs
+   ending either with a DECL or a MEM_REF with zero offset.  */
+
+static bool
+path_comparable_for_same_access (tree expr)
+{
+  while (handled_component_p (expr))
+    {
+      if (TREE_CODE (expr) == ARRAY_REF)
+	{
+	  /* SSA name indices can occur here too when the array is of sie one.
+	     But we cannot just re-use array_refs with SSA names elsewhere in
+	     the function, so disallow non-constant indices.  TODO: Remove this
+	     limitation after teaching build_reconstructed_reference to replace
+	     the index with the index type lower bound.  */
+	  if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST)
+	    return false;
+	}
+      else if (TREE_CODE (expr) != COMPONENT_REF)
+	return false;
+
+      expr = TREE_OPERAND (expr, 0);
+    }
+
+  if (TREE_CODE (expr) == MEM_REF)
+    {
+      if (!zerop (TREE_OPERAND (expr, 1)))
+	return false;
+    }
+  else
+    gcc_assert (DECL_P (expr));
+
+  return true;
+}
+
+/* Assuming that EXP1 consists of only COMPONENT_REFs and ARRAY_REFs, return
+   true if the chain of these handled components are exactly the same as EXP2
+   and the expression under them is the same DECL or an equivalent MEM_REF.
+   The reference picked by compare_access_positions must go to EXP1.  */
+
+static bool
+same_access_path_p (tree exp1, tree exp2)
+{
+  while (handled_component_p (exp1))
+    {
+      if (TREE_CODE (exp1) != TREE_CODE (exp2))
+	{
+	  /* Special case single-field structures loaded sometimes as the field
+	     and sometimes as the structure.  If the field is of a scalar type,
+	     compare_access_positions will put it into exp1.
+
+	     TODO: The gimple register type condition can be removed if teach
+	     compare_access_positions to put inner types first.  */
+	  if (is_gimple_reg_type (TREE_TYPE (exp1))
+	      && TREE_CODE (exp1) == COMPONENT_REF
+	      && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (exp1, 0)))
+		  == TYPE_MAIN_VARIANT (TREE_TYPE (exp2))))
+	    {
+	      exp1 = TREE_OPERAND (exp1, 0);
+	      continue;
+	    }
+	  return false;
+	}
+
+      if (TREE_CODE (exp1) == COMPONENT_REF)
+	{
+	  if (TREE_OPERAND (exp1, 1) != TREE_OPERAND (exp2, 1)
+	      || !tree_int_cst_equal (TREE_OPERAND (exp1, 2),
+				      TREE_OPERAND (exp2, 2)))
+	    return false;
+	}
+      else if (TREE_CODE (exp1) == ARRAY_REF)
+	{
+	  if (!tree_int_cst_equal (TREE_OPERAND (exp1, 1),
+				   TREE_OPERAND (exp2, 1))
+	      || !tree_int_cst_equal (array_ref_low_bound (exp1),
+				      array_ref_low_bound (exp2))
+	      || !tree_int_cst_equal (array_ref_element_size (exp1),
+				      array_ref_element_size (exp2)))
+	    return false;
+	}
+      else
+	gcc_unreachable ();
+
+      exp1 = TREE_OPERAND (exp1, 0);
+      exp2 = TREE_OPERAND (exp2, 0);
+    }
+
+  if (TREE_CODE (exp1) != TREE_CODE (exp2))
+    return false;
+
+  if (DECL_P (exp1))
+    {
+      gcc_assert (exp1 == exp2);
+      return true;
+    }
+  else if (TREE_CODE (exp1) == MEM_REF)
+    {
+      gcc_assert (TREE_CODE (TREE_OPERAND (exp1, 0)) == ADDR_EXPR
+		  && TREE_CODE (TREE_OPERAND (exp2, 0)) == ADDR_EXPR
+		  && DECL_P (TREE_OPERAND (TREE_OPERAND (exp1, 0), 0))
+		  && (TREE_OPERAND (TREE_OPERAND (exp1, 0), 0)
+		      == TREE_OPERAND (TREE_OPERAND (exp1, 0), 0))
+		  && tree_int_cst_equal (TREE_OPERAND (exp1, 1),
+					 TREE_OPERAND (exp2, 1)));
+
+      return ((TYPE_MAIN_VARIANT (TREE_TYPE (exp1))
+	       == TYPE_MAIN_VARIANT (TREE_TYPE (exp2)))
+	      && (TYPE_MAIN_VARIANT (reference_alias_ptr_type (exp1))
+		  == TYPE_MAIN_VARIANT (reference_alias_ptr_type (exp2))));
+    }
+  else
+    return false;
+}
+
 /* Sort all accesses for the given variable, check for partial overlaps and
    return NULL if there are any.  If there are none, pick a representative for
    each combination of offset and size and create a linked list out of them.
@@ -2116,6 +2282,7 @@ sort_and_splice_var_accesses (tree var)
       bool grp_partial_lhs = access->grp_partial_lhs;
       bool first_scalar = is_gimple_reg_type (access->type);
       bool unscalarizable_region = access->grp_unscalarizable_region;
+      bool grp_same_access_path = true;
       bool bf_non_full_precision
 	= (INTEGRAL_TYPE_P (access->type)
 	   && TYPE_PRECISION (access->type) != access->size
@@ -2134,6 +2301,8 @@ sort_and_splice_var_accesses (tree var)
 	gcc_assert (access->offset >= low
 		    && access->offset + access->size <= high);
 
+      grp_same_access_path = path_comparable_for_same_access (access->expr);
+
       j = i + 1;
       while (j < access_count)
 	{
@@ -2184,6 +2353,11 @@ sort_and_splice_var_accesses (tree var)
 		}
 	      unscalarizable_region = true;
 	    }
+
+	  if (grp_same_access_path
+	      && !same_access_path_p (access->expr, ac2->expr))
+	    grp_same_access_path = false;
+
 	  ac2->group_representative = access;
 	  j++;
 	}
@@ -2202,6 +2376,7 @@ sort_and_splice_var_accesses (tree var)
       access->grp_total_scalarization = total_scalarization;
       access->grp_partial_lhs = grp_partial_lhs;
       access->grp_unscalarizable_region = unscalarizable_region;
+      access->grp_same_access_path = grp_same_access_path;
 
       *prev_acc_ptr = access;
       prev_acc_ptr = &access->next_grp;
@@ -2471,6 +2646,8 @@ analyze_access_subtree (struct access *root, struct access *parent,
 	root->grp_assignment_write = 1;
       if (parent->grp_total_scalarization)
 	root->grp_total_scalarization = 1;
+      if (!parent->grp_same_access_path)
+	root->grp_same_access_path = 0;
     }
 
   if (root->grp_unscalarizable_region)
@@ -2721,13 +2898,17 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
 	  lacc->type = racc->type;
 	  if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t),
 						  lacc->offset, racc->type))
-	    lacc->expr = t;
+	    {
+	      lacc->expr = t;
+	      lacc->grp_same_access_path = true;
+	    }
 	  else
 	    {
 	      lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base),
 						lacc->base, lacc->offset,
 						racc, NULL, false);
 	      lacc->grp_no_warning = true;
+	      lacc->grp_same_access_path = false;
 	    }
 	}
       return ret;
-- 
2.21.0

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Martin Jambor]

Hi,
(now even including gcc-patches mailing list which we managed to drop
again and Honza whom I forgot to CC the last time)

On Thu, Jun 06 2019, Richard Biener wrote:
> yOn Tue, 4 Jun 2019, Martin Jambor wrote:
>> >> @@ -1822,9 +1863,19 @@ build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
>> >>  			      NULL_TREE);
>> >>      }
>> >>    else
>> >> -    return
>> >> -      build_ref_for_offset (loc, base, offset, model->reverse, model->type,
>> >> -			    gsi, insert_after);
>> >> +    {
>> >> +      tree res;
>> >> +      if (model->grp_same_access_path
>> >> +	  && offset <= model->offset
>> >> +	  && get_object_alignment (base) >= TYPE_ALIGN (TREE_TYPE (base))
>> >
>> > not sure what this tests - but I think it should be part of the
>> > grp_same_access_path check?
>> >
>> 
>> It checks that base is not under-aligned, I was assuming that I can
>> safely construct COMPONENT_REFs and ARRAY_REFs on a properly aligned
>> base.  I hope that is still safe even of reference copying with
>> unsharing but of course there is more room for surprises.
>> 
>> It cannot be part of grp_same_access_path check because BASE is now
>> something quite different.  For example when optimizing
>> 
>>   s = *p;
>>   v = s.i;
>> 
>> build_ref_for_model can be called to construct reference to load p->i
>> and BASE is *p, as opposed to grp_same_access_path where the path is
>> based on s.
>
> Oh, I see.  Still alignment is ultimatively on the base, so
> there shouldn't be any constraints here.  That is, if you
> substitute a base with different alignment the accesses will
> change accordingly and that's independend on whether you
> use a simple MEM_REF or re-build the access path.
>
>> 
>> The patch passes bootstrap end testing on x86_64-linux, please let me
>> know if there is anything else you'd like me to adjust.
>
> Looks good to me.  As said, eventually the alignment check is
> unnecessary.

OK, thank you.

I am going to commit it and then immediately follow up with a patch
removing the test.  The combination has just passed bootstrap and
testing on an x86_64-linux.  At least I hope the above is a permission
to do so.

Thanks,

Martin



Subject: [PATCH 2/2] Drop alignment check in build_reconstructed_reference

2019-06-06  Martin Jambor  <mjambor@suse.cz>

	* tree-sra.c (build_reconstructed_reference): Drop the alignment
	check.
---
 gcc/tree-sra.c | 3 ---
 1 file changed, 3 deletions(-)

diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c
index a246a93a48d..074d4964379 100644
--- a/gcc/tree-sra.c
+++ b/gcc/tree-sra.c
@@ -1817,9 +1817,6 @@ build_reconstructed_reference (location_t, tree base, struct access *model)
       expr = TREE_OPERAND (expr, 0);
     }
 
-  if (get_object_alignment (base) < get_object_alignment (expr))
-    return NULL;
-
   TREE_OPERAND (prev_expr, 0) = base;
   tree ref = unshare_expr (model->expr);
   TREE_OPERAND (prev_expr, 0) = expr;
-- 
2.21.0



For the reference of people on the mailing list, the first patch was:


Subject: [PATCH 1/2] Make SRA re-construct orginal memory accesses when easy

2019-06-03  Martin Jambor  <mjambor@suse.cz>

	* tree-sra.c (struct access): New field grp_same_access_path.
	(dump_access): Dump it.
	(build_reconstructed_reference): New function.
	(build_ref_for_model): Use it if possible.
	(path_comparable_for_same_access): New function.
	(same_access_path_p): Likewise.
	(sort_and_splice_var_accesses): Set the new flag.
	(analyze_access_subtree): Likewise.
	(propagate_subaccesses_across_link): Propagate zero value of the new
	flag down the access tree.

	testsuite/
	* gcc.dg/tree-ssa/alias-access-path-1.c: Remove -fno-tree-sra option.
	* gcc.dg/tree-ssa/ssa-dse-26.c: Disable FRE.
	* testsuite/gnat.dg/opt39.adb: Adjust scan dump.

Addressed Richi's comments
---
 .../gcc.dg/tree-ssa/alias-access-path-1.c     |   2 +-
 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c    |   2 +-
 gcc/testsuite/gnat.dg/opt39.adb               |   3 +-
 gcc/tree-sra.c                                | 135 ++++++++++++++++--
 4 files changed, 131 insertions(+), 11 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
index 264f72aff0a..ba90b56fe5c 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-fre3 -fno-tree-sra" } */
+/* { dg-options "-O2 -fdump-tree-fre3" } */
 struct foo
 {
   int val;
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c
index 32d63899b63..836a8092ab9 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-dse1-details -fno-short-enums" } */
+/* { dg-options "-O2 -fdump-tree-dse1-details -fno-short-enums -fno-tree-fre" } */
 /* { dg-skip-if "temporary variable for constraint_expr is never used" { msp430-*-* } } */
 
 enum constraint_expr_type
diff --git a/gcc/testsuite/gnat.dg/opt39.adb b/gcc/testsuite/gnat.dg/opt39.adb
index 3b12cf201ec..0a5ef67a2ed 100644
--- a/gcc/testsuite/gnat.dg/opt39.adb
+++ b/gcc/testsuite/gnat.dg/opt39.adb
@@ -27,4 +27,5 @@ begin
   end if;
 end;
 
--- { dg-final { scan-tree-dump-times "MEM" 1 "optimized" } }
+-- { dg-final { scan-tree-dump-not "MEM" "optimized" } }
+-- { dg-final { scan-tree-dump-not "tmp" "optimized" } }
diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c
index fd51a3d0323..a246a93a48d 100644
--- a/gcc/tree-sra.c
+++ b/gcc/tree-sra.c
@@ -106,6 +106,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "ipa-utils.h"
 #include "builtins.h"
 
+
 /* Enumeration of all aggregate reductions we can do.  */
 enum sra_mode { SRA_MODE_EARLY_IPA,   /* early call regularization */
 		SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
@@ -242,6 +243,10 @@ struct access
      access tree.  */
   unsigned grp_unscalarized_data : 1;
 
+  /* Set if all accesses in the group consist of the same chain of
+     COMPONENT_REFs and ARRAY_REFs.  */
+  unsigned grp_same_access_path : 1;
+
   /* Does this access and/or group contain a write access through a
      BIT_FIELD_REF?  */
   unsigned grp_partial_lhs : 1;
@@ -443,16 +448,18 @@ dump_access (FILE *f, struct access *access, bool grp)
 	     "grp_scalar_write = %d, grp_total_scalarization = %d, "
 	     "grp_hint = %d, grp_covered = %d, "
 	     "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
-	     "grp_partial_lhs = %d, grp_to_be_replaced = %d, "
-	     "grp_to_be_debug_replaced = %d, grp_maybe_modified = %d, "
+	     "grp_same_access_path = %d, grp_partial_lhs = %d, "
+	     "grp_to_be_replaced = %d, grp_to_be_debug_replaced = %d, "
+	     "grp_maybe_modified = %d, "
 	     "grp_not_necessarilly_dereferenced = %d\n",
 	     access->grp_read, access->grp_write, access->grp_assignment_read,
 	     access->grp_assignment_write, access->grp_scalar_read,
 	     access->grp_scalar_write, access->grp_total_scalarization,
 	     access->grp_hint, access->grp_covered,
 	     access->grp_unscalarizable_region, access->grp_unscalarized_data,
-	     access->grp_partial_lhs, access->grp_to_be_replaced,
-	     access->grp_to_be_debug_replaced, access->grp_maybe_modified,
+	     access->grp_same_access_path, access->grp_partial_lhs,
+	     access->grp_to_be_replaced, access->grp_to_be_debug_replaced,
+	     access->grp_maybe_modified,
 	     access->grp_not_necessarilly_dereferenced);
   else
     fprintf (f, ", write = %d, grp_total_scalarization = %d, "
@@ -1795,6 +1802,30 @@ build_ref_for_offset (location_t loc, tree base, poly_int64 offset,
   return mem_ref;
 }
 
+/* Construct and return a memory reference that is equal to a portion of
+   MODEL->expr but is based on BASE.  If this cannot be done, return NULL.  */
+
+static tree
+build_reconstructed_reference (location_t, tree base, struct access *model)
+{
+  tree expr = model->expr, prev_expr = NULL;
+  while (!types_compatible_p (TREE_TYPE (expr), TREE_TYPE (base)))
+    {
+      if (!handled_component_p (expr))
+	return NULL;
+      prev_expr = expr;
+      expr = TREE_OPERAND (expr, 0);
+    }
+
+  if (get_object_alignment (base) < get_object_alignment (expr))
+    return NULL;
+
+  TREE_OPERAND (prev_expr, 0) = base;
+  tree ref = unshare_expr (model->expr);
+  TREE_OPERAND (prev_expr, 0) = expr;
+  return ref;
+}
+
 /* Construct a memory reference to a part of an aggregate BASE at the given
    OFFSET and of the same type as MODEL.  In case this is a reference to a
    bit-field, the function will replicate the last component_ref of model's
@@ -1822,9 +1853,19 @@ build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset,
 			      NULL_TREE);
     }
   else
-    return
-      build_ref_for_offset (loc, base, offset, model->reverse, model->type,
-			    gsi, insert_after);
+    {
+      tree res;
+      if (model->grp_same_access_path
+	  && !TREE_THIS_VOLATILE (base)
+	  && offset <= model->offset
+	  /* build_reconstructed_reference can still fail if we have already
+	     massaged BASE because of another type incompatibility.  */
+	  && (res = build_reconstructed_reference (loc, base, model)))
+	return res;
+      else
+	return build_ref_for_offset (loc, base, offset, model->reverse,
+				     model->type, gsi, insert_after);
+    }
 }
 
 /* Attempt to build a memory reference that we could but into a gimple
@@ -2076,6 +2117,69 @@ find_var_candidates (void)
   return ret;
 }
 
+/* Return true if EXP is a reference chain of COMPONENT_REFs and AREAY_REFs
+   ending either with a DECL or a MEM_REF with zero offset.  */
+
+static bool
+path_comparable_for_same_access (tree expr)
+{
+  while (handled_component_p (expr))
+    {
+      if (TREE_CODE (expr) == ARRAY_REF)
+	{
+	  /* SSA name indices can occur here too when the array is of sie one.
+	     But we cannot just re-use array_refs with SSA names elsewhere in
+	     the function, so disallow non-constant indices.  TODO: Remove this
+	     limitation after teaching build_reconstructed_reference to replace
+	     the index with the index type lower bound.  */
+	  if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST)
+	    return false;
+	}
+      expr = TREE_OPERAND (expr, 0);
+    }
+
+  if (TREE_CODE (expr) == MEM_REF)
+    {
+      if (!zerop (TREE_OPERAND (expr, 1)))
+	return false;
+    }
+  else
+    gcc_assert (DECL_P (expr));
+
+  return true;
+}
+
+/* Assuming that EXP1 consists of only COMPONENT_REFs and ARRAY_REFs, return
+   true if the chain of these handled components are exactly the same as EXP2
+   and the expression under them is the same DECL or an equivalent MEM_REF.
+   The reference picked by compare_access_positions must go to EXP1.  */
+
+static bool
+same_access_path_p (tree exp1, tree exp2)
+{
+  if (TREE_CODE (exp1) != TREE_CODE (exp2))
+    {
+      /* Special case single-field structures loaded sometimes as the field
+	 and sometimes as the structure.  If the field is of a scalar type,
+	 compare_access_positions will put it into exp1.
+
+	 TODO: The gimple register type condition can be removed if teach
+	 compare_access_positions to put inner types first.  */
+      if (is_gimple_reg_type (TREE_TYPE (exp1))
+	  && TREE_CODE (exp1) == COMPONENT_REF
+	  && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (exp1, 0)))
+	      == TYPE_MAIN_VARIANT (TREE_TYPE (exp2))))
+	exp1 = TREE_OPERAND (exp1, 0);
+      else
+	return false;
+    }
+
+  if (!operand_equal_p (exp1, exp2, OEP_ADDRESS_OF))
+    return false;
+
+  return true;
+}
+
 /* Sort all accesses for the given variable, check for partial overlaps and
    return NULL if there are any.  If there are none, pick a representative for
    each combination of offset and size and create a linked list out of them.
@@ -2116,6 +2220,7 @@ sort_and_splice_var_accesses (tree var)
       bool grp_partial_lhs = access->grp_partial_lhs;
       bool first_scalar = is_gimple_reg_type (access->type);
       bool unscalarizable_region = access->grp_unscalarizable_region;
+      bool grp_same_access_path = true;
       bool bf_non_full_precision
 	= (INTEGRAL_TYPE_P (access->type)
 	   && TYPE_PRECISION (access->type) != access->size
@@ -2134,6 +2239,8 @@ sort_and_splice_var_accesses (tree var)
 	gcc_assert (access->offset >= low
 		    && access->offset + access->size <= high);
 
+      grp_same_access_path = path_comparable_for_same_access (access->expr);
+
       j = i + 1;
       while (j < access_count)
 	{
@@ -2184,6 +2291,11 @@ sort_and_splice_var_accesses (tree var)
 		}
 	      unscalarizable_region = true;
 	    }
+
+	  if (grp_same_access_path
+	      && !same_access_path_p (access->expr, ac2->expr))
+	    grp_same_access_path = false;
+
 	  ac2->group_representative = access;
 	  j++;
 	}
@@ -2202,6 +2314,7 @@ sort_and_splice_var_accesses (tree var)
       access->grp_total_scalarization = total_scalarization;
       access->grp_partial_lhs = grp_partial_lhs;
       access->grp_unscalarizable_region = unscalarizable_region;
+      access->grp_same_access_path = grp_same_access_path;
 
       *prev_acc_ptr = access;
       prev_acc_ptr = &access->next_grp;
@@ -2471,6 +2584,8 @@ analyze_access_subtree (struct access *root, struct access *parent,
 	root->grp_assignment_write = 1;
       if (parent->grp_total_scalarization)
 	root->grp_total_scalarization = 1;
+      if (!parent->grp_same_access_path)
+	root->grp_same_access_path = 0;
     }
 
   if (root->grp_unscalarizable_region)
@@ -2721,13 +2836,17 @@ propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
 	  lacc->type = racc->type;
 	  if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t),
 						  lacc->offset, racc->type))
-	    lacc->expr = t;
+	    {
+	      lacc->expr = t;
+	      lacc->grp_same_access_path = true;
+	    }
 	  else
 	    {
 	      lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base),
 						lacc->base, lacc->offset,
 						racc, NULL, false);
 	      lacc->grp_no_warning = true;
+	      lacc->grp_same_access_path = false;
 	    }
 	}
       return ret;
-- 
2.21.0

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Jan Hubicka]

Hi,
this is a variant of testcase I have comitted. Once Martin implements SRA
part, we could add next variant that drops -fno-tree-sra.

It seems odd that constant propagation only happens in fre3.
I woud expect fre1 to discover this already.
The IL before fre1 and 3 differs only by:

 test ()
 {
   struct foo foo;
   struct bar * barptr.0_1;
   struct foo * fooptr.1_2;
-  struct bar * barptr.2_3;
-  int _8;
+  int _7;
 
-  <bb 2> :
+  <bb 2> [local count: 1073741824]:
   foo.val = 0;
   barptr.0_1 = barptr;
   barptr.0_1->val2 = 123;
   fooptr.1_2 = fooptr;
   *fooptr.1_2 = foo;
-  barptr.2_3 = barptr;
-  _8 = barptr.2_3->val2;
+  _7 = barptr.0_1->val2;
   foo ={v} {CLOBBER};
-  return _8;
+  return _7;
 
 }

Why VN is not able to optimize the barptr access and lookup through
it at once?  It looks that could potentially save some need to re-run
GVN since it is common to store pointers to memory and use them multiple
times to access other pointers.

	* tree-ssa/alias-access-spath-1.c: new testcase.

Index: gcc.dg/tree-ssa/alias-access-path-1.c
===================================================================
--- gcc.dg/tree-ssa/alias-access-path-1.c	(nonexistent)
+++ gcc.dg/tree-ssa/alias-access-path-1.c	(working copy)
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre3 -fno-tree-sra" } */
+struct foo
+{
+  int val;
+} *fooptr;
+struct bar
+{
+  struct foo foo;
+  int val2;
+} *barptr;
+int
+test ()
+{
+  struct foo foo = { 0 };
+  barptr->val2 = 123;
+  *fooptr = foo;
+  return barptr->val2;
+}
+
+/* { dg-final { scan-tree-dump-times "return 123" 1 "fre3"} } */

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Richard Biener]

On Wed, 29 May 2019, Jan Hubicka wrote:

> Hi,
> this is a variant of testcase I have comitted. Once Martin implements SRA
> part, we could add next variant that drops -fno-tree-sra.
> 
> It seems odd that constant propagation only happens in fre3.
> I woud expect fre1 to discover this already.
> The IL before fre1 and 3 differs only by:
> 
>  test ()
>  {
>    struct foo foo;
>    struct bar * barptr.0_1;
>    struct foo * fooptr.1_2;
> -  struct bar * barptr.2_3;
> -  int _8;
> +  int _7;
>  
> -  <bb 2> :
> +  <bb 2> [local count: 1073741824]:
>    foo.val = 0;
>    barptr.0_1 = barptr;
>    barptr.0_1->val2 = 123;
>    fooptr.1_2 = fooptr;
>    *fooptr.1_2 = foo;
> -  barptr.2_3 = barptr;
> -  _8 = barptr.2_3->val2;
> +  _7 = barptr.0_1->val2;
>    foo ={v} {CLOBBER};
> -  return _8;
> +  return _7;
>  
>  }
> 
> Why VN is not able to optimize the barptr access and lookup through
> it at once?  It looks that could potentially save some need to re-run
> GVN since it is common to store pointers to memory and use them multiple
> times to access other pointers.

This is because in the first pass we substitute the value of
barptr.2_3 (barptr.0_1) when looking up barptr.2_3->val2 and
since that happens in VNs IL we run into
ao_ref_init_from_vn_reference which does not re-build
a GENERIC tree for the access path but leaves us with NULL
ao_ref.ref -- I suppose we could put the original ref tree
in there, too, even if the pieces are "valueized", it's just
a more imprecise representation of the ref.

That helps this testcase.

Bootstrap / regtest running on x86_64-unknown-linux-gnu.

Richard.

2019-05-31  Richard Biener  <rguenther@suse.de>

	* tree-ssa-sccvn.c (ao_ref_init_from_vn_reference): Get original
	full reference tree and record in ref->ref.
	(vn_reference_lookup_3): Pass in original ref to
	ao_ref_init_from_vn_reference.
	(vn_reference_lookup): Likewise.
	* tree-ssa-sccvn.h (ao_ref_init_from_vn_reference): Adjust prototype.

	* gcc.dg/tree-ssa/alias-access-path-1.c: Scan fre1.

Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c	(revision 271803)
+++ gcc/tree-ssa-sccvn.c	(working copy)
@@ -995,7 +995,7 @@ copy_reference_ops_from_ref (tree ref, v
 bool
 ao_ref_init_from_vn_reference (ao_ref *ref,
 			       alias_set_type set, tree type,
-			       vec<vn_reference_op_s> ops)
+			       vec<vn_reference_op_s> ops, tree orig_ref)
 {
   vn_reference_op_t op;
   unsigned i;
@@ -1149,7 +1149,7 @@ ao_ref_init_from_vn_reference (ao_ref *r
   if (base == NULL_TREE)
     return false;
 
-  ref->ref = NULL_TREE;
+  ref->ref = orig_ref;
   ref->base = base;
   ref->ref_alias_set = set;
   if (base_alias_set != -1)
@@ -1976,7 +1976,8 @@ vn_reference_lookup_3 (ao_ref *ref, tree
 	{
 	  lhs_ref_ok = ao_ref_init_from_vn_reference (&lhs_ref,
 						      get_alias_set (lhs),
-						      TREE_TYPE (lhs), lhs_ops);
+						      TREE_TYPE (lhs), lhs_ops,
+						      lhs);
 	  if (lhs_ref_ok
 	      && !refs_may_alias_p_1 (ref, &lhs_ref, true))
 	    {
@@ -2718,7 +2719,7 @@ vn_reference_lookup (tree op, tree vuse,
          Otherwise preserve the full reference for advanced TBAA.  */
       if (!valuezied_anything
 	  || !ao_ref_init_from_vn_reference (&r, vr1.set, vr1.type,
-					     vr1.operands))
+					     vr1.operands, op))
 	ao_ref_init (&r, op);
       if (! tbaa_p)
 	r.ref_alias_set = r.base_alias_set = 0;
Index: gcc/tree-ssa-sccvn.h
===================================================================
--- gcc/tree-ssa-sccvn.h	(revision 271803)
+++ gcc/tree-ssa-sccvn.h	(working copy)
@@ -229,7 +229,7 @@ vn_nary_op_t vn_nary_op_insert (tree, tr
 vn_nary_op_t vn_nary_op_insert_pieces (unsigned int, enum tree_code,
 				       tree, tree *, tree, unsigned int);
 bool ao_ref_init_from_vn_reference (ao_ref *, alias_set_type, tree,
-				    vec<vn_reference_op_s> );
+				    vec<vn_reference_op_s>, tree = NULL_TREE);
 vec<vn_reference_op_s> vn_reference_operands_for_lookup (tree);
 tree vn_reference_lookup_pieces (tree, alias_set_type, tree,
 				 vec<vn_reference_op_s> ,
Index: gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c	(revision 271803)
+++ gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c	(working copy)
@@ -1,5 +1,6 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-fre3 -fno-tree-sra" } */
+/* { dg-options "-O2 -fdump-tree-fre1 -fno-tree-sra" } */
+
 struct foo
 {
   int val;
@@ -18,4 +19,4 @@ test ()
   return barptr->val2;
 }
 
-/* { dg-final { scan-tree-dump-times "return 123" 1 "fre3"} } */
+/* { dg-final { scan-tree-dump-times "return 123" 1 "fre1"} } */

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Jan Hubicka]

Hi,
this is minimal version of patch adding just the pointer compare.
Bootstrapped/regtested x86_64-linux, makes sense? :)

Honza

	* tree-ssa-alias.c (same_type_for_tbaa): Return 1 if types
	same as pointers.

Index: tree-ssa-alias.c
===================================================================
--- tree-ssa-alias.c	(revision 271599)
+++ tree-ssa-alias.c	(working copy)
@@ -787,6 +787,10 @@ same_type_for_tbaa (tree type1, tree typ
   type1 = TYPE_MAIN_VARIANT (type1);
   type2 = TYPE_MAIN_VARIANT (type2);
 
+  /* Handle common case.  */
+  if (type1 == type2)
+    return 1;
+
   /* If we would have to do structural comparison bail out.  */
   if (TYPE_STRUCTURAL_EQUALITY_P (type1)
       || TYPE_STRUCTURAL_EQUALITY_P (type2))

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Richard Biener]

On Mon, 27 May 2019, Jan Hubicka wrote:

> Hi,
> this is minimal version of patch adding just the pointer compare.
> Bootstrapped/regtested x86_64-linux, makes sense? :)

Yes, obviously.

Richard.

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Jan Hubicka]

> On Mon, 27 May 2019, Jan Hubicka wrote:
> 
> > Hi,
> > this is minimal version of patch adding just the pointer compare.
> > Bootstrapped/regtested x86_64-linux, makes sense? :)
> 
> Yes, obviously.

Thanks, i will go ahead with installing it.
Note that I have also tested removal of:

  /* ??? Array types are not properly unified in all cases as we have
     spurious changes in the index types for example.  Removing this
     causes all sorts of problems with the Fortran frontend.  */
  if (TREE_CODE (type1) == ARRAY_TYPE
      && TREE_CODE (type2) == ARRAY_TYPE)
    return -1;

And it causes no regressions.  I looked for the history and see you
added it in 2009 because Fortran mixes up array of chars with char
itself.  I am not sure if that was fixed since then or it is just
about missing testcase?

It does not seem to be that important, but looks odd 
and makes me woried about other changes :)

Honza
> 
> Richard.

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Richard Biener]

[-- Attachment #1: Type: text/plain, Size: 2136 bytes --]

On Wed, 29 May 2019, Jan Hubicka wrote:

> > On Mon, 27 May 2019, Jan Hubicka wrote:
> > 
> > > Hi,
> > > this is minimal version of patch adding just the pointer compare.
> > > Bootstrapped/regtested x86_64-linux, makes sense? :)
> > 
> > Yes, obviously.
> 
> Thanks, i will go ahead with installing it.
> Note that I have also tested removal of:
> 
>   /* ??? Array types are not properly unified in all cases as we have
>      spurious changes in the index types for example.  Removing this
>      causes all sorts of problems with the Fortran frontend.  */
>   if (TREE_CODE (type1) == ARRAY_TYPE
>       && TREE_CODE (type2) == ARRAY_TYPE)
>     return -1;
> 
> And it causes no regressions.  I looked for the history and see you
> added it in 2009 because Fortran mixes up array of chars with char
> itself.  I am not sure if that was fixed since then or it is just
> about missing testcase?

I think we had a testcase back then and I'm not aware of any fixes
here.  The introducing mail says we miscompile protein (part of
polyhedron).  Another thing about arrays is that unification
doesn't work for VLAs even in C (consider nested fns being
inlined and sharing an array type with the caller), so we cannot
really say ARRAY_TYPEs with non-constant bounds are ever
"not equal".  So simply dropping this check looks wrong.
I'm not sure about char[] vs char but the FE definitely can
end up with char vs. char[1] and we need not consider those
different.

The fortran FE is similarly sloppy in other areas, see

      /* ??? We cannot simply use the type of operand #0 of the refs here
         as the Fortran compiler smuggles type punning into COMPONENT_REFs
         for common blocks instead of using unions like everyone else.  */
      tree type1 = DECL_CONTEXT (field1);
      tree type2 = DECL_CONTEXT (field2);



> It does not seem to be that important, but looks odd 
> and makes me woried about other changes :)
> 
> Honza
> > 
> > Richard.
> 

-- 
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)

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Jan Hubicka]

> >   /* ??? Array types are not properly unified in all cases as we have
> >      spurious changes in the index types for example.  Removing this
> >      causes all sorts of problems with the Fortran frontend.  */
> >   if (TREE_CODE (type1) == ARRAY_TYPE
> >       && TREE_CODE (type2) == ARRAY_TYPE)
> >     return -1;
> > 
> > And it causes no regressions.  I looked for the history and see you
> > added it in 2009 because Fortran mixes up array of chars with char
> > itself.  I am not sure if that was fixed since then or it is just
> > about missing testcase?
> 
> I think we had a testcase back then and I'm not aware of any fixes
> here.  The introducing mail says we miscompile protein (part of
> polyhedron).  Another thing about arrays is that unification
> doesn't work for VLAs even in C (consider nested fns being
> inlined and sharing an array type with the caller), so we cannot
> really say ARRAY_TYPEs with non-constant bounds are ever
> "not equal".  So simply dropping this check looks wrong.
> I'm not sure about char[] vs char but the FE definitely can
> end up with char vs. char[1] and we need not consider those
> different.
> 
> The fortran FE is similarly sloppy in other areas, see
> 
>       /* ??? We cannot simply use the type of operand #0 of the refs here
>          as the Fortran compiler smuggles type punning into COMPONENT_REFs
>          for common blocks instead of using unions like everyone else.  */
>       tree type1 = DECL_CONTEXT (field1);
>       tree type2 = DECL_CONTEXT (field2);

I think the reason why tings work now is the following test:

  /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
     object of one of its constrained subtypes, e.g. when a function with an
     unconstrained parameter passed by reference is called on an object and
     inlined.  But, even in the case of a fixed size, type and subtypes are
     not equivalent enough as to share the same TYPE_CANONICAL, since this
     would mean that conversions between them are useless, whereas they are
     not (e.g. type and subtypes can have different modes).  So, in the end,
     they are only guaranteed to have the same alias set.  */
  if (get_alias_set (type1) == get_alias_set (type2))
    return -1;

If you have arrays of compatible basetype, say
 int a[10] 
 int b[var] 
or array and its basetype, say
 int a[10] 
 int
we will end up returning -1 because array alias set is basetype alias
set unless it is TYPE_NONALIASED_COMPONENT (and I think those we should
be able to skip inside the access patch oracles).

With the array check removed we however will disambiguate
 int a[10];
 short a[10];

This has similar effect as logic I implemented in the original patch
(i.e. we can prove arrays to be incompatible, but without extra care
about VLA bounds we can't prove them to be same)

Honza
> 
> 
> 
> > It does not seem to be that important, but looks odd 
> > and makes me woried about other changes :)
> > 
> > Honza
> > > 
> > > Richard.
> > 
> 
> -- 
> 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)

Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors

[Jan Hubicka]

> I don't think it works like this, peeling arrays/vectors from
> types individually instead of in lock-step?
> 
> I think for better testing coverage you want to force
> TYPE_STRUCTURAL_EQUALITY on all types here - this shouldn't
> make things invalid but otherwise these code-paths are not
> tested very well.

Here is coverage of the function compiling tramp3d with -flto.
All the paths through are relatively frequent.
Most of time we call function for case where type1 and type2 have same
main variants.  Out of 1.5m remaining cases approx 30k are
pointers/arrays and go the structural walk which in 17k cases goes to
mismatched pointer types.

2k cases are considered equivalent because of canonical check and
126k cases we disprove equivalence.

        -:  780:/* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
        -:  781:   purpose of TBAA.  Return 0 if they are distinct and -1 if we cannot
        -:  782:   decide.  */
        -:  783:
        -:  784:static inline int
   669818:  785:same_type_for_tbaa (tree type1, tree type2)
        -:  786:{
   669818:  787:  type1 = TYPE_MAIN_VARIANT (type1);
   669818:  788:  type2 = TYPE_MAIN_VARIANT (type2);
        -:  789:
        -:  790:  /* If same_type_for_tbaa returns true we make an assumption that pointers to
        -:  791:     TYPE1 and TYPE2 can either point to same copy of the type or completely
        -:  792:     different.
        -:  793:
        -:  794:     This is not necessarily true for arrays where overlap can be partial
        -:  795:     as in gcc.dg/torture/alias-2.c.  So we can only prove that arrays are
        -:  796:     disjoint becuase they are derived from different types but we can not
        -:  797:     prove they are same.
        -:  798:
        -:  799:     On the other hand for pointers we can always consider them to be same
        -:  800:     unless we can prove that pointed-to types are different.
        -:  801:
        -:  802:     So normally return values are
        -:  803:       0  if types are known to be different
        -:  804:       1  if types are same and there is no partial overlap
        -:  805:       -1 otherwise.
        -:  806:
        -:  807:     However if comparing two pointers return values are
        -:  808:       0  if pointed to types are known to be different
        -:  809:       1  otherwise (because partial overlaps do not happen).
        -:  810:
        -:  811:     If comparing array or vector to other type return values are
        -:  812:       0  if types array/vector are derived from are known to be different
        -:  813:       -1 otherwise (to watch for partial overlaps).  */
        -:  814:
   669818:  815:  bool in_ptr = false;
   669818:  816:  bool in_array = false;
        -:  817:
   669818:  818:  if (type1 == type2)
   515089:  819:    return 1;
        -:  820:
        -:  821:  /* Do structural comparsion for types that have no canonical types in LTO.  */
   162119:  822:  while (TYPE_STRUCTURAL_EQUALITY_P (type1)
   162119:  823:	 || TYPE_STRUCTURAL_EQUALITY_P (type2))
        -:  824:    {
        -:  825:      /* Pointer types are same if they point to same types.  */
    30761:  826:      if (POINTER_TYPE_P (type1) && POINTER_TYPE_P (type2))
        -:  827:	{
     4662:  828:	  type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
     4662:  829:	  type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
     4662:  830:	  if (!in_array)
     4662:  831:	    in_ptr = true;
        -:  832:	}
        -:  833:      /* Peel out arrays and vector to compare inner types.  */
    52198:  834:      else if ((TREE_CODE (type1) == ARRAY_TYPE
    23728:  835:	        || TREE_CODE (type1) == VECTOR_TYPE)
    49827:  836:	       && TYPE_STRUCTURAL_EQUALITY_P (type1))
        -:  837:	{
     2371:  838:	  type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
     2371:  839:	  if (!in_ptr)
     2371:  840:	    in_array = true;
        -:  841:	}
    47456:  842:      else if ((TREE_CODE (type2) == ARRAY_TYPE
    21042:  843:	        || TREE_CODE (type2) == VECTOR_TYPE)
    44770:  844:	       && TYPE_STRUCTURAL_EQUALITY_P (type2))
        -:  845:	{
     2686:  846:	  type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
     2686:  847:	  if (!in_ptr)
     2686:  848:	    in_array = true;
        -:  849:	}
        -:  850:      else
        -:  851:	{
    21042:  852:	  if (POINTER_TYPE_P (type1) != POINTER_TYPE_P (type2))
    17208:  853:	    return 0;
    3834*:  854:	  return in_ptr ? 1 : -1;
        -:  855:	}
        -:  856:
     9719:  857:      if (type1 == type2)
     2329:  858:        return in_array ? -1 : 1;
        -:  859:    }
        -:  860:
        -:  861:  /* Compare the canonical types.  */
   131358:  862:  if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
    2604*:  863:    return in_array ? -1 : 1;
        -:  864:
        -:  865:  /* ??? Array types are not properly unified in all cases as we have
        -:  866:     spurious changes in the index types for example.  Removing this
        -:  867:     causes all sorts of problems with the Fortran frontend.  */
   128754:  868:  if (TREE_CODE (type1) == ARRAY_TYPE
    #####:  869:      && TREE_CODE (type2) == ARRAY_TYPE)
    #####:  870:    return in_ptr ? 1 : -1;
        -:  871:
        -:  872:  /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
        -:  873:     object of one of its constrained subtypes, e.g. when a function with an
        -:  874:     unconstrained parameter passed by reference is called on an object and
        -:  875:     inlined.  But, even in the case of a fixed size, type and subtypes are
        -:  876:     not equivalent enough as to share the same TYPE_CANONICAL, since this
        -:  877:     would mean that conversions between them are useless, whereas they are
        -:  878:     not (e.g. type and subtypes can have different modes).  So, in the end,
        -:  879:     they are only guaranteed to have the same alias set.  */
   128754:  880:  if (get_alias_set (type1) == get_alias_set (type2))
    1950*:  881:    return in_ptr ? 1 : -1;
        -:  882:
        -:  883:  /* The types are known to be not equal.  */
   126804:  884:  return 0;
        -:  885:}

Here is profile with unpatched version

        -:  780:/* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
        -:  781:   purpose of TBAA.  Return 0 if they are distinct and -1 if we cannot
        -:  782:   decide.  */
        -:  783:
        -:  784:static inline int
   610943:  785:same_type_for_tbaa (tree type1, tree type2)
        -:  786:{
   610943:  787:  type1 = TYPE_MAIN_VARIANT (type1);
   610943:  788:  type2 = TYPE_MAIN_VARIANT (type2);
        -:  789:
        -:  790:  /* If we would have to do structural comparison bail out.  */
   610943:  791:  if (TYPE_STRUCTURAL_EQUALITY_P (type1)
   610943:  792:      || TYPE_STRUCTURAL_EQUALITY_P (type2))
    36090:  793:    return -1;
        -:  794:
        -:  795:  /* Compare the canonical types.  */
   574853:  796:  if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
   452828:  797:    return 1;
        -:  798:
        -:  799:  /* ??? Array types are not properly unified in all cases as we have
        -:  800:     spurious changes in the index types for example.  Removing this
        -:  801:     causes all sorts of problems with the Fortran frontend.  */
   122025:  802:  if (TREE_CODE (type1) == ARRAY_TYPE
    #####:  803:      && TREE_CODE (type2) == ARRAY_TYPE)
    #####:  804:    return -1;
        -:  805:
        -:  806:  /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
        -:  807:     object of one of its constrained subtypes, e.g. when a function with an
        -:  808:     unconstrained parameter passed by reference is called on an object and
        -:  809:     inlined.  But, even in the case of a fixed size, type and subtypes are
        -:  810:     not equivalent enough as to share the same TYPE_CANONICAL, since this
        -:  811:     would mean that conversions between them are useless, whereas they are
        -:  812:     not (e.g. type and subtypes can have different modes).  So, in the end,
        -:  813:     they are only guaranteed to have the same alias set.  */
   122025:  814:  if (get_alias_set (type1) == get_alias_set (type2))
     1945:  815:    return -1;
        -:  816:
        -:  817:  /* The types are known to be not equal.  */
   120080:  818:  return 0;
        -:  819:}

I have started bootstrap where the pointer and array walks are forced
even for non-lto builds.
Honza