This is an archive of the discontinued LLVM Phabricator instance.

[Sema] Implement __make_integer_seq
ClosedPublic

Authored by majnemer on Oct 15 2015, 2:04 PM.

Details

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.

Diff Detail

Event Timeline

majnemer updated this revision to Diff 37517.Oct 15 2015, 2:04 PM
majnemer retitled this revision from to [Sema] Implement __make_integer_seq.
majnemer updated this object.
majnemer added a reviewer: rsmith.
majnemer added a subscriber: cfe-commits.
majnemer updated this revision to Diff 37518.Oct 15 2015, 2:06 PM
  • Add an llvm_unreachable to ASTDeclReader::VisitBuiltinTemplateDecl
rsmith added inline comments.Oct 15 2015, 5:47 PM
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 added a subscriber: EricWF.Oct 15 2015, 7:04 PM

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 updated this revision to Diff 37558.Oct 15 2015, 10:57 PM
majnemer marked 2 inline comments as done.
  • Address Richard's review comments.
majnemer updated this revision to Diff 37612.Oct 16 2015, 10:54 AM
  • Add an llvm_unreachable to ASTDeclReader::VisitBuiltinTemplateDecl
  • Address Richard's review comments.
  • Add logic to check [intseq.intseq]p1.
majnemer updated this revision to Diff 37673.Oct 17 2015, 2:42 AM
  • Remove TemplateName::BuiltinTemplate
majnemer updated this revision to Diff 37674.Oct 17 2015, 2:48 AM
  • Rename BuiltinTemplateNameKind to BuiltinTemplateKind
majnemer updated this revision to Diff 37675.Oct 17 2015, 3:02 AM
  • Make __make_integer_seq parameters as implicit
  • Remove Sema::Ident___make_integer_seq
  • Remove extraneous whitespace change
majnemer updated this revision to Diff 37676.Oct 17 2015, 3:03 AM
  • Add test for __make_integer_seq

@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?

rsmith added inline comments.Nov 2 2015, 11:21 AM
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 updated this revision to Diff 39145.Nov 3 2015, 6:43 PM
  • 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 accepted this revision.Nov 3 2015, 7:11 PM
rsmith edited edge metadata.

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

This revision is now accepted and ready to land.Nov 3 2015, 7:11 PM
majnemer updated this revision to Diff 39153.Nov 3 2015, 7:39 PM
majnemer edited edge metadata.
  • Address Richard's latest comments
This revision was automatically updated to reflect the committed changes.