Make nonoverlapping_component_refs work with duplicated main variants

[Jan Hubicka <hubicka@ucw.cz>]

Hi,
this patch avoids == compare of main varinats in nonoverlapping_component_refs
making them work on unmerged type (such as when one is C++ ODR and other is C).
This is not hard to do
   - nonoverlapping_component_refs_since_match is
     -fno-strict-aliasing safe and only cares about type sizes/field offsets.
   - nonoverlapping_component_refs_p does same test as aliasing_component_refs
     (use TBAA to derive the fact that types either fully overlap or not at
      all) and thus can use types_same_for_tbaa_p.
     For structures this leads to TYPE_CANONICAL compare so I now use decl
     uids of canonical types in the loop.
I have also refactored the code to share the logic about bitfields and uids
which was copied to multple places.

Bootstrapped/regtested x86_64-linux, OK?

	* 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,63 @@ aliasing_component_refs_p (tree ref1,
   return false;
 }
 
+/* FIELD1 and FIELD2 are two component refs whose bases are either
+   both at the same address or completely disjoint.
+   Return 1 if FIELD1 and FIELD2 are non-overlapping
+   Return 0 if FIELD1 and FIELD2 are having same addresses or are
+     completely disjoint.
+   Return -1 if we can not decide.  */
+
+static int
+nonoverlapping_component_refs_p_1 (const_tree field1, const_tree field2)
+{
+  /* ??? 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);
+
+  /* A simple fast path.  */
+  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 -1;
+      return 1;
+    }
+  else 
+    {
+      if (operand_equal_p (DECL_FIELD_BIT_OFFSET (field1),
+			   DECL_FIELD_BIT_OFFSET (field2), 0))
+	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 -1;
+
+      poly_uint64 offset1;
+      poly_uint64 offset2;
+      poly_uint64 size1;
+      poly_uint64 size2;
+      if (!poly_int_tree_p (DECL_FIELD_BIT_OFFSET (field1), &offset1)
+	  || !poly_int_tree_p (DECL_FIELD_BIT_OFFSET (field2), &offset2)
+	  || !poly_int_tree_p (DECL_SIZE (field1), &size1)
+	  || !poly_int_tree_p (DECL_SIZE (field2), &size2)
+	  || ranges_maybe_overlap_p (offset1, size1, offset2, size2))
+	return -1;
+      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 +1281,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 +1291,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 +1305,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 +1324,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,16 +1353,33 @@ 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.  */
 
 static inline int
-ncr_compar (const void *field1_, const void *field2_)
+ncr_compar (const void *field1, const void *field2)
 {
-  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 (*(const_tree *) field1);
+  unsigned int uid2 = ncr_type_uid (*(const_tree *) field2);
+
   if (uid1 < uid2)
     return -1;
   else if (uid1 > uid2)
@@ -1377,10 +1446,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 +1481,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;
+}
+