Message ID | 13944748.gGd7vrWRPJ@polaris |
---|---|
State | New |
Headers | show |
On Tue, Apr 16, 2013 at 11:55 AM, Eric Botcazou <ebotcazou@adacore.com> wrote: >> 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. Hmm, ok. Sad :/ > Thanks for the review. Updated patch attached. + if (type1 != type2 || TREE_CODE (type1) != RECORD_TYPE) + goto may_overlap; ick, can TREE_CODE (type1) != RECORD_TYPE happen as well here? Please add a comment similar to the Fortran ??? above. Can you please also add at least one testcase as gcc.dg/tree-ssa/ssa-fre-??.c that tests the functionality of this and that wasn't handled before? I suppose it would be sth like struct S { int i; int j; }; struct U { struct S a[10]; } u; u.a[n].i= i; u.a[n].j = j; return u.a[n].i; where we miss to CSE the load from u.a[n].i. Otherwise the patch is ok. Thanks! Richard.
> + if (type1 != type2 || TREE_CODE (type1) != RECORD_TYPE) > + goto may_overlap; > > ick, can TREE_CODE (type1) != RECORD_TYPE happen as well here? > Please add a comment similar to the Fortran ??? above. It can happen because we stop at unions (and qualified unions) and for them we cannot disambiguate based on the fields. I'll add a regular comment. > Can you please also add at least one testcase as > gcc.dg/tree-ssa/ssa-fre-??.c that tests the functionality of this and that > wasn't handled before? I suppose it would be sth like > > struct S { int i; int j; }; > struct U > { > struct S a[10]; > } u; > > u.a[n].i= i; > u.a[n].j = j; > return u.a[n].i; > > where we miss to CSE the load from u.a[n].i. Yes, the patch does eliminate the redundant load in .fre1: u.a[n_2(D)].i = i_3(D); u.a[n_2(D)].j = j_5(D); _7 = u.a[n_2(D)].i; return _7; becomes: u.a[n_2(D)].i = i_3(D); u.a[n_2(D)].j = j_5(D); _7 = i_3(D); return _7; > Otherwise the patch is ok. Thanks.
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); } }