Re: [patch] Fix ICE during RTL expansion at -O1

[Eric Botcazou <ebotcazou at adacore dot com>]

> Note that looking at the access path _is_ assuming TBAA constraints as
> soon as the base objects are not the same (in the above case '*p' and 'a'
> are not the same and p could alias a in a way that all f1 and f2 overlap).

Right, but here I'm assuming (and asserting) that the base objects are the 
same.

> Index: alias.c
> ===================================================================
> --- alias.c     (revision 197926)
> +++ alias.c     (working copy)
> @@ -2232,8 +2232,11 @@ nonoverlapping_component_refs_p (const_r
> 
>      found:
>        /* If we're left with accessing different fields of a structure, then
> no -        possible overlap, unless they are both bitfields.  */
> -      if (TREE_CODE (typex) == RECORD_TYPE && fieldx != fieldy)
> +        possible overlap, unless they are both bitfields.
> +        ??? Pointer inequality is too fragile in the LTO compiler.  */
> +      if (TREE_CODE (typex) == RECORD_TYPE
> +         && fieldx != fieldy
> +         && DECL_NAME (fieldx) != DECL_NAME (fieldy))
> 
> this, if at all, should go in with a separate patch and a testcase.
> And I think it should _not_ go in.

OK, I can remove the LTO related bits.

> Otoh...
> 
> +      /* ??? 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 = TYPE_MAIN_VARIANT (DECL_CONTEXT (field1));
> +      tree type2 = TYPE_MAIN_VARIANT (DECL_CONTEXT (field2));
> +
> +      if (type1 != type2 || TREE_CODE (type1) != RECORD_TYPE)
> +        goto may_overlap;
> +
> +      /* ??? Pointer inequality is too fragile in the LTO compiler.  */
> +      if (field1 != field2 && DECL_NAME (field1) != DECL_NAME (field2))
> 
> this suggests you are seeing multiple FIELD_DECLs for the same field
> in the _same_ FIELD_DECL chain ...?!  Are you sure this happens with
> GCC 4.8?  There were some fixes in that area in the LTO type merging code.

No, let's drop the LTO related bits for mainline.  But the Fortran related 
bits are necessary, it's the verification you talked about earlier: for a 
COMPONENT_REF

  TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (t, 0)))
    = TYPE_MAIN_VARIANT (DECL_CONTEXT (TREE_OPERAND (t, 1)))

is expected to be always true (but isn't checked as you pointed out).  But the 
Fortran compiler violates it (4.9, gfortran.dg/aliasing_array_result_1.f90) as 
it implements a common block by defining 2 RECORD_TYPEs with 1 field, one for 
each variables, and does an implicit type conversion of TREE_OPERAND (t, 0).

> Index: tree-streamer.c
> ===================================================================
> --- tree-streamer.c     (revision 197926)
> +++ tree-streamer.c     (working copy)
> @@ -267,10 +267,9 @@ record_common_node (struct streamer_tree
>        /* The FIELD_DECLs of structures should be shared, so that every
>          COMPONENT_REF uses the same tree node when referencing a field.
>          Pointer equality between FIELD_DECLs is used by the alias
> -        machinery to compute overlapping memory references (See
> -        nonoverlapping_component_refs_p).  */
> -      tree f;
> -      for (f = TYPE_FIELDS (node); f; f = TREE_CHAIN (f))
> +        machinery to compute overlapping component references (see
> +        nonoverlapping_component_refs_of_decl_p).  */
> +      for (tree f = TYPE_FIELDS (node); f; f = TREE_CHAIN (f))
>         record_common_node (cache, f);
>      }
>  }
> 
> without actually removing nonoverlapping_component_refs_p it still applies
> to both...

Will adjust.

> Can you port the non-quadratic algorithm to the RTL
> nonoverlapping_component_refs_p first?  The core code should exactly
> be the same ... (and shared, and only called once from the RTL oracle).

No, it cannot be ported, the non-quadratic aspect is a consequence of the same 
base object assumption.  It you don't have it, you need to be quadratic to be 
able to deal with variable offsets in this way.

