[XRay] Implement `llvm-xray extract`, start of the llvm-xray tool

[dberris]

Summary

Usage:

llvm-xray extract <object file> [-o <filename or '-'>]

The tool gets the XRay instrumentation map from an object file and turns
it into YAML. We first support ELF64 sleds on x86_64 binaries, with
provision for supporting other supported platforms and formats later.

This is the first of a many-part change to fully implement the
llvm-xray tool.

We also define a subcommand registration and dispatch mechanism to be
used by other further subcommand implementations for llvm-xray.

Depends on D21982 for the in-memory logging in compiler-rt.
Depends on D21983 for the changes to flags in clang.

[dberris]

tools/xray/xray-fc-account.cc

168–171

If these are just standard layout structs (which they seem to be), you could allocate an array of them with 'new XRaySledEntry[N]' as usual. Though I think you could get aligned memory by new'ing a std::aligned_storage object... maybe?

Unfortunately, neither of those are guaranteed to be honoured by the standard allocator (or even the default implementation of 'new') in terms of returning an aligned memory location. :(

What's happening here really is that, since the data is a global, defined by the compiler (when we emit the XRay sleds) we have an opportunity to align the data then. I suspect that has to be fixed first for this to work predictably (i.e. make each entry in the sled be always aligned to 32-byte boundaries). Let me send a change to make that happen, so that this would "just work".

But this'll still only work to run the tool on the same architecture, layout, etc, as the original - is that an intentional limitation? Or should we be making a more fixed/deliberate choice about the file format and having writers format it appropriately, and readers deserialize it appropriately?

This is currently relying on ELF sections for the data. I suspect that's fine for now, but later on a more flexible representation of the sleds would be required (for example, if the instrumentation map was encoded as json or some other format that's easier to consume with other tools).

168–171

new'ing a std::aligned_storage object doesn't seem to work. :( C++17 fixes this by being able to provide an alignment target to new, but we can't use that yet (also, alignment-aware allocators aren't a thing yet AFAICT either).

What will work is asking for 2 x sizeof(T) then manually aligning the address and then inplace new'ing. That might be a useful little utility, but I don't think we need to do that here (yet).

Note that this is loaded from the ELF file section using the reader. I don't know yet whether the alignment enforced by the compiler/linker will translate to aligned memory pointers -- though if they're being mmapped then they _should_ be.

For now we're assuming that we're reading the ELF section and that there's an analog to this in other formats (COFF, MachO, etc.) that LLVM supports.

Does this help?

266

Yeah, this turns out to be much simpler if the body of the loop was empty. Thanks. :)

[dblaikie]

