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
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 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
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 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.