[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

pass the map by reference

42–68

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

73

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

[wallace]

lldb/include/lldb/Target/TraceHTR.h

29

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

See my comment above, this is too memory expensive

[jj10306]

lldb/include/lldb/Target/TraceHTR.h

3

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

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

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

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

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

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

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

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

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

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

ah yes. Makes sense.

73

That sounds good to me

lldb/source/Commands/CommandObjectThread.cpp

2172

Sounds good!

lldb/source/Target/TraceHTR.cpp

56

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

1 ↗

(On Diff #359848)

@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

Update docs - remove count and add export_format

[jj10306]

lldb/source/Target/TraceHTR.cpp

206–218

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

1 ↗

(On Diff #359848)

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.

42–45 ↗

(On Diff #359848)

you need some blank lines

lldb/include/lldb/Target/Trace.h

66–68

remove this and add an entry for export_format

lldb/include/lldb/Target/TraceHTR.h

2–10

27–37

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

46

add a period . after the parenthesis

51–55

spaces between methods and documentation

58–64

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

73

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

100

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

105–107

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

108–114

documentation of non-override methods

117

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

125

pretty nice!

135

documentation

137–141

why do you need both?

171

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

173

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

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

27

s/GetMostFrequentyly/GetMostFrequently

29–35

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

40–42

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?

54

remove a llvm::ArrayRef<HTRBlockLayerUP>

54–58

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

58

return HTRInstructionLayer &

62–63

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

68

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

72

consider moving the HTRBlock instead of copying

79

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

127

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

152

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

160

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

207

remove this assignment, just use m_instruction_layer directly

208

you might need to cast *m_instruction_layer_up to ILayer &

[jj10306]

lldb/include/lldb/Target/TraceHTR.h

137–141

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

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

152

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?

396

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

137–141

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

lldb/source/Commands/CommandObjectThread.cpp

2145–2151

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

152

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

396

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

54–58

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

152

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

67

just return a ConstString

211

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

273

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

324

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.

340

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

76

add an empty life before this

125

remove this

127

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

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

132

calculate this outside of this function and reuse the variable

[wallace]

lldb/source/Target/TraceHTR.cpp

153

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

161

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

165

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

165

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);
}

169

remove this

185–186

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

188–191

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.

198

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

205–206

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

213–215

remove this comment

217

better create a new method ArePassesDone

224

also call the ArePassesDone method here

226–228

remove this

234

return an llvm::Error instead of receiving a Stream

234–235

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

241–242

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

246

can you also show the actual error message from os?

254–258

remove

261

you don't need this

413

remove this comment

413–423

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

440–441

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

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

60 ↗

(On Diff #360965)

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

273

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.

340

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

153

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.

198

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.

205–206

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

234

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

440–441

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

60 ↗

(On Diff #360965)

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

273

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

340

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

153

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

198

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

440–441

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

60 ↗

(On Diff #360965)

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

273

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/

340

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

440–441

Will update that function to return a StringRef 🙂

[jj10306]

lldb/include/lldb/Target/TraceHTR.h

273

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

161

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

246

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

[wallace]

lldb/source/Target/TraceHTR.cpp

161

more_data_in_trace is fine!

246

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

54–56 ↗

(On Diff #361460)

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 ↗

(On Diff #362455)

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 ↗

(On Diff #362455)

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 ↗

(On Diff #362455)

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 ↗

(On Diff #362455)

Why not move 'func_calls' instead of copying it?

[wallace]

Sure thing. Sorry for not being that thorough.

[foad]

lldb/docs/htr.rst

13 ↗

(On Diff #362455)

Typo "oad".

22 ↗

(On Diff #362455)

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/include/lldb/Target/Trace.h

public:
   /// This function will dump all of the trace data for all threads in a user
   /// readable format. Options for dumping can be added as this API is iterated
   /// on.
   ///
   /// \param[in] s
   ///     A stream object to dump the information to.
   virtual void Dump(Stream *s) const = 0;
 
+  /// Dump the trace into Chrome Trace Format (CTF)
+  ///
+  /// \param[in] thread
+  ///     The thread that owns the trace in question
+  ///
+  /// \param[in] s
+  ///     A stream object to dump the information to.
+  ///
+  /// \param[in] count
+  ///     The number of trace instructions to include in the CTF dump
+  ///
+  /// \param[in] outfile
+  ///     Path of the file to output the CTF dump
+  void DumpChromeTraceFormat(Thread &thread, lldb::TraceCursorUP &&cursor,
+                             Stream &s, llvm::Optional<size_t> count,
+                             std::string outfile);
+
   /// Find a trace plug-in using JSON data.
   ///
   /// When loading trace data from disk, the information for the trace data
   /// can be contained in multiple files and require plug-in specific
   /// information about the CPU. Using data like JSON provides an
   /// easy way to specify all of the settings and information that we will need
   /// to load trace data into LLDB. This structured data can include:
   ///   - The plug-in name (this allows a specific plug-in to be selected)

lldb/include/lldb/Target/TraceHTR.h

+//===-- TraceHTR.h -------------------------------------------------*- C++
+//-*-===//
+//
+// 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 <unordered_map>
+#include <unordered_set>
+
+namespace lldb_private {
+struct TraceInstruction {
+  lldb::addr_t load_address;
+  lldb::TraceInstructionControlFlowType type;
+};
+
+template <class TMetadata> class TraceHTR;
+
+/// \class HTRBlockMetadata TraceHTR.h "lldb/Target/TraceHTR.h"
+/// Metadata associated with an HTR block
+/// Metadata is initially populated in Layer 1 and merged as blocks are merged
+class HTRBlockMetadata {
+public:
+  HTRBlockMetadata(Thread &thread, TraceInstruction curr_instruction,
+                   llvm::Optional<TraceInstruction> next_instruction);
+  HTRBlockMetadata(size_t num_instructions,
+                   std::unordered_map<std::string, size_t> func_calls)
+      : m_num_instructions(num_instructions), m_func_calls(func_calls) {}
+  static HTRBlockMetadata MergeMetadata(HTRBlockMetadata &m1,
+                                        HTRBlockMetadata &m2);
+
+private:
+  size_t m_num_instructions;
+  std::unordered_map<std::string, size_t> m_func_calls;
+  friend llvm::json::Value toJSON(const HTRBlockMetadata &metadata);
+  template <class M> friend llvm::json::Value toJSON(const TraceHTR<M> &layer);
+};
+
+/// \class HTRBlock TraceHTR.h "lldb/Target/TraceHTR.h"
+/// Trace agnostic block structure
+/// Sequences of blocks are merged to create a new, single block
+/// Each block indirectly corresponds to a sequence of "unit" blocks (ie
+/// instructions)
+template <class TMetadata> class HTRBlock {
+public:
+  HTRBlock(size_t offset, size_t size, TMetadata metadata)
+      : m_offset(offset), m_size(size), m_metadata(metadata) {}
+
+private:
+  /// Offset in the previous layer's trace
+  size_t m_offset;
+  /// Size of block - number of blocks that make up this block in the previous
+  /// layer
+  size_t m_size;
+  /// General metadata about this block
+  TMetadata m_metadata;
+  // TODO: better way of doing this?
+  // Why does `friend class HTRLayer<TMetadata>` not work
+  template <class T> friend class HTRLayer;
+  template <class M> friend llvm::json::Value toJSON(const TraceHTR<M> &layer);
+  template <class B> friend llvm::json::Value toJSON(const HTRBlock<B> &block);
+};
+
+/// \class HTRBlockDefs TraceHTR.h "lldb/Target/TraceHTR.h"
+/// Maps the unique Block IDs to their respective Blocks
+template <class TMetadata> class HTRBlockDefs {
+public:
+  /// Maps a unique Block ID to the corresponding HTRBlock
+  std::unordered_map<size_t, HTRBlock<TMetadata>> m_block_id_map;
+};
+
+/// \class HTRLayer TraceHTR.h "lldb/Target/TraceHTR.h"
+/// Layer of the HTR representing a sequence of blocks
+template <class TMetadata> class HTRLayer {
+public:
+  /// 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.
+  ///
+  /// \return
+  ///     A new layer instance representing the merge of blocks in the
+  ///     previous layer
+  HTRLayer HeadsAndTailsMerge();
+
+private:
+  /// Creates a new block from the result of merging a sequence of blocks in
+  /// this layer
+  ///
+  /// \param[in] start_block_index
+  ///     The index of the first block to be merged
+  ///
+  /// \param[in] num_blocks
+  ///     The number of blocks to be merged
+  ///
+  /// \return
+  ///     A new block instance representing the merge of the specified blocks
+  HTRBlock<TMetadata> MergeBlocks(size_t start_block_index, size_t num_blocks);
+  /// Unique Layer ID
+  size_t uuid;
+  /// Maps block ID to HTRBlock for this layer
+  HTRBlockDefs<TMetadata> block_defs;
+  /// Reduce memory footprint by just storing block_id trace and use
+  // \a HTRBlockDefs to get the \a HTRBlock from an block id
+  std::vector<size_t> block_id_trace;
+  template <class T> friend class TraceHTR;
+  template <class M> friend llvm::json::Value toJSON(const TraceHTR<M> &layer);
+};
+
+/// \class TraceHTR TraceHTR.h "lldb/Target/TraceHTR.h"
+/// Hierarchical Trace Representation (HTR)
+///
+/// HTR is a trace agnostic format that efficiently encodes a trace's raw
+/// representation in hierarchical layers, allowing for summarization of the
+/// trace
+///
+/// Each layer of HTR contains a sequence of blocks
+/// Different passes merge groups of blocks and create a new layer with these
+/// new blocks representing the merge of groups of blocks in the previous layer
+template <class TMetadata> class TraceHTR {
+
+public:
+  TraceHTR(Thread &thread, lldb::TraceCursorUP &&cursor,
+           llvm::Optional<size_t> instruction_count, std::string outfile);
+  /// Executes `HeadsAndTailsMerge` on the HTR layers until no compression
+  /// occurs The HTR layers are converted to Chrome Trace Format (CTF) and
+  /// dumped to `outfile`
+  void DumpChromeTraceFormat(Stream &s, std::string outfile);
+
+private:
+  std::map<size_t, HTRLayer<TMetadata>> layers;
+  // Number of trace instructions to include in this HTR
+  // None means include all instructions in the trace
+  llvm::Optional<size_t> m_instruction_count;
+  template <class L> friend llvm::json::Value toJSON(const TraceHTR<L> &layer);
+};
+
+} // namespace lldb_private
+
+#endif // LLDB_TARGET_TRACE_HTR_H

lldb/source/Commands/CommandObjectThread.cpp

protected:
   CommandOptions m_options;
 
   // Repeat command helpers
   std::string m_repeat_command;
   bool m_create_repeat_command_just_invoked;
   std::map<const Thread *, TraceCursorUP> m_cursors;
 };
 
+// CommandObjectTraceDumpChromeTraceFormat
+#define LLDB_OPTIONS_thread_trace_dump_ctf
+#include "CommandOptions.inc"
+
+class CommandObjectTraceDumpChromeTraceFormat
+    : public CommandObjectIterateOverThreads {
+public:
+  class CommandOptions : public Options {
+  public:
+    CommandOptions() : Options() { OptionParsingStarting(nullptr); }
+
+    ~CommandOptions() override = default;
+
+    Status SetOptionValue(uint32_t option_idx, llvm::StringRef option_arg,
+                          ExecutionContext *execution_context) override {
+      Status error;
+      const int short_option = m_getopt_table[option_idx].val;
+
+      switch (short_option) {
+      case 'c': {
+        int32_t count;
+        if (option_arg.empty() || option_arg.getAsInteger(0, count) ||
+            count < 0)
+          error.SetErrorStringWithFormat(
+              "invalid integer value for option '%s'",
+              option_arg.str().c_str());
+        else
+          m_count = count;
+        break;
+      }
+      case 'f': {
+        m_file.assign(std::string(option_arg));
+        break;
+      }
+      default:
+        llvm_unreachable("Unimplemented option");
+      }
+      return error;
+    }
+
+    void OptionParsingStarting(ExecutionContext *execution_context) override {
+      m_count = llvm::None;
+      m_file.clear();
+    }
+
+    llvm::ArrayRef<OptionDefinition> GetDefinitions() override {
+      return llvm::makeArrayRef(g_thread_trace_dump_ctf_options);
+    }
+
+    // Instance variables to hold the values for command options.
+    // None indicates the entire trace should be dumped to CTF
+    llvm::Optional<size_t> m_count;
+    std::string m_file;
+  };
+
+  CommandObjectTraceDumpChromeTraceFormat(CommandInterpreter &interpreter)
+      : CommandObjectIterateOverThreads(
+            interpreter, "thread trace dump ctf",
+            "Dump the a thread's trace to Chrome Trace Format (CTF).", nullptr,
+            eCommandRequiresProcess | eCommandTryTargetAPILock |
+                eCommandProcessMustBeLaunched | eCommandProcessMustBePaused |
+                eCommandProcessMustBeTraced),
+        m_options() {}
+
+  ~CommandObjectTraceDumpChromeTraceFormat() override = default;
+
+  Options *GetOptions() override { return &m_options; }
+
+protected:
+  bool HandleOneThread(lldb::tid_t tid, CommandReturnObject &result) override {
+    const TraceSP &trace_sp = m_exe_ctx.GetTargetSP()->GetTrace();
+    ThreadSP thread_sp =
+        m_exe_ctx.GetProcessPtr()->GetThreadList().FindThreadByID(tid);
+    trace_sp->DumpChromeTraceFormat(*thread_sp, trace_sp->GetCursor(*thread_sp),
+                                    result.GetOutputStream(), m_options.m_count,
+                                    m_options.m_file);
+    return true;
+  }
+
+  CommandOptions m_options;
+};
+
 // CommandObjectMultiwordTraceDump
 class CommandObjectMultiwordTraceDump : public CommandObjectMultiword {
 public:
   CommandObjectMultiwordTraceDump(CommandInterpreter &interpreter)
       : CommandObjectMultiword(
             interpreter, "dump",
             "Commands for displaying trace information of the threads "
             "in the current process.",
             "thread trace dump <subcommand> [<subcommand objects>]") {
     LoadSubCommand(
         "instructions",
         CommandObjectSP(new CommandObjectTraceDumpInstructions(interpreter)));
+    LoadSubCommand(
+        "ctf", CommandObjectSP(
+                   new CommandObjectTraceDumpChromeTraceFormat(interpreter)));
   }
   ~CommandObjectMultiwordTraceDump() override = default;
 };
 
 // CommandObjectMultiwordTrace
 class CommandObjectMultiwordTrace : public CommandObjectMultiword {
 public:
   CommandObjectMultiwordTrace(CommandInterpreter &interpreter)

lldb/source/Commands/Options.td

def thread_trace_dump_instructions_skip: Option<"skip", "s">,
     Arg<"Index">,
     Desc<"How many instruction to skip from the end of the trace to start "
     "dumping instructions, or from the beginning if --forwards is provided">;
   def thread_trace_dump_instructions_raw : Option<"raw", "r">,
     Group<1>,
     Desc<"Dump only instruction address without disassembly nor symbol information.">;
 }
 
+let Command = "thread trace dump ctf" in {
+  def thread_trace_dump_ctf_count : Option<"count", "c">, Group<1>,
+    Arg<"Count">,
+    Desc<"The number of trace instructions to include in the CTF dump">;
+  def thread_trace_dump_ctf_file : Option<"file", "f">, Required, Group<1>,
+    Arg<"Filename">,
+    Desc<"Path of the file to output the CTF dump">;
+}
+
 let Command = "type summary add" in {
   def type_summary_add_category : Option<"category", "w">, Arg<"Name">,
     Desc<"Add this to the given category instead of the default one.">;
   def type_summary_add_cascade : Option<"cascade", "C">, Arg<"Boolean">,
     Desc<"If true, cascade through typedef chains.">;
   def type_summary_add_no_value : Option<"no-value", "v">,
     Desc<"Don't show the value, just show the summary, for this type.">;
   def type_summary_add_skip_pointers : Option<"skip-pointers", "p">,

lldb/source/Target/CMakeLists.txt

add_lldb_library(lldbTarget
   ThreadPlanStepThrough.cpp
   ThreadPlanStepUntil.cpp
   ThreadPlanTracer.cpp
   ThreadPlanStack.cpp
   ThreadSpec.cpp
   ThreadPostMortemTrace.cpp
   Trace.cpp
   TraceCursor.cpp
+  TraceHTR.cpp
   TraceSessionFileParser.cpp
   UnixSignals.cpp
   UnwindAssembly.cpp
   UnwindLLDB.cpp
 
   LINK_LIBS
     lldbBreakpoint
     lldbCore

lldb/source/Target/Trace.cpp

 #include "lldb/Core/Module.h"
 #include "lldb/Core/PluginManager.h"
 #include "lldb/Symbol/Function.h"
 #include "lldb/Target/ExecutionContext.h"
 #include "lldb/Target/Process.h"
 #include "lldb/Target/SectionLoadList.h"
 #include "lldb/Target/Thread.h"
 #include "lldb/Target/ThreadPostMortemTrace.h"
+#include "lldb/Target/TraceHTR.h"
 #include "lldb/Utility/Stream.h"
 
 using namespace lldb;
 using namespace lldb_private;
 using namespace llvm;
 
 // Helper structs used to extract the type of a trace session json without
 // having to parse the entire object.
void Trace::RefreshLiveProcessState() {
   }
 
   for (const TraceBinaryData &item : live_process_state->processBinaryData)
     m_live_process_data[item.kind] = item.size;
 
   DoRefreshLiveProcessState(std::move(live_process_state));
 }
 
+void Trace::DumpChromeTraceFormat(Thread &thread, lldb::TraceCursorUP &&cursor,
+                                  Stream &s, llvm::Optional<size_t> count,
+                                  std::string outfile) {
+  TraceHTR<HTRBlockMetadata> trace_htr(thread, std::move(cursor), count,
+                                       outfile);
+  trace_htr.DumpChromeTraceFormat(s, outfile);
+}
+
 uint32_t Trace::GetStopID() {
   RefreshLiveProcessState();
   return m_stop_id;
 }

lldb/source/Target/TraceCursor.cpp

 //===-- TraceCursor.cpp -----------------------------------------*- C++ -*-===//
 //
 // 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 "lldb/Target/TraceCursor.h"
 
 #include "lldb/Core/Module.h"
 #include "lldb/Symbol/Function.h"
 #include "lldb/Target/ExecutionContext.h"
 #include "lldb/Target/Process.h"
 #include "lldb/Target/SectionLoadList.h"
 #include "lldb/Target/Trace.h"
+#include "lldb/Target/TraceHTR.h"
 
 using namespace lldb;
 using namespace lldb_private;
 using namespace llvm;
 
 static int GetNumberOfDigits(int num) {
   if (num == 0)
     return 1;

lldb/source/Target/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 "lldb/Target/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;
+
+HTRBlockMetadata::HTRBlockMetadata(
+    Thread &thread, TraceInstruction curr_instruction,
+    llvm::Optional<TraceInstruction> next_instruction) {
+  m_num_instructions = 1;
+
+  if (curr_instruction.type & lldb::eTraceInstructionControlFlowTypeCall &&
+      next_instruction) {
+    lldb::addr_t next_load_addr = next_instruction->load_address;
+    lldb_private::Address pc_addr;
+    Target &target = thread.GetProcess()->GetTarget();
+    SymbolContext sc;
+    if (target.ResolveLoadAddress(next_load_addr, pc_addr) &&
+        pc_addr.CalculateSymbolContext(&sc)) {
+      ConstString func_name = sc.GetFunctionName();
+      if (func_name) {
+        std::string str_func_name(func_name.AsCString());
+        m_func_calls[str_func_name] = 1;
+      }
+    }
+  }
+}
+
+template <class TMetadata>
+TraceHTR<TMetadata>::TraceHTR(Thread &thread, lldb::TraceCursorUP &&cursor,
+                              llvm::Optional<size_t> instruction_count,
+                              std::string outfile) {
+  // Layer 0 of HTR
+  HTRLayer<HTRBlockMetadata> instruction_layer;
+  instruction_layer.uuid = 0;
+
+  // Move cursor to the first instruction in the trace
+  cursor->SeekToBegin();
+
+  int block_id = 0;
+  std::unordered_map<lldb::addr_t, size_t> load_address_to_block_id;
+  // This flag becomes true when cursor->Next() returns false
+  bool valid_cursor = true;
+  size_t i = 0;
+  // Predicate to check if the trace traversal should continue
+  auto continue_traversal = [&]() {
+    // Traverse the first `instruction_count` instructions of the trace
+    // If no `instruction_count` was specified, traverse the entire trace
+    bool valid_trace_index = instruction_count ? i < *instruction_count : true;
+    return valid_cursor && valid_trace_index;
+  };
+  // We keep two mappings:
+  // 1. instruction load address to unique block id
+  // 2. unique block id: block
+  while (continue_traversal()) {
+    // TODO: how should we handle cursor errors in this loop?
+    lldb::addr_t current_instruction_load_address = cursor->GetLoadAddress();
+    lldb::TraceInstructionControlFlowType current_instruction_type =
+        cursor->GetInstructionControlFlowType();
+    TraceInstruction current_instruction = {current_instruction_load_address,
+                                            current_instruction_type};
+
+    // If this instruction doesn't have an id mapping, create one and create
+    // a mapping from this id to this new block
+    // Add this new id to the trace
+    // Increment id since this is a new id
+    if (load_address_to_block_id.find(current_instruction_load_address) ==
+        load_address_to_block_id.end()) {
+      // Update load_addr: block id mapping
+      load_address_to_block_id[current_instruction_load_address] = block_id;
+
+      llvm::Optional<TraceInstruction> next_instruction = llvm::None;
+      if (cursor->Next()) {
+        lldb::addr_t next_instruction_load_address = cursor->GetLoadAddress();
+        lldb::TraceInstructionControlFlowType next_type =
+            cursor->GetInstructionControlFlowType();
+        next_instruction = {next_instruction_load_address, next_type};
+      } else {
+        valid_cursor = false;
+      }
+
+      HTRBlockMetadata metadata(thread, current_instruction, next_instruction);
+      // All blocks in Layer 0 (instruction layer) have a size of 1
+      HTRBlock<HTRBlockMetadata> block(current_instruction_load_address, 1,
+                                       metadata);
+
+      // Update id: block mapping
+      instruction_layer.block_defs.m_block_id_map.emplace(block_id, block);
+
+      // Update trace
+      instruction_layer.block_id_trace.emplace_back(block_id);
+      block_id++;
+    } else {
+      // this address already has block id mapping, so get the block id from
+      // the mapping and add this repeated id to the trace
+      auto repeated_id =
+          load_address_to_block_id[current_instruction_load_address];
+      instruction_layer.block_id_trace.emplace_back(repeated_id);
+      if (!cursor->Next()) {
+        valid_cursor = false;
+      }
+    }
+    i++;
+  }
+  layers.emplace(instruction_layer.uuid, instruction_layer);
+}
+
+HTRBlockMetadata HTRBlockMetadata::MergeMetadata(HTRBlockMetadata &m1,
+                                                 HTRBlockMetadata &m2) {
+  size_t num_instructions = m1.m_num_instructions + m2.m_num_instructions;
+  std::unordered_map<std::string, size_t> func_calls;
+  func_calls.insert(m1.m_func_calls.begin(), m1.m_func_calls.end());
+  for (const auto &[name, num_calls] : m2.m_func_calls) {
+    if (func_calls.find(name) == func_calls.end())
+      func_calls[name] = num_calls;
+    else
+      func_calls[name] += num_calls;
+  }
+
+  return {num_instructions, func_calls};
+}
+
+template <class TMetadata>
+HTRBlock<TMetadata> HTRLayer<TMetadata>::MergeBlocks(size_t start_block_index,
+                                                     size_t num_blocks) {
+  assert(num_blocks > 0);
+  std::unordered_map<std::string, size_t> func_calls;
+  llvm::Optional<TMetadata> merged_metadata = llvm::None;
+  llvm::Optional<size_t> start_block_offset = llvm::None;
+  for (size_t i = start_block_index; i < start_block_index + num_blocks; i++) {
+    size_t id = block_id_trace[i];
+    HTRBlock<TMetadata> block = block_defs.m_block_id_map.find(id)->second;
+    if (!start_block_offset)
+      start_block_offset = block.m_offset;
+    if (!merged_metadata) {
+      merged_metadata = block.m_metadata;
+    } else {
+      merged_metadata =
+          TMetadata::MergeMetadata(*merged_metadata, block.m_metadata);
+    }
+  }
+  return {*start_block_offset, num_blocks, *merged_metadata};
+}
+
+template <class TMetadata>
+HTRLayer<TMetadata> HTRLayer<TMetadata>::HeadsAndTailsMerge() {
+  HTRLayer new_layer;
+  new_layer.uuid = this->uuid + 1;
+
+  if (block_id_trace.size()) {
+    // 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;
+    // map block id to a set it's preceding block ids
+    // Future Improvement: no need to store all it's 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<size_t, std::unordered_set<size_t>> head_map;
+    size_t prev = block_id_trace[0];
+    // This excludes the first block since it has no previous instruction
+    for (size_t i = 1; i < block_id_trace.size(); i++) {
+      size_t id = block_id_trace[i];
+      head_map[id].insert(prev);
+      prev = id;
+    }
+    for (const auto &[idx, predecessor_set] : head_map) {
+      if (predecessor_set.size() > 1)
+        heads.insert(idx);
+    }
+
+    // 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<size_t> tails;
+    std::unordered_map<size_t, std::unordered_set<size_t>> tail_map;
+
+    // This excludes the last block since it has no next block
+    for (size_t i = 0; i < block_id_trace.size() - 1; i++) {
+      size_t next = block_id_trace[i + 1];
+
+      size_t id = block_id_trace[i];
+      tail_map[id].insert(next);
+    }
+    // Mark last block as tail so the algorithm stops gracefully
+    size_t last_id = block_id_trace[block_id_trace.size() - 1];
+    tails.insert(last_id);
+    for (const auto &[idx, successor_set] : tail_map) {
+      if (successor_set.size() > 1)
+        tails.insert(idx);
+    }
+    // Maps the starting block of a sequence of blocks that were merged to a
+    // unique id
+    std::unordered_map<size_t, size_t> block_sequence_to_id;
+
+    // Need to keep track of size of string since things we push are variable
+    // length
+    size_t size = 0;
+    // Each super block always has the same first block (we call this the block
+    // head) This gurantee allows us to use the block_head as the unique key
+    // mapping to the super block it begins
+    llvm::Optional<size_t> block_head = llvm::None;
+    size_t sequence_id = 0;
+    auto construct_next_layer = [&](size_t merge_start,
+                                    size_t merge_end) -> void {
+      if (!block_head)
+        return;
+      if (block_sequence_to_id.find(*block_head) ==
+          block_sequence_to_id.end()) {
+        // Update sequence to id mapping
+        block_sequence_to_id[*block_head] = sequence_id;
+        // Create new block for next layer by merging this group
+        auto new_block = MergeBlocks(merge_start, merge_end);
+        // Update next layer's block_id map
+        new_layer.block_defs.m_block_id_map.emplace(sequence_id, new_block);
+        // Update next layer's id trace
+        new_layer.block_id_trace.emplace_back(sequence_id);
+        sequence_id++;
+      } else {
+        size_t repeated_id = block_sequence_to_id.find(*block_head)->second;
+        // Update next layer's id trace
+        new_layer.block_id_trace.emplace_back(repeated_id);
+      }
+    };
+    for (size_t i = 0; i < block_id_trace.size(); i++) {
+      auto block_id = block_id_trace[i];
+      auto isHead = heads.count(block_id) > 0;
+      auto isTail = tails.count(block_id) > 0;
+
+      std::string str_id = std::to_string(block_id);
+      if (isHead && isTail) {
+        // Head logic
+        if (size) { // this handles (tail, head) adjacency - otherwise an empty
+                    // block is created
+          construct_next_layer(i - size, size);
+        }
+        // Current id is first in next super block since it's a head
+        block_head = block_id;
+        size = 1;
+
+        // Tail logic
+        construct_next_layer(i - size + 1, size);
+        // Reset the block_head since the prev super block has come to and end
+        block_head = llvm::None;
+        size = 0;
+      } else if (isHead) {
+        if (size) { // this handles (tail, head) adjacency - otherwise an empty
+                    // block is created
+          // End previous super block
+          construct_next_layer(i - size, size);
+        }
+        // Current id is first in next super block since it's a head
+        block_head = block_id;
+        size = 1;
+      } else if (isTail) {
+        if (!block_head)
+          block_head = block_id;
+        size++;
+
+        // End previous super block
+        construct_next_layer(i - size + 1, size);
+        // Reset the block_head since the prev super block has come to and end
+        block_head = llvm::None;
+        size = 0;
+      } else {
+        if (!block_head)
+          block_head = block_id;
+        size++;
+      }
+    }
+  }
+  return new_layer;
+}
+
+template <class TMetadata>
+void TraceHTR<TMetadata>::DumpChromeTraceFormat(Stream &s,
+                                                std::string outfile) {
+  if (layers.find(0) == layers.end()) {
+    s.Printf("No HTR layers found\n");
+    return;
+  }
+  auto current_layer = layers[0];
+
+  while (true) {
+    auto new_layer = current_layer.HeadsAndTailsMerge();
+    if (current_layer.block_id_trace.size() == new_layer.block_id_trace.size())
+      break;
+    layers.emplace(new_layer.uuid, new_layer);
+    current_layer = new_layer;
+  }
+
+  std::error_code ec;
+  llvm::raw_fd_ostream os(outfile, ec, llvm::sys::fs::OF_Text);
+  auto outfile_cstr = outfile.c_str();
+  if (ec) {
+    s.Printf("Error dumping CTF to %s\n", outfile_cstr);
+    return;
+  }
+  os << toJSON(*this);
+  os.flush();
+  s.Printf("Success! Dumped CTF data to %s\n", outfile_cstr);
+  for (const auto &[id, layer] : layers) {
+    s.Printf("Layer %ld: %ld Total Blocks, %ld Unique Blocks\n", id,
+             layer.block_id_trace.size(),
+             layer.block_defs.m_block_id_map.size());
+  }
+}
+
+namespace lldb_private {
+template <class TMetadata>
+llvm::json::Value toJSON(const TraceHTR<TMetadata> &htr) {
+  std::vector<llvm::json::Value> layers_as_json;
+  for (const auto &[id, layer] : htr.layers) {
+    size_t start_ts = 0;
+    for (size_t i = 0; i < layer.block_id_trace.size(); i++) {
+      auto id = layer.block_id_trace[i];
+      auto block = layer.block_defs.m_block_id_map.find(id)->second;
+      auto block_json = toJSON(block);
+      auto layer_id = layer.uuid;
+      // auto end_ts = start_ts + (layer_id ? block.m_size : 1);
+      auto end_ts = start_ts + block.m_size;
+
+      size_t max_calls = 0;
+      llvm::Optional<std::string> max_name = llvm::None;
+      for (const auto &[name, ncalls] : block.m_metadata.m_func_calls) {
+        if (ncalls > max_calls) {
+          max_calls = ncalls;
+          max_name = name;
+        }
+      }
+      std::stringstream stream;
+      stream << "0x" << std::hex << block.m_offset;
+      std::string offset_hex_string(stream.str());
+      auto display_name =
+          max_name ? offset_hex_string + ", " + *max_name : offset_hex_string;
+      layers_as_json.emplace_back(llvm::json::Object{
+          {"name", display_name},
+          {"ph", "B"},
+          {"ts", (ssize_t)start_ts},
+          {"pid", (ssize_t)layer_id},
+          {"tid", (ssize_t)layer_id},
+      });
+
+      layers_as_json.emplace_back(llvm::json::Object{
+          {"ph", "E"},
+          {"ts", (ssize_t)end_ts},
+          {"pid", (ssize_t)layer_id},
+          {"tid", (ssize_t)layer_id},
+          {"args", block_json},
+      });
+      start_ts = end_ts;
+    }
+  }
+  return layers_as_json;
+}
+
+template <class TMetadata>
+llvm::json::Value toJSON(const HTRBlock<TMetadata> &block) {
+  return llvm::json::Value(llvm::json::Object{{"Functions", block.m_metadata}});
+}
+llvm::json::Value toJSON(const HTRBlockMetadata &metadata) {
+  std::vector<llvm::json::Value> function_calls;
+  for (const auto &[name, n_calls] : metadata.m_func_calls)
+    function_calls.emplace_back(llvm::formatv("({0}: {1})", name, n_calls));
+
+  return llvm::json::Value(llvm::json::Object{
+      {"Number of Instructions", (ssize_t)metadata.m_num_instructions},
+      {"Functions", function_calls}});
+}
+
+// explicit template instantiation to prevent moving method definitions to
+// header file
+template class TraceHTR<HTRBlockMetadata>;
+} // namespace lldb_private

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

+import lldb
+from intelpt_testcase import *
+from lldbsuite.test.lldbtest import *
+from lldbsuite.test import lldbutil
+from lldbsuite.test.decorators import *
+import os
+
+class TestTraceDumpInstructions(TraceIntelPTTestCaseBase):
+
+    mydir = TestBase.compute_mydir(__file__)
+
+    def testErrorMessages(self):
+        # We first check the output when there are no targets
+        self.expect("thread trace dump ctf",
+            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("thread trace dump ctf",
+            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("thread trace dump ctf",
+            substrs=["error: Process is not being traced"],
+            error=True)
+
+    def testDumpCTF(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")
+
+        # file name, no count
+        if os.path.exists(ctf_test_file):
+            remove_file(ctf_test_file)
+        self.expect(f"thread trace dump ctf --file {ctf_test_file}",
+                substrs=["Success", f"{ctf_test_file}", "21 Total Blocks"])
+        self.assertTrue(os.path.exists(ctf_test_file))
+
+        # file name, "normal" count
+        if os.path.exists(ctf_test_file):
+            remove_file(ctf_test_file)
+        self.expect(f"thread trace dump ctf --file {ctf_test_file} --count 10",
+                substrs=["Success", f"{ctf_test_file}", "10 Total Blocks"])
+        self.assertTrue(os.path.exists(ctf_test_file))
+
+        # file name, count exceeding size of trace (21 instructions)
+        if os.path.exists(ctf_test_file):
+            remove_file(ctf_test_file)
+        self.expect(f"thread trace dump ctf --file {ctf_test_file} --count 34",
+                substrs=["Success", f"{ctf_test_file}", "21 Total Blocks"])
+        self.assertTrue(os.path.exists(ctf_test_file))
+
+        # file name, 0 count
+        if os.path.exists(ctf_test_file):
+            remove_file(ctf_test_file)
+        # count of 0 still create a file containing an empty JSON array
+        self.expect(f"thread trace dump ctf --file {ctf_test_file} --count 0",
+                substrs=["Success", f"{ctf_test_file}", "0 Total Blocks"])
+        self.assertTrue(os.path.exists(ctf_test_file))