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

[Jan Hubicka <hubicka@ucw.cz>]

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