middle-end: Fix wrong code caused by disagreemed between FRE and access path oracle [PR 92152]

Hi,
This patch solves problem caused by the disagreement between FRE and access
path orracle.

FRE is checking stores for equivalence based on their address, value and
base+ref alias sets.  Because ref alias set is not always the alias set of
innermost type, but it may be one of refs in the access path (as decided by
component_uses_parent_alias_set_from) it means that we can not really rely on
the remaining part of access path to be meaningful in any way except for
offset+size computation.

The patch makes alias (which is used by FRE to validate transform) and
tree-ssa-alias to share same logic for ending the access path relevant for
TBAA. tree-ssa-alias previously ended access paths on VIEW_CONVERT_EXPR and
BIT_FIELD_REF so it is not hard to wire in common predicate.  However it led to
additional issues (I tried to read the code quite carefully for possible extra
fun, so I hope I found it all):

  1) alias_component_refs_walk compares base and reference sizes to see
     if one access path may continue by another.  This check can be confused
     by an union containing structure with zero sized array.  In this case we
     no longer see the refernece to zero sized array and think that ref size
     is 0.

     In an access path there can be at most one (valid) trailing/zero sized
     array access, so the sizes in the access path are decreasing with the
     this exception. This is already handled by the logic, however the access
     is not expected to happen past the end of TBAA segment.  I suppose this
     was kind of latent problem before because one can think of access path
     doing traling array past VIEW_CONVERT_EXPR, but since in C code we don't
     VCE and in non-C we don't do trailing arrays, we did not hit the problem.

     I fixed this by tracking if the trailing array references appearing after
     the end of TBAA access path and mostly punt in the second case (because we
     need to support kind of all type puning here). I do not think we can assume
     much of sanity here, in particular, we no longer know there is only one
     because FRE may mix things up.

     An exception is the walk that looks for occurence of basetype of path1
     within TBAA relevant part of path2.  Here we realy care about TBAA
     relevant parts of paths and thus do not need to give up.

     I broke out the logic into ends_tbaa_access_path_p to avoid duplication and
     to let me stick some detailed comments. This became much more complex
     than I originally imagined (still it is useful to make oracle both faster
     and more precise).

     Note that logic in aliasing_component_refs_walk is safe since it works
     on TBAA relevant segments of paths only.
  2) nonoverlapping_refs_since_match_p is using TBAA only in the corner case
     that the paths got out of sync and re-synchronize of types of same size
     are found.  I thus extended it to whole paths (not only TBAA relevant
     parts) and track if the TBAA part can be used by counting of number of
     TBAA relevant res on the stack.

     I have noticed that in one case we call nonoverlapping_refs_since_match_p
     before checking for view converting MEM_REFs and in others we check
     after.  I think we want to just disable TBAA part if view convert
     is in there but still disambiguate.  I will do this incrementaly.
  3) nonoverlapping_component_refs_p uses TBAA so it needs to punt on
     end of TBAA path. It deals with no sizes and thus there is not the issue
     as in 1).

I am also attaching one (most probably) valid C++ testcase (by Mark Williams)
where we incorrectly disambiguated while the code is valid by the common
initial sequence rule.  This happens to be fixed by same patch. Here one access
goes through union and follows by access path trhough one filed, while other
access path start by different field of the union with common initial sequence.
This made aliasing_component_refs_p to not find the overlapping type (because
there is none) and disambiguate.  Now we cut the first access path by the union
reference and this makes us to find the path continuation in
alias_component_refs_walk.

If FRE is ever made more careful about access paths past the fist union
reference (I think that would be good idea since unions are quite common in C++
and we throw away quite useful info) then we will need to teach access path
oracle about the common initial sequence rule (which, as Mark pointed out, is
part of both C and C++ standards).

Only argument that can possibly invalidate this testcase is that I do not see
that stadnard is clear about the situation where one access path contains the
union but other starts after the union.

Clearly if both start after the union reference we are right to disambiguate
(since there is no union unvolved).  If both starts before union then there is
common initial sequence and by standard it is defined. This case works on current
trunk because aliasing_component_refs_p resorts to base+offset after finding
the match. But even that is more or less an accident I would say.

I had to xfail three testcases.  While alias-access-path ones are
artificial and odd, 20030807-7 is derived from gcc and shows that we
give up on disambiguations of: tree is typedef to union  tree_node, so
this patch disables useful references through tree pointers.

I am still planning to collect some data on the effect of this change to
TBAA (running LTO bootstrap now), but unless we want to reorganize FRE,
I do not think there is better solution.

Bootstrapped/regtested x86_64-linux, OK?

gcc/ChangeLog:

2020-02-26  Jan Hubicka  <hubicka@ucw.cz>

	PR middle-end/92152
	* alias.c (ends_tbaa_access_path_p): Break out from ...
	(component_uses_parent_alias_set_from): ... here.
	* alias.h (ends_tbaa_access_path_p): Declare.
	* tree-ssa-alias.c (access_path_may_continue_p): Break out from ...;
	handle trailing arrays past end of tbaa access path.
	(aliasing_component_refs_p): ... here; likewise.
	(nonoverlapping_refs_since_match_p): Track TBAA segment of the access
	path; disambiguate also past end of it.
	(nonoverlapping_component_refs_p): Use only TBAA segment of the access
	path.