> I don't understand the "reference several fields" comment.  Because I
> can clearly have aggregate copies of RECORD_TYPE.  Can you try
> do elaborate more on why the algorithm should be sufficient to catch
> all cases?

I can, but you need to keep in mind that the base objects are the same.

> You could enhance it to not require
> 
> +  /* We must have the same base DECL.  */
> +  gcc_assert (ref1 == ref2);
> 
> for MEM_REF bases under the same conditions like aliasing_component_refs_p,
> that is if the MEM_REF isn't view-converting.

The code already handles MEM_REF<ADDR_EXPR> though (and checks that the offset 
is zero).  I'm not sure that we need more (but ready to be proved wrong here).

> That said, if the bases are the same DECLs then indeed you do not
> rely on TBAA.  The RTL nonoverlapping_component_refs_p does not
> disable itself properly for pointer based accesses that might be
> view-converted / aliased accesses (a simple testcase with ref-all
> pointers properly offsetted to alias two adjacent fields may be enough to
> show that).
> 
> Also with your patch enhanced like I suggest we should be able to
> remove aliasing_component_refs_p as well, no?

My revised patch is only a safe, non-quadratic, non-TBAA based disambiguation 
for references based on the same DECL, so it's a full replacement neither for 
aliasing_component_refs_p nor for nonoverlapping_component_refs_p.

Thanks for the review.  Updated patch attached.


        * tree-ssa-alias.c (nonoverlapping_component_refs_of_decl_p): New.
        (decl_refs_may_alias_p): Add REF1 and REF2 parameters.
        Use nonoverlapping_component_refs_of_decl_p to disambiguate component
        references.
        (refs_may_alias_p_1): Adjust call to decl_refs_may_alias_p.
        * tree-streamer.c (record_common_node): Adjust reference in comment.


-- 
Eric Botcazou

Index: tree-ssa-alias.c
===================================================================
--- tree-ssa-alias.c	(revision 197926)
+++ tree-ssa-alias.c	(working copy)
@@ -719,14 +719,112 @@ aliasing_component_refs_p (tree ref1,
   return false;
 }
 
+/* Return true if we can determine that component references REF1 and REF2,
+   that are within a common DECL, cannot overlap.  */
+
+static bool
+nonoverlapping_component_refs_of_decl_p (tree ref1, tree ref2)
+{
+  vec<tree, va_stack> component_refs1;
+  vec<tree, va_stack> component_refs2;
+
+  vec_stack_alloc (tree, component_refs1, 16);
+  vec_stack_alloc (tree, component_refs2, 16);
+
+  /* Create the stack of handled components for REF1.  */
+  while (handled_component_p (ref1))
+    {
+      component_refs1.safe_push (ref1);
+      ref1 = TREE_OPERAND (ref1, 0);
+    }
+  if (TREE_CODE (ref1) == MEM_REF)
+    {
+      if (!integer_zerop (TREE_OPERAND (ref1, 1)))
+	goto may_overlap;
+      ref1 = TREE_OPERAND (TREE_OPERAND (ref1, 0), 0);
+    }
+
+  /* Create the stack of handled components for REF2.  */
+  while (handled_component_p (ref2))
+    {
+      component_refs2.safe_push (ref2);
+      ref2 = TREE_OPERAND (ref2, 0);
+    }
+  if (TREE_CODE (ref2) == MEM_REF)
+    {
+      if (!integer_zerop (TREE_OPERAND (ref2, 1)))
+	goto may_overlap;
+      ref2 = TREE_OPERAND (TREE_OPERAND (ref2, 0), 0);
+    }
+
+  /* We must have the same base DECL.  */
+  gcc_assert (ref1 == ref2);
+
+  /* Pop the stacks in parallel and examine the COMPONENT_REFs of the same
+     rank.  This is sufficient because we start from the same DECL and you
+     cannot reference several fields at a time with COMPONENT_REFs (unlike
+     with ARRAY_RANGE_REFs for arrays) so you always need the same number
+     of them to access a sub-component, unless you're in a union, in which
+     case the return value will precisely be false.  */
+  while (true)
+    {
+      do
+	{
+	  if (component_refs1.is_empty ())
+	    goto may_overlap;
+	  ref1 = component_refs1.pop ();
+	}
+      while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1, 0))));
+
+      do
+	{
+	  if (component_refs2.is_empty ())
+	     goto may_overlap;
+	  ref2 = component_refs2.pop ();
+	}
+      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)
+	goto may_overlap;
+
+      tree field1 = TREE_OPERAND (ref1, 1);
+      tree field2 = TREE_OPERAND (ref2, 1);
+
+      /* ??? 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 = TYPE_MAIN_VARIANT (DECL_CONTEXT (field1));
+      tree type2 = TYPE_MAIN_VARIANT (DECL_CONTEXT (field2));
+
+      if (type1 != type2 || TREE_CODE (type1) != RECORD_TYPE)
+	 goto may_overlap;
+
+      /* Different fields of the same RECORD_TYPE cannot overlap.  */
+      if (field1 != field2)
+	{
+	  component_refs1.release ();
+	  component_refs2.release ();
+	  return true;
+	}
+    }
+
+may_overlap:
+  component_refs1.release ();
+  component_refs2.release ();
+  return false;
+}
+
 /* Return true if two memory references based on the variables BASE1
    and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
-   [OFFSET2, OFFSET2 + MAX_SIZE2) may alias.  */
+   [OFFSET2, OFFSET2 + MAX_SIZE2) may alias.  REF1 and REF2
+   if non-NULL are the complete memory reference trees.  */
 
 static bool
