[trace] Introduce Hierarchical Trace Representation (HTR) and add `thread trace export ctf` command for Intel PT trace visualization

[jj10306]

Summary

This diff introduces Hierarchical Trace Representation (HTR) and creates the thread trace export ctf -f <filename> -t <thread_id> command to export an Intel PT trace's HTR to Chrome Trace Format (CTF) for visualization.

See lldb/docs/htr.rst for context/documentation on HTR.

Overview of Changes

• Add HTR documentation (see lldb/docs/htr.rst)
• Add HTR structures (layer, block, block metadata)
• Implement "Basic Super Block" HTR pass
• Add 'thread trace export ctf' command to export the HTR of an Intel PT trace to Chrome Trace Format (CTF)

As this diff is the first iteration of HTR and trace visualization, future diffs will build on this work by generalizing the internal design of HTR and implementing new HTR passes that provide better trace summarization/visualization.

See attached video for an example of Intel PT trace visualization:

[wallace]

lldb/include/lldb/Target/TraceHTR.h

33 ↗

(On Diff #357641)

pass the map by reference

42–68 ↗

(On Diff #357641)

the consistent style is that toJSON methods are not class members but static functions

73 ↗

(On Diff #357641)

+1
I don't think you should go with templates unless you had more TMetadata objects

[wallace]

lldb/include/lldb/Target/TraceHTR.h

29 ↗

(On Diff #357641)

This is a very expensive structure if you are going to have for Layer 1, which is just a bunch of instructions => m_num_instructions will always be 1 and m_func_calls will have 0 or 1 entries.

I'd suggest creating two classes:

InstructionLayer (layer 0), where you could assume that m_num_instructions is 1 and instead of having the map m_func_calls, you can have an Optional<ConstString> for the function call, or you could also have a map (address -> ConstString) at the layer level that could use to look up function calls instead of storing this information in each instruction. If you follow the latter advice, the memory usage of Layer 0 would have small overhead, i.e. InstructionLayer = Instruction list + function map

BlockLayer (layer 1+), here you have blocks of 1 or more instructions. Assuming that the number of blocks will be small, you could store more metadata in each block and here statistics like number of function calls make more sense.

41 ↗

(On Diff #357641)

See my comment above, this is too memory expensive

[jj10306]

lldb/include/lldb/Target/TraceHTR.h

3 ↗

(On Diff #357641)

Working on comprehensive HTR documentation that I plan to store in docs/ - will update the documentation in this file to mention where the comprehensive documentation can be found.

27 ↗

(On Diff #357641)

Working on comprehensive HTR documentation that I plan to store in docs/ - will update the documentation in this file to mention where the comprehensive documentation can be found.

29 ↗

(On Diff #357641)

Discussed offline - decided on creating an ILayer that the InstructionLayer and BlockLayer will inherit from. ILayer will define the interfaces to interact with a layer.

41 ↗

(On Diff #357641)

I tried using ConstString here, but I was running into issues because I don't believe there's a hash implementation for ConstString so it's unable to be the key type for an unordered_map. I'm considering using a map instead which should allow the use of ConstString, but at the cost of performance because lookups in these map are done quite often (every time two blocks are merged). What are your thoughts?

48–50 ↗

(On Diff #357641)

Working on comprehensive HTR documentation that I plan to store in docs/ - will update the documentation in this file to mention where the comprehensive documentation can be found.

73 ↗

(On Diff #357641)

Currently, the templates are not needed because we have a single metadata type, but I added the templates to make this design extensible to different use cases that may require different metadata.

Since we currently have just a single metadata type, I'll go ahead and remove the templates and if we ever need to add a new metadata type we can discuss how to extend the design.

143–144 ↗

(On Diff #357641)

I'm going to add getters to these classes so this should allow for all the friends to be removed

lldb/source/Commands/CommandObjectThread.cpp

2172 ↗

(On Diff #357641)

I agree that the allowing exporting to different formats is useful, so I think the trace export plug-in is a great idea.

Discussed with @wallace offline and we decided for this diff we are going to add a thread trace export command that has a --format option and in a future diff we could add implement the plug-in logic.

lldb/source/Target/TraceHTR.cpp

56 ↗

(On Diff #357641)

Correct, each unique address gets an entry in this map.

For the example you gave load_address_to_block_id would end up containing:

0x1000 -> 0
0x1004 -> 1
0x1008 -> 2
0x100c -> 3
0x2000 -> 4
0x2004 -> 5
0x2008 -> 6

The goal of this map is to assign each load address a new, unique id. The idea with assigning a new unique id is that this id could be smaller in size compared to a load address (ie 4 bytes versus 8 bytes) since the number of unique instructions in a trace is typically significantly smaller than the total number of instructions in a trace (<1% based on some testing I did) - this obviously would depend on the specific trace but the high level idea is there is potentially an opportunity to save space since it is very unlikely that any useful trace would have more than 2^32 - 1 unique instructions.

size_t is currently used as the type for the ids so this memory saving idea isn't implemented here, but wanted to get feedback on this idea.

For this diff, I'll go ahead and remove this map as a whole and just use the load addresses themselves as the unique id for a block, but I'd like to keep the idea I described above in mind for future work.

[clayborg]

lldb/include/lldb/Target/TraceHTR.h

41 ↗

(On Diff #357641)

The constant string pool uses llvm::StringMap which ends up using "uint32_t llvm::djbHash(StringRef)". That being said, I would try and use the llvm::DenseMap instead of std::unordered_map since we already wrote the needed hashing accessors for it (search for "template <> struct DenseMapInfo<lldb_private::ConstString>" in the ConstString.h file for details).

68 ↗

(On Diff #357641)

ah yes. Makes sense.

73 ↗

(On Diff #357641)

That sounds good to me

lldb/source/Commands/CommandObjectThread.cpp

2172 ↗

(On Diff #357641)

Sounds good!

lldb/source/Target/TraceHTR.cpp

56 ↗

(On Diff #357641)

Sounds good, thanks for the explanation.

[jj10306]

• Add HTR documentation to lldb/docs/htr.rst
• Change new command to thread trace export --format <format> --outfile <filename>
• Distinguish between the instruction layer and all other layers - add IHTRLayer interface that HTRInstructionLayer and HTRBlockLayer implement
• Remove unnecessary templates
• Add accessor methods to HTR classes and remove all uses of friend

[jj10306]

lldb/docs/htr.rst

2

@clayborg @wallace Is there a way to view the "rendered" rst to ensure the the format is as I intended and that the image links are working?

lldb/include/lldb/Target/Trace.h

65–68 ↗

(On Diff #359848)

Update docs - remove count and add export_format

[jj10306]

lldb/source/Target/TraceHTR.cpp

205–217 ↗

(On Diff #359848)

Any idea why the "Edit" I made above does not work?
I tried this first but after using lldb to understand why it wasn't working, it appeared that current_layer = new_block_layer wasn't properly updating the value stored in current_layer. I thought that using a reference to an abstract class as the type for current_layer would allow this variable to bind to any value that implements the interface, but after changing the code to only use concrete types (the non-edited version of this code), the code behaves as expected.

[wallace]

Much better! We are getting closer. There's documentation missing. Besides, you should use unique_ptrs as mentioned in the comments so that you prevent copying massively large objects. I also left some indications on how to deal with errors.

lldb/docs/htr.rst

2

TL;DR: just do the small fix I mention below

you can use http://rst.ninjs.org/ to check the rendering. According to it you need to make the small fix I mention below.

Regarding the image, well, probably you could build the documentation locally and see that everything is working. If you look at docs/CMakeLists.txt, you'll see that there's a target called lldb-cpp-doc, but you need to enable doxygen first.

However, some parts of the documentation are kept within the tree and not exposed in the lldb website. For example, if you look at docs/lldb-gdb-remote.txt, it's not shown anywhere in https://lldb.llvm.org/index.html. So if we keep this documentation internal, this file is okay as it is, as the reader can open the image manually if needed. Once all of tracing becomes more stable and with more features, we can start making documentation like this more visible in the website, but that won't happen soon.

43–46

you need some blank lines

lldb/include/lldb/Target/Trace.h

66–68 ↗

(On Diff #359848)

remove this and add an entry for export_format

lldb/include/lldb/Target/TraceHTR.h

1–9 ↗

(On Diff #359848)

26–36 ↗

(On Diff #359848)

leave spaces between functions for readability and add documentation for all the methods

45 ↗

(On Diff #359848)

add a period . after the parenthesis

50–54 ↗

(On Diff #359848)

spaces between methods and documentation

57–63 ↗

(On Diff #359848)

leave this comments here, but generally we try to make the documentation of the API methods more verbose than the private members, which are rarely seen

72 ↗

(On Diff #359848)

better have a constructor here that expects an ID, so that at any point in the life of the object, there's always a valid ID

99 ↗

(On Diff #359848)

Add a small line in the documentation summarizing what this is. The htr.rst file should be used for digging deeper into this structure

104–106 ↗

(On Diff #359848)

remove this, instead mention in the original function declaration that the implementation class can decide how to store or generate this data, as for instructions we want to do it lazily

107–113 ↗

(On Diff #359848)

documentation of non-override methods

116 ↗

(On Diff #359848)

mention here about the order of the trace. Are the instructions stored backwards or forwards chronologically?

124 ↗

(On Diff #359848)

pretty nice!

134 ↗

(On Diff #359848)

documentation

136–140 ↗

(On Diff #359848)

why do you need both?

170 ↗

(On Diff #359848)

Make this a std::unique_ptr<HTRInstructionLayer> so that you avoid making copies of it. You can use std::make_unique<HTRInstructionLayer>(constructor args...) to create a new instance.
Otherwise you are at the risk of creating copies, which would be super memory inefficient

172 ↗

(On Diff #359848)

Same here, you should use unique pointers. You could create typedef/using declarations to have shorter names HTRInstructionLayerUP and HTRBlockLayerUP. Also your variable should have the _up suffix, e.g. m_instruction_layer_up

lldb/include/lldb/lldb-enumerations.h

1148–1151 ↗

(On Diff #359848)

move this enum to Trace.h. to avoid exposing this too much.

Also remove the "unknown" format, as it's useless

I'm working on a way to create Trace Plugins, so that you could add "exporter" plugins without having to modify anything from lldb proper. That would be similar to TraceIntelPT, which is self-contained in its own folder

lldb/source/Commands/CommandObjectThread.cpp

2145–2151 ↗

(On Diff #359848)

as we are going to have exporter plugins, to simplify this code, just expect the "ctf" string here explicitly. Later I'll do the smart lookup

lldb/source/Target/TraceHTR.cpp

26 ↗

(On Diff #359848)

s/GetMostFrequentyly/GetMostFrequently

28–34 ↗

(On Diff #359848)

a possible future optimization could be to calculate this maximum number on the fly as the map is being generated

39–41 ↗

(On Diff #359848)

you have to explain somewhere how you identify functions: do you find the corresponding function of each instruction, or do you do it just for CALL instructions?

53 ↗

(On Diff #359848)

remove a llvm::ArrayRef<HTRBlockLayerUP>

53–57 ↗

(On Diff #359848)

as these layers could change because of merges and what not, better remove the consts out of these methods

57 ↗

(On Diff #359848)

return HTRInstructionLayer &

61–62 ↗

(On Diff #359848)

it might be better to use move semantics here, to avoid creating a copy inside m_block_layers. Something like this should be fine

67 ↗

(On Diff #359848)

it would be better if the layer id is set at construction time

71 ↗

(On Diff #359848)

consider moving the HTRBlock instead of copying

78 ↗

(On Diff #359848)

Use an ArrayRef, and remove the const from the return type

126 ↗

(On Diff #359848)

probably you don't want to get the ownership of the cursor, just request a lldb::TraceCursor & reference instead of the unique_ptr. You can use *cursor_up to get that reference

151 ↗

(On Diff #359848)

you need to enhance the Instruction object, to support errors. You can store the error string in it using a char * pointer from a ConstString. Errors are not frequent, so that should be fine. You need to display the errors in the export data as well, as hiding them could be misleading to the user

159 ↗

(On Diff #359848)

check here as well that the current position of the trace is not an error

If you need a trace with an error, try doing

trace load test/API/commands/trace/intelpt-trace-multi-file/multi-file-no-ld.json

e.g.

(lldb) trace load /data/users/wallace/llvm-sand/external/llvm-project/lldb/test/API/commands/trace/intelpt-trace-multi-file/multi-file-no-ld.json
(lldb) thread trace dump instructions -f -c 100
thread #1: tid = 815455

a.out`main + 15 at main.cpp:10
  [ 0] 0x000000000040066f    callq  0x400540                  ; symbol stub for: foo()
a.out`symbol stub for: foo()
  [ 1] 0x0000000000400540    jmpq   *0x200ae2(%rip)           ; _GLOBAL_OFFSET_TABLE_ + 40
  [ 2] 0x0000000000400546    pushq  $0x2
  [ 3] 0x000000000040054b    jmp    0x400510
a.out`(none)
  [ 4] 0x0000000000400510    pushq  0x200af2(%rip)            ; _GLOBAL_OFFSET_TABLE_ + 8
  [ 5] 0x0000000000400516    jmpq   *0x200af4(%rip)           ; _GLOBAL_OFFSET_TABLE_ + 16
  [ 6] 0x00007ffff7df1950    error: no memory mapped at this address
  ...missing instructions
a.out`main + 20 at main.cpp:10

206 ↗

(On Diff #359848)

remove this assignment, just use m_instruction_layer directly

207 ↗

(On Diff #359848)

you might need to cast *m_instruction_layer_up to ILayer &

[jj10306]

lldb/include/lldb/Target/TraceHTR.h

136–140 ↗

(On Diff #359848)

AppendBlockId is for when we just need to append a block id to the block id trace. This is needed when we encounter a block that we have previously encountered, so we only need to append its block id and not worry about creating a new block.
AddNewBlock is needed when a new block has been encountered. In this case, the new block needs to be added to m_block_defs and the its block id needs to be appended to the block id trace.

lldb/source/Commands/CommandObjectThread.cpp

2145–2151 ↗

(On Diff #359848)

Are you suggesting that, for the time being, we just check that option_arg is "ctf" and set m_trace_export_format to eTraceExportChromeTraceFormat if so and report an error otherwise?

lldb/source/Target/TraceHTR.cpp

151 ↗

(On Diff #359848)

What Instruction object are you referring to?
Given the way the InstructionLayer currently works, vector of load addresses and a map for metadata, how would you suggest incorporating the error information?
My first thought was to store a special value (such as 0) in the vector of load addresses for each error, but this seems a bit hacky and doesn't allow a way to map a specific error back to its error message.
What are your thoughts?

395 ↗

(On Diff #359848)

Is there a way to store uint64s in JSON? If not, what's the suggested way to handle overflow here?

[wallace]

lldb/include/lldb/Target/TraceHTR.h

136–140 ↗

(On Diff #359848)

ahh, then better rename them. AppendRepeatingBlockToEnd and AppendNewBlockToEnd might be better. You could omit the ToEnd suffix

lldb/source/Commands/CommandObjectThread.cpp

2145–2151 ↗

(On Diff #359848)

yes, just to simplify the code. This check will go away as soon as I implement the barebones for the TraceExporter plugins

lldb/source/Target/TraceHTR.cpp

151 ↗

(On Diff #359848)

If in CTR you can embed error messages, it would be nice to have that in the metadata. It's also valid to have an instruction address of 0 in the case of errors. However, you have end up having abnormal blocks like

insn1 insn2 error_kind1 insn1 insn2 error_kind2

so if you just look at the addresses, [insn1, insn2, 0] is a block that appears twice.

Now the question is: if your users will want to see the specific errors, then you'll have to handle it accordingly in the metadata. But if your users don't case what kind of errors are displayed in the chrome trace view, then replacing an error with address 0 makes sense. You could leave a TODO here in that case. Let's sync up offline anyway

395 ↗

(On Diff #359848)

no, only int64_t, that's the type you have to use. And you won't have an overflow, AFAIK OSs don't use the last bits of addresses, as they use them internally for other things.

[jj10306]

lldb/source/Target/TraceHTR.cpp

53–57 ↗

(On Diff #359848)

Layers are not mutated after being constructed by a pass, so there is currently no reason to expose mutable references to these structures.

151 ↗

(On Diff #359848)

Discussed offline - decided to replace errors with an address of 0 for the time being. If decoding errors are common/users want to know the specifics of the error, we can add logic to store the error's message in a future diff.

[jj10306]

Address comments:

• use unique_ptr to prevent unnecessary copying
• add support for trace decoding errors

[wallace]

So much better. There's an optimization that you can make when merging maps, and besides that you need a more comprehensive test.

lldb/include/lldb/Target/TraceHTR.h

66 ↗

(On Diff #360965)

just return a ConstString

210 ↗

(On Diff #360965)

you dont need this btw, as the parent's destructor is already virtual

272 ↗

(On Diff #360965)

As this is const, the only way to use this unordered_map is to do look ups, then let's better hide the implementation detail that is an unordered map and create this method instead

const HTRBlock &GetBlockById(size_t id);

that way we can later change unordered_map for anything else without affecting any callers

323 ↗

(On Diff #360965)

the constructor shouldn't print anything and it it doesn't look right for a TraceHTR object to own a stream It's not part of its state.

339 ↗

(On Diff #360965)

better return an llvm::Error that will contain the error message, if any. The CommandObject that invokes this method can then get the error and dump it if necessary. So, don't pass any streams here

lldb/include/lldb/lldb-enumerations.h

1147 ↗

(On Diff #360965)

revert this change to diminish the noise

lldb/include/lldb/lldb-forward.h

330–331 ↗

(On Diff #360965)

move this to the same file as HTR as we'll end up moving HTR to its own plugin folder

lldb/source/Target/TraceHTR.cpp

75 ↗

(On Diff #360965)

add an empty life before this

124 ↗

(On Diff #360965)

remove this

126 ↗

(On Diff #360965)

once you rebase with the current code, you might need to invoke

cursor.SetForwards(true) 
cursor.SeekToBegin(TraceCursor::SeekType::Set, 0)

131 ↗

(On Diff #360965)

calculate this outside of this function and reuse the variable

[wallace]

lldb/source/Target/TraceHTR.cpp

152 ↗

(On Diff #360965)

this Printf is too noisy. You don't really need that. Just remove it and instead of invoking cursor.GetError(), invoke cursor.IsError() after rebasing the code

160 ↗

(On Diff #360965)

valid_cursor is not a nice name, just call it no_more_data, end_of_trace, or something like that

164 ↗

(On Diff #360965)

just call IsError as you don't need the error message

164 ↗

(On Diff #360965)

i'm a little bit confused here, lines 165 -> 167 will only be execute if the current instruction is an error, whose load address is going to be 0, so you'll get an invalid function name. This should instead be

if(!end_of_trace && !cursor.IsError()) {
  m_instruction_layer_up->AddCallInstructionMetadata(
              current_instruction_load_address,
              function_name_from_load_address(cursor.GetLoadAddress()));
} else {
  m_instruction_layer_up->AddCallInstructionMetadata(
            current_instruction_load_address, llvm::None);
}

168 ↗

(On Diff #360965)

remove this

184–185 ↗

(On Diff #360965)

you could also just do

llvm::DenseMap<ConstString, size_t> func_calls = m1.m_func_calls;

if the object doesn't allow it, then it's fine

187–190 ↗

(On Diff #360965)

did you try just doing

func_calls[name] += num_calls;

std::map will create a zeroed value for a new key when using the [] operator, so I imagine DenseMap work the same way. Nevermind if that doesn't work.

197 ↗

(On Diff #360965)

remove this assert, the code wouldn't break if num_units is 0

204–205 ↗

(On Diff #360965)

this is very expensive. Let's suppose that num_units is N, then you'll invoke MergeMetadata N - 1 times, and each element of the first map will be copied N - 1 times, each one from the second map will be copied N - 2 times, etc. So you'll have N^2 copies, which is just too slow.

Instead, you have two options:

• when you merge A and B, you don't create a new map, you just copy the elements from B to A, effectively modifying A's map. That way after N merges, each element from each map will need to be copied only once. This might intuitively makes sense from an API standpoint, because when you merge blocks, you might expect the original blocks to go away
• remove the merge method that accepts only two blocks and do the merging here coping everything to the same single map

up to you

212–214 ↗

(On Diff #360965)

remove this comment

216 ↗

(On Diff #360965)

better create a new method ArePassesDone

223 ↗

(On Diff #360965)

also call the ArePassesDone method here

225–227 ↗

(On Diff #360965)

remove this

233 ↗

(On Diff #360965)

return an llvm::Error instead of receiving a Stream

233–234 ↗

(On Diff #360965)

remove the TraceExportFormat enum. You don't really need it because there's one single case for now

240–241 ↗

(On Diff #360965)

include the error code in the error message. See how other parts of the code emit a meaningful error message for this kind of calls

245 ↗

(On Diff #360965)

can you also show the actual error message from os?

253–257 ↗

(On Diff #360965)

remove

260 ↗

(On Diff #360965)

you don't need this

412 ↗

(On Diff #360965)

remove this comment

412–422 ↗

(On Diff #360965)

use int64_t just in case, as that's how it's defined

439–440 ↗

(On Diff #360965)

this comment doens't make sense, as you are instead passing display_name to the json object

lldb/test/API/commands/trace/TestTraceExport.py

61

Add a new test in which you run this algorithm on a program with a few levels of function calls, and check that the output trace makes sense. Don't check for individual load addresses, but instead check for the appearance of the methods and blocks that you expect.

[jj10306]

lldb/include/lldb/Target/TraceHTR.h

272 ↗

(On Diff #360965)

Makes sense. How should the case when an id that the layer doesn't contain is passed in? I would like to use llvm::Optional here but it's not possible to have an Optional reference (i.e. Optional<& const HTRBlock>). I was thinking about creating different methods:

bool ContainsBlock(size_t id) const for checking if the layer contains an ID
HTRBlock const & GetBlockById(size_t id) const for retrieving a reference to a block in the layer
but this still doesn't solve the issue of if a caller calls GetBlockId with an invalid ID.

Another option would be to change GetBlockId to return Optional<HTRBlock> instead of a reference, but this would result in an unnecessary copy, when all we really need is an const reference.

339 ↗

(On Diff #360965)

I based this method off of TraceCursor::DumpInstructions which takes in a Stream & to output its success/error messages to. This method (TraceHTR::Export) prints a message to the console on success (not only failure) so I'm not sure how the success message could be propagated back up to the caller. I agree that using llvm::Error here would make sense if we were only printing if an Error occurred, but since we print on success I'm not sure if we should use llvm::Error over passing the Stream.

lldb/source/Target/TraceHTR.cpp

152 ↗

(On Diff #360965)

Initially I wasn't planning on displaying the error, but then I was getting runtime errors because I wasn't doing anything with the error. As a result, I decided to display the error and looked at how TraceCursor::DumpInstructions does it: s << toString(std::move(err));.
I believe if an isError() method existed then I would not have this issue about not checking/using the error and I could just use the isError() method to check for the presence of an error without actually retrieving the error object.

197 ↗

(On Diff #360965)

If num_units is 0 then the loop body would never execute and thus merged_metadata would be None at the time of return. This would be problematic since we return *merged_metadata.

204–205 ↗

(On Diff #360965)

Ahh yep, I've been meaning to update this method to take the first approach you described.

233 ↗

(On Diff #360965)

See comment on this function's declaration in TraceHTR.h

439–440 ↗

(On Diff #360965)

I was trying to indicate that GetMostFrequentlyCalledFunction returns a std::string instead of ConstString because eventually the ConsString function name will need to be converted to std::string in order to be serialized, but I will remove this comment and just change the function to return ConstString and then do the conversion in the ternary that defines display_name.

lldb/test/API/commands/trace/TestTraceExport.py

61

Yes, this makes sense. Is the way to do this by loading the JSON file's contents into memory in the test and doing assertions on that structure?

[wallace]

lldb/include/lldb/Target/TraceHTR.h

272 ↗

(On Diff #360965)

Optional<const HTRBlock &> should work like a charm. You can't put the & before the const AFAIK. People normally read the & backwards as in "reference to <const HTRBlock>"

339 ↗

(On Diff #360965)

It's different, because DumpInstructions is supposed to dump information in the stream, but in this case Export is printing to a file. So what if someone wants to invoke Export but not from a command? e.g. from a python script. You are making this case a little bit more complicated.
You can just return llvm::success() and let the caller print anything to Stream if available. In any case, it's standard in lldb to not print anything if the operation is a success

lldb/source/Target/TraceHTR.cpp

152 ↗

(On Diff #360965)

yes my bad =P After rebasing you should be able to use IsError() :) Sorry for the hiccup

197 ↗

(On Diff #360965)

Ahh, true. Then also mention in the documentation that num_units must be >= 1, otherwise someone might think that could somehow get an empty HTRBlock ><

439–440 ↗

(On Diff #360965)

you shouldn't change a generic API just to ease a single instance of a usage. Better return a ConstString, or even better, a llvm::StringRef, which can point to anything. ConstString has a method to get a StringRef out of it. StringRef::str() gets you a std::string if you need it, or you can use StringRef::data() to get the const char *, which helps you avoid one copy.

lldb/test/API/commands/trace/TestTraceExport.py

61

yes, that should be fine. You can also precompile a non-trivial a.out file and include it here, if you want the code to be fully deterministic. If you make it non-trivial enough, we should be able to reuse for other intel pt tests as well

[jj10306]

lldb/include/lldb/Target/TraceHTR.h

272 ↗

(On Diff #360965)

I tried what you suggested and also just a reference (no const), but it none of them work - this is the error message:

llvm/include/llvm/ADT/Optional.h:281:5: error: 'getPointer' declared as a pointer to a reference of type 'lldb_
private::HTRBlock &'
  T *getPointer() { return &Storage.getValue(); }

A cursory search of the issue brought up many articles, here's one:
https://www.fluentcpp.com/2018/10/05/pros-cons-optional-references/

339 ↗

(On Diff #360965)

Ah I see, that makes sense. I'll switch it to use llvm::Error and not print anything in the case of success, because the success indication isn't particularly useful.

lldb/source/Target/TraceHTR.cpp

439–440 ↗

(On Diff #360965)

Will update that function to return a StringRef 🙂

[jj10306]

lldb/include/lldb/Target/TraceHTR.h

272 ↗

(On Diff #360965)

Discussed offline - decided to return HTRBlock * const with a nullptr indicating that the layer does not contain a bock with the specified block id.

lldb/source/Target/TraceHTR.cpp

160 ↗

(On Diff #360965)

I was trying to use "positive logic", otherwise using something like end_of_trace would require and negating every use of it and every time the Next() is called (i.e end_of_trace =!cursor->Next()).

This is obviously a very minor thing, but I think using a well named "positive logic" variable makes the code easier to read - thoughts on using a name like more_data_in_trace? It's definitely harder to come up with a well named positive logic variable so let me know if you have any better suggestions

245 ↗

(On Diff #360965)

I don't believe llvm::raw_fd_ostream stores the error message, only the error code.

[wallace]

lldb/source/Target/TraceHTR.cpp

160 ↗

(On Diff #360965)

more_data_in_trace is fine!

245 ↗

(On Diff #360965)

you can invoke os.error() and then convert that value to a string :)

[jj10306]

Rebase and address comments

[jj10306]

Looks like I pulled in some unwanted changes related to the traceinstruction dumper and tsc when I rebased - will resolve this issue before landing

[wallace]

Pretty good. Just some minor nits. Once you rebase on top of the trace exporter plugin patch, this should be good to go.

lldb/test/API/commands/trace/TestTraceExport.py

55–57

delete this. You can actually compile a main.cpp file as part of the test and trace it with intel pt, and then check its output. You don't need "trace save" to do that.

lldb/test/API/commands/trace/intelpt-trace/functions_example.cpp

1 ↗

(On Diff #361460)

rename this file to export_htr_input.cpp or something like that. Same for the a.out

26 ↗

(On Diff #361460)

given that we are going to add a binary and we don't want to do it often, add another function like

void iterative_handle_request_by_id(int id, int reps) {
  for (int i = 0; i < reps; i++) {
    if (i % 2 == 0)
      slow_handle_request(id);
    else
      fast_handle_request(id);
}

just to have someone interesting to test later. Then recompile your a.out

[jj10306]

Rebased (integrate with https://reviews.llvm.org/D106501#change-SoRRVpoqDNdx) and address comments

[wallace]

Nice! I'll land this for you

[wallace]

Landed as aad17c55a8116cd3831d4392d909139702019d65

[omjavaid]

In D105741#2910908, @wallace wrote:

Landed as aad17c55a8116cd3831d4392d909139702019d65

Temporarily reverted this change as it breaks LLDB build on 32 bit Arm/Linux bot:
https://lab.llvm.org/buildbot/#/builders/17/builds/9497

[teemperor]

lldb/source/Plugins/TraceExporter/ctf/CommandObjectThreadTraceExportCTF.cpp

78

This generates a compiler warning:

[3344/4085] Building CXX object tools/lldb/source/Plugins/TraceExporter/ctf/CMakeFiles/lldbPluginTraceExporterCTF.dir/CommandObjectThreadTraceExportCTF.cpp.o
/Users/teemperor/3llvm/llvm-project/lldb/source/Plugins/TraceExporter/ctf/CommandObjectThreadTraceExportCTF.cpp:79:82: warning: format specifies type 'unsigned long long' but the argument has type 'size_t' (aka 'unsigned long') [-Wformat]
        "Thread index %" PRIu64 " is out of range (valid values are 0 - %u).\n", tid,
                      ~~~~~~~~~                                                  ^~~

The variadic format methods are obsolete and you can just use llvm::formatv(...).str() until we have a type-safe replacement.

[wallace]

lldb/source/Plugins/TraceExporter/ctf/CommandObjectThreadTraceExportCTF.cpp

78

thanks for the suggestion. TIL :)
I'll make a quick fix for this

[vsk]

Hey @jj10306, thanks for working on this.

@wallace @clayborg -- It seems like there are a ton of logic changes introduced in this patch that are tested at too coarse a level. I'm not confident in the changes being made here. For example, there's a bunch of subtle work being done in BasicSuperBlockMerge, but only ~one opaque high-level check that attempts to validate any of the logic: self.assertTrue(num_units_by_layer[1] == 383). Where does 383 come from? How do we know that that's the right result? If there's a bug in BasicSuperBlockMerge, would the regression test just look like changing the magic 383 number?

I'm not really comfortable with this being checked in, and would suggest a revert until some more granular unit tests can be added to the patch. (Also paging @JDevlieghere in case he has thoughts on the testing.)

lldb/docs/htr.rst

27

Would be helpful to describe a brief feature roadmap here, explaining what debugger functionality can be built on top of this HTR concept.

lldb/source/Plugins/TraceExporter/common/TraceHTR.h

38

Why not move 'func_calls' instead of copying it?

[wallace]

Sure thing. Sorry for not being that thorough.

[foad]

lldb/docs/htr.rst

13

Typo "oad".

22

Stray "l" at end of line.

[jj10306]

In D105741#2920588, @vsk wrote:

Hey @jj10306, thanks for working on this.

@wallace @clayborg -- It seems like there are a ton of logic changes introduced in this patch that are tested at too coarse a level. I'm not confident in the changes being made here. For example, there's a bunch of subtle work being done in BasicSuperBlockMerge, but only ~one opaque high-level check that attempts to validate any of the logic: self.assertTrue(num_units_by_layer[1] == 383). Where does 383 come from? How do we know that that's the right result? If there's a bug in BasicSuperBlockMerge, would the regression test just look like changing the magic 383 number?

I'm not really comfortable with this being checked in, and would suggest a revert until some more granular unit tests can be added to the patch. (Also paging @JDevlieghere in case he has thoughts on the testing.)

Apologies for this - will submit a patch with more comprehensive tests and other minor fixes this week!

[jj10306]

A more comprehensive test for this logic was added in https://reviews.llvm.org/D107674

lldb/docs/htr.rst

+Hierarchical Trace Representation (HTR)
+======================================
+The humongous amount of data processor traces like the ones obtained with Intel PT contain is not digestible to humans in its raw form. Given this, it is useful to summarize these massive traces by extracting useful information. Hierarchical Trace Representation (HTR) is the way lldb represents a summarized trace internally. HTR efficiently stores trace data and allows the trace data to be transformed in a way akin to compiler passes.
+
+Concepts
+--------
+**Block:** One or more contiguous units of the trace. At minimum, the unit of a trace is the load address of an instruction.
+
+**Block Metadata:** Metadata associated with each *block*. For processor traces, some metadata examples are the number of instructions in the block or information on what functions are called in the block.
+
+**Layer:** The representation of trace data between passes. For Intel PT there are two types of layers:
+
+ **Instruction Layer:** Composed of the oad addresses of the instructions in the trace. In an effort to save space, 
+ metadata is only stored for instructions that are of interest, not every instruction in the trace. HTR contains a 
+ single instruction layer.
+
+ **Block Layer:** Composed of blocks - a block in *layer n* refers to a sequence of blocks in *layer n - 1*. A block in 
+ *layer 1* refers to a sequence of instructions in *layer 0* (the instruction layer). Metadata is stored for each block in 
+ a block layer. HTR contains one or more block layers.
+
+**Pass:** A transformation applied to a *layer* that generates a new *layer* that is a more summarized, consolidated representation of the trace data.
+A pass merges instructions/blocks based on its specific purpose - for example, a pass designed to summarize a processor trace by function calls would merge all the blocks of a function into a single block representing the entire function.l
+
+The image below illusrates the transformation of a trace's representation (HTR)
+
+.. image:: media/htr-example.png
+
+Passes
+------
+A *pass* is applied to a *layer* to extract useful information (summarization) and compress the trace representation into a new *layer*. The idea is to have a series of passes where each pass specializes in extracting certain information about the trace. Some examples of potential passes include: identifying functions, identifying loops, or a more general purpose such as identifying long sequences of instructions that are repeated (i.e. Basic Super Block). Below you will find a description of each pass currently implemented in lldb.
+
+**Basic Super Block Reduction**
+
+A “basic super block” is the longest sequence of blocks that always occur in the same order. (The concept is akin to “Basic Block'' in compiler theory, but refers to dynamic occurrences rather than CFG nodes).
+
+The image below shows the "basic super blocks" of the sequence. Each unique "basic super block" is marked with a different color
+
+.. image:: media/basic_super_block_pass.png
+
+*Procedure to find all super blocks:*
+
+- For each block, compute the number of distinct predecessor and successor blocks.
+
+ - **Predecessor** - the block that occurs directly before (to the left of) the current block
+ - **Successor** - the block that occurs directly after (to the right of) the current block
+
+- A block with more than one distinct successor is always the start of a super block, the super block will continue until the next block with more than one distinct predecessor or successor.

lldb/source/Plugins/TraceExporter/CMakeLists.txt

+add_subdirectory(common)
 add_subdirectory(ctf)

lldb/source/Plugins/TraceExporter/common/CMakeLists.txt

+add_lldb_library(lldbPluginTraceExporterCommon
+  TraceHTR.cpp
+
+  LINK_LIBS
+    lldbCore
+    lldbTarget
+  )

lldb/source/Plugins/TraceExporter/common/TraceHTR.h

+//===-- TraceHTR.h --------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache
+// License v2.0 with LLVM Exceptions.// See https://llvm.org/LICENSE.txt for
+// license information.// SPDX-License-Identifier: Apache-2.0 WITH
+// LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLDB_TARGET_TRACE_HTR_H
+#define LLDB_TARGET_TRACE_HTR_H
+
+#include "lldb/Target/Thread.h"
+#include "lldb/Target/Trace.h"
+
+#include <unordered_map>
+#include <unordered_set>
+
+namespace lldb_private {
+
+/// Metadata associated with an HTR block
+/// See lldb/docs/htr.rst for comprehensive HTR documentation
+class HTRBlockMetadata {
+public:
+  /// Constructor for a block's metadata.
+  ///
+  /// \param[in] first_instruction_load_address
+  ///     The load address of the block's first instruction.
+  ///
+  /// \param[in] num_instructions
+  ///     The total number of instructions in the block.
+  ///
+  /// \param[in] func_calls
+  ///     The map of a function name to the number of times it is called from
+  ///     the block.
+  HTRBlockMetadata(lldb::addr_t first_instruction_load_address,
+                   size_t num_instructions,
+                   llvm::DenseMap<ConstString, size_t> &func_calls)
+      : m_first_instruction_load_address(first_instruction_load_address),
+        m_num_instructions(num_instructions), m_func_calls(func_calls) {}
+
+  /// Merge two \a HTRBlockMetadata in place.
+  ///
+  /// \param[in][out] merged_metadata
+  ///     Metadata that metadata_to_merge will be merged into.
+  ///
+  /// \param[in] metadata_to_merge
+  ///     Metadata to merge into merged_metadata.
+  static void MergeMetadata(HTRBlockMetadata &merged_metadata,
+                            HTRBlockMetadata const &metadata_to_merge);
+  /// Get the number of instructions in the block.
+  ///
+  /// \return
+  ///     The number of instructions in the block.
+  size_t GetNumInstructions() const;
+
+  /// Get the name of the most frequently called function from the block.
+  ///
+  /// \return
+  ///     The name of the function that is called the most from this block or
+  ///     None if no function is called from this block.
+  llvm::Optional<llvm::StringRef> GetMostFrequentlyCalledFunction() const;
+
+  /// Get the load address of the first instruction in the block.
+  ///
+  /// \return
+  ///     The load address of the first instruction in the block.
+  lldb::addr_t GetFirstInstructionLoadAddress() const;
+
+  /// Get the function calls map for the block.
+  /// Function calls are identified in the instruction layer by finding 'call'
+  /// instructions and determining the function they are calling. As these
+  /// instructions are merged into blocks, we merge these different function
+  /// calls into a single map containing the function names to the number of
+  /// times it is called from this block.
+  ///
+  /// \return
+  ///     The mapping of function name to the number of times it is called from
+  ///     this block.
+  llvm::DenseMap<ConstString, size_t> const &GetFunctionCalls() const;
+
+private:
+  lldb::addr_t m_first_instruction_load_address;
+  size_t m_num_instructions;
+  llvm::DenseMap<ConstString, size_t> m_func_calls;
+};
+
+/// Block structure representing a sequence of trace "units" (ie instructions).
+/// Sequences of blocks are merged to create a new, single block
+/// See lldb/docs/htr.rst for comprehensive HTR documentation
+class HTRBlock {
+public:
+  /// Constructor for a block of an HTR layer.
+  ///
+  /// \param[in] offset
+  ///     The offset of the start of this block in the previous layer.
+  ///
+  /// \param[in] size
+  ///     Number of blocks/instructions that make up this block in the previous
+  ///     layer.
+  ///
+  /// \param[in] metadata
+  ///     General metadata for this block.
+  HTRBlock(size_t offset, size_t size, HTRBlockMetadata metadata)
+      : m_offset(offset), m_size(size), m_metadata(metadata) {}
+
+  /// Get the offset of the start of this block in the previous layer.
+  ///
+  /// \return
+  ///     The offset of the block.
+  size_t GetOffset() const;
+
+  /// Get the number of blocks/instructions that make up this block in the
+  /// previous layer.
+  ///
+  /// \return
+  ///     The size of the block.
+  size_t GetSize() const;
+
+  /// Get the metadata for this block.
+  ///
+  /// \return
+  ///     The metadata of the block.
+  HTRBlockMetadata const &GetMetadata() const;
+
+private:
+  /// Offset in the previous layer
+  size_t m_offset;
+  /// Number of blocks/instructions that make up this block in the previous
+  /// layer
+  size_t m_size;
+  /// General metadata for this block
+  HTRBlockMetadata m_metadata;
+};
+
+/// HTR layer interface
+/// See lldb/docs/htr.rst for comprehensive HTR documentation
+class IHTRLayer {
+public:
+  /// Construct new HTR layer.
+  //
+  /// \param[in] id
+  ///     The layer's id.
+  IHTRLayer(size_t id) : m_layer_id(id) {}
+
+  /// Get the ID of the layer.
+  ///
+  /// \return
+  ///     The layer ID of this layer.
+  size_t GetLayerId() const;
+
+  /// Get the metadata of a unit (instruction or block) in the layer.
+  ///
+  /// \param[in] index
+  ///     The position of the unit in the layer.
+  ///
+  /// \return
+  ///     The metadata of the unit in the layer.
+  virtual HTRBlockMetadata GetMetadataByIndex(size_t index) const = 0;
+
+  /// Get the total number of units (instruction or block) in this layer.
+  ///
+  /// \return
+  ///     The total number of units in the layer.
+  virtual size_t GetNumUnits() const = 0;
+
+  /// Creates a new block from the result of merging a contiguous sequence of
+  /// "units" (instructions or blocks depending on layer type) in this layer
+  /// This allows the implementation class to decide how to store/generate this
+  /// metadata. For example, in the case of the instruction layer we want to
+  /// lazily generate this metadata instead of storing it for each instruction.
+  ///
+  /// \param[in] start_unit_index
+  ///     The index of the first unit to be merged.
+  ///
+  /// \param[in] num_units
+  ///     The number of units to be merged. Must be >= 1, since merging 0 blocks
+  ///     does not make sense.
+  ///
+  /// \return
+  ///     A new block instance representing the merge of the specified units.
+  HTRBlock MergeUnits(size_t start_unit_index, size_t num_units);
+
+  virtual ~IHTRLayer() = default;
+
+protected:
+  /// ID of the layer.
+  size_t m_layer_id;
+};
+
+/// "Base" layer of HTR representing the dynamic instructions of the trace.
+/// See lldb/docs/htr.rst for comprehensive HTR documentation
+class HTRInstructionLayer : public IHTRLayer {
+public:
+  /// Construct new instruction layer.
+  //
+  /// \param[in] id
+  ///     The layer's id.
+  HTRInstructionLayer(size_t id) : IHTRLayer(id) {}
+
+  size_t GetNumUnits() const override;
+
+  HTRBlockMetadata GetMetadataByIndex(size_t index) const override;
+
+  /// Get the dynamic instruction trace.
+  ///
+  /// \return
+  ///     The dynamic instruction trace.
+  llvm::ArrayRef<lldb::addr_t> GetInstructionTrace() const;
+
+  /// Add metadata for a 'call' instruction of the trace.
+  ///
+  /// \param[in] load_addr
+  ///     The load address of the 'call' instruction.
+  ///
+  /// \param[in] func_name
+  ///     The name of the function the 'call' instruction is calling if it can
+  ///     be determined, None otherwise.
+  void AddCallInstructionMetadata(lldb::addr_t load_addr,
+                                  llvm::Optional<ConstString> func_name);
+
+  /// Append the load address of an instruction to the dynamic instruction
+  /// trace.
+  ///
+  /// \param[in] load_addr
+  ///     The load address of the instruction.
+  void AppendInstruction(lldb::addr_t load_addr);
+
+private:
+  // Dynamic instructions of trace are stored in chronological order.
+  std::vector<lldb::addr_t> m_instruction_trace;
+  // Only store metadata for instructions of interest (call instructions)
+  // If we stored metadata for each instruction this would be wasteful since
+  // most instructions don't contain useful metadata
+
+  // This map contains the load address of all the call instructions.
+  // load address maps to the name of the function it calls (None if function
+  // name can't be determined)
+  std::unordered_map<lldb::addr_t, llvm::Optional<ConstString>> m_call_isns;
+};
+
+/// HTR layer composed of blocks of the trace.
+/// See lldb/docs/htr.rst for comprehensive HTR documentation
+class HTRBlockLayer : public IHTRLayer {
+public:
+  /// Construct new block layer.
+  //
+  /// \param[in] id
+  ///     The layer's id.
+  HTRBlockLayer(size_t id) : IHTRLayer(id) {}
+
+  size_t GetNumUnits() const override;
+
+  HTRBlockMetadata GetMetadataByIndex(size_t index) const override;
+
+  /// Get an \a HTRBlock from its block id.
+  ///
+  /// \param[in] block_id
+  ///     The id of the block to retrieve.
+  ///
+  /// \return
+  ///     The \a HTRBlock with the specified id, nullptr if no there is no block
+  ///     in the layer with the specified block id.
+  HTRBlock const *GetBlockById(size_t block_id) const;
+
+  /// Get the block ID trace for this layer.
+  /// This block ID trace stores the block ID of each block that occured in the
+  /// trace and the block defs map maps block ID to the corresponding \a
+  /// HTRBlock.
+  ///
+  /// \return
+  ///     The block ID trace for this layer.
+  llvm::ArrayRef<size_t> GetBlockIdTrace() const;
+
+  /// Appends a new block to the layer.
+  ///
+  /// \param[in] block_id
+  ///     The block id of the new block.
+  ///
+  /// \param[in] block
+  ///     The new \a HTRBlock to be appended to the layer. This block is moved
+  ///     into the layer.
+  void AppendNewBlock(size_t block_id, HTRBlock &&block);
+
+  /// Appends a repeated block to the layer.
+  ///
+  /// \param[in] block_id
+  ///     The block id of the repeated block.
+  void AppendRepeatedBlock(size_t block_id);
+
+private:
+  /// Maps a unique Block ID to the corresponding HTRBlock
+  std::unordered_map<size_t, HTRBlock> m_block_defs;
+  /// Reduce memory footprint by just storing a trace of block IDs and use
+  /// m_block_defs to map a block_id to its corresponding HTRBlock
+  std::vector<size_t> m_block_id_trace;
+};
+
+typedef std::unique_ptr<lldb_private::HTRBlockLayer> HTRBlockLayerUP;
+typedef std::unique_ptr<lldb_private::HTRInstructionLayer>
+    HTRInstructionLayerUP;
+
+/// Top-level HTR class
+/// See lldb/docs/htr.rst for comprehensive HTR documentation
+class TraceHTR {
+
+public:
+  /// Constructor for a trace's HTR.
+  ///
+  /// \param[in] thread
+  ///     The thread the trace belongs to.
+  ///
+  /// \param[in] cursor
+  ///     The trace cursor that gives access to the trace's contents.
+  TraceHTR(Thread &thread, TraceCursor &cursor);
+
+  /// Executes passes on the HTR layers until no further
+  /// summarization/compression is achieved
+  void ExecutePasses();
+
+  /// Export HTR layers to the specified format and outfile.
+  ///
+  /// \param[in] outfile
+  ///     The file that the exported HTR data will be written to.
+  ///
+  /// \return
+  ///     Success if the export is successful, Error otherwise.
+  llvm::Error Export(std::string outfile);
+
+  /// Get the block layers of this HTR.
+  ///
+  /// \return
+  ///     The block layers of this HTR.
+  llvm::ArrayRef<HTRBlockLayerUP> GetBlockLayers() const;
+
+  /// Get the instruction layer of this HTR.
+  ///
+  /// \return
+  ///     The instruction layer of this HTR.
+  HTRInstructionLayer const &GetInstructionLayer() const;
+
+  /// Add a new block layer to this HTR.
+  ///
+  /// \param[in]
+  ///     The new block layer to be added.
+  void AddNewBlockLayer(HTRBlockLayerUP &&block_layer);
+
+private:
+  // There is a single instruction layer per HTR
+  HTRInstructionLayerUP m_instruction_layer_up;
+  // There are one or more block layers per HTR
+  std::vector<HTRBlockLayerUP> m_block_layer_ups;
+};
+
+// Serialization functions for exporting HTR to Chrome Trace Format
+llvm::json::Value toJSON(const TraceHTR &htr);
+llvm::json::Value toJSON(const HTRBlock &block);
+llvm::json::Value toJSON(const HTRBlockMetadata &metadata);
+
+/// The HTR passes are defined below:
+
+/// Creates a new layer by merging the "basic super blocks" in the current layer
+///
+/// A "basic super block" is the longest sequence of blocks that always occur in
+/// the same order. (The concept is akin to “Basic Block" in compiler theory,
+/// but refers to dynamic occurrences rather than CFG nodes)
+///
+/// Procedure to find all basic super blocks:
+//
+///   - For each block, compute the number of distinct predecessor and
+///   successor blocks.
+///       Predecessor - the block that occurs directly before (to the left of)
+///       the current block Successor  - the block that occurs directly after
+///       (to the right of) the current block
+///   - A block with more than one distinct successor is always the start of a
+///   super block, the super block will continue until the next block with
+///   more than one distinct predecessor or successor.
+///
+/// The implementation makes use of two terms - 'heads' and 'tails' known as
+/// the 'endpoints' of a basic super block:
+///   A 'head' is defined to be a block in the trace that doesn't have a
+///   unique predecessor
+///   A 'tail' is defined to be a block in the trace that doesn't have a
+///   unique successor
+///
+/// A basic super block is defined to be a sequence of blocks between two
+/// endpoints
+///
+/// A head represents the start of the next group, so the current group
+/// ends at the block preceding the head and the next group begins with
+/// this head block
+///
+/// A tail represents the end of the current group, so the current group
+/// ends with the tail block and the next group begins with the
+/// following block.
+///
+/// See lldb/docs/htr.rst for comprehensive HTR documentation
+///
+/// \param[in] layer
+///     The layer to execute the pass on.
+///
+/// \return
+///     A new layer instance representing the merge of blocks in the
+///     previous layer
+HTRBlockLayerUP BasicSuperBlockMerge(IHTRLayer &layer);
+
+} // namespace lldb_private
+
+#endif // LLDB_TARGET_TRACE_HTR_H

lldb/source/Plugins/TraceExporter/common/TraceHTR.cpp

+//===-- TraceHTR.cpp ------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "TraceHTR.h"
+
+#include "lldb/Symbol/Function.h"
+#include "lldb/Target/Process.h"
+#include "lldb/Target/Target.h"
+#include "llvm/Support/JSON.h"
+#include <sstream>
+#include <string>
+
+using namespace lldb_private;
+using namespace lldb;
+
+size_t HTRBlockMetadata::GetNumInstructions() const {
+  return m_num_instructions;
+}
+
+llvm::Optional<llvm::StringRef>
+HTRBlockMetadata::GetMostFrequentlyCalledFunction() const {
+  size_t max_ncalls = 0;
+  llvm::Optional<llvm::StringRef> max_name = llvm::None;
+  for (const auto &it : m_func_calls) {
+    ConstString name = it.first;
+    size_t ncalls = it.second;
+    if (ncalls > max_ncalls) {
+      max_ncalls = ncalls;
+      max_name = name.GetStringRef();
+    }
+  }
+  return max_name;
+}
+
+llvm::DenseMap<ConstString, size_t> const &
+HTRBlockMetadata::GetFunctionCalls() const {
+  return m_func_calls;
+}
+
+lldb::addr_t HTRBlockMetadata::GetFirstInstructionLoadAddress() const {
+  return m_first_instruction_load_address;
+}
+
+size_t HTRBlock::GetOffset() const { return m_offset; }
+
+size_t HTRBlock::GetSize() const { return m_size; }
+
+HTRBlockMetadata const &HTRBlock::GetMetadata() const { return m_metadata; }
+
+llvm::ArrayRef<HTRBlockLayerUP> TraceHTR::GetBlockLayers() const {
+  return m_block_layer_ups;
+}
+
+HTRInstructionLayer const &TraceHTR::GetInstructionLayer() const {
+  return *m_instruction_layer_up;
+}
+
+void TraceHTR::AddNewBlockLayer(HTRBlockLayerUP &&block_layer) {
+  m_block_layer_ups.emplace_back(std::move(block_layer));
+}
+
+size_t IHTRLayer::GetLayerId() const { return m_layer_id; }
+
+void HTRBlockLayer::AppendNewBlock(size_t block_id, HTRBlock &&block) {
+  m_block_id_trace.emplace_back(block_id);
+  m_block_defs.emplace(block_id, block);
+}
+
+void HTRBlockLayer::AppendRepeatedBlock(size_t block_id) {
+  m_block_id_trace.emplace_back(block_id);
+}
+
+llvm::ArrayRef<size_t> HTRInstructionLayer::GetInstructionTrace() const {
+  return m_instruction_trace;
+}
+
+void HTRInstructionLayer::AddCallInstructionMetadata(
+    lldb::addr_t load_addr, llvm::Optional<ConstString> func_name) {
+  m_call_isns.emplace(load_addr, func_name);
+}
+
+void HTRInstructionLayer::AppendInstruction(lldb::addr_t load_addr) {
+  m_instruction_trace.emplace_back(load_addr);
+}
+
+HTRBlock const *HTRBlockLayer::GetBlockById(size_t block_id) const {
+  auto block_it = m_block_defs.find(block_id);
+  if (block_it == m_block_defs.end())
+    return nullptr;
+  else
+    return &block_it->second;
+}
+
+llvm::ArrayRef<size_t> HTRBlockLayer::GetBlockIdTrace() const {
+  return m_block_id_trace;
+}
+
+size_t HTRBlockLayer::GetNumUnits() const { return m_block_id_trace.size(); }
+
+HTRBlockMetadata HTRInstructionLayer::GetMetadataByIndex(size_t index) const {
+  lldb::addr_t instruction_load_address = m_instruction_trace[index];
+  llvm::DenseMap<ConstString, size_t> func_calls;
+
+  auto func_name_it = m_call_isns.find(instruction_load_address);
+  if (func_name_it != m_call_isns.end()) {
+    if (llvm::Optional<ConstString> func_name = func_name_it->second) {
+      func_calls[*func_name] = 1;
+    }
+  }
+  return {instruction_load_address, 1, func_calls};
+}
+
+size_t HTRInstructionLayer::GetNumUnits() const {
+  return m_instruction_trace.size();
+}
+
+HTRBlockMetadata HTRBlockLayer::GetMetadataByIndex(size_t index) const {
+  size_t block_id = m_block_id_trace[index];
+  HTRBlock block = m_block_defs.find(block_id)->second;
+  return block.GetMetadata();
+}
+
+TraceHTR::TraceHTR(Thread &thread, TraceCursor &cursor)
+    : m_instruction_layer_up(std::make_unique<HTRInstructionLayer>(0)) {
+
+  // Move cursor to the first instruction in the trace
+  cursor.SetForwards(true);
+  cursor.Seek(0, TraceCursor::SeekType::Set);
+
+  Target &target = thread.GetProcess()->GetTarget();
+  auto function_name_from_load_address =
+      [&](lldb::addr_t load_address) -> llvm::Optional<ConstString> {
+    lldb_private::Address pc_addr;
+    SymbolContext sc;
+    if (target.ResolveLoadAddress(load_address, pc_addr) &&
+        pc_addr.CalculateSymbolContext(&sc))
+      return sc.GetFunctionName()
+                 ? llvm::Optional<ConstString>(sc.GetFunctionName())
+                 : llvm::None;
+    else
+      return llvm::None;
+  };
+
+  bool more_data_in_trace = true;
+  while (more_data_in_trace) {
+    if (cursor.IsError()) {
+      // Append a load address of 0 for all instructions that an error occured
+      // while decoding.
+      // TODO: Make distinction between errors by storing the error messages.
+      // Currently, all errors are treated the same.
+      m_instruction_layer_up->AppendInstruction(0);
+      more_data_in_trace = cursor.Next();
+    } else {
+      lldb::addr_t current_instruction_load_address = cursor.GetLoadAddress();
+      lldb::TraceInstructionControlFlowType current_instruction_type =
+          cursor.GetInstructionControlFlowType();
+
+      m_instruction_layer_up->AppendInstruction(
+          current_instruction_load_address);
+      more_data_in_trace = cursor.Next();
+      if (current_instruction_type &
+          lldb::eTraceInstructionControlFlowTypeCall) {
+        if (more_data_in_trace && !cursor.IsError()) {
+          m_instruction_layer_up->AddCallInstructionMetadata(
+              current_instruction_load_address,
+              function_name_from_load_address(cursor.GetLoadAddress()));
+        } else {
+          // Next instruction is not known - pass None to indicate the name
+          // of the function being called is not known
+          m_instruction_layer_up->AddCallInstructionMetadata(
+              current_instruction_load_address, llvm::None);
+        }
+      }
+    }
+  }
+}
+
+void HTRBlockMetadata::MergeMetadata(
+    HTRBlockMetadata &merged_metadata,
+    HTRBlockMetadata const &metadata_to_merge) {
+  merged_metadata.m_num_instructions += metadata_to_merge.m_num_instructions;
+  for (const auto &it : metadata_to_merge.m_func_calls) {
+    ConstString name = it.first;
+    size_t num_calls = it.second;
+    merged_metadata.m_func_calls[name] += num_calls;
+  }
+}
+
+HTRBlock IHTRLayer::MergeUnits(size_t start_unit_index, size_t num_units) {
+  // TODO: make this function take `end_unit_index` as a parameter instead of
+  // unit and merge the range [start_unit_indx, end_unit_index] inclusive.
+  HTRBlockMetadata merged_metadata = GetMetadataByIndex(start_unit_index);
+  for (size_t i = start_unit_index + 1; i < start_unit_index + num_units; i++) {
+    // merge the new metadata into merged_metadata
+    HTRBlockMetadata::MergeMetadata(merged_metadata, GetMetadataByIndex(i));
+  }
+  return {start_unit_index, num_units, merged_metadata};
+}
+
+void TraceHTR::ExecutePasses() {
+  auto are_passes_done = [](IHTRLayer &l1, IHTRLayer &l2) {
+    return l1.GetNumUnits() == l2.GetNumUnits();
+  };
+  HTRBlockLayerUP current_block_layer_up =
+      BasicSuperBlockMerge(*m_instruction_layer_up);
+  HTRBlockLayer &current_block_layer = *current_block_layer_up;
+  if (are_passes_done(*m_instruction_layer_up, *current_block_layer_up))
+    return;
+
+  AddNewBlockLayer(std::move(current_block_layer_up));
+  while (true) {
+    HTRBlockLayerUP new_block_layer_up =
+        BasicSuperBlockMerge(current_block_layer);
+    if (are_passes_done(current_block_layer, *new_block_layer_up))
+      return;
+
+    current_block_layer = *new_block_layer_up;
+    AddNewBlockLayer(std::move(new_block_layer_up));
+  }
+}
+
+llvm::Error TraceHTR::Export(std::string outfile) {
+  std::error_code ec;
+  llvm::raw_fd_ostream os(outfile, ec, llvm::sys::fs::OF_Text);
+  if (ec) {
+    return llvm::make_error<llvm::StringError>(
+        "unable to open destination file: " + outfile, os.error());
+  } else {
+    os << toJSON(*this);
+    os.close();
+    if (os.has_error()) {
+      return llvm::make_error<llvm::StringError>(
+          "unable to write to destination file: " + outfile, os.error());
+    }
+  }
+  return llvm::Error::success();
+}
+
+HTRBlockLayerUP lldb_private::BasicSuperBlockMerge(IHTRLayer &layer) {
+  std::unique_ptr<HTRBlockLayer> new_block_layer =
+      std::make_unique<HTRBlockLayer>(layer.GetLayerId() + 1);
+
+  if (layer.GetNumUnits()) {
+    // Future Improvement: split this into two functions - one for finding heads
+    // and tails, one for merging/creating the next layer A 'head' is defined to
+    // be a block whose occurrences in the trace do not have a unique preceding
+    // block.
+    std::unordered_set<size_t> heads;
+
+    // The load address of the first instruction of a block is the unique ID for
+    // that block (i.e. blocks with the same first instruction load address are
+    // the same block)
+
+    // Future Improvement: no need to store all its preceding block ids, all we
+    // care about is that there is more than one preceding block id, so an enum
+    // could be used
+    std::unordered_map<lldb::addr_t, std::unordered_set<lldb::addr_t>> head_map;
+    lldb::addr_t prev_id =
+        layer.GetMetadataByIndex(0).GetFirstInstructionLoadAddress();
+    size_t num_units = layer.GetNumUnits();
+    // This excludes the first unit since it has no previous unit
+    for (size_t i = 1; i < num_units; i++) {
+      lldb::addr_t current_id =
+          layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress();
+      head_map[current_id].insert(prev_id);
+      prev_id = current_id;
+    }
+    for (const auto &it : head_map) {
+      // ID of 0 represents an error - errors can't be heads or tails
+      lldb::addr_t id = it.first;
+      const std::unordered_set<lldb::addr_t> predecessor_set = it.second;
+      if (id && predecessor_set.size() > 1)
+        heads.insert(id);
+    }
+
+    // Future Improvement: identify heads and tails in the same loop
+    // A 'tail' is defined to be a block whose occurrences in the trace do
+    // not have a unique succeeding block.
+    std::unordered_set<lldb::addr_t> tails;
+    std::unordered_map<lldb::addr_t, std::unordered_set<lldb::addr_t>> tail_map;
+
+    // This excludes the last unit since it has no next unit
+    for (size_t i = 0; i < num_units - 1; i++) {
+      lldb::addr_t current_id =
+          layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress();
+      lldb::addr_t next_id =
+          layer.GetMetadataByIndex(i + 1).GetFirstInstructionLoadAddress();
+      tail_map[current_id].insert(next_id);
+    }
+
+    // Mark last block as tail so the algorithm stops gracefully
+    lldb::addr_t last_id = layer.GetMetadataByIndex(num_units - 1)
+                               .GetFirstInstructionLoadAddress();
+    tails.insert(last_id);
+    for (const auto &it : tail_map) {
+      lldb::addr_t id = it.first;
+      const std::unordered_set<lldb::addr_t> successor_set = it.second;
+      // ID of 0 represents an error - errors can't be heads or tails
+      if (id && successor_set.size() > 1)
+        tails.insert(id);
+    }
+
+    // Need to keep track of size of string since things we push are variable
+    // length
+    size_t superblock_size = 0;
+    // Each super block always has the same first unit (we call this the
+    // super block head) This gurantee allows us to use the super block head as
+    // the unique key mapping to the super block it begins
+    llvm::Optional<size_t> superblock_head = llvm::None;
+    auto construct_next_layer = [&](size_t merge_start, size_t n) -> void {
+      if (!superblock_head)
+        return;
+      if (new_block_layer->GetBlockById(*superblock_head)) {
+        new_block_layer->AppendRepeatedBlock(*superblock_head);
+      } else {
+        HTRBlock new_block = layer.MergeUnits(merge_start, n);
+        new_block_layer->AppendNewBlock(*superblock_head, std::move(new_block));
+      }
+    };
+
+    for (size_t i = 0; i < num_units; i++) {
+      lldb::addr_t unit_id =
+          layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress();
+      auto isHead = heads.count(unit_id) > 0;
+      auto isTail = tails.count(unit_id) > 0;
+
+      if (isHead && isTail) {
+        // Head logic
+        if (superblock_size) { // this handles (tail, head) adjacency -
+                               // otherwise an empty
+                               // block is created
+          // End previous super block
+          construct_next_layer(i - superblock_size, superblock_size);
+        }
+        // Current id is first in next super block since it's a head
+        superblock_head = unit_id;
+        superblock_size = 1;
+
+        // Tail logic
+        construct_next_layer(i - superblock_size + 1, superblock_size);
+        // Reset the block_head since the prev super block has come to and end
+        superblock_head = llvm::None;
+        superblock_size = 0;
+      } else if (isHead) {
+        if (superblock_size) { // this handles (tail, head) adjacency -
+                               // otherwise an empty
+                               // block is created
+          // End previous super block
+          construct_next_layer(i - superblock_size, superblock_size);
+        }
+        // Current id is first in next super block since it's a head
+        superblock_head = unit_id;
+        superblock_size = 1;
+      } else if (isTail) {
+        if (!superblock_head)
+          superblock_head = unit_id;
+        superblock_size++;
+
+        // End previous super block
+        construct_next_layer(i - superblock_size + 1, superblock_size);
+        // Reset the block_head since the prev super block has come to and end
+        superblock_head = llvm::None;
+        superblock_size = 0;
+      } else {
+        if (!superblock_head)
+          superblock_head = unit_id;
+        superblock_size++;
+      }
+    }
+  }
+  return new_block_layer;
+}
+
+llvm::json::Value lldb_private::toJSON(const TraceHTR &htr) {
+  std::vector<llvm::json::Value> layers_as_json;
+  for (size_t i = 0; i < htr.GetInstructionLayer().GetInstructionTrace().size();
+       i++) {
+    size_t layer_id = htr.GetInstructionLayer().GetLayerId();
+    HTRBlockMetadata metadata = htr.GetInstructionLayer().GetMetadataByIndex(i);
+    lldb::addr_t load_address = metadata.GetFirstInstructionLoadAddress();
+
+    std::string display_name;
+
+    std::stringstream stream;
+    stream << "0x" << std::hex << load_address;
+    std::string load_address_hex_string(stream.str());
+    display_name.assign(load_address_hex_string);
+
+    layers_as_json.emplace_back(llvm::json::Object{
+        {"name", display_name},
+        {"ph", "B"},
+        {"ts", (int64_t)i},
+
+        {"pid", (int64_t)layer_id},
+        {"tid", (int64_t)layer_id},
+    });
+
+    layers_as_json.emplace_back(llvm::json::Object{
+        {"ph", "E"},
+        {"ts", (int64_t)i + 1},
+        {"pid", (int64_t)layer_id},
+        {"tid", (int64_t)layer_id},
+    });
+  }
+
+  for (const auto &layer : htr.GetBlockLayers()) {
+    size_t start_ts = 0;
+    std::vector<size_t> block_id_trace = layer->GetBlockIdTrace();
+    for (size_t i = 0; i < block_id_trace.size(); i++) {
+      size_t id = block_id_trace[i];
+      // Guranteed that this ID is valid, so safe to dereference here.
+      HTRBlock block = *layer->GetBlockById(id);
+      llvm::json::Value block_json = toJSON(block);
+      size_t layer_id = layer->GetLayerId();
+
+      HTRBlockMetadata metadata = block.GetMetadata();
+
+      size_t end_ts = start_ts + metadata.GetNumInstructions();
+
+      llvm::Optional<llvm::StringRef> most_freq_func =
+          metadata.GetMostFrequentlyCalledFunction();
+      std::stringstream stream;
+      stream << "0x" << std::hex << metadata.GetFirstInstructionLoadAddress();
+      std::string offset_hex_string(stream.str());
+      std::string display_name =
+          most_freq_func ? offset_hex_string + ": " + most_freq_func->str()
+                         : offset_hex_string;
+
+      layers_as_json.emplace_back(llvm::json::Object{
+          {"name", display_name},
+          {"ph", "B"},
+          {"ts", (int64_t)start_ts},
+          {"pid", (int64_t)layer_id},
+          {"tid", (int64_t)layer_id},
+      });
+
+      layers_as_json.emplace_back(llvm::json::Object{
+          {"ph", "E"},
+          {"ts", (int64_t)end_ts},
+          {"pid", (int64_t)layer_id},
+          {"tid", (int64_t)layer_id},
+          {"args", block_json},
+      });
+      start_ts = end_ts;
+    }
+  }
+  return layers_as_json;
+}
+
+llvm::json::Value lldb_private::toJSON(const HTRBlock &block) {
+  return llvm::json::Value(
+      llvm::json::Object{{"Metadata", block.GetMetadata()}});
+}
+
+llvm::json::Value lldb_private::toJSON(const HTRBlockMetadata &metadata) {
+  std::vector<llvm::json::Value> function_calls;
+  for (const auto &it : metadata.GetFunctionCalls()) {
+    ConstString name = it.first;
+    size_t n_calls = it.second;
+    function_calls.emplace_back(llvm::formatv("({0}: {1})", name, n_calls));
+  }
+
+  return llvm::json::Value(llvm::json::Object{
+      {"Number of Instructions", (ssize_t)metadata.GetNumInstructions()},
+      {"Functions", function_calls}});
+}

lldb/source/Plugins/TraceExporter/ctf/CMakeLists.txt

 lldb_tablegen(TraceExporterCTFCommandOptions.inc -gen-lldb-option-defs
   SOURCE TraceExporterCTFOptions.td
   TARGET TraceExporterCTFOptionsGen)
 
 add_lldb_library(lldbPluginTraceExporterCTF PLUGIN
 CommandObjectThreadTraceExportCTF.cpp
   TraceExporterCTF.cpp
 
   LINK_LIBS
     lldbCore
     lldbSymbol
     lldbTarget
+    lldbPluginTraceExporterCommon
   LINK_COMPONENTS
     Support
   )
 
 add_dependencies(lldbPluginTraceExporterCTF TraceExporterCTFOptionsGen)

lldb/source/Plugins/TraceExporter/ctf/CommandObjectThreadTraceExportCTF.h

public:
     Status SetOptionValue(uint32_t option_idx, llvm::StringRef option_arg,
                           ExecutionContext *execution_context) override;
 
     void OptionParsingStarting(ExecutionContext *execution_context) override;
 
     llvm::ArrayRef<OptionDefinition> GetDefinitions() override;
 
     llvm::Optional<size_t> m_thread_index;
+    std::string m_file;
   };
 
   CommandObjectThreadTraceExportCTF(CommandInterpreter &interpreter)
       : CommandObjectParsed(
             interpreter, "thread trace export ctf",
             "Export a given thread's trace to Chrome Trace Format",
             "thread trace export ctf [<ctf-options>]",
             lldb::eCommandRequiresProcess | lldb::eCommandTryTargetAPILock |
                 lldb::eCommandProcessMustBeLaunched |
-                lldb::eCommandProcessMustBePaused),
+                lldb::eCommandProcessMustBePaused |
+                lldb::eCommandProcessMustBeTraced),
         m_options() {}
 
   Options *GetOptions() override { return &m_options; }
 
 protected:
   bool DoExecute(Args &command, CommandReturnObject &result) override;
 
   CommandOptions m_options;
 };
 
 } // namespace ctf
 } // namespace lldb_private
 
 #endif // LLDB_SOURCE_PLUGINS_TRACE_INTEL_PT_COMMANDOBJECTTHREADTRACEEXPORTCTF_H

lldb/source/Plugins/TraceExporter/ctf/CommandObjectThreadTraceExportCTF.cpp

 //===-- CommandObjectThreadTraceExportCTF.cpp -----------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "CommandObjectThreadTraceExportCTF.h"
 
+#include "../common/TraceHTR.h"
 #include "lldb/Host/OptionParser.h"
+#include "lldb/Target/Process.h"
+#include "lldb/Target/Trace.h"
 
 using namespace lldb;
 using namespace lldb_private;
 using namespace lldb_private::ctf;
 using namespace llvm;
 
 // CommandObjectThreadTraceExportCTF
 
 #define LLDB_OPTIONS_thread_trace_export_ctf
 #include "TraceExporterCTFCommandOptions.inc"
 
 Status CommandObjectThreadTraceExportCTF::CommandOptions::SetOptionValue(
     uint32_t option_idx, llvm::StringRef option_arg,
     ExecutionContext *execution_context) {
   Status error;
   const int short_option = m_getopt_table[option_idx].val;
 
   switch (short_option) {
+  case 'f': {
+    m_file.assign(std::string(option_arg));
+    break;
+  }
   case 't': {
     int64_t thread_index;
     if (option_arg.empty() || option_arg.getAsInteger(0, thread_index) ||
         thread_index < 0)
       error.SetErrorStringWithFormat("invalid integer value for option '%s'",
                                      option_arg.str().c_str());
     else
       m_thread_index = thread_index;
     break;
   }
   default:
     llvm_unreachable("Unimplemented option");
   }
   return error;
 }
 
 void CommandObjectThreadTraceExportCTF::CommandOptions::OptionParsingStarting(
     ExecutionContext *execution_context) {
+  m_file.clear();
   m_thread_index = None;
 }
 
 llvm::ArrayRef<OptionDefinition>
 CommandObjectThreadTraceExportCTF::CommandOptions::GetDefinitions() {
   return llvm::makeArrayRef(g_thread_trace_export_ctf_options);
 }
 
 bool CommandObjectThreadTraceExportCTF::DoExecute(Args &command,
                                                   CommandReturnObject &result) {
-  Stream &s = result.GetOutputStream();
-  // TODO: create an actual instance of the exporter and invoke it
-  if (m_options.m_thread_index)
-    s.Printf("got thread index %d\n", (int)m_options.m_thread_index.getValue());
-  else
-    s.Printf("didn't get a thread index\n");
-
-  return result.Succeeded();
+  const TraceSP &trace_sp = m_exe_ctx.GetTargetSP()->GetTrace();
+  Process *process = m_exe_ctx.GetProcessPtr();
+  Thread *thread = m_options.m_thread_index
+                       ? process->GetThreadList()
+                             .FindThreadByIndexID(*m_options.m_thread_index)
+                             .get()
+                       : GetDefaultThread();
+
+  if (thread == nullptr) {
+    const uint32_t num_threads = process->GetThreadList().GetSize();
+    size_t tid = m_options.m_thread_index ? *m_options.m_thread_index
+                                          : LLDB_INVALID_THREAD_ID;
+    result.AppendErrorWithFormat(
+        "Thread index %lu is out of range (valid values are 0 - %u).\n", tid,
+        num_threads);
+    return false;
+  } else {
+    TraceHTR htr(*thread, *trace_sp->GetCursor(*thread));
+    htr.ExecutePasses();
+    if (llvm::Error err = htr.Export(m_options.m_file)) {
+      result.AppendErrorWithFormat("%s\n", toString(std::move(err)).c_str());
+      return false;
+    } else {
+      return true;
+    }
+  }
 }

lldb/source/Plugins/TraceExporter/ctf/TraceExporterCTFOptions.td

 include "../../../../source/Commands/OptionsBase.td"
 
 let Command = "thread trace export ctf" in {
   def thread_trace_export_ctf: Option<"tid", "t">,
     Group<1>,
     Arg<"ThreadIndex">,
     Desc<"Export the trace for the specified thread index. Otherwise, the "
          "currently selected thread will be used.">;
+  def thread_trace_export_file: Option<"file", "f">, Required,
+    Group<1>,
+    Arg<"Filename">,
+    Desc<"Path of the file to export the trace data">;
 }

lldb/test/API/commands/trace/TestTraceExport.py

+from collections import defaultdict
+import lldb
+import json
+from intelpt_testcase import *
+from lldbsuite.test.lldbtest import *
+from lldbsuite.test import lldbutil
+from lldbsuite.test.decorators import *
+import os
+
+class TestTraceExport(TraceIntelPTTestCaseBase):
+
+    mydir = TestBase.compute_mydir(__file__)
+
+    def testErrorMessages(self):
+        ctf_test_file = self.getBuildArtifact("ctf-test.json")
+        # We first check the output when there are no targets
+        self.expect(f"thread trace export ctf --file {ctf_test_file}",
+            substrs=["error: invalid target, create a target using the 'target create' command"],
+            error=True)
+
+        # We now check the output when there's a non-running target
+        self.expect("target create " +
+            os.path.join(self.getSourceDir(), "intelpt-trace", "a.out"))
+
+        self.expect(f"thread trace export ctf --file {ctf_test_file}",
+            substrs=["error: invalid process"],
+            error=True)
+
+        # Now we check the output when there's a running target without a trace
+        self.expect("b main")
+        self.expect("run")
+
+        self.expect(f"thread trace export ctf --file {ctf_test_file}",
+            substrs=["error: Process is not being traced"],
+            error=True)
+
+    def testExportCreatesFile(self):
+        self.expect("trace load -v " +
+            os.path.join(self.getSourceDir(), "intelpt-trace", "trace.json"),
+            substrs=["intel-pt"])
+
+        ctf_test_file = self.getBuildArtifact("ctf-test.json")
+
+        if os.path.exists(ctf_test_file):
+            remove_file(ctf_test_file)
+        self.expect(f"thread trace export ctf --file {ctf_test_file}")
+        self.assertTrue(os.path.exists(ctf_test_file))
+
+
+    def testHtrBasicSuperBlockPass(self):
+        '''
+        Test the BasicSuperBlock pass of HTR
+
+        TODO: Once the "trace save" command is implemented, gather Intel PT
+        trace of this program and load it like the other tests instead of
+        manually executing the commands to trace the program.
+        '''
+        self.expect(f"target create {os.path.join(self.getSourceDir(), 'intelpt-trace', 'export_ctf_test_program.out')}")
+        self.expect("b main")
+        self.expect("r")
+        self.expect("b exit")
+        self.expect("thread trace start")
+        self.expect("c")
+
+        ctf_test_file = self.getBuildArtifact("ctf-test.json")
+
+        if os.path.exists(ctf_test_file):
+            remove_file(ctf_test_file)
+        self.expect(f"thread trace export ctf --file {ctf_test_file}")
+        self.assertTrue(os.path.exists(ctf_test_file))
+
+
+        with open(ctf_test_file) as f:
+            data = json.load(f)
+
+        num_units_by_layer = defaultdict(int)
+        index_of_first_layer_1_block = None
+        for i, event in enumerate(data):
+            layer_id = event.get('pid')
+            if layer_id == 1 and index_of_first_layer_1_block is None:
+                index_of_first_layer_1_block = i
+            if layer_id is not None and event['ph'] == 'B':
+                num_units_by_layer[layer_id] += 1
+
+        # Check that there are two layers
+        self.assertTrue(0 in num_units_by_layer and 1 in num_units_by_layer)
+        # Check that each layer has the correct total number of blocks
+        self.assertTrue(num_units_by_layer[0] == 1630)
+        self.assertTrue(num_units_by_layer[1] == 383)
+
+
+        expected_block_names = [
+                '0x4005f0',
+                '0x4005fe',
+                '0x400606: iterative_handle_request_by_id(int, int)',
+                '0x4005a7',
+                '0x4005af',
+                '0x4005b9: fast_handle_request(int)',
+                '0x4005d5: log_response(int)',
+        ]
+        # There are two events per block, a beginning and an end. This means we must increment data_index by 2, so we only encounter the beginning event of each block.
+        data_index = index_of_first_layer_1_block
+        expected_index = 0
+        while expected_index < len(expected_block_names):
+            self.assertTrue(data[data_index]['name'] == expected_block_names[expected_index])
+            self.assertTrue(data[data_index]['name'] == expected_block_names[expected_index])
+            data_index += 2
+            expected_index += 1
+

lldb/test/API/commands/trace/intelpt-trace/export_ctf_test_program.cpp

+void log_response(int reqest_response) {
+  // fake logging logic
+}
+
+int slow_handle_request(int id) {
+  // "slow" request handling logic
+  for (int i = 0; i < 10; i++)
+    id += 2;
+  return id;
+}
+
+int fast_handle_request(int id) {
+  // "fast" request handling logic
+  return id + 2;
+}
+
+void iterative_handle_request_by_id(int id, int reps) {
+  int response;
+  for (int i = 0; i < reps; i++) {
+    if (i % 2 == 0)
+      response = fast_handle_request(id);
+    else
+      response = slow_handle_request(id);
+    log_response(response);
+  }
+}
+
+int main() {
+  int n_requests = 10;
+  for (int id = 0; id < n_requests; id++) {
+    iterative_handle_request_by_id(id, 3);
+  }
+  return 0;
+}