GIMPLE type system
GIMPLE IL type verifier
The GIMPLE IL type verifier is implemented in tree-cfg.cc, at it's core it tests that operations such as arithmetics and assignments operate on compatible types. This is checked by asking the useless_type_conversion_p predicate or the symmetric types_compatible_p predicate with the later defined in terms of the former if both directions hold. Generally when assigning A to B then the type of A should be trivially convertible to B (without a conversion operation).
useless_type_conversion_p builds on type sets formed by TYPE_CANONICAL recorded in each type node Types A and B are trivially convertible to each other (types_compatible_p) if they have the same TYPE_CANONICAL. useless_type_conversion_p allows trivial conversions in additional cases.
Useless_type_conversion_p uses TYPE_CANONICAL only for records types and recursive checking of structural equivalency for all other types. Historically TYPE_CANONICAL was only consistently set for record and union types so the middle-end couldn't rely on that for basic integer types or array types. For those the structural equality checks are spelled out in useless_type_conversion_p given they also only ever have a constant number of components while the number of components in record types is unbound and thus TYPE_CANONICAL provides a caching effect here.
Function types are another example with a non-constant number of components and we should rely on TYPE_CANONICAL there as we do compute that consistently but additional leeway may be needed to not make existing IL invalid that way. Note there's no TBAA required for function types (and pointer types are treated specially for TBAA).
For non-record/union types TYPE_CANONICAL and what useless_type_conversion_p spells out should not contradict itself. Meaning, the
inner_type = TYPE_MAIN_VARIANT (inner_type); outer_type = TYPE_MAIN_VARIANT (outer_type);
punning to TYPE_MAIN_VARIANT could have used the stronger punning to TYPE_CANONICAL (but TYPE_CANONICAL is NULL for TYPE_STRUCTURAL_EQUALITY_P types). That should also answer the first question to some extent - but the GIMPLE IL allows more conversions to be elided for basic types, even though they might get different alias sets when used in memory reference context. But useless_type_conversion_p is about rvalue conversions, you may not use useless_type_conversion_p to decide whether you can use an lvalue of type 'unsigned int' in place of one of type 'enum X' when accessing memory.
A conversion in GIMPLE IL is required when !useless_type_conversion_p, it can be a VIEW_CONVERT_EXPR if it's a bit-pattern preserving conversion (and the objects have the same size) or any other kind of conversion, including FIX_TRUNC_EXPR (float to int convert, etc.). The middle-end only ever _strip_ conversions created by the frontends that are useless, but is not "fixing up" frontend GENERIC (which has stricter type requirements than GIMPLE).
GIMPLE TBAA
Type based aliasing in the middle-end ensures that all types with the same TYPE_CANONICAL get the same alias-set assigned (see alias.cc). Frontends have the ability to override alias-sets with the TYPE_ALIAS_SET langhook, but other than the special aliases-everything zero this information is not carried over to the LTO frontend and link-time optimization. The LTO frontend re-computes TYPE_CANONICAL from scratch by determining structural equivalence classes from all types (see lto/lto-common.cc) based on gimple_canonical_types_compatible_p. This should never tear apart types into different sets that were unified by a language frontend (that would be a bug), so the GIMPLE type system is one that should be compatible with all language frontend constraints (for both TBAA and IL validity).
get_alias_set does not do any comparisons and relies on all types that are supposed to be the "same" with respect to TBAA to get a single get_alias_set query. The alias-set is stored in TYPE_ALIAS_SET of the leader of such group which is the TYPE_CANONICAL type of each of them.
In the middle end, TYPE_CANONICAL is not used for anything else than for computing alias sets and inside useless_type_conversion_p.
There two function for determining type compatiblity. useless_type_conversion_p is meant to use TYPE_CANONICAL (but does not for non-records for the reasons explained above) and gimple_canonical_types_compatible_p is for recomputing TYPE_CANONICAL for LTO. (it may have been moved from the LTO frontend since it was used for IPA devirt somehow.)
useless_type_conversion_p defines the type system in terms of a sub-type relationship (in terms of the operations allowed on the type). int(*)[3] is more specific than int(*)[] so the conversion from int(*)[3] to int(*)[] is useless, but the other direction is not. Two types are compatible if both directions are useless. So int(*)[3] and int(*)[] are not compatible (in contrast to C).
For TBAA one has to form equivalence classes, so int(*)[3] and int(*)[] should be in the same class (because both types could be used for memory accesses to the same pointer object). TBAA for arrays and vectors are put into the equivalence class of their component, that's something to keep in mind when marrying the TBAA and type system roles of TYPE_CANONICAL. There's similar treatment for pointers but it's not as simple as with arrays and vectors, see alias.cc:get_alias_set for a big comment on how TBAA of pointer lvalues is handled. Together with useless_type_conversion_p open-coding handling of pointer and array types this means we have some freedom with chosing TYPE_CANONICAL here, so by itself that int(*)[3] and int(*)[] are not types_compatible_p but share the same alias-set by means of special-casing pointer handling isn't a problem. But this also shows that TYPE_CANONICAL does not on its own (or does not need to) ensure TBAA is "correct". TYPE_CANONICAL _is_ the important bit for record and union types here, though.
TYPE_CANONICAL forms equivalence classes which are not big enough for C for TBAA (but almost because of the pointer skipping which essentially makes it almost large enough, with only corner cases related to FAMs or VLAs in struct remaining), but because it is also used for type_useless_conversion_p it can not be larger because then we may declare some conversions useless which are required. One reason why those might be required is between types of different size (?).
MU: I still do not quite get what went wrong in the Ada case. Somehow we must have removed as VIEW_CONVERT_EXPR because we now declared it useless, e.g. something similar to a conversion between:
int n = 3; struct foo { char buf[n]; } b; struct foo { char buf[3]; } a = b;
But why exactly did this cause a problem? Would the conversion call back into some Ada specific code which is now omitted? (and if only the total size of the struct is the issue, checking for this explicitly in type_useless_c_p would seem cheap)
Language Specialties
C
C has a type system based on a symmetric but non-transitive notion of type compatibility implemented by comptypes family of functions in the C FE. Those functions can also compute a relaxed version of type equivalency by ignoring specific aspects of the type judging types equivalent which are similar but not compatible according to C semantics (comptypes_equiv_p). The type equivalency computed in this way is the strictest possible which can be used for TBAA without causing wrong code. It is generally stricter than
- gimple_canonical_types_compatible_p, e.g. by recursing in pointers.
For tagged types, C traditionally distinguishes between inter and intra TU type compatibility. The equivalency relationship is based on the inter TU relationship which is more conservative (i.e. more types are compatible). For LTO and the middle-end, the inter TU type compatibility is relevant.
In C23, the intra TU compatibility became more similar to the inter TU compatibility and the FE started to set TYPE_CANONICAL for structures and unions. This assigns different TYPE_CANONICAL to certain types where LTO would assign the same, e.g. because gimple_canonical_types_compatible_p does not recursive into pointers while the C FE does and might see that the types are not compatible.
That C23 has more TYPE_CANONICAL sets than LTO re-assigns isn't be a problem, but there are/were corner cases where we end up with two types that C23 put into the same set in two different sets with LTO. Example: Any combination of the following types
struct foo { int x; char a[2]; }; int n = 2; struct foo { int x; char a[n]; }; struct foo { int x; char a[0]; }; struct foo { int x; char a[]; };
can not alias with LTO. One related bug is PR114713 and the corresponding test (the test is for C23 but it fails also with earlier versions when splitting up into two files as indicated by the comment). This is fixed by r14-11478-g73549be0a3c819b2ab78e0e973f5b4d41b9f4a2d and the preceding commit (which handles mode differences for related structures).
The C frontend does not currently use TYPE_CANONICAL for itself, unlike the C++ frontend. It could use it also as a cache to quickly determine when types are *not* compatible.
( But in principle, there is no problem changing all this in the C FE or even just setting STRUCTURAL_EQUALITY and computing the information in the middle end (but somehow I tried this originally and we then decided after discussion to set TYPE_CANONICAL instead). It would also not fix the problem with LTO where the middle end *does* compute it but not quite in the right way. Switching to setting alias sets also would not work, because those are not preserved for LTO. I guess we could set the alias set of all affected types to zero, but this would affect all structure/unions with array at the end and all types derived from it. )
The TYPE_ALIAS_SET language hook should be only ever used to make use of alias-set zero.
MU: The strategic question is whether TYPE_CANONICAL should stay as it is (reverting my patch also for 15 and finding another solution for TBAA in C in the middle end, probably by changing how alias sets are (re-)computed for such types) or whether TYPE_CANONICAL should determine TBAA and then useless_compatible_p would not fully rely on it but take into account other information.
The later seems more logical to me, because why have the detailed information about direction of useless conversion in the first place, when then computing it from TYPE_CANONICAL which can not possibly represent more detailed information (the relationship always must be symmetric, i.e. TC is the same or not). It could still be used to quickly decide that conversion is *not* useless if TYPE_CANONICAL is different and for the case TYPE_CANONICAL is the same one would need to check whether the last element is an array and whether the size of the last element is the same. If this is too slow, one maybe could have bit which caches this....
RB: I agree the later seems more logical, up to date we managed to have TBAA and compatibility requirements "match" for record/union types (those we fully rely on TYPE_CANONICAL in useless_type_conversion_p). The alternative would be to fully open-code that. The other alternative I have played with is to accept the fact that aggregate (record/union) values are just a collection of bytes and thus all that matters for compatibility of such value "assignments" is their size. There is only the size and bit-preserving VIEW_CONVERT_EXPR for such values and that's always "useless". There are consumers that interpret more into an aggregate assignment like SRA which attempts to hack it into pieces, ignoring padding, so a V_C_E<type-with-padding> (object-w/o-padding) = V_C_E<type-with-padding> (object-w/o-padding) would have different semantics to SRA (but I believe this is a bug in SRA). There is the Ada case where dropping a V_C_E is problematic - but ISTR Ada has V_C_Es between types of _different_ size, so that might be it. So if we had TYPE_CANONICAL fully specify only the TBAA sets we'd solve some problems (by streaming it to LTO bytecode we could preserve set membership by only ever merging full sets when we "recompute" the canonical type). I think an intermediate thing with useless_type_conversion_p comparing actual struct members like gimple_canonical_types_compatible_p would be overly expensive.
MU: I think one could possible go for some middle ground. If we keep the change to TYPE_CANONICAL, we could get old useless_type_conversion_p behavior back by checking TYPE_CANONICAL and in case there are identical, only checking for the size / bounds of the last member if is an array. Not sure if this is too expensive as one has to find the last member, but the logic would not be recursive. But maybe Ada does not even need this, and something even cheaper could be done.
RB: I do think walking all fields to find the last one is too expensive, comparing size would not work for VLAs since we cannot reliably see equivalence here. But maybe it's enough to reject mismatching constant size.
MU: Which brings me back to the question what is truly needed here... Why did Ada have an issue here? What would retaining a V_C_E fix for mismatching sizes? Or for matching sizes where this is known only at run-time (because one side is variable).
BTW: useless_type_conversion does not seem to consider the union case.
RB: It does, the RECORD case also handles the UNION case since we catch both with AGGREGATE_TYPE_P
MU: Right, in the C standard aggregate excludes unions, so I sometimes get confused
C++
The C++ frontend was the one that introduced TYPE_CANONICAL for its own use and it still uses it today.
Ada
The Ada frontend does not currently use TYPE_CANONICAL for itself, unlike the C++ frontend.