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

[Patrick Palka <ppalka@redhat.com>]

On Thu, 7 Jul 2022, Jonathan Wakely via Gcc-patches 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.

Rather than giving the trait a different name from __type_pack_element,
I wonder if we could just special case cp_parser_trait to expect <>
instead of parens for this trait?

Btw the frontend recently got a generic TRAIT_TYPE tree code, which gets
rid of much of the boilerplate of adding a new type-yielding built-in
trait, see e.g. cp-trait.def.

> 
> 
> 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 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).
> 
> 
> 
> FIXME 3:This change regresses diagnostics from std::tuple_element
> because as well as the existing:
> 
> tuple:1357: error: static assertion failed: tuple index must be in range
> 
> we now also get:
> 
> bits/utility.h:231: error: '__builtin_type_pack_element' index is out of range
> 
> which is not very user-friendly.
> 
> Maybe that should not mention the built-in by name, and just say
> something generic like "out of range index into type pack". Or maybe
> diagnose it as std::_Nth_type_t, like I plan to mangle it. That would be
> a bit confusing for anybody using the built-in directly, but I'm sure
> they can live with it - they're already using a non-portable intrinsic.
> 
> That still means two errors where we used to only print one though.
> Maybe the library needs to try harder to not let invalid indices reach
> the built-in. Currently we have:
> 
>   template<size_t __i, typename... _Types>
>     struct tuple_element<__i, tuple<_Types...>>
>     {
>       static_assert(__i < sizeof...(_Types), "tuple index must be in range");
> 
>       using type = _Nth_type_t<__i, _Types...>;
>     };
> 
> And _Nth_type_t is an alias for a type defined using the built-in.
> 
> Maybe I need to add another level of indirection (losing some of the
> compile-time improvements that the built-in is supposed to provide) or
> use concepts to constrain _Nth_type_t (which doesn't help pre-C++20).
> 
> This seems like another case where the compiler should just stop when a
> static assert fails. The whole point of that assertion is that what
> follows doesn't make sense unless it passes.
> 
> 
> Suggestions for how to fix these issues are welcome, I think I've gone
> as far as I can for now.
> 
> 
> -- >8 --
> 
> Add __builtin_type_pack_element so that std::tuple_element and
> std::variant_alternative can be implemented efficiently, without
> recursive class template instantiations.
> 
> The name is intended to be similar to Clang's __type_pack_element<>
> built-in which has the same behaviour, but uses template syntax instead
> of function-call syntax.
> 
> The libstdc++ headers can be updated to use this new built-in, or
> Clang's equivalent. Until the FIXME in mangle.cc:write_type is fixed
> (i.e. mangling for the built-in is added) we can't defined the
> _Nth_type_t alias template to use the built-in directly, because
> function templates that use the alias would need to mangle the built-in.
> I suggest mangling it as typename _Nth_type<N, T...>::type which will be
> backwards compatible with symbol names from GCC 12 and Clang.
> 
> 	PR c++/100157
> 
> gcc/c-family/ChangeLog:
> 
> 	* c-common.cc (c_common_reswords): Add
> 	__builtin_type_pack_element.
> 	* c-common.h (enum rid): Add RID_TYPE_PACK_ELEMENT.
> 
> gcc/cp/ChangeLog:
> 
> 	* constraint.cc (diagnose_trait_expr): Add
> 	CPTK_TYPE_PACK_ELEMENT to switch.
> 	* cp-objcp-common.cc (names_builtin_p): Add
> 	RID_TYPE_PACK_ELEMENT to switch.
> 	(cp_common_init_ts): Mark TYPE_PACK_ELEMENT as not having a
> 	common member.
> 	* cp-tree.def (TYPE_PACK_ELEMENT): Define tree code.
> 	* cp-tree.h (enum cp_trait_kind): Add CPTK_TYPE_PACK_ELEMENT.
> 	(TYPE_PACK_ELEMENT_ARGS): Define.
> 	(finish_type_pack_element): Declare.
> 	* error.cc (dump_type): Add TYPE_PACK_ELEMENT to switch.
> 	(dump_type_prefix): Likewise.
> 	(dump_type_suffix): Likewise.
> 	* mangle.cc (write_type): Likewise.
> 	* parser.cc (cp_keyword_starts_decl_specifier_p): Add
> 	RID_TYPE_PACK_ELEMENT to switch.
> 	(cp_parser_trait_expr): Likewise. Parse its arguments and call
> 	finish_type_pack_element.
> 	(cp_parser_simple_type_specifier): Add RID_TYPE_PACK_ELEMENT to
> 	switch.
> 	* pt.cc (for_each_template_parm_r): Add TYPE_PACK_ELEMENT to
> 	switch.
> 	(tsubst): Likewise.
> 	(unify): Likewise.
> 	(dependent_type_p_r): A TYPE_PACK_ELEMENT is dependent.
> 	* semantics.cc (finish_type_pack_element): New function.
> 
> gcc/ChangeLog:
> 
> 	* doc/extend.texi (Type Traits): Document new built-in.
> 
> libstdc++-v3/ChangeLog:
> 
> 	* include/bits/utility.h (_Nth_type_t): New alias template using
> 	built-ins when available.
> 	* include/std/tuple: Use _Nth_type_t instead of _Nth_type.
> 	* include/std/variant: Likewise.
> 	* testsuite/20_util/tuple/element_access/get_neg.cc: Prune
> 	additional errors from the new built-in.
> 
> gcc/testsuite/ChangeLog:
> 
> 	* g++.dg/ext/type_pack_element1.C: New test.
> 	* g++.dg/ext/type_pack_element2.C: New test.
> ---
>  gcc/c-family/c-common.cc                      |  1 +
>  gcc/c-family/c-common.h                       |  1 +
>  gcc/cp/constraint.cc                          |  1 +
>  gcc/cp/cp-objcp-common.cc                     |  2 +
>  gcc/cp/cp-tree.def                            |  4 ++
>  gcc/cp/cp-tree.h                              |  6 +++
>  gcc/cp/error.cc                               | 16 +++++++
>  gcc/cp/mangle.cc                              |  5 +++
>  gcc/cp/parser.cc                              | 39 ++++++++++++++--
>  gcc/cp/pt.cc                                  | 18 ++++++--
>  gcc/cp/semantics.cc                           | 44 +++++++++++++++++++
>  gcc/doc/extend.texi                           |  6 +++
>  gcc/testsuite/g++.dg/ext/type_pack_element1.C | 26 +++++++++++
>  gcc/testsuite/g++.dg/ext/type_pack_element2.C | 31 +++++++++++++
>  libstdc++-v3/include/bits/utility.h           | 26 +++++++++++
>  libstdc++-v3/include/std/tuple                |  2 +-
>  libstdc++-v3/include/std/variant              | 24 +++++-----
>  .../20_util/tuple/element_access/get_neg.cc   |  1 +
>  18 files changed, 232 insertions(+), 21 deletions(-)
>  create mode 100644 gcc/testsuite/g++.dg/ext/type_pack_element1.C
>  create mode 100644 gcc/testsuite/g++.dg/ext/type_pack_element2.C
> 
> diff --git a/gcc/c-family/c-common.cc b/gcc/c-family/c-common.cc
> index 1b8e73f7bc5..655b571a4ee 100644
> --- a/gcc/c-family/c-common.cc
> +++ b/gcc/c-family/c-common.cc
> @@ -389,6 +389,7 @@ const struct c_common_resword c_common_reswords[] =
>    { "__builtin_shufflevector", RID_BUILTIN_SHUFFLEVECTOR, 0 },
>    { "__builtin_tgmath", RID_BUILTIN_TGMATH, D_CONLY },
>    { "__builtin_offsetof", RID_OFFSETOF, 0 },
> +  { "__builtin_type_pack_element", RID_TYPE_PACK_ELEMENT, D_CXXONLY },
>    { "__builtin_types_compatible_p", RID_TYPES_COMPATIBLE_P, D_CONLY },
>    { "__builtin_va_arg",	RID_VA_ARG,	0 },
>    { "__complex",	RID_COMPLEX,	0 },
> diff --git a/gcc/c-family/c-common.h b/gcc/c-family/c-common.h
> index c0900848965..e9d0864f2ba 100644
> --- a/gcc/c-family/c-common.h
> +++ b/gcc/c-family/c-common.h
> @@ -184,6 +184,7 @@ enum rid
>    RID_IS_UNION,                RID_UNDERLYING_TYPE,
>    RID_IS_ASSIGNABLE,           RID_IS_CONSTRUCTIBLE,
>    RID_IS_NOTHROW_ASSIGNABLE,   RID_IS_NOTHROW_CONSTRUCTIBLE,
> +  RID_TYPE_PACK_ELEMENT,
>  
>    /* C++11 */
>    RID_CONSTEXPR, RID_DECLTYPE, RID_NOEXCEPT, RID_NULLPTR, RID_STATIC_ASSERT,
> diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
> index 591155cee22..f7bd189ae47 100644
> --- a/gcc/cp/constraint.cc
> +++ b/gcc/cp/constraint.cc
> @@ -3690,6 +3690,7 @@ diagnose_trait_expr (tree expr, tree args)
>      case CPTK_BASES:
>      case CPTK_DIRECT_BASES:
>      case CPTK_UNDERLYING_TYPE:
> +    case CPTK_TYPE_PACK_ELEMENT:
>        /* We shouldn't see these non-expression traits.  */
>        gcc_unreachable ();
>      /* We deliberately omit the default case so that when adding a new
> diff --git a/gcc/cp/cp-objcp-common.cc b/gcc/cp/cp-objcp-common.cc
> index 0b70d5567e4..bac6b5a6214 100644
> --- a/gcc/cp/cp-objcp-common.cc
> +++ b/gcc/cp/cp-objcp-common.cc
> @@ -461,6 +461,7 @@ names_builtin_p (const char *name)
>      case RID_IS_ASSIGNABLE:
>      case RID_IS_CONSTRUCTIBLE:
>      case RID_UNDERLYING_TYPE:
> +    case RID_TYPE_PACK_ELEMENT:
>        return true;
>      default:
>        break;
> @@ -517,6 +518,7 @@ cp_common_init_ts (void)
>    MARK_TS_TYPE_NON_COMMON (TEMPLATE_TEMPLATE_PARM);
>    MARK_TS_TYPE_NON_COMMON (TEMPLATE_TYPE_PARM);
>    MARK_TS_TYPE_NON_COMMON (TYPE_PACK_EXPANSION);
> +  MARK_TS_TYPE_NON_COMMON (TYPE_PACK_ELEMENT);
>  
>    /* Statements.  */
>    MARK_TS_EXP (CLEANUP_STMT);
> diff --git a/gcc/cp/cp-tree.def b/gcc/cp/cp-tree.def
> index f9cbd339f19..6ea197f16af 100644
> --- a/gcc/cp/cp-tree.def
> +++ b/gcc/cp/cp-tree.def
> @@ -470,6 +470,10 @@ DEFTREECODE (DECLTYPE_TYPE, "decltype_type", tcc_type, 0)
>     UNDERLYING_TYPE_TYPE is the type in question.  */
>  DEFTREECODE (UNDERLYING_TYPE, "underlying_type", tcc_type, 0)
>  
> +/* A type designated by `__builtin_type_pack_element (n, type)'.
> +   TYPE_PACK_ELEMENT_ARGS contains the arguments.  */
> +DEFTREECODE (TYPE_PACK_ELEMENT, "builtin_type_pack_element", tcc_type, 0)
> +
>  /* A type designated by one of the bases type traits.
>     BASES_TYPE is the type in question.  */
>  DEFTREECODE (BASES, "bases", tcc_type, 0)
> diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
> index 2fde4f83b41..2430b0b94c1 100644
> --- a/gcc/cp/cp-tree.h
> +++ b/gcc/cp/cp-tree.h
> @@ -1393,6 +1393,7 @@ enum cp_trait_kind
>    CPTK_IS_TRIVIALLY_CONSTRUCTIBLE,
>    CPTK_IS_TRIVIALLY_COPYABLE,
>    CPTK_IS_UNION,
> +  CPTK_TYPE_PACK_ELEMENT,
>    CPTK_UNDERLYING_TYPE,
>    CPTK_IS_ASSIGNABLE,
>    CPTK_IS_CONSTRUCTIBLE,
> @@ -4789,6 +4790,10 @@ get_vec_init_expr (tree t)
>  #define UNDERLYING_TYPE_TYPE(NODE) \
>    (TYPE_VALUES_RAW (UNDERLYING_TYPE_CHECK (NODE)))
>  
> +/* The arguments for a TYPE_PACK_ELEMENT.  */
> +#define TYPE_PACK_ELEMENT_ARGS(NODE) \
> +  (TYPE_VALUES_RAW (TYPE_PACK_ELEMENT_CHECK (NODE)))
> +
>  /* The type in question for BASES.  */
>  #define BASES_TYPE(NODE) \
>    (TYPE_VALUES_RAW (BASES_CHECK (NODE)))
> @@ -7640,6 +7645,7 @@ extern cp_expr finish_id_expression		(tree, tree, tree,
>                                                   location_t);
>  extern tree finish_typeof			(tree);
>  extern tree finish_underlying_type	        (tree);
> +extern tree finish_type_pack_element	        (tree, tree);
>  extern tree calculate_bases                     (tree, tsubst_flags_t);
>  extern tree finish_bases                        (tree, bool);
>  extern tree calculate_direct_bases              (tree, tsubst_flags_t);
> diff --git a/gcc/cp/error.cc b/gcc/cp/error.cc
> index 94181e76d0e..1b6f4df51b9 100644
> --- a/gcc/cp/error.cc
> +++ b/gcc/cp/error.cc
> @@ -706,6 +706,20 @@ dump_type (cxx_pretty_printer *pp, tree t, int flags)
>        pp_cxx_right_paren (pp);
>        break;
>  
> +    case TYPE_PACK_ELEMENT:
> +      t = TYPE_PACK_ELEMENT_ARGS (t);
> +      pp_cxx_ws_string (pp, "__builtin_type_pack_element");
> +      pp_cxx_whitespace (pp);
> +      pp_cxx_left_paren (pp);
> +      dump_expr (pp, TREE_VALUE (t), flags & ~TFF_EXPR_IN_PARENS);
> +      for (tree arg = TREE_CHAIN (t); arg; arg = TREE_CHAIN (arg))
> +	{
> +	  pp_separate_with_comma (pp);
> +	  dump_type (pp, TREE_VALUE (arg), flags);
> +	}
> +      pp_cxx_right_paren (pp);
> +      break;
> +
>      case TYPE_PACK_EXPANSION:
>        dump_type (pp, PACK_EXPANSION_PATTERN (t), flags);
>        pp_cxx_ws_string (pp, "...");
> @@ -974,6 +988,7 @@ dump_type_prefix (cxx_pretty_printer *pp, tree t, int flags)
>      case UNDERLYING_TYPE:
>      case DECLTYPE_TYPE:
>      case TYPE_PACK_EXPANSION:
> +    case TYPE_PACK_ELEMENT:
>      case FIXED_POINT_TYPE:
>      case NULLPTR_TYPE:
>        dump_type (pp, t, flags);
> @@ -1098,6 +1113,7 @@ dump_type_suffix (cxx_pretty_printer *pp, tree t, int flags)
>      case UNDERLYING_TYPE:
>      case DECLTYPE_TYPE:
>      case TYPE_PACK_EXPANSION:
> +    case TYPE_PACK_ELEMENT:
>      case FIXED_POINT_TYPE:
>      case NULLPTR_TYPE:
>        break;
> diff --git a/gcc/cp/mangle.cc b/gcc/cp/mangle.cc
> index 75388e99bfd..fbaed426940 100644
> --- a/gcc/cp/mangle.cc
> +++ b/gcc/cp/mangle.cc
> @@ -2393,6 +2393,11 @@ write_type (tree type)
>  	      sorry ("mangling %<__underlying_type%>");
>  	      break;
>  
> +	    case TYPE_PACK_ELEMENT:
> +	      /* FIXME: Mangle as std::_Nth_type<N, T...>::type.  */
> +	      sorry ("mangling %<__builtin_type_pack_element%>");
> +	      break;
> +
>  	    case LANG_TYPE:
>  	      /* fall through.  */
>  
> diff --git a/gcc/cp/parser.cc b/gcc/cp/parser.cc
> index bf9ea3685f8..8f0f0331d4f 100644
> --- a/gcc/cp/parser.cc
> +++ b/gcc/cp/parser.cc
> @@ -1142,6 +1142,7 @@ cp_keyword_starts_decl_specifier_p (enum rid keyword)
>        /* C++11 extensions.  */
>      case RID_DECLTYPE:
>      case RID_UNDERLYING_TYPE:
> +    case RID_TYPE_PACK_ELEMENT:
>      case RID_CONSTEXPR:
>        /* C++20 extensions.  */
>      case RID_CONSTINIT:
> @@ -10966,6 +10967,10 @@ cp_parser_trait_expr (cp_parser* parser, enum rid keyword)
>      case RID_UNDERLYING_TYPE:
>        kind = CPTK_UNDERLYING_TYPE;
>        break;
> +    case RID_TYPE_PACK_ELEMENT:
> +      kind = CPTK_TYPE_PACK_ELEMENT;
> +      variadic = true;
> +      break;
>      case RID_BASES:
>        kind = CPTK_BASES;
>        break;
> @@ -11001,10 +11006,24 @@ cp_parser_trait_expr (cp_parser* parser, enum rid keyword)
>    matching_parens parens;
>    parens.require_open (parser);
>  
> -  {
> -    type_id_in_expr_sentinel s (parser);
> -    type1 = cp_parser_type_id (parser);
> -  }
> +  if (kind == CPTK_TYPE_PACK_ELEMENT)
> +    {
> +      cp_expr e = cp_parser_constant_expression (parser, 0, nullptr, true);
> +      if (!cp_lexer_next_token_is (parser->lexer, CPP_COMMA))
> +	{
> +	  location_t err_loc = cp_lexer_peek_token (parser->lexer)->location;
> +	  err_loc = make_location (err_loc, start_loc, err_loc);
> +	  error_at (err_loc, "%<__builtin_type_pack_element%> requires"
> +			      " one or more type arguments");
> +	  return error_mark_node;
> +	}
> +      type1 = e.get_value (); // actually a constant-expression, not a type
> +    }
> +  else
> +    {
> +      type_id_in_expr_sentinel s (parser);
> +      type1 = cp_parser_type_id (parser);
> +    }
>  
>    if (type1 == error_mark_node)
>      return error_mark_node;
> @@ -11054,6 +11073,8 @@ cp_parser_trait_expr (cp_parser* parser, enum rid keyword)
>      {
>      case CPTK_UNDERLYING_TYPE:
>        return cp_expr (finish_underlying_type (type1), trait_loc);
> +    case CPTK_TYPE_PACK_ELEMENT:
> +      return cp_expr (finish_type_pack_element (type1, type2), trait_loc);
>      case CPTK_BASES:
>        return cp_expr (finish_bases (type1, false), trait_loc);
>      case CPTK_DIRECT_BASES:
> @@ -19571,6 +19592,7 @@ cp_parser_type_specifier (cp_parser* parser,
>       char16_t
>       char32_t
>       __underlying_type ( type-id )
> +     __builtin_type_pack_element ( constant-expression , type-id , [opt] )
>  
>     C++17 extension:
>  
> @@ -19783,6 +19805,15 @@ cp_parser_simple_type_specifier (cp_parser* parser,
>  
>        return type;
>  
> +    case RID_TYPE_PACK_ELEMENT:
> +      type = cp_parser_trait_expr (parser, RID_TYPE_PACK_ELEMENT);
> +      if (decl_specs)
> +	cp_parser_set_decl_spec_type (decl_specs, type,
> +				      token,
> +				      /*type_definition_p=*/false);
> +
> +      return type;
> +
>      case RID_BASES:
>      case RID_DIRECT_BASES:
>        type = cp_parser_trait_expr (parser, token->keyword);
> diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc
> index 8672da123f4..590b3eccc84 100644
> --- a/gcc/cp/pt.cc
> +++ b/gcc/cp/pt.cc
> @@ -10592,6 +10592,7 @@ for_each_template_parm_r (tree *tp, int *walk_subtrees, void *d)
>      case TYPEOF_TYPE:
>      case DECLTYPE_TYPE:
>      case UNDERLYING_TYPE:
> +    case TYPE_PACK_ELEMENT:
>        if (pfd->include_nondeduced_p
>  	  && for_each_template_parm (TYPE_VALUES_RAW (t), fn, data,
>  				     pfd->visited,
> @@ -16430,6 +16431,15 @@ tsubst (tree t, tree args, tsubst_flags_t complain, tree in_decl)
>  	return finish_underlying_type (type);
>        }
>  
> +    case TYPE_PACK_ELEMENT:
> +      {
> +	tree subst_args = tsubst (TYPE_PACK_ELEMENT_ARGS (t), args,
> +				  complain, in_decl);
> +	tree pack_index = TREE_VALUE (subst_args);
> +	tree types = TREE_CHAIN (subst_args);
> +	return finish_type_pack_element (pack_index, types);
> +      }
> +
>      case TYPE_ARGUMENT_PACK:
>      case NONTYPE_ARGUMENT_PACK:
>        return tsubst_argument_pack (t, args, complain, in_decl);
> @@ -24829,8 +24839,9 @@ unify (tree tparms, tree targs, tree parm, tree arg, int strict,
>      case TYPEOF_TYPE:
>      case DECLTYPE_TYPE:
>      case UNDERLYING_TYPE:
> +    case TYPE_PACK_ELEMENT:
>        /* Cannot deduce anything from TYPEOF_TYPE, DECLTYPE_TYPE,
> -	 or UNDERLYING_TYPE nodes.  */
> +	 UNDERLYING_TYPE, or TYPE_PACK_ELEMENT nodes.  */
>        return unify_success (explain_p);
>  
>      case ERROR_MARK:
> @@ -27405,12 +27416,13 @@ dependent_type_p_r (tree type)
>  	       (INNERMOST_TEMPLATE_ARGS (CLASSTYPE_TI_ARGS (type)))))
>      return true;
>  
> -  /* All TYPEOF_TYPEs, DECLTYPE_TYPEs, and UNDERLYING_TYPEs are
> +  /* All these are
>       dependent; if the argument of the `typeof' expression is not
>       type-dependent, then it should already been have resolved.  */
>    if (TREE_CODE (type) == TYPEOF_TYPE
>        || TREE_CODE (type) == DECLTYPE_TYPE
> -      || TREE_CODE (type) == UNDERLYING_TYPE)
> +      || TREE_CODE (type) == UNDERLYING_TYPE
> +      || TREE_CODE (type) == TYPE_PACK_ELEMENT)
>      return true;
>  
>    /* A template argument pack is dependent if any of its packed
> diff --git a/gcc/cp/semantics.cc b/gcc/cp/semantics.cc
> index 2344b5eea00..36eff75ed45 100644
> --- a/gcc/cp/semantics.cc
> +++ b/gcc/cp/semantics.cc
> @@ -4418,6 +4418,50 @@ finish_underlying_type (tree type)
>    return underlying_type;
>  }
>  
> +/* Implement the __builtin_type_pack_element keyword: Return the type
> +   at index N in TYPES..., suitable for use as a type-specifier.  */
> +
> +tree
> +finish_type_pack_element (tree n, tree types)
> +{
> +  if (n == error_mark_node
> +      || types == error_mark_node)
> +    return error_mark_node;
> +
> +  if (processing_template_decl)
> +    {
> +      if (value_dependent_expression_p (n) || uses_template_parms (types))
> +	{
> +	  tree t = cxx_make_type (TYPE_PACK_ELEMENT);
> +	  TYPE_PACK_ELEMENT_ARGS (t) = tree_cons (NULL_TREE, n, types);
> +	  return t;
> +	}
> +    }
> +
> +  n = fold_non_dependent_expr (n);
> +
> +  if (!INTEGRAL_TYPE_P (TREE_TYPE (n)) || TREE_CODE (n) != INTEGER_CST)
> +    {
> +      error ("%<__builtin_type_pack_element%> index is not an integral"
> +	     " constant");
> +      return error_mark_node;
> +    }
> +
> +  HOST_WIDE_INT lunroll = tree_to_shwi (n);
> +  if (lunroll < 0 || lunroll >= list_length (types))
> +    {
> +      error ("%<__builtin_type_pack_element%> index is out of range");
> +      return error_mark_node;
> +    }
> +
> +  unsigned index = (unsigned)lunroll;
> +  while (index-- > 0 && types != NULL_TREE)
> +    types = TREE_CHAIN (types);
> +  if (types == NULL_TREE)
> +    return error_mark_node;
> +  return TREE_VALUE (types);
> +}
> +
>  /* Implement the __direct_bases keyword: Return the direct base classes
>     of type.  */
>  
> diff --git a/gcc/doc/extend.texi b/gcc/doc/extend.texi
> index dfbe33ac652..5f0f39fe72e 100644
> --- a/gcc/doc/extend.texi
> +++ b/gcc/doc/extend.texi
> @@ -25201,6 +25201,12 @@ definition, expands to a template argument pack containing integers
>  from @code{0} to @code{length-1}.  This is provided for efficient
>  implementation of @code{std::make_integer_sequence}.
>  
> +@item __builtin_type_pack_element (n, types...)
> +The Nth type in the list of types.
> +This is provided for efficient
> +implementation of @code{std::tuple_element} and similar.
> +Requires: 0 @leq{} @code{n} < number of type arguments.
> +
>  @end table
>  
>  
> diff --git a/gcc/testsuite/g++.dg/ext/type_pack_element1.C b/gcc/testsuite/g++.dg/ext/type_pack_element1.C
> new file mode 100644
> index 00000000000..cc4b6b4b67f
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/ext/type_pack_element1.C
> @@ -0,0 +1,26 @@
> +// { dg-do compile { target c++11 } }
> +
> +template<class, class> struct is_same { static constexpr bool value = false; };
> +template<class T> struct is_same<T,T> { static constexpr bool value = true; };
> +
> +static_assert( is_same<__builtin_type_pack_element(0, int), int>::value, "" );
> +static_assert( is_same<__builtin_type_pack_element(0, long), long>::value, "" );
> +static_assert( is_same<__builtin_type_pack_element(1, float, char, int), char>::value, "" );
> +
> +using T = __builtin_type_pack_element(sizeof('0'), int, int);
> +
> +template<int N, class... T>
> +using Nth_type = __builtin_type_pack_element(N, T...);
> +
> +static_assert( is_same<Nth_type<0, int>, int>::value, "" );
> +static_assert( is_same<Nth_type<0, long>, long>::value, "" );
> +static_assert( is_same<Nth_type<1, float, char, int>, char>::value, "" );
> +
> +template<int N>
> +struct Nth_type_class_template
> +{
> +  using type = __builtin_type_pack_element(N, int, void, char, float, long);
> +};
> +
> +static_assert( is_same<typename Nth_type_class_template<0>::type, int>::value, "" );
> +static_assert( is_same<typename Nth_type_class_template<1>::type, void>::value, "" );
> diff --git a/gcc/testsuite/g++.dg/ext/type_pack_element2.C b/gcc/testsuite/g++.dg/ext/type_pack_element2.C
> new file mode 100644
> index 00000000000..04040e0e84f
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/ext/type_pack_element2.C
> @@ -0,0 +1,31 @@
> +// { dg-do compile { target c++11 } }
> +// { dg-options -w }
> +
> +using X1 = __builtin_type_pack_element(1);  // { dg-error "one or more type" }
> +using X2 = __builtin_type_pack_element(1, 1); // { dg-error "expected type" }
> +int i;
> +using X3 = __builtin_type_pack_element(1, i); // { dg-error "does not name a type" }
> +using X4 = __builtin_type_pack_element(1, int); // { dg-error "out of range" }
> +
> +using X5 = __builtin_type_pack_element(-1, int); // { dg-error "out of range" }
> +using X6 = __builtin_type_pack_element(nullptr, int); // { dg-error "integral" }
> +
> +template<int N, class T>
> +struct uninstantiated_template
> +{
> +  using X = __builtin_type_pack_element(2, int); // { dg-error "out of range" }
> +  using Y = __builtin_type_pack_element(2, T);   // { dg-bogus "out of range" }
> +  using Z = __builtin_type_pack_element(N, int); // { dg-bogus "." }
> +};
> +
> +
> +template<int N, class T>
> +struct instantiated_template
> +{
> +  using Y = __builtin_type_pack_element(2, T); // { dg-error "out of range" }
> +  using Z = __builtin_type_pack_element(N, T); // { dg-error "out of range" }
> +};
> +
> +using Y = typename instantiated_template<0, int>::Y;
> +using Z = typename instantiated_template<1, int>::Z;
> +// { dg-prune-output "invalid combination of multiple type-specifiers" }
> diff --git a/libstdc++-v3/include/bits/utility.h b/libstdc++-v3/include/bits/utility.h
> index e0e40309a6d..0b105e0df1b 100644
> --- a/libstdc++-v3/include/bits/utility.h
> +++ b/libstdc++-v3/include/bits/utility.h
> @@ -224,6 +224,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>  #endif // C++17
>  #endif // C++14
>  
> +#if __has_builtin(__builtin_type_pack_element) // GCC
> +
> +  template<size_t _Np, typename... _Types>
> +    struct _Nth_type
> +    { using type = __builtin_type_pack_element(_Np, _Types...); };
> +
> +  // FIXME: use built-in directly, but requires mangling for the built-in.
> +  template<size_t _Np, typename... _Types>
> +    using _Nth_type_t = typename _Nth_type<_Np, _Types...>::type;
> +
> +#elif __has_builtin(__type_pack_element) // Clang
> +
> +  template<size_t _Np, typename... _Types>
> +    struct _Nth_type
> +    { using type = __type_pack_element<_Np, _Types...>; };
> +
> +  // Defined this way to keep the mangling compatible.
> +  template<size_t _Np, typename... _Types>
> +    using _Nth_type_t = typename _Nth_type<_Np, _Types...>::type;
> +
> +#else // Pure C++ fallback
> +
>    template<size_t _Np, typename... _Types>
>      struct _Nth_type
>      { };
> @@ -263,6 +285,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>      { using type = _Tp1; };
>  #endif
>  
> +  template<size_t _Np, typename... _Types>
> +    using _Nth_type_t = typename _Nth_type<_Np, _Types...>::type;
> +#endif // __has_builtin(__builtin_type_pack_element)
> +
>  _GLIBCXX_END_NAMESPACE_VERSION
>  } // namespace
>  
> diff --git a/libstdc++-v3/include/std/tuple b/libstdc++-v3/include/std/tuple
> index 6d0060a191c..8ff1ab42d20 100644
> --- a/libstdc++-v3/include/std/tuple
> +++ b/libstdc++-v3/include/std/tuple
> @@ -1356,7 +1356,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>      {
>        static_assert(__i < sizeof...(_Types), "tuple index must be in range");
>  
> -      using type = typename _Nth_type<__i, _Types...>::type;
> +      using type = _Nth_type_t<__i, _Types...>;
>      };
>  
>    template<size_t __i, typename _Head, typename... _Tail>
> diff --git a/libstdc++-v3/include/std/variant b/libstdc++-v3/include/std/variant
> index 5ff1e3edcdf..5cfdaf31e24 100644
> --- a/libstdc++-v3/include/std/variant
> +++ b/libstdc++-v3/include/std/variant
> @@ -98,7 +98,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>      {
>        static_assert(_Np < sizeof...(_Types));
>  
> -      using type = typename _Nth_type<_Np, _Types...>::type;
> +      using type = _Nth_type_t<_Np, _Types...>;
>      };
>  
>    template<size_t _Np, typename _Variant>
> @@ -324,7 +324,7 @@ namespace __variant
>      struct _Traits
>      {
>        static constexpr bool _S_default_ctor =
> -	  is_default_constructible_v<typename _Nth_type<0, _Types...>::type>;
> +	  is_default_constructible_v<_Nth_type_t<0, _Types...>>;
>        static constexpr bool _S_copy_ctor =
>  	  (is_copy_constructible_v<_Types> && ...);
>        static constexpr bool _S_move_ctor =
> @@ -352,8 +352,7 @@ namespace __variant
>        // The following nothrow traits are for non-trivial SMFs. Trivial SMFs
>        // are always nothrow.
>        static constexpr bool _S_nothrow_default_ctor =
> -	  is_nothrow_default_constructible_v<
> -	      typename _Nth_type<0, _Types...>::type>;
> +	  is_nothrow_default_constructible_v<_Nth_type_t<0, _Types...>>;
>        static constexpr bool _S_nothrow_copy_ctor = false;
>        static constexpr bool _S_nothrow_move_ctor =
>  	  (is_nothrow_move_constructible_v<_Types> && ...);
> @@ -645,7 +644,7 @@ namespace __variant
>  	      __variant::__get<__j>(*this) = __rhs_mem;
>  	    else
>  	      {
> -		using _Tj = typename _Nth_type<__j, _Types...>::type;
> +		using _Tj = _Nth_type_t<__j, _Types...>;
>  		if constexpr (is_nothrow_copy_constructible_v<_Tj>
>  			      || !is_nothrow_move_constructible_v<_Tj>)
>  		  __variant::__emplace<__j>(*this, __rhs_mem);
> @@ -697,7 +696,7 @@ namespace __variant
>  		  __variant::__get<__j>(*this) = std::move(__rhs_mem);
>  		else
>  		  {
> -		    using _Tj = typename _Nth_type<__j, _Types...>::type;
> +		    using _Tj = _Nth_type_t<__j, _Types...>;
>  		    if constexpr (is_nothrow_move_constructible_v<_Tj>)
>  		      __variant::__emplace<__j>(*this, std::move(__rhs_mem));
>  		    else
> @@ -870,7 +869,7 @@ namespace __variant
>        static constexpr size_t __index =
>  	sizeof...(_Variants) - sizeof...(__rest) - 1;
>  
> -      using _Variant = typename _Nth_type<__index, _Variants...>::type;
> +      using _Variant = _Nth_type_t<__index, _Variants...>;
>  
>        static constexpr int __do_cookie =
>  	__extra_visit_slot_needed<_Ret, _Variant> ? 1 : 0;
> @@ -932,8 +931,7 @@ namespace __variant
>  	std::index_sequence<__indices...>>
>      {
>        using _Next =
> -	  remove_reference_t<typename _Nth_type<sizeof...(__indices),
> -			     _Variants...>::type>;
> +	  remove_reference_t<_Nth_type_t<sizeof...(__indices), _Variants...>>;
>        using _Array_type =
>  	  _Multi_array<_Result_type (*)(_Visitor, _Variants...),
>  		       __dimensions...>;
> @@ -1374,7 +1372,7 @@ namespace __variant
>  	  = __detail::__variant::__accepted_index<_Tp, variant>;
>  
>        template<size_t _Np, typename = enable_if_t<(_Np < sizeof...(_Types))>>
> -	using __to_type = typename _Nth_type<_Np, _Types...>::type;
> +	using __to_type = _Nth_type_t<_Np, _Types...>;
>  
>        template<typename _Tp, typename = enable_if_t<__not_self<_Tp>>>
>  	using __accepted_type = __to_type<__accepted_index<_Tp>>;
> @@ -1511,7 +1509,7 @@ namespace __variant
>  	emplace(_Args&&... __args)
>  	{
>  	  namespace __variant = std::__detail::__variant;
> -	  using type = typename _Nth_type<_Np, _Types...>::type;
> +	  using type = _Nth_type_t<_Np, _Types...>;
>  	  // Provide the strong exception-safety guarantee when possible,
>  	  // to avoid becoming valueless.
>  	  if constexpr (is_nothrow_constructible_v<type, _Args...>)
> @@ -1551,7 +1549,7 @@ namespace __variant
>  	emplace(initializer_list<_Up> __il, _Args&&... __args)
>  	{
>  	  namespace __variant = std::__detail::__variant;
> -	  using type = typename _Nth_type<_Np, _Types...>::type;
> +	  using type = _Nth_type_t<_Np, _Types...>;
>  	  // Provide the strong exception-safety guarantee when possible,
>  	  // to avoid becoming valueless.
>  	  if constexpr (is_nothrow_constructible_v<type,
> @@ -1734,7 +1732,7 @@ namespace __variant
>  	  constexpr size_t __max = 11; // "These go to eleven."
>  
>  	  // The type of the first variant in the pack.
> -	  using _V0 = typename _Nth_type<0, _Variants...>::type;
> +	  using _V0 = _Nth_type_t<0, _Variants...>;
>  	  // The number of alternatives in that first variant.
>  	  constexpr auto __n = variant_size_v<remove_reference_t<_V0>>;
>  
> diff --git a/libstdc++-v3/testsuite/20_util/tuple/element_access/get_neg.cc b/libstdc++-v3/testsuite/20_util/tuple/element_access/get_neg.cc
> index 84e085ebfbf..6279e24ba79 100644
> --- a/libstdc++-v3/testsuite/20_util/tuple/element_access/get_neg.cc
> +++ b/libstdc++-v3/testsuite/20_util/tuple/element_access/get_neg.cc
> @@ -61,3 +61,4 @@ test03()
>  
>  // { dg-error "tuple index must be in range" "" { target *-*-* } 0 }
>  // { dg-prune-output "no type named 'type' in .*_Nth_type" }
> +// { dg-prune-output "'__builtin_type_pack_element' index is out of range" }
> -- 
> 2.36.1
> 
>