gcc/testsuite/ChangeLog:

2020-02-26  Jan Hubicka  <hubicka@ucw.cz>

	* gcc.dg/tree-ssa/alias-access-path-12.c: New testcase.
	* g++.dg/torture/pr92152.C: New testcase.
	* gcc.dg/torture/pr92152.c: New testcase.
	* gcc.dg/tree-ssa/20030807-7.c: xfail.
	* gcc.dg/tree-ssa/alias-access-path-4.c: xfail one case.
	* gcc.dg/tree-ssa/alias-access-path-5.c: xfail one case.

On Wed, 26 Feb 2020, Jan Hubicka wrote:

> Hi,
> This patch solves problem caused by the disagreement between FRE and access
> path orracle.
> 
> FRE is checking stores for equivalence based on their address, value and
> base+ref alias sets.  Because ref alias set is not always the alias set of
> innermost type, but it may be one of refs in the access path (as decided by
> component_uses_parent_alias_set_from) it means that we can not really rely on
> the remaining part of access path to be meaningful in any way except for
> offset+size computation.
> 
> The patch makes alias (which is used by FRE to validate transform) and
> tree-ssa-alias to share same logic for ending the access path relevant for
> TBAA. tree-ssa-alias previously ended access paths on VIEW_CONVERT_EXPR and
> BIT_FIELD_REF so it is not hard to wire in common predicate.  However it led to
> additional issues (I tried to read the code quite carefully for possible extra
> fun, so I hope I found it all):
> 
>   1) alias_component_refs_walk compares base and reference sizes to see
>      if one access path may continue by another.  This check can be confused
>      by an union containing structure with zero sized array.  In this case we
>      no longer see the refernece to zero sized array and think that ref size
>      is 0.
> 
>      In an access path there can be at most one (valid) trailing/zero sized
>      array access, so the sizes in the access path are decreasing with the
>      this exception. This is already handled by the logic, however the access
>      is not expected to happen past the end of TBAA segment.  I suppose this
>      was kind of latent problem before because one can think of access path
>      doing traling array past VIEW_CONVERT_EXPR, but since in C code we don't
>      VCE and in non-C we don't do trailing arrays, we did not hit the problem.
> 
>      I fixed this by tracking if the trailing array references appearing after
>      the end of TBAA access path and mostly punt in the second case (because we
>      need to support kind of all type puning here). I do not think we can assume
>      much of sanity here, in particular, we no longer know there is only one
>      because FRE may mix things up.
> 
>      An exception is the walk that looks for occurence of basetype of path1
>      within TBAA relevant part of path2.  Here we realy care about TBAA
>      relevant parts of paths and thus do not need to give up.
> 
>      I broke out the logic into ends_tbaa_access_path_p to avoid duplication and
>      to let me stick some detailed comments. This became much more complex
>      than I originally imagined (still it is useful to make oracle both faster
>      and more precise).
> 
>      Note that logic in aliasing_component_refs_walk is safe since it works
>      on TBAA relevant segments of paths only.
>   2) nonoverlapping_refs_since_match_p is using TBAA only in the corner case
>      that the paths got out of sync and re-synchronize of types of same size
>      are found.  I thus extended it to whole paths (not only TBAA relevant
>      parts) and track if the TBAA part can be used by counting of number of
>      TBAA relevant res on the stack.
> 
>      I have noticed that in one case we call nonoverlapping_refs_since_match_p
>      before checking for view converting MEM_REFs and in others we check
>      after.  I think we want to just disable TBAA part if view convert
>      is in there but still disambiguate.  I will do this incrementaly.
>   3) nonoverlapping_component_refs_p uses TBAA so it needs to punt on
>      end of TBAA path. It deals with no sizes and thus there is not the issue
>      as in 1).
> 
> I am also attaching one (most probably) valid C++ testcase (by Mark Williams)
> where we incorrectly disambiguated while the code is valid by the common
> initial sequence rule.  This happens to be fixed by same patch. Here one access
> goes through union and follows by access path trhough one filed, while other
> access path start by different field of the union with common initial sequence.
> This made aliasing_component_refs_p to not find the overlapping type (because
> there is none) and disambiguate.  Now we cut the first access path by the union
> reference and this makes us to find the path continuation in
> alias_component_refs_walk.
> 
> If FRE is ever made more careful about access paths past the fist union
> reference (I think that would be good idea since unions are quite common in C++
> and we throw away quite useful info) then we will need to teach access path
> oracle about the common initial sequence rule (which, as Mark pointed out, is
> part of both C and C++ standards).
> 
> Only argument that can possibly invalidate this testcase is that I do not see
> that stadnard is clear about the situation where one access path contains the
> union but other starts after the union.
> 
> Clearly if both start after the union reference we are right to disambiguate
> (since there is no union unvolved).  If both starts before union then there is
> common initial sequence and by standard it is defined. This case works on current
> trunk because aliasing_component_refs_p resorts to base+offset after finding
> the match. But even that is more or less an accident I would say.
> 
> I had to xfail three testcases.  While alias-access-path ones are
> artificial and odd, 20030807-7 is derived from gcc and shows that we
> give up on disambiguations of: tree is typedef to union  tree_node, so
> this patch disables useful references through tree pointers.
> 
> I am still planning to collect some data on the effect of this change to
> TBAA (running LTO bootstrap now), but unless we want to reorganize FRE,
> I do not think there is better solution.
> 
> Bootstrapped/regtested x86_64-linux, OK?

