Re: [PATCH] c++: Define built-in for std::tuple_element [PR100157]

[Jonathan Wakely <jwakely@redhat.com>]

On Thu, 7 Jul 2022 at 20:29, Jason Merrill <jason@redhat.com> wrote:
>
> On 7/7/22 13:14, Jonathan Wakely wrote:
> > This adds a new built-in to replace the recursive class template
> > instantiations done by traits such as std::tuple_element and
> > std::variant_alternative. The purpose is to select the Nth type from a
> > list of types, e.g. __builtin_type_pack_element(1, char, int, float) is
> > int.
> >
> > For a pathological example tuple_element_t<1000, tuple<2000 types...>>
> > the compilation time is reduced by more than 90% and the memory  used by
> > the compiler is reduced by 97%. In realistic examples the gains will be
> > much smaller, but still relevant.
> >
> > Clang has a similar built-in, __type_pack_element<N, T...>, but that's a
> > "magic template" built-in using <> syntax, which GCC doesn't support. So
> > this provides an equivalent feature, but as a built-in function using
> > parens instead of <>. I don't really like the name "type pack element"
> > (it gives you an element from a pack of types) but the semi-consistency
> > with Clang seems like a reasonable argument in favour of keeping the
> > name. I'd be open to alternative names though, e.g. __builtin_nth_type
> > or __builtin_type_at_index.
> >
> >
> > The patch has some problems though ...
> >
> > FIXME 1: Marek pointed out that this this ICEs:
> > template<class... T> using type = __builtin_type_pack_element(sizeof(T), T...);
> > type<int, char> c;
> >
> > The sizeof(T) expression is invalid, because T is an unexpanded pack,
> > but it's not rejected and instead crashes:
> >
> > ice.C: In substitution of 'template<class ... T> using type = __builtin_type_pack_element (sizeof (T), T ...) [with T = {int, char}]':
> > ice.C:2:15:   required from here
> > ice.C:1:63: internal compiler error: in dependent_type_p, at cp/pt.cc:27490
> >      1 | template<class... T> using type = __builtin_type_pack_element(sizeof(T), T...);
> >        |                                                               ^~~~~~~~~
> > 0xe13eea dependent_type_p(tree_node*)
> >          /home/jwakely/src/gcc/gcc/gcc/cp/pt.cc:27490
> > 0xeb1286 cxx_sizeof_or_alignof_type(unsigned int, tree_node*, tree_code, bool, bool)
> >          /home/jwakely/src/gcc/gcc/gcc/cp/typeck.cc:1912
> > 0xdf4fcc tsubst_copy_and_build(tree_node*, tree_node*, int, tree_node*, bool, bool)
> >          /home/jwakely/src/gcc/gcc/gcc/cp/pt.cc:20582
> > 0xdd9121 tsubst_tree_list(tree_node*, tree_node*, int, tree_node*)
> >          /home/jwakely/src/gcc/gcc/gcc/cp/pt.cc:15587
> > 0xddb583 tsubst(tree_node*, tree_node*, int, tree_node*)
> >          /home/jwakely/src/gcc/gcc/gcc/cp/pt.cc:16056
> > 0xddcc9d tsubst(tree_node*, tree_node*, int, tree_node*)
> >          /home/jwakely/src/gcc/gcc/gcc/cp/pt.cc:16436
> > 0xdd6d45 tsubst_decl
> >          /home/jwakely/src/gcc/gcc/gcc/cp/pt.cc:15038
> > 0xdd952a tsubst(tree_node*, tree_node*, int, tree_node*)
> >          /home/jwakely/src/gcc/gcc/gcc/cp/pt.cc:15668
> > 0xdfb9a1 instantiate_template(tree_node*, tree_node*, int)
> >          /home/jwakely/src/gcc/gcc/gcc/cp/pt.cc:21811
> > 0xdfc1b6 instantiate_alias_template
> >          /home/jwakely/src/gcc/gcc/gcc/cp/pt.cc:21896
> > 0xdd9796 tsubst(tree_node*, tree_node*, int, tree_node*)
> >          /home/jwakely/src/gcc/gcc/gcc/cp/pt.cc:15696
> > 0xdbaba5 lookup_template_class(tree_node*, tree_node*, tree_node*, tree_node*, int, int)
> >          /home/jwakely/src/gcc/gcc/gcc/cp/pt.cc:10131
> > 0xe4bac0 finish_template_type(tree_node*, tree_node*, int)
> >          /home/jwakely/src/gcc/gcc/gcc/cp/semantics.cc:3727
> > 0xd334c8 cp_parser_template_id
> >          /home/jwakely/src/gcc/gcc/gcc/cp/parser.cc:18458
> > 0xd429b0 cp_parser_class_name
> >          /home/jwakely/src/gcc/gcc/gcc/cp/parser.cc:25923
> > 0xd1ade9 cp_parser_qualifying_entity
> >          /home/jwakely/src/gcc/gcc/gcc/cp/parser.cc:7193
> > 0xd1a2c8 cp_parser_nested_name_specifier_opt
> >          /home/jwakely/src/gcc/gcc/gcc/cp/parser.cc:6875
> > 0xd4eefd cp_parser_template_introduction
> >          /home/jwakely/src/gcc/gcc/gcc/cp/parser.cc:31668
> > 0xd4f416 cp_parser_template_declaration_after_export
> >          /home/jwakely/src/gcc/gcc/gcc/cp/parser.cc:31840
> > 0xd2d60e cp_parser_declaration
> >          /home/jwakely/src/gcc/gcc/gcc/cp/parser.cc:15083
> >
> >
> > FIXME 2: I want to mangle __builtin_type_pack_element(N, T...) the same as
> > typename std::_Nth_type<N, T...>::type but I don't know how. Instead of
> > trying to fake the mangled string, it's probably better to build a decl
> > for that nested type, right? Any suggestions where to find something
> > similar I can learn from?
>
> The tricky thing is dealing with mangling compression, where we use a
> substitution instead of repeating a type; that's definitely easier if we
> actually have the type.

Yeah, that's what I discovered when trying to fudge it as
"19__builtin_type_pack_elementE" etc.

> So you'd probably want to have a declaration of std::_Nth_type to work
> with, and lookup_template_class to get the type of that specialization.
>   And then if it's complete, look up ...::type; if not, we could
> probably stuff a ...::type in its TYPE_FIELDS that would get clobbered
> if we actually instantiated the type...
>
> > The reason to mangle it that way is that it preserves the same symbol
> > names as the library produced in GCC 12, and that it will still produce
> > with non-GCC compilers (see the definitions of std::_Nth_type in the
> > library parts of the patch). If we don't do that then either we need to
> > ensure it never appears in a mangled name, or define some other
> > GCC-specific mangling for this built-in (e.g. we could just mangle it as
> > though it's a function, "19__builtin_type_pack_elementELm1EJDpT_E" or
> > something like that!). If we ensure it doesn't appear in mangled names
> > that means we still need to instantiate the _Nth_type class template,
> > rather than defining the alias template _Nth_type_t to use the built-in
> > directly.  That loses a little of the compilation performance gain that
> > comes from defining the built-in in the first place (although avoid the
> > recusrion is the biggest gain, which we'd still get).
>
> ...but this seems a lot simpler.

Yeah, it works fine, and if the built-in ever accidentally creeps into
a mangled name we get a sorry, not an incorrect mangling. OK, I'll
keep it simple.

I'll try Marek's fix for the ICE and will not worry about mangling for
now. We can revisit later if we decide to care more about it.