Re: [PATCH] middle-end/114931 - type_hash_canon and structual equality types

[Martin Uecker <uecker@tugraz.at>]

Am Freitag, dem 03.05.2024 um 19:30 +0200 schrieb Jakub Jelinek:
> On Fri, May 03, 2024 at 05:32:12PM +0200, Martin Uecker wrote:
> > Am Freitag, dem 03.05.2024 um 14:13 +0200 schrieb Richard Biener:
> > > TYPE_STRUCTURAL_EQUALITY_P is part of our type system so we have
> > > to make sure to include that into the type unification done via
> > > type_hash_canon.  This requires the flag to be set before querying
> > > the hash which is the biggest part of the patch.
> > 
> > I assume this does not affect structs / unions because they
> > do not make this mechanism of type unification (each tagged type
> > is a unique type), but only derived types that end up having
> > TYPE_STRUCTURAL_EQUALITY_P because they are constructed from
> > incomplete structs / unions before TYPE_CANONICAL is set.
> > 
> > I do not yet understand why this change is needed. Type
> > identity should not be affected by setting TYPE_CANONICAL, so
> > why do we need to keep such types separate?  I understand that we
> > created some inconsistencies, but I do not see why this change
> > is needed to fix it.  But I also haven't understood how we ended
> > up with a TYPE_CANONICAL having TYPE_STRUCTURAL_EQUALITY_P in
> > PR 114931 ...
> 
> So, the C23 situation before the r14-10045 change (not counting the
> r14-9763 change that was later reverted) was that sometimes TYPE_CANONICAL
> of a RECORD_TYPE/UNION_TYPE could change from self to a different
> RECORD_TYPE/UNION_TYPE and we didn't bother to adjust derived types.
> That was really dangerous, I think e.g. type alias set wasn't recomputed.
> 
> r14-10045 changed it to the non-ideal, but perhaps less wrong model,
> where we start with TYPE_STRUCTURAL_EQUALITY_P on incomplete types in C23
> and perhaps later on change them to !TYPE_STRUCTURAL_EQUALITY_P when
> the type is completed, and adjust TYPE_CANONICAL of some easily discoverable
> derived types but certainly not all.
> 
> Still, that change introduces something novel to the type system, namely
> that TYPE_CANONICAL can change on a type, even when it is just limited to
> the TYPE_STRUCTURAL_EQUALITY_P -> !TYPE_STRUCTURAL_EQUALITY_P kind of
> change and we never change one non-NULL TYPE_CANONICAL to a different one
> (ok, not counting the short lived TYPE_CANONICAL being initially set to
> self during make_node and then quickly adjusted in the callers).
> 
> One question is, could we for C23 somehow limit this for the most common
> case where people just forward declare some aggregate type and then soon
> after define it?  But guess the problematic counterexample there is
> struct S; // forward declare
> struct S *p; // create some derived types from it
> void foo (void)
> {
>   struct S { int s; };	// define the type in a different scope
> 			// (perhaps with a forward declaration as well)
>   struct S s;
>   use (&s);		// create derived types
> }
> struct S { int s; };	// define the type in the global scope to something
> 			// that matches previously defined struct S in
> 			// another scope
> So e.g. noting in the hash table that a particular type has been forward
> declared so far and using TYPE_STRUCTURAL_EQUALITY_P only if it has been
> forward declared in some other scope wouldn't work.
> 
> Another question is whether c_update_type_canonical can or should try to
> update TYPE_ALIAS_SET if TYPE_ALIAS_SET_KNOWN_P.  Or do we never cache
> alias sets for TYPE_STRUCTURAL_EQUALITY_P types?
> 
> Anyway, the ICE on the testcase is because alias.cc asserts that
> a !TYPE_STRUCTURAL_EQUALITY_P (type) has
> !TYPE_STRUCTURAL_EQUALITY_P (TYPE_CANONICAL (type)).
> 
> The possibilities to resolve that are either at c_update_type_canonical
> time try to find all the derived types rather than just some and recompute
> their TYPE_CANONICAL.  Guess we could e.g. just traverse the whole
> type_hash_table hash table and for each type see if it is in any way related
> to the type that is being changed and then recompute them.  Though,
> especially FUNCTION_TYPEs make that really ugly and furthermore it needs
> to be recomputed in the right order, basically in the derivation order.
> Without doing that, we'll have some TYPE_STRUCTURAL_EQUALITY_P derived
> types in the type_hash_table hash table; that is conservatively correct,
> but can result in worse code generation because of using alias set 0.
> 
> Another possibility is what Richi posted, essentially stop reusing
> derived types created from the time when the base type was incomplete
> when asking for a new derived type.  We'll get the TYPE_STRUCTURAL_EQUALITY_P
> derived types if they were created before the base type was completed
> when used directly (e.g. when it is a TREE_TYPE of some decl etc.), but
> when we ask for a new type we'd disregard the old type and create a new one.
> I'm not sure the patch is complete for that, because it doesn't adjust
> check_base_type, build_pointer_type_for_mode, build_reference_type_for_mode
> which don't use type_hash_canon but walk TYPE_NEXT_VARIANT list or
> TYPE_POINTER_TO or TYPE_REFERENCE_TO chains.  Though, maybe it is ok
> as is when c_update_type_canonical adjusts the pointer types
> and variant types, those will be adjusted and as soon as we hit the first
> ARRAY_TYPE/FUNCTION_TYPE or other type_canon_hash using derived types and
> they aren't shared but have a new one created, further derived
> pointer/qualified types will be based on the new ones, not the old ones.
> 
> Another possibility is what I wrote in the PR, ensure the
> !TYPE_STRUCTURAL_EQUALITY_P (type) ->
> !TYPE_STRUCTURAL_EQUALITY_P (TYPE_CANONICAL (type)) implication alias.cc
> relies on is held.  Without the complete update of all derived types or
> Richi's patch, there is always a chance that some TYPE_CANONICAL (...) =
> assignment will get a TYPE_STRUCTURAL_EQUALITY_P type which was created
> while the base type was incomplete.  So, we could just check for that
> case and use conservative type as well.  I.e. after each TYPE_CANONICAL
> (...) = ... (except the TYPE_CANONICAL (t) = t; cases which are always
> fine) add
>   if (TYPE_STRUCTURAL_EQUALITY_P (TYPE_CANONICAL (type)))
>     SET_TYPE_STRUCTURAL_EQUALITY (type);
> That is conservatively fine.
> 
> And yet another option is to change alias.cc to handle the
> TYPE_STRUCTURAL_EQUALITY_P (TYPE_CANONICAL (type)) case the same
> as TYPE_STRUCTURAL_EQUALITY_P (type) instead of asserting it is not
> ok.
> 
> I think we'd get best generated code if we managed to update all derived
> types, Richi's patch is the second and the other changes result in even
> worse code.


A change that is not optimal but would avoid a lot of trouble is to
only use the tag of the struct for computing a TYPE_CANONICAL, which
could then be set already for incomplete types and never needs to
change again. We would not differentiate between different struct
types with the same tag for aliasing analysis, but in most cases
I would expect different structs to have a different tag.

Martin