On Mon, Apr 15, 2013 at 11:47 AM, Richard Biener
<richard.guent...@gmail.com> wrote:
> On Sun, Apr 14, 2013 at 9:46 AM, Eric Botcazou <ebotca...@adacore.com> wrote:
>>> 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.
>
> 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).
>
>> 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.
>
> 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. Instead, as the case passes
>
> if (typex == typey)
> goto found;
>
> earlier you should assert that DECL_CONTEXT (fieldx) == DECL_CONTEXT
> (fieldy) == typex == typey here. Note that fails of this test are
> expected even in the
> non-LTO case because I cannot find any IL verification that would verify
> that for a COMPONENT_REF TREE_TYPE (TREE_OPERAND (cr, 0))
> == DECL_CONTEXT (TREE_OPERAND (cr, 1)) (due to sharing of the FIELD_DECL
> chain between different type variants the check will fail for all
> non-main-variants
> I think, so refining it to look at the main variant is probably advised).
>
> 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.
>
> 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...
>
>
> 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).
>
> + /* 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)
>
> 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?
>
> 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.
>
> 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).
Testcase:
struct S {
int i;
int j;
};
struct U {
struct S s;
} __attribute__((may_alias));
int __attribute__((noinline,noclone))
foo (struct U *p, struct U *q)
{
int i;
q->s.j = 1;
i = p->s.i;
return i;
}
int main()
{
int *p = (int *)__builtin_alloca (sizeof (int) * 3);
p[1] = 0;
if (foo ((struct U *)(p + 1), (struct U *)p) != 1)
__builtin_abort ();
return 0;
}
fails on x86_64 with -O2 -fschedule-insns because scheduling exchanges
the store and the load.
Richard.
>
> Also with your patch enhanced like I suggest we should be able to
> remove aliasing_component_refs_p as well, no?
>
> Thanks,
> Richard.
>
>>
>> --
>> Eric Botcazou