OK and thanks for the elaborate write-up and comments in the code ;)

Thanks,
Richard.

> gcc/ChangeLog:
> 
> 2020-02-26  Jan Hubicka  <hubicka@ucw.cz>
> 
> 	PR middle-end/92152
> 	* alias.c (ends_tbaa_access_path_p): Break out from ...
> 	(component_uses_parent_alias_set_from): ... here.
> 	* alias.h (ends_tbaa_access_path_p): Declare.
> 	* tree-ssa-alias.c (access_path_may_continue_p): Break out from ...;
> 	handle trailing arrays past end of tbaa access path.
> 	(aliasing_component_refs_p): ... here; likewise.
> 	(nonoverlapping_refs_since_match_p): Track TBAA segment of the access
> 	path; disambiguate also past end of it.
> 	(nonoverlapping_component_refs_p): Use only TBAA segment of the access
> 	path.
> 
> gcc/testsuite/ChangeLog:
> 
> 2020-02-26  Jan Hubicka  <hubicka@ucw.cz>
> 
> 	* gcc.dg/tree-ssa/alias-access-path-12.c: New testcase.
> 	* g++.dg/torture/pr92152.C: New testcase.
> 	* gcc.dg/torture/pr92152.c: New testcase.
> 	* gcc.dg/tree-ssa/20030807-7.c: xfail.
> 	* gcc.dg/tree-ssa/alias-access-path-4.c: xfail one case.
> 	* gcc.dg/tree-ssa/alias-access-path-5.c: xfail one case.
> 
> 
> diff --git a/gcc/alias.c b/gcc/alias.c
> index 3794f9b6a9e..fe75e22cdb5 100644
> --- a/gcc/alias.c
> +++ b/gcc/alias.c
> @@ -587,6 +587,49 @@ objects_must_conflict_p (tree t1, tree t2)
>    return alias_sets_must_conflict_p (set1, set2);
>  }
>  
> +/* Return true if T is an end of the access path which can be used
> +   by type based alias oracle.  */
> +
> +bool
> +ends_tbaa_access_path_p (const_tree t)
> +{
> +  switch (TREE_CODE (t))
> +    {
> +    case COMPONENT_REF:
> +      if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)))
> +	return true;
> +      /* Permit type-punning when accessing a union, provided the access
> +	 is directly through the union.  For example, this code does not
> +	 permit taking the address of a union member and then storing
> +	 through it.  Even the type-punning allowed here is a GCC
> +	 extension, albeit a common and useful one; the C standard says
> +	 that such accesses have implementation-defined behavior.  */
> +      else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (t, 0))) == UNION_TYPE)
> +	return true;
> +      break;
> +
> +    case ARRAY_REF:
> +    case ARRAY_RANGE_REF:
> +      if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0))))
> +	return true;
> +      break;
> +
> +    case REALPART_EXPR:
> +    case IMAGPART_EXPR:
> +      break;
> +
> +    case BIT_FIELD_REF:
> +    case VIEW_CONVERT_EXPR:
> +      /* Bitfields and casts are never addressable.  */
> +      return true;
> +      break;
> +
> +    default:
> +      gcc_unreachable ();
> +    }
> +  return false;
> +}
> +
>  /* Return the outermost parent of component present in the chain of
>     component references handled by get_inner_reference in T with the
>     following property:
> @@ -601,40 +644,8 @@ component_uses_parent_alias_set_from (const_tree t)
>  
>    while (handled_component_p (t))
>      {
> -      switch (TREE_CODE (t))
> -	{
> -	case COMPONENT_REF:
> -	  if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)))
> -	    found = t;
> -	  /* Permit type-punning when accessing a union, provided the access
> -	     is directly through the union.  For example, this code does not
> -	     permit taking the address of a union member and then storing
> -	     through it.  Even the type-punning allowed here is a GCC
> -	     extension, albeit a common and useful one; the C standard says
> -	     that such accesses have implementation-defined behavior.  */
> -	  else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (t, 0))) == UNION_TYPE)
> -	    found = t;
> -	  break;
> -
> -	case ARRAY_REF:
> -	case ARRAY_RANGE_REF:
> -	  if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0))))
> -	    found = t;
> -	  break;
> -
> -	case REALPART_EXPR:
> -	case IMAGPART_EXPR:
> -	  break;
> -
> -	case BIT_FIELD_REF:
> -	case VIEW_CONVERT_EXPR:
> -	  /* Bitfields and casts are never addressable.  */
> -	  found = t;
> -	  break;
> -
> -	default:
> -	  gcc_unreachable ();
> -	}
> +      if (ends_tbaa_access_path_p (t))
> +	found = t;
>  
>        t = TREE_OPERAND (t, 0);
>      }
> diff --git a/gcc/alias.h b/gcc/alias.h
> index 0fdf0095f2c..781b040fec1 100644
> --- a/gcc/alias.h
> +++ b/gcc/alias.h
> @@ -26,6 +26,7 @@ extern alias_set_type get_deref_alias_set (tree);
>  extern alias_set_type get_varargs_alias_set (void);
>  extern alias_set_type get_frame_alias_set (void);
>  extern tree component_uses_parent_alias_set_from (const_tree);
> +extern bool ends_tbaa_access_path_p (const_tree);
>  extern bool alias_set_subset_of (alias_set_type, alias_set_type);
>  extern void record_alias_subset (alias_set_type, alias_set_type);
>  extern void record_component_aliases (tree);
> diff --git a/gcc/testsuite/g++.dg/torture/pr92152.C b/gcc/testsuite/g++.dg/torture/pr92152.C
> new file mode 100644
> index 00000000000..1aff9b735be
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/torture/pr92152.C
> @@ -0,0 +1,74 @@
> +/* { dg-do run } */
> +using size_t = unsigned long;
> +using uint64_t = unsigned long;
> +
> +namespace HPHP {
> +
> +inline void bitvec_set(uint64_t* bits, size_t index) {
> +  bits[index / 64] |= 1ull << (index % 64);
> +}
> +
> +namespace jit {
> +///////////////////////////////////////////////////////////////////////////////
> +
> +struct VregSet {
> +  struct Block;
> +
> +  VregSet() : blocks{} { blocks.data[1] = 1LL << 0x30; };
> +
> +  VregSet(const VregSet& o)
> +    : blocks{o.blocks}
> +  {
> +  }
> +
> +  bool any() const {
> +    if (!isExtended()) return blocks.any();
> +    return true;
> +  }
> +  void removePhys() {
> +    auto const b = !isExtended() ? &blocks : extended.blocks;
> +    b->data[0] = 0;
> +    b->data[1] = 0;
> +  }
> +  static constexpr size_t kBitsPerBlock = 256;
> +  bool isExtended() const {
> +    return extended.data[1] & (1ULL << (kExtendedBit % 64));
> +  }
> +
> +  static constexpr size_t kExtendedBit = 127;
> +
> +  struct Block {
> +    bool any() const {
> +      return data[0] | data[1];
> +    }
> +    uint64_t data[2];
> +  };
> +  struct Extended {
> +    uint64_t data[2];
> +    Block* blocks;
> +  };
> +
> +  union {
> +    Block blocks{};
> +    Extended extended;
> +  };
> +};
> +
> +//////////////////////////////////////////////////////////////////////
> +
> +
> +__attribute__((noinline))
> +bool test(VregSet&& c) {
> +  auto copy = c;
> +  copy.removePhys();
> +  return copy.any();
> +}
> +///////////////////////////////////////////////////////////////////////////////
> +}}
> +///////////////////////////////////////////////////////////////////////////////
> +
> +int main() {
> +  if (HPHP::jit::test(HPHP::jit::VregSet{}))
> +    __builtin_abort ();
> +  return 0;
> +} 
> diff --git a/gcc/testsuite/gcc.dg/torture/pr92152.c b/gcc/testsuite/gcc.dg/torture/pr92152.c
> new file mode 100644
> index 00000000000..a4f883956d4
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/torture/pr92152.c
> @@ -0,0 +1,23 @@
> +/* { dg-do run } */
> +union U
> +{
> +  long long i;
> +  long f;
> +} v;
> + 	
> +long
> +foo (long *f)
> +{
> +  *f = 1;
> +  v.i = 0;
> +  v.f = 0;
> +  return *f;
> +}
> + 	
> +int
> +main ()
> +{
> +  if (foo (&v.f) != 0)
> +    __builtin_abort ();
> +  return 0;
> +}
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/20030807-7.c b/gcc/testsuite/gcc.dg/tree-ssa/20030807-7.c
> index 0dda180d43a..ca06f712890 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/20030807-7.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/20030807-7.c
> @@ -34,4 +34,4 @@ simplify_condition (cond_p)
>  }
>  
>  /* There should be exactly one IF conditional.  */
> -/* { dg-final { scan-tree-dump-times "if " 1 "vrp1" } } */
> +/* { dg-final { scan-tree-dump-times "if " 1 "vrp1" { xfail *-*-* } } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-12.c b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-12.c
> new file mode 100644
> index 00000000000..738f45503a5
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-12.c
> @@ -0,0 +1,20 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O1 -fno-strict-aliasing -fdump-tree-optimized" } */
> +
> +struct S
> +{
> +  int i;
> +  int j;
> +};
> +union U
> +{
> +  struct S a[10];
> +};
> +int
> +foo (union U *u, int n, int i, int j)
> +{
> +  u->a[i].i = 123;
> +  u->a[j].j = j;
> +  return u->a[i].i;
> +}
> +/* { dg-final { scan-tree-dump-times "return 123" 1 "optimized"} } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-4.c b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-4.c
> index 641ef89cbb8..2883fd37f31 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-4.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-4.c
> @@ -20,5 +20,5 @@ test2 (struct b *bptr1, union c *cptr, int i, int j)
>    cptr->b.a[j].v1=1;
>    return bptr1->a[i].v1;
>  }
> -/* { dg-final { scan-tree-dump-times "return 123" 1 "optimized"} } */
> +/* { dg-final { scan-tree-dump-times "return 123" 1 "optimized"  { xfail *-*-* } } } */
>  /* { dg-final { scan-tree-dump-not "return 124" "optimized"} } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-5.c b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-5.c
> index 412f99e7c55..c58d478e0eb 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-5.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-5.c
> @@ -21,5 +21,5 @@ test2 (struct b *bptr1, union c *cptr, int i, int j)
>    cptr->b.a[j].v1=1;
>    return bptr1->a[i].v1;
>  }
> -/* { dg-final { scan-tree-dump-times "return 123" 1 "optimized"} } */
> +/* { dg-final { scan-tree-dump-times "return 123" 1 "optimized"  { xfail *-*-* } } } */
>  /* { dg-final { scan-tree-dump-not "return 124" "optimized"} } */
> diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
> index 7554e209efa..2e8290f35d5 100644
> --- a/gcc/tree-ssa-alias.c
> +++ b/gcc/tree-ssa-alias.c
> @@ -995,6 +995,51 @@ aliasing_component_refs_walk (tree ref1, tree type1, tree base1,
>    return -1;
>  }
>  
> +/* Consider access path1 base1....ref1 and access path2 base2...ref2.
> +   Return true if they can be composed to single access path
> +   base1...ref1...base2...ref2.
> +
> +   REF_TYPE1 if type of REF1.  END_STRUCT_PAST_END1 is true if there is
> +   a trailing array access after REF1 in the non-TBAA part of the access.
> +   REF1_ALIAS_SET is the alias set of REF1.
> +
> +   BASE_TYPE2 is type of base2.  END_STRUCT_REF2 is non-NULL if there is
> +   a traling array access in the TBAA part of access path2.
> +   BASE2_ALIAS_SET is the alias set of base2.  */
> +
> +bool
> +access_path_may_continue_p (tree ref_type1, bool end_struct_past_end1,
> +			    alias_set_type ref1_alias_set,
> +			    tree base_type2, tree end_struct_ref2,
> +			    alias_set_type base2_alias_set)
> +{
> +  /* Access path can not continue past types with no components.  */
> +  if (!type_has_components_p (ref_type1))
> +    return false;
> +
> +  /* If first access path ends by too small type to hold base of
> +     the second access path, typically paths can not continue.
> +
> +     Punt if end_struct_past_end1 is true.  We want to support arbitrary
> +     type puning past first COMPONENT_REF to union because redundant store
> +     elimination depends on this, see PR92152.  For this reason we can not
> +     check size of the reference because types may partially overlap.  */
> +  if (!end_struct_past_end1)
> +    {
> +      if (compare_type_sizes (ref_type1, base_type2) < 0)
> +	return false;
> +      /* If the path2 contains trailing array access we can strenghten the check
> +	 to verify that also the size of element of the trailing array fits.
> +	 In fact we could check for offset + type_size, but we do not track
> +	 offsets and this is quite side case.  */
> +      if (end_struct_ref2
> +	  && compare_type_sizes (ref_type1, TREE_TYPE (end_struct_ref2)) < 0)
> +	return false;
> +    }
> +  return (base2_alias_set == ref1_alias_set
> +	  || alias_set_subset_of (base2_alias_set, ref1_alias_set));
> +}
> +
>  /* Determine if the two component references REF1 and REF2 which are
>     based on access types TYPE1 and TYPE2 and of which at least one is based
>     on an indirect reference may alias.  
> @@ -1021,8 +1066,30 @@ aliasing_component_refs_p (tree ref1,
>    tree type1, type2;
>    bool maybe_match = false;
>    tree end_struct_ref1 = NULL, end_struct_ref2 = NULL;
> +  bool end_struct_past_end1 = false;
> +  bool end_struct_past_end2 = false;
> +
> +  /* Choose bases and base types to search for.
> +     The access path is as follows:
> +       base....end_of_tbaa_ref...actual_ref
> +     At one place in the access path may be a reference to zero sized or
> +     trailing array.
> +
> +     We generally discard the segment after end_of_tbaa_ref however
> +     we need to be careful in case it contains zero sized or traling array.
> +     These may happen after refernce to union and in this case we need to
> +     not disambiguate type puning scenarios.
> +
> +     We set:
> +	base1 to point to base
> +
> +	ref1 to point to end_of_tbaa_ref
>  
> -  /* Choose bases and base types to search for.  */
> +	end_struct_ref1 to point the trailing reference (if it exists
> + 	in range base....end_of_tbaa_ref
> +
> +	end_struct_past_end1 is true if this traling refernece occurs in
> +	end_of_tbaa_ref...actual_ref.  */
>    base1 = ref1;
>    while (handled_component_p (base1))
>      {
> @@ -1042,9 +1109,15 @@ aliasing_component_refs_p (tree ref1,
>  	  gcc_checking_assert (!end_struct_ref1);
>            end_struct_ref1 = base1;
>  	}
> -      if (TREE_CODE (base1) == VIEW_CONVERT_EXPR
> -	  || TREE_CODE (base1) == BIT_FIELD_REF)
> -	ref1 = TREE_OPERAND (base1, 0);
> +      if (ends_tbaa_access_path_p (base1))
> +	{
> +	  ref1 = TREE_OPERAND (base1, 0);
> +	  if (end_struct_ref1)
> +	    {
> +	      end_struct_past_end1 = true;
> +	      end_struct_ref1 = NULL;
> +	    }
> +	}
>        base1 = TREE_OPERAND (base1, 0);
>      }
>    type1 = TREE_TYPE (base1);
> @@ -1056,9 +1129,15 @@ aliasing_component_refs_p (tree ref1,
>  	  gcc_checking_assert (!end_struct_ref2);
>  	  end_struct_ref2 = base2;
>  	}
> -      if (TREE_CODE (base2) == VIEW_CONVERT_EXPR
> -	  || TREE_CODE (base2) == BIT_FIELD_REF)
> -	ref2 = TREE_OPERAND (base2, 0);
> +      if (ends_tbaa_access_path_p (base2))
> +	{
> +	  ref2 = TREE_OPERAND (base2, 0);
> +	  if (end_struct_ref2)
> +	    {
> +	      end_struct_past_end2 = true;
> +	      end_struct_ref2 = NULL;
> +	    }
> +	}
>        base2 = TREE_OPERAND (base2, 0);
>      }
>    type2 = TREE_TYPE (base2);
> @@ -1070,7 +1149,8 @@ aliasing_component_refs_p (tree ref1,
>  
>    /* If type2 is big enough to contain type1 walk its access path.
>       We also need to care of arrays at the end of structs that may extend
> -     beyond the end of structure.  */
> +     beyond the end of structure.  If this occurs in the TBAA part of the
> +     access path, we need to consider the increased type as well.  */
>    if (cmp_outer >= 0
>        || (end_struct_ref2
>  	  && compare_type_sizes (TREE_TYPE (end_struct_ref2), type1) >= 0))
> @@ -1113,31 +1193,14 @@ aliasing_component_refs_p (tree ref1,
>        return false;
>      }
>  
> -  /* If we have two type access paths B1.path1 and B2.path2 they may
> -     only alias if either B1 is in B2.path2 or B2 is in B1.path1.
> -     But we can still have a path that goes B1.path1...B2.path2 with
> -     a part that we do not see.  So we can only disambiguate now
> -     if there is no B2 in the tail of path1 and no B1 on the
> -     tail of path2.  */
> -  if (compare_type_sizes (TREE_TYPE (ref2), type1) >= 0
> -      && (!end_struct_ref1
> -	  || compare_type_sizes (TREE_TYPE (ref2),
> -		 		 TREE_TYPE (end_struct_ref1)) >= 0)
> -      && type_has_components_p (TREE_TYPE (ref2))
> -      && (base1_alias_set == ref2_alias_set
> -          || alias_set_subset_of (base1_alias_set, ref2_alias_set)))
> -    {
> -      ++alias_stats.aliasing_component_refs_p_may_alias;
> -      return true;
> -    }
> -  /* If this is ptr vs. decl then we know there is no ptr ... decl path.  */
> -  if (compare_type_sizes (TREE_TYPE (ref1), type2) >= 0
> -      && (!end_struct_ref2
> -	  || compare_type_sizes (TREE_TYPE (ref1),
> -		 		 TREE_TYPE (end_struct_ref2)) >= 0)
> -      && type_has_components_p (TREE_TYPE (ref1))
> -      && (base2_alias_set == ref1_alias_set
> -	  || alias_set_subset_of (base2_alias_set, ref1_alias_set)))
> +  if (access_path_may_continue_p (TREE_TYPE (ref1), end_struct_past_end1,
> +				  ref1_alias_set,
> +				  type2, end_struct_ref2,
> +				  base2_alias_set)
> +      || access_path_may_continue_p (TREE_TYPE (ref2), end_struct_past_end2,
> +				     ref2_alias_set,
> +				     type1, end_struct_ref1,
> +				     base1_alias_set))
>      {
>        ++alias_stats.aliasing_component_refs_p_may_alias;
>        return true;
> @@ -1348,6 +1411,7 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
>  				   tree match2, tree ref2,
>  				   bool partial_overlap)
>  {
> +  int ntbaa1 = 0, ntbaa2 = 0;
>    /* Early return if there are no references to match, we do not need
>       to walk the access paths.
>  
> @@ -1365,25 +1429,33 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
>    /* Create the stack of handled components for REF1.  */
>    while (handled_component_p (ref1) && ref1 != match1)
>      {
> -      if (TREE_CODE (ref1) == VIEW_CONVERT_EXPR
> -	  || TREE_CODE (ref1) == BIT_FIELD_REF)
> -	component_refs1.truncate (0);
> +      /* We use TBAA only to re-synchronize after mismatched refs.  So we
> +	 do not need to truncate access path after TBAA part ends.  */
> +      if (ends_tbaa_access_path_p (ref1))
> +	ntbaa1 = 0;
>        else
> -        component_refs1.safe_push (ref1);
> +	ntbaa1++;
> +      component_refs1.safe_push (ref1);
>        ref1 = TREE_OPERAND (ref1, 0);
>      }
>  
>    /* Create the stack of handled components for REF2.  */
>    while (handled_component_p (ref2) && ref2 != match2)
>      {
> -      if (TREE_CODE (ref2) == VIEW_CONVERT_EXPR
> -	  || TREE_CODE (ref2) == BIT_FIELD_REF)
> -	component_refs2.truncate (0);
> +      if (ends_tbaa_access_path_p (ref2))
> +	ntbaa2 = 0;
>        else
> -        component_refs2.safe_push (ref2);
> +	ntbaa2++;
> +      component_refs2.safe_push (ref2);
>        ref2 = TREE_OPERAND (ref2, 0);
>      }
>  
> +  if (!flag_strict_aliasing)
> +    {
> +      ntbaa1 = 0;
> +      ntbaa2 = 0;
> +    }
> +
>    bool mem_ref1 = TREE_CODE (ref1) == MEM_REF && ref1 != match1;
>    bool mem_ref2 = TREE_CODE (ref2) == MEM_REF && ref2 != match2;
>  
> @@ -1444,6 +1516,7 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
>  	  for (; narray_refs1 > narray_refs2; narray_refs1--)
>  	    {
>  	      ref1 = component_refs1.pop ();
> +	      ntbaa1--;
>  
>  	      /* If index is non-zero we need to check whether the reference
>  		 does not break the main invariant that bases are either
> @@ -1471,6 +1544,7 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
>  	  for (; narray_refs2 > narray_refs1; narray_refs2--)
>  	    {
>  	      ref2 = component_refs2.pop ();
> +	      ntbaa2--;
>  	      if (!operand_equal_p (TREE_OPERAND (ref2, 1),
>  				    cheap_array_ref_low_bound (ref2), 0))
>  		return 0;
> @@ -1480,6 +1554,8 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
>  	    {
>  	      int cmp = nonoverlapping_array_refs_p (component_refs1.pop (),
>  						     component_refs2.pop ());
> +	      ntbaa1--;
> +	      ntbaa2--;
>  	      if (cmp == 1 && !partial_overlap)
>  		{
>  		  ++alias_stats
> @@ -1494,7 +1570,7 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
>  		     from type based alias analysis if we reach referneces to
>  		     same sizes.  We do not attempt to match array sizes, so
>  		     just finish array walking and look for component refs.  */
> -		  if (!flag_strict_aliasing)
> +		  if (ntbaa1 < 0 || ntbaa2 < 0)
>  		    {
>  		      ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
>  		      return -1;
> @@ -1503,6 +1579,8 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
>  		    {
>  		      component_refs1.pop ();
>  		      component_refs2.pop ();
> +		      ntbaa1--;
> +		      ntbaa2--;
>  		    }
>  		  break;
>  		}
> @@ -1520,10 +1598,11 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
>  	      return 0;
>  	    }
>  	  ref1 = component_refs1.pop ();
> +	  ntbaa1--;
>  	  if (TREE_CODE (ref1) != COMPONENT_REF)
>  	    {
>  	      seen_unmatched_ref_p = true;
> -	      if (!flag_strict_aliasing)
> +	      if (ntbaa1 < 0 || ntbaa2 < 0)
>  		{
>  		  ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
>  		  return -1;
> @@ -1541,9 +1620,10 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
>  	      return 0;
>  	    }
>  	  ref2 = component_refs2.pop ();
> +	  ntbaa2--;
>  	  if (TREE_CODE (ref2) != COMPONENT_REF)
>  	    {
> -	      if (!flag_strict_aliasing)
> +	      if (ntbaa1 < 0 || ntbaa2 < 0)
>  		{
>  		  ++alias_stats.nonoverlapping_refs_since_match_p_may_alias;
>  		  return -1;
> @@ -1569,11 +1649,9 @@ nonoverlapping_refs_since_match_p (tree match1, tree ref1,
>  
>        partial_overlap = false;
>  
> -      gcc_checking_assert (!seen_unmatched_ref_p || flag_strict_aliasing);
> -
>        /* If we skipped array refs on type of different sizes, we can
>  	 no longer be sure that there are not partial overlaps.  */
> -      if (seen_unmatched_ref_p
> +      if (seen_unmatched_ref_p && ntbaa1 >= 0 && ntbaa2 >= 0
>  	  && !operand_equal_p (TYPE_SIZE (type1), TYPE_SIZE (type2), 0))
>  	{
>  	  ++alias_stats
> @@ -1663,8 +1741,7 @@ nonoverlapping_component_refs_p (const_tree x, const_tree y)
>  	  if (TREE_CODE (type) == RECORD_TYPE)
>  	    fieldsx.safe_push (field);
>  	}
> -      else if (TREE_CODE (x) == VIEW_CONVERT_EXPR
> -	       || TREE_CODE (x) == BIT_FIELD_REF)
> +      else if (ends_tbaa_access_path_p (x))
>  	fieldsx.truncate (0);
>        x = TREE_OPERAND (x, 0);
>      }
> @@ -1680,8 +1757,7 @@ nonoverlapping_component_refs_p (const_tree x, const_tree y)
>  	  if (TREE_CODE (type) == RECORD_TYPE)
>  	    fieldsy.safe_push (TREE_OPERAND (y, 1));
>  	}
> -      else if (TREE_CODE (y) == VIEW_CONVERT_EXPR
> -	       || TREE_CODE (y) == BIT_FIELD_REF)
> +      else if (ends_tbaa_access_path_p (y))
>  	fieldsy.truncate (0);
>        y = TREE_OPERAND (y, 0);
>      }
>

> > Bootstrapped/regtested x86_64-linux, OK?
> 
> OK and thanks for the elaborate write-up and comments in the code ;)

Unforutnately our discussion on IRC let me construct another wrong code
testcase based on mixing up base alias sets

union U { long long i; long f; };
struct a {union U u;};
struct aa {struct a a;};
struct b {union U u;};
struct bb {struct b b;};
 
long
foo (struct bb *bv, void *ptr)
{
  struct aa *a = ptr;
  struct bb *b = ptr;
  bv->b.u.f = 1;
  a->a.u.i = 0;
  b->b.u.f = 0;
  return bv->b.u.f;
}
 
int
main ()
{
  union C {struct aa aa; struct bb bb;} v;
  if (foo (&v.bb, &v) != 0)
    __builtin_abort ();
  return 0;
}

I think there is no undefined behaviour here (at least if we assume that
first store to v.aa changes the type inmplied by earlier store to v.bb.

Honza

Hi,
this is and TBAA stat for building cc1 with -flto-partition=none.

From:

Alias oracle query stats:
  refs_may_alias_p: 46099243 disambiguations, 55677716 queries
  ref_maybe_used_by_call_p: 124351 disambiguations, 46883813 queries
  call_may_clobber_ref_p: 12673 disambiguations, 17133 queries
  nonoverlapping_component_refs_p: 0 disambiguations, 3803 queries
  nonoverlapping_refs_since_match_p: 19034 disambiguations, 46849 must overlaps, 67934 queries
  aliasing_component_refs_p: 76737 disambiguations, 300234 queries
  TBAA oracle: 15816119 disambiguations 39888339 queries
               12364426 are in alias set 0
               7655945 queries asked about the same object
               178 queries asked about the same alias set
               0 access volatile
               2963837 are dependent in the DAG
               1087834 are aritificially in conflict with void *

PTA query stats:
  pt_solution_includes: 904096 disambiguations, 9062937 queries
  pt_solutions_intersect: 853990 disambiguations, 10098128 queries

to:

Alias oracle query stats:
  refs_may_alias_p: 48168904 disambiguations, 57845554 queries
  ref_maybe_used_by_call_p: 124062 disambiguations, 48953042 queries
  call_may_clobber_ref_p: 12658 disambiguations, 17137 queries
  nonoverlapping_component_refs_p: 0 disambiguations, 3312 queries
  nonoverlapping_refs_since_match_p: 18997 disambiguations, 45778 must overlaps, 67109 queries
  aliasing_component_refs_p: 58756 disambiguations, 296126 queries
  TBAA oracle: 16036749 disambiguations 40132907 queries
               12352609 are in alias set 0
               7697466 queries asked about the same object
               178 queries asked about the same alias set
               0 access volatile
               2964615 are dependent in the DAG
               1081290 are aritificially in conflict with void *

PTA query stats:
  pt_solution_includes: 826579 disambiguations, 8987330 queries
  pt_solutions_intersect: 841758 disambiguations, 10078495 queries

So aliasing_component_refs_p drops from 25% disambiguation rate to 19% which
is quite noticeable. I will run SPEC benchmarks.
Firefox is not very releavnt here since it is -fno-strict-aliasing.

Honza

On Wed, 26 Feb 2020, Jan Hubicka wrote:

> Hi,
> this is and TBAA stat for building cc1 with -flto-partition=none.
> 
> From:
> 
> Alias oracle query stats:
>   refs_may_alias_p: 46099243 disambiguations, 55677716 queries
>   ref_maybe_used_by_call_p: 124351 disambiguations, 46883813 queries
>   call_may_clobber_ref_p: 12673 disambiguations, 17133 queries
>   nonoverlapping_component_refs_p: 0 disambiguations, 3803 queries
>   nonoverlapping_refs_since_match_p: 19034 disambiguations, 46849 must overlaps, 67934 queries
>   aliasing_component_refs_p: 76737 disambiguations, 300234 queries
>   TBAA oracle: 15816119 disambiguations 39888339 queries
>                12364426 are in alias set 0
>                7655945 queries asked about the same object
>                178 queries asked about the same alias set
>                0 access volatile
>                2963837 are dependent in the DAG
>                1087834 are aritificially in conflict with void *
> 
> PTA query stats:
>   pt_solution_includes: 904096 disambiguations, 9062937 queries
>   pt_solutions_intersect: 853990 disambiguations, 10098128 queries
> 
> to:
> 
> Alias oracle query stats:
>   refs_may_alias_p: 48168904 disambiguations, 57845554 queries
>   ref_maybe_used_by_call_p: 124062 disambiguations, 48953042 queries
>   call_may_clobber_ref_p: 12658 disambiguations, 17137 queries
>   nonoverlapping_component_refs_p: 0 disambiguations, 3312 queries
>   nonoverlapping_refs_since_match_p: 18997 disambiguations, 45778 must overlaps, 67109 queries
>   aliasing_component_refs_p: 58756 disambiguations, 296126 queries
>   TBAA oracle: 16036749 disambiguations 40132907 queries
>                12352609 are in alias set 0
>                7697466 queries asked about the same object
>                178 queries asked about the same alias set
>                0 access volatile
>                2964615 are dependent in the DAG
>                1081290 are aritificially in conflict with void *
> 
> PTA query stats:
>   pt_solution_includes: 826579 disambiguations, 8987330 queries
>   pt_solutions_intersect: 841758 disambiguations, 10078495 queries
> 
> So aliasing_component_refs_p drops from 25% disambiguation rate to 19% which
> is quite noticeable. I will run SPEC benchmarks.

OTOH overall TBAA oracle goes from 39.95% to 39.65% only also overall
refs_may_alias_p disambiguation rate goes up!  So I'm not sure you
can compare those numbers since the set of queries in both is
different and possibly unrelated enough...

Different early opt and thus different partitioning/inlining might
also lead to a not meaningful comparison.

Richard.