https://github.com/ilya-biryukov created https://github.com/llvm/llvm-project/pull/139730
Deduplicating types via standard C++ can be a huge compile-time hog, we have observed that on some of the large targets we have internally this can be up to 25%. This builtin can be used to improve compilation times in places where the template metaprogramming like this cannot be avoided. The lack of a release note is deliberate, there is a good chance we may want to remove this before release and instead go with a builtin that produces packs. To follow a discussion about a more sophisticated version of this builtin that would produce a pack directly and for generalizations about sorting types based on mangling, follow #106730 and https://discourse.llvm.org/t/rfc-adding-builtin-for-deduplicating-type-lists/80986. >From 837d8612193ecfc730aa8dd5bfc451db40cb2af8 Mon Sep 17 00:00:00 2001 From: Ilya Biryukov <ibiryu...@google.com> Date: Tue, 13 May 2025 15:17:05 +0200 Subject: [PATCH] [Clang] Add a builtin for efficient type deduplication Deduplicating types via standard C++ can be a huge compile-time hog, we have observed that on some of the large targets we have internally this can be up to 25%. This builtin can be used to improve compilation times in places where the template metaprogramming like this cannot be avoided. The lack of a release note is deliberate, there is a good chance we may want to remove this before release and instead go with a builtin that produces packs. To follow a discussion about a more sophisticated version of this builtin that would produce a pack directly and for generalizations about sorting types based on mangling, follow #106730 and https://discourse.llvm.org/t/rfc-adding-builtin-for-deduplicating-type-lists/80986. --- clang/include/clang/Basic/BuiltinTemplates.td | 5 ++ clang/lib/Sema/SemaTemplate.cpp | 27 +++++++ .../test/SemaTemplate/dedup-types-builtin.cpp | 75 +++++++++++++++++++ 3 files changed, 107 insertions(+) create mode 100644 clang/test/SemaTemplate/dedup-types-builtin.cpp diff --git a/clang/include/clang/Basic/BuiltinTemplates.td b/clang/include/clang/Basic/BuiltinTemplates.td index d46ce063d2f7e..49eaadb4e8920 100644 --- a/clang/include/clang/Basic/BuiltinTemplates.td +++ b/clang/include/clang/Basic/BuiltinTemplates.td @@ -50,3 +50,8 @@ def __builtin_common_type : BuiltinTemplate< Template<[Class<"TypeMember">], "HasTypeMember">, Class<"HasNoTypeMember">, Class<"Ts", /*is_variadic=*/1>]>; + +// template <template<class...> class Template, class ...Args> +def __builtin_dedup_types + : BuiltinTemplate<[Template<[Class<"", /*is_variadic=*/1>], "Template">, + Class<"Args", /*is_variadic=*/1>]>; diff --git a/clang/lib/Sema/SemaTemplate.cpp b/clang/lib/Sema/SemaTemplate.cpp index 94f4c1c46c1fb..47ea4a6714913 100644 --- a/clang/lib/Sema/SemaTemplate.cpp +++ b/clang/lib/Sema/SemaTemplate.cpp @@ -17,7 +17,9 @@ #include "clang/AST/DynamicRecursiveASTVisitor.h" #include "clang/AST/Expr.h" #include "clang/AST/ExprCXX.h" +#include "clang/AST/TemplateBase.h" #include "clang/AST/TemplateName.h" +#include "clang/AST/TypeOrdering.h" #include "clang/AST/TypeVisitor.h" #include "clang/Basic/Builtins.h" #include "clang/Basic/DiagnosticSema.h" @@ -3331,6 +3333,31 @@ checkBuiltinTemplateIdType(Sema &SemaRef, BuiltinTemplateDecl *BTD, QualType HasNoTypeMember = Converted[2].getAsType(); return HasNoTypeMember; } + case BTK__builtin_dedup_types: { + assert(Converted.size() == 2 && + "__builtin_dedup_types expects 2 arguments"); + TemplateArgument Tmpl = Converted[0]; + TemplateArgument Ts = Converted[1]; + assert(Tmpl.getKind() == clang::TemplateArgument::Template); + assert(Ts.getKind() == clang::TemplateArgument::Pack); + // Delay the computation until we can compute the final result. We choose + // not to remove the duplicates upfront before substitution to keep the code + // simple. + if (Tmpl.isDependent() || Ts.isDependent()) + return QualType(); + TemplateArgumentListInfo OutArgs; + llvm::SmallDenseSet<QualType> Seen; + // Synthesize a new template argument list, removing duplicates. + for (auto T : Ts.getPackAsArray()) { + assert(T.getKind() == clang::TemplateArgument::Type); + if (!Seen.insert(T.getAsType().getCanonicalType()).second) + continue; + OutArgs.addArgument(TemplateArgumentLoc( + T, SemaRef.Context.getTrivialTypeSourceInfo(T.getAsType()))); + } + return SemaRef.CheckTemplateIdType(Tmpl.getAsTemplate(), TemplateLoc, + OutArgs); + } } llvm_unreachable("unexpected BuiltinTemplateDecl!"); } diff --git a/clang/test/SemaTemplate/dedup-types-builtin.cpp b/clang/test/SemaTemplate/dedup-types-builtin.cpp new file mode 100644 index 0000000000000..608c73698fe18 --- /dev/null +++ b/clang/test/SemaTemplate/dedup-types-builtin.cpp @@ -0,0 +1,75 @@ +// RUN: %clang_cc1 %s -verify + +template <typename...> struct TypeList; + +// FIXME: better error message, note for the location of the builtin. +static_assert(__is_same( + __builtin_dedup_types<TypeList, int, int*, int, double, float>, + TypeList<int, int*, double, float>)); + +template <template<typename ...> typename Templ, typename ...Types> +struct Dependent { + using empty_list = __builtin_dedup_types<Templ>; + using same = __builtin_dedup_types<Templ, Types...>; + using twice = __builtin_dedup_types<Templ, Types..., Types...>; + using dep_only_types = __builtin_dedup_types<TypeList, Types...>; + using dep_only_template = __builtin_dedup_types<Templ, int, double, int>; +}; + +// Check the reverse condition to make sure we see an error and not accidentally produced dependent expression. +static_assert(!__is_same(Dependent<TypeList>::empty_list, TypeList<>)); // expected-error {{static assertion failed}} +static_assert(!__is_same(Dependent<TypeList>::same, TypeList<>)); // expected-error {{static assertion failed}} +static_assert(!__is_same(Dependent<TypeList>::twice, TypeList<>)); // expected-error {{static assertion failed}} +static_assert(!__is_same(Dependent<TypeList>::dep_only_types, TypeList<>)); // expected-error {{static assertion failed}} +static_assert(!__is_same(Dependent<TypeList>::dep_only_template, TypeList<int, double>)); // expected-error {{static assertion failed}} +static_assert(!__is_same(Dependent<TypeList, int*, double*, int*>::empty_list, TypeList<>)); // expected-error {{static assertion failed}} +static_assert(!__is_same(Dependent<TypeList, int*, double*, int*>::same, TypeList<int*, double*>)); // expected-error {{static assertion failed}} +static_assert(!__is_same(Dependent<TypeList, int*, double*, int*>::twice, TypeList<int*, double*>)); // expected-error {{static assertion failed}} +static_assert(!__is_same(Dependent<TypeList, int*, double*, int*>::dep_only_types, TypeList<int*, double*>)); // expected-error {{static assertion failed}} +static_assert(!__is_same(Dependent<TypeList, int*, double*, int*>::dep_only_template, TypeList<int, double>)); // expected-error {{static assertion failed}} + + +template <class ...T> +using Twice = TypeList<T..., T...>; + +// FIXME: move this test into a template, add a test that doing expansions outside of templates is an error. +static_assert(!__is_same(__builtin_dedup_types<Twice, int, double, int>, TypeList<int, double, int, double>)); // expected-error {{static assertion failed}} + +template <int...> struct IntList; +// Wrong kinds of template arguments. +// FIXME: make the error message below point at this file. +__builtin_dedup_types<IntList, int>* wrong_template; // expected-error@* {{template argument for non-type template parameter must be an expression}} + // expected-note@* {{template template argument has different template parameters than its corresponding template template parameter}} + // expected-note@-5 {{template parameter is declared here}} +__builtin_dedup_types<TypeList, 1, 2, 3>* wrong_template_args; // expected-error {{template argument for template type parameter must be a type}} + // expected-note@* {{template parameter from hidden source}} +__builtin_dedup_types<> not_enough_args; // expected-error {{too few template arguments}} + // expected-note@* {{template declaration from hidden source}} +__builtin_dedup_types missing_template_args; // expected-error {{use of template '__builtin_dedup_types' requires template arguments}} + // expected-note@* {{template declaration from hidden source}} + +// Make sure various canonical / non-canonical type representations do not affect results +// of the deduplication and the qualifiers do end up creating different types when C++ requires it. +using Int = int; +using CInt = const Int; +using IntArray = Int[10]; +using CIntArray = Int[10]; +using IntPtr = int*; +using CIntPtr = const int*; + +static_assert( + !__is_same( // expected-error {{static assertion failed}} + __builtin_dedup_types<TypeList, + Int, int, + const int, const Int, CInt, const CInt, + IntArray, Int[10], int[10], + const IntArray, const int[10], CIntArray, const CIntArray, + IntPtr, int*, + const IntPtr, int* const, + CIntPtr, const int*, + const IntPtr*, int*const*, + CIntPtr*, const int**, + const CIntPtr*, const int* const* + >, + TypeList<int, const int, int[10], const int [10], int*, int* const, const int*, int*const *, const int**, const int*const*>), + ""); _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
