jj10306 created this revision.
jj10306 added reviewers: wallace, clayborg.
Herald added subscribers: dang, mgorny.
jj10306 requested review of this revision.
Herald added a project: LLDB.
Herald added a subscriber: lldb-commits.
This diff enables visualization of Intel PT traces by converting a summarized
trace representation (HTR) to Chrome Trace Format (CTF) via the `thread trace
dump ctf -f <filename>` command - see attached video for an example of Intel PT
trace visualization.
**Context**
To efficiently store and operate on traces we introduce HTR (Hierarchical Trace
Representation). HTR is designed to be extensible and agnostic to trace type.
In HTR, a trace is transformed in a way akin to compiler passes. Each pass
modifies the trace and outputs a new HTR-based representation of the trace. A
**layer** is each instance of trace data between passes.
A layer is composed of **blocks** - a block in //layer n// refers to a sequence
of blocks in //layer n - 1//. The blocks in the first layer correspond to a
dynamic instruction in the trace.
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. This diff contains one such
pass - //Basic Super Block Reduction//.
**Overview of Changes**
- Add basic HTR structures (layer, block, block metadata)
- Implement Super Basic Block Reduction Pass (HeadsAndTailsMerge in the code)
to identify and merge patterns of repeated instructions
- Add 'thread trace dump ctf' command to export the HTR of an Intel PT trace to
Chrome Trace Format (CTF)
F17851042: lldbdemo.mov <https://reviews.llvm.org/F17851042>
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D105741
Files:
lldb/include/lldb/Target/Trace.h
lldb/include/lldb/Target/TraceHTR.h
lldb/source/Commands/CommandObjectThread.cpp
lldb/source/Commands/Options.td
lldb/source/Target/CMakeLists.txt
lldb/source/Target/Trace.cpp
lldb/source/Target/TraceCursor.cpp
lldb/source/Target/TraceHTR.cpp
lldb/test/API/commands/trace/TestTraceDumpCTF.py
Index: lldb/test/API/commands/trace/TestTraceDumpCTF.py
===================================================================
--- /dev/null
+++ lldb/test/API/commands/trace/TestTraceDumpCTF.py
@@ -0,0 +1,68 @@
+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))
Index: lldb/source/Target/TraceHTR.cpp
===================================================================
--- /dev/null
+++ lldb/source/Target/TraceHTR.cpp
@@ -0,0 +1,390 @@
+//===-- 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
Index: lldb/source/Target/TraceCursor.cpp
===================================================================
--- lldb/source/Target/TraceCursor.cpp
+++ lldb/source/Target/TraceCursor.cpp
@@ -14,6 +14,7 @@
#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;
Index: lldb/source/Target/Trace.cpp
===================================================================
--- lldb/source/Target/Trace.cpp
+++ lldb/source/Target/Trace.cpp
@@ -18,6 +18,7 @@
#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;
@@ -216,6 +217,14 @@
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;
Index: lldb/source/Target/CMakeLists.txt
===================================================================
--- lldb/source/Target/CMakeLists.txt
+++ lldb/source/Target/CMakeLists.txt
@@ -69,6 +69,7 @@
ThreadPostMortemTrace.cpp
Trace.cpp
TraceCursor.cpp
+ TraceHTR.cpp
TraceSessionFileParser.cpp
UnixSignals.cpp
UnwindAssembly.cpp
Index: lldb/source/Commands/Options.td
===================================================================
--- lldb/source/Commands/Options.td
+++ lldb/source/Commands/Options.td
@@ -1065,6 +1065,15 @@
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.">;
Index: lldb/source/Commands/CommandObjectThread.cpp
===================================================================
--- lldb/source/Commands/CommandObjectThread.cpp
+++ lldb/source/Commands/CommandObjectThread.cpp
@@ -2114,6 +2114,88 @@
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:
@@ -2126,6 +2208,9 @@
LoadSubCommand(
"instructions",
CommandObjectSP(new CommandObjectTraceDumpInstructions(interpreter)));
+ LoadSubCommand(
+ "ctf", CommandObjectSP(
+ new CommandObjectTraceDumpChromeTraceFormat(interpreter)));
}
~CommandObjectMultiwordTraceDump() override = default;
};
Index: lldb/include/lldb/Target/TraceHTR.h
===================================================================
--- /dev/null
+++ lldb/include/lldb/Target/TraceHTR.h
@@ -0,0 +1,177 @@
+//===-- 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
Index: lldb/include/lldb/Target/Trace.h
===================================================================
--- lldb/include/lldb/Target/Trace.h
+++ lldb/include/lldb/Target/Trace.h
@@ -55,6 +55,23 @@
/// 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
_______________________________________________
lldb-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
