> On Wed, 20 May 2015, Jan Hubicka wrote: > > > Richard, > > this is my attempt to make sense of TYPE_CANONICAL at LTO. My > > undrestanding is > > that gimple_canonical_types_compatible_p needs to return true for all pairs > > of > > types that are considered compatible across compilation unit for any of > > languages we support (and in a sane way for cross language, too) and > > moreover > > it needs to form an equivalence so it can be used to do canonical type > > merging. > > > > Now C definition of type compatibility ignores type names and only boils > > down > > to structural compare (which we get wrong for unions, but I will look into > > that > > incrementally, also C explicitely require fields names to match, which we > > don't) > > and it of course says that incompete type can match complete. > > field-names are difficult to match cross-language.
Yep, I suppose that may be tricky. One thing that may make sense is to detect if whole program is C/C++ only and switch to the standard compliant matching here. > > > This is bit generous on structures and unions, because every incomplete > > RECORD_TYPE is compatible with every RECORD_TYPE in program and similarly > > incomplete UNION_TYPE is compatible with every UNION_TYPE in program. > > > > Now from the fact that gimple_canonical_types_compatible_p must be > > equivalence > > (and thus transitive) we immmediately get that there is no way to make > > difference between two RECORD_TYPEs (or UNION_TYPEs) at all: there always > > may > > be incomplete that forces them equivalent. > > > > This is not how the code works. gimple_canonical_types_compatible_p will not > > match complete type with incomplete and this is not a prolblem only because > > TYPE_CANONICAL matters for complete types only. TBAA machinery never needs > > alias sets of an incomplete type (modulo bugs). > > Correct. > > > More precisely we have two equivalences: > > 1) full structural equivalence matching fields, array sizes and function > > parameters, where pointer types are however recursively matched only > > with 2) > > Not sure about function parameters (well, function types at all - they > don't play a role in TBAA) - function "members" are always pointers, so > see 2) OK, we compute the canonical types for functions just to ignore them, indeed. > > > 2) structural equivalence ignoring any info from complete types: > > here all RECORD_TYPEs are equal, so are UNION_TYPEs, for functions we > > can only match return value (because of existence of non-prototypes), > > for arrays only TREE_TYPE. > > In this equivalence we also can't match TYPE_MODE of aggregates/arrays > > because it may not be set for incomplete ones. > > > > Now our implementation somehow compute only 1) and 2) is approximated by > > matching TREE_CODE of the pointer-to type. This is unnecesarily pesimistic. > > Pointer to pointer to int does not need to match pointer to pointer to > > structure. > > Note that you have (a lot of!) pointer members that point to structures > in various state of completeness. A pointer to an incomplete type > needs to match all other pointer types (well, the current code tries > to make the exception that a pointer to an aggregate stays a pointer > to an aggregate - thus the matching of pointed-to type - sorry to > only remember now the connection to incompleteness ...) Yes, that is actually consistent with what C standard says - the incomplete types (cross language) depends only on the tag and tag is basically ARRAY_TYPE/ RECORD_TYPE/UNION_TYPE distinction. > > > The patch bellow changes it in the following way: > > > > a) it adds MATCH_INCOMPLETE_TYPES parameter to > > gimple_canonical_types_compatible_p and gimple_canonical_type_hash > > to determine whether we compute equivalence 1) or 2). > > > > The way we handle pointers is updated so we set MATCH_INCOMPLETE_TYPES > > when recursing down to pointer type. This makes it possible for > > complete structure referring incomplete pointer type to be equivalent > > with > > a complete structure referring complete pointer type. > > But does this really end up getting more equivalence classes than the > crude approach matching TREE_CODE? We can distinguish different pointers to pointers and pointers to types that are always complete (integers/reals). It makes relatively small difference on Firefox (about 2-5% more disambiguations with my patch), but I think it is more correct and extensible. For example, now it is quite clear how to handle anonymous C++ types incrementally. > > > I believe that in this definition we do best possible equivalence > > passing the rules above and we do not need to care about SCC - the > > only way how type can reffer itself is via pointer and that will make us > > to drop to MATCH_INCOMPLETE_TYPES. > > b) it disables TYPE_CANONICAL calculation for incomplete types and > > functions > > types. It makes it clear that TYPE_CANONICAL is always 1) which is not > > defined on these. > > Sounds good (please split up the patch - I'm actually not looking at > it right now). OK, will try - the changes closely interact with each other. Disabling caluclation on incomplete types will probably cause fun because of the current code recurse where it should not. I will give it a try. > > > This seems to reduce number of canonical types computed to 1/3. > > We get bit more recursion in gimple_canonical_types_compatible_p > > and gimple_canonical_type_hash but only in MATCH_INCOMPLETE_TYPES mode > > that converges quite quickly. > > > > I know that it is not how other FEs works, but it is because they > > do have type equivalence notion that include TYPE_NAME so it is possible > > to determine TYPE_CANONICAL uniquely before the type is completed. > > The code was never intended to be "generic" it was LTO specific and > middle-end specific (for TBAA and useless_type_conversion_p). Frontends > (well, the C++ frontend) use TYPE_CANONICAL for their own idea of > "canonicalness". Yes, I am just trying to get point that instead of calculating a "nonsence" equivalence for incomplete types, we are better of to not calculate that at all (for LTO) since it is less confusing to ourself and permits sanity check. Yes, other FEs are different, since they know type names. > > > c) adds sanity checking > > > > - I can check that canonical_type_hash is not used for incomplete types > > (modulo ARRAY_TYPE that may appear as a field of complete structure) > > so the definition of cases we flip from complete to incomplete is > > catching everything > > Sounds good. > > > - I can check that alias is never used on types we do not define > > TYPE_CANONICAL for. This actually catch a case in ipa-icf-gimple that > > tires to compare alias classes of voidtypes. > > How do you verify that? (just using NULL TYPE_CANONICAL will end up > using alias-set zero I think) Because using these is bogus. With my patch VOID type do not get TYPE_CANONICAL and because icf-gimple compares VOID as a return value it started to think that no functions returning void can be equivlaent. I think it is better to avoid the bogus querries. > > > - I added check that we do not have prototypes of method types since > > I make difference between methods and functions (this is useful so > > we also match the BASETYPE argument) > > ? > > > d) drops TYPE_METHOD_BASETYPE hashing since it is not tested by > > gimple_canonical_types_compatible_p > > it also drops matching function type attributes that seems wrong as > > discused > > earlier. > > Sounds good. > > > > > On Firefox the canonical table changes from: > > [WPA] GIMPLE canonical type table: size 262139, 110992 elements, 2153232 > > searches, 808238 collisions (ratio: 0.375360) > > [WPA] GIMPLE canonical type pointer-map: 110992 elements, 4723435 searches > > to: > > [WPA] GIMPLE canonical type table: size 65521, 32676 elements, 1634147 > > searches, 474609 collisions (ratio: 0.290432) > > [WPA] GIMPLE canonical type pointer-map: 32676 elements, 2302719 searches > > > > I also checked that before throwing away all the functions/method types, the > > number of canonical types grown up to about 135k, so we seem to have 20-30% > > increase in precision. > > Can you highlight some cases please? I'd be interested to compare just > the change to add following pointers (so that part should be split out > of the patch at least). I will try to. As i said splitting is bit tricky area. > > > Code quality does not seem to be affected too much, > > which I suppose is partly thanks to that tree-ssa-alias.c pointer hack. My > > main point was to cleanup the hack about comparing only TYPE_CODE of > > pointer_type and make more sense of the whole machinery. > > Well, TYPE_CODE was supposed to mimic what you do explicitely now. I'm > curious when the recursion determines incompatibility but the TYPE_CODE > is equal. What cases are those? > > How do you handle void * vs. any other pointer type? For cross-language > LTO I think we need to treat those compatible. At least void * is > equal to struct Foo * (with incomplete Foo). Well, if you would force this rule for canonical type calculation, then by transitivity we could make no difference between pointers at all. I think the only way to enforce such non-transitive rules is via alias sets. Just like alias set 0 alias with everything without really degenerating every canonical type to a single type. > > > Bootstrapped/regtested x86_64-linux with LTO and also tested on Firefox. > > ppc64 > > build in progress. OK? > > Not looking at the patch - please split it up into small pieces so we > can bisect in case of problems. This is a tricky area, esp. considering > cross-language LTO. We might be not conservative enough with > canonical types (given the get_alias_set pointer handling). Yep, i looked into the pointer handling hack. Thanks for looking into this. I know it is a tricky area. Honza
