Re: Make nonoverlapping_component_refs work with duplicated main variants

[Jan Hubicka <hubicka@ucw.cz>]

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?
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);
+
+  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 
+    {
+      /* 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;
+
+      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;
+
+      /* 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;
+
+      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;
+}
+