Make nonoverlapping_component_refs work with duplicated main variants

Make nonoverlapping_component_refs work with duplicated main variants

[Jan Hubicka]

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;
+}
+

Re: Make nonoverlapping_component_refs work with duplicated main variants

[Richard Biener]

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

On Mon, 8 Jul 2019, Jan Hubicka wrote:

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

completely disjoint?  I guess

  Return 0 if accesses to FIELD1 and FIELD2 are possibly overlapping.

is better matching actual behavior.  Likewise mentioning 'accesses'
in the first because of the bitfield treatment (the fields may
be non-overlapping but actual accesses might be).

> +   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.  */

Merge this and the previous comment please, it's all for the 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;

This is similar as the DECL_BIT_FIELD_REPRESENTATIVE check so why
return -1 instead of 0?

> +      return 1;
> +    }

Unconditional return above so avoid the else {} below but put
a comment here like

  /* Resort to slower overlap checking by looking at the actual
     (possibly non-constant) offsets and sizes.  */

> +  else 
> +    {
> +      if (operand_equal_p (DECL_FIELD_BIT_OFFSET (field1),
> +			   DECL_FIELD_BIT_OFFSET (field2), 0))
> +	return 0;

I think this is overly pessimistic - the offset of a field
is DECL_FIELD_OFFSET + DECL_FIELD_BIT_OFFSET (the latter is
only up to DECL_OFFSET_ALIGN, the rest of the constant
offset spills into DECL_FIELD_OFFSET).  Which also means ...

> +
> +      /* 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))

this is technically wrong in case we had DECL_FIELD_OFFSETs 4 and 8
and DECL_FIELD_BIT_OFFSETs 32 and 0.

So you have to compute the combined offsets first.

> +	return -1;

I think it may make sense to return -1 if any of the !poly_int_tree_p
tests fire, but otherwise?  I'm not actually sure what -1 vs. 0
means here - is 0 a must exactly overlap and -1 is a may overlap
somehow?

> +      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;
> +}
> +
> 

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

Re: Make nonoverlapping_component_refs work with duplicated main variants

[Jan Hubicka]

> > +/* 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.
> 
> completely disjoint?  I guess
> 
>   Return 0 if accesses to FIELD1 and FIELD2 are possibly overlapping.
> 
> is better matching actual behavior.  Likewise mentioning 'accesses'
> in the first because of the bitfield treatment (the fields may
> be non-overlapping but actual accesses might be).

I was trying to describe difference between 0 and -1.
We return 0 when we fully structurally matched the path and we know it
is same. -1 means that we arrived to somehting we can not handle (union,
mismatched offsets) and it would make sense to try disambiguating
further.

Currently it means that in addition to
nonoverlapping_component_refs_since_match_p we also do
nonoverlapping_component_refs_p which has some chance to recover from
the mismatched REF pair, match the types later on path and still
disambiguate.  It seem to happen very rarely though.
> 
> > +      /* 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;
> 
> This is similar as the DECL_BIT_FIELD_REPRESENTATIVE check so why
> return -1 instead of 0?

Well, my plan is to put this test before ref_and_offset which still have
chace to suceed if fields are far away. But i am happy to return 0 here
and mess with that later.
> > +  else 
> > +    {
> > +      if (operand_equal_p (DECL_FIELD_BIT_OFFSET (field1),
> > +			   DECL_FIELD_BIT_OFFSET (field2), 0))
> > +	return 0;
> 
> I think this is overly pessimistic - the offset of a field
> is DECL_FIELD_OFFSET + DECL_FIELD_BIT_OFFSET (the latter is
> only up to DECL_OFFSET_ALIGN, the rest of the constant
> offset spills into DECL_FIELD_OFFSET).  Which also means ...
> 
> > +
> > +      /* 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))
> 
> this is technically wrong in case we had DECL_FIELD_OFFSETs 4 and 8
> and DECL_FIELD_BIT_OFFSETs 32 and 0.
> 
> So you have to compute the combined offsets first.

OK, I guess I can take look at the get_base_ref_and_offset there. Thanks
for pointing this out.
> 
> > +	return -1;
> 
> I think it may make sense to return -1 if any of the !poly_int_tree_p
> tests fire, but otherwise?  I'm not actually sure what -1 vs. 0
> means here - is 0 a must exactly overlap and -1 is a may overlap
> somehow?

Well, we have two fields that overlap partly from two different types
in >nonoverlapping_component_refs_since_match_p  so it can not
continue walking (since the main invariant is broken)
we may still suceed with the nonoverlaping_component_refs 

Thanks, I will update the patch.
Honza

Re: Make nonoverlapping_component_refs work with duplicated main variants

[Jan Hubicka]

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;
+}
+

Re: Make nonoverlapping_component_refs work with duplicated main variants

[Richard Biener]

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

Re: Make nonoverlapping_component_refs work with duplicated main variants

[Jan Hubicka]

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

OK, i tought that if I put SVE into structures, we may end up with
these.
> > +      /* 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).

OK.
> 
> > +      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.

tree_int_cst_equal will return false if offsets are not INTEGER_CST.
I was not sure if I can safely use operand_equal_p.  What happens for
fields with variable offsets when I inline two copies of same function
which takes size as parameter and make the size different? Will I get
here proper SSA name so operand_equal_p will work?

If so, I still see no point for fast-path for DECL_OFFSET_ALIGN. In many
cases BIT_OFFSET will be just 0, so even if offset alignments are
different we are likely going to hit this fast path avoiding parsing
trees later.
> 
> > +      /* 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?

Because the types I am comparing may not have same canonical types.

nonoverlapping_component_refs_since_match_p is called when we prove that
base pointers are the same (even with -fno-strict-aliasing).  In such
cases the access paths may be based on completely different types. The
point of nonoverlapping_component_refs_since_match_p is to match them as
far as possible when they are semantically equivalent in hope to get
non-overlapping refs in the last step.

This is stronger than the get_base_ref_and_extend based check in
presence of non-constant ARRAY_REFs.

Honza

Re: Make nonoverlapping_component_refs work with duplicated main variants

[Richard Biener]

On Tue, 9 Jul 2019, Jan Hubicka wrote:

> > For consistency yes I guess but IIRC they cannot really appear in 
> > FIELD_DECLs.
> 
> OK, i tought that if I put SVE into structures, we may end up with
> these.
> > > +      /* 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).
> 
> OK.
> > 
> > > +      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.
> 
> tree_int_cst_equal will return false if offsets are not INTEGER_CST.
> I was not sure if I can safely use operand_equal_p.  What happens for
> fields with variable offsets when I inline two copies of same function
> which takes size as parameter and make the size different? Will I get
> here proper SSA name so operand_equal_p will work?

No, you get a DECL, but yes, I think operand_equal_p will work.
Consider two _same_ variable sizes, you'll not see that you
have to return zero then?  But yes, in case you have types
globbed to the canonical type (but not FIELD_DECLs) then
you'll get false !operand_equal_p as well.

The question is really what is desired here.  If you want/need precision
for non-constant offsets then you have to look at the COMPONENT_REF
trees because the relevant offset (SSA name) is only there
(in TREE_OPERAND (component_ref, 2)).

If you want to give up for non-constants and can do that without
correctness issue then fine (but Ada probably would like to have
it - so also never forget to include Ada in testing here ;))

> If so, I still see no point for fast-path for DECL_OFFSET_ALIGN. In many
> cases BIT_OFFSET will be just 0, so even if offset alignments are
> different we are likely going to hit this fast path avoiding parsing
> trees later.

Ok.

> > 
> > > +      /* 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?
> 
> Because the types I am comparing may not have same canonical types.
> 
> nonoverlapping_component_refs_since_match_p is called when we prove that
> base pointers are the same (even with -fno-strict-aliasing).  In such
> cases the access paths may be based on completely different types. The
> point of nonoverlapping_component_refs_since_match_p is to match them as
> far as possible when they are semantically equivalent in hope to get
> non-overlapping refs in the last step.

Oh, OK ... a bit more explaining commentary might be nice
(at the top of the function - basically what the input
constraints to the FIELD_DECLs are).

Btw, the offsets in FIELD_DECLs are relative to DECL_CONTEXT so
comparing when DECL_CONTEXT are not related at all doesn't make
any sense.  Well, unless we know _those_ are at the same offset,
so - the constraint for the FIELD_DECLs we compare is that
the containing structure type object instances live at the same
address?

Richard.

Re: Make nonoverlapping_component_refs work with duplicated main variants

[Jan Hubicka]

> > tree_int_cst_equal will return false if offsets are not INTEGER_CST.
> > I was not sure if I can safely use operand_equal_p.  What happens for
> > fields with variable offsets when I inline two copies of same function
> > which takes size as parameter and make the size different? Will I get
> > here proper SSA name so operand_equal_p will work?
> 
> No, you get a DECL, but yes, I think operand_equal_p will work.
> Consider two _same_ variable sizes, you'll not see that you
> have to return zero then?  But yes, in case you have types
> globbed to the canonical type (but not FIELD_DECLs) then
> you'll get false !operand_equal_p as well.
> 
> The question is really what is desired here.  If you want/need precision
> for non-constant offsets then you have to look at the COMPONENT_REF
> trees because the relevant offset (SSA name) is only there
> (in TREE_OPERAND (component_ref, 2)).
> 
> If you want to give up for non-constants and can do that without
> correctness issue then fine (but Ada probably would like to have
> it - so also never forget to include Ada in testing here ;))

I would like to have precision here. so perhaps as incremental change I
can
 1) reorganize callers to pass refs rather than just field_decls
 2) check if TREE_OPERAND (component_ref, 2) is non-NULL in both case
    a) if so do operand_equal_p on them and return 0 on match
    b) if there is no match see if I have same canonical types and
       return 1 then
    c) return -1 otherwise
 3) continue with parsing FIELD_DECLS we work on now.
> 
> Oh, OK ... a bit more explaining commentary might be nice
> (at the top of the function - basically what the input
> constraints to the FIELD_DECLs are).

OK, will try to improve comments (though i tried to be relatively
thorough).

Honza
> 
> Btw, the offsets in FIELD_DECLs are relative to DECL_CONTEXT so
> comparing when DECL_CONTEXT are not related at all doesn't make
> any sense.  Well, unless we know _those_ are at the same offset,
> so - the constraint for the FIELD_DECLs we compare is that
> the containing structure type object instances live at the same
> address?
> 
> Richard.

Re: Make nonoverlapping_component_refs work with duplicated main variants

[Richard Biener]

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

On Tue, 9 Jul 2019, Jan Hubicka wrote:

> > > tree_int_cst_equal will return false if offsets are not INTEGER_CST.
> > > I was not sure if I can safely use operand_equal_p.  What happens for
> > > fields with variable offsets when I inline two copies of same function
> > > which takes size as parameter and make the size different? Will I get
> > > here proper SSA name so operand_equal_p will work?
> > 
> > No, you get a DECL, but yes, I think operand_equal_p will work.
> > Consider two _same_ variable sizes, you'll not see that you
> > have to return zero then?  But yes, in case you have types
> > globbed to the canonical type (but not FIELD_DECLs) then
> > you'll get false !operand_equal_p as well.
> > 
> > The question is really what is desired here.  If you want/need precision
> > for non-constant offsets then you have to look at the COMPONENT_REF
> > trees because the relevant offset (SSA name) is only there
> > (in TREE_OPERAND (component_ref, 2)).
> > 
> > If you want to give up for non-constants and can do that without
> > correctness issue then fine (but Ada probably would like to have
> > it - so also never forget to include Ada in testing here ;))
> 
> I would like to have precision here. so perhaps as incremental change I
> can
>  1) reorganize callers to pass refs rather than just field_decls
>  2) check if TREE_OPERAND (component_ref, 2) is non-NULL in both case
>     a) if so do operand_equal_p on them and return 0 on match
>     b) if there is no match see if I have same canonical types and
>        return 1 then
>     c) return -1 otherwise

makes sense

>  3) continue with parsing FIELD_DECLS we work on now.
> > 
> > Oh, OK ... a bit more explaining commentary might be nice
> > (at the top of the function - basically what the input
> > constraints to the FIELD_DECLs are).
> 
> OK, will try to improve comments (though i tried to be relatively
> thorough).
> 
> Honza
> > 
> > Btw, the offsets in FIELD_DECLs are relative to DECL_CONTEXT so
> > comparing when DECL_CONTEXT are not related at all doesn't make
> > any sense.  Well, unless we know _those_ are at the same offset,
> > so - the constraint for the FIELD_DECLs we compare is that
> > the containing structure type object instances live at the same
> > address?
> > 
> > Richard.
> 

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

Re: Make nonoverlapping_component_refs work with duplicated main variants

[Jan Hubicka]

Hi,
this is updated variant I am testing.
It documents better how function works and streamlines the checks.

OK assuming it passes the tests?

Honza

Index: tree-ssa-alias.c
===================================================================
--- tree-ssa-alias.c	(revision 273193)
+++ tree-ssa-alias.c	(working copy)
@@ -1128,6 +1128,91 @@ aliasing_component_refs_p (tree ref1,
   return false;
 }
 
+/* FIELD1 and FIELD2 are two fields of component refs.  We assume
+   that bases of both component refs are
+     (*) are either equivalent or they point to different objects.
+   We do not assume that FIELD1 and FIELD2 are of same type.
+
+   Return 0 if FIELD1 and FIELD2 satisfy (*).
+   This is the case when their offsets are the same.
+
+   Return 1 if FIELD1 and FIELD2 are non-overlapping.
+
+   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.
+
+   Note that this function is used even with -fno-strict-aliasing
+   and makes use of no TBAA assumptions.  */
+
+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.  */
+  tree type1 = DECL_CONTEXT (field1);
+  tree type2 = DECL_CONTEXT (field2);
+
+  if (DECL_BIT_FIELD_REPRESENTATIVE (field1))
+    field1 = DECL_BIT_FIELD_REPRESENTATIVE (field1);
+  if (DECL_BIT_FIELD_REPRESENTATIVE (field2))
+    field2 = DECL_BIT_FIELD_REPRESENTATIVE (field1);
+
+  /* ??? Bitfields can overlap at RTL level so punt on them.
+     FIXME: RTL expansion should be fixed by adjusting the access path
+     when producing MEM_ATTRs for MEMs which are wider than 
+     the bitfields similarly as done in set_mem_attrs_minus_bitpos.  */
+  if (DECL_BIT_FIELD (field1) && DECL_BIT_FIELD (field2))
+    return -1;
+
+  /* Assume that different FIELD_DECLs never overlap within a RECORD_TYPE.  */
+  if (type1 == type2 && TREE_CODE (type1) == RECORD_TYPE)
+    return field1 != field2;
+
+  /* In common case the offsets and bit offsets will be the same.
+     However if frontends do not agree on the alignment, they may be
+     different even if they actually represent same address.
+     Try the common case first and if that fails calcualte the
+     actual bit offset.  */
+  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;
+
+  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))
+    {
+      offset1 = (offset1 << LOG2_BITS_PER_UNIT) + bit_offset1;
+      offset2 = (offset2 << LOG2_BITS_PER_UNIT) + bit_offset2;
+
+      if (known_eq (offset1, offset2))
+	return 0;
+
+      poly_uint64 size1, size2;
+
+      if (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;
+    }
+  /* 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 +1309,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 +1319,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 +1333,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 +1352,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 +1381,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 +1407,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 +1476,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 +1511,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 ())

Re: Make nonoverlapping_component_refs work with duplicated main variants

[Richard Biener]

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

On Tue, 9 Jul 2019, Jan Hubicka wrote:

> Hi,
> this is updated variant I am testing.
> It documents better how function works and streamlines the checks.
> 
> OK assuming it passes the tests?
> 
> Honza
> 
> Index: tree-ssa-alias.c
> ===================================================================
> --- tree-ssa-alias.c	(revision 273193)
> +++ tree-ssa-alias.c	(working copy)
> @@ -1128,6 +1128,91 @@ aliasing_component_refs_p (tree ref1,
>    return false;
>  }
>  
> +/* FIELD1 and FIELD2 are two fields of component refs.  We assume
> +   that bases of both component refs are
> +     (*) are either equivalent or they point to different objects.

are either equivalent(*) or not overlapping

> +   We do not assume that FIELD1 and FIELD2 are of same type.

that the containers of FIELD1 and FIELD2 are of the same type?

> +
> +   Return 0 if FIELD1 and FIELD2 satisfy (*).
> +   This is the case when their offsets are the same.

Hmm, so when the offsets are the same then the bases are equivalent?
I think you want to say

     Return 0 if in case the component refs satisfy (*) we
     know FIELD1 and FIELD2 are overlapping exactly.

> +   Return 1 if FIELD1 and FIELD2 are non-overlapping.
> +
> +   Return -1 otherwise.
> +
> +   Main difference between 0 and -1 is to let
> +   nonoverlapping_component_refs_since_match_p discover the semnatically

semantically

otherwise looks good now.

Thanks,
Richard.

> +   equivalent part of the access path.
> +
> +   Note that this function is used even with -fno-strict-aliasing
> +   and makes use of no TBAA assumptions.  */
> +
> +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.  */
> +  tree type1 = DECL_CONTEXT (field1);
> +  tree type2 = DECL_CONTEXT (field2);
> +
> +  if (DECL_BIT_FIELD_REPRESENTATIVE (field1))
> +    field1 = DECL_BIT_FIELD_REPRESENTATIVE (field1);
> +  if (DECL_BIT_FIELD_REPRESENTATIVE (field2))
> +    field2 = DECL_BIT_FIELD_REPRESENTATIVE (field1);
> +
> +  /* ??? Bitfields can overlap at RTL level so punt on them.
> +     FIXME: RTL expansion should be fixed by adjusting the access path
> +     when producing MEM_ATTRs for MEMs which are wider than 
> +     the bitfields similarly as done in set_mem_attrs_minus_bitpos.  */
> +  if (DECL_BIT_FIELD (field1) && DECL_BIT_FIELD (field2))
> +    return -1;
> +
> +  /* Assume that different FIELD_DECLs never overlap within a RECORD_TYPE.  */
> +  if (type1 == type2 && TREE_CODE (type1) == RECORD_TYPE)
> +    return field1 != field2;
> +
> +  /* In common case the offsets and bit offsets will be the same.
> +     However if frontends do not agree on the alignment, they may be
> +     different even if they actually represent same address.
> +     Try the common case first and if that fails calcualte the
> +     actual bit offset.  */
> +  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;
> +
> +  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))
> +    {
> +      offset1 = (offset1 << LOG2_BITS_PER_UNIT) + bit_offset1;
> +      offset2 = (offset2 << LOG2_BITS_PER_UNIT) + bit_offset2;
> +
> +      if (known_eq (offset1, offset2))
> +	return 0;
> +
> +      poly_uint64 size1, size2;
> +
> +      if (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;
> +    }
> +  /* 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 +1309,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 +1319,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 +1333,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 +1352,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 +1381,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 +1407,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 +1476,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 +1511,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 ())
> 

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

Re: Make nonoverlapping_component_refs work with duplicated main variants

[Bernhard Reutner-Fischer]

On 9 July 2019 15:37:30 CEST, Richard Biener <rguenther@suse.de> wrote:
>On Tue, 9 Jul 2019, Jan Hubicka wrote:
>
>> Hi,
>> this is updated variant I am testing.
>> It documents better how function works and streamlines the checks.
>> 
>> OK assuming it passes the tests?
>> 
>> Honza
>> 
>> Index: tree-ssa-alias.c
>> ===================================================================
>> --- tree-ssa-alias.c	(revision 273193)
>> +++ tree-ssa-alias.c	(working copy)
>> @@ -1128,6 +1128,91 @@ aliasing_component_refs_p (tree ref1,
>>    return false;
>>  }
>>  
>> +/* FIELD1 and FIELD2 are two fields of component refs.  We assume
>> +   that bases of both component refs are
>> +     (*) are either equivalent or they point to different objects.
>
>are either equivalent(*) or not overlapping
>
>> +   We do not assume that FIELD1 and FIELD2 are of same type.
>
>that the containers of FIELD1 and FIELD2 are of the same type?
>
>> +
>> +   Return 0 if FIELD1 and FIELD2 satisfy (*).
>> +   This is the case when their offsets are the same.
>
>Hmm, so when the offsets are the same then the bases are equivalent?
>I think you want to say
>
>     Return 0 if in case the component refs satisfy (*) we
>     know FIELD1 and FIELD2 are overlapping exactly.
>
>> +   Return 1 if FIELD1 and FIELD2 are non-overlapping.
>> +
>> +   Return -1 otherwise.
>> +
>> +   Main difference between 0 and -1 is to let
>> +   nonoverlapping_component_refs_since_match_p discover the
>semnatically
>
>semantically
>
>otherwise looks good now.
>
>Thanks,
>Richard.
>
>> +   equivalent part of the access path.
>> +
>> +   Note that this function is used even with -fno-strict-aliasing
>> +   and makes use of no TBAA assumptions.  */
>> +
>> +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.  */
>> +  tree type1 = DECL_CONTEXT (field1);
>> +  tree type2 = DECL_CONTEXT (field2);
>> +
>> +  if (DECL_BIT_FIELD_REPRESENTATIVE (field1))
>> +    field1 = DECL_BIT_FIELD_REPRESENTATIVE (field1);
>> +  if (DECL_BIT_FIELD_REPRESENTATIVE (field2))
>> +    field2 = DECL_BIT_FIELD_REPRESENTATIVE (field1);

Typo: s/field1/field2/

>> +
>> +  /* ??? Bitfields can overlap at RTL level so punt on them.
>> +     FIXME: RTL expansion should be fixed by adjusting the access
>path
>> +     when producing MEM_ATTRs for MEMs which are wider than 
>> +     the bitfields similarly as done in set_mem_attrs_minus_bitpos. 
>*/
>> +  if (DECL_BIT_FIELD (field1) && DECL_BIT_FIELD (field2))
>> +    return -1;

That's a pity.
thanks,

Re: Make nonoverlapping_component_refs work with duplicated main variants

[Rainer Orth]

Hi Jan,

> 	* g++.dg/lto/alias-3_0.C: New file.
> 	* g++.dg/lto/alias-3_1.c: New file.

the new test has a couple of problems: DejaGnu warns everywhere:

WARNING: lto.exp does not support dg-lto-do in secondary source files
WARNING: lto.exp does not support dg-lto-options in secondary source files

This would have been prominent in either mail-report.log or the runtest
output.

Besides, the test FAILs in the same way as its companions lto/alias-[12]
on Solaris (PRs ipa/90720 and lto/91028).  Your fix for the latter two
didn't change anything, btw., neither on Solaris nor on Linux/x86_64
with -fno-use-linker-plugin.

	Rainer

-- 
-----------------------------------------------------------------------------
Rainer Orth, Center for Biotechnology, Bielefeld University

Re: Make nonoverlapping_component_refs work with duplicated main variants

[Jan Hubicka]

> Hi Jan,
> 
> > 	* g++.dg/lto/alias-3_0.C: New file.
> > 	* g++.dg/lto/alias-3_1.c: New file.
> 
> the new test has a couple of problems: DejaGnu warns everywhere:
> 
> WARNING: lto.exp does not support dg-lto-do in secondary source files
> WARNING: lto.exp does not support dg-lto-options in secondary source files
> 
> This would have been prominent in either mail-report.log or the runtest
> output.
> 
> Besides, the test FAILs in the same way as its companions lto/alias-[12]
> on Solaris (PRs ipa/90720 and lto/91028).  Your fix for the latter two
> didn't change anything, btw., neither on Solaris nor on Linux/x86_64
> with -fno-use-linker-plugin.
Hi,
sorry for the noise.  This patch fixes -fno-use-linker-plugin for me and
also removes the extra dg-do I forgot in alias_3-1.c

	* alias-1_0.C: Use -O3.
	* alias-2_0.C: Use -O3.
	* alias-3_0.C: Add loop to enable inlining with -fno-use-linker-plugin.
	* alias-3_1.C: Remove dg-lto-do and dg-lto-options.
Index: g++.dg/lto/alias-1_0.C
===================================================================
--- g++.dg/lto/alias-1_0.C	(revision 273478)
+++ g++.dg/lto/alias-1_0.C	(working copy)
@@ -1,5 +1,5 @@
 /* { dg-lto-do run } */
-/* { dg-lto-options { { -O2 -flto } } } */
+/* { dg-lto-options { { -O3 -flto } } } */
 
 /* With LTO we consider all pointers to incomplete types to be possibly
    aliasing.  This makes *bptr to alias with aptr.
Index: g++.dg/lto/alias-2_0.C
===================================================================
--- g++.dg/lto/alias-2_0.C	(revision 273478)
+++ g++.dg/lto/alias-2_0.C	(working copy)
@@ -1,5 +1,5 @@
 /* { dg-lto-do run } */
-/* { dg-lto-options { { -O2 -flto } } } */
+/* { dg-lto-options { { -O3 -flto } } } */
 
 /* With LTO we consider all pointers to incomplete types to be possibly
    aliasing.  This makes *bptr to alias with aptr.
Index: g++.dg/lto/alias-3_0.C
===================================================================
--- g++.dg/lto/alias-3_0.C	(revision 273478)
+++ g++.dg/lto/alias-3_0.C	(working copy)
@@ -14,13 +14,15 @@ __attribute__ ((used)) struct b b, *bptr
 __attribute__ ((used)) int i,j;
 
 extern "C" void inline_me_late (void);
+int n=1;
 
 int
 main (void)
 {
   int jj=j;
   bptr2->a[jj].bar = 0;
-  inline_me_late ();
+  for (int i=0; i<n; i++)
+    inline_me_late ();
   if (!__builtin_constant_p (bptr2->a[jj].bar == 0))
     __builtin_abort ();
   return 0;
Index: g++.dg/lto/alias-3_1.c
===================================================================
--- g++.dg/lto/alias-3_1.c	(revision 273478)
+++ g++.dg/lto/alias-3_1.c	(working copy)
@@ -1,5 +1,3 @@
-/* { dg-lto-do run } */
-/* { dg-lto-options { { -O3 -flto -fno-early-inlining } } } */
 struct a
 {
   int foo,bar;

Re: Make nonoverlapping_component_refs work with duplicated main variants

[Rainer Orth]

Hi Jan,

>> Hi Jan,
>> 
>> > 	* g++.dg/lto/alias-3_0.C: New file.
>> > 	* g++.dg/lto/alias-3_1.c: New file.
>> 
>> the new test has a couple of problems: DejaGnu warns everywhere:
>> 
>> WARNING: lto.exp does not support dg-lto-do in secondary source files
>> WARNING: lto.exp does not support dg-lto-options in secondary source files
>> 
>> This would have been prominent in either mail-report.log or the runtest
>> output.
>> 
>> Besides, the test FAILs in the same way as its companions lto/alias-[12]
>> on Solaris (PRs ipa/90720 and lto/91028).  Your fix for the latter two
>> didn't change anything, btw., neither on Solaris nor on Linux/x86_64
>> with -fno-use-linker-plugin.
> Hi,
> sorry for the noise.  This patch fixes -fno-use-linker-plugin for me and
> also removes the extra dg-do I forgot in alias_3-1.c

works for me, too, on both sparc-sun-solaris2.11 and
i386-pc-solaris2.11.

Thanks.

	Rainer

-- 
-----------------------------------------------------------------------------
Rainer Orth, Center for Biotechnology, Bielefeld University