Page MenuHomePhabricator

Template Instantiation Observer + a few other templight-related changes
ClosedPublic

Authored by sabel83 on Oct 13 2014, 10:45 PM.

Details

Summary

This patch adds a base-class called TemplateInstantiationObserver which gets notified whenever a template instantiation is entered or exited during semantic analysis. This is a base class used to implement the template profiling and debugging tool called Templight (https://github.com/mikael-s-persson/templight).

The patch also makes a few more changes:

  • ActiveTemplateInstantiation class is moved out of the Sema class (so it can be used with inclusion of Sema.h).
  • CreateFrontendAction function in front-end utilities is given external linkage (not longer a hidden static function).
  • TemplateInstObserverChain data member added to Sema class to hold the list of template-inst observers.
  • Notifications to the template-inst observer are added at the key places where templates are instantiated.

I believe this patch should be fairly uncontroversial as the changes are very limited. I tried to keep them minimal, it does not add any end-user feature or bug-fix, and the impact to the main-line code is negligible. AFAIK, all LLVM / Clang guidelines have been respected.

The patch was made against r219658.

Diff Detail

Repository
rL LLVM

Event Timeline

mikael-s-persson retitled this revision from to Template Instantiation Observer + a few other templight-related changes.
mikael-s-persson updated this object.
mikael-s-persson edited the test plan for this revision. (Show Details)
mikael-s-persson added a subscriber: Unknown Object (MLST).

We are working on an interactive shell supporting template metaprogramming, which includes a template metaprogram debugger that needs the functionality this patch provides. Currently our utility is using another implementation of this functionality but we are actively working on migrating our tool to use this patch and therefore its acceptance would make the development and deployment of our utility much easier.

Our application can be found here: https://github.com/sabel83/metashell
The (yet unmerged) branch which migrates to a version of Clang using this patch can be found here: https://github.com/r0mai/metashell

There's a few minor cosmetic issues that apply across multiple files:

  • Some if-statements have extra spaces inside the parentheses. "if (foo)" not "if ( foo )".
  • Some files are inconsistent about * and & placement in types. We usually place them next to the variable names.
  • include/clang/Sema/ActiveTemplateInst.h has extra blank lines.

You may find it simplest to use clang-format-diff.py.

I think we'll want a way to test out this interface; it should probably come with a command-line tool that has a very simple template observer that prints out the callbacks as they're called, and a test which runs this tool to exercise it. This might also be a FrontendAction in clang, similar to -ast-dump, instead of a separate tool. (This is not a trivial amount of work, you may want to wait for another clang developer to chime in before spending time on it.)

Overall I'm happy with the design!

include/clang/Sema/TemplateInstObserver.h
25–26 ↗(On Diff #14850)

Alphabetize.

28 ↗(On Diff #14850)

What about a callback when clang transitions from parsing the TU to actOnEndOfTranslationUnit? Template instantiation is different before and after we reach the end-of-TU.

lib/Sema/SemaType.cpp
5202 ↗(On Diff #14850)

Is there a guarantee that this is a template? Offhand it looks like this could fire on any struct, couldn't it?

Thanks for the feedback Nick!

I fixed all the minor cosmetic issues you pointed out, and I also fixed a few "more than 80 char" lines in the original diff.

I changed the name "Observer" to "Callbacks" as requested in the mailing list discussion:
http://clang-developers.42468.n3.nabble.com/Templight-Templight-quot-v2-quot-with-gdb-style-debugger-td4038413.html

Here the new diff (how do I replace the original diff with this one in this llvm-reviews system? I'm new to this system).

To your comments:

I think we'll want a way to test out this interface; it should probably come with a command-line tool that has a very simple template observer that prints out the callbacks as they're called, and a test which runs this tool to exercise it. This might also be a FrontendAction in clang, similar to -ast-dump, instead of a separate tool. (This is not a trivial amount of work, you may want to wait for another clang developer to chime in before spending time on it.)

That is essentially what I have done for the templight tool (https://github.com/mikael-s-persson/templight). I created a new FrontendAction that creates the templight tracer / debugger as a TemplateInstCallbacks. The templight tracer is essentially what you describe, it dumps a trace of all the callbacks (plus a bit of optional filtering and gathering / pretty-formatting of the information). If you want me to distil it down to a more "raw" tracer that only dumps everything to stdout, then that can easily be done.

But there is one hick-up. If the idea is to use this as a kind of unit-test for the tool, that is, to verify that the trace of callbacks are "correct" (as in, later changes to clang should preserve the same trace), then I think that is a great idea in principle. However, I see two problems with that.

First, it's hard to be sure that the current traces are "correct", as in, maybe this patch has some loop-holes that miss some instantiations, or maybe clang is currently incorrect in some ways that might potentially be fixed in the future (at least, I have seen several "FIXME" notes all over the template instantiation code of the Sema and Parser classes).

Second, according to my tests so far, the traces produced by clang are non-deterministic. Different runs on the same source code will produce different trace files. They only differ in inconsequential ways (different ordering of nested instantiations and memoizations). But the point is that a simple comparison of the trace file with some reference trace file would most certainly always fail, unless the test is really trivial.

Therefore, the notion of what makes a trace "correct" for a given source file is not well-defined, and might never be. But if such a notion could be defined (for example, from the C++ standard), this could end up as a great way to evaluate the correctness of Clang (e.g., "does clang instantiate templates in a standard-compliant way?").

But this is far beyond the scope of this patch.

Alphabetize.

Fixed in new patch.

What about a callback when clang transitions from parsing the TU to actOnEndOfTranslationUnit? Template instantiation is different before and after we reach the end-of-TU.

Thanks for pointing that out. I'm not sure what impact this really has. The initialize / finalize pair of callbacks bracket the entire TU parsing, as far as I know. Therefore, all instantiations are captured by the trace, again, AFAIK. After this comment, I know that there are some late implicit instantiations being instantiated when EOF is reached, basically, right? AFAIK, these are still captured by the callbacks.

I don't know if there is any meaning to a callback at this point. If I were debugging Clang, I might see some value in being able to distinguish the instantiations happening before and after this point. But from the perspective of profiling the template instantiations, I don't really need to know this. In any case, I think that this can be the subject of a future patch if a good concrete use-case / motivation is brought forward. And this also raises the question (maybe more appropriate for cfe-dev mailing list) of whether Clang developers would be interested in using this TemplateInstCallbacks as a means to evaluate / debug the clang compiler itself, which might motivate the addition of more callbacks in it.

Is there a guarantee that this is a template? Offhand it looks like this could fire on any struct, couldn't it?

You are correct in that this callback (for memoizations) picks up a lot of things that are not templates. I am very well aware of this issue and it has been pointed out before, but there is really not a lot I can do to change this. Firstly, memoizations are really important (which I am just beginning to realize after making plans for a call-graph like visualization of the instantiations). Secondly, much of the clang template instantiation code is structured as a "check if instantiated already, if not, instantiate it", which means that there are many many places in clang where some kind of "check if instantiated already" logic exists and it varies greatly from context to context. This makes it very hard to insert the memoization callbacks in proper places. So, as far as I know, this particular placements is not too bad because it picks up most, if not all, checks, and generates noise that can be dealt with (I don't do it currently in templight, but I plan to add that soon, and this is logic that could go into the TemplateInstCallbacks if needed), i.e., it's easier to filter out spurious callbacks than to miss some important ones.

But at the end of the day, the only way that this can be fixed is for someone from the Clang development team who is very much familiar with the complete template instantiation code to provide his/her hands-on assistance for this. I am simply not in a position to be able to figure out how to appropriately trace the memoizations reliably and without too much noise.

Thanks for the feedback Nick!

I fixed all the minor cosmetic issues you pointed out, and I also fixed a few "more than 80 char" lines in the original diff.

I changed the name "Observer" to "Callbacks" as requested in the mailing list discussion:
http://clang-developers.42468.n3.nabble.com/Templight-Templight-quot-v2-quot-with-gdb-style-debugger-td4038413.html

Here the new diff (how do I replace the original diff with this one in this llvm-reviews system? I'm new to this system).

Honestly, I don't know, I tend not to use phabricator myself.

+ / Added for Template instantiation observation
+
/ Memoization means we are _not_ instantiating a template because
+ / it is already instantiated (but we entered a context where we
+
/ would have had to if it was not already instantiated).
+ Memoization
+
+ } Kind;

Extra newline before "} Kind;".

+ llvm_unreachable("Invalid InstantiationKind!");
+}
+
+
+}

At least one of those newlines is extra.

To your comments:

I think we'll want a way to test out this interface; it should probably come with a command-line tool that has a very simple template observer that prints out the callbacks as they're called, and a test which runs this tool to exercise it. This might also be a FrontendAction in clang, similar to -ast-dump, instead of a separate tool. (This is not a trivial amount of work, you may want to wait for another clang developer to chime in before spending time on it.)

That is essentially what I have done for the templight tool (https://github.com/mikael-s-persson/templight). I created a new FrontendAction that creates the templight tracer / debugger as a TemplateInstCallbacks. The templight tracer is essentially what you describe, it dumps a trace of all the callbacks (plus a bit of optional filtering and gathering / pretty-formatting of the information). If you want me to distil it down to a more "raw" tracer that only dumps everything to stdout, then that can easily be done.

Yes, a raw tracer is what I had in mind. We could then write the tests with FileCheck. I realize this isn't great as a testing apparatus because you don't want tests to be too closely coupled to implementation details, but we'll need something that exercizes the new code in this patch.

But there is one hick-up. If the idea is to use this as a kind of unit-test for the tool, that is, to verify that the trace of callbacks are "correct" (as in, later changes to clang should preserve the same trace), then I think that is a great idea in principle. However, I see two problems with that.

First, it's hard to be sure that the current traces are "correct", as in, maybe this patch has some loop-holes that miss some instantiations, or maybe clang is currently incorrect in some ways that might potentially be fixed in the future (at least, I have seen several "FIXME" notes all over the template instantiation code of the Sema and Parser classes).

Second, according to my tests so far, the traces produced by clang are non-deterministic.

Non-determinism is a serious problem, I'm surprised we get .o file output as deterministically as we do. Having a mode in clang that exposes the non-determinism to us developers is an important first step in getting the causes found and fixed.

Different runs on the same source code will produce different trace files. They only differ in inconsequential ways (different ordering of nested instantiations and memoizations). But the point is that a simple comparison of the trace file with some reference trace file would most certainly always fail, unless the test is really trivial.

Therefore, the notion of what makes a trace "correct" for a given source file is not well-defined, and might never be. But if such a notion could be defined (for example, from the C++ standard), this could end up as a great way to evaluate the correctness of Clang (e.g., "does clang instantiate templates in a standard-compliant way?").

But this is far beyond the scope of this patch.

Alphabetize.

Fixed in new patch.

What about a callback when clang transitions from parsing the TU to actOnEndOfTranslationUnit? Template instantiation is different before and after we reach the end-of-TU.

Thanks for pointing that out. I'm not sure what impact this really has. The initialize / finalize pair of callbacks bracket the entire TU parsing, as far as I know. Therefore, all instantiations are captured by the trace, again, AFAIK. After this comment, I know that there are some late implicit instantiations being instantiated when EOF is reached, basically, right? AFAIK, these are still captured by the callbacks.

It's more interesting when combined with other features such as PCH or modules. Instantiations which are done before the end-of-TU can be written into a C++ module file and reused by all users of the module while those done after the end-of-TU must be done by every user of the module. For performance we'd like to have more of the former and fewer of the latter. For debugging, there are things we could do to find point-of-instantiation bugs in source code if we defer more instantiation until the end-of-TU, but that isn't in tree*, mainly because clang doesn't do a great job of tracking the PoI.

I don't know if there is any meaning to a callback at this point. If I were debugging Clang, I might see some value in being able to distinguish the instantiations happening before and after this point. But from the perspective of profiling the template instantiations, I don't really need to know this. In any case, I think that this can be the subject of a future patch if a good concrete use-case / motivation is brought forward.

Sounds good.

And this also raises the question (maybe more appropriate for cfe-dev mailing list) of whether Clang developers would be interested in using this TemplateInstCallbacks as a means to evaluate / debug the clang compiler itself, which might motivate the addition of more callbacks in it.

I think the answer has to be yes. Debugging non-determinism inside clang itself should be a good enough motivator.

Is there a guarantee that this is a template? Offhand it looks like this could fire on any struct, couldn't it?

You are correct in that this callback (for memoizations) picks up a lot of things that are not templates. I am very well aware of this issue and it has been pointed out before, but there is really not a lot I can do to change this. Firstly, memoizations are really important (which I am just beginning to realize after making plans for a call-graph like visualization of the instantiations). Secondly, much of the clang template instantiation code is structured as a "check if instantiated already, if not, instantiate it", which means that there are many many places in clang where some kind of "check if instantiated already" logic exists and it varies greatly from context to context. This makes it very hard to insert the memoization callbacks in proper places. So, as far as I know, this particular placements is not too bad because it picks up most, if not all, checks, and generates noise that can be dealt with (I don't do it currently in templight, but I plan to add that soon, and this is logic that could go into the TemplateInstCallbacks if needed), i.e., it's easier to filter out spurious callbacks than to miss some important ones.

But at the end of the day, the only way that this can be fixed is for someone from the Clang development team who is very much familiar with the complete template instantiation code to provide his/her hands-on assistance for this. I am simply not in a position to be able to figure out how to appropriately trace the memoizations reliably and without too much noise.

I agree, I'll let another clang developer handle that one.

Made the changes requested by some reviewers.

klimek added a subscriber: klimek.Nov 1 2015, 9:57 AM

Is this still the most current patch out there?

Hi Manuel,

The patch is maintained in the Templight git repository (https://github.com/mikael-s-persson/templight/blob/master/templight_clang_patch.diff). I've written some tests for it (based on our discussion at CppCon), they are under review at the moment (see https://github.com/mikael-s-persson/templight/pull/25 for the details). Note that these are just some initial tests, not covering the entire patch.

zporky added a subscriber: zporky.Nov 2 2015, 2:09 AM
r0mai added a subscriber: r0mai.Nov 2 2015, 2:26 AM
klimek added a comment.Nov 2 2015, 8:56 AM

Ok, just let me know when you have an updated patch out for review for submission, so I can make sure we'll get the reviews done in a timely fashion. I really want to see this go in :)

sabel83 commandeered this revision.Oct 17 2017, 12:50 PM
sabel83 added a reviewer: mikael-s-persson.
klimek edited edge metadata.Oct 17 2017, 3:18 PM

Whee, thanks for driving this, much appreciated :D

include/clang/FrontendTool/Utils.h
25 ↗(On Diff #119377)

Please add a comment now that this is exported.

include/clang/Sema/TemplateInstCallbacks.h
32 ↗(On Diff #119377)

Note sure how others think about this, but I'd have expected the design to have:
a) a pure interface
b) an implementation TemplateInstantiationCallbacksCollection or somesuch that has a vector of TICs and forwards calls on them

sabel83 updated this revision to Diff 119774.Oct 21 2017, 11:38 PM

I've updated the patch based on your comments.

Ok, I think this is starting to look really good. Now we should try to grab Richard's attention to make sure it's fine to submit with the current set of FIXMEs.

lib/Frontend/FrontendActions.cpp
386 ↗(On Diff #119774)

Usually we don't use ascii art. Perhaps instead of marking a scope with arrows, pull out a small function that explains what we want to do instead?

sabel83 updated this revision to Diff 120358.Oct 25 2017, 10:00 PM
sabel83 marked 2 inline comments as done.

Just FYI, I talked with Richard and he'll not get to it before next week. Hope that's fine.

klimek added a comment.Nov 7 2017, 1:05 AM

Weekly ping. This week is C++ committee, so it's again going to be hard to get Richards attention :( It's an unfortunate time of year to land major API-touching changes.

rsmith edited edge metadata.Nov 8 2017, 7:02 PM

I'm not entirely sure what's happening with this and https://reviews.llvm.org/D38818, but the direction looks good to me, and I left a couple of comments on the other review thread.

sabel83 updated this revision to Diff 122325.Nov 9 2017, 1:37 PM
sabel83 marked an inline comment as done.

I'm not entirely sure what's happening with this and https://reviews.llvm.org/D38818, but the direction looks good to me, and I left a couple of comments on the other review thread.

This was the original pull request. I created D38818 when I didn't know how to update this one (it was originally created by Mikael, not me). I have updated D38818 and this one as well based on the comments, so both pull requests have the same code now (and I'll cancel the one that does not get merged).

rsmith accepted this revision.Nov 14 2017, 4:50 PM

LGTM

This revision is now accepted and ready to land.Nov 14 2017, 4:50 PM
xazax.hun added inline comments.Nov 15 2017, 1:47 AM
include/clang/Sema/TemplateInstCallback.h
44 ↗(On Diff #122325)

Nit: this file should be clang formatted, it does not follow the LLVM style. (This also applies to some other changes.) Also, I would prefer to remove the trailing underscore from parameter names.

sabel83 updated this revision to Diff 123465.Nov 18 2017, 10:57 AM
xazax.hun accepted this revision.Nov 28 2017, 4:24 AM

I found some nit, otherwise LG!

I think you should includ the context in the patches, that makes them reviewing much easier. See: https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

include/clang/Sema/TemplateInstCallback.h
47 ↗(On Diff #123465)

We usually omit the braces for one line long single statements guarded by ifs.

lib/Frontend/FrontendActions.cpp
326 ↗(On Diff #123465)

The methods should start with a lowercase letter even if they are static.

sabel83 updated this revision to Diff 125272.Dec 2 2017, 11:37 AM
sabel83 marked an inline comment as done.
sabel83 marked 2 inline comments as done.Dec 2 2017, 11:39 AM

I have extended the context as suggested.

xgsa added a subscriber: xgsa.Dec 14 2017, 7:43 AM

I have no commit access, please commit the patch for me.

sabel83 updated this revision to Diff 132778.Feb 4 2018, 11:59 AM

Overall looks good. Was this tested on large software? I would also be grateful if you could run the regression tests with templight always being enabled to see if they uncover any assertions/crashes.

include/clang/Driver/CC1Options.td
537 ↗(On Diff #132778)

Do we want to keep the templight name? I am ok with it, but I wonder if something like dump template instantiation information, or dump template profile information would be more descriptive to the newcomers.

include/clang/Sema/Sema.h
7117 ↗(On Diff #132778)

Terminate the first sentence with period.

include/clang/Sema/TemplateInstCallback.h
26 ↗(On Diff #132778)

Prefer = default;

lib/Frontend/FrontendActions.cpp
29 ↗(On Diff #132778)

Is this header used? If not (after solving my other comments below), please remove it.

319 ↗(On Diff #132778)

std::cout is rarely used in LLVM. Did you consider llvm::outs?
Also, do we want to output to the standard output or standard error? Is there other dump functionality that is being printed to the standard output?

357 ↗(On Diff #132778)

Some methods still starts with uppercase letters.

377 ↗(On Diff #132778)

Use auto * to avoid repeating the type name.

lib/FrontendTool/ExecuteCompilerInvocation.cpp
261 ↗(On Diff #132778)

Add namespace closing comment.

lib/Sema/Sema.cpp
40 ↗(On Diff #132778)

Do you need to add this include?

lib/Sema/SemaTemplateInstantiate.cpp
204 ↗(On Diff #132778)

This function should never be called with Memoization? Maybe this worth a comment?

This pull requests consists of two parts:

a) a hook, which is called during template instantiation events

b) a callback, which dumps the details of the events out to standard output

Tools like Templight (https://github.com/mikael-s-persson/templight) rely on the hook. The callback is available to make it testable (see the tests, which are part of the pull request) and can be used as a simple way of querying some information about template instantiations if needed.

  1. Testing on larger software: Templight is based on the hook and Metashell (http://metashell.org) is using Templight intensively. We have a branch of Metashell using the YAML output for template debugging (https://github.com/sabel83/metashell/tree/use_templight_dump).
  1. What do you mean by regression tests? We have run the clang-test target successfully on the patched code (which has the hook). Note that the hook this pull request provides is implemented as a ProgramAction. It is not intended to be used together with other program actions, I don't see how we could turn it on for other tests (if that is what you referred to).
sabel83 marked an inline comment as done.Feb 6 2018, 8:22 AM
sabel83 added inline comments.
include/clang/Driver/CC1Options.td
537 ↗(On Diff #132778)
lib/Frontend/FrontendActions.cpp
319 ↗(On Diff #132778)

We dump to standard output because the original purpose of this callback is to make the hook itself testable with FileCheck.

  1. What do you mean by regression tests? We have run the clang-test target successfully on the patched code (which has the hook). Note that the hook this pull request provides is implemented as a ProgramAction. It is not intended to be used together with other program actions, I don't see how we could turn it on for other tests (if that is what you referred to).

I would bet the sema tests are full of tricky edge cases. So running templight on those tests would be a helpful exercise. I am only interested in assertion fails, so we do not need to check the output. One option to do so would be to add the -templight-dump option to the %clang_cc1 variable when running the tests. Note that the tests are likely to fail because the output will change, but if there are no crashes, it is fine.

sabel83 updated this revision to Diff 133400.Feb 8 2018, 4:14 AM
sabel83 marked an inline comment as done.
sabel83 marked 8 inline comments as done.Feb 8 2018, 4:20 AM
Szelethus added inline comments.Feb 8 2018, 6:45 AM
lib/Sema/Sema.cpp
40 ↗(On Diff #132778)

Yes, in Sema.h the class TemplateInstantiationCallback is only forward declared. That headers contains the definition.

xazax.hun added inline comments.Feb 9 2018, 2:15 AM
lib/FrontendTool/ExecuteCompilerInvocation.cpp
261 ↗(On Diff #133400)

Nit: this should be // namespace clang

xazax.hun added inline comments.Feb 9 2018, 2:31 AM
lib/Sema/SemaTemplateInstantiate.cpp
646 ↗(On Diff #133400)

Use either LLVM_FALLTHROUGH; here or break to avoid compiler warnings.

Szelethus added a comment.EditedFeb 9 2018, 5:55 AM
  1. What do you mean by regression tests? We have run the clang-test target successfully on the patched code (which has the hook). Note that the hook this pull request provides is implemented as a ProgramAction. It is not intended to be used together with other program actions, I don't see how we could turn it on for other tests (if that is what you referred to).

I would bet the sema tests are full of tricky edge cases. So running templight on those tests would be a helpful exercise. I am only interested in assertion fails, so we do not need to check the output. One option to do so would be to add the -templight-dump option to the %clang_cc1 variable when running the tests. Note that the tests are likely to fail because the output will change, but if there are no crashes, it is fine.

I did just that, and nothing crashed during the regression tests (in fact, every single one passed)!

sabel83 updated this revision to Diff 133614.Feb 9 2018, 6:45 AM
sabel83 marked 2 inline comments as done.
xazax.hun accepted this revision.Feb 9 2018, 6:51 AM

Thanks, this looks good to me! I will try this out soon and commit after that.

Closed by commit rL324808: [Templight] Template Instantiation Observer (authored by xazax, committed by ). · Explain WhyFeb 10 2018, 6:06 AM
This revision was automatically updated to reflect the committed changes.