I've added something which should explain a little what this tool already does at the moment. For the moment I'll hold off on adding more tests (I haven't figured out where the tests for the tools or parts of the tools go yet).

Tests generally go in with the functionality in the same commit - and tests for the <foo> tool live in the test/tools/<foo> directory. If some of this functionality ends up sufficiently factored out into utility libraries, unit tests may be written - though unit tests are pretty rare in LLVM (just culturally - I'm actually more of a fan of them) outside of the general data structures in ADT and some of Support. Mostly it's just end-to-end testing of specific tools, optimization passes, etc.

tools/xray/xray-fc-account.cc

168–171

Helps a bit - but generally LLVM tools are platform agnostic. It sounds like this currently is not - that the tool would only work on the platform that generated the file (& that when we port xray to other platforms, again, the tool would only work on the desired platform)

Seems pretty likely someone might take a report from some buildbot that they don't have local hardware for, then want to analyze that on their x86 developer machine. So I think it's probably a good idea to ensure the tools are not platform specific like this. But perhaps I'm overengineering this?

237–267

I'm not sure whether a generic CSV-style output library would be that important/useful, but maybe I'm not quite picturing what you have in mind.

As for an output system - I'd probably skip the array of variants and use a variadic function template to take all the fields.

I was thinking something more high level/closer to the format you have in mind here, but perhpas I'm having trouble picturing exactly what the output formats are and how generic an API to them would look.

Perhaps there is a reasonable high level API for this that could abstract away the differences between CSV and pretty printed output that wouldn't be specific to the contents.

Test cases might make it easier to see what the final output formats look like & thus what some common API to produce that information might look like.

453

std::min_element?

453–471

Reckon it'd be easier to just sort this then pick out the elements you want? Or are all these partial orderings better?

467

Timings.begin() + Timings.size() == Timings.end() ?

And then it's probably just std::max_element rather than std::nth_element?

470–476

Maybe just move the declaration of Row up and initialize all these members directly so you don't need the extra/duplicate variables?

509–516

Inconsistent use of {} on single line statements (I don't think there's a convention to put {} on if/else but not on if - some people put {} on all parts of an if/else chain if any one part needs them, but that's not the case here)

521

I'd consider breaking each of these blocks (there are several top level blocks in main, each with a comment at the start) of code out into a separate function for readability? Comment -> function name, ideally

[dberris]

Tests generally go in with the functionality in the same commit - and tests for the <foo> tool live in the test/tools/<foo> directory.

Thanks -- yes, I'll add them to the change, but thought of holding off until I got a bit more feedback. :)

If some of this functionality ends up sufficiently factored out into utility libraries, unit tests may be written - though unit tests are pretty rare in LLVM (just culturally - I'm actually more of a fan of them) outside of the general data structures in ADT and some of Support. Mostly it's just end-to-end testing of specific tools, optimization passes, etc.

Since this is a new tool, I'd like to be able to test the units in isolation, so I'll add both end-to-end tests and unit tests. This makes reasoning about the requirements and implementation a lot easier.

I'll ping when I have them lined up, it shouldn't take too long as long as I don't go too deep into the refactoring rabbit hole. :)

tools/xray/xray-fc-account.cc

168–171

Good point -- no your suggestion isn't over-engineered.

I think a neutral format is much better for the tooling. I suspect we can provide a platform-dependent way of extracting the instrumentation map and exporting it in a neutral format. I'm thinking json is the most portable and easier format to consume/transport. So instead of doing this ELF-specific parsing/loading, we can make this step something that can be done in isolation.

I'll break this out into a specific tool that takes an XRay-instrumented binary, and extracts the instrumentation map and turns it into JSON. That way, we can implement this extraction mechanism for every platform supported and have one canonical format for the instrumentation map. This then becomes an alternative input (note that the instrumentation map isn't exactly required, since the XRay trace contains most/all the information that's useful, albeit in the form of function id's). If all we ever had was the function id's, then we can still provide useful information -- the instrumentation map helps only for providing human-readable metadata, like which function is called, and if we have debugging symbols where the function was defined.

237–267

I hadn't thought of just a variadic template -- yes, this would work, with dispatch for handling special kinds of values (i.e. if it's a string, wrap it in quotes and escape any quotes already in the string, etc.).

I'll add test for this specific API since I think it's important to get this right.

[dberris]

• Add initial implementation of llvm-xray extract

[dberris]

Implement llvm-xray account, subset of xray-fc-account.

[dberris]

I'm going to be implementing the error handling logic in xray-account.cc as well as some cosmetic improvements to the text output.

Also, as mentioned in the RFC I sent out (http://lists.llvm.org/pipermail/llvm-dev/2016-August/103984.html) this change might be getting a little too big to be manageable as a single change. I'll probably break this out into smaller pieces, but will do so once we have a better idea of the extent of the changes involved in this effort.

[dberris]

Fairly substantial update that shows the overall structure (or direction) of how this tooling should develop/evolve as we add more subcommands.

There's a lot here to be looked at, and I think it's a good idea to start picking this apart into smaller self-contained pieces.

Reviewers, please specifically have a look at:

• Overall structure/design. I suspect there are better ways to subdivide and remove repetitions in some places. Happy to get feedback on those and start evolving this to a cleaner state even before submit.
• Stylistic issues. Specifically for things like documentation, file organisation, etc. (still fairly new to the LLVM coding guidelines).

The state of this patch now is as follows:

1. We have a tool for extracting the instrumentation map from an xray-instrumented binary (currently just ELF 64-bit for now) and turns it into YAML or JSON.
2. We have a tool for converting an XRay trace from binary to YAML. We follow the naive logging format that's already in compiler-rt.
3. We have a tool for doing some basic function call accounting.

These three tools are implemented as subcommands.

[dberris]

Apologies for piling on a bit on this, just updated the llvm-xray account ...
subcommand to handle tail/sibling call deduction. We also now support loading
YAML instrumentation maps and YAML traces for all subcommands.

[dblaikie]

It's sort of a bit hard to see the forest for the trees reviewing this - I know it's a pain to do smaller reviews that might end up with large refactorings that'll have knock-on effects to later patches, but I think that might work better. Stacking up lots of work unreviewed gets a bit tricky.

Still some outstanding design issues to discuss re: file formats, conversions, portability, etc. But once that's done.

I'm still concerned about reading/writing the binary format using memory mapping/splatting - I think the tools should be portable (in the same way that LLVM/Clang are - we don't build cross compilers, we just build tools that can read/write from/to any format on any platform), but even that's an implementation detail to a degree (unless making the tools that generic removes the need for the separate portable format/conversion tools).

& not sure about YAML+JSON. If you've a strong/unavoidable need for JSON, it's probably best to just implement that. (maybe it's best to just do JSON anyway if you just have a vague preference - as I said in the design review thread, I'm not sure how strong the binding to YAML is in the project)

Higher level design/coding style stuff:

Might be worth pulling out each of the subcommands into their own utility function/file along with the command line arguments. Though I can see an argument (har har) to be made for keeping all the arguments in the same place - but maybe subcommand arguments make sense to be grouped together along with the functionality, separate from the main file.

Basic stylistic stuff: Commenting and header file layout looks fine. Oh, we don't seem to put the trailing _ in our header file names, and other headers in tools use "LLVM_TOOLS_FOO_H" rather than just "FOO_H", so that's probably a good idea to avoid naming conflicts.

tools/llvm-xray/CMakeLists.txt

3–6 ↗

(On Diff #69796)

I think we usually keep these lists (including the source file lists below) sorted... though I see I've not done that consistently in the past either.

tools/llvm-xray/xray-account.cc

27 ↗

(On Diff #69796)

Calling forward on the same object more than once seems problematic - if this was ever passed as an xvalue the pair would construct from the xvalue, then again from the xvalue but now with that value in a moved-from state.

(also does'nt seem like it needs to be a template - that might be overly generic at this point/given the current code)

32 ↗

(On Diff #69796)

Does this need to be a template? Should the parameters be const ref? (might be easier to judge whether const ref is missing if it wasn't a template so we could see what sort of types it was for)

94–169 ↗

(On Diff #69796)

This seems like more than is necessary - I know we were talking in the early versions about how to abstract out the different formats, but what I meant was whether we could abstract out the whole file format, rather than this one part of it. (eg: by having a "HumanWriter" and a "CSVWriter" that just get handed the data, etc). Probably doesn't need a whole record type of its own, and could just pass the relevant parameters to the function as arguments (though a struct doesn't hurt, I suppoes... *shrug)

tools/llvm-xray/xray-log-reader.h

65–73 ↗

(On Diff #69796)

Wouldn't bother about implementing every variant of (c)(begin|end)(const) - just what you need. It's not like you're implementing the whole Container requirements anyway.

tools/xray/xray-extract.cc

32–33 ↗

(On Diff #67999)

Should this be llvm::Error return instead?

37–38 ↗

(On Diff #67999)

branch-to-unreachable should be an assert instead

[dberris]

In D21987#534750, @dblaikie wrote:

It's sort of a bit hard to see the forest for the trees reviewing this - I know it's a pain to do smaller reviews that might end up with large refactorings that'll have knock-on effects to later patches, but I think that might work better. Stacking up lots of work unreviewed gets a bit tricky.

I agree. I'll break this up into multiple smaller changes, and update accordingly.

Still some outstanding design issues to discuss re: file formats, conversions, portability, etc. But once that's done.

I'm still concerned about reading/writing the binary format using memory mapping/splatting - I think the tools should be portable (in the same way that LLVM/Clang are - we don't build cross compilers, we just build tools that can read/write from/to any format on any platform), but even that's an implementation detail to a degree (unless making the tools that generic removes the need for the separate portable format/conversion tools).

That's a tricky one. The problem with _not_ doing this memory-dump format is the cost of doing it in the XRay runtime. We try to be as cheap as possible there (in compiler-rt) so that we don't spend too much time just formatting the log when the process is writing it down to disk. The tradeoff we've made here consciously is that any conversion should happen externally -- i.e. the tool should be able to read this format, and then turn it into something more manageable offline. That's a very conscious trade-off here because we can't afford to use too much time or too much memory on the compiler-rt implementation.

& not sure about YAML+JSON. If you've a strong/unavoidable need for JSON, it's probably best to just implement that. (maybe it's best to just do JSON anyway if you just have a vague preference - as I said in the design review thread, I'm not sure how strong the binding to YAML is in the project)

Not strong, and if anything, I might just drop JSON. :)

Higher level design/coding style stuff:

Might be worth pulling out each of the subcommands into their own utility function/file along with the command line arguments. Though I can see an argument (har har) to be made for keeping all the arguments in the same place - but maybe subcommand arguments make sense to be grouped together along with the functionality, separate from the main file.

I thought about that, then it started to feel over-engineered -- since I'd have to figure out how to dispatch anyway from the main file, I still need to know which command to call based on which subcommand, this seemed like the more prudent thing to do.

Basic stylistic stuff: Commenting and header file layout looks fine. Oh, we don't seem to put the trailing _ in our header file names, and other headers in tools use "LLVM_TOOLS_FOO_H" rather than just "FOO_H", so that's probably a good idea to avoid naming conflicts.

Ah, right. Let me fix those.

tools/llvm-xray/xray-account.cc

94–169 ↗

(On Diff #69796)

Right -- I'm ambivalent about coming up with some generic writer interface here.

One the one hand, the stats generated by this one sub-command follow a very specific format, defined for this particular set of data. I don't see how we can abstract out a writer for CSV and for pretty-printed data, since we'd have different information anyway. For example, the text output currently just has auto-formatted values -- I am thinking of potentially using a formatting ostream here to fix column widths, etc. (very hard to do with a generic implementation).

On the other hand, if we could figure out a way of generating pretty-printed console I/O for arbitrary data, then that sounds like a bigger library than something that just does the simple thing. :)

tools/llvm-xray/xray-log-reader.h

65–73 ↗

(On Diff #69796)

Believe it or not, it seemed like I needed all of these. :/

[dberris]

• [XRay] Implement llvm-xray extract, start of the llvm-xray tool
• Fix header guard spelling

[dblaikie]

Still some outstanding design issues to discuss re: file formats, conversions, portability, etc. But once that's done.

I'm still concerned about reading/writing the binary format using memory mapping/splatting - I think the tools should be portable (in the same way that LLVM/Clang are - we don't build cross compilers, we just build tools that can read/write from/to any format on any platform), but even that's an implementation detail to a degree (unless making the tools that generic removes the need for the separate portable format/conversion tools).

That's a tricky one. The problem with _not_ doing this memory-dump format is the cost of doing it in the XRay runtime.

Ah, sorry - I should clarify/be more specific.

I don't have so much of a problem with the writing side - I appreciate there are performance concerns there. (but wouldn't mind understanding them better - how important is the performance once xray features are turned on? (obviously having xray be as close to zero cost when not in use is important) What sort of cost do you see if it did write a consistent record format? (copying integers into known-width types, changing to a fixed endianness))

But what I'm thinking about is whether the tool could read the input no matter which platform it was running on - each architecture would have a different, but known, format (I mean, it already does - it's just defined more implicitly in terms of "what I can read from memory with this struct overlay"). So the reader can do all the "read this many bytes of integer, switch the endianness from whatever was written to whatever I need in this process, etc". That way the output file becomes portable, without changing the bits/incurring extra cost during the writing step.

Having the tools only work on the architecture where the file was generated seems especially tricky/not-great - and I don't think we have anything like that in LLVM today. llvm-objdump works on COFF files for ARM even when it's run on Linux X86, etc (or should do, if it supports COFF, etc - I haven't looked closely... ).

We try to be as cheap as possible there (in compiler-rt) so that we don't spend too much time just formatting the log when the process is writing it down to disk. The tradeoff we've made here consciously is that any conversion should happen externally -- i.e. the tool should be able to read this format, and then turn it into something more manageable offline. That's a very conscious trade-off here because we can't afford to use too much time or too much memory on the compiler-rt implementation.

Higher level design/coding style stuff:

Might be worth pulling out each of the subcommands into their own utility function/file along with the command line arguments. Though I can see an argument (har har) to be made for keeping all the arguments in the same place - but maybe subcommand arguments make sense to be grouped together along with the functionality, separate from the main file.

I thought about that, then it started to feel over-engineered -- since I'd have to figure out how to dispatch anyway from the main file, I still need to know which command to call based on which subcommand, this seemed like the more prudent thing to do.

Not sure I quite follow - I was thinking something fairly simple, just taking the contents of the "if (Extract)" block in main, and pulling it into a function (with whatever parameters it needs - probably not many, since they're all subcommand arguments anyway, mostly - which could be moved over to that other file (the implementation of extract) or left here and all passed in (but that might be a lot of argument passing)).

[dberris]

In D21987#538323, @dblaikie wrote:

Still some outstanding design issues to discuss re: file formats, conversions, portability, etc. But once that's done.

I'm still concerned about reading/writing the binary format using memory mapping/splatting - I think the tools should be portable (in the same way that LLVM/Clang are - we don't build cross compilers, we just build tools that can read/write from/to any format on any platform), but even that's an implementation detail to a degree (unless making the tools that generic removes the need for the separate portable format/conversion tools).

That's a tricky one. The problem with _not_ doing this memory-dump format is the cost of doing it in the XRay runtime.

Ah, sorry - I should clarify/be more specific.

I don't have so much of a problem with the writing side - I appreciate there are performance concerns there. (but wouldn't mind understanding them better - how important is the performance once xray features are turned on? (obviously having xray be as close to zero cost when not in use is important) What sort of cost do you see if it did write a consistent record format? (copying integers into known-width types, changing to a fixed endianness))

That's a good question.

When it's off, we'd like the cost to be as close to 0 as possible. When it's recording, we'd like the recording cost to be as little as possible so as not to interfere too much with the latency profiles of the functions being instrumented. So this means, if we can get away with introducing a fixed overhead when on (say 0.05 microseconds or 50 nanoseconds on every record) then that's how we'd structure it. So far we've been measuring far less than that on the fixed costs of the trampolines, but we've very wary of the cost of the actual recording as well. So while we can tolerate 0.05 microseconds maximum when we're recording, we'd get up there in case we need to.

Now with future work for various modes and trade-offs on the runtime side, there's a lot of opportunities for reducing other costs -- like memory (doing selective recording based on duration), durable storage (how many bytes are on disk for the log/trace), as well as the cost of the actual recording operation. But in the meantime, we're exploring the bare minimum we can get, and the implementation we currently have does exactly this. :)

But what I'm thinking about is whether the tool could read the input no matter which platform it was running on - each architecture would have a different, but known, format (I mean, it already does - it's just defined more implicitly in terms of "what I can read from memory with this struct overlay"). So the reader can do all the "read this many bytes of integer, switch the endianness from whatever was written to whatever I need in this process, etc". That way the output file becomes portable, without changing the bits/incurring extra cost during the writing step.

Having the tools only work on the architecture where the file was generated seems especially tricky/not-great - and I don't think we have anything like that in LLVM today. llvm-objdump works on COFF files for ARM even when it's run on Linux X86, etc (or should do, if it supports COFF, etc - I haven't looked closely... ).

I agree. There are two changes that could facilitate this support:

1. Indicate in the log what system the log was generated from. This could very well indicate endiannes, sizes of certain fields, etc. We have enough padding in the file headers to support encoding most of this information.
2. Handle the data accordingly from the tools based on the header information.

In the meantime, since we only just run on x86_64 and we have very specific fields, it seems premature to engineer something that will support all the platforms that come along later. And when we end up porting XRay to these other platforms, then we cross that bridge of extending the tool to support data generated from other systems.

Are these concerns a blocker to getting something that works in LLVM first, then evolving it as we support more platforms?

We try to be as cheap as possible there (in compiler-rt) so that we don't spend too much time just formatting the log when the process is writing it down to disk. The tradeoff we've made here consciously is that any conversion should happen externally -- i.e. the tool should be able to read this format, and then turn it into something more manageable offline. That's a very conscious trade-off here because we can't afford to use too much time or too much memory on the compiler-rt implementation.

Higher level design/coding style stuff:

Might be worth pulling out each of the subcommands into their own utility function/file along with the command line arguments. Though I can see an argument (har har) to be made for keeping all the arguments in the same place - but maybe subcommand arguments make sense to be grouped together along with the functionality, separate from the main file.

I thought about that, then it started to feel over-engineered -- since I'd have to figure out how to dispatch anyway from the main file, I still need to know which command to call based on which subcommand, this seemed like the more prudent thing to do.

Not sure I quite follow - I was thinking something fairly simple, just taking the contents of the "if (Extract)" block in main, and pulling it into a function (with whatever parameters it needs - probably not many, since they're all subcommand arguments anyway, mostly - which could be moved over to that other file (the implementation of extract) or left here and all passed in (but that might be a lot of argument passing)).

I thought about this, except I'm not quite as familiar with the commandline flags library -- is there a way to declare the subcommand in the main, then have that defined elsewhere? I ask because of the way adding flags to the subcommands involves getting a reference to a Subcommand. Then in main(...) we still end up checking the Subcommand, and then calling a function.

So if the suggestion is, move the Subcommand and flag definitions in headers, and define a single entry point function, and leave the dispatch to main, that might be doable -- but not sure how much cleaner that would be...

In the meantime I'll do the function argument passing, and see how it goes for the other more complex examples later.

[dberris]

• Move invocation logic to function in subcommand definition

[majnemer]

tools/llvm-xray/xray-extract.cc

92 ↗

(On Diff #70978)

Do you need the llvm:: qualifier here?

92 ↗

(On Diff #70978)

SectionRef is cheap, I'd pass it by value.

tools/llvm-xray/xray-sleds.h

20–26 ↗

(On Diff #70978)

This seems problematic, the fields should probably be ulittle64_t, etc.. This way they have the correct endianness and alignment.

[dberris]

• Address review comments

tools/llvm-xray/xray-sleds.h

20–26 ↗

(On Diff #70978)

Interesting -- can we use ulittle64_t in compiler-rt as well?

[dberris]

• Rebase

[dberris]

• Add a command registry interface

[dblaikie]

test/tools/llvm-xray/X86/Inputs/simple-instrmap.yaml

1 ↗

(On Diff #73604)

What's this file used for? I couldn't see its name mentioned anywhere else and it has no RUN lines.

test/tools/llvm-xray/X86/extract-instrmap.ll

5–6 ↗

(On Diff #73604)

Do we need both yaml and json? If this is only for testing purposes, seems one would suffice? (is this for other purposes?)

tools/llvm-xray/llvm-xray.cc

37–38 ↗

(On Diff #73604)

Roll the variable declaration into the condition

38–40 ↗

(On Diff #73604)

Drop the {} on single-line blocks

(possibly even on the "if (*SC)" block too - though that's more questionable, some people take teh LLVM convention as "no braces on single line blocks" others as "no braces on single statement blocks, even if the statement is spread over multiple lines")

tools/llvm-xray/xray-extract.cc

114 ↗

(On Diff #73604)

pair<StringRef, error_code> looks a bit like it should be llvm::Error, no?

118–119 ↗

(On Diff #73604)

Branch-to-unreachable should be an assert instead, but chances are this should be a handled error case, right? Or is filename non-empty a precondition to this function?

302–303 ↗

(On Diff #73604)

Might be worth making the registerCommand into a "CommandRegistration" (since they'll all want to do it in a global init anyway, so it's not like you'll have other callers/uses of registerCommand except in idioms that all look like this global ctor):

static CommandRegistration Unused(&Extract, [] { ... });

tools/llvm-xray/xray-extract.h

46 ↗

(On Diff #73604)

No need for explicit on multi-arg ctors - we haven't bothered to try to do that across the LLVM codebase.

61–63 ↗

(On Diff #73604)

Documentation comment, perhaps?

It's not clear, looking at the signature, what this might do (how could the output be provided in a StringRef? What would the ownership semantics be? Should this be called "convert" rather than "extract" if it maps from one format to another? Should this have an intermediate representation so that different input and output formats can be generically composed?)

[dberris]

tools/llvm-xray/xray-extract.cc

114 ↗

(On Diff #73604)

Ooh, nice -- I wasn't aware of llvm::Error before. I'll use that instead.

118–119 ↗

(On Diff #73604)

Actually this should be an error, I'll change it.

302–303 ↗

(On Diff #73604)

That's a really good point, I definitely like this style better too. :)

tools/llvm-xray/xray-extract.h

61–63 ↗

(On Diff #73604)

Actually, this is vestigial (we don't define this function anymore).

[dberris]

test/tools/llvm-xray/X86/Inputs/simple-instrmap.yaml

1 ↗

(On Diff #73604)

Ah, yes, this one is required in later patches. I'll remove this from this change.

[dberris]

• Address review comments

[dberris]

Thanks @dblaikie -- PTAL

test/tools/llvm-xray/X86/extract-instrmap.ll

5–6 ↗

(On Diff #73604)

JSON is convenient but not strictly required. Removed.

[dberris]

• Rebase
• Remove unnecessary end marker for enums

[dberris]

Ping?

[dblaikie]

tools/llvm-xray/xray-extract.cc

51–57 ↗

(On Diff #74089)

Could we detect which kind of file we're reading with file magic instead of passing an argument to specify the input format?

Is it useful to specify the input format as YAML if the only task to be performed is to generate YAML? Perhaps the only input format should be ELF/object file.

62–67 ↗

(On Diff #74089)

LLVM isn't too fussy about using declarations/directives - you're welcome to "using llvm::yaml" if that seems suitable, I think? (maybe the yaml namespace has particularly vague names that are problematic?)

(also we don't tend to bother with the '::' global scope qualifier)

104 ↗

(On Diff #74089)

If you can get away without needing to be convertible to error_code, that's probably a good thing (it's just there for backwards compatibility in APIs where we haven't migrated the whole stack to llvm::Error yet)

Also you might be able to get away without needing a custom Error type entirely - maybe just use StringError?

130–132 ↗

(On Diff #74089)

Test case for this codepath? (goes for all the error paths, ideally)

154 ↗

(On Diff #74089)

If you're already using a random access iterator, I'd probably suggest writing this using op- instead of std::distance. std::distance is handy when you need to write generic code which might be applied to non-random access iterators, but otherwise seems a bit obfuscatory.

192–203 ↗

(On Diff #74089)

Same feedback, might be fine to just use StringError

263–265 ↗

(On Diff #74089)

It'd probably be good to keep in the llvm::Error space rather than dropping to std::error_code - you'll probably be losing extra diagnostic information by collapsing into an error code like this. (same a few lines up with BinaryInstrELFError)

279 ↗

(On Diff #74089)

What's the purpose of this conditional operator ("AlwaysIntrument ? true : false") - one would assume AlwaysInstrument is already a boolean and this conditional operator is redundant.

Ah, because it matches the binary format on disk, it's a char.

Could we just get away from memcpying the struct off disk - only being 4 fields, llvm::DataExtractor might suffice to quickly pull 4 fields of known sizes out of a stream? & then the struct's members can be the right types, etc.

(I wonder, but assume it's not appropriate, if we could just use the YAML struct for everything? But I guess we want various APIs consuming these data structures/records that shouldn't be aware of any YAML binding, etc)

285–286 ↗

(On Diff #74089)

a static variable inside a namespace - is the namespace there to have the same effect as "using"? Would using "using" be more obvious/straightforward? Oh, they're already 'using' at the top. So do these namespace decls provide anything?

288 ↗

(On Diff #74089)

Might even be worth having the command registration functor return an llvm::Error, then the error printing could be handled up in the caller (if everyone's just going to print an error and return 1, at least - that could happen up there).

[dberris]

Thanks @dblaikie -- I'll make some changes and ping when ready. :)

tools/llvm-xray/xray-extract.cc

51–57 ↗

(On Diff #74089)

Could we detect which kind of file we're reading with file magic instead of passing an argument to specify the input format?

Not with how we've defined it in compiler-rt, no. :(

Is it useful to specify the input format as YAML if the only task to be performed is to generate YAML? Perhaps the only input format should be ELF/object file.

Good point. For extraction it doesn't make sense. But the class that does extraction can be used (and actually is used in later patches) to load an instrumentation map in YAML. I'll remove the flag and assume that extraction will only ever make sense on ELF/object files.

62–67 ↗

(On Diff #74089)

LLVM isn't too fussy about using declarations/directives - you're welcome to "using llvm::yaml" if that seems suitable, I think? (maybe the yaml namespace has particularly vague names that are problematic?)

Right -- I was merely following the examples. I'll try with just using namespace llvm::yaml here.

(also we don't tend to bother with the '::' global scope qualifier)

Will fix this -- force of habit. :)

104 ↗

(On Diff #74089)

If you can get away without needing to be convertible to error_code, that's probably a good thing (it's just there for backwards compatibility in APIs where we haven't migrated the whole stack to llvm::Error yet)

Unfortunately that seems to be a pure virtual function in ErrorInfo<...>. :(

I like StringError though, I'll change this to use StringError instead (less types, better).

279 ↗

(On Diff #74089)

Yeah, we're constrained by the structure that's in disk. I thought about only ever using the YAML struct for everything, and it boils down to allowing it to be ported/used by other classes/functions that need to load the instrumentation map and don't need any of the YAML functionality.

285–286 ↗

(On Diff #74089)

This is vestigial -- it used to be that there was a function defined in the namespace, and it's changed to this global registration approach. I'll remove the namespaces. :)

288 ↗

(On Diff #74089)

Good idea, yeah I'll change this to make the function return an llvm::Error and consolidate the logging and exit in main.

[dberris]

• Address some review comments

[dberris]

I haven't added the tests, will do so when the style questions have been resolved.

tools/llvm-xray/xray-extract.cc

130–132 ↗

(On Diff #74089)

I'll add more test cases in the next revision.

[dblaikie]

tools/llvm-xray/xray-extract.cc

237–239 ↗

(On Diff #74477)

Previous code only printed this "Cannot extract" message, new code will print that as well as whatever text is in Err, right? Is that a desired change?

Is there some nice/easy way to append/prepend the "Cannot extract" text to the exsiting Error to pass up to main to print there? (splitting the diagnostic printing between the two places seems a bit awkward)

245–246 ↗

(On Diff #74477)

Ideally pass up the string and error code here, rather than printing then passing?

279 ↗

(On Diff #74089)

Still, think it might be nice to move away from it being splatted back and forth to memory like that - and having the expected C++ types (like enums and bools).

[dberris]

• Use errors exclusively

[dberris]

Please have another look @dblaikie -- before I add more tests?

tools/llvm-xray/xray-extract.cc

279 ↗

(On Diff #74089)

I agree -- on the ELF section (and the stuff embedded in the binaries), I think we're a bit constrained by what we can effectively write on the compiler-side (and read on the tooling side). On the trace files though I'm a bit more open to working with a unified encoding format, that was a bit more clever than it currently is.

[dblaikie]

tools/llvm-xray/xray-extract.cc

279 ↗

(On Diff #74089)

I agree -- on the ELF section (and the stuff embedded in the binaries), I think we're a bit constrained by what we can effectively write on the compiler-side (and read on the tooling side). On the trace files though I'm a bit more open to working with a unified encoding format, that was a bit more clever than it currently is.

Sorry I think I'm still confused/we're talking past each other. All I mean is that, rather than this tool splatting into a carefully laid out struct, it would use something like DataExtractor to extract the carefully laid out bytes into a more generic struct.

The file formats and writer would remain the same - just the reader would be more robust and more a usable type for the rest of the APIs.

(I suppose put another way: Using the YAML struct with its YAML types isn't really ideal for general tool code that's trying to process these records. Equally, using a carefully laid out struct with surprising types (char instead of bool/enum, explicit padding, etc) has the same problem. The main interchange structure should probably be the generic semantic thing, not YAML or binary file related - and once that happens, we could skip the packed struct entirely and just read in the few records with DataExtractor or a similar API)

[dberris]

• Use a common sled representation, hide ELF64-specific implementation detail

[dberris]

Please have another look @dblaikie.

tools/llvm-xray/xray-extract.cc

279 ↗

(On Diff #74089)

Ah, yes, this makes sense. I've hidden the ELF64-specific sled layout and defined a higher level SledEntry type that could be exposed later.

[dblaikie]

tools/llvm-xray/xray-extract.cc

141–144 ↗

(On Diff #74945)

I'm still a bit concerned about doing this via memory mapping (what if we are on a different platform that happens to add some extra padding between fields, etc?)

So I'd suggest using DataExtractor or similar (then you don't have to worry about alignment either) techniques/devices/tools, probably?

Maybe it just seems like this function is harder to read than it is in the code review, but might consider breaking it up - perhaps taking all the error handling at the beginning and turning it into one utility function, so this function (LoadBinaryInstrELF) can focus on the parsing, etc (or break out this parsing into another function, etc - or even both).

262–266 ↗

(On Diff #74945)

Would it make sense to sink this code into InstrumentationMapExtractor's ctor? (it has all the information - it knows it's trying to extract an instrumentation map, and the name of the input - so it seems it should be responsible for creating this message, maybe?)

[dberris]

• Use DataExtractor to load data from the memory mapped object file.

[dberris]

PTAL @dblaikie

tools/llvm-xray/xray-extract.cc

141–144 ↗

(On Diff #74945)

Ah, I get it now. I'm using llvm::DataExtractor now.

Refactoring this further seems pre-mature, given that this is already an implementation detail. When supporting other formats, it would be something to think about, I agree.

262–266 ↗

(On Diff #74945)

Actually, nope -- because users of this class could choose to ignore the errors (i.e. treat it as if there was no available instrumentation map). It's just that for this sub-command, it wouldn't work if extraction actually failed. :)

[dblaikie]

Generally looking pretty good - a few little nits & more test coverage (error cases, for example) is probably a good idea.

test/tools/llvm-xray/X86/extract-instrmap.ll

5–6 ↗

(On Diff #73604)

Convenient how?
I suppose what i'm trying to understand is: why /both/? (which is to say, what does each offer that the other doesn't)

12 ↗

(On Diff #75109)

Is it worth checking the specific addresses? If this test is simple enough to provide fairly stable values here - to make sure the algorithms, etc, are working correctly & not just printing garbage values?

tools/llvm-xray/xray-extract.cc

85 ↗

(On Diff #75109)

I'd sink this down into the function/near the use (the general principle of keeping variables in the smallest scope needed)

163 ↗

(On Diff #75109)

Drop the "? false : true" here, and use !=, perhaps:

"Entry.AlwaysInstrument = AlwaysInstrument != 0" (potentially even drop the "!= 0", but I can see how that helps readability.

181 ↗

(On Diff #75109)

Move assignment rather than swap? (but equally I wouldn't mind the old code that left the OutputSleds in an unspecified state on failure)

233–237 ↗

(On Diff #75109)

This code (& LoadYAMLInstrFile) is dead/untested - perhaps should be moved into another/separate change.

262–266 ↗

(On Diff #74945)

I'm not sure I understand this - could you rephrase?

What I mean is: The joining of this "Cannot extract instrumentation map from" seems like it could go inside the InstrumentationMapExtractor ctor (since it has all the context to make that message and the message seems appropriate at that level). Then at this level (in the CommandRegistration) we just propagate the error up ("if (Err) return Err; or whatever)

tools/llvm-xray/xray-extract.h

38 ↗

(On Diff #75109)

Doesn't look like this needs to be a member? (it's only used during construction, if I'm reading it correctly)

50 ↗

(On Diff #75109)

Unused/dead code

tools/llvm-xray/xray-registry.h

31–32 ↗

(On Diff #75109)

Could just make this a struct - since it's only member's public anyway.

36 ↗

(On Diff #75109)

It doesn't seem like it actually requires that SC is not null (& pedantically the terminology would be "not null" (or "not a null pointer" - 'nullptr' is just some specific null pointer literal)) - but, sure - seems OK to say that's not acceptable even if it'd be fine for the current implementation.

Is it worth just defining this function to only work if the SubCommand is registered? (assert when not found, instead of returning the empty std::function)

[dberris]

• Add failure tests
• Address more review comments

[dberris]

test/tools/llvm-xray/X86/extract-instrmap.ll

5–6 ↗

(On Diff #73604)

JSON was convenient for making it easily parse-able and view-able by anything that will show it on a browser. :)

12 ↗

(On Diff #75109)

Yep, added a few more functions to be a bit more complete.

tools/llvm-xray/xray-extract.cc

262–266 ↗

(On Diff #74945)

Ah, right -- I've moved the concatenation of the Twine into the error generation parts.

tools/llvm-xray/xray-extract.h

50 ↗

(On Diff #75109)

Unused/dead code

Yes, but this is actually used in a later (stacked) change...

[dberris]

This is ready for another look @dblaikie -- added some failure tests that were easy to catch (not found, no instrumentation map) and provided some sample binaries to use instead of creating one on the fly (as it seemed harder to generate a final linked executable from a .ll).

If you have ideas about how to make the sequence:

llc ...; <link the .o into a final binary> ;  llvm-xray extract <final binary>

work in a .ll test, I'd be very interested to try.

[dblaikie]

In D21987#576231, @dberris wrote:

This is ready for another look @dblaikie -- added some failure tests that were easy to catch (not found, no instrumentation map) and provided some sample binaries to use instead of creating one on the fly (as it seemed harder to generate a final linked executable from a .ll).

If you have ideas about how to make the sequence:

llc ...; <link the .o into a final binary> ;  llvm-xray extract <final binary>

work in a .ll test, I'd be very interested to try.

Could you explain why you need a linked binary rather than just an object file? What changes? Relocations, I guess? All the addresses look like zero?

Yeah, doubt there's much to do about that - no way to produce linked binaries with the LLVM tools available to the test suite, and no point implementing support in the tool to handle unapplied relocations (unlike dwarfdump which does handle them, and there's more reason to run dwarfdump on unlinked objects, so it's worth having that support for more than just testing).

tools/llvm-xray/xray-extract.cc

89–92 ↗

(On Diff #75393)

Untested (do we need this test? Presumably we just won't be able to open the file)

97–98 ↗

(On Diff #75393)

I'm guessing this is the path we take for "no such file or directory"? (ie: covered by the test for that)

100–103 ↗

(On Diff #75393)

Untested

118–121 ↗

(On Diff #75393)

Untested (though, granted - not sure quite how to test this, but could look further into libObject to see how getContents can fail)

127–131 ↗

(On Diff #75393)

Untested

206–208 ↗

(On Diff #75393)

Guess this should just be an assert for now? (represents a programmer error/isn't reachable/testable/etc?)

tools/llvm-xray/xray-registry.cc

34–35 ↗

(On Diff #75393)

Replace branch-to-unreachable with assert.

[dberris]

In D21987#576626, @dblaikie wrote:

In D21987#576231, @dberris wrote:

This is ready for another look @dblaikie -- added some failure tests that were easy to catch (not found, no instrumentation map) and provided some sample binaries to use instead of creating one on the fly (as it seemed harder to generate a final linked executable from a .ll).

If you have ideas about how to make the sequence:

llc ...; <link the .o into a final binary> ;  llvm-xray extract <final binary>

work in a .ll test, I'd be very interested to try.

Could you explain why you need a linked binary rather than just an object file? What changes? Relocations, I guess? All the addresses look like zero?

The addresses are basically zero on a .o :/

Yeah, doubt there's much to do about that - no way to produce linked binaries with the LLVM tools available to the test suite, and no point implementing support in the tool to handle unapplied relocations (unlike dwarfdump which does handle them, and there's more reason to run dwarfdump on unlinked objects, so it's worth having that support for more than just testing).

Yep, I think the binary should be fine here.

However, I'm having some trouble generating malformed binaries without resorting to hex-editing some existing files. Any recommendations for faking "bad" inputs to test the error conditions?

tools/llvm-xray/xray-extract.cc

89–92 ↗

(On Diff #75393)

Good point, removed.

97–98 ↗

(On Diff #75393)

Yes. that's correct.

[dberris]

• Add test for empty, convert some if-unreachable to assert

[dberris]

• Add elf32 sample and test for unsupportedness
• Add test for badly sized instrumentation map entries.

[dberris]

Added a couple more tests, ptal -- I haven't quite resorted to hex-editing files, but close enough with deliberately generating a bad XRay instrumentation map with a modified clang+llvm local build.

tools/llvm-xray/xray-extract.cc

118–121 ↗

(On Diff #75393)

I looked, and it had something to do with the ELF encoding of a file (say, if the supposed size of the section defined in the header is different in reality (through some checks)). Not sure how to properly test this yet.

[dblaikie]

tools/llvm-xray/llvm-xray.cc

35 ↗

(On Diff #75672)

Perhaps it'd be better to catch this case earlier - disallow registering with a null/empty function (just assert) rather than quietly not executing anything?

[dberris]

Squash local commits and rebase before landing.

[dberris]

Thanks for the review @dblaikie!

tools/llvm-xray/llvm-xray.cc

35 ↗

(On Diff #75672)

Good idea. Added an assert on the registration path to make sure the function is not "empty".

[dberris]

Update description.

[dberris]

Landed in rL285155.

[dberris]

Rolled back in rL285155, broke the tests.

[dberris]

Landed as rL285165.

tools/CMakeLists.txt

 # requires targets specified in DEPENDS to exist before the call to
 # ExternalProject_Add.
 add_llvm_tool_subdirectory(lto)
 add_llvm_tool_subdirectory(gold)
 add_llvm_tool_subdirectory(llvm-ar)
 add_llvm_tool_subdirectory(llvm-config)
 add_llvm_tool_subdirectory(llvm-lto)
 add_llvm_tool_subdirectory(llvm-profdata)
+add_llvm_tool_subdirectory(xray)
 
 # Projects supported via LLVM_EXTERNAL_*_SOURCE_DIR need to be explicitly
 # specified.
 add_llvm_external_project(clang)
 add_llvm_external_project(llgo)
 add_llvm_external_project(lld)
 add_llvm_external_project(lldb)
 

tools/xray/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  ${LLVM_TARGETS_TO_BUILD}
+  Support
+  DebugInfoDWARF
+  Symbolize
+  Object)
+
+add_llvm_tool(xray-fc-account
+  xray-fc-account.cc)

tools/xray/xray-fc-account.cc

+//===- xray-fc-account.cc - XRay Function Call Accounting Tool ------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the Function Call Accounting tool that takes an XRay
+// trace and generates function call accounting statistics for that given trace.
+//
+//===----------------------------------------------------------------------===//
+//
+// Usage:
+//
+//   xray-fc-account [-instr_map=<binary/map file>] [-verbose] [-keep_going]
+//                   [-format=csv/text]
+//                   <input file>
+//
+// This tool computes some useful statistics regarding function calls present
+// from an XRay trace file. The kinds of statistics this generates fall into the
+// following categories:
+//
+//   - Basic latency statistics (count, minimum, median, 90th percentile, 99th
+//     percentile, maximum).
+//   - Per-thread timestamp accounting (minimum and maximum timestamps per
+//     thread)
+//   - Per-CPU timestamp accounting (minimum and maximum timestamps per CPU)
+//
+// In '-verbose' mode, we also reconstruct the stack traces encountered from the
+// input trace file showing entries of the following form:
+//
+//   [<TSC>,cpu=<CPU>] Entry/Exit  <function indented by stack level>
+//
+
+#include <algorithm>
+#include <fcntl.h>
+#include <map>
+#include <sstream>
+#include <stack>
+#include <unistd.h>
+#include <unordered_map>
+#include <utility>
+
+#include "llvm/DebugInfo/Symbolize/Symbolize.h"
+#include "llvm/Object/ELF.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ELF.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+static StringRef ToolName;
+
+static cl::opt<std::string> Input(cl::Positional, cl::desc("<input file>"),
+                                  cl::Required);
+
+static cl::opt<std::string> BinaryInstrMap(
+    "instr_map",
+    cl::desc("file containing an xray instrumentation map section"),
+    cl::value_desc("filename"), cl::Optional);
+static cl::alias BinaryInstrMap2("m", cl::desc("Alias for -instr_map"),
+                                 cl::aliasopt(BinaryInstrMap));
+static cl::opt<bool> Verbose(
+    "verbose",
+    cl::desc(
+        "play-by-play logging of encountered records, useful for debugging"),
+    cl::init(false));
+static cl::alias Verbose2("v", cl::desc("Alias for -verbose"),
+                          cl::aliasopt(Verbose));
+
+static cl::opt<bool>
+    KeepGoing("keep_going",
+              cl::desc("print errors and continue processing log"),
+              cl::init(false));
+static cl::alias KeepGoing2("k", cl::desc("Alias for -keep_going"),
+                            cl::aliasopt(KeepGoing));
+
+enum OutputFormats { TEXT, CSV };
+static cl::opt<OutputFormats> OutputFormat(
+    "format", cl::desc("output format"),
+    cl::values(clEnumValN(OutputFormats::TEXT, "text", "text summary output"),
+               clEnumValN(OutputFormats::CSV, "csv", "output data in csv"),
+               clEnumValEnd),
+    cl::init(OutputFormats::TEXT));
+
+LLVM_ATTRIBUTE_NORETURN static void fail(Twine Error) {
+  outs() << ToolName << ": " << Error << ".\n";
+  exit(1);
+}
+
+class FileCloser {
+  int Fd;
+
+public:
+  explicit FileCloser(int Fd) : Fd(Fd) {}
+
+  ~FileCloser() {
+    if (Fd != -1)
+      close(Fd);
+  }
+};
+
+namespace __xray {
+// FIXME: Make these available in a common header between compiler-rt and this
+// tool?
+
+struct alignas(32) XRayFileHeader {
+  uint16_t Version = 0;
+  uint16_t Type = 0;
+  uint64_t CycleFrequency = 0;
+  bool ConstantTSC = 0;
+  bool NonstopTSC = 0;
+  char Padding[14] = {};
+} __attribute__((packed));
+
+struct alignas(32) XRayRecord {
+  uint16_t RecordType = 0;
+  // The CPU where the thread is running. We assume number of CPUs <= 256.
+  uint8_t CPU = 0;
+
+  // The type of the event. Usually either ENTER = 0 or EXIT = 1.
+  uint8_t Type = 0;
+
+  // The function ID for the record.
+  int32_t FuncId = 0;
+
+  // Get the full 8 bytes of the TSC when we get the log record.
+  uint64_t TSC = 0;
+
+  // The thread ID for the currently running thread.
+  uint32_t TId = 0;
+
+  // Use some bytes in the end of the record for buffers.
+  char Buffer[4] = {};
+} __attribute__((packed));
+
+struct XRaySledEntry {
+  uint64_t Address;
+  uint64_t Function;
+  unsigned char Kind;
+  unsigned char AlwaysInstrument;
+  unsigned char Padding[14];
+};
+}
+
+typedef std::unordered_map<int32_t, uint64_t> FunctionAddressMap;
+
+using namespace __xray;
+
+FunctionAddressMap LoadBinaryInstr() {
+  FunctionAddressMap InstrMap;
+  if (BinaryInstrMap.empty()) {
+    errs() << ToolName << ": instrumentation map not provided, using raw "
+                          "function IDs in output.\n";
+    return InstrMap;
+  }
+
+  auto ObjectFile = object::ObjectFile::createObjectFile(BinaryInstrMap);
+
+  // FIXME: Maybe support other ELF formats. For now, 64-bit Little Endian only.
+  if (!ObjectFile || !ObjectFile->getBinary()->isELF())
+    fail("File format not supported (only does ELF).");
+
+  // Find the section named "xray_instr_map".
+  StringRef Contents = "";
+  const auto &Sections = ObjectFile->getBinary()->sections();
+  auto I = llvm::find_if(Sections, [&](const object::SectionRef &Section) {
+    StringRef Name = "";
+    if (Section.getName(Name))
+      return false;
+    return Name == "xray_instr_map";
+  });
+  if (I == Sections.end())
+    fail("Failed to find XRay instrumentation map.");
+  if (I->getContents(Contents))
+    fail("Failed to get contents of 'xray_instr_map' section.");
+
+  // Treat Contents as though it were an array of XRaySledEntry elements.
+  ArrayRef<XRaySledEntry> Sleds(
+      reinterpret_cast<const XRaySledEntry *>(Contents.data()),
+      Contents.size() / sizeof(XRaySledEntry));
+
+  // We replicate the function id generation scheme implemented in the runtime
+  // here. Ideally we should be able to break it out, or output this map from
+  // the runtime, but that's a design point we can discuss later on. For now, we
+  // replicate the logic and move on.
+  int32_t FuncId = 1;
+  uint64_t CurFn = 0;
+  for (const auto &Sled : Sleds) {
+    auto F = Sled.Function;
+    if (CurFn == 0) {
+      CurFn = F;
+      InstrMap[FuncId] = F;
+    }
+    if (F != CurFn) {
+      ++FuncId;
+      CurFn = F;
+      InstrMap[FuncId] = F;
+    }
+  }
+  return InstrMap;
+}
+
+// This class consolidates common operations related to Function IDs.
+class FuncIdConversionHelper {
+  symbolize::LLVMSymbolizer &Symbolizer;
+  const FunctionAddressMap &FunctionAddresses;
+
+public:
+  FuncIdConversionHelper(symbolize::LLVMSymbolizer &Symbolizer,
+                         const FunctionAddressMap &FunctionAddresses)
+      : Symbolizer(Symbolizer), FunctionAddresses(FunctionAddresses) {}
+
+  FuncIdConversionHelper(const FuncIdConversionHelper &) = default;
+
+  std::string SymbolOrNumber(int32_t FuncId) const {
+    std::ostringstream F;
+    auto It = FunctionAddresses.find(FuncId);
+    if (It == FunctionAddresses.end()) {
+      F << "#" << FuncId;
+      return F.str();
+    }
+
+    auto ResOrErr = Symbolizer.symbolizeCode(BinaryInstrMap, It->second);
+    if (!ResOrErr || ResOrErr.get().FunctionName == "<invalid>") {
+      F << "@(" << std::hex << It->second << ")";
+    } else {
+      auto &DI = ResOrErr.get();
+      F << DI.FunctionName;
+    }
+    return F.str();
+  }
+
+  std::string FileLineAndColumn(int32_t FuncId) const {
+    auto It = FunctionAddresses.find(FuncId);
+    if (It == FunctionAddresses.end()) {
+      return "(unknown)";
+    }
+    std::ostringstream F;
+    auto ResOrErr = Symbolizer.symbolizeCode(BinaryInstrMap, It->second);
+    if (!ResOrErr || ResOrErr.get().FileName == "<invalid>")
+      return "(unknown)";
+    auto &DI = ResOrErr.get();
+    auto LastSlash = DI.FileName.find_last_of('/');
+    if (LastSlash != std::string::npos) {
+      F << DI.FileName.substr(LastSlash + 1);
+    } else {
+      F << DI.FileName;
+    }
+    F << ":" << DI.Line << ":" << DI.Column;
+    return F.str();
+  }
+};
+
+// We consolidate the data into a struct which we can output in various forms.
+struct ResultRow {
+  uint64_t Count;
+  double Min;
+  double Median;
+  double Pct90;
+  double Pct99;
+  double Max;
+  std::string DebugInfo;
+  std::string Function;
+};
+
+void PrintStatsCSV(const ResultRow &Row) {
+  outs() << Row.Count << ',' << Row.Min << ',' << Row.Median << ',' << Row.Pct90
+         << ',' << Row.Pct99 << ',' << Row.Max << ",\"" << Row.DebugInfo
+         << "\"," << '"' << Row.Function << "\"\n";
+}
+
+void PrintStatsTEXT(const ResultRow &Row) {
+  outs() << Row.Count << "\t"
+         << "[" << Row.Min << ", " << Row.Median << ", " << Row.Pct90 << ", "
+         << Row.Pct99 << ", " << Row.Max << "] " << Row.DebugInfo << "\t"
+         << Row.Function << "\n";
+}
+
+void PrintStatsHeader(OutputFormats OF) {
+  if (OF == OutputFormats::TEXT)
+    outs() << "count\t[min,median,90%ile,99%ile,max]\tdebug\tfunction\n";
+  if (OF == OutputFormats::CSV)
+    outs() << "count,min,median,90%ile,99%ile,max,debuginfo,function\n";
+}
+
+int main(int argc, char *argv[]) {
+  ToolName = argv[0];
+  cl::ParseCommandLineOptions(
+      argc, argv, "XRay Function Call Accounting (xray-fc-account)\n\n"
+                  "  This program takes an XRay trace file and does some basic "
+                  "function call accounting statistics.\n");
+
+  if (Input.empty())
+    fail("No input file provided.");
+
+  FunctionAddressMap FunctionAddresses = LoadBinaryInstr();
+  if (OutputFormat == OutputFormats::TEXT)
+    outs() << "Loaded " << FunctionAddresses.size()
+           << " entries for the instrumentation map.\n";
+
+  int Fd;
+  do {
+    Fd = open(Input.c_str(), O_RDONLY);
+  } while (Fd == -1 && errno == EINTR);
+  if (Fd == -1)
+    fail(Twine("Failed to open file '") + Input + "'; errno=" + Twine(errno));
+  FileCloser FC(Fd);
+  symbolize::LLVMSymbolizer::Options Opts(
+      symbolize::FunctionNameKind::LinkageName, true, true, false, "");
+  symbolize::LLVMSymbolizer Symbolizer(Opts);
+  XRayFileHeader Header;
+  int ReadBytes = 0;
+  while ((ReadBytes = read(Fd, &Header, sizeof(XRayFileHeader))) == -1 &&
+         errno == EINTR) {
+    // Do nothing.
+  }
+  if (ReadBytes == 0 || ReadBytes == -1)
+    fail(Twine("Failed to read file '") + Input + "'; " + Twine(errno));
+
+  XRayRecord Record;
+  std::map<pid_t, std::vector<std::pair<int32_t, uint64_t>>> FunctionStack;
+  std::map<int32_t, std::vector<int64_t>> FunctionTimings;
+  std::map<pid_t, std::pair<uint64_t, uint64_t>> ThreadMinMaxTSC;
+  std::map<uint8_t, std::pair<uint64_t, uint64_t>> CPUMinMaxTSC;
+  uint64_t CurTSC = 0;
+  FuncIdConversionHelper H(Symbolizer, FunctionAddresses);
+  while (auto ReadBytes = read(Fd, &Record, sizeof(XRayRecord))) {
+    if (ReadBytes == -1) {
+      if (errno == EINTR)
+        continue;
+      fail(Twine("Failed to read file '") + Input + "'; errno=" + Twine(errno));
+    }
+
+    if (CurTSC == 0)
+      CurTSC = Record.TSC;
+
+    auto &ThreadFuncStack = FunctionStack[Record.TId];
+    if (Verbose) {
+      outs() << "[tid=" << Record.TId << ",cpu=" << int32_t{Record.CPU} << "] "
+             << Record.TSC << ": " << (Record.Type == 0 ? "E" : "X")
+             << Record.FuncId << "@(";
+      auto FuncAddr = FunctionAddresses.find(Record.FuncId);
+      if (FuncAddr == FunctionAddresses.end()) {
+        outs() << "unknown";
+      } else {
+        outs().write_hex(FuncAddr->second);
+      }
+      outs() << ") ";
+
+      // Let's indent according to stack depth for this thread. For Entry, we
+      // just add the correct number of indents. For Exit, we reduce it by 1.
+      for (size_t i = 0 + Record.Type; i < ThreadFuncStack.size(); i++) {
+        outs() << "  ";
+      }
+      outs() << H.SymbolOrNumber(Record.FuncId) << "\n";
+    }
+
+    // Record Thread min/max TSC's.
+    {
+      auto &MinMaxTSC = ThreadMinMaxTSC[Record.TId];
+      if (MinMaxTSC.first == 0 || MinMaxTSC.second == 0)
+        MinMaxTSC = std::make_pair(Record.TSC, Record.TSC);
+      MinMaxTSC = std::make_pair(std::min(MinMaxTSC.first, Record.TSC),
+                                 std::max(MinMaxTSC.second, Record.TSC));
+    }
+
+    // Record CPU min/max TSC's.
+    {
+      auto &MinMaxTSC = CPUMinMaxTSC[Record.CPU];
+      if (MinMaxTSC.first == 0 || MinMaxTSC.second == 0)
+        MinMaxTSC = std::make_pair(Record.TSC, Record.TSC);
+      MinMaxTSC = std::make_pair(std::min(MinMaxTSC.first, Record.TSC),
+                                 std::max(MinMaxTSC.second, Record.TSC));
+    }
+
+    if (Record.TSC < CurTSC) {
+      errs() << "Record TSC (" << Record.TSC << ") < Latest TSC (" << CurTSC
+             << ")\n";
+      if (!KeepGoing)
+        fail("Out-of-order TSC records found.");
+    }
+
+    if (Record.Type == 0)
+      FunctionStack[Record.TId].push_back({Record.FuncId, Record.TSC});
+
+    if (Record.Type == 1) {
+      if (FunctionStack[Record.TId].back().first != Record.FuncId) {
+        // This could be a tail call, so look up the stack to see whether we've
+        // found an entry that shouldn't be there.
+        auto Parent =
+            std::find_if(ThreadFuncStack.rbegin(), ThreadFuncStack.rend(),
+                         [&](const std::pair<const int32_t, uint64_t> &Entry) {
+                           return Entry.first == Record.FuncId;
+                         });
+        if (Parent != ThreadFuncStack.rend()) {
+          auto It = ThreadFuncStack.rbegin();
+          while (It <= Parent) {
+            const auto &Top = *It;
+            int64_t Timing = std::max(Top.second, Record.TSC) -
+                             std::min(Top.second, Record.TSC);
+            FunctionTimings[Top.first].push_back(Timing);
+            ThreadFuncStack.pop_back();
+            It = ThreadFuncStack.rbegin();
+          }
+        } else {
+          errs() << ToolName << ": Encountered X" << Record.FuncId << "("
+                 << H.SymbolOrNumber(Record.FuncId) << ") not matching E"
+                 << ThreadFuncStack.back().first << "("
+                 << H.SymbolOrNumber(ThreadFuncStack.back().first) << ")\n";
+          errs() << "Current stack dump:\n";
+          for (auto &ThreadStack : FunctionStack) {
+            errs() << "Thread ID: " << ThreadStack.first << "\n";
+            auto Level = ThreadStack.second.size();
+            for (const auto &Entry : llvm::reverse(ThreadStack.second)) {
+              errs() << "#" << Level-- << "\t" << H.SymbolOrNumber(Entry.first)
+                     << '\n';
+            }
+          }
+          if (!KeepGoing)
+            fail("Corrupted input file found.");
+        }
+      } else {
+        const auto &Top = FunctionStack[Record.TId].back();
+        int64_t Timing =
+            std::max(Top.second, Record.TSC) - std::min(Top.second, Record.TSC);
+        auto &Timings = FunctionTimings[Record.FuncId];
+        Timings.push_back(Timing);
+        ThreadFuncStack.pop_back();
+      }
+    }
+    CurTSC = Record.TSC;
+  }
+
+  bool HasCyclesPerSec = Header.CycleFrequency != 0;
+  auto CyclesPerSec = static_cast<double>(Header.CycleFrequency);
+
+  if (OutputFormat == OutputFormats::TEXT && HasCyclesPerSec)
+    outs() << "Cycle counter frequency = " << Header.CycleFrequency << "hz\n"
+           << "Durations below are in seconds.\n";
+
+  if (!FunctionTimings.empty()) {
+    if (OutputFormat == OutputFormats::TEXT)
+      outs() << "\nTotal functions with timings: " << FunctionTimings.size()
+             << '\n';
+    PrintStatsHeader(OutputFormat);
+    for (auto &FT : FunctionTimings) {
+      const auto &FuncId = FT.first;
+      auto &Timings = FT.second;
+      std::nth_element(Timings.begin(), Timings.begin(), Timings.end());
+      auto Min = Timings.front();
+      auto MedianOff = Timings.size() / 2;
+      std::nth_element(Timings.begin(), Timings.begin() + MedianOff,
+                       Timings.end());
+      auto Median = Timings[MedianOff];
+      auto Pct90Off = std::floor(Timings.size() * 0.9);
+      std::nth_element(Timings.begin(), Timings.begin() + Pct90Off,
+                       Timings.end());
+      auto Pct90 = Timings[Pct90Off];
+      auto Pct99Off = std::floor(Timings.size() * 0.99);
+      std::nth_element(Timings.begin(), Timings.begin() + Pct99Off,
+                       Timings.end());
+      auto Pct99 = Timings[Pct99Off];
+      std::nth_element(Timings.begin(), Timings.begin() + Timings.size(),
+                       Timings.end());
+      auto Max = Timings.back();
+      ResultRow Row;
+      Row.Count = Timings.size();
+      Row.Min = Min;
+      Row.Median = Median;
+      Row.Pct90 = Pct90;
+      Row.Pct99 = Pct99;
+      Row.Max = Max;
+      if (HasCyclesPerSec) {
+        Row.Min /= CyclesPerSec;
+        Row.Median /= CyclesPerSec;
+        Row.Pct90 /= CyclesPerSec;
+        Row.Pct99 /= CyclesPerSec;
+        Row.Max /= CyclesPerSec;
+      }
+      Row.DebugInfo = H.FileLineAndColumn(FuncId);
+      Row.Function = H.SymbolOrNumber(FuncId);
+      switch (OutputFormat) {
+      case OutputFormats::TEXT:
+        PrintStatsTEXT(Row);
+        break;
+      case OutputFormats::CSV:
+        PrintStatsCSV(Row);
+        break;
+      };
+    }
+  }
+
+  // Print out thread total durations.
+  if (!ThreadMinMaxTSC.empty()) {
+    if (OutputFormat == OutputFormats::TEXT)
+      outs() << "\nTotal threads: " << ThreadMinMaxTSC.size()
+             << "\nTID\t(min,max)\tduration in secs\n";
+    if (OutputFormat == OutputFormats::CSV)
+      outs() << "\nTID,min tsc,max tsc,duration\n";
+    for (auto &Thread : ThreadMinMaxTSC) {
+      auto &MinMax = Thread.second;
+      if (OutputFormat == OutputFormats::TEXT)
+        outs() << Thread.first << "\t(" << MinMax.first << ", " << MinMax.second
+               << ")\t";
+      if (OutputFormat == OutputFormats::CSV)
+        outs() << Thread.first << ',' << MinMax.first << ',' << MinMax.second
+               << ',';
+      if (HasCyclesPerSec) {
+        outs() << (MinMax.second - MinMax.first) / CyclesPerSec;
+      } else {
+        outs() << (MinMax.second - MinMax.first);
+      }
+      outs() << '\n';
+    }
+  }
+
+  // Print out CPU start/end ranges and durations.
+  if (!CPUMinMaxTSC.empty()) {
+    if (OutputFormat == OutputFormats::TEXT)
+      outs() << "\nTotal CPUs: " << CPUMinMaxTSC.size()
+             << "\nCPUID\t(min,max)\tduration in secs\n";
+    if (OutputFormat == OutputFormats::CSV)
+      outs() << "\nCPUID,min tsc,max tsc,duration\n";
+    for (auto &CPU : CPUMinMaxTSC) {
+      auto &MinMax = CPU.second;
+      if (OutputFormat == OutputFormats::TEXT)
+        outs() << static_cast<uint32_t>(CPU.first) << "\t(" << MinMax.first
+               << ", " << MinMax.second << ")\t";
+      if (OutputFormat == OutputFormats::CSV)
+        outs() << static_cast<uint32_t>(CPU.first) << ',' << MinMax.first << ','
+               << MinMax.second << ',';
+      if (HasCyclesPerSec) {
+        outs() << (MinMax.second - MinMax.first) / CyclesPerSec;
+      } else {
+        outs() << (MinMax.second - MinMax.first);
+      }
+      outs() << '\n';
+    }
+  }
+}