Re: Make nonoverlapping_component_refs work with duplicated main variants

[Richard Biener <rguenther@suse.de>]

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

On Tue, 9 Jul 2019, Jan Hubicka wrote:

> Hi,
> this is updated patch.  I based the logic on gimple_compare_field_offset but
> dropped bits about PLACEHOLDER_EXPR since my understanding is that to get
> comparsion done I would then need to compare operand #2 of COMPONENT_REF which
> I don't.
> 
> I also wrote the range checks using polyint since I believe that most code is
> supposed to be updated this way (shall we update gimple_compare_field_offset?

For consistency yes I guess but IIRC they cannot really appear in 
FIELD_DECLs.

> It is used in canonical type merging and considering fields different may lead
> to wrong code I would say, but I do not know enough about SVE to construct
> testcase).
> 
> I updated documentation of return values which I also find somewhat confusing
> since 1/0 meanings in nonoverlapping_* is reversed compared to
> aliasing_component_refs.  Main entry is called refs_may_alias so I am
> considering rename all the functions into *_may_alias and make them return 0
> for disambiguation, 1 for non-disambiguation and use -1's to keep decidion
> whether to work harder.
> 
> However for now I am sticking with the nonoverlapping reversed semantics.
> 
> 
> There are no changes in tramp3d stats (there are no unmerged types)
> Here are stats on cc1plus build:
> 
> Alias oracle query stats:
>   refs_may_alias_p: 43435216 disambiguations, 51989307 queries
>   ref_maybe_used_by_call_p: 60843 disambiguations, 44040532 queries
>   call_may_clobber_ref_p: 6051 disambiguations, 9115 queries
>   nonoverlapping_component_refs_p: 0 disambiguations, 2535 queries
>   nonoverlapping_component_refs_since_match_p: 12297 disambiguations, 40458 must overlaps, 53243 queries
>   aliasing_component_refs_p: 70892 disambiguations, 374789 queries
>   TBAA oracle: 12680127 disambiguations 32179405 queries
>                10383370 are in alias set 0
>                5747729 queries asked about the same object
>                148 queries asked about the same alias set
>                0 access volatile
>                2482808 are dependent in the DAG
>                885223 are aritificially in conflict with void *
> 
> PTA query stats:
>   pt_solution_includes: 562382 disambiguations, 7467931 queries
>   pt_solutions_intersect: 412873 disambiguations, 7818955 queries
> 
> It seems that nonoverlapping_component_refs_since_match_p is pretty good on
> making decision and there are only few cases where it return -1 which is good.
> So i guess teaching it about ARRAY_REFs is logical next step.
> 
> If I would like to benchmark alias oracle compile time, what is
> reasonable way to do that?
> 
> Bootstrapped/regtested x86_64-linux, OK?
> 
> Honza
> 
> 	* tree-ssa-alias.c (nonoverlapping_component_refs_p_1): Break out
> 	from ...; work also on duplicated types.
> 	(nonoverlapping_component_refs_since_match): ... here
> 	(ncr_type_uid): Break out from ...
> 	(ncr_compar): ... here; look for TYPE_UID of canonical type if
> 	available.
> 	(nonoverlapping_component_refs_p): Use same_type_for_tbaa to match
> 	the types and nonoverlapping_component_refs_p_1 to disambiguate.
> 	* g++.dg/lto/alias-3_0.C: New file.
> 	* g++.dg/lto/alias-3_1.c: New file.
> 
> Index: tree-ssa-alias.c
> ===================================================================
> --- tree-ssa-alias.c	(revision 273193)
> +++ tree-ssa-alias.c	(working copy)
> @@ -1128,6 +1128,90 @@ aliasing_component_refs_p (tree ref1,
>    return false;
>  }
>  
> +/* FIELD1 and FIELD2 are two component refs whose bases either do
> +   not overlap at all or their addresses are the same.
> +
> +   Return 1 if FIELD1 and FIELD2 are non-overlapping
> +
> +   Return 0 if FIELD1 and FIELD2 are posisbly overlapping but in case of
> +   overlap their addresses are the same.
> +
> +   Return -1 otherwise.
> +
> +   Main difference between 0 and -1 is to let
> +   nonoverlapping_component_refs_since_match_p discover the semnatically
> +   equivalent part of the access path.  */
> +
> +static int
> +nonoverlapping_component_refs_p_1 (const_tree field1, const_tree field2)
> +{
> +  /* If both fields are of the same type, we could save hard work of
> +     comparing offsets.
> +     ??? 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);
> +

drop the vertical space

> +  if (type1 == type2 && TREE_CODE (type1) == RECORD_TYPE)
> +    {
> +      if (field1 == field2)
> +	return 0;
> +      /* A field and its representative need to be considered the
> +	 same.  */
> +      if (DECL_BIT_FIELD_REPRESENTATIVE (field1) == field2
> +	  || DECL_BIT_FIELD_REPRESENTATIVE (field2) == field1)
> +	return 0;
> +      /* Different fields of the same record type cannot overlap.
> +	 ??? Bitfields can overlap at RTL level so punt on them.  */
> +      if (DECL_BIT_FIELD (field1) && DECL_BIT_FIELD (field2))
> +	return 0;
> +      /* Assume that different FIELD_DECLs never overlap in a RECORD_TYPE.  */
> +      return 1;
> +    }
> +  else 
> +    {

drop the else {

> +      /* Different fields of the same record type cannot overlap.
> +	 ??? Bitfields can overlap at RTL level so punt on them.  */
> +      if (DECL_BIT_FIELD (field1) && DECL_BIT_FIELD (field2))
> +	return 0;
> +

don't you need the DECL_BIT_FIELD_REPRESENTATIVE check here as well?
I'd do

        if (DECL_BIT_FIELD_REPRESENTATIVE (field1))
          field1 = DECL_BIT_FIELD_REPRESENTATIVE (field1);
        if (DECL_BIT_FIELD_REPRESENTATIVE (field2))
          field2 = DECL_BIT_FIELD_REPRESENTATIVE (field2);

thus use the representative for the overlap check.  It might
be the case that we can improve here and if we do this
can do the DECL_BIT_FIELD check after this (hoping the
representative doesn't have it set).

> +      if (tree_int_cst_equal (DECL_FIELD_OFFSET (field1),
> +			      DECL_FIELD_OFFSET (field2))
> +	  && tree_int_cst_equal (DECL_FIELD_BIT_OFFSET (field1),
> +				 DECL_FIELD_BIT_OFFSET (field2)))
> +	return 0;

In gimple_compare_field_offset this was fast-pathed for
DECL_OFFSET_ALIGN (f1) == DECL_OFFSET_ALIGN (f2) so I suggest to
do that here as well.  Note that DECL_FIELD_OFFSET can be
a non-constant which means you cannot use tree_int_cst_equal
unconditionally here but you have to use operand_equal_p.

> +      /* Note that it may be possible to use component_ref_field_offset
> +	 which would provide offsets as trees. However constructing and folding
> +	 trees is expensive and does not seem to be worth the compile time
> +	 cost.  */
> +
> +      poly_uint64 offset1, offset2;
> +      poly_uint64 bit_offset1, bit_offset2;
> +      poly_uint64 size1, size2;

I think you need poly_offset_int here since you convert to bits below.

The gimple_compare_field_offset checking way looks cheaper btw, so
I wonder why you don't simply call it but replicate things here?
When do we expect to have partially overlapping field decls?  Even
when considering canonical type merging?

> +      if (poly_int_tree_p (DECL_FIELD_OFFSET (field1), &offset1)
> +	  && poly_int_tree_p (DECL_FIELD_OFFSET (field2), &offset2)
> +          && poly_int_tree_p (DECL_FIELD_BIT_OFFSET (field1), &bit_offset1)
> +	  && poly_int_tree_p (DECL_FIELD_BIT_OFFSET (field2), &bit_offset2)
> +	  && poly_int_tree_p (DECL_SIZE (field1), &size1)
> +	  && poly_int_tree_p (DECL_SIZE (field2), &size2))
> +	{
> +	  offset1 = (offset1 << LOG2_BITS_PER_UNIT) + bit_offset1;
> +	  offset2 = (offset2 << LOG2_BITS_PER_UNIT) + bit_offset2;
> +
> +	  if (known_eq (offset1, offset2))
> +	    return 0;
> +	  if (!ranges_maybe_overlap_p (offset1, size1, offset2, size2))
> +	    return 1;
> +	}
> +    }
> +  /* Resort to slower overlap checking by looking for matching types in
> +     the middle of access path.  */
> +  return -1;
> +}
> +
>  /* Try to disambiguate REF1 and REF2 under the assumption that MATCH1 and
>     MATCH2 either point to the same address or are disjoint.
>     MATCH1 and MATCH2 are assumed to be ref in the access path of REF1 and REF2
> @@ -1224,6 +1308,7 @@ nonoverlapping_component_refs_since_matc
>       case the return value will precisely be false.  */
>    while (true)
>      {
> +      bool seen_noncomponent_ref_p = false;
>        do
>  	{
>  	  if (component_refs1.is_empty ())
> @@ -1233,6 +1318,8 @@ nonoverlapping_component_refs_since_matc
>  	      return 0;
>  	    }
>  	  ref1 = component_refs1.pop ();
> +	  if (TREE_CODE (ref1) != COMPONENT_REF)
> +	    seen_noncomponent_ref_p = true;
>  	}
>        while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1, 0))));
>  
> @@ -1245,17 +1332,15 @@ nonoverlapping_component_refs_since_matc
>  	      return 0;
>  	    }
>  	  ref2 = component_refs2.pop ();
> +	  if (TREE_CODE (ref2) != COMPONENT_REF)
> +	    seen_noncomponent_ref_p = true;
>  	}
>        while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2, 0))));
>  
> -      /* Beware of BIT_FIELD_REF.  */
> -      if (TREE_CODE (ref1) != COMPONENT_REF
> -	  || TREE_CODE (ref2) != COMPONENT_REF)
> -	{
> -	  ++alias_stats
> -		.nonoverlapping_component_refs_since_match_p_may_alias;
> -	  return -1;
> -	}
> +      /* BIT_FIELD_REF and VIEW_CONVERT_EXPR are taken off the vectors
> +	 earlier.  */
> +      gcc_checking_assert (TREE_CODE (ref1) == COMPONENT_REF
> +			   && TREE_CODE (ref2) == COMPONENT_REF);
>  
>        tree field1 = TREE_OPERAND (ref1, 1);
>        tree field2 = TREE_OPERAND (ref2, 1);
> @@ -1266,33 +1351,27 @@ nonoverlapping_component_refs_since_matc
>        tree type1 = DECL_CONTEXT (field1);
>        tree type2 = DECL_CONTEXT (field2);
>  
> -      /* We cannot disambiguate fields in a union or qualified union.  */
> -      if (type1 != type2 || TREE_CODE (type1) != RECORD_TYPE)
> +      /* If we skipped array refs on type of different sizes, we can
> +	 no longer be sure that there are not partial overlaps.  */
> +      if (seen_noncomponent_ref_p
> +	  && !operand_equal_p (TYPE_SIZE (type1), TYPE_SIZE (type2), 0))
>  	{
> -	  ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias;
> +	  ++alias_stats
> +	    .nonoverlapping_component_refs_since_match_p_may_alias;
>  	  return -1;
>  	}
>  
> -      if (field1 != field2)
> +      int cmp = nonoverlapping_component_refs_p_1 (field1, field2);
> +      if (cmp == -1)
>  	{
> -	  /* A field and its representative need to be considered the
> -	     same.  */
> -	  if (DECL_BIT_FIELD_REPRESENTATIVE (field1) == field2
> -	      || DECL_BIT_FIELD_REPRESENTATIVE (field2) == field1)
> -	    {
> -	      ++alias_stats
> -		.nonoverlapping_component_refs_since_match_p_must_overlap;
> -	      return 0;
> -	    }
> -	  /* Different fields of the same record type cannot overlap.
> -	     ??? Bitfields can overlap at RTL level so punt on them.  */
> -	  if (DECL_BIT_FIELD (field1) && DECL_BIT_FIELD (field2))
> -	    {
> -	      ++alias_stats
> -		.nonoverlapping_component_refs_since_match_p_must_overlap;
> -	      return 0;
> -	    }
> -	  ++alias_stats.nonoverlapping_component_refs_since_match_p_no_alias;
> +	  ++alias_stats
> +	    .nonoverlapping_component_refs_since_match_p_may_alias;
> +	  return -1;
> +	}
> +      else if (cmp == 1)
> +	{
> +	  ++alias_stats
> +	    .nonoverlapping_component_refs_since_match_p_no_alias;
>  	  return 1;
>  	}
>      }
> @@ -1301,6 +1380,24 @@ nonoverlapping_component_refs_since_matc
>    return 0;
>  }
>  
> +/* Return TYPE_UID which can be used to match record types we consider
> +   same for TBAA purposes.  */
> +
> +static inline int
> +ncr_type_uid (const_tree field)
> +{
> +  /* ??? 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 type = DECL_FIELD_CONTEXT (field);
> +  /* With LTO types considered same_type_for_tbaa_p 
> +     from different translation unit may not have same
> +     main variant.  They however have same TYPE_CANONICAL.  */
> +  if (TYPE_CANONICAL (type))
> +    return TYPE_UID (TYPE_CANONICAL (type));
> +  return TYPE_UID (type);
> +}
> +
>  /* qsort compare function to sort FIELD_DECLs after their
>     DECL_FIELD_CONTEXT TYPE_UID.  */
>  
> @@ -1309,8 +1406,9 @@ ncr_compar (const void *field1_, const v
>  {
>    const_tree field1 = *(const_tree *) const_cast <void *>(field1_);
>    const_tree field2 = *(const_tree *) const_cast <void *>(field2_);
> -  unsigned int uid1 = TYPE_UID (DECL_FIELD_CONTEXT (field1));
> -  unsigned int uid2 = TYPE_UID (DECL_FIELD_CONTEXT (field2));
> +  unsigned int uid1 = ncr_type_uid (field1);
> +  unsigned int uid2 = ncr_type_uid (field2);
> +
>    if (uid1 < uid2)
>      return -1;
>    else if (uid1 > uid2)
> @@ -1377,10 +1475,9 @@ nonoverlapping_component_refs_p (const_t
>    if (fieldsx.length () == 1
>        && fieldsy.length () == 1)
>     {
> -     if ((DECL_FIELD_CONTEXT (fieldsx[0])
> -         == DECL_FIELD_CONTEXT (fieldsy[0]))
> -        && fieldsx[0] != fieldsy[0]
> -        && !(DECL_BIT_FIELD (fieldsx[0]) && DECL_BIT_FIELD (fieldsy[0])))
> +     if (same_type_for_tbaa (DECL_FIELD_CONTEXT (fieldsx[0]),
> +			     DECL_FIELD_CONTEXT (fieldsy[0])) == 1
> +	 && nonoverlapping_component_refs_p_1 (fieldsx[0], fieldsy[0]) == 1)
>        {
>           ++alias_stats.nonoverlapping_component_refs_p_no_alias;
>           return true;
> @@ -1413,31 +1510,18 @@ nonoverlapping_component_refs_p (const_t
>      {
>        const_tree fieldx = fieldsx[i];
>        const_tree fieldy = fieldsy[j];
> -      tree typex = DECL_FIELD_CONTEXT (fieldx);
> -      tree typey = DECL_FIELD_CONTEXT (fieldy);
> -      if (typex == typey)
> -	{
> -	  /* We're left with accessing different fields of a structure,
> -	     no possible overlap.  */
> -	  if (fieldx != fieldy)
> -	    {
> -	      /* A field and its representative need to be considered the
> -		 same.  */
> -	      if (DECL_BIT_FIELD_REPRESENTATIVE (fieldx) == fieldy
> -		  || DECL_BIT_FIELD_REPRESENTATIVE (fieldy) == fieldx)
> -		;
> -	      /* Different fields of the same record type cannot overlap.
> -		 ??? Bitfields can overlap at RTL level so punt on them.  */
> -	      else if (DECL_BIT_FIELD (fieldx) && DECL_BIT_FIELD (fieldy))
> -		;
> -	      else
> -		{
> -		  ++alias_stats.nonoverlapping_component_refs_p_no_alias;
> -		  return true;
> -		}
> -	    }
> +
> +      /* We're left with accessing different fields of a structure,
> +	 no possible overlap.  */
> +      if (same_type_for_tbaa (DECL_FIELD_CONTEXT (fieldx),
> +			      DECL_FIELD_CONTEXT (fieldy)) == 1
> +	  && nonoverlapping_component_refs_p_1 (fieldx, fieldy) == 1)
> +	{
> +	  ++alias_stats.nonoverlapping_component_refs_p_no_alias;
> +	  return true;
>  	}
> -      if (TYPE_UID (typex) < TYPE_UID (typey))
> +
> +      if (ncr_type_uid (fieldx) < ncr_type_uid (fieldy))
>  	{
>  	  i++;
>  	  if (i == fieldsx.length ())
> Index: testsuite/g++.dg/lto/alias-3_0.C
> ===================================================================
> --- testsuite/g++.dg/lto/alias-3_0.C	(nonexistent)
> +++ testsuite/g++.dg/lto/alias-3_0.C	(working copy)
> @@ -0,0 +1,27 @@
> +/* { dg-lto-do run } */
> +/* { dg-lto-options { { -O3 -flto -fno-early-inlining } } } */
> +
> +struct a
> +{
> +  int foo,bar;
> +};
> +struct b
> +{
> +  struct a a[10];
> +};
> +
> +__attribute__ ((used)) struct b b, *bptr=&b, *bptr2=&b;
> +__attribute__ ((used)) int i,j;
> +
> +extern "C" void inline_me_late (void);
> +
> +int
> +main (void)
> +{
> +  int jj=j;
> +  bptr2->a[jj].bar = 0;
> +  inline_me_late ();
> +  if (!__builtin_constant_p (bptr2->a[jj].bar == 0))
> +    __builtin_abort ();
> +  return 0;
> +}
> Index: testsuite/g++.dg/lto/alias-3_1.c
> ===================================================================
> --- testsuite/g++.dg/lto/alias-3_1.c	(nonexistent)
> +++ testsuite/g++.dg/lto/alias-3_1.c	(working copy)
> @@ -0,0 +1,20 @@
> +/* { dg-lto-do run } */
> +/* { dg-lto-options { { -O3 -flto -fno-early-inlining } } } */
> +struct a
> +{
> +  int foo,bar;
> +};
> +struct b
> +{
> +  struct a a[10];
> +};
> +
> +extern  struct b *bptr;
> +extern  int i;
> +
> +void
> +inline_me_late (void)
> +{
> +  bptr->a[i].foo=1;
> +}
> +
> 

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