-decl_refs_may_alias_p (tree base1,
+decl_refs_may_alias_p (tree ref1, tree base1,
 		       HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
-		       tree base2,
+		       tree ref2, tree base2,
 		       HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2)
 {
   gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
@@ -737,7 +835,17 @@ decl_refs_may_alias_p (tree base1,
 
   /* If both references are based on the same variable, they cannot alias if
      the accesses do not overlap.  */
-  return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
+  if (!ranges_overlap_p (offset1, max_size1, offset2, max_size2))
+    return false;
+
+  /* For components with variable position, the above test isn't sufficient,
+     so we disambiguate component references manually.  */
+  if (ref1 && ref2
+      && handled_component_p (ref1) && handled_component_p (ref2)
+      && nonoverlapping_component_refs_of_decl_p (ref1, ref2))
+    return false;
+
+  return true;     
 }
 
 /* Return true if an indirect reference based on *PTR1 constrained
@@ -1086,8 +1194,8 @@ refs_may_alias_p_1 (ao_ref *ref1, ao_ref
   var1_p = DECL_P (base1);
   var2_p = DECL_P (base2);
   if (var1_p && var2_p)
-    return decl_refs_may_alias_p (base1, offset1, max_size1,
-				  base2, offset2, max_size2);
+    return decl_refs_may_alias_p (ref1->ref, base1, offset1, max_size1,
+				  ref2->ref, base2, offset2, max_size2);
 
   ind1_p = (TREE_CODE (base1) == MEM_REF
 	    || TREE_CODE (base1) == TARGET_MEM_REF);
Index: tree-streamer.c
===================================================================
--- tree-streamer.c	(revision 197926)
+++ tree-streamer.c	(working copy)
@@ -267,10 +267,10 @@ record_common_node (struct streamer_tree
       /* The FIELD_DECLs of structures should be shared, so that every
 	 COMPONENT_REF uses the same tree node when referencing a field.
 	 Pointer equality between FIELD_DECLs is used by the alias
-	 machinery to compute overlapping memory references (See
-	 nonoverlapping_component_refs_p).  */
-      tree f;
-      for (f = TYPE_FIELDS (node); f; f = TREE_CHAIN (f))
+	 machinery to compute overlapping component references (see
+	 nonoverlapping_component_refs_p and
+	 nonoverlapping_component_refs_of_decl_p).  */
+      for (tree f = TYPE_FIELDS (node); f; f = TREE_CHAIN (f))
 	record_common_node (cache, f);
     }
 }