[Clang] Add a builtin that deduplicate types into a pack #106730
Conversation
|
✅ With the latest revision this PR passed the C/C++ code formatter. |
|
RFC for this change: https://discourse.llvm.org/t/rfc-adding-builtin-for-deduplicating-type-lists/80986 |
505cd54 to
3365026
Compare
|
@llvm/pr-subscribers-clang-modules @llvm/pr-subscribers-clangd Author: Ilya Biryukov (ilya-biryukov) ChangesThis allows to deduplicate the type lists efficiently in C++. It is possible to achieve the same effect via template metaprogramming, but performance of the resulting code is much lower than in the compiler. We have observed that this code is quite common in our internal codebase and this builtin allows to have significant savings (up to 25% of compile time on targets that already take 3 minutes to compile). The same builtin is also used widely enough in the codebase that we expect a savings from a long tail of uses, too, although it is hard to put an estimate on this number in advance. The implementation aims to be as simple as possible and relies on the exsisting machinery for builtin templates. Patch is 20.75 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/106730.diff 16 Files Affected:
diff --git a/clang-tools-extra/clangd/unittests/FindTargetTests.cpp b/clang-tools-extra/clangd/unittests/FindTargetTests.cpp
index 3220a5a6a98250..d9f788cbf2a8a2 100644
--- a/clang-tools-extra/clangd/unittests/FindTargetTests.cpp
+++ b/clang-tools-extra/clangd/unittests/FindTargetTests.cpp
@@ -731,6 +731,12 @@ TEST_F(TargetDeclTest, BuiltinTemplates) {
using type_pack_element = [[__type_pack_element]]<N, Pack...>;
)cpp";
EXPECT_DECLS("TemplateSpecializationTypeLoc", );
+
+ Code = R"cpp(
+ template <template <class...> Templ, class... Types>
+ using type_list_dedup = [[__type_list_dedup]]<Templ, Types...>;
+ )cpp";
+ EXPECT_DECLS("TemplateSpecializationTypeLoc", );
}
TEST_F(TargetDeclTest, MemberOfTemplate) {
diff --git a/clang/include/clang/AST/ASTContext.h b/clang/include/clang/AST/ASTContext.h
index 89bb5768dbd40d..1960ec1e99f652 100644
--- a/clang/include/clang/AST/ASTContext.h
+++ b/clang/include/clang/AST/ASTContext.h
@@ -401,6 +401,9 @@ class ASTContext : public RefCountedBase<ASTContext> {
/// The identifier '__type_pack_element'.
mutable IdentifierInfo *TypePackElementName = nullptr;
+ /// The identifier '__type_list_dedup'.
+ mutable IdentifierInfo *TypeListDedupName = nullptr;
+
QualType ObjCConstantStringType;
mutable RecordDecl *CFConstantStringTagDecl = nullptr;
mutable TypedefDecl *CFConstantStringTypeDecl = nullptr;
@@ -608,6 +611,7 @@ class ASTContext : public RefCountedBase<ASTContext> {
mutable ExternCContextDecl *ExternCContext = nullptr;
mutable BuiltinTemplateDecl *MakeIntegerSeqDecl = nullptr;
mutable BuiltinTemplateDecl *TypePackElementDecl = nullptr;
+ mutable BuiltinTemplateDecl *TypeListDedupDecl = nullptr;
/// The associated SourceManager object.
SourceManager &SourceMgr;
@@ -1115,6 +1119,7 @@ class ASTContext : public RefCountedBase<ASTContext> {
ExternCContextDecl *getExternCContextDecl() const;
BuiltinTemplateDecl *getMakeIntegerSeqDecl() const;
BuiltinTemplateDecl *getTypePackElementDecl() const;
+ BuiltinTemplateDecl *getTypeListDedupDecl() const;
// Builtin Types.
CanQualType VoidTy;
@@ -2006,6 +2011,12 @@ class ASTContext : public RefCountedBase<ASTContext> {
return TypePackElementName;
}
+ IdentifierInfo *getTypeListDedupName() const {
+ if (!TypeListDedupName)
+ TypeListDedupName = &Idents.get("__type_list_dedup");
+ return TypeListDedupName;
+ }
+
/// Retrieve the Objective-C "instancetype" type, if already known;
/// otherwise, returns a NULL type;
QualType getObjCInstanceType() {
diff --git a/clang/include/clang/AST/DeclID.h b/clang/include/clang/AST/DeclID.h
index 81454a247229f5..41cecf1b8a9ebf 100644
--- a/clang/include/clang/AST/DeclID.h
+++ b/clang/include/clang/AST/DeclID.h
@@ -83,6 +83,9 @@ enum PredefinedDeclIDs {
/// The internal '__type_pack_element' template.
PREDEF_DECL_TYPE_PACK_ELEMENT_ID,
+ /// The internal '__type_list_dedup' template.
+ PREDEF_DECL_TYPE_LIST_DEDUP_ID,
+
/// The number of declaration IDs that are predefined.
NUM_PREDEF_DECL_IDS
};
diff --git a/clang/include/clang/Basic/Builtins.h b/clang/include/clang/Basic/Builtins.h
index e85ec5b2dca14e..018996c0da527e 100644
--- a/clang/include/clang/Basic/Builtins.h
+++ b/clang/include/clang/Basic/Builtins.h
@@ -309,7 +309,10 @@ enum BuiltinTemplateKind : int {
BTK__make_integer_seq,
/// This names the __type_pack_element BuiltinTemplateDecl.
- BTK__type_pack_element
+ BTK__type_pack_element,
+
+ /// This names the __type_list_dedup BuiltinTemplateDecl.
+ BTK__type_list_dedup,
};
} // end namespace clang
diff --git a/clang/lib/AST/ASTContext.cpp b/clang/lib/AST/ASTContext.cpp
index c61234aa4d1af1..aaea59eb9962c4 100644
--- a/clang/lib/AST/ASTContext.cpp
+++ b/clang/lib/AST/ASTContext.cpp
@@ -1170,6 +1170,13 @@ ASTContext::getTypePackElementDecl() const {
return TypePackElementDecl;
}
+BuiltinTemplateDecl *ASTContext::getTypeListDedupDecl() const {
+ if (!TypeListDedupDecl)
+ TypeListDedupDecl =
+ buildBuiltinTemplateDecl(BTK__type_list_dedup, getTypeListDedupName());
+ return TypeListDedupDecl;
+}
+
RecordDecl *ASTContext::buildImplicitRecord(StringRef Name,
RecordDecl::TagKind TK) const {
SourceLocation Loc;
diff --git a/clang/lib/AST/ASTImporter.cpp b/clang/lib/AST/ASTImporter.cpp
index fa850409ba1210..7d97558ff0a87a 100644
--- a/clang/lib/AST/ASTImporter.cpp
+++ b/clang/lib/AST/ASTImporter.cpp
@@ -5476,6 +5476,9 @@ ExpectedDecl ASTNodeImporter::VisitBuiltinTemplateDecl(BuiltinTemplateDecl *D) {
case BuiltinTemplateKind::BTK__type_pack_element:
ToD = Importer.getToContext().getTypePackElementDecl();
break;
+ case BuiltinTemplateKind::BTK__type_list_dedup:
+ ToD = Importer.getToContext().getTypeListDedupDecl();
+ break;
}
assert(ToD && "BuiltinTemplateDecl of unsupported kind!");
Importer.MapImported(D, ToD);
diff --git a/clang/lib/AST/DeclTemplate.cpp b/clang/lib/AST/DeclTemplate.cpp
index 976b3a3e1ecedb..727f9a0751cf82 100644
--- a/clang/lib/AST/DeclTemplate.cpp
+++ b/clang/lib/AST/DeclTemplate.cpp
@@ -1608,6 +1608,35 @@ createTypePackElementParameterList(const ASTContext &C, DeclContext *DC) {
nullptr);
}
+static TemplateParameterList *
+createTypeListDedupParameterList(const ASTContext &C, DeclContext *DC) {
+ // template <typename ...> typename Templ
+ auto *InnerTs = TemplateTypeParmDecl::Create(
+ C, DC, SourceLocation(), SourceLocation(), /*Depth=*/1, /*Position=*/0,
+ /*Id=*/nullptr, /*Typename=*/true, /*ParameterPack=*/true,
+ /*HasTypeConstraint=*/false);
+ InnerTs->setImplicit(true);
+ auto *TemplateParamList = TemplateParameterList::Create(
+ C, SourceLocation(), SourceLocation(), {InnerTs}, SourceLocation(),
+ /*RequiresClause=*/nullptr);
+ auto *Template = TemplateTemplateParmDecl::Create(
+ C, DC, SourceLocation(), /*Depth=*/0,
+ /*Position=*/0, /*ParameterPack=*/false, /*Id=*/nullptr,
+ /*Typename=*/true, TemplateParamList);
+ Template->setImplicit(true);
+
+ // typename ...Ts
+ auto *Ts = TemplateTypeParmDecl::Create(
+ C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/1,
+ /*Id=*/nullptr, /*Typename=*/true, /*ParameterPack=*/true,
+ /*HasTypeConstraint=*/false);
+ Ts->setImplicit(true);
+ return TemplateParameterList::Create(
+ C, SourceLocation(), SourceLocation(),
+ llvm::ArrayRef<NamedDecl *>({Template, Ts}), SourceLocation(),
+ /*RequiresClause=*/nullptr);
+}
+
static TemplateParameterList *createBuiltinTemplateParameterList(
const ASTContext &C, DeclContext *DC, BuiltinTemplateKind BTK) {
switch (BTK) {
@@ -1615,6 +1644,8 @@ static TemplateParameterList *createBuiltinTemplateParameterList(
return createMakeIntegerSeqParameterList(C, DC);
case BTK__type_pack_element:
return createTypePackElementParameterList(C, DC);
+ case BTK__type_list_dedup:
+ return createTypeListDedupParameterList(C, DC);
}
llvm_unreachable("unhandled BuiltinTemplateKind!");
diff --git a/clang/lib/Lex/PPMacroExpansion.cpp b/clang/lib/Lex/PPMacroExpansion.cpp
index 1d671ab72b0c03..f2d091ab29082e 100644
--- a/clang/lib/Lex/PPMacroExpansion.cpp
+++ b/clang/lib/Lex/PPMacroExpansion.cpp
@@ -1836,6 +1836,7 @@ void Preprocessor::ExpandBuiltinMacro(Token &Tok) {
// Report builtin templates as being builtins.
.Case("__make_integer_seq", getLangOpts().CPlusPlus)
.Case("__type_pack_element", getLangOpts().CPlusPlus)
+ .Case("__type_list_dedup", getLangOpts().CPlusPlus)
// Likewise for some builtin preprocessor macros.
// FIXME: This is inconsistent; we usually suggest detecting
// builtin macros via #ifdef. Don't add more cases here.
diff --git a/clang/lib/Sema/SemaLookup.cpp b/clang/lib/Sema/SemaLookup.cpp
index 7a6a64529f52ec..cf75caca67088b 100644
--- a/clang/lib/Sema/SemaLookup.cpp
+++ b/clang/lib/Sema/SemaLookup.cpp
@@ -928,10 +928,15 @@ bool Sema::LookupBuiltin(LookupResult &R) {
if (II == getASTContext().getMakeIntegerSeqName()) {
R.addDecl(getASTContext().getMakeIntegerSeqDecl());
return true;
- } else if (II == getASTContext().getTypePackElementName()) {
+ }
+ if (II == getASTContext().getTypePackElementName()) {
R.addDecl(getASTContext().getTypePackElementDecl());
return true;
}
+ if (II == getASTContext().getTypeListDedupName()) {
+ R.addDecl(getASTContext().getTypeListDedupDecl());
+ return true;
+ }
}
// Check if this is an OpenCL Builtin, and if so, insert its overloads.
diff --git a/clang/lib/Sema/SemaTemplate.cpp b/clang/lib/Sema/SemaTemplate.cpp
index bf6b53700d90eb..cace516263a78d 100644
--- a/clang/lib/Sema/SemaTemplate.cpp
+++ b/clang/lib/Sema/SemaTemplate.cpp
@@ -17,7 +17,9 @@
#include "clang/AST/Expr.h"
#include "clang/AST/ExprCXX.h"
#include "clang/AST/RecursiveASTVisitor.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"
@@ -38,9 +40,11 @@
#include "clang/Sema/Template.h"
#include "clang/Sema/TemplateDeduction.h"
#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/raw_ostream.h"
#include <iterator>
#include <optional>
@@ -3132,12 +3136,12 @@ checkBuiltinTemplateIdType(Sema &SemaRef, BuiltinTemplateDecl *BTD,
TemplateLoc, SyntheticTemplateArgs);
}
- case BTK__type_pack_element:
+ case BTK__type_pack_element: {
// Specializations of
// __type_pack_element<Index, T_1, ..., T_N>
// are treated like T_Index.
assert(Converted.size() == 2 &&
- "__type_pack_element should be given an index and a parameter pack");
+ "__type_pack_element should be given an index and a parameter pack");
TemplateArgument IndexArg = Converted[0], Ts = Converted[1];
if (IndexArg.isDependent() || Ts.isDependent())
@@ -3158,6 +3162,33 @@ checkBuiltinTemplateIdType(Sema &SemaRef, BuiltinTemplateDecl *BTD,
int64_t N = Index.getExtValue();
return Ts.getPackAsArray()[N].getAsType();
}
+ case BTK__type_list_dedup: {
+ assert(Converted.size() == 2 &&
+ "__type_list_dedup should be given a template and a parameter pack");
+ TemplateArgument Template = Converted[0];
+ TemplateArgument Ts = Converted[1];
+ if (Template.isDependent() || Ts.isDependent())
+ return Context.getCanonicalTemplateSpecializationType(TemplateName(BTD),
+ Converted);
+
+ assert(Template.getKind() == clang::TemplateArgument::Template);
+ assert(Ts.getKind() == clang::TemplateArgument::Pack);
+ TemplateArgumentListInfo SyntheticTemplateArgs;
+ llvm::DenseSet<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;
+ SyntheticTemplateArgs.addArgument(TemplateArgumentLoc(
+ TemplateArgument(T), SemaRef.Context.getTrivialTypeSourceInfo(
+ T.getAsType(),
+ /*FIXME: add location*/ SourceLocation())));
+ }
+ return SemaRef.CheckTemplateIdType(Template.getAsTemplate(), TemplateLoc,
+ SyntheticTemplateArgs);
+ }
+ }
llvm_unreachable("unexpected BuiltinTemplateDecl!");
}
diff --git a/clang/lib/Serialization/ASTReader.cpp b/clang/lib/Serialization/ASTReader.cpp
index e5a1e20a265616..78cb449d60c474 100644
--- a/clang/lib/Serialization/ASTReader.cpp
+++ b/clang/lib/Serialization/ASTReader.cpp
@@ -23,6 +23,7 @@
#include "clang/AST/DeclCXX.h"
#include "clang/AST/DeclFriend.h"
#include "clang/AST/DeclGroup.h"
+#include "clang/AST/DeclID.h"
#include "clang/AST/DeclObjC.h"
#include "clang/AST/DeclTemplate.h"
#include "clang/AST/DeclarationName.h"
@@ -7897,6 +7898,11 @@ Decl *ASTReader::getPredefinedDecl(PredefinedDeclIDs ID) {
return Context.TypePackElementDecl;
NewLoaded = Context.getTypePackElementDecl();
break;
+ case PREDEF_DECL_TYPE_LIST_DEDUP_ID:
+ if (Context.TypeListDedupDecl)
+ return Context.TypeListDedupDecl;
+ NewLoaded = Context.getTypeListDedupDecl();
+ break;
case NUM_PREDEF_DECL_IDS:
llvm_unreachable("Invalid decl ID");
break;
diff --git a/clang/lib/Serialization/ASTWriter.cpp b/clang/lib/Serialization/ASTWriter.cpp
index c6289493fce1de..9a1c67e33894bd 100644
--- a/clang/lib/Serialization/ASTWriter.cpp
+++ b/clang/lib/Serialization/ASTWriter.cpp
@@ -22,6 +22,7 @@
#include "clang/AST/DeclCXX.h"
#include "clang/AST/DeclContextInternals.h"
#include "clang/AST/DeclFriend.h"
+#include "clang/AST/DeclID.h"
#include "clang/AST/DeclObjC.h"
#include "clang/AST/DeclTemplate.h"
#include "clang/AST/DeclarationName.h"
@@ -5051,6 +5052,7 @@ void ASTWriter::PrepareWritingSpecialDecls(Sema &SemaRef) {
PREDEF_DECL_CF_CONSTANT_STRING_TAG_ID);
RegisterPredefDecl(Context.TypePackElementDecl,
PREDEF_DECL_TYPE_PACK_ELEMENT_ID);
+ RegisterPredefDecl(Context.TypeListDedupDecl, PREDEF_DECL_TYPE_LIST_DEDUP_ID);
const TranslationUnitDecl *TU = Context.getTranslationUnitDecl();
diff --git a/clang/test/Import/builtin-template/Inputs/S.cpp b/clang/test/Import/builtin-template/Inputs/S.cpp
index d5c9a9ae0309d3..6cde0732d3719f 100644
--- a/clang/test/Import/builtin-template/Inputs/S.cpp
+++ b/clang/test/Import/builtin-template/Inputs/S.cpp
@@ -14,3 +14,10 @@ using TypePackElement = __type_pack_element<i, T...>;
template <int i>
struct X;
+
+
+template <template <class...> class Templ, class...Types>
+using TypeListDedup = __type_list_dedup<Templ, Types...>;
+
+template <class ...Ts>
+struct TypeList {};
diff --git a/clang/test/Import/builtin-template/test.cpp b/clang/test/Import/builtin-template/test.cpp
index 590efad0c71dca..ca67457d73f2b6 100644
--- a/clang/test/Import/builtin-template/test.cpp
+++ b/clang/test/Import/builtin-template/test.cpp
@@ -1,9 +1,11 @@
// RUN: clang-import-test -dump-ast -import %S/Inputs/S.cpp -expression %s -Xcc -DSEQ | FileCheck --check-prefix=CHECK-SEQ %s
// RUN: clang-import-test -dump-ast -import %S/Inputs/S.cpp -expression %s -Xcc -DPACK | FileCheck --check-prefix=CHECK-PACK %s
-// RUN: clang-import-test -dump-ast -import %S/Inputs/S.cpp -expression %s -Xcc -DPACK -Xcc -DSEQ | FileCheck --check-prefixes=CHECK-SEQ,CHECK-PACK %s
+// RUN: clang-import-test -dump-ast -import %S/Inputs/S.cpp -expression %s -Xcc -DDEDUP | FileCheck --check-prefix=CHECK-DEDUP %s
+// RUN: clang-import-test -dump-ast -import %S/Inputs/S.cpp -expression %s -Xcc -DPACK -Xcc -DSEQ -Xcc -DDEDUP | FileCheck --check-prefixes=CHECK-SEQ,CHECK-PACK,CHECK-DEDUP %s
// CHECK-SEQ: BuiltinTemplateDecl {{.+}} <<invalid sloc>> <invalid sloc> implicit __make_integer_seq{{$}}
// CHECK-PACK: BuiltinTemplateDecl {{.+}} <<invalid sloc>> <invalid sloc> implicit __type_pack_element{{$}}
+// CHECK-DEDUP: BuiltinTemplateDecl {{.+}} <<invalid sloc>> <invalid sloc> implicit __type_list_dedup{{$}}
void expr() {
#ifdef SEQ
@@ -20,4 +22,10 @@ void expr() {
static_assert(__is_same(TypePackElement<0, X<0>, X<1>>, X<0>), "");
static_assert(__is_same(TypePackElement<1, X<0>, X<1>>, X<1>), "");
#endif
+
+#ifdef DEDUP
+ static_assert(__is_same(TypeListDedup<TypeList>, TypeList<>), "");
+ static_assert(__is_same(TypeListDedup<TypeList, int, double, int>, TypeList<int, double>), "");
+ static_assert(__is_same(TypeListDedup<TypeList, X<0>, X<1>, X<1>, X<2>, X<0>>, TypeList<X<0>, X<1>, X<2>>), "");
+#endif
}
diff --git a/clang/test/PCH/type_list_dedup.cpp b/clang/test/PCH/type_list_dedup.cpp
new file mode 100644
index 00000000000000..a84dc340160edf
--- /dev/null
+++ b/clang/test/PCH/type_list_dedup.cpp
@@ -0,0 +1,20 @@
+// RUN: %clang_cc1 -std=c++14 -x c++-header %s -emit-pch -o %t.pch
+// RUN: %clang_cc1 -std=c++14 -x c++ /dev/null -include-pch %t.pch
+
+// RUN: %clang_cc1 -std=c++14 -x c++-header %s -emit-pch -fpch-instantiate-templates -o %t.pch
+// RUN: %clang_cc1 -std=c++14 -x c++ /dev/null -include-pch %t.pch
+
+template <template <class...> class Templ, class...Types>
+using TypeListDedup = __type_list_dedup<Templ, Types...>;
+
+template <class ...Ts>
+struct TypeList {};
+
+template <int i>
+struct X {};
+
+void fn1() {
+ TypeList<int, double> l1 = TypeListDedup<TypeList, int, double, int>{};
+ TypeList<> l2 = TypeListDedup<TypeList>{};
+ TypeList<X<0>, X<1>> x1 = TypeListDedup<TypeList, X<0>, X<1>, X<0>, X<1>>{};
+}
diff --git a/clang/test/SemaTemplate/temp-param-list-dedup.cpp b/clang/test/SemaTemplate/temp-param-list-dedup.cpp
new file mode 100644
index 00000000000000..7a9f6c79419445
--- /dev/null
+++ b/clang/test/SemaTemplate/temp-param-list-dedup.cpp
@@ -0,0 +1,57 @@
+// RUN: %clang_cc1 %s -verify
+
+template <typename...> struct TypeList;
+
+static_assert(__is_same(
+ __type_list_dedup<TypeList, int, int*, int, double, float>,
+ TypeList<int, int*, double, float>));
+
+template <template<typename ...> typename Templ, typename ...Types>
+struct Dependent {
+ using empty_list = __type_list_dedup<Templ>;
+ using same = __type_list_dedup<Templ, Types...>;
+ using twice = __type_list_dedup<Templ, Types..., Types...>;
+ using dep_only_types = __type_list_dedup<TypeList, Types...>;
+ using dep_only_template = __type_list_dedup<Templ, int, double, int>;
+};
+
+static_assert(__is_same(Dependent<TypeList>::empty_list, TypeList<>));
+static_assert(__is_same(Dependent<TypeList>::same, TypeList<>));
+static_assert(__is_same(Dependent<TypeList>::twice, TypeList<>));
+static_assert(__is_same(Dependent<TypeList>::dep_only_types, TypeList<>));
+static_assert(__is_same(Dependent<TypeList>::dep_only_template, TypeList<int, double>));
+
+static_assert(__is_same(Dependent<TypeList, int*, double*, int*>::empty_list, TypeList<>));
+static_assert(__is_same(Dependent<TypeList, int*, double*, int*>::same, TypeList<int*, double*>));
+static_assert(__is_same(Dependent<TypeList, int*, double*, int*>::twice, TypeList<int*, double*>));
+static_assert(__is_same(Dependent<TypeList, int*, double*, int*>::dep_only_types, TypeList<int*, double*>));
+static_assert(__is_same(Dependent<TypeList, int*, double*, int*>::dep_only_template, TypeList<int, double>));
+
+
+template <class ...T>
+using Twice = TypeList<T..., T...>;
+
+static_assert(__is_same(__type_list_dedup<Twice, int, double, int>, TypeList<int, double, int, double>));
+
+
+template <int...> struct IntList;
+// Wrong kinds of template arguments.
+__type_list_dedup<IntList>* wrong_template; // expected-error {{template template argument has different template parameters than its corresponding template template parameter}}
+ // expected-note@-3 {{template parameter has a different kind in template argument}}
+__type_list_dedup<TypeList, 1, 2, 3>* wrong_template_args; // expected-error {{template argument for template type parameter must be a type}}
+ // expected-note@* {{previous template template parameter is here}}
+ // expected-note@* {{template parameter from hidden source}}
+__type_list_dedup<> not_enough_args; // expected-error {{too few template arguments for template '__type_list_dedup'}}
+ // expected-note@* {{template declaration from hidden source}}
+__type_list_dedup missing_template_args; // expected-error {{use of template '__type_list_dedup' requires template arguments}}
+ // expected-note@* {{template declaration from hidden source}}
+
+// Direct recursive use will fail because the signature of template parameters does not match.
+// The intention for this test is to anticipate a failure mode where compiler may start running the deduplication recursively, going int...
[truncated]
|
|
I still need to add code that preserves source locations for template arguments and tests for it, but otherwise this is ready for review and I would like to get some initial feedback. The RFC did not get any comments so far, but also happy to discuss the general design there. |
clang/include/clang/Basic/Builtins.h
Outdated
| BTK__type_pack_element, | ||
|
|
||
| /// This names the __type_list_dedup BuiltinTemplateDecl. | ||
| BTK__type_list_dedup, |
There was a problem hiding this comment.
What do you think about implementing this as a TypeTrait? This could be part of clang/Basic/TransformTypeTraits.def. Looking at the other transform type traits, their implementation looks much less complex and needs to touch much fewer files if we want to add more traits.
(That currently uses "Unary"TransformType. If this does not fit our purpose, we could introduce a variadic version of VariadicTransformType. This would be particularly helpful for future when we want to add more of such useful type_traits, we would be sharing a lot of code and would introducing such traits much less complex.)
There was a problem hiding this comment.
I have mentioned that in the RFC, see alternatives considered section.
I think the builtin template is better because it:
- provides the most obvious semantics for type aliases and avoids confusion,
- avoids the need for instantiation of the underlying template with non-duplicated list types,
- is simpler to implement.
There was a problem hiding this comment.
On the argument of adding VariadicTransformType, maybe it's useful for something, but I definitely don't see why introducing a new bulitin template is more complicated than introducing a new type trait. I think they're quite on par in terms of complexity and we should be looking at what fits the language design better (see first two bullet points above on why I feel it's a better choice for the language).
There was a problem hiding this comment.
Given that we already have builtin templates, if we're concerned about the boilerplate involved in adding a new one, perhaps we could remove most of that boilerplate instead? It looks like an xmacro (.def file) approach could handle most of these changes. Though I'd suggest we decouple that refactoring from this change.
Unless we think that builtin templates were a mistake, and we instead would prefer to deprecate and eventually remove our support for builtin templates?
For what it's worth, as I recall the idea was that builtin templates would be a lot less invasive than builtin type traits for this kind of thing. They don't need a new keyword, separate parsing rules, a new AST representation, etc -- they're just another kind of type template name. And they support type arguments, non-type arguments, and templates as arguments without extra work. And they can reuse our normal type-checking for templates. The big downside is that they don't work in C, but for things intended for operating on parameter packs such as the existing two builtin templates and this new one, that's fine.
There was a problem hiding this comment.
FYI I have a local patch to refactor most of the code into just a BuiltinTemplates.td. In the end that should only make it required to modify BuiltinTemplate.td and SemaTemplate.cpp.
There was a problem hiding this comment.
Unless we think that builtin templates were a mistake, and we instead would prefer to deprecate and eventually remove our support for builtin templates?
I certainly feel they are a useful tool to have and we should probably keep them.
I'm definitely very supportive of reducing the boilerplate.
On that front, @philnik777 do you feel like you digging out that local patch or should I take a stab at it?
In any case, I'd do this in a separate change. The boilerplate present in this commit is still very much manageable (and already done), so I don't think that blocking this PR on removing this boileerplate would be my first choice.
There was a problem hiding this comment.
One downside of builtin templates is that they can affect mangling, if we wish to support cases where we can't specialize them until dependencies are resolved.
For example, we can't do anything with __make_integer_seq if the count is value dependent, which means in order to support that case, we build a canonical TST which is named by the builtin template name, and this means __make_integer_seq will be mangled.
There was a problem hiding this comment.
An advantage of the builtin templates is that we can introduce deduction rules for them, although we currently don't do that for any of the existing ones.
One example:
template <class...> struct A {};
template <class T, class U> void f(__builtin_type_pack_dedup<A, T, U>);
void test() {
A<int, int, char> a;
f(a); // OK, deduced as T = int, U = char
}An example of how this could apply to existing __make_integer_seq:
template <class T, T Count> void f(__make_integer_seq(std::integer_sequence, T, Count)) {}
void test() {
f(std::make_integer_sequence<int, 12>{}); // OK, deduced T = int, Count = 12
}|
(This is in my list of PR/RFC to review, I'll try to get to it this week) |
clang/include/clang/Basic/Builtins.h
Outdated
| BTK__type_pack_element | ||
| BTK__type_pack_element, | ||
|
|
||
| /// This names the __type_list_dedup BuiltinTemplateDecl. |
There was a problem hiding this comment.
This name seems inconsistent with the previous builtin: using the __type_pack prefix for both would be more uniform.
There was a problem hiding this comment.
I think we've decided somewhere that all new builtin functionality should have a __builtin_ prefix. The main reason was to avoid naming conflicts. While I don't think that's a huge issue here, we should probably be consistent in that regard. So this should probably be __builtin_type_pack_dedup.
There was a problem hiding this comment.
Thanks, I don't actually know why I didn't pick type_pack prefix in the first place. I think I was confused when I started and thought that type_pack_element was more different than it ended up being.
It's now __builtin_type_pack_dedup, as suggested.
clang/include/clang/Basic/Builtins.h
Outdated
| BTK__type_pack_element, | ||
|
|
||
| /// This names the __type_list_dedup BuiltinTemplateDecl. | ||
| BTK__type_list_dedup, |
There was a problem hiding this comment.
Given that we already have builtin templates, if we're concerned about the boilerplate involved in adding a new one, perhaps we could remove most of that boilerplate instead? It looks like an xmacro (.def file) approach could handle most of these changes. Though I'd suggest we decouple that refactoring from this change.
Unless we think that builtin templates were a mistake, and we instead would prefer to deprecate and eventually remove our support for builtin templates?
For what it's worth, as I recall the idea was that builtin templates would be a lot less invasive than builtin type traits for this kind of thing. They don't need a new keyword, separate parsing rules, a new AST representation, etc -- they're just another kind of type template name. And they support type arguments, non-type arguments, and templates as arguments without extra work. And they can reuse our normal type-checking for templates. The big downside is that they don't work in C, but for things intended for operating on parameter packs such as the existing two builtin templates and this new one, that's fine.
| @@ -0,0 +1,57 @@ | |||
| // RUN: %clang_cc1 %s -verify | |||
There was a problem hiding this comment.
I'd like to also see some testing of the case where the template arguments have different sugar but are canonically the same, and when they differ by only cv-qualifiers. Those seem like likely cases for us to get wrong. Eg:
using T = int;
using CT = const T;
static_assert(__is_same(__type_list_dedup<TypeList, T, int, const int, const T, CT, const CT>,
TypeList<int, const int>));There was a problem hiding this comment.
Done. I have also added a few tests with arrays and pointers, which should also exhibit a few more combinations of types that subsume qualifiers and could be different when canonical/non-canonical.
6f0f00f to
3e51c6d
Compare
clang/lib/Sema/SemaTemplate.cpp
Outdated
| SyntheticTemplateArgs.addArgument(TemplateArgumentLoc( | ||
| TemplateArgument(T), SemaRef.Context.getTrivialTypeSourceInfo( | ||
| T.getAsType(), | ||
| /*FIXME: add location*/ SourceLocation()))); |
There was a problem hiding this comment.
After looking at the code, I am afraid the not-very-precise source location will stay a limitation of this builtin (it also seems like it's the case for some other cases involving packs? as soon as a template argument gets added into a pack, it seems we should be loosing its location information at least in some cases)
We do not seem to be tracking the TemplateArgumentLocs of TempateArguments we get from the pack very precisely. While it's possible to poke at the TemplateArgumentList provided into the function and match them with the types I get from Converted, I am not entirely sure what the structure of the TemplateArgumentListInfo is [1] and whether the complexity around it is worth it?
@zygoloid any thoughts on this? is it worth digging into the various representations the passed TemplateArgumentListInfo might have or is it a dead end?
[1]: is it always flattened? does it always have packs? can it be both?
There was a problem hiding this comment.
I think the only thing we would use this source location for is to diagnose in CheckTemplateIdType if the template arguments aren't suitable for use as arguments of Template, which we already checked before getting here. So I don't think it's worth going to any effort to get a good location. Let's just pass in TemplateLoc as the location.
(It's notable that __make_integer_seq uses (eg) TemplateArguments[1].getLocation(). We could do the same, but that will break once we add universal template parameters, which seem to be making good progress through WG21 -- where there might be only a single template argument that pack-expands to all the arguments of __make_integer_seq, and likewise here. So maybe it'd be worth changing __make_integer_seq to pass in TemplateLoc instead while we're thinking about this.)
|
Friendly ping for another round of review. |
There was a problem hiding this comment.
Thanks for working on this problem!
I think the current approach is limited in ABI stability, we could broaden the usability here by designing this builtin so it produces a type list which is unique per set of types (order independent).
I had a chat with @lewissbaker a couple of months ago, and they need a similar facility for stdexec, except that ABI stability is important for them.
One possible approach would be to sort the types according to their Itanium mangling, or something similarly stable.
Would that suit your needs as well?
clang/lib/Sema/SemaTemplate.cpp
Outdated
| "a template and a parameter pack"); | ||
| TemplateArgument Template = Converted[0]; | ||
| TemplateArgument Ts = Converted[1]; | ||
| if (Template.isDependent() || Ts.isDependent()) |
There was a problem hiding this comment.
I think the only reason we would need to hold off on building the template specialization would be if Ts contains an unexpanded pack, otherwise we are good to go, subsequent substitutions will produce the correct type list anyway.
This would also reduce the size of the argument list.
Be aware that holding this specialization will make this builtin appear in mangling, so I'd avoid doing that unless necessary.
There was a problem hiding this comment.
We could remove the dependency on the template, but I don't think we can ignore the dependency inside the types themselves.
Consider
template <class T, class U, template <class...> class TL = TypeList>
struct Foo {
// 1. the substitution has to be postponed until T and U are known.
using result = __dedup<TypeList, T, U>;
// 2. this is already computed right away.
using result2 = __dedup<TypeList, int, int>;
// 3. this **could** be computed right away, but it is not now.
using result3 = __dedup<TL, int, int>
};
static_assert(__is_same(TypeList<int>, Foo<int, int>::result));
static_assert(__is_same(TypeList<int, doubel>, Foo<int, double>::result));- Is there something I'm missing that would allow (1) to be substituted earlier?
- Do you feel strongly that we need to do (3) ?
Be aware that holding this specialization will make this builtin appear in mangling, so I'd avoid doing that unless necessary.
I do not think we can avoid this completely (see above) and it's not unprecedented: other builtin templates can already appear in mangling too when the arguments are dependent. So I do think it's necessary and I'm not sure which problems it carries.
There was a problem hiding this comment.
You are right that we can't drop out the builtin template specialization just yet if any of the arguments are dependent.
But we can still unique the list in that case. This actually even applies for unexpanded packs as well.
One advantage I see is that you would avoid the possibility of the user introducing multiple overloads that are equivalent, which you wouldn't be able to partial order later.
Ie
template <class...> struct A;
template <class T> void f(__builtin_type_pack_dedup<A, T>) {}
template <class T> void f(__builtin_type_pack_dedup<A, T, T>) {}This would be ill-formed because f is being redefined.
This also increases the ABI stability for the same reason. If the user introduces another repeated template argument, it's still results in the same templated entity with the same mangling.
Do you feel strongly that we need to do (3) ?
See above.
I do not think we can avoid this completely (see above) and it's not unprecedented: other builtin templates can already appear in mangling too when the arguments are dependent. So I do think it's necessary and I'm not sure which problems it carries.
Right, it's not completely unavoidable, but at least for the dependent template name case that we can resolve early, it makes it so this builtin can be introduced without causing an ABI break.
|
Thanks for the reviews everyone. I have responded on the RFC and plan to address the small caveats mentioned here too. |
|
@cor3ntin and everyone else, would you mind taking another look? I wanted to bring this up again and tried to do all the proposed changes:
I was worried that the latter would be too complicated, but it actually wasn't. I would appreciate if folks took another look here and provided their feedback. |
There was a problem hiding this comment.
Modulo nits, I think this is almost ready to be landed. I hope the few fixme are investigated in follow ups.
Can you add a release note and some documentation in LanguageExtensions.rst, in the Type Trait Primitives section?
I hope @mizvekov @zyn0217 and @erichkeane can do a last pass on this PR
I have added both, PTAL. I opted for the "builtin type aliases" section as this is where other template builtins like |
|
Friendly ping for another round / final approves. |
| typedef std::pair<llvm::PointerUnion<const TemplateTypeParmType *, NamedDecl *, | ||
| const TemplateSpecializationType *, | ||
| const SubstBuiltinTemplatePackType *>, |
There was a problem hiding this comment.
I think we could leave it as-is :) No fixme nor issue is required because one would notice that when adding new types
|
Thanks a lot for the review, everyone! I will create the concrete issues for the follow-ups required tomorrow and will start tackling them after that. |
|
@ilya-biryukov After this PR, I'm getting: Is there any way you could take look? |
…m#106730)" This reverts commits 85043c1 and 65de318. The first commit above triggers the following warnings: clang/lib/Sema/SemaTemplateVariadic.cpp:1069:22: error: variable 'TST' set but not used [-Werror,-Wunused-but-set-variable] lldb/source/Plugins/TypeSystem/Clang/TypeSystemClang.cpp:4148:11: error: enumeration value 'SubstBuiltinTemplatePack' not handled in switch [-Werror,-Wswitch] 4148 | switch (qual_type->getTypeClass()) { | ^~~~~~~~~~~~~~~~~~~~~~~~~ lldb/source/Plugins/TypeSystem/Clang/TypeSystemClang.cpp:4852:11: error: enumeration value 'SubstBuiltinTemplatePack' not handled in switch [-Werror,-Wswitch] 4852 | switch (qual_type->getTypeClass()) { | ^~~~~~~~~~~~~~~~~~~~~~~~~ lldb/source/Plugins/TypeSystem/Clang/TypeSystemClang.cpp:5153:11: error: enumeration value 'SubstBuiltinTemplatePack' not handled in switch [-Werror,-Wswitch] 5153 | switch (qual_type->getTypeClass()) { | ^~~~~~~~~~~~~~~~~~~~~~~~~
|
@ilya-biryukov I've addressed these warnings with #154606. |
Thanks a lot! And sorry for not spotting this earlier, I do not have LLDB build configured locally. It would be great to add this to presubmits at some point in order to spot those problems. |
The new builtin
__builtin_dedup_packremoves duplicates from list of types.The added builtin is special in that they produce an unexpanded pack
in the spirit of P3115R0 proposal.
Produced packs can be used directly in template argument lists and get
immediately expanded as soon as results of the computation are
available.
It allows to easily combine them, e.g.:
Limitations:
The actual implementation proceeds as follows:
__builtin_dedup_packor other type-producingbuiltin with dependent arguments, it creates a dependent
TemplateSpecializationType.will produce: a new type
SubstBuiltinTemplatePackType, which storesan argument pack that needs to be substituted. This type is similar to
the existing
SubstTemplateParmPackin that it carries the argumentpack that needs to be expanded further. The relevant code is shared.
TemplateSpecializationType, but this time only as a sugar.SubstBuiltinTemplatePackTypeinsideCollectUnexpandedPacks.Because we know the size of the produces packs only after the initial
substitution, places that do the actual expansion will need to have a
second run over the substituted type to finalize the expansions (in
this patch we only support this for template arguments, see
ExpandTemplateArgument).If the expansion are requested in the places we do not currently
support, we will produce an error.
More follow-up work will be needed to fully shape this:
P3670 R1 Pack Indexing for Template Names cplusplus/papers#2300).