| Message ID | 20151122230025.GA85269@kam.mff.cuni.cz |
|---|---|
| State | New |
| Headers | show |
> + tree t = TREE_TYPE (field); > + if (in_lto_p) > + { > + /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their > + element type and that type has to be normalized to void *, > + too, in the case it is a pointer. */ > + while ((TREE_CODE (t) == ARRAY_TYPE > + && (!COMPLETE_TYPE_P (t) > + || TYPE_NONALIASED_COMPONENT (t))) > + || TREE_CODE (t) == VECTOR_TYPE) > + t = TREE_TYPE (t); > + if (POINTER_TYPE_P (t)) > + t = ptr_type_node; > + } > + > + record_alias_subset (superset, get_alias_set (t)); > + } > break; Are you sure that it's not !TYPE_NONALIASED_COMPONENT (t) here?
> > + tree t = TREE_TYPE (field); > > + if (in_lto_p) > > + { > > + /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their > > + element type and that type has to be normalized to void *, > > + too, in the case it is a pointer. */ > > + while ((TREE_CODE (t) == ARRAY_TYPE > > + && (!COMPLETE_TYPE_P (t) > > + || TYPE_NONALIASED_COMPONENT (t))) > > + || TREE_CODE (t) == VECTOR_TYPE) > > + t = TREE_TYPE (t); > > + if (POINTER_TYPE_P (t)) > > + t = ptr_type_node; > > + } > > + > > + record_alias_subset (superset, get_alias_set (t)); > > + } > > break; > > Are you sure that it's not !TYPE_NONALIASED_COMPONENT (t) here? You are right, TYPE_NONALIASED_COMPONENT is the wrong way. I will fix it and try to come up with a testcase (TYPE_NONALIASED_COMPONENT is quite rarely used beast) Honza > > -- > Eric Botcazou
> You are right, TYPE_NONALIASED_COMPONENT is the wrong way. I will fix it > and try to come up with a testcase (TYPE_NONALIASED_COMPONENT is quite > rarely used beast) It's only used in Ada as far as I know, but is quite sensitive and quickly leads to wrong code if not handled properly in my experience, so this could well be responsible for the gnat1 miscompilation.
On Mon, 23 Nov 2015, Jan Hubicka wrote: > Hi, > here is updated patch which I finally comitted today. It addresses all the comments > and also fixes one nasty bug that really cost me a lot of time to understand. > > + /* LTO type merging does not make any difference between > + component pointer types. We may have > + > + struct foo {int *a;}; > + > + as TYPE_CANONICAL of > + > + struct bar {float *a;}; > + > + Because accesses to int * and float * do not alias, we would get > + false negative when accessing the same memory location by > + float ** and bar *. We thus record the canonical type as: > + > + struct {void *a;}; > + > + void * is special cased and works as a universal pointer type. > + Accesses to it conflicts with accesses to any other pointer > + type. */ > > This problem manifested itself only as a lto-bootstrap miscompare on 32bit > build and I spent a lot of time localizing the wrong code since it reproduces > only in quite large programs where we get conficts in canonical type merging > like this. > > The patch thus updates record_component_aliases to substitute > void_ptr_type for all pointer types. I re-did the stats. Now the > improvement on dealII is 14% that is quite a bit lower than earlier, but > still substantial. Since we have voidptr globing counter, I know that > the number of disambiguations would go at least 19% up if we did not do > it. Please in future leave patches for review again if you do such big changes before committing... I don't understand why we need this (testcase?) because get_alias_set () is supposed to do the alias-set of pointer globbing for us. Thanks, Richard. > THere is a lot of low hanging fruit in that area now, but the real > solution is to track types that needs to be merge by fortran rules and > don't do all this fancy globing for C/C++ types. I will open branch for > IPA work and try to prepare this for next stage 1. > > bootstrapped/regtested x86_64-linux and ppc64-linux, earlier version tested on i386-linux > and also on some bigger apps, committed > > Note that we still have bootstrap miscompare with LTO build and --disable-checking, > I am looking for that now. Additoinally after fixing the ICEs preventing us to build > the gnat1 binary, gnat1 aborts. Both these are independent of the patch. > > Honza > * lto.c (iterative_hash_canonical_type): Always recurse for pointers. > (gimple_register_canonical_type_1): Check that pointers do not get > canonical types. > (gimple_register_canonical_type): Do not register pointers. > > * tree.c (build_pointer_type_for_mode,build_reference_type_for_mode): > In LTO we do not compute TYPE_CANONICAL of pointers. > (gimple_canonical_types_compatible_p): Improve coments; sanity check > that pointers do not have canonical type that would make us believe > they are different. > * alias.c (get_alias_set): Do structural type equality on pointers; > enable pointer path for LTO; also glob pointer to vector with pointer > to vector element; glob pointers and references for LTO; do more strict > sanity checking about build_pointer_type returning the canonical type > which is also the main variant. > (record_component_aliases): When component type is pointer and we > do LTO; record void_type_node alias set. > Index: tree.c > =================================================================== > --- tree.c (revision 230714) > +++ tree.c (working copy) > @@ -7919,7 +7919,8 @@ build_pointer_type_for_mode (tree to_typ > TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type); > TYPE_POINTER_TO (to_type) = t; > > - if (TYPE_STRUCTURAL_EQUALITY_P (to_type)) > + /* During LTO we do not set TYPE_CANONICAL of pointers and references. */ > + if (TYPE_STRUCTURAL_EQUALITY_P (to_type) || in_lto_p) > SET_TYPE_STRUCTURAL_EQUALITY (t); > else if (TYPE_CANONICAL (to_type) != to_type || could_alias) > TYPE_CANONICAL (t) > @@ -7987,7 +7988,8 @@ build_reference_type_for_mode (tree to_t > TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type); > TYPE_REFERENCE_TO (to_type) = t; > > - if (TYPE_STRUCTURAL_EQUALITY_P (to_type)) > + /* During LTO we do not set TYPE_CANONICAL of pointers and references. */ > + if (TYPE_STRUCTURAL_EQUALITY_P (to_type) || in_lto_p) > SET_TYPE_STRUCTURAL_EQUALITY (t); > else if (TYPE_CANONICAL (to_type) != to_type || could_alias) > TYPE_CANONICAL (t) > @@ -13224,7 +13226,9 @@ type_with_interoperable_signedness (cons > TBAA is concerned. > This function is used both by lto.c canonical type merging and by the > verifier. If TRUST_TYPE_CANONICAL we do not look into structure of types > - that have TYPE_CANONICAL defined and assume them equivalent. */ > + that have TYPE_CANONICAL defined and assume them equivalent. This is useful > + only for LTO because only in these cases TYPE_CANONICAL equivalence > + correspond to one defined by gimple_canonical_types_compatible_p. */ > > bool > gimple_canonical_types_compatible_p (const_tree t1, const_tree t2, > @@ -13265,9 +13269,19 @@ gimple_canonical_types_compatible_p (con > || (type_with_alias_set_p (t1) && type_with_alias_set_p (t2))); > /* If the types have been previously registered and found equal > they still are. */ > + > if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t2) > && trust_type_canonical) > - return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2); > + { > + /* Do not use TYPE_CANONICAL of pointer types. For LTO streamed types > + they are always NULL, but they are set to non-NULL for types > + constructed by build_pointer_type and variants. In this case the > + TYPE_CANONICAL is more fine grained than the equivalnce we test (where > + all pointers are considered equal. Be sure to not return false > + negatives. */ > + gcc_checking_assert (!POINTER_TYPE_P (t1) && !POINTER_TYPE_P (t2)); > + return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2); > + } > > /* Can't be the same type if the types don't have the same code. */ > enum tree_code code = tree_code_for_canonical_type_merging (TREE_CODE (t1)); > Index: lto/lto.c > =================================================================== > --- lto/lto.c (revision 230714) > +++ lto/lto.c (working copy) > @@ -388,8 +388,13 @@ iterative_hash_canonical_type (tree type > > /* All type variants have same TYPE_CANONICAL. */ > type = TYPE_MAIN_VARIANT (type); > + > + /* We do not compute TYPE_CANONICAl of POINTER_TYPE because the aliasing > + code never use it anyway. */ > + if (POINTER_TYPE_P (type)) > + v = hash_canonical_type (type); > /* An already processed type. */ > - if (TYPE_CANONICAL (type)) > + else if (TYPE_CANONICAL (type)) > { > type = TYPE_CANONICAL (type); > v = gimple_canonical_type_hash (type); > @@ -437,7 +442,9 @@ gimple_register_canonical_type_1 (tree t > { > void **slot; > > - gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t)); > + gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t) > + && type_with_alias_set_p (t) > + && !POINTER_TYPE_P (t)); > > slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash, INSERT); > if (*slot) > @@ -470,7 +477,7 @@ gimple_register_canonical_type_1 (tree t > static void > gimple_register_canonical_type (tree t) > { > - if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t)) > + if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t) || POINTER_TYPE_P (t)) > return; > > /* Canonical types are same among all complete variants. */ > Index: alias.c > =================================================================== > --- alias.c (revision 230714) > +++ alias.c (working copy) > @@ -869,13 +869,23 @@ get_alias_set (tree t) > set = lang_hooks.get_alias_set (t); > if (set != -1) > return set; > - return 0; > + /* Handle structure type equality for pointer types. This is easy > + to do, because the code bellow ignore canonical types on these anyway. > + This is important for LTO, where TYPE_CANONICAL for pointers can not > + be meaningfuly computed by the frotnend. */ > + if (!POINTER_TYPE_P (t)) > + { > + /* In LTO we set canonical types for all types where it makes > + sense to do so. Double check we did not miss some type. */ > + gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t)); > + return 0; > + } > + } > + else > + { > + t = TYPE_CANONICAL (t); > + gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t)); > } > - > - t = TYPE_CANONICAL (t); > - > - /* The canonical type should not require structural equality checks. */ > - gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t)); > > /* If this is a type with a known alias set, return it. */ > if (TYPE_ALIAS_SET_KNOWN_P (t)) > @@ -952,20 +962,23 @@ get_alias_set (tree t) > ptr_type_node but that is a bad idea, because it prevents disabiguations > in between pointers. For Firefox this accounts about 20% of all > disambiguations in the program. */ > - else if (POINTER_TYPE_P (t) && t != ptr_type_node && !in_lto_p) > + else if (POINTER_TYPE_P (t) && t != ptr_type_node) > { > tree p; > auto_vec <bool, 8> reference; > > /* Unnest all pointers and references. > - We also want to make pointer to array equivalent to pointer to its > - element. So skip all array types, too. */ > + We also want to make pointer to array/vector equivalent to pointer to > + its element (see the reasoning above). Skip all those types, too. */ > for (p = t; POINTER_TYPE_P (p) > - || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p)); > + || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p)) > + || TREE_CODE (p) == VECTOR_TYPE; > p = TREE_TYPE (p)) > { > if (TREE_CODE (p) == REFERENCE_TYPE) > - reference.safe_push (true); > + /* In LTO we want languages that use references to be compatible > + with languages that use pointers. */ > + reference.safe_push (true && !in_lto_p); > if (TREE_CODE (p) == POINTER_TYPE) > reference.safe_push (false); > } > @@ -981,7 +994,7 @@ get_alias_set (tree t) > set = get_alias_set (ptr_type_node); > else > { > - /* Rebuild pointer type from starting from canonical types using > + /* Rebuild pointer type starting from canonical types using > unqualified pointers and references only. This way all such > pointers will have the same alias set and will conflict with > each other. > @@ -998,9 +1011,15 @@ get_alias_set (tree t) > p = build_reference_type (p); > else > p = build_pointer_type (p); > - p = TYPE_CANONICAL (TYPE_MAIN_VARIANT (p)); > + gcc_checking_assert (p == TYPE_MAIN_VARIANT (p)); > + /* build_pointer_type should always return the canonical type. > + For LTO TYPE_CANOINCAL may be NULL, because we do not compute > + them. Be sure that frontends do not glob canonical types of > + pointers in unexpected way and that p == TYPE_CANONICAL (p) > + in all other cases. */ > + gcc_checking_assert (!TYPE_CANONICAL (p) > + || p == TYPE_CANONICAL (p)); > } > - gcc_checking_assert (TYPE_CANONICAL (p) == p); > > /* Assign the alias set to both p and t. > We can not call get_alias_set (p) here as that would trigger > @@ -1015,11 +1034,12 @@ get_alias_set (tree t) > } > } > } > - /* In LTO the rules above needs to be part of canonical type machinery. > - For now just punt. */ > - else if (POINTER_TYPE_P (t) > - && t != TYPE_CANONICAL (ptr_type_node) && in_lto_p) > - set = get_alias_set (TYPE_CANONICAL (ptr_type_node)); > + /* Alias set of ptr_type_node is special and serve as universal pointer which > + is TBAA compatible with every other pointer type. Be sure we have the > + alias set built even for LTO which otherwise keeps all TYPE_CANONICAL > + of pointer types NULL. */ > + else if (t == ptr_type_node) > + set = new_alias_set (); > > /* Otherwise make a new alias set for this type. */ > else > @@ -1155,7 +1175,42 @@ record_component_aliases (tree type) > case QUAL_UNION_TYPE: > for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field)) > if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field)) > - record_alias_subset (superset, get_alias_set (TREE_TYPE (field))); > + { > + /* LTO type merging does not make any difference between > + component pointer types. We may have > + > + struct foo {int *a;}; > + > + as TYPE_CANONICAL of > + > + struct bar {float *a;}; > + > + Because accesses to int * and float * do not alias, we would get > + false negative when accessing the same memory location by > + float ** and bar *. We thus record the canonical type as: > + > + struct {void *a;}; > + > + void * is special cased and works as a universal pointer type. > + Accesses to it conflicts with accesses to any other pointer > + type. */ > + tree t = TREE_TYPE (field); > + if (in_lto_p) > + { > + /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their > + element type and that type has to be normalized to void *, > + too, in the case it is a pointer. */ > + while ((TREE_CODE (t) == ARRAY_TYPE > + && (!COMPLETE_TYPE_P (t) > + || TYPE_NONALIASED_COMPONENT (t))) > + || TREE_CODE (t) == VECTOR_TYPE) > + t = TREE_TYPE (t); > + if (POINTER_TYPE_P (t)) > + t = ptr_type_node; > + } > + > + record_alias_subset (superset, get_alias_set (t)); > + } > break; > > case COMPLEX_TYPE: > >
> > Please in future leave patches for review again if you do such > big changes before committing... Uhm, sorry, next time I will be more cureful. It seemed rather easy after debugging it but indeed it is somewhat surprising issue. > > I don't understand why we need this (testcase?) because get_alias_set () > is supposed to do the alias-set of pointer globbing for us. The situation is as follows. You can have struct a { int *ptr; } struct b { float *ptr; } Now, if becase type is ignored by TYPE_CANONICAL, we have TYPE_CANONICAL (sturct b) = struct a. and while building alias set of "struct a" we record compoents as: struct a ^ | int * Now do struct b b = {NULL}; float *p=&b->ptr; *p=nonnull; return b.ptr; Now alias set of the initialization is alias set of "struct a". The alias set of of the pointer store is "float *". We ask alias oracle if "struct a" can conflict with "float *" and answer is no, because "int *" (component of struct b) and "float *" are not conflicting. With the change we record component alias as follows: struct a ^ | void * which makes the answer to be correct, because "int *" conflicts with all pointers, so all such queries about a structure gimple_canonical_types_compatible with "struct a" will be handled correctly. I will add aritifical testcase for this after double checking that the code above miscompiles without that conditional. I found that having warning about TBAA incompatibility when doing merigng in lto-symtab is great to catch issues like this. I had this patch for quite some time, but it was producing obviously wrong positives (in Fortran, Ada and also sometimes in Firefox on array initializes of style int a[]={1,2,3}). I wrongly assumed tha the bug is because we compute TYPE_CANONICAL sensitively to array size and there are permited transitions of array sizes between units. THis is not the case. Yesterday I found that the problem is with interaction of get_alias_set globbing and gimple_canonical_types_compatible globbing. We can't have get_alias_set globbing more or less coarse than gimple_canonical_types_compatible does. Here the situation is reverse to the case above : because array type is inherited from element type, we can't have TYPE_CANONICAL more globbed for array than we have get_alias_set. In this case the problem appeared when TYPE_NONALIASED_COMPONENT array previaled in type merging other arrays. The situation got worse with pointer, becuase array of pointers of one type could prevail array of pointers of other type and then the array type gets different alias sets in different units. This seems to work for C programs, but is wrong. I will send patch and separate explanation after re-testing final version shortly. Honza
> > You are right, TYPE_NONALIASED_COMPONENT is the wrong way. I will fix it > > and try to come up with a testcase (TYPE_NONALIASED_COMPONENT is quite > > rarely used beast) > > It's only used in Ada as far as I know, but is quite sensitive and quickly > leads to wrong code if not handled properly in my experience, so this could > well be responsible for the gnat1 miscompilation. Build fialed same way before my patch. Moreover the problem can only happen on array of pointers that are type punned (i.e. using store like (void *[r])array = [NULL, NULL, NULL] and then accessing it as (int *[r]) array. I do not think C or Ada can produce code like that. I am re-testing with the fix to TYPE_NONALIASED_COMPONENT arrays I explained in other email. Perhaps that helps, or perhaps it is one of those Ada/C type puning glues getting miscompiled? Other Ada binaries (gnatbind) seems to work fine. I will post backtrace once my testing gets to the ICE again. Honza > > -- > Eric Botcazou
On Mon, 23 Nov 2015, Jan Hubicka wrote: > > > > Please in future leave patches for review again if you do such > > big changes before committing... > > Uhm, sorry, next time I will be more cureful. It seemed rather easy after > debugging it but indeed it is somewhat surprising issue. > > > > I don't understand why we need this (testcase?) because get_alias_set () > > is supposed to do the alias-set of pointer globbing for us. > > The situation is as follows. You can have > > struct a { > int *ptr; > } > > struct b { > float *ptr; > } > > Now, if becase type is ignored by TYPE_CANONICAL, we have > > TYPE_CANONICAL (sturct b) = struct a. > > and while building alias set of "struct a" we record compoents as: > > struct a > ^ > | > int * > > Now do > > struct b b = {NULL}; > float *p=&b->ptr; > *p=nonnull; > return b.ptr; > > Now alias set of the initialization is alias set of "struct a". The alias set > of of the pointer store is "float *". We ask alias oracle if "struct a" can > conflict with "float *" and answer is no, because "int *" (component of struct > b) and "float *" are not conflicting. With the change we record component > alias as follows: Ah, with my original pointer globbing I side-stepped this. So are you _really_ sure that we want to handle int * different from float *? Because that makes the situation much more complicated in these cases. > > struct a > ^ > | > void * > > which makes the answer to be correct, because "int *" conflicts with all > pointers, so all such queries about a structure > gimple_canonical_types_compatible with "struct a" will be handled > correctly. > > I will add aritifical testcase for this after double checking that the code above > miscompiles without that conditional. > > I found that having warning about TBAA incompatibility when doing merigng in > lto-symtab is great to catch issues like this. > > I had this patch for quite some time, but it was producing obviously wrong > positives (in Fortran, Ada and also sometimes in Firefox on array initializes > of style int a[]={1,2,3}). I wrongly assumed tha the bug is because we compute > TYPE_CANONICAL sensitively to array size and there are permited transitions > of array sizes between units. THis is not the case. > > Yesterday I found that the problem is with interaction of get_alias_set > globbing and gimple_canonical_types_compatible globbing. We can't have > get_alias_set globbing more or less coarse than > gimple_canonical_types_compatible does. > > Here the situation is reverse to the case above : because array type is > inherited from element type, we can't have TYPE_CANONICAL more globbed for > array than we have get_alias_set. In this case the problem appeared when > TYPE_NONALIASED_COMPONENT array previaled in type merging other arrays. The > situation got worse with pointer, becuase array of pointers of one type could > prevail array of pointers of other type and then the array type gets different > alias sets in different units. This seems to work for C programs, but is > wrong. I will send patch and separate explanation after re-testing final > version shortly. I feel we need to document all this somewhere. Richard. > Honza > >
> > Now alias set of the initialization is alias set of "struct a". The alias set > > of of the pointer store is "float *". We ask alias oracle if "struct a" can > > conflict with "float *" and answer is no, because "int *" (component of struct > > b) and "float *" are not conflicting. With the change we record component > > alias as follows: > > Ah, with my original pointer globbing I side-stepped this. So are > you _really_ sure that we want to handle int * different from float *? > Because that makes the situation much more complicated in these cases. Yep, keeping track of different pointer types in C++ is really important and moreover the old globbing was not able to deal with C/Fortran compatibility fun anyway. Average higher level C++ code has dozen of differently typed containers for random stuff and shuffles the pointers around them in memory. Without being able to track down pointers stored in memory there is no hope to optimize the code. This very basic pointer LTO reduced rodata cc1 binary by 7% which I think are from 99% the removed sanity checking __FUNCTION__ locators. Globing all pointers to void * is just part of the problem anyway. The previous code did not implemented Fortran/C interoperability correctly anyway. I hope that with these changes we have infrastructure robust and flexible enough to model more precisely what we really want. > > Here the situation is reverse to the case above : because array type is > > inherited from element type, we can't have TYPE_CANONICAL more globbed for > > array than we have get_alias_set. In this case the problem appeared when > > TYPE_NONALIASED_COMPONENT array previaled in type merging other arrays. The > > situation got worse with pointer, becuase array of pointers of one type could > > prevail array of pointers of other type and then the array type gets different > > alias sets in different units. This seems to work for C programs, but is > > wrong. I will send patch and separate explanation after re-testing final > > version shortly. > > I feel we need to document all this somewhere. Yeah, that would be a good idea. Probably comment at beggining of alias.c? I was thinking of moving the code to one place, perhaps moving gimple_canonical_type from tree.c to alias.c would make sense, or inventing new place for this. Moreover I was thinking of extending type verifier to check that all components of a type alias with the whole tihng, so we do not run into bugs like this again. Together with the TBAA checking in lto-symtab.c it should make it pretty hard to make nasty bugs like this. Thanks, Honza > > Richard. > > > Honza > > > > > > -- > Richard Biener <rguenther@suse.de> > SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)
On Tue, 24 Nov 2015, Jan Hubicka wrote: > > > Now alias set of the initialization is alias set of "struct a". The alias set > > > of of the pointer store is "float *". We ask alias oracle if "struct a" can > > > conflict with "float *" and answer is no, because "int *" (component of struct > > > b) and "float *" are not conflicting. With the change we record component > > > alias as follows: > > > > Ah, with my original pointer globbing I side-stepped this. So are > > you _really_ sure that we want to handle int * different from float *? > > Because that makes the situation much more complicated in these cases. > > Yep, keeping track of different pointer types in C++ is really important > and moreover the old globbing was not able to deal with C/Fortran compatibility > fun anyway. > > Average higher level C++ code has dozen of differently typed containers for > random stuff and shuffles the pointers around them in memory. Without being > able to track down pointers stored in memory there is no hope to optimize the > code. > > This very basic pointer LTO reduced rodata cc1 binary by 7% which I think are > from 99% the removed sanity checking __FUNCTION__ locators. > > Globing all pointers to void * is just part of the problem anyway. The previous > code did not implemented Fortran/C interoperability correctly anyway. I hope > that with these changes we have infrastructure robust and flexible enough > to model more precisely what we really want. > > > > Here the situation is reverse to the case above : because array type is > > > inherited from element type, we can't have TYPE_CANONICAL more globbed for > > > array than we have get_alias_set. In this case the problem appeared when > > > TYPE_NONALIASED_COMPONENT array previaled in type merging other arrays. The > > > situation got worse with pointer, becuase array of pointers of one type could > > > prevail array of pointers of other type and then the array type gets different > > > alias sets in different units. This seems to work for C programs, but is > > > wrong. I will send patch and separate explanation after re-testing final > > > version shortly. > > > > I feel we need to document all this somewhere. > > Yeah, that would be a good idea. Probably comment at beggining of alias.c? Yes, that sounds good. > I was thinking of moving the code to one place, perhaps moving > gimple_canonical_type from tree.c to alias.c would make sense, or inventing > new place for this. Didn't like tree.c for this anyway and yes, alias.c sounds better given its connection to alias. > Moreover I was thinking of extending type verifier to check that all > components of a type alias with the whole tihng, so we do not run into > bugs like this again. Together with the TBAA checking in lto-symtab.c it > should make it pretty hard to make nasty bugs like this. Might be a bit expensive though. It also reminds me of all the ICEs we have PRs for WRT the type verifier. Remember we are in stage3 now so rather than introducing new issues you should spend some time fixing the existing ones you caused ;)) (just look for bugs CCed to hubicka@gcc.gnu.org) Thanks, Richard.
> > Might be a bit expensive though. It also reminds me of all the > ICEs we have PRs for WRT the type verifier. Remember we are in stage3 > now so rather than introducing new issues you should spend some time > fixing the existing ones you caused ;)) (just look for bugs > CCed to hubicka@gcc.gnu.org) Yep, I already fixed some of these, will push out patches today. Honza > > Thanks, > Richard.
Index: tree.c =================================================================== --- tree.c (revision 230714) +++ tree.c (working copy) @@ -7919,7 +7919,8 @@ build_pointer_type_for_mode (tree to_typ TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type); TYPE_POINTER_TO (to_type) = t; - if (TYPE_STRUCTURAL_EQUALITY_P (to_type)) + /* During LTO we do not set TYPE_CANONICAL of pointers and references. */ + if (TYPE_STRUCTURAL_EQUALITY_P (to_type) || in_lto_p) SET_TYPE_STRUCTURAL_EQUALITY (t); else if (TYPE_CANONICAL (to_type) != to_type || could_alias) TYPE_CANONICAL (t) @@ -7987,7 +7988,8 @@ build_reference_type_for_mode (tree to_t TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type); TYPE_REFERENCE_TO (to_type) = t; - if (TYPE_STRUCTURAL_EQUALITY_P (to_type)) + /* During LTO we do not set TYPE_CANONICAL of pointers and references. */ + if (TYPE_STRUCTURAL_EQUALITY_P (to_type) || in_lto_p) SET_TYPE_STRUCTURAL_EQUALITY (t); else if (TYPE_CANONICAL (to_type) != to_type || could_alias) TYPE_CANONICAL (t) @@ -13224,7 +13226,9 @@ type_with_interoperable_signedness (cons TBAA is concerned. This function is used both by lto.c canonical type merging and by the verifier. If TRUST_TYPE_CANONICAL we do not look into structure of types - that have TYPE_CANONICAL defined and assume them equivalent. */ + that have TYPE_CANONICAL defined and assume them equivalent. This is useful + only for LTO because only in these cases TYPE_CANONICAL equivalence + correspond to one defined by gimple_canonical_types_compatible_p. */ bool gimple_canonical_types_compatible_p (const_tree t1, const_tree t2, @@ -13265,9 +13269,19 @@ gimple_canonical_types_compatible_p (con || (type_with_alias_set_p (t1) && type_with_alias_set_p (t2))); /* If the types have been previously registered and found equal they still are. */ + if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t2) && trust_type_canonical) - return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2); + { + /* Do not use TYPE_CANONICAL of pointer types. For LTO streamed types + they are always NULL, but they are set to non-NULL for types + constructed by build_pointer_type and variants. In this case the + TYPE_CANONICAL is more fine grained than the equivalnce we test (where + all pointers are considered equal. Be sure to not return false + negatives. */ + gcc_checking_assert (!POINTER_TYPE_P (t1) && !POINTER_TYPE_P (t2)); + return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2); + } /* Can't be the same type if the types don't have the same code. */ enum tree_code code = tree_code_for_canonical_type_merging (TREE_CODE (t1)); Index: lto/lto.c =================================================================== --- lto/lto.c (revision 230714) +++ lto/lto.c (working copy) @@ -388,8 +388,13 @@ iterative_hash_canonical_type (tree type /* All type variants have same TYPE_CANONICAL. */ type = TYPE_MAIN_VARIANT (type); + + /* We do not compute TYPE_CANONICAl of POINTER_TYPE because the aliasing + code never use it anyway. */ + if (POINTER_TYPE_P (type)) + v = hash_canonical_type (type); /* An already processed type. */ - if (TYPE_CANONICAL (type)) + else if (TYPE_CANONICAL (type)) { type = TYPE_CANONICAL (type); v = gimple_canonical_type_hash (type); @@ -437,7 +442,9 @@ gimple_register_canonical_type_1 (tree t { void **slot; - gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t)); + gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t) + && type_with_alias_set_p (t) + && !POINTER_TYPE_P (t)); slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash, INSERT); if (*slot) @@ -470,7 +477,7 @@ gimple_register_canonical_type_1 (tree t static void gimple_register_canonical_type (tree t) { - if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t)) + if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t) || POINTER_TYPE_P (t)) return; /* Canonical types are same among all complete variants. */ Index: alias.c =================================================================== --- alias.c (revision 230714) +++ alias.c (working copy) @@ -869,13 +869,23 @@ get_alias_set (tree t) set = lang_hooks.get_alias_set (t); if (set != -1) return set; - return 0; + /* Handle structure type equality for pointer types. This is easy + to do, because the code bellow ignore canonical types on these anyway. + This is important for LTO, where TYPE_CANONICAL for pointers can not + be meaningfuly computed by the frotnend. */ + if (!POINTER_TYPE_P (t)) + { + /* In LTO we set canonical types for all types where it makes + sense to do so. Double check we did not miss some type. */ + gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t)); + return 0; + } + } + else + { + t = TYPE_CANONICAL (t); + gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t)); } - - t = TYPE_CANONICAL (t); - - /* The canonical type should not require structural equality checks. */ - gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t)); /* If this is a type with a known alias set, return it. */ if (TYPE_ALIAS_SET_KNOWN_P (t)) @@ -952,20 +962,23 @@ get_alias_set (tree t) ptr_type_node but that is a bad idea, because it prevents disabiguations in between pointers. For Firefox this accounts about 20% of all disambiguations in the program. */ - else if (POINTER_TYPE_P (t) && t != ptr_type_node && !in_lto_p) + else if (POINTER_TYPE_P (t) && t != ptr_type_node) { tree p; auto_vec <bool, 8> reference; /* Unnest all pointers and references. - We also want to make pointer to array equivalent to pointer to its - element. So skip all array types, too. */ + We also want to make pointer to array/vector equivalent to pointer to + its element (see the reasoning above). Skip all those types, too. */ for (p = t; POINTER_TYPE_P (p) - || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p)); + || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p)) + || TREE_CODE (p) == VECTOR_TYPE; p = TREE_TYPE (p)) { if (TREE_CODE (p) == REFERENCE_TYPE) - reference.safe_push (true); + /* In LTO we want languages that use references to be compatible + with languages that use pointers. */ + reference.safe_push (true && !in_lto_p); if (TREE_CODE (p) == POINTER_TYPE) reference.safe_push (false); } @@ -981,7 +994,7 @@ get_alias_set (tree t) set = get_alias_set (ptr_type_node); else { - /* Rebuild pointer type from starting from canonical types using + /* Rebuild pointer type starting from canonical types using unqualified pointers and references only. This way all such pointers will have the same alias set and will conflict with each other. @@ -998,9 +1011,15 @@ get_alias_set (tree t) p = build_reference_type (p); else p = build_pointer_type (p); - p = TYPE_CANONICAL (TYPE_MAIN_VARIANT (p)); + gcc_checking_assert (p == TYPE_MAIN_VARIANT (p)); + /* build_pointer_type should always return the canonical type. + For LTO TYPE_CANOINCAL may be NULL, because we do not compute + them. Be sure that frontends do not glob canonical types of + pointers in unexpected way and that p == TYPE_CANONICAL (p) + in all other cases. */ + gcc_checking_assert (!TYPE_CANONICAL (p) + || p == TYPE_CANONICAL (p)); } - gcc_checking_assert (TYPE_CANONICAL (p) == p); /* Assign the alias set to both p and t. We can not call get_alias_set (p) here as that would trigger @@ -1015,11 +1034,12 @@ get_alias_set (tree t) } } } - /* In LTO the rules above needs to be part of canonical type machinery. - For now just punt. */ - else if (POINTER_TYPE_P (t) - && t != TYPE_CANONICAL (ptr_type_node) && in_lto_p) - set = get_alias_set (TYPE_CANONICAL (ptr_type_node)); + /* Alias set of ptr_type_node is special and serve as universal pointer which + is TBAA compatible with every other pointer type. Be sure we have the + alias set built even for LTO which otherwise keeps all TYPE_CANONICAL + of pointer types NULL. */ + else if (t == ptr_type_node) + set = new_alias_set (); /* Otherwise make a new alias set for this type. */ else @@ -1155,7 +1175,42 @@ record_component_aliases (tree type) case QUAL_UNION_TYPE: for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field)) if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field)) - record_alias_subset (superset, get_alias_set (TREE_TYPE (field))); + { + /* LTO type merging does not make any difference between + component pointer types. We may have + + struct foo {int *a;}; + + as TYPE_CANONICAL of + + struct bar {float *a;}; + + Because accesses to int * and float * do not alias, we would get + false negative when accessing the same memory location by + float ** and bar *. We thus record the canonical type as: + + struct {void *a;}; + + void * is special cased and works as a universal pointer type. + Accesses to it conflicts with accesses to any other pointer + type. */ + tree t = TREE_TYPE (field); + if (in_lto_p) + { + /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their + element type and that type has to be normalized to void *, + too, in the case it is a pointer. */ + while ((TREE_CODE (t) == ARRAY_TYPE + && (!COMPLETE_TYPE_P (t) + || TYPE_NONALIASED_COMPONENT (t))) + || TREE_CODE (t) == VECTOR_TYPE) + t = TREE_TYPE (t); + if (POINTER_TYPE_P (t)) + t = ptr_type_node; + } + + record_alias_subset (superset, get_alias_set (t)); + } break; case COMPLEX_TYPE:
Hi, here is updated patch which I finally comitted today. It addresses all the comments and also fixes one nasty bug that really cost me a lot of time to understand. + /* LTO type merging does not make any difference between + component pointer types. We may have + + struct foo {int *a;}; + + as TYPE_CANONICAL of + + struct bar {float *a;}; + + Because accesses to int * and float * do not alias, we would get + false negative when accessing the same memory location by + float ** and bar *. We thus record the canonical type as: + + struct {void *a;}; + + void * is special cased and works as a universal pointer type. + Accesses to it conflicts with accesses to any other pointer + type. */ This problem manifested itself only as a lto-bootstrap miscompare on 32bit build and I spent a lot of time localizing the wrong code since it reproduces only in quite large programs where we get conficts in canonical type merging like this. The patch thus updates record_component_aliases to substitute void_ptr_type for all pointer types. I re-did the stats. Now the improvement on dealII is 14% that is quite a bit lower than earlier, but still substantial. Since we have voidptr globing counter, I know that the number of disambiguations would go at least 19% up if we did not do it. THere is a lot of low hanging fruit in that area now, but the real solution is to track types that needs to be merge by fortran rules and don't do all this fancy globing for C/C++ types. I will open branch for IPA work and try to prepare this for next stage 1. bootstrapped/regtested x86_64-linux and ppc64-linux, earlier version tested on i386-linux and also on some bigger apps, committed Note that we still have bootstrap miscompare with LTO build and --disable-checking, I am looking for that now. Additoinally after fixing the ICEs preventing us to build the gnat1 binary, gnat1 aborts. Both these are independent of the patch. Honza * lto.c (iterative_hash_canonical_type): Always recurse for pointers. (gimple_register_canonical_type_1): Check that pointers do not get canonical types. (gimple_register_canonical_type): Do not register pointers. * tree.c (build_pointer_type_for_mode,build_reference_type_for_mode): In LTO we do not compute TYPE_CANONICAL of pointers. (gimple_canonical_types_compatible_p): Improve coments; sanity check that pointers do not have canonical type that would make us believe they are different. * alias.c (get_alias_set): Do structural type equality on pointers; enable pointer path for LTO; also glob pointer to vector with pointer to vector element; glob pointers and references for LTO; do more strict sanity checking about build_pointer_type returning the canonical type which is also the main variant. (record_component_aliases): When component type is pointer and we do LTO; record void_type_node alias set.