[Sema] Implement __make_integer_seq

[majnemer]

Summary

This new builtin template allows for incredibly fast instantiations of
templates like std::integer_sequence.

Performance numbers follow:
My work station has 64 GB of ram + 20 Xeon Cores at 2.8 GHz.

__make_integer_seq<std::integer_sequence, int, 90000> takes 0.25
seconds.

std::make_integer_sequence<int, 90000> takes unbound time, it is still
running. Clang is consuming gigabytes of memory.

[majnemer]

• Add an llvm_unreachable to ASTDeclReader::VisitBuiltinTemplateDecl

[rsmith]

include/clang/AST/TemplateName.h

93–100 ↗

(On Diff #37518)

Please add an enum for builtin template names (and pass it around when creating TemplateNames and BuiltinTemplateDecls as appropriate), even though it will only have one value for now.

lib/Parse/ParseDecl.cpp

2937–2939 ↗

(On Diff #37518)

Reflow this comment.

lib/Sema/SemaTemplate.cpp

2059–2101

Please factor this out into a separate function, CheckBuiltinTemplateIdType or similar.

2068–2070

I would prefer to see this structured as follows:

In the if chain below where we're dispatching on the type of the template, if the template is a BuiltinTemplateDecl, then do some special-case handling to compute the CanonType (which is really poorly / misleadingly named; it's just the underlying type, not the canonical type). In the __make_integer_sequence case, this would involve recursively calling back into CheckTemplateIdType to build the template-id for the expanded form.

This means you'll retain an intermediate TST between the __make_integer_seq and the ultimate type.

2082–2084

Is it worth putting some kind of upper bound on what we'll accept here?

[EricWF]

Cool! I imagine that a lot of parts of libc++ could benefit from this. Having something like this that slices parameter packs would probably help libc++ compile times for tuple. Is that something your considering as well?

[majnemer]

• Address Richard's review comments.

[majnemer]

• Add an llvm_unreachable to ASTDeclReader::VisitBuiltinTemplateDecl
• Address Richard's review comments.
• Add logic to check [intseq.intseq]p1.

[majnemer]

• Remove TemplateName::BuiltinTemplate

[majnemer]

• Rename BuiltinTemplateNameKind to BuiltinTemplateKind

[majnemer]

• Make __make_integer_seq parameters as implicit
• Remove Sema::Ident___make_integer_seq
• Remove extraneous whitespace change

[majnemer]

• Add test for __make_integer_seq

[majnemer]

@rsmith, I've kept the caching of the BuiltinTemplateDecl for __make_integer_seq as we keep falling into the LookupBuiltin. Is there more that must be done to get "normal" lookups to find the decl?

[majnemer]

Ping.

[rsmith]

lib/AST/ASTDumper.cpp

1340–1344

This seems redundant given that you dumped the name on the prior line.

lib/AST/DeclTemplate.cpp

1204

I think you mean T ...Ints (and likewise in comments below).

1229

This should be T N or similar, right? (In particular, it's not a pack.)

lib/Sema/SemaTemplate.cpp

2177–2179

Factor this out into a separate function to compute the canonical type for a builtin template; CheckTemplateIdType is long enough already :)

2211

Maybe use the location from the third template argument here?

lib/Serialization/ASTReaderDecl.cpp

1861

So what happens when we serialize an AST that references a builtin template? It's probably best to treat them as predefined declarations (look for existing references to PREDEF_DECL_* to see how this should fit in).

[majnemer]

• Add an llvm_unreachable to ASTDeclReader::VisitBuiltinTemplateDecl
• Address Richard's review comments.
• Add logic to check [intseq.intseq]p1.
• Remove TemplateName::BuiltinTemplate
• Rename BuiltinTemplateNameKind to BuiltinTemplateKind
• Make __make_integer_seq parameters as implicit
• Remove Sema::Ident___make_integer_seq
• Remove extraneous whitespace change
• Add test for __make_integer_seq
• Address Richard's review feedback

[rsmith]

Please add a test for serialization/deserialization of this declaration. Otherwise, this looks fine.

include/clang/Serialization/ASTBitCodes.h

994 ↗

(On Diff #39145)

Increase this by 1, please :)

lib/AST/DeclTemplate.cpp

1212

This should say T ...Ints too.

1217

And this.

1238

This should say T ...Ints and then T N

[majnemer]

• Address Richard's latest comments

include/clang/AST/ASTContext.h

namespace clang {
   class ObjCIvarDecl;
   class ObjCPropertyDecl;
   class UnresolvedSetIterator;
   class UsingDecl;
   class UsingShadowDecl;
   class VTableContextBase;
 
   namespace Builtin { class Context; }
+  enum BuiltinTemplateKind : int;
 
   namespace comments {
     class FullComment;
   }
 
   struct TypeInfo {
     uint64_t Width;
     unsigned Align;
class ASTContext : public RefCountedBase<ASTContext> {
   QualType ObjCSelRedefinitionType;
 
   /// The identifier 'NSObject'.
   IdentifierInfo *NSObjectName = nullptr;
 
   /// The identifier 'NSCopying'.
   IdentifierInfo *NSCopyingName = nullptr;
 
+  /// The identifier '__make_integer_seq'.
+  mutable IdentifierInfo *MakeIntegerSeqName = nullptr;
+
   QualType ObjCConstantStringType;
   mutable RecordDecl *CFConstantStringTypeDecl;
   
   mutable QualType ObjCSuperType;
   
   QualType ObjCNSStringType;
 
   /// \brief The typedef declaration for the Objective-C "instancetype" type.
private:
   typedef llvm::DenseMap<const VarDecl *, unsigned> ParameterIndexTable;
   ParameterIndexTable ParamIndices;  
   
   ImportDecl *FirstLocalImport;
   ImportDecl *LastLocalImport;
   
   TranslationUnitDecl *TUDecl;
   mutable ExternCContextDecl *ExternCContext;
+  mutable BuiltinTemplateDecl *MakeIntegerSeqDecl;
 
   /// \brief The associated SourceManager object.a
   SourceManager &SourceMgr;
 
   /// \brief The language options used to create the AST associated with
   ///  this ASTContext object.
   LangOptions &LangOpts;
 
ArrayRef<Module*> getModulesWithMergedDefinition(NamedDecl *Def) {
     if (MergedIt == MergedDefModules.end())
       return None;
     return MergedIt->second;
   }
 
   TranslationUnitDecl *getTranslationUnitDecl() const { return TUDecl; }
 
   ExternCContextDecl *getExternCContextDecl() const;
+  BuiltinTemplateDecl *getMakeIntegerSeqDecl() const;
 
   // Builtin Types.
   CanQualType VoidTy;
   CanQualType BoolTy;
   CanQualType CharTy;
   CanQualType WCharTy;  // [C++ 3.9.1p5].
   CanQualType WideCharTy; // Same as WCharTy in C++, integer type in C99.
   CanQualType WIntTy;   // [C99 7.24.1], integer type unchanged by default promotions.
public:
 
   /// \brief Retrieve a pointer to the AST mutation listener associated
   /// with this AST context, if any.
   ASTMutationListener *getASTMutationListener() const { return Listener; }
 
   void PrintStats() const;
   const SmallVectorImpl<Type *>& getTypes() const { return Types; }
 
+  BuiltinTemplateDecl *buildBuiltinTemplateDecl(BuiltinTemplateKind BTK,
+                                                const IdentifierInfo *II) const;
+
   /// \brief Create a new implicit TU-level CXXRecordDecl or RecordDecl
   /// declaration.
   RecordDecl *buildImplicitRecord(StringRef Name,
                                   RecordDecl::TagKind TK = TTK_Struct) const;
 
   /// \brief Create a new implicit TU-level typedef declaration.
   TypedefDecl *buildImplicitTypedef(QualType T, StringRef Name) const;
 
public:
   IdentifierInfo *getNSCopyingName() {
     if (!NSCopyingName) {
       NSCopyingName = &Idents.get("NSCopying");
     }
 
     return NSCopyingName;
   }
 
+  IdentifierInfo *getMakeIntegerSeqName() const {
+    if (!MakeIntegerSeqName)
+      MakeIntegerSeqName = &Idents.get("__make_integer_seq");
+    return MakeIntegerSeqName;
+  }
+
   /// \brief Retrieve the Objective-C "instancetype" type, if already known;
   /// otherwise, returns a NULL type;
   QualType getObjCInstanceType() {
     return getTypeDeclType(getObjCInstanceTypeDecl());
   }
 
   /// \brief Retrieve the typedef declaration corresponding to the Objective-C
   /// "instancetype" type.

include/clang/AST/DataRecursiveASTVisitor.h

DEF_TRAVERSE_DECL(FunctionTemplateDecl, {
   //
   // We only traverse the function instantiations when we see the canonical
   // declaration of the template, to ensure we only visit them once.
   if (getDerived().shouldVisitTemplateInstantiations() &&
       D == D->getCanonicalDecl())
     TRY_TO(TraverseFunctionInstantiations(D));
 })
 
+DEF_TRAVERSE_DECL(BuiltinTemplateDecl, {
+  TRY_TO(TraverseTemplateParameterListHelper(D->getTemplateParameters()));
+})
+
 DEF_TRAVERSE_DECL(TemplateTemplateParmDecl, {
   // D is the "T" in something like
   //   template <template <typename> class T> class container { };
   TRY_TO(TraverseDecl(D->getTemplatedDecl()));
   if (D->hasDefaultArgument()) {
     TRY_TO(TraverseTemplateArgumentLoc(D->getDefaultArgument()));
   }
   TRY_TO(TraverseTemplateParameterListHelper(D->getTemplateParameters()));

include/clang/AST/DeclTemplate.h

 #include "clang/AST/TemplateBase.h"
 #include "llvm/ADT/PointerUnion.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/TrailingObjects.h"
 #include <limits>
 
 namespace clang {
 
+enum BuiltinTemplateKind : int;
 class TemplateParameterList;
 class TemplateDecl;
 class RedeclarableTemplateDecl;
 class FunctionTemplateDecl;
 class ClassTemplateDecl;
 class ClassTemplatePartialSpecializationDecl;
 class TemplateTypeParmDecl;
 class NonTypeTemplateParmDecl;
public:
   static bool classof(const Decl *D) { return classofKind(D->getKind()); }
   static bool classofKind(Kind K) { return K == TemplateTemplateParm; }
 
   friend class ASTDeclReader;
   friend class ASTDeclWriter;
   friend TrailingObjects;
 };
 
+/// \brief Represents the builtin template declaration which is used to
+/// implement __make_integer_seq.  It serves no real purpose beyond existing as
+/// a place to hold template parameters.
+class BuiltinTemplateDecl : public TemplateDecl {
+  void anchor() override;
+
+  BuiltinTemplateDecl(const ASTContext &C, DeclContext *DC,
+                      DeclarationName Name, BuiltinTemplateKind BTK);
+
+  BuiltinTemplateKind BTK;
+
+public:
+  // Implement isa/cast/dyncast support
+  static bool classof(const Decl *D) { return classofKind(D->getKind()); }
+  static bool classofKind(Kind K) { return K == BuiltinTemplate; }
+
+  static BuiltinTemplateDecl *Create(const ASTContext &C, DeclContext *DC,
+                                     DeclarationName Name,
+                                     BuiltinTemplateKind BTK) {
+    return new (C, DC) BuiltinTemplateDecl(C, DC, Name, BTK);
+  }
+
+  SourceRange getSourceRange() const override LLVM_READONLY {
+    return SourceRange();
+  }
+
+  BuiltinTemplateKind getBuiltinTemplateKind() const { return BTK; }
+};
+
 /// \brief Represents a class template specialization, which refers to
 /// a class template with a given set of template arguments.
 ///
 /// Class template specializations represent both explicit
 /// specialization of class templates, as in the example below, and
 /// implicit instantiations of class templates.
 ///
 /// \code

include/clang/AST/RecursiveASTVisitor.h

DEF_TRAVERSE_DECL(TemplateTemplateParmDecl, {
   //   template <template <typename> class T> class container { };
   TRY_TO(TraverseDecl(D->getTemplatedDecl()));
   if (D->hasDefaultArgument() && !D->defaultArgumentWasInherited()) {
     TRY_TO(TraverseTemplateArgumentLoc(D->getDefaultArgument()));
   }
   TRY_TO(TraverseTemplateParameterListHelper(D->getTemplateParameters()));
 })
 
+DEF_TRAVERSE_DECL(BuiltinTemplateDecl, {
+  TRY_TO(TraverseTemplateParameterListHelper(D->getTemplateParameters()));
+})
+
 DEF_TRAVERSE_DECL(TemplateTypeParmDecl, {
   // D is the "T" in something like "template<typename T> class vector;"
   if (D->getTypeForDecl())
     TRY_TO(TraverseType(QualType(D->getTypeForDecl(), 0)));
   if (D->hasDefaultArgument() && !D->defaultArgumentWasInherited())
     TRY_TO(TraverseTypeLoc(D->getDefaultArgumentInfo()->getTypeLoc()));
 })
 

include/clang/Basic/Builtins.h

bool builtinIsSupported(const Builtin::Info &BuiltinInfo,
                           const LangOptions &LangOpts);
 
   /// \brief Helper function for isPrintfLike and isScanfLike.
   bool isLike(unsigned ID, unsigned &FormatIdx, bool &HasVAListArg,
               const char *Fmt) const;
 };
 
 }
+
+/// \brief Kinds of BuiltinTemplateDecl.
+enum BuiltinTemplateKind : int {
+  /// \brief This names the __make_integer_seq BuiltinTemplateDecl.
+  BTK__make_integer_seq
+};
+
 } // end namespace clang
 #endif

include/clang/Basic/DeclNodes.td

def Declarator : DDecl<Value, 1>;
       def NonTypeTemplateParm : DDecl<Declarator>;
   def Template : DDecl<Named, 1>;
     def RedeclarableTemplate : DDecl<Template, 1>;
       def FunctionTemplate : DDecl<RedeclarableTemplate>;
       def ClassTemplate : DDecl<RedeclarableTemplate>;
       def VarTemplate : DDecl<RedeclarableTemplate>;
       def TypeAliasTemplate : DDecl<RedeclarableTemplate>;
     def TemplateTemplateParm : DDecl<Template>;
+    def BuiltinTemplate : DDecl<Template>;
   def Using : DDecl<Named>;
   def UsingShadow : DDecl<Named>;
   def ObjCMethod : DDecl<Named>, DeclContext;
   def ObjCContainer : DDecl<Named, 1>, DeclContext;
     def ObjCCategory : DDecl<ObjCContainer>;
     def ObjCProtocol : DDecl<ObjCContainer>;
     def ObjCInterface : DDecl<ObjCContainer>;
     def ObjCImpl : DDecl<ObjCContainer, 1>;

include/clang/Basic/DiagnosticSemaKinds.td

 def err_concept_decl_invalid_specifiers : Error<
   "%select{variable|function}0 concept cannot be declared "
   "'%select{thread_local|inline|friend|constexpr}1'">;
 
 // C++11 char16_t/char32_t
 def warn_cxx98_compat_unicode_type : Warning<
   "'%0' type specifier is incompatible with C++98">,
   InGroup<CXX98Compat>, DefaultIgnore;
- 
+// __make_integer_seq
+def err_integer_sequence_negative_length : Error<
+  "integer sequences must have non-negative sequence length">;
+def err_integer_sequence_integral_element_type : Error<
+  "integer sequences must have integral element type">;
+
 // Objective-C++
 def err_objc_decls_may_only_appear_in_global_scope : Error<
   "Objective-C declarations may only appear in global scope">;
 def warn_auto_var_is_id : Warning<
   "'auto' deduced as 'id' in declaration of %0">,
   InGroup<DiagGroup<"auto-var-id">>;
 
 // Attributes

include/clang/Sema/Sema.h

private:
 
   /// \brief The parser's current scope.
   ///
   /// The parser maintains this state here.
   Scope *CurScope;
 
   mutable IdentifierInfo *Ident_super;
   mutable IdentifierInfo *Ident___float128;
+  mutable IdentifierInfo *Ident___make_integer_seq;
 
   /// Nullability type specifiers.
   IdentifierInfo *Ident__Nonnull = nullptr;
   IdentifierInfo *Ident__Nullable = nullptr;
   IdentifierInfo *Ident__Null_unspecified = nullptr;
 
   IdentifierInfo *Ident_NSError = nullptr;
 
public:
   Scope *getCurScope() const { return CurScope; }
 
   void incrementMSManglingNumber() const {
     return CurScope->incrementMSManglingNumber();
   }
 
   IdentifierInfo *getSuperIdentifier() const;
   IdentifierInfo *getFloat128Identifier() const;
+  IdentifierInfo *getMakeIntegerSeqIdentifier() const;
 
   Decl *getObjCDeclContext() const;
 
   DeclContext *getCurLexicalContext() const {
     return OriginalLexicalContext ? OriginalLexicalContext : CurContext;
   }
 
   AvailabilityResult getCurContextAvailability() const;

lib/AST/ASTContext.cpp

: FunctionProtoTypes(this_()), TemplateSpecializationTypes(this_()),
       BuiltinVaListDecl(nullptr), BuiltinMSVaListDecl(nullptr),
       ObjCIdDecl(nullptr), ObjCSelDecl(nullptr), ObjCClassDecl(nullptr),
       ObjCProtocolClassDecl(nullptr), BOOLDecl(nullptr),
       CFConstantStringTypeDecl(nullptr), ObjCInstanceTypeDecl(nullptr),
       FILEDecl(nullptr), jmp_bufDecl(nullptr), sigjmp_bufDecl(nullptr),
       ucontext_tDecl(nullptr), BlockDescriptorType(nullptr),
       BlockDescriptorExtendedType(nullptr), cudaConfigureCallDecl(nullptr),
       FirstLocalImport(), LastLocalImport(), ExternCContext(nullptr),
-      SourceMgr(SM), LangOpts(LOpts),
+      MakeIntegerSeqDecl(nullptr), SourceMgr(SM), LangOpts(LOpts),
       SanitizerBL(new SanitizerBlacklist(LangOpts.SanitizerBlacklistFiles, SM)),
       AddrSpaceMap(nullptr), Target(nullptr), AuxTarget(nullptr),
       PrintingPolicy(LOpts), Idents(idents), Selectors(sels),
       BuiltinInfo(builtins), DeclarationNames(*this), ExternalSource(nullptr),
       Listener(nullptr), Comments(SM), CommentsLoaded(false),
       CommentCommandTraits(BumpAlloc, LOpts.CommentOpts), LastSDM(nullptr, 0) {
   TUDecl = TranslationUnitDecl::Create(*this);
 }

 
 ExternCContextDecl *ASTContext::getExternCContextDecl() const {
   if (!ExternCContext)
     ExternCContext = ExternCContextDecl::Create(*this, getTranslationUnitDecl());
 
   return ExternCContext;
 }
 
+BuiltinTemplateDecl *
+ASTContext::buildBuiltinTemplateDecl(BuiltinTemplateKind BTK,
+                                     const IdentifierInfo *II) const {
+  auto *BuiltinTemplate = BuiltinTemplateDecl::Create(*this, TUDecl, II, BTK);
+  BuiltinTemplate->setImplicit();
+  TUDecl->addDecl(BuiltinTemplate);
+
+  return BuiltinTemplate;
+}
+
+BuiltinTemplateDecl *
+ASTContext::getMakeIntegerSeqDecl() const {
+  if (!MakeIntegerSeqDecl)
+    MakeIntegerSeqDecl = buildBuiltinTemplateDecl(BTK__make_integer_seq,
+                                                  getMakeIntegerSeqName());
+  return MakeIntegerSeqDecl;
+}
+
 RecordDecl *ASTContext::buildImplicitRecord(StringRef Name,
                                             RecordDecl::TagKind TK) const {
   SourceLocation Loc;
   RecordDecl *NewDecl;
   if (getLangOpts().CPlusPlus)
     NewDecl = CXXRecordDecl::Create(*this, TK, getTranslationUnitDecl(), Loc,
                                     Loc, &Idents.get(Name));
   else

lib/AST/ASTDumper.cpp

 #include "clang/AST/Attr.h"
 #include "clang/AST/CommentVisitor.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclLookups.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/DeclVisitor.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/AST/TypeVisitor.h"
+#include "clang/Basic/Builtins.h"
 #include "clang/Basic/Module.h"
 #include "clang/Basic/SourceManager.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace clang;
 using namespace clang::comments;
 
 //===----------------------------------------------------------------------===//
 // ASTDumper Visitor
public:
     void VisitFunctionTemplateDecl(const FunctionTemplateDecl *D);
     void VisitClassTemplateDecl(const ClassTemplateDecl *D);
     void VisitClassTemplateSpecializationDecl(
         const ClassTemplateSpecializationDecl *D);
     void VisitClassTemplatePartialSpecializationDecl(
         const ClassTemplatePartialSpecializationDecl *D);
     void VisitClassScopeFunctionSpecializationDecl(
         const ClassScopeFunctionSpecializationDecl *D);
+    void VisitBuiltinTemplateDecl(const BuiltinTemplateDecl *D);
     void VisitVarTemplateDecl(const VarTemplateDecl *D);
     void VisitVarTemplateSpecializationDecl(
         const VarTemplateSpecializationDecl *D);
     void VisitVarTemplatePartialSpecializationDecl(
         const VarTemplatePartialSpecializationDecl *D);
     void VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D);
     void VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl *D);
     void VisitTemplateTemplateParmDecl(const TemplateTemplateParmDecl *D);
void ASTDumper::VisitClassScopeFunctionSpecializationDecl(
   if (D->hasExplicitTemplateArgs())
     dumpTemplateArgumentListInfo(D->templateArgs());
 }
 
 void ASTDumper::VisitVarTemplateDecl(const VarTemplateDecl *D) {
   VisitTemplateDecl(D, false);
 }
 
+void ASTDumper::VisitBuiltinTemplateDecl(const BuiltinTemplateDecl *D) {
+  dumpName(D);
+  switch (D->getBuiltinTemplateKind()) {
+  case BTK__make_integer_seq:
+    OS << " __make_integer_seq";
+    break;
+  }
+  dumpTemplateParameters(D->getTemplateParameters());
+}
+
 void ASTDumper::VisitVarTemplateSpecializationDecl(
     const VarTemplateSpecializationDecl *D) {
   dumpTemplateArgumentList(D->getTemplateArgs());
   VisitVarDecl(D);
 }
 
 void ASTDumper::VisitVarTemplatePartialSpecializationDecl(
     const VarTemplatePartialSpecializationDecl *D) {

lib/AST/DeclBase.cpp

switch (DeclKind) {
     case StaticAssert:
     case ObjCPropertyImpl:
     case Block:
     case Captured:
     case TranslationUnit:
     case ExternCContext:
 
     case UsingDirective:
+    case BuiltinTemplate:
     case ClassTemplateSpecialization:
     case ClassTemplatePartialSpecialization:
     case ClassScopeFunctionSpecialization:
     case VarTemplateSpecialization:
     case VarTemplatePartialSpecialization:
     case ObjCImplementation:
     case ObjCCategory:
     case ObjCCategoryImpl:

lib/AST/DeclTemplate.cpp

 
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTMutationListener.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/TypeLoc.h"
+#include "clang/Basic/Builtins.h"
 #include "clang/Basic/IdentifierTable.h"
 #include "llvm/ADT/STLExtras.h"
 #include <memory>
 using namespace clang;
 
 //===----------------------------------------------------------------------===//
 // TemplateParameterList Implementation
 //===----------------------------------------------------------------------===//
VarTemplatePartialSpecializationDecl::Create(
   return Result;
 }
 
 VarTemplatePartialSpecializationDecl *
 VarTemplatePartialSpecializationDecl::CreateDeserialized(ASTContext &C,
                                                          unsigned ID) {
   return new (C, ID) VarTemplatePartialSpecializationDecl(C);
 }
+
+static TemplateParameterList *
+createMakeIntegerSeqParameterList(const ASTContext &C, DeclContext *DC) {
+  // typename T
+  auto *T = TemplateTypeParmDecl::Create(
+      C, DC, SourceLocation(), SourceLocation(), /*Depth=*/1, /*Position=*/0,
+      /*Id=*/nullptr, /*Typename=*/true, /*ParameterPack=*/false);
+
+  // Ints...
+  TypeSourceInfo *TI =
+      C.getTrivialTypeSourceInfo(QualType(T->getTypeForDecl(), 0));
+  auto *N = NonTypeTemplateParmDecl::Create(
+      C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/1,
+      /*Id=*/nullptr, TI->getType(), /*ParameterPack=*/true, TI);
+
+  // <typename T, Ints...>
+  NamedDecl *P[2] = {T, N};
+  auto *TPL = TemplateParameterList::Create(
+      C, SourceLocation(), SourceLocation(), P, 2, SourceLocation());
+
+  // template <typename T, Ints...> class IntSeq
+  auto *TemplateTemplateParm = TemplateTemplateParmDecl::Create(
+      C, DC, SourceLocation(), /*Depth=*/0, /*Position=*/0,
+      /*ParameterPack=*/false, /*Id=*/nullptr, TPL);
+
+  // typename T
+  auto *TemplateTypeParm = TemplateTypeParmDecl::Create(
+      C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/1,
+      /*Id=*/nullptr, /*Typename=*/true, /*ParameterPack=*/false);
+
+  // Ints...
+  TypeSourceInfo *TInfo = C.getTrivialTypeSourceInfo(
+      QualType(TemplateTypeParm->getTypeForDecl(), 0));
+  auto *NonTypeTemplateParm = NonTypeTemplateParmDecl::Create(
+      C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/2,
+      /*Id=*/nullptr, TInfo->getType(), /*ParameterPack=*/false, TInfo);
+  NamedDecl *Params[] = {TemplateTemplateParm, TemplateTypeParm,
+                         NonTypeTemplateParm};
+
+  // template <template <typename T, Ints...> class IntSeq, typename T, Ints...>
+  return TemplateParameterList::Create(C, SourceLocation(), SourceLocation(),
+                                       Params, 3, SourceLocation());
+}
+
+static TemplateParameterList *createBuiltinTemplateParameterList(
+    const ASTContext &C, DeclContext *DC, BuiltinTemplateKind BTK) {
+  switch (BTK) {
+  case BTK__make_integer_seq:
+    return createMakeIntegerSeqParameterList(C, DC);
+  }
+
+  llvm_unreachable("unhandled BuiltinTemplateKind!");
+}
+
+void BuiltinTemplateDecl::anchor() {}
+
+BuiltinTemplateDecl::BuiltinTemplateDecl(const ASTContext &C, DeclContext *DC,
+                                         DeclarationName Name,
+                                         BuiltinTemplateKind BTK)
+    : TemplateDecl(BuiltinTemplate, DC, SourceLocation(), Name,
+                   createBuiltinTemplateParameterList(C, DC, BTK)),
+      BTK(BTK) {}

lib/CodeGen/CGDecl.cpp

 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Type.h"
 using namespace clang;
 using namespace CodeGen;
 
 
 void CodeGenFunction::EmitDecl(const Decl &D) {
   switch (D.getKind()) {
+  case Decl::BuiltinTemplate:
   case Decl::TranslationUnit:
   case Decl::ExternCContext:
   case Decl::Namespace:
   case Decl::UnresolvedUsingTypename:
   case Decl::ClassTemplateSpecialization:
   case Decl::ClassTemplatePartialSpecialization:
   case Decl::VarTemplateSpecialization:
   case Decl::VarTemplatePartialSpecialization:

lib/Sema/Sema.cpp

: ExternalSource(nullptr),
     TUKind(TUKind),
     NumSFINAEErrors(0),
     CachedFakeTopLevelModule(nullptr),
     AccessCheckingSFINAE(false), InNonInstantiationSFINAEContext(false),
     NonInstantiationEntries(0), ArgumentPackSubstitutionIndex(-1),
     CurrentInstantiationScope(nullptr), DisableTypoCorrection(false),
     TyposCorrected(0), AnalysisWarnings(*this), ThreadSafetyDeclCache(nullptr),
     VarDataSharingAttributesStack(nullptr), CurScope(nullptr),
-    Ident_super(nullptr), Ident___float128(nullptr)
+    Ident_super(nullptr), Ident___float128(nullptr),
+    Ident___make_integer_seq(nullptr)
 {
   TUScope = nullptr;
 
   LoadedExternalKnownNamespaces = false;
   for (unsigned I = 0; I != NSAPI::NumNSNumberLiteralMethods; ++I)
     NSNumberLiteralMethods[I] = nullptr;
 
   if (getLangOpts().ObjC1)

lib/Sema/SemaLookup.cpp

if (NameKind == Sema::LookupOrdinaryName ||
     if (II) {
       if (S.getLangOpts().CPlusPlus11 && S.getLangOpts().GNUMode &&
           II == S.getFloat128Identifier()) {
         // libstdc++4.7's type_traits expects type __float128 to exist, so
         // insert a dummy type to make that header build in gnu++11 mode.
         R.addDecl(S.getASTContext().getFloat128StubType());
         return true;
       }
+      if (S.getLangOpts().CPlusPlus && NameKind == Sema::LookupOrdinaryName &&
+          II == S.getASTContext().getMakeIntegerSeqName()) {
+        R.addDecl(S.getASTContext().getMakeIntegerSeqDecl());
+        return true;
+      }
 
       // If this is a builtin on this (or all) targets, create the decl.
       if (unsigned BuiltinID = II->getBuiltinID()) {
         // In C++, we don't have any predefined library functions like
         // 'malloc'. Instead, we'll just error.
         if (S.getLangOpts().CPlusPlus &&
             S.Context.BuiltinInfo.isPredefinedLibFunction(BuiltinID))
           return false;

lib/Sema/SemaTemplate.cpp

 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/DeclFriend.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/TypeVisitor.h"
+#include "clang/Basic/Builtins.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/PartialDiagnostic.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/Sema/DeclSpec.h"
 #include "clang/Sema/Lookup.h"
 #include "clang/Sema/ParsedTemplate.h"
 #include "clang/Sema/Scope.h"
 #include "clang/Sema/SemaInternal.h"
if (ResultCount > 1) {
 
     if (isa<FunctionTemplateDecl>(TD)) {
       TemplateKind = TNK_Function_template;
 
       // We'll do this lookup again later.
       R.suppressDiagnostics();
     } else {
       assert(isa<ClassTemplateDecl>(TD) || isa<TemplateTemplateParmDecl>(TD) ||
-             isa<TypeAliasTemplateDecl>(TD) || isa<VarTemplateDecl>(TD));
+             isa<TypeAliasTemplateDecl>(TD) || isa<VarTemplateDecl>(TD) ||
+             isa<BuiltinTemplateDecl>(TD));
       TemplateKind =
           isa<VarTemplateDecl>(TD) ? TNK_Var_template : TNK_Type_template;
     }
   }
 
   TemplateResult = TemplateTy::make(Template);
   return TemplateKind;
 }
if (DTN && DTN->isIdentifier())
     // correct, or the code is ill-formed and will be diagnosed when the
     // dependent name is substituted.
     return Context.getDependentTemplateSpecializationType(ETK_None,
                                                           DTN->getQualifier(),
                                                           DTN->getIdentifier(),
                                                           TemplateArgs);
 
   TemplateDecl *Template = Name.getAsTemplateDecl();
+
   if (!Template || isa<FunctionTemplateDecl>(Template) ||
       isa<VarTemplateDecl>(Template)) {
     // We might have a substituted template template parameter pack. If so,
     // build a template specialization type for it.
     if (Name.getAsSubstTemplateTemplateParmPack())
       return Context.getTemplateSpecializationType(Name, TemplateArgs);
 
     Diag(TemplateLoc, diag::err_template_id_not_a_type)
       << Name;
     NoteAllFoundTemplates(Name);
     return QualType();
   }
 
   // Check that the template argument list is well-formed for this
   // template.
   SmallVector<TemplateArgument, 4> Converted;
   if (CheckTemplateArgumentList(Template, TemplateLoc, TemplateArgs,
                                 false, Converted))
     return QualType();
 
   QualType CanonType;
 
   bool InstantiationDependent = false;
   if (TypeAliasTemplateDecl *AliasTemplate =
           dyn_cast<TypeAliasTemplateDecl>(Template)) {
     // Find the canonical type for this type alias template specialization.
     TypeAliasDecl *Pattern = AliasTemplate->getTemplatedDecl();
     if (Pattern->isInvalidDecl())
       return QualType();
 
     TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
                                       Converted.data(), Converted.size());
 
     // Only substitute for the innermost template argument list.
     MultiLevelTemplateArgumentList TemplateArgLists;
     TemplateArgLists.addOuterTemplateArguments(&TemplateArgs);
     unsigned Depth = AliasTemplate->getTemplateParameters()->getDepth();
     for (unsigned I = 0; I < Depth; ++I)
       TemplateArgLists.addOuterTemplateArguments(None);
 
     LocalInstantiationScope Scope(*this);
     InstantiatingTemplate Inst(*this, TemplateLoc, Template);
     if (Inst.isInvalid())
       return QualType();
 
     CanonType = SubstType(Pattern->getUnderlyingType(),
                           TemplateArgLists, AliasTemplate->getLocation(),
                           AliasTemplate->getDeclName());
     if (CanonType.isNull())
       return QualType();
   } else if (Name.isDependent() ||
              TemplateSpecializationType::anyDependentTemplateArguments(
                TemplateArgs, InstantiationDependent)) {
     // This class template specialization is a dependent
     // type. Therefore, its canonical type is another class template
     // specialization type that contains all of the converted
     // arguments in canonical form. This ensures that, e.g., A<T> and
     // A<T, T> have identical types when A is declared as:
     //
     //   template<typename T, typename U = T> struct A;
     TemplateName CanonName = Context.getCanonicalTemplateName(Name);
     CanonType = Context.getTemplateSpecializationType(CanonName,
                                                       Converted.data(),
                                                       Converted.size());
 
     // FIXME: CanonType is not actually the canonical type, and unfortunately
     // it is a TemplateSpecializationType that we will never use again.
     // In the future, we need to teach getTemplateSpecializationType to only
     // build the canonical type and return that to us.
     CanonType = Context.getCanonicalType(CanonType);
 
if (TypeAliasTemplateDecl *AliasTemplate =
     }
 
     // Diagnose uses of this specialization.
     (void)DiagnoseUseOfDecl(Decl, TemplateLoc);
 
     CanonType = Context.getTypeDeclType(Decl);
     assert(isa<RecordType>(CanonType) &&
            "type of non-dependent specialization is not a RecordType");
+  } else if (auto *BTD = dyn_cast<BuiltinTemplateDecl>(Template)) {
+    switch (BTD->getBuiltinTemplateKind()) {
+    case BTK__make_integer_seq:
+      // Specializations of __make_integer_seq<S, T, N> are treated like
+      // S<T, 0, ..., N-1>.
+
+      // C++14 [inteseq.intseq]p1:
+      //   T shall be an integer type.
+      if (!Converted[1].getAsType()->isIntegralType(Context)) {
+        Diag(TemplateArgs[1].getLocation(),
+             diag::err_integer_sequence_integral_element_type);
+        return QualType();
+      }
+
+      // C++14 [inteseq.make]p1:
+      //   If N is negative the program is ill-formed.
+      TemplateArgument NumArgsArg = Converted[2];
+      llvm::APSInt NumArgs = NumArgsArg.getAsIntegral();
+      if (NumArgs < 0) {
+        Diag(TemplateArgs[2].getLocation(),
+             diag::err_integer_sequence_negative_length);
+        return QualType();
+      }
+
+      QualType ArgTy = NumArgsArg.getIntegralType();
+      TemplateArgumentListInfo SyntheticTemplateArgs;
+      // The type argument gets reused as the first template argument in the
+      // synthetic template argument list.
+      SyntheticTemplateArgs.addArgument(TemplateArgs[1]);
+      // Expand N into 0 ... N-1.
+      for (llvm::APSInt I(NumArgs.getBitWidth(), NumArgs.isUnsigned());
+           I < NumArgs; ++I) {
+        TemplateArgument TA(Context, I, ArgTy);
+        Expr *E =
+            BuildExpressionFromIntegralTemplateArgument(TA, SourceLocation())
+                .getAs<Expr>();
+        SyntheticTemplateArgs.addArgument(
+            TemplateArgumentLoc(TemplateArgument(E), E));
+      }
+      // The first template argument will be reused as the template decl that
+      // our synthetic template arguments will be applied to.
+      CanonType = CheckTemplateIdType(Converted[0].getAsTemplate(), TemplateLoc,
+                                      SyntheticTemplateArgs);
+      break;
+    }
   }
 
   // Build the fully-sugared type for this class template
   // specialization, which refers back to the class template
   // specialization we created or found.
   return Context.getTemplateSpecializationType(Name, TemplateArgs, CanonType);
 }
 

lib/Sema/SemaTemplateInstantiateDecl.cpp

SemaRef.ActOnEnumBody(Enum->getLocation(), SourceLocation(),
                         Enumerators,
                         nullptr, nullptr);
 }
 
 Decl *TemplateDeclInstantiator::VisitEnumConstantDecl(EnumConstantDecl *D) {
   llvm_unreachable("EnumConstantDecls can only occur within EnumDecls.");
 }
 
+Decl *
+TemplateDeclInstantiator::VisitBuiltinTemplateDecl(BuiltinTemplateDecl *D) {
+  llvm_unreachable("BuiltinTemplateDecls cannot be instantiated.");
+}
+
 Decl *TemplateDeclInstantiator::VisitClassTemplateDecl(ClassTemplateDecl *D) {
   bool isFriend = (D->getFriendObjectKind() != Decl::FOK_None);
 
   // Create a local instantiation scope for this class template, which
   // will contain the instantiations of the template parameters.
   LocalInstantiationScope Scope(SemaRef);
   TemplateParameterList *TempParams = D->getTemplateParameters();
   TemplateParameterList *InstParams = SubstTemplateParams(TempParams);

lib/Serialization/ASTCommon.cpp

bool serialization::isRedeclarableDeclKind(unsigned Kind) {
   case Decl::Friend:
   case Decl::FriendTemplate:
   case Decl::StaticAssert:
   case Decl::Block:
   case Decl::Captured:
   case Decl::ClassScopeFunctionSpecialization:
   case Decl::Import:
   case Decl::OMPThreadPrivate:
+  case Decl::BuiltinTemplate:
     return false;
 
   // These indirectly derive from Redeclarable<T> but are not actually
   // redeclarable.
   case Decl::ImplicitParam:
   case Decl::ParmVar:
   case Decl::ObjCTypeParam:
     return false;

lib/Serialization/ASTReaderDecl.cpp

public:
     RedeclarableResult VisitVarDeclImpl(VarDecl *D);
     void VisitVarDecl(VarDecl *VD) { VisitVarDeclImpl(VD); }
     void VisitImplicitParamDecl(ImplicitParamDecl *PD);
     void VisitParmVarDecl(ParmVarDecl *PD);
     void VisitNonTypeTemplateParmDecl(NonTypeTemplateParmDecl *D);
     DeclID VisitTemplateDecl(TemplateDecl *D);
     RedeclarableResult VisitRedeclarableTemplateDecl(RedeclarableTemplateDecl *D);
     void VisitClassTemplateDecl(ClassTemplateDecl *D);
+    void VisitBuiltinTemplateDecl(BuiltinTemplateDecl *D);
     void VisitVarTemplateDecl(VarTemplateDecl *D);
     void VisitFunctionTemplateDecl(FunctionTemplateDecl *D);
     void VisitTemplateTemplateParmDecl(TemplateTemplateParmDecl *D);
     void VisitTypeAliasTemplateDecl(TypeAliasTemplateDecl *D);
     void VisitUsingDecl(UsingDecl *D);
     void VisitUsingShadowDecl(UsingShadowDecl *D);
     void VisitLinkageSpecDecl(LinkageSpecDecl *D);
     void VisitFileScopeAsmDecl(FileScopeAsmDecl *AD);
if (D->getTemplatedDecl()->TemplateOrInstantiation) {
     // We were loaded before our templated declaration was. We've not set up
     // its corresponding type yet (see VisitCXXRecordDeclImpl), so reconstruct
     // it now.
     Reader.Context.getInjectedClassNameType(
         D->getTemplatedDecl(), D->getInjectedClassNameSpecialization());
   }
 }
 
+void ASTDeclReader::VisitBuiltinTemplateDecl(BuiltinTemplateDecl *D) {
+  llvm_unreachable("BuiltinTemplates are not serialized");
+}
+
 /// TODO: Unify with ClassTemplateDecl version?
 ///       May require unifying ClassTemplateDecl and
 ///        VarTemplateDecl beyond TemplateDecl...
 void ASTDeclReader::VisitVarTemplateDecl(VarTemplateDecl *D) {
   RedeclarableResult Redecl = VisitRedeclarableTemplateDecl(D);
 
   if (ThisDeclID == Redecl.getFirstID()) {
     // This VarTemplateDecl owns a CommonPtr; read it to keep track of all of

tools/libclang/CIndex.cpp

CXCursor clang_getCursorDefinition(CXCursor C) {
   case Decl::StaticAssert:
   case Decl::Block:
   case Decl::Captured:
   case Decl::Label:  // FIXME: Is this right??
   case Decl::ClassScopeFunctionSpecialization:
   case Decl::Import:
   case Decl::OMPThreadPrivate:
   case Decl::ObjCTypeParam:
+  case Decl::BuiltinTemplate:
     return C;
 
   // Declaration kinds that don't make any sense here, but are
   // nonetheless harmless.
   case Decl::Empty:
   case Decl::TranslationUnit:
   case Decl::ExternCContext:
     break;