[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

99–106

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

Reflow this comment.

lib/Sema/SemaTemplate.cpp

2068–2110

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

2077–2079

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.

2091–2093

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

2186–2188

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

2220

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 BuiltinTemplateNameKind : int;
 
   namespace comments {
     class FullComment;
   }
 
   struct TypeInfo {
     uint64_t Width;
     unsigned Align;
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(BuiltinTemplateNameKind BTNK) 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;
 
QualType getUnqualifiedObjCPointerType(QualType type) const {
     Qualifiers Qs = type.getQualifiers();
     Qs.removeObjCLifetime();
     return getQualifiedType(type.getUnqualifiedType(), Qs);
   }
   
   DeclarationNameInfo getNameForTemplate(TemplateName Name,
                                          SourceLocation NameLoc) const;
 
+  TemplateName getBuiltinTemplateName(BuiltinTemplateNameKind BTNK) const;
+
   TemplateName getOverloadedTemplateName(UnresolvedSetIterator Begin,
                                          UnresolvedSetIterator End) const;
 
   TemplateName getQualifiedTemplateName(NestedNameSpecifier *NNS,
                                         bool TemplateKeyword,
                                         TemplateDecl *Template) const;
 
   TemplateName getDependentTemplateName(NestedNameSpecifier *NNS,

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 BuiltinTemplateNameKind : 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, BuiltinTemplateNameKind BTNK,
+                      DeclContext *DC);
+
+  BuiltinTemplateNameKind BTNK;
+
+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, BuiltinTemplateNameKind BTNK, DeclContext *DC) {
+    return new (C, DC) BuiltinTemplateDecl(C, BTNK, DC);
+  }
+
+  SourceRange getSourceRange() const override LLVM_READONLY {
+    return SourceRange();
+  }
+
+  BuiltinTemplateNameKind getBuiltinTemplateNameKind() const { return BTNK; }
+};
+
 /// \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/AST/TemplateName.h

 
 #include "clang/Basic/LLVM.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/PointerUnion.h"
 
 namespace clang {
   
 class ASTContext;
+class BuiltinTemplateStorage;
+enum BuiltinTemplateNameKind : int;
 class DependentTemplateName;
 class DiagnosticBuilder;
 class IdentifierInfo;
 class NamedDecl;
 class NestedNameSpecifier;
 enum OverloadedOperatorKind : int;
 class OverloadedTemplateStorage;
 struct PrintingPolicy;
 class QualifiedTemplateName;
 class SubstTemplateTemplateParmPackStorage;
 class SubstTemplateTemplateParmStorage;
 class TemplateArgument;
 class TemplateDecl;
 class TemplateTemplateParmDecl;
   
 /// \brief Implementation class used to describe either a set of overloaded
 /// template names or an already-substituted template template parameter pack.
 class UncommonTemplateNameStorage {
 protected:
   enum Kind {
+    Builtin,
     Overloaded,
     SubstTemplateTemplateParm,
     SubstTemplateTemplateParmPack
   };
 
   struct BitsTag {
     /// \brief A Kind.
     unsigned Kind : 2;
protected:
   
   UncommonTemplateNameStorage(Kind kind, unsigned size) {
     Bits.Kind = kind;
     Bits.Size = size;
   }
   
 public:
   unsigned size() const { return Bits.Size; }
-  
+  BuiltinTemplateStorage *getAsBuiltinTemplate() {
+    return Bits.Kind == Builtin
+               ? reinterpret_cast<BuiltinTemplateStorage *>(this)
+               : nullptr;
+  }
+
   OverloadedTemplateStorage *getAsOverloadedStorage()  {
     return Bits.Kind == Overloaded
              ? reinterpret_cast<OverloadedTemplateStorage *>(this) 
              : nullptr;
   }
   
   SubstTemplateTemplateParmStorage *getAsSubstTemplateTemplateParm() {
     return Bits.Kind == SubstTemplateTemplateParm
              ? reinterpret_cast<SubstTemplateTemplateParmStorage *>(this)
              : nullptr;
   }
 
   SubstTemplateTemplateParmPackStorage *getAsSubstTemplateTemplateParmPack() {
     return Bits.Kind == SubstTemplateTemplateParmPack
              ? reinterpret_cast<SubstTemplateTemplateParmPackStorage *>(this)
              : nullptr;
   }
 };
-  
 /// \brief A structure for storing the information associated with an
+/// builtin template name.
+class BuiltinTemplateStorage : public UncommonTemplateNameStorage {
+  friend class ASTContext;
+  BuiltinTemplateNameKind BTNK;
+
+public:
+  BuiltinTemplateStorage(BuiltinTemplateNameKind BTNK)
+      : UncommonTemplateNameStorage(Builtin, 0), BTNK(BTNK) {}
+
+  BuiltinTemplateNameKind getKind() const { return BTNK; }
+};
+
+/// \brief A structure for storing the information associated with an
 /// overloaded template name.
 class OverloadedTemplateStorage : public UncommonTemplateNameStorage {
   friend class ASTContext;
 
   OverloadedTemplateStorage(unsigned size) 
     : UncommonTemplateNameStorage(Overloaded, size) { }
 
   NamedDecl **getStorage() {
explicit TemplateName(void *Ptr) {
     Storage = StorageType::getFromOpaqueValue(Ptr);
   }
 
 public:
   // \brief Kind of name that is actually stored.
   enum NameKind {
     /// \brief A single template declaration.
     Template,
+    /// \brief A builtin, compiler defined template.
+    BuiltinTemplate,
     /// \brief A set of overloaded template declarations.
     OverloadedTemplate,
-    /// \brief A qualified template name, where the qualification is kept 
+    /// \brief A qualified template name, where the qualification is kept
     /// to describe the source code as written.
     QualifiedTemplate,
-    /// \brief A dependent template name that has not been resolved to a 
+    /// \brief A dependent template name that has not been resolved to a
     /// template (or set of templates).
     DependentTemplate,
     /// \brief A template template parameter that has been substituted
     /// for some other template name.
     SubstTemplateTemplateParm,
-    /// \brief A template template parameter pack that has been substituted for 
+    /// \brief A template template parameter pack that has been substituted for
     /// a template template argument pack, but has not yet been expanded into
     /// individual arguments.
     SubstTemplateTemplateParmPack
   };
 
   TemplateName() : Storage() { }
   explicit TemplateName(TemplateDecl *Template) : Storage(Template) { }
+  explicit TemplateName(BuiltinTemplateStorage *Storage) : Storage(Storage) {}
   explicit TemplateName(OverloadedTemplateStorage *Storage)
     : Storage(Storage) { }
   explicit TemplateName(SubstTemplateTemplateParmStorage *Storage);
   explicit TemplateName(SubstTemplateTemplateParmPackStorage *Storage)
     : Storage(Storage) { }
   explicit TemplateName(QualifiedTemplateName *Qual) : Storage(Qual) { }
   explicit TemplateName(DependentTemplateName *Dep) : Storage(Dep) { }
 
public:
   }
 
   /// \brief Retrieve the underlying dependent template name
   /// structure, if any.
   DependentTemplateName *getAsDependentTemplateName() const {
     return Storage.dyn_cast<DependentTemplateName *>();
   }
 
+  /// \brief Retrieve the underlying builtin template name structure, if any.
+  BuiltinTemplateStorage *getAsBuiltinTemplate() const {
+    if (auto *Uncommon = Storage.dyn_cast<UncommonTemplateNameStorage *>())
+      return Uncommon->getAsBuiltinTemplate();
+    return nullptr;
+  }
+
   TemplateName getUnderlying() const;
 
   /// \brief Determines whether this is a dependent template name.
   bool isDependent() const;
 
   /// \brief Determines whether this is a template name that somehow
   /// depends on a template parameter.
   bool isInstantiationDependent() const;

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 BuiltinTemplate TemplateNames.
+enum BuiltinTemplateNameKind : int {
+  /// \brief This names the __make_integer_seq BuiltinTemplateDecl.
+  BTNK__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 cannot have a negative sequence length">;
+
 // 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/Basic/TokenKinds.def

 KEYWORD(__declspec                  , 0)
 
 // Microsoft Extension.
 KEYWORD(__cdecl                     , KEYALL)
 KEYWORD(__stdcall                   , KEYALL)
 KEYWORD(__fastcall                  , KEYALL)
 KEYWORD(__thiscall                  , KEYALL)
 KEYWORD(__vectorcall                , KEYALL)
+KEYWORD(__make_integer_seq          , KEYCXX)
 KEYWORD(__forceinline               , KEYMS)
 KEYWORD(__unaligned                 , KEYMS)
 KEYWORD(__super                     , KEYMS)
 
 // OpenCL address space qualifiers
 KEYWORD(__global                    , KEYOPENCL)
 KEYWORD(__local                     , KEYOPENCL)
 KEYWORD(__constant                  , KEYOPENCL)

include/clang/Sema/Sema.h

void FilterAcceptableTemplateNames(LookupResult &R,
                                      bool AllowFunctionTemplates = true);
   bool hasAnyAcceptableTemplateNames(LookupResult &R,
                                      bool AllowFunctionTemplates = true);
 
   void LookupTemplateName(LookupResult &R, Scope *S, CXXScopeSpec &SS,
                           QualType ObjectType, bool EnteringContext,
                           bool &MemberOfUnknownSpecialization);
 
+  void actOnBuiltinTemplateName(TemplateTy &TemplateResult,
+                                BuiltinTemplateNameKind BTNK);
+
   TemplateNameKind isTemplateName(Scope *S,
                                   CXXScopeSpec &SS,
                                   bool hasTemplateKeyword,
                                   UnqualifiedId &Name,
                                   ParsedType ObjectType,
                                   bool EnteringContext,
                                   TemplateTy &Template,
                                   bool &MemberOfUnknownSpecialization);

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(BuiltinTemplateNameKind BTNK) const {
+  auto *BuiltinTemplate =
+      BuiltinTemplateDecl::Create(*this, BTNK, getTranslationUnitDecl());
+  BuiltinTemplate->setImplicit();
+
+  return BuiltinTemplate;
+}
+
+BuiltinTemplateDecl *
+ASTContext::getMakeIntegerSeqDecl() const {
+  if (!MakeIntegerSeqDecl)
+    MakeIntegerSeqDecl = buildBuiltinTemplateDecl(BTNK__make_integer_seq);
+  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
bool ASTContext::UnwrapSimilarPointerTypes(QualType &T1, QualType &T2) {
   
   return false;
 }
 
 DeclarationNameInfo
 ASTContext::getNameForTemplate(TemplateName Name,
                                SourceLocation NameLoc) const {
   switch (Name.getKind()) {
+  case TemplateName::BuiltinTemplate:
+    return DeclarationNameInfo();
   case TemplateName::QualifiedTemplate:
   case TemplateName::Template:
     // DNInfo work in progress: CHECKME: what about DNLoc?
     return DeclarationNameInfo(Name.getAsTemplateDecl()->getDeclName(),
                                NameLoc);
 
   case TemplateName::OverloadedTemplate: {
     OverloadedTemplateStorage *Storage = Name.getAsOverloadedTemplate();
ASTContext::getNameForTemplate(TemplateName Name,
   }
   }
 
   llvm_unreachable("bad template name kind!");
 }
 
 TemplateName ASTContext::getCanonicalTemplateName(TemplateName Name) const {
   switch (Name.getKind()) {
+  case TemplateName::BuiltinTemplate:
+    return Name;
   case TemplateName::QualifiedTemplate:
   case TemplateName::Template: {
     TemplateDecl *Template = Name.getAsTemplateDecl();
     if (TemplateTemplateParmDecl *TTP 
           = dyn_cast<TemplateTemplateParmDecl>(Template))
       Template = getCanonicalTemplateTemplateParmDecl(TTP);
   
     // The canonical template name is the canonical template declaration.

 
 void ASTContext::setObjCConstantStringInterface(ObjCInterfaceDecl *Decl) {
   assert(ObjCConstantStringType.isNull() &&
          "'NSConstantString' type already set!");
 
   ObjCConstantStringType = getObjCInterfaceType(Decl);
 }
 
+/// \brief Retrieve the template name that corresponds to a __make_integer_seq.
+TemplateName
+ASTContext::getBuiltinTemplateName(BuiltinTemplateNameKind BTNK) const {
+  void *Memory = Allocate(sizeof(BuiltinTemplateStorage));
+  auto *BTS = new (Memory) BuiltinTemplateStorage(BTNK);
+  return TemplateName(BTS);
+}
+
 /// \brief Retrieve the template name that corresponds to a non-empty
 /// lookup.
 TemplateName
 ASTContext::getOverloadedTemplateName(UnresolvedSetIterator Begin,
                                       UnresolvedSetIterator End) const {
   unsigned size = End - Begin;
   assert(size > 1 && "set is not overloaded!");
 

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->getBuiltinTemplateNameKind()) {
+  case BTNK__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/ASTImporter.cpp

case TemplateName::SubstTemplateTemplateParmPack: {
     ASTNodeImporter Importer(*this);
     TemplateArgument ArgPack 
       = Importer.ImportTemplateArgument(SubstPack->getArgumentPack());
     if (ArgPack.isNull())
       return TemplateName();
     
     return ToContext.getSubstTemplateTemplateParmPack(Param, ArgPack);
   }
+  case TemplateName::BuiltinTemplate: {
+    return ToContext.getBuiltinTemplateName(
+        From.getAsBuiltinTemplate()->getKind());
+  }
   }
   
   llvm_unreachable("Invalid template name kind");
 }
 
 SourceLocation ASTImporter::Import(SourceLocation FromLoc) {
   if (FromLoc.isInvalid())
     return SourceLocation();

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, BuiltinTemplateNameKind BTNK, DeclContext *DC) {
+  switch (BTNK) {
+  case BTNK__make_integer_seq:
+    return createMakeIntegerSeqParameterList(C, DC);
+  }
+
+  llvm_unreachable("unhandled BuiltinTemplateNameKind!");
+}
+
+void BuiltinTemplateDecl::anchor() {}
+
+BuiltinTemplateDecl::BuiltinTemplateDecl(const ASTContext &C,
+                                         BuiltinTemplateNameKind BTNK,
+                                         DeclContext *DC)
+    : TemplateDecl(BuiltinTemplate, DC, SourceLocation(), DeclarationName(),
+                   createBuiltinTemplateParameterList(C, BTNK, DC)),
+      BTNK(BTNK) {}

lib/AST/ItaniumMangle.cpp

if (isa<TemplateTemplateParmDecl>(TD))
       mangleTemplateParameter(cast<TemplateTemplateParmDecl>(TD)->getIndex());
     else
       mangleName(TD);
     break;
 
   case TemplateName::OverloadedTemplate:
     llvm_unreachable("can't mangle an overloaded template name as a <type>");
 
+  case TemplateName::BuiltinTemplate: {
+    DiagnosticsEngine &Diags = Context.getDiags();
+    unsigned DiagID =
+        Diags.getCustomDiagID(DiagnosticsEngine::Error,
+                              "mangling builtin templates is not supported");
+    Diags.Report(DiagID);
+  }
+
   case TemplateName::DependentTemplate: {
     const DependentTemplateName *Dependent = TN.getAsDependentTemplateName();
     assert(Dependent->isIdentifier());
 
     // <class-enum-type> ::= <name>
     // <name> ::= <nested-name>
     mangleUnresolvedPrefix(Dependent->getQualifier());
     mangleSourceName(Dependent->getIdentifier());
case TemplateName::QualifiedTemplate: {
       assert(TD && "no template for template specialization type");
       if (isa<TemplateTemplateParmDecl>(TD))
         goto unresolvedType;
 
       mangleSourceName(TD->getIdentifier());
       break;
     }
 
+    case TemplateName::BuiltinTemplate:
     case TemplateName::OverloadedTemplate:
     case TemplateName::DependentTemplate:
       llvm_unreachable("invalid base for a template specialization type");
 
     case TemplateName::SubstTemplateTemplateParm: {
       SubstTemplateTemplateParmStorage *subst =
           TN.getAsSubstTemplateTemplateParm();
       mangleExistingSubstitution(subst->getReplacement());

lib/AST/TemplateName.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/TemplateName.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/NestedNameSpecifier.h"
 #include "clang/AST/PrettyPrinter.h"
 #include "clang/AST/TemplateBase.h"
+#include "clang/Basic/Builtins.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/LangOptions.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace clang;
 using namespace llvm;
 
 TemplateArgument 
 SubstTemplateTemplateParmPackStorage::getArgumentPack() const {
if (Storage.is<TemplateDecl *>())
     return Template;
   if (Storage.is<DependentTemplateName *>())
     return DependentTemplate;
   if (Storage.is<QualifiedTemplateName *>())
     return QualifiedTemplate;
 
   UncommonTemplateNameStorage *uncommon
     = Storage.get<UncommonTemplateNameStorage*>();
+  if (uncommon->getAsBuiltinTemplate())
+    return BuiltinTemplate;
   if (uncommon->getAsOverloadedStorage())
     return OverloadedTemplate;
   if (uncommon->getAsSubstTemplateTemplateParm())
     return SubstTemplateTemplateParm;
   return SubstTemplateTemplateParmPack;
 }
 
 TemplateDecl *TemplateName::getAsTemplateDecl() const {
if (isa<TemplateTemplateParmDecl>(Template))
       return true;
     // FIXME: Hack, getDeclContext() can be null if Template is still
     // initializing due to PCH reading, so we check it before using it.
     // Should probably modify TemplateSpecializationType to allow constructing
     // it without the isDependent() checking.
     return Template->getDeclContext() &&
            Template->getDeclContext()->isDependentContext();
   }
+  if (BuiltinTemplateStorage *BTS = getAsBuiltinTemplate()) {
+    switch (BTS->getKind()) {
+    case BTNK__make_integer_seq:
+      return false;
+    }
+  }
 
   assert(!getAsOverloadedTemplate() &&
          "overloaded templates shouldn't survive to here");
 
   return true;
 }
 
 bool TemplateName::isInstantiationDependent() const {
else if (QualifiedTemplateName *QTN = getAsQualifiedTemplateName()) {
     
     if (DTN->isIdentifier())
       OS << DTN->getIdentifier()->getName();
     else
       OS << "operator " << getOperatorSpelling(DTN->getOperator());
   } else if (SubstTemplateTemplateParmStorage *subst
                = getAsSubstTemplateTemplateParm()) {
     subst->getReplacement().print(OS, Policy, SuppressNNS);
-  } else if (SubstTemplateTemplateParmPackStorage *SubstPack
-                                        = getAsSubstTemplateTemplateParmPack())
+  } else if (SubstTemplateTemplateParmPackStorage *SubstPack =
+                 getAsSubstTemplateTemplateParmPack()) {
     OS << *SubstPack->getParameterPack();
-  else {
-    OverloadedTemplateStorage *OTS = getAsOverloadedTemplate();
+  } else if (OverloadedTemplateStorage *OTS = getAsOverloadedTemplate()) {
     (*OTS->begin())->printName(OS);
+  } else if (BuiltinTemplateStorage *BTS = getAsBuiltinTemplate()) {
+    switch (BTS->getKind()) {
+    case BTNK__make_integer_seq:
+      OS << "__make_integer_seq";
+      break;
+    }
   }
 }
 
 const DiagnosticBuilder &clang::operator<<(const DiagnosticBuilder &DB,
                                            TemplateName N) {
   std::string NameStr;
   raw_string_ostream OS(NameStr);
   LangOptions LO;

lib/AST/Type.cpp

: Type(TemplateSpecialization,
          Canon.isNull()? true : Canon->isInstantiationDependentType(),
          false,
          T.containsUnexpandedParameterPack()),
     Template(T), NumArgs(NumArgs), TypeAlias(!AliasedType.isNull()) {
   assert(!T.getAsDependentTemplateName() && 
          "Use DependentTemplateSpecializationType for dependent template-name");
   assert((T.getKind() == TemplateName::Template ||
           T.getKind() == TemplateName::SubstTemplateTemplateParm ||
-          T.getKind() == TemplateName::SubstTemplateTemplateParmPack) &&
+          T.getKind() == TemplateName::SubstTemplateTemplateParmPack ||
+          T.getKind() == TemplateName::BuiltinTemplate) &&
          "Unexpected template name for TemplateSpecializationType");
 
   TemplateArgument *TemplateArgs
     = reinterpret_cast<TemplateArgument *>(this + 1);
   for (unsigned Arg = 0; Arg < NumArgs; ++Arg) {
     // Update instantiation-dependent and variably-modified bits.
     // If the canonical type exists and is non-dependent, the template
     // specialization type can be non-dependent even if one of the type

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/Parse/ParseDecl.cpp

case tok::annot_typename: {
         break;
 
       DS.SetRangeEnd(Tok.getAnnotationEndLoc());
       ConsumeToken(); // The typename
 
       continue;
     }
 
+    case tok::kw___make_integer_seq: {
+      assert(getLangOpts().CPlusPlus &&
+             "Can only annotate template-ids in C++");
+      TemplateTy Template;
+      Actions.actOnBuiltinTemplateName(Template, BTNK__make_integer_seq);
+
+      if (!NextToken().is(tok::less)) {
+        DS.SetTypeSpecError();
+        break;
+      }
+
+      // Consume the template-name.
+      SourceLocation TemplateNameLoc = ConsumeToken();
+
+      assert(Template && Tok.is(tok::less) &&
+             "Parser isn't at the beginning of a template-id");
+
+      // Parse the enclosed template argument list.
+      SourceLocation LAngleLoc, RAngleLoc, TemplateKWLoc;
+      TemplateArgList TemplateArgs;
+      CXXScopeSpec SS;
+      bool IsInvalid =
+          ParseTemplateIdAfterTemplateName(Template, TemplateNameLoc, SS, false,
+                                           LAngleLoc, TemplateArgs, RAngleLoc);
+
+      if (IsInvalid) {
+        // If we failed to parse the template ID but skipped ahead to a >,
+        // we're not going to be able to form a token annotation.
+        // Eat the '>' if present.
+        TryConsumeToken(tok::greater);
+        DS.SetTypeSpecError();
+        break;
+      }
+
+      ASTTemplateArgsPtr TemplateArgsPtr(TemplateArgs);
+      TypeResult Type = Actions.ActOnTemplateIdType(SS, TemplateKWLoc, Template,
+                                                    TemplateNameLoc, LAngleLoc,
+                                                    TemplateArgsPtr, RAngleLoc);
+      if (Type.isInvalid()) {
+        // If we failed to parse the template ID but skipped ahead to a >, we're
+        // not going to be able to form a token annotation.  Eat the '>' if
+        // present.
+        TryConsumeToken(tok::greater);
+        DS.SetTypeSpecError();
+        break;
+      }
+
+      Tok.setKind(tok::annot_typename);
+      setTypeAnnotation(Tok, Type.get());
+      Tok.setLocation(TemplateNameLoc);
+      Tok.setAnnotationEndLoc(RAngleLoc);
+      // In case the tokens were cached, have Preprocessor replace them with the
+      // annotation token.
+      PP.AnnotateCachedTokens(Tok);
+      continue;
+    }
+
     case tok::kw___is_signed:
       // GNU libstdc++ 4.4 uses __is_signed as an identifier, but Clang
       // typically treats it as a trait. If we see __is_signed as it appears
       // in libstdc++, e.g.,
       //
       //   static const bool __is_signed;
       //
       // then treat __is_signed as an identifier rather than as a keyword.

lib/Sema/SemaDecl.cpp

static ParsedType buildNestedType(Sema &S, CXXScopeSpec &SS,
 
   T = S.getElaboratedType(ETK_None, SS, T);
   ElaboratedTypeLoc ElabTL = Builder.push<ElaboratedTypeLoc>(T);
   ElabTL.setElaboratedKeywordLoc(SourceLocation());
   ElabTL.setQualifierLoc(SS.getWithLocInContext(Context));
   return S.CreateParsedType(T, Builder.getTypeSourceInfo(Context, T));
 }
 
+void Sema::actOnBuiltinTemplateName(TemplateTy &TemplateResult,
+                                    BuiltinTemplateNameKind BTNK) {
+  TemplateResult = TemplateTy::make(Context.getBuiltinTemplateName(BTNK));
+}
+
 Sema::NameClassification
 Sema::ClassifyName(Scope *S, CXXScopeSpec &SS, IdentifierInfo *&Name,
                    SourceLocation NameLoc, const Token &NextToken,
                    bool IsAddressOfOperand,
                    std::unique_ptr<CorrectionCandidateCallback> CCC) {
   DeclarationNameInfo NameInfo(Name, NameLoc);
   ObjCMethodDecl *CurMethod = getCurMethodDecl();
 

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 (DTN && DTN->isIdentifier())
     // assume the template is a type template. Either our assumption is
     // 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();
+  BuiltinTemplateStorage *BTS = Name.getAsBuiltinTemplate();
+  TemplateDecl *Template;
+  if (BTS) {
+    switch (BTS->getKind()) {
+    case BTNK__make_integer_seq:
+      Template = Context.getMakeIntegerSeqDecl();
+      break;
+    }
+  } else {
+    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 (BTS) {
+    switch (BTS->getKind()) {
+    case BTNK__make_integer_seq:
+      // Instantiations involving __make_integer_seq<S, T, N> are treated like
+      // S<T, 0, ..., N-1>.
+      TemplateArgument NumArgsArg = Converted[2];
+      llvm::APSInt NumArgs = NumArgsArg.getAsIntegral();
+
+      // Diagnose attempts to create integer sequences with a negative length.
+      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/Sema/TreeTransform.h

if (SubstTemplateTemplateParmPackStorage *SubstPack
     if (!getDerived().AlwaysRebuild() &&
         TransParam == SubstPack->getParameterPack())
       return Name;
 
     return getDerived().RebuildTemplateName(TransParam,
                                             SubstPack->getArgumentPack());
   }
 
+  if (Name.getKind() == TemplateName::BuiltinTemplate)
+    return Name;
+
   // These should be getting filtered out before they reach the AST.
   llvm_unreachable("overloaded function decl survived to here");
 }
 
 template<typename Derived>
 void TreeTransform<Derived>::InventTemplateArgumentLoc(
                                          const TemplateArgument &Arg,
                                          TemplateArgumentLoc &Output) {

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/ASTReader.cpp

if (!Param)
       return TemplateName();
     
     TemplateArgument ArgPack = ReadTemplateArgument(F, Record, Idx);
     if (ArgPack.getKind() != TemplateArgument::Pack)
       return TemplateName();
     
     return Context.getSubstTemplateTemplateParmPack(Param, ArgPack);
   }
+  case TemplateName::BuiltinTemplate: {
+    BuiltinTemplateNameKind BTNK = (BuiltinTemplateNameKind)Record[Idx++];
+    return Context.getBuiltinTemplateName(BTNK);
+  }
   }
 
   llvm_unreachable("Unhandled template name kind!");
 }
 
 TemplateArgument ASTReader::ReadTemplateArgument(ModuleFile &F,
                                                  const RecordData &Record,
                                                  unsigned &Idx,

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

lib/Serialization/ASTWriter.cpp

void ASTWriter::AddTemplateName(TemplateName Name, RecordDataImpl &Record) {
       
   case TemplateName::SubstTemplateTemplateParmPack: {
     SubstTemplateTemplateParmPackStorage *SubstPack
       = Name.getAsSubstTemplateTemplateParmPack();
     AddDeclRef(SubstPack->getParameterPack(), Record);
     AddTemplateArgument(SubstPack->getArgumentPack(), Record);
     break;
   }
+  case TemplateName::BuiltinTemplate: {
+    BuiltinTemplateStorage *BTS = Name.getAsBuiltinTemplate();
+    BuiltinTemplateNameKind BTNK = BTS->getKind();
+    Record.push_back(BTNK);
+    break;
+  }
   }
 }
 
 void ASTWriter::AddTemplateArgument(const TemplateArgument &Arg,
                                     RecordDataImpl &Record) {
   Record.push_back(Arg.getKind());
   switch (Arg.getKind()) {
   case TemplateArgument::Null:

tools/libclang/CIndex.cpp

case TemplateName::SubstTemplateTemplateParm:
     return Visit(MakeCursorTemplateRef(
                          Name.getAsSubstTemplateTemplateParm()->getParameter(),
                                        Loc, TU));
       
   case TemplateName::SubstTemplateTemplateParmPack:
     return Visit(MakeCursorTemplateRef(
                   Name.getAsSubstTemplateTemplateParmPack()->getParameterPack(),
                                        Loc, TU));
+
+  case TemplateName::BuiltinTemplate:
+    return false;
   }
 
   llvm_unreachable("Invalid TemplateName::Kind!");
 }
 
 bool CursorVisitor::VisitTemplateArgumentLoc(const TemplateArgumentLoc &TAL) {
   switch (TAL.getArgument().getKind()) {
   case TemplateArgument::Null:
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;