> 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 BotcazouIndex: 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);
}
}
