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

[Eric Botcazou <ebotcazou at adacore dot com>]

> This is a quadratic algorithm and as such not ok.  We already have
> aliasing_component_refs_p in tree-ssa-alias.c which is supposed to be
> the non-quadratic replacement.  It's not used via decl_refs_may_alias_p,
> so that may be the thing to fix.

aliasing_component_refs_p isn't powerful enough, it eliminates the quadratic 
aspect by assuming that all offsets are constants, so it misses cases like 
(*p)[i].f1 vs a[j].f2.  Moreover it assumes TBAA and we don't need it here.

I can rewrite nonoverlapping_component_refs_of_decl_p to make it non-quadratic 
and catch the same cases I think, patch attached (without the vect testsuite 
adjustments, but they are still needed).

> nonoverlapping_component_refs_of_decl_p on RTL should go - in fact
> we do call the tree oracle from all its callers so we only ever do redundant
> work (after your proposed patch even more so).

Not clear if the tree oracle can catch the above case with *p and a, but, yes, 
nonoverlapping_component_refs_p should go in the long term.


	* alias.c (nonoverlapping_component_refs_p): Protect again LTO quirk.
	* 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: 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))
 	return !(DECL_BIT_FIELD (fieldx) && DECL_BIT_FIELD (fieldy));
 
       /* The comparison on the current field failed.  If we're accessing
Index: tree-ssa-alias.c
===================================================================
--- tree-ssa-alias.c	(revision 197926)
+++ tree-ssa-alias.c	(working copy)
@@ -719,14 +719,110 @@ 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 you cannot reference several fields
+     at a time (unlike for arrays with slices), unless you're in a union,
+     in which case the return value will be false in any case.  */
+  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;
+
+      /* ??? Pointer inequality is too fragile in the LTO compiler.  */
+      if (field1 != field2 && DECL_NAME (field1) != DECL_NAME (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 +833,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 +1192,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,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);
     }
 }