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

[Jakub Jelinek <jakub@redhat.com>]

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.

	Jakub