1349cc55cSDimitry Andric //===-- TraceHTR.cpp ------------------------------------------------------===//
2349cc55cSDimitry Andric //
3349cc55cSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4349cc55cSDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
5349cc55cSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6349cc55cSDimitry Andric //
7349cc55cSDimitry Andric //===----------------------------------------------------------------------===//
8349cc55cSDimitry Andric
9349cc55cSDimitry Andric #include "TraceHTR.h"
10349cc55cSDimitry Andric
11349cc55cSDimitry Andric #include "lldb/Symbol/Function.h"
12349cc55cSDimitry Andric #include "lldb/Target/Process.h"
13349cc55cSDimitry Andric #include "lldb/Target/Target.h"
14349cc55cSDimitry Andric #include "llvm/Support/JSON.h"
15bdd1243dSDimitry Andric #include <optional>
16349cc55cSDimitry Andric #include <sstream>
17349cc55cSDimitry Andric #include <string>
18349cc55cSDimitry Andric
19349cc55cSDimitry Andric using namespace lldb_private;
20349cc55cSDimitry Andric using namespace lldb;
21349cc55cSDimitry Andric
GetNumInstructions() const22349cc55cSDimitry Andric size_t HTRBlockMetadata::GetNumInstructions() const {
23349cc55cSDimitry Andric return m_num_instructions;
24349cc55cSDimitry Andric }
25349cc55cSDimitry Andric
26bdd1243dSDimitry Andric std::optional<llvm::StringRef>
GetMostFrequentlyCalledFunction() const27349cc55cSDimitry Andric HTRBlockMetadata::GetMostFrequentlyCalledFunction() const {
28349cc55cSDimitry Andric size_t max_ncalls = 0;
29bdd1243dSDimitry Andric std::optional<llvm::StringRef> max_name;
30349cc55cSDimitry Andric for (const auto &it : m_func_calls) {
31349cc55cSDimitry Andric ConstString name = it.first;
32349cc55cSDimitry Andric size_t ncalls = it.second;
33349cc55cSDimitry Andric if (ncalls > max_ncalls) {
34349cc55cSDimitry Andric max_ncalls = ncalls;
35349cc55cSDimitry Andric max_name = name.GetStringRef();
36349cc55cSDimitry Andric }
37349cc55cSDimitry Andric }
38349cc55cSDimitry Andric return max_name;
39349cc55cSDimitry Andric }
40349cc55cSDimitry Andric
41349cc55cSDimitry Andric llvm::DenseMap<ConstString, size_t> const &
GetFunctionCalls() const42349cc55cSDimitry Andric HTRBlockMetadata::GetFunctionCalls() const {
43349cc55cSDimitry Andric return m_func_calls;
44349cc55cSDimitry Andric }
45349cc55cSDimitry Andric
GetFirstInstructionLoadAddress() const46349cc55cSDimitry Andric lldb::addr_t HTRBlockMetadata::GetFirstInstructionLoadAddress() const {
47349cc55cSDimitry Andric return m_first_instruction_load_address;
48349cc55cSDimitry Andric }
49349cc55cSDimitry Andric
GetOffset() const50349cc55cSDimitry Andric size_t HTRBlock::GetOffset() const { return m_offset; }
51349cc55cSDimitry Andric
GetSize() const52349cc55cSDimitry Andric size_t HTRBlock::GetSize() const { return m_size; }
53349cc55cSDimitry Andric
GetMetadata() const54349cc55cSDimitry Andric HTRBlockMetadata const &HTRBlock::GetMetadata() const { return m_metadata; }
55349cc55cSDimitry Andric
GetBlockLayers() const56349cc55cSDimitry Andric llvm::ArrayRef<HTRBlockLayerUP> TraceHTR::GetBlockLayers() const {
57349cc55cSDimitry Andric return m_block_layer_ups;
58349cc55cSDimitry Andric }
59349cc55cSDimitry Andric
GetInstructionLayer() const60349cc55cSDimitry Andric HTRInstructionLayer const &TraceHTR::GetInstructionLayer() const {
61349cc55cSDimitry Andric return *m_instruction_layer_up;
62349cc55cSDimitry Andric }
63349cc55cSDimitry Andric
AddNewBlockLayer(HTRBlockLayerUP && block_layer)64349cc55cSDimitry Andric void TraceHTR::AddNewBlockLayer(HTRBlockLayerUP &&block_layer) {
65349cc55cSDimitry Andric m_block_layer_ups.emplace_back(std::move(block_layer));
66349cc55cSDimitry Andric }
67349cc55cSDimitry Andric
GetLayerId() const68349cc55cSDimitry Andric size_t IHTRLayer::GetLayerId() const { return m_layer_id; }
69349cc55cSDimitry Andric
AppendNewBlock(size_t block_id,HTRBlock && block)70349cc55cSDimitry Andric void HTRBlockLayer::AppendNewBlock(size_t block_id, HTRBlock &&block) {
71349cc55cSDimitry Andric m_block_id_trace.emplace_back(block_id);
72*06c3fb27SDimitry Andric m_block_defs.emplace(block_id, std::move(block));
73349cc55cSDimitry Andric }
74349cc55cSDimitry Andric
AppendRepeatedBlock(size_t block_id)75349cc55cSDimitry Andric void HTRBlockLayer::AppendRepeatedBlock(size_t block_id) {
76349cc55cSDimitry Andric m_block_id_trace.emplace_back(block_id);
77349cc55cSDimitry Andric }
78349cc55cSDimitry Andric
GetInstructionTrace() const79349cc55cSDimitry Andric llvm::ArrayRef<lldb::addr_t> HTRInstructionLayer::GetInstructionTrace() const {
80349cc55cSDimitry Andric return m_instruction_trace;
81349cc55cSDimitry Andric }
82349cc55cSDimitry Andric
AddCallInstructionMetadata(lldb::addr_t load_addr,std::optional<ConstString> func_name)83349cc55cSDimitry Andric void HTRInstructionLayer::AddCallInstructionMetadata(
84bdd1243dSDimitry Andric lldb::addr_t load_addr, std::optional<ConstString> func_name) {
85349cc55cSDimitry Andric m_call_isns.emplace(load_addr, func_name);
86349cc55cSDimitry Andric }
87349cc55cSDimitry Andric
AppendInstruction(lldb::addr_t load_addr)88349cc55cSDimitry Andric void HTRInstructionLayer::AppendInstruction(lldb::addr_t load_addr) {
89349cc55cSDimitry Andric m_instruction_trace.emplace_back(load_addr);
90349cc55cSDimitry Andric }
91349cc55cSDimitry Andric
GetBlockById(size_t block_id) const92349cc55cSDimitry Andric HTRBlock const *HTRBlockLayer::GetBlockById(size_t block_id) const {
93349cc55cSDimitry Andric auto block_it = m_block_defs.find(block_id);
94349cc55cSDimitry Andric if (block_it == m_block_defs.end())
95349cc55cSDimitry Andric return nullptr;
96349cc55cSDimitry Andric else
97349cc55cSDimitry Andric return &block_it->second;
98349cc55cSDimitry Andric }
99349cc55cSDimitry Andric
GetBlockIdTrace() const100349cc55cSDimitry Andric llvm::ArrayRef<size_t> HTRBlockLayer::GetBlockIdTrace() const {
101349cc55cSDimitry Andric return m_block_id_trace;
102349cc55cSDimitry Andric }
103349cc55cSDimitry Andric
GetNumUnits() const104349cc55cSDimitry Andric size_t HTRBlockLayer::GetNumUnits() const { return m_block_id_trace.size(); }
105349cc55cSDimitry Andric
GetMetadataByIndex(size_t index) const106349cc55cSDimitry Andric HTRBlockMetadata HTRInstructionLayer::GetMetadataByIndex(size_t index) const {
107349cc55cSDimitry Andric lldb::addr_t instruction_load_address = m_instruction_trace[index];
108349cc55cSDimitry Andric llvm::DenseMap<ConstString, size_t> func_calls;
109349cc55cSDimitry Andric
110349cc55cSDimitry Andric auto func_name_it = m_call_isns.find(instruction_load_address);
111349cc55cSDimitry Andric if (func_name_it != m_call_isns.end()) {
112bdd1243dSDimitry Andric if (std::optional<ConstString> func_name = func_name_it->second) {
113349cc55cSDimitry Andric func_calls[*func_name] = 1;
114349cc55cSDimitry Andric }
115349cc55cSDimitry Andric }
116349cc55cSDimitry Andric return {instruction_load_address, 1, std::move(func_calls)};
117349cc55cSDimitry Andric }
118349cc55cSDimitry Andric
GetNumUnits() const119349cc55cSDimitry Andric size_t HTRInstructionLayer::GetNumUnits() const {
120349cc55cSDimitry Andric return m_instruction_trace.size();
121349cc55cSDimitry Andric }
122349cc55cSDimitry Andric
GetMetadataByIndex(size_t index) const123349cc55cSDimitry Andric HTRBlockMetadata HTRBlockLayer::GetMetadataByIndex(size_t index) const {
124349cc55cSDimitry Andric size_t block_id = m_block_id_trace[index];
125349cc55cSDimitry Andric HTRBlock block = m_block_defs.find(block_id)->second;
126349cc55cSDimitry Andric return block.GetMetadata();
127349cc55cSDimitry Andric }
128349cc55cSDimitry Andric
TraceHTR(Thread & thread,TraceCursor & cursor)129349cc55cSDimitry Andric TraceHTR::TraceHTR(Thread &thread, TraceCursor &cursor)
130349cc55cSDimitry Andric : m_instruction_layer_up(std::make_unique<HTRInstructionLayer>(0)) {
131349cc55cSDimitry Andric
132349cc55cSDimitry Andric // Move cursor to the first instruction in the trace
133349cc55cSDimitry Andric cursor.SetForwards(true);
134bdd1243dSDimitry Andric cursor.Seek(0, lldb::eTraceCursorSeekTypeBeginning);
135349cc55cSDimitry Andric
13681ad6265SDimitry Andric // TODO: fix after persona0220's patch on a new way to access instruction
13781ad6265SDimitry Andric // kinds
13881ad6265SDimitry Andric /*
139349cc55cSDimitry Andric Target &target = thread.GetProcess()->GetTarget();
140349cc55cSDimitry Andric auto function_name_from_load_address =
141bdd1243dSDimitry Andric [&](lldb::addr_t load_address) -> std::optional<ConstString> {
142349cc55cSDimitry Andric lldb_private::Address pc_addr;
143349cc55cSDimitry Andric SymbolContext sc;
144349cc55cSDimitry Andric if (target.ResolveLoadAddress(load_address, pc_addr) &&
145349cc55cSDimitry Andric pc_addr.CalculateSymbolContext(&sc))
146349cc55cSDimitry Andric return sc.GetFunctionName()
147bdd1243dSDimitry Andric ? std::optional<ConstString>(sc.GetFunctionName())
148bdd1243dSDimitry Andric : std::nullopt;
149349cc55cSDimitry Andric else
150bdd1243dSDimitry Andric return std::nullopt;
151349cc55cSDimitry Andric };
152349cc55cSDimitry Andric
15381ad6265SDimitry Andric while (cursor.HasValue()) { if (cursor.IsError()) {
154349cc55cSDimitry Andric // Append a load address of 0 for all instructions that an error occured
155349cc55cSDimitry Andric // while decoding.
156349cc55cSDimitry Andric // TODO: Make distinction between errors by storing the error messages.
157349cc55cSDimitry Andric // Currently, all errors are treated the same.
158349cc55cSDimitry Andric m_instruction_layer_up->AppendInstruction(0);
15981ad6265SDimitry Andric cursor.Next();
16081ad6265SDimitry Andric } else if (cursor.IsEvent()) {
16181ad6265SDimitry Andric cursor.Next();
162349cc55cSDimitry Andric } else {
163349cc55cSDimitry Andric lldb::addr_t current_instruction_load_address = cursor.GetLoadAddress();
164753f127fSDimitry Andric lldb::InstructionControlFlowKind current_instruction_type =
165753f127fSDimitry Andric cursor.GetInstructionControlFlowKind();
166349cc55cSDimitry Andric
167349cc55cSDimitry Andric m_instruction_layer_up->AppendInstruction(
168349cc55cSDimitry Andric current_instruction_load_address);
16981ad6265SDimitry Andric cursor.Next();
17081ad6265SDimitry Andric bool more_data_in_trace = cursor.HasValue();
171349cc55cSDimitry Andric if (current_instruction_type &
172753f127fSDimitry Andric lldb::eInstructionControlFlowKindCall) {
173349cc55cSDimitry Andric if (more_data_in_trace && !cursor.IsError()) {
174349cc55cSDimitry Andric m_instruction_layer_up->AddCallInstructionMetadata(
175349cc55cSDimitry Andric current_instruction_load_address,
176349cc55cSDimitry Andric function_name_from_load_address(cursor.GetLoadAddress()));
177349cc55cSDimitry Andric } else {
178349cc55cSDimitry Andric // Next instruction is not known - pass None to indicate the name
179349cc55cSDimitry Andric // of the function being called is not known
180349cc55cSDimitry Andric m_instruction_layer_up->AddCallInstructionMetadata(
181bdd1243dSDimitry Andric current_instruction_load_address, std::nullopt);
182349cc55cSDimitry Andric }
183349cc55cSDimitry Andric }
184349cc55cSDimitry Andric }
185349cc55cSDimitry Andric }
18681ad6265SDimitry Andric */
187349cc55cSDimitry Andric }
188349cc55cSDimitry Andric
MergeMetadata(HTRBlockMetadata & merged_metadata,HTRBlockMetadata const & metadata_to_merge)189349cc55cSDimitry Andric void HTRBlockMetadata::MergeMetadata(
190349cc55cSDimitry Andric HTRBlockMetadata &merged_metadata,
191349cc55cSDimitry Andric HTRBlockMetadata const &metadata_to_merge) {
192349cc55cSDimitry Andric merged_metadata.m_num_instructions += metadata_to_merge.m_num_instructions;
193349cc55cSDimitry Andric for (const auto &it : metadata_to_merge.m_func_calls) {
194349cc55cSDimitry Andric ConstString name = it.first;
195349cc55cSDimitry Andric size_t num_calls = it.second;
196349cc55cSDimitry Andric merged_metadata.m_func_calls[name] += num_calls;
197349cc55cSDimitry Andric }
198349cc55cSDimitry Andric }
199349cc55cSDimitry Andric
MergeUnits(size_t start_unit_index,size_t num_units)200349cc55cSDimitry Andric HTRBlock IHTRLayer::MergeUnits(size_t start_unit_index, size_t num_units) {
201349cc55cSDimitry Andric // TODO: make this function take `end_unit_index` as a parameter instead of
202349cc55cSDimitry Andric // unit and merge the range [start_unit_indx, end_unit_index] inclusive.
203349cc55cSDimitry Andric HTRBlockMetadata merged_metadata = GetMetadataByIndex(start_unit_index);
204349cc55cSDimitry Andric for (size_t i = start_unit_index + 1; i < start_unit_index + num_units; i++) {
205349cc55cSDimitry Andric // merge the new metadata into merged_metadata
206349cc55cSDimitry Andric HTRBlockMetadata::MergeMetadata(merged_metadata, GetMetadataByIndex(i));
207349cc55cSDimitry Andric }
208349cc55cSDimitry Andric return {start_unit_index, num_units, merged_metadata};
209349cc55cSDimitry Andric }
210349cc55cSDimitry Andric
ExecutePasses()211349cc55cSDimitry Andric void TraceHTR::ExecutePasses() {
212349cc55cSDimitry Andric auto are_passes_done = [](IHTRLayer &l1, IHTRLayer &l2) {
213349cc55cSDimitry Andric return l1.GetNumUnits() == l2.GetNumUnits();
214349cc55cSDimitry Andric };
215349cc55cSDimitry Andric HTRBlockLayerUP current_block_layer_up =
216349cc55cSDimitry Andric BasicSuperBlockMerge(*m_instruction_layer_up);
217349cc55cSDimitry Andric HTRBlockLayer ¤t_block_layer = *current_block_layer_up;
218349cc55cSDimitry Andric if (are_passes_done(*m_instruction_layer_up, *current_block_layer_up))
219349cc55cSDimitry Andric return;
220349cc55cSDimitry Andric
221349cc55cSDimitry Andric AddNewBlockLayer(std::move(current_block_layer_up));
222349cc55cSDimitry Andric while (true) {
223349cc55cSDimitry Andric HTRBlockLayerUP new_block_layer_up =
224349cc55cSDimitry Andric BasicSuperBlockMerge(current_block_layer);
225349cc55cSDimitry Andric if (are_passes_done(current_block_layer, *new_block_layer_up))
226349cc55cSDimitry Andric return;
227349cc55cSDimitry Andric
228349cc55cSDimitry Andric current_block_layer = *new_block_layer_up;
229349cc55cSDimitry Andric AddNewBlockLayer(std::move(new_block_layer_up));
230349cc55cSDimitry Andric }
231349cc55cSDimitry Andric }
232349cc55cSDimitry Andric
Export(std::string outfile)233349cc55cSDimitry Andric llvm::Error TraceHTR::Export(std::string outfile) {
234349cc55cSDimitry Andric std::error_code ec;
235349cc55cSDimitry Andric llvm::raw_fd_ostream os(outfile, ec, llvm::sys::fs::OF_Text);
236349cc55cSDimitry Andric if (ec) {
237349cc55cSDimitry Andric return llvm::make_error<llvm::StringError>(
238349cc55cSDimitry Andric "unable to open destination file: " + outfile, os.error());
239349cc55cSDimitry Andric } else {
240349cc55cSDimitry Andric os << toJSON(*this);
241349cc55cSDimitry Andric os.close();
242349cc55cSDimitry Andric if (os.has_error()) {
243349cc55cSDimitry Andric return llvm::make_error<llvm::StringError>(
244349cc55cSDimitry Andric "unable to write to destination file: " + outfile, os.error());
245349cc55cSDimitry Andric }
246349cc55cSDimitry Andric }
247349cc55cSDimitry Andric return llvm::Error::success();
248349cc55cSDimitry Andric }
249349cc55cSDimitry Andric
BasicSuperBlockMerge(IHTRLayer & layer)250349cc55cSDimitry Andric HTRBlockLayerUP lldb_private::BasicSuperBlockMerge(IHTRLayer &layer) {
251349cc55cSDimitry Andric std::unique_ptr<HTRBlockLayer> new_block_layer =
252349cc55cSDimitry Andric std::make_unique<HTRBlockLayer>(layer.GetLayerId() + 1);
253349cc55cSDimitry Andric
254349cc55cSDimitry Andric if (layer.GetNumUnits()) {
255349cc55cSDimitry Andric // Future Improvement: split this into two functions - one for finding heads
256349cc55cSDimitry Andric // and tails, one for merging/creating the next layer A 'head' is defined to
257349cc55cSDimitry Andric // be a block whose occurrences in the trace do not have a unique preceding
258349cc55cSDimitry Andric // block.
259349cc55cSDimitry Andric std::unordered_set<size_t> heads;
260349cc55cSDimitry Andric
261349cc55cSDimitry Andric // The load address of the first instruction of a block is the unique ID for
262349cc55cSDimitry Andric // that block (i.e. blocks with the same first instruction load address are
263349cc55cSDimitry Andric // the same block)
264349cc55cSDimitry Andric
265349cc55cSDimitry Andric // Future Improvement: no need to store all its preceding block ids, all we
266349cc55cSDimitry Andric // care about is that there is more than one preceding block id, so an enum
267349cc55cSDimitry Andric // could be used
268349cc55cSDimitry Andric std::unordered_map<lldb::addr_t, std::unordered_set<lldb::addr_t>> head_map;
269349cc55cSDimitry Andric lldb::addr_t prev_id =
270349cc55cSDimitry Andric layer.GetMetadataByIndex(0).GetFirstInstructionLoadAddress();
271349cc55cSDimitry Andric size_t num_units = layer.GetNumUnits();
272349cc55cSDimitry Andric // This excludes the first unit since it has no previous unit
273349cc55cSDimitry Andric for (size_t i = 1; i < num_units; i++) {
274349cc55cSDimitry Andric lldb::addr_t current_id =
275349cc55cSDimitry Andric layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress();
276349cc55cSDimitry Andric head_map[current_id].insert(prev_id);
277349cc55cSDimitry Andric prev_id = current_id;
278349cc55cSDimitry Andric }
279349cc55cSDimitry Andric for (const auto &it : head_map) {
280349cc55cSDimitry Andric // ID of 0 represents an error - errors can't be heads or tails
281349cc55cSDimitry Andric lldb::addr_t id = it.first;
282349cc55cSDimitry Andric const std::unordered_set<lldb::addr_t> predecessor_set = it.second;
283349cc55cSDimitry Andric if (id && predecessor_set.size() > 1)
284349cc55cSDimitry Andric heads.insert(id);
285349cc55cSDimitry Andric }
286349cc55cSDimitry Andric
287349cc55cSDimitry Andric // Future Improvement: identify heads and tails in the same loop
288349cc55cSDimitry Andric // A 'tail' is defined to be a block whose occurrences in the trace do
289349cc55cSDimitry Andric // not have a unique succeeding block.
290349cc55cSDimitry Andric std::unordered_set<lldb::addr_t> tails;
291349cc55cSDimitry Andric std::unordered_map<lldb::addr_t, std::unordered_set<lldb::addr_t>> tail_map;
292349cc55cSDimitry Andric
293349cc55cSDimitry Andric // This excludes the last unit since it has no next unit
294349cc55cSDimitry Andric for (size_t i = 0; i < num_units - 1; i++) {
295349cc55cSDimitry Andric lldb::addr_t current_id =
296349cc55cSDimitry Andric layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress();
297349cc55cSDimitry Andric lldb::addr_t next_id =
298349cc55cSDimitry Andric layer.GetMetadataByIndex(i + 1).GetFirstInstructionLoadAddress();
299349cc55cSDimitry Andric tail_map[current_id].insert(next_id);
300349cc55cSDimitry Andric }
301349cc55cSDimitry Andric
302349cc55cSDimitry Andric // Mark last block as tail so the algorithm stops gracefully
303349cc55cSDimitry Andric lldb::addr_t last_id = layer.GetMetadataByIndex(num_units - 1)
304349cc55cSDimitry Andric .GetFirstInstructionLoadAddress();
305349cc55cSDimitry Andric tails.insert(last_id);
306349cc55cSDimitry Andric for (const auto &it : tail_map) {
307349cc55cSDimitry Andric lldb::addr_t id = it.first;
308349cc55cSDimitry Andric const std::unordered_set<lldb::addr_t> successor_set = it.second;
309349cc55cSDimitry Andric // ID of 0 represents an error - errors can't be heads or tails
310349cc55cSDimitry Andric if (id && successor_set.size() > 1)
311349cc55cSDimitry Andric tails.insert(id);
312349cc55cSDimitry Andric }
313349cc55cSDimitry Andric
314349cc55cSDimitry Andric // Need to keep track of size of string since things we push are variable
315349cc55cSDimitry Andric // length
316349cc55cSDimitry Andric size_t superblock_size = 0;
317349cc55cSDimitry Andric // Each super block always has the same first unit (we call this the
318349cc55cSDimitry Andric // super block head) This gurantee allows us to use the super block head as
319349cc55cSDimitry Andric // the unique key mapping to the super block it begins
320bdd1243dSDimitry Andric std::optional<size_t> superblock_head;
321349cc55cSDimitry Andric auto construct_next_layer = [&](size_t merge_start, size_t n) -> void {
322349cc55cSDimitry Andric if (!superblock_head)
323349cc55cSDimitry Andric return;
324349cc55cSDimitry Andric if (new_block_layer->GetBlockById(*superblock_head)) {
325349cc55cSDimitry Andric new_block_layer->AppendRepeatedBlock(*superblock_head);
326349cc55cSDimitry Andric } else {
327349cc55cSDimitry Andric HTRBlock new_block = layer.MergeUnits(merge_start, n);
328349cc55cSDimitry Andric new_block_layer->AppendNewBlock(*superblock_head, std::move(new_block));
329349cc55cSDimitry Andric }
330349cc55cSDimitry Andric };
331349cc55cSDimitry Andric
332349cc55cSDimitry Andric for (size_t i = 0; i < num_units; i++) {
333349cc55cSDimitry Andric lldb::addr_t unit_id =
334349cc55cSDimitry Andric layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress();
335349cc55cSDimitry Andric auto isHead = heads.count(unit_id) > 0;
336349cc55cSDimitry Andric auto isTail = tails.count(unit_id) > 0;
337349cc55cSDimitry Andric
338349cc55cSDimitry Andric if (isHead && isTail) {
339349cc55cSDimitry Andric // Head logic
340349cc55cSDimitry Andric if (superblock_size) { // this handles (tail, head) adjacency -
341349cc55cSDimitry Andric // otherwise an empty
342349cc55cSDimitry Andric // block is created
343349cc55cSDimitry Andric // End previous super block
344349cc55cSDimitry Andric construct_next_layer(i - superblock_size, superblock_size);
345349cc55cSDimitry Andric }
346349cc55cSDimitry Andric // Current id is first in next super block since it's a head
347349cc55cSDimitry Andric superblock_head = unit_id;
348349cc55cSDimitry Andric superblock_size = 1;
349349cc55cSDimitry Andric
350349cc55cSDimitry Andric // Tail logic
351349cc55cSDimitry Andric construct_next_layer(i - superblock_size + 1, superblock_size);
352349cc55cSDimitry Andric // Reset the block_head since the prev super block has come to and end
353bdd1243dSDimitry Andric superblock_head = std::nullopt;
354349cc55cSDimitry Andric superblock_size = 0;
355349cc55cSDimitry Andric } else if (isHead) {
356349cc55cSDimitry Andric if (superblock_size) { // this handles (tail, head) adjacency -
357349cc55cSDimitry Andric // otherwise an empty
358349cc55cSDimitry Andric // block is created
359349cc55cSDimitry Andric // End previous super block
360349cc55cSDimitry Andric construct_next_layer(i - superblock_size, superblock_size);
361349cc55cSDimitry Andric }
362349cc55cSDimitry Andric // Current id is first in next super block since it's a head
363349cc55cSDimitry Andric superblock_head = unit_id;
364349cc55cSDimitry Andric superblock_size = 1;
365349cc55cSDimitry Andric } else if (isTail) {
366349cc55cSDimitry Andric if (!superblock_head)
367349cc55cSDimitry Andric superblock_head = unit_id;
368349cc55cSDimitry Andric superblock_size++;
369349cc55cSDimitry Andric
370349cc55cSDimitry Andric // End previous super block
371349cc55cSDimitry Andric construct_next_layer(i - superblock_size + 1, superblock_size);
372349cc55cSDimitry Andric // Reset the block_head since the prev super block has come to and end
373bdd1243dSDimitry Andric superblock_head = std::nullopt;
374349cc55cSDimitry Andric superblock_size = 0;
375349cc55cSDimitry Andric } else {
376349cc55cSDimitry Andric if (!superblock_head)
377349cc55cSDimitry Andric superblock_head = unit_id;
378349cc55cSDimitry Andric superblock_size++;
379349cc55cSDimitry Andric }
380349cc55cSDimitry Andric }
381349cc55cSDimitry Andric }
382349cc55cSDimitry Andric return new_block_layer;
383349cc55cSDimitry Andric }
384349cc55cSDimitry Andric
toJSON(const TraceHTR & htr)385349cc55cSDimitry Andric llvm::json::Value lldb_private::toJSON(const TraceHTR &htr) {
386349cc55cSDimitry Andric std::vector<llvm::json::Value> layers_as_json;
387349cc55cSDimitry Andric for (size_t i = 0; i < htr.GetInstructionLayer().GetInstructionTrace().size();
388349cc55cSDimitry Andric i++) {
389349cc55cSDimitry Andric size_t layer_id = htr.GetInstructionLayer().GetLayerId();
390349cc55cSDimitry Andric HTRBlockMetadata metadata = htr.GetInstructionLayer().GetMetadataByIndex(i);
391349cc55cSDimitry Andric lldb::addr_t load_address = metadata.GetFirstInstructionLoadAddress();
392349cc55cSDimitry Andric
393349cc55cSDimitry Andric std::string display_name;
394349cc55cSDimitry Andric
395349cc55cSDimitry Andric std::stringstream stream;
396349cc55cSDimitry Andric stream << "0x" << std::hex << load_address;
397349cc55cSDimitry Andric std::string load_address_hex_string(stream.str());
398349cc55cSDimitry Andric display_name.assign(load_address_hex_string);
399349cc55cSDimitry Andric
400349cc55cSDimitry Andric // name: load address of the first instruction of the block and the name
401349cc55cSDimitry Andric // of the most frequently called function from the block (if applicable)
402349cc55cSDimitry Andric
403349cc55cSDimitry Andric // ph: the event type - 'X' for Complete events (see link to documentation
404349cc55cSDimitry Andric // below)
405349cc55cSDimitry Andric
406349cc55cSDimitry Andric // Since trace timestamps aren't yet supported in HTR, the ts (timestamp) is
407349cc55cSDimitry Andric // based on the instruction's offset in the trace and the dur (duration) is
408349cc55cSDimitry Andric // 1 since this layer contains single instructions. Using the instruction
409349cc55cSDimitry Andric // offset and a duration of 1 oversimplifies the true timing information of
410349cc55cSDimitry Andric // the trace, nonetheless, these approximate timestamps/durations provide an
411349cc55cSDimitry Andric // clear visualization of the trace.
412349cc55cSDimitry Andric
413349cc55cSDimitry Andric // ts: offset from the beginning of the trace for the first instruction in
414349cc55cSDimitry Andric // the block
415349cc55cSDimitry Andric
416349cc55cSDimitry Andric // dur: 1 since this layer contains single instructions.
417349cc55cSDimitry Andric
418349cc55cSDimitry Andric // pid: the ID of the HTR layer the blocks belong to
419349cc55cSDimitry Andric
420349cc55cSDimitry Andric // See
421349cc55cSDimitry Andric // https://docs.google.com/document/d/1CvAClvFfyA5R-PhYUmn5OOQtYMH4h6I0nSsKchNAySU/preview#heading=h.j75x71ritcoy
422349cc55cSDimitry Andric // for documentation on the Trace Event Format
423349cc55cSDimitry Andric layers_as_json.emplace_back(llvm::json::Object{
424349cc55cSDimitry Andric {"name", display_name},
425349cc55cSDimitry Andric {"ph", "X"},
426349cc55cSDimitry Andric {"ts", (int64_t)i},
427349cc55cSDimitry Andric {"dur", 1},
428349cc55cSDimitry Andric {"pid", (int64_t)layer_id},
429349cc55cSDimitry Andric });
430349cc55cSDimitry Andric }
431349cc55cSDimitry Andric
432349cc55cSDimitry Andric for (const auto &layer : htr.GetBlockLayers()) {
433349cc55cSDimitry Andric size_t start_ts = 0;
434349cc55cSDimitry Andric std::vector<size_t> block_id_trace = layer->GetBlockIdTrace();
435349cc55cSDimitry Andric for (size_t i = 0; i < block_id_trace.size(); i++) {
436349cc55cSDimitry Andric size_t id = block_id_trace[i];
437349cc55cSDimitry Andric // Guranteed that this ID is valid, so safe to dereference here.
438349cc55cSDimitry Andric HTRBlock block = *layer->GetBlockById(id);
439349cc55cSDimitry Andric llvm::json::Value block_json = toJSON(block);
440349cc55cSDimitry Andric size_t layer_id = layer->GetLayerId();
441349cc55cSDimitry Andric
442349cc55cSDimitry Andric HTRBlockMetadata metadata = block.GetMetadata();
443349cc55cSDimitry Andric
444bdd1243dSDimitry Andric std::optional<llvm::StringRef> most_freq_func =
445349cc55cSDimitry Andric metadata.GetMostFrequentlyCalledFunction();
446349cc55cSDimitry Andric std::stringstream stream;
447349cc55cSDimitry Andric stream << "0x" << std::hex << metadata.GetFirstInstructionLoadAddress();
448349cc55cSDimitry Andric std::string offset_hex_string(stream.str());
449349cc55cSDimitry Andric std::string display_name =
450349cc55cSDimitry Andric most_freq_func ? offset_hex_string + ": " + most_freq_func->str()
451349cc55cSDimitry Andric : offset_hex_string;
452349cc55cSDimitry Andric
453349cc55cSDimitry Andric // Since trace timestamps aren't yet supported in HTR, the ts (timestamp)
454349cc55cSDimitry Andric // and dur (duration) are based on the block's offset in the trace and
455349cc55cSDimitry Andric // number of instructions in the block, respectively. Using the block
456349cc55cSDimitry Andric // offset and the number of instructions oversimplifies the true timing
457349cc55cSDimitry Andric // information of the trace, nonetheless, these approximate
458349cc55cSDimitry Andric // timestamps/durations provide an understandable visualization of the
459349cc55cSDimitry Andric // trace.
460349cc55cSDimitry Andric auto duration = metadata.GetNumInstructions();
461349cc55cSDimitry Andric layers_as_json.emplace_back(llvm::json::Object{
462349cc55cSDimitry Andric {"name", display_name},
463349cc55cSDimitry Andric {"ph", "X"},
464349cc55cSDimitry Andric {"ts", (int64_t)start_ts},
465349cc55cSDimitry Andric {"dur", (int64_t)duration},
466349cc55cSDimitry Andric {"pid", (int64_t)layer_id},
467349cc55cSDimitry Andric {"args", block_json},
468349cc55cSDimitry Andric });
469349cc55cSDimitry Andric start_ts += duration;
470349cc55cSDimitry Andric }
471349cc55cSDimitry Andric }
472349cc55cSDimitry Andric return layers_as_json;
473349cc55cSDimitry Andric }
474349cc55cSDimitry Andric
toJSON(const HTRBlock & block)475349cc55cSDimitry Andric llvm::json::Value lldb_private::toJSON(const HTRBlock &block) {
476349cc55cSDimitry Andric return llvm::json::Value(
477349cc55cSDimitry Andric llvm::json::Object{{"Metadata", block.GetMetadata()}});
478349cc55cSDimitry Andric }
479349cc55cSDimitry Andric
toJSON(const HTRBlockMetadata & metadata)480349cc55cSDimitry Andric llvm::json::Value lldb_private::toJSON(const HTRBlockMetadata &metadata) {
481349cc55cSDimitry Andric std::vector<llvm::json::Value> function_calls;
482349cc55cSDimitry Andric for (const auto &it : metadata.GetFunctionCalls()) {
483349cc55cSDimitry Andric ConstString name = it.first;
484349cc55cSDimitry Andric size_t n_calls = it.second;
485349cc55cSDimitry Andric function_calls.emplace_back(llvm::formatv("({0}: {1})", name, n_calls));
486349cc55cSDimitry Andric }
487349cc55cSDimitry Andric
488349cc55cSDimitry Andric return llvm::json::Value(llvm::json::Object{
489349cc55cSDimitry Andric {"Number of Instructions", (ssize_t)metadata.GetNumInstructions()},
490349cc55cSDimitry Andric {"Functions", function_calls}});
491349cc55cSDimitry Andric }
492