Strenghten aliasing_component_refs_p

[Jan Hubicka]

> On Thu, 23 May 2019, Bernhard Reutner-Fischer wrote:
> 
> > On 20 May 2019 11:40:17 CEST, Richard Biener <rguenther@suse.de> wrote:
> > >On Sun, 19 May 2019, Jan Hubicka wrote:
> > >
> > >> > On Fri, 17 May 2019, Jan Hubicka wrote:
> > >> > 
> > >> > > Hi,
> > >> > > this patch cuts walks in aliasing_component_refs_p if the type we
> > >look for
> > >> > > can not fit into a given type by comparing their sizes. Similar
> > >logic
> > >> > > already exists in indirect_ref_may_alias_decl_p.
> > >> > > 
> > >> > > When we walk reference a.b.c.d.e looking for type x we only need
> > >to do
> > >> > > it if sizeof(a)>=sizeof(x) and continue woking from e until
> > >> > > sizeof(e)<=sizeof(x). We do not need to compare types where sizes
> > >are
> > >> > > known to be different.
> > >> > > 
> > >> > > This saves some work (by not walking refs and not comparing their
> > >types
> > >> > > if they can not match) but also increases number of
> > >disambiguations
> > >> > > quite noticably. This is because same_type_for_tbaa often returns
> > >-1 and
> > >> > > makes aliasing_compinent_refs_p to give up.  Using the simple
> > >size check
> > >> > > prevents hitting such problematic type pairs in many common
> > >cases.
> > >> > > 
> > >> > > Stats on tramp3d lto build change From:
> > >> > > 
> > >> > > Alias oracle query stats:
> > >> > >   refs_may_alias_p: 0 disambiguations, 0 queries
> > >> > >   ref_maybe_used_by_call_p: 6451 disambiguations, 25578 queries
> > >> > >   call_may_clobber_ref_p: 817 disambiguations, 817 queries
> > >> > >   aliasing_component_ref_p: 14 disambiguations, 12528 queries
> > >> > >   TBAA oracle: 1468347 disambiguations 3010562 queries
> > >> > >                550690 are in alias set 0
> > >> > >                614235 queries asked about the same object
> > >> > >                0 queries asked about the same alias set
> > >> > >                0 access volatile
> > >> > >                260937 are dependent in the DAG
> > >> > >                116353 are aritificially in conflict with void *
> > >> > > 
> > >> > > to:
> > >> > > 
> > >> > > Alias oracle query stats:
> > >> > >   refs_may_alias_p: 0 disambiguations, 0 queries
> > >> > >   ref_maybe_used_by_call_p: 6451 disambiguations, 25580 queries
> > >> > >   call_may_clobber_ref_p: 817 disambiguations, 817 queries
> > >> > >   aliasing_component_ref_p: 118 disambiguations, 12552 queries
> > >> > >   TBAA oracle: 1468413 disambiguations 3010714 queries
> > >> > >                550719 are in alias set 0
> > >> > >                614247 queries asked about the same object
> > >> > >                0 queries asked about the same alias set
> > >> > >                0 access volatile
> > >> > >                260970 are dependent in the DAG
> > >> > >                116365 are aritificially in conflict with void *
> > >> > > 
> > >> > > So disambiguations are up from 14 to 118 which is still quite
> > >low.
> > >> > > 
> > >> > > A followup patch making types_same_for_tbaa to not give up for
> > >> > > TYPE_STRUCTURAL_EQUALITY pointers and arrays improves hitrate to
> > >2723.
> > >> > > 
> > >> > > Bootstrapped/regtested x86_64-linux, OK?
> > >> > > 
> > >> > > 	* tree-ssa-alias.c (type_big_enough_for_type_p): New function.
> > >> > > 	(aliasing_component_refs_p): Use it.
> > >> > > Index: tree-ssa-alias.c
> > >> > >
> > >===================================================================
> > >> > > --- tree-ssa-alias.c	(revision 271292)
> > >> > > +++ tree-ssa-alias.c	(working copy)
> > >> > > @@ -735,6 +735,27 @@ ao_ref_init_from_ptr_and_size (ao_ref *r
> > >> > >    ref->volatile_p = false;
> > >> > >  }
> > >> > >  
> > >> > > +/* Return true if TYPE1 may contain TYPE2 by its size.  */
> > >> > > +
> > >> > > +static bool
> > >> > > +type_big_enough_for_type_p (tree type1, tree type2)
> > >> > > +{
> > >> > > +  if (!TYPE_SIZE (type1) || !TYPE_SIZE (type2))
> > >> > > +    return true;
> > >> > > +  /* Be conservative for arrays and vectors.  We want to support
> > >partial
> > >> > > +     overlap on int[3] and int[3] as tested in
> > >gcc.dg/torture/alias-2.c.  */
> > >> > > +  while (TREE_CODE (type2) == ARRAY_TYPE
> > >> > > +	 || TREE_CODE (type2) == VECTOR_TYPE)
> > >> > > +    type2 = TREE_TYPE (type2);
> > >> > 
> > >> > Eww ;)  I guess this means same-type can never return true for
> > >> > array or vectors?
> > >> > 
> > >> > > +  if (!poly_int_tree_p (TYPE_SIZE (type1))
> > >> > > +      || !poly_int_tree_p (TYPE_SIZE (type2)))
> > >> > > +    return true;
> > >> > 
> > >> > Use
> > >> > 
> > >> >     poly_uint64 size1;
> > >> >     if (!poly_int_tree_p (TYPE_SIZE (type1), &size1)
> > >> >  ...
> > >> > 
> > >> > > +  if (known_lt (wi::to_poly_widest (TYPE_SIZE (type1)),
> > >> > > +		wi::to_poly_widest (TYPE_SIZE (type2))))
> > >> > 
> > >> > and
> > >> > 
> > >> >      if (known_lt (size1, size2))
> > >> > 
> > >> > I wonder if you can compute whether type1 fits in type2 and
> > >> > the other way around at the same time, saving seemingly
> > >> > redundant work since you test both ways most of the time below.
> > >> > So sth like type_size_compare_for_fitting () returning
> > >> > -1, 0, 1 and use zero for "don't know"?
> > >> 
> > >> Hi,
> > >> this patch implements the three way compare and also merges the code
> > >> with same logic in indirect_ref_may_alias_decl_p.
> > >> We end up doing more known_lt calls than necessary because sometimes
> > >we
> > >> do not care about the three way outcome, but I asusme that this
> > >should
> > >> be relatively cheap once we pass the earlier test and tree to
> > >poly_int
> > >> conversion.
> > >> 
> > >> Bootstrapped/regtested x86_64-linux, OK?
> > >> 
> > >> 	* tree-ssa-alias.c (compare_sizes): New function.
> > >> 	(sompare_type_sizes): New function
> > >> 	(aliasing_component_refs_p): Use it.
> > >> 	(indirect_ref_may_alias_decl_p): Likewise.
> > >> Index: tree-ssa-alias.c
> > >> ===================================================================
> > >> --- tree-ssa-alias.c	(revision 271379)
> > >> +++ tree-ssa-alias.c	(working copy)
> > >> @@ -735,6 +735,48 @@ ao_ref_init_from_ptr_and_size (ao_ref *r
> > >>    ref->volatile_p = false;
> > >>  }
> > >>  
> > >> +/* S1 and S2 are TYPE_SIZE or DECL_SIZE.  Compare them:
> > >> +   Return -1 if S1 < S2
> > >> +   Return 1 if S1 > S2
> > >> +   Return 0 if equal or incoparable.  */
> > >
> > >incomparable.
> > >
> > >OK with that fix.
> > 
> > Really? See below.
> > 
> > >
> > >Richard.
> > >
> > >> +
> > >> +static int
> > >> +compare_sizes (tree s1, tree s2)
> > >> +{
> > >> +  if (!s1 || !s2)
> > >> +    return 0;
> > >> +
> > >> +  poly_uint64 size1 = poly_int_tree_p (s1, &size1);
> > >> +  poly_uint64 size2 = poly_int_tree_p (s2, &size2);
> > 
> > Doesn't poly_into_tree_p return a bool?
> > I think we want to omit these two initializers.
> > thanks,
> 
> Whoops, didn't notice that.
> 
> Indeed - Honza please fix.

Sorry for that - too much cut&paste I assume.
I am testing fix (the bug is harmless, we just do the conversion
twice) and looking into the soplex issue.

Honza