1 //===-- TraceHTR.cpp ------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "TraceHTR.h" 10 11 #include "lldb/Symbol/Function.h" 12 #include "lldb/Target/Process.h" 13 #include "lldb/Target/Target.h" 14 #include "llvm/Support/JSON.h" 15 #include <sstream> 16 #include <string> 17 18 using namespace lldb_private; 19 using namespace lldb; 20 21 size_t HTRBlockMetadata::GetNumInstructions() const { 22 return m_num_instructions; 23 } 24 25 llvm::Optional<llvm::StringRef> 26 HTRBlockMetadata::GetMostFrequentlyCalledFunction() const { 27 size_t max_ncalls = 0; 28 llvm::Optional<llvm::StringRef> max_name = llvm::None; 29 for (const auto &it : m_func_calls) { 30 ConstString name = it.first; 31 size_t ncalls = it.second; 32 if (ncalls > max_ncalls) { 33 max_ncalls = ncalls; 34 max_name = name.GetStringRef(); 35 } 36 } 37 return max_name; 38 } 39 40 llvm::DenseMap<ConstString, size_t> const & 41 HTRBlockMetadata::GetFunctionCalls() const { 42 return m_func_calls; 43 } 44 45 lldb::addr_t HTRBlockMetadata::GetFirstInstructionLoadAddress() const { 46 return m_first_instruction_load_address; 47 } 48 49 size_t HTRBlock::GetOffset() const { return m_offset; } 50 51 size_t HTRBlock::GetSize() const { return m_size; } 52 53 HTRBlockMetadata const &HTRBlock::GetMetadata() const { return m_metadata; } 54 55 llvm::ArrayRef<HTRBlockLayerUP> TraceHTR::GetBlockLayers() const { 56 return m_block_layer_ups; 57 } 58 59 HTRInstructionLayer const &TraceHTR::GetInstructionLayer() const { 60 return *m_instruction_layer_up; 61 } 62 63 void TraceHTR::AddNewBlockLayer(HTRBlockLayerUP &&block_layer) { 64 m_block_layer_ups.emplace_back(std::move(block_layer)); 65 } 66 67 size_t IHTRLayer::GetLayerId() const { return m_layer_id; } 68 69 void HTRBlockLayer::AppendNewBlock(size_t block_id, HTRBlock &&block) { 70 m_block_id_trace.emplace_back(block_id); 71 m_block_defs.emplace(block_id, block); 72 } 73 74 void HTRBlockLayer::AppendRepeatedBlock(size_t block_id) { 75 m_block_id_trace.emplace_back(block_id); 76 } 77 78 llvm::ArrayRef<lldb::addr_t> HTRInstructionLayer::GetInstructionTrace() const { 79 return m_instruction_trace; 80 } 81 82 void HTRInstructionLayer::AddCallInstructionMetadata( 83 lldb::addr_t load_addr, llvm::Optional<ConstString> func_name) { 84 m_call_isns.emplace(load_addr, func_name); 85 } 86 87 void HTRInstructionLayer::AppendInstruction(lldb::addr_t load_addr) { 88 m_instruction_trace.emplace_back(load_addr); 89 } 90 91 HTRBlock const *HTRBlockLayer::GetBlockById(size_t block_id) const { 92 auto block_it = m_block_defs.find(block_id); 93 if (block_it == m_block_defs.end()) 94 return nullptr; 95 else 96 return &block_it->second; 97 } 98 99 llvm::ArrayRef<size_t> HTRBlockLayer::GetBlockIdTrace() const { 100 return m_block_id_trace; 101 } 102 103 size_t HTRBlockLayer::GetNumUnits() const { return m_block_id_trace.size(); } 104 105 HTRBlockMetadata HTRInstructionLayer::GetMetadataByIndex(size_t index) const { 106 lldb::addr_t instruction_load_address = m_instruction_trace[index]; 107 llvm::DenseMap<ConstString, size_t> func_calls; 108 109 auto func_name_it = m_call_isns.find(instruction_load_address); 110 if (func_name_it != m_call_isns.end()) { 111 if (llvm::Optional<ConstString> func_name = func_name_it->second) { 112 func_calls[*func_name] = 1; 113 } 114 } 115 return {instruction_load_address, 1, std::move(func_calls)}; 116 } 117 118 size_t HTRInstructionLayer::GetNumUnits() const { 119 return m_instruction_trace.size(); 120 } 121 122 HTRBlockMetadata HTRBlockLayer::GetMetadataByIndex(size_t index) const { 123 size_t block_id = m_block_id_trace[index]; 124 HTRBlock block = m_block_defs.find(block_id)->second; 125 return block.GetMetadata(); 126 } 127 128 TraceHTR::TraceHTR(Thread &thread, TraceCursor &cursor) 129 : m_instruction_layer_up(std::make_unique<HTRInstructionLayer>(0)) { 130 131 // Move cursor to the first instruction in the trace 132 cursor.SetForwards(true); 133 cursor.Seek(0, TraceCursor::SeekType::Beginning); 134 135 // TODO: fix after persona0220's patch on a new way to access instruction 136 // kinds 137 /* 138 Target &target = thread.GetProcess()->GetTarget(); 139 auto function_name_from_load_address = 140 [&](lldb::addr_t load_address) -> llvm::Optional<ConstString> { 141 lldb_private::Address pc_addr; 142 SymbolContext sc; 143 if (target.ResolveLoadAddress(load_address, pc_addr) && 144 pc_addr.CalculateSymbolContext(&sc)) 145 return sc.GetFunctionName() 146 ? llvm::Optional<ConstString>(sc.GetFunctionName()) 147 : llvm::None; 148 else 149 return llvm::None; 150 }; 151 152 while (cursor.HasValue()) { if (cursor.IsError()) { 153 // Append a load address of 0 for all instructions that an error occured 154 // while decoding. 155 // TODO: Make distinction between errors by storing the error messages. 156 // Currently, all errors are treated the same. 157 m_instruction_layer_up->AppendInstruction(0); 158 cursor.Next(); 159 } else if (cursor.IsEvent()) { 160 cursor.Next(); 161 } else { 162 lldb::addr_t current_instruction_load_address = cursor.GetLoadAddress(); 163 lldb::InstructionControlFlowKind current_instruction_type = 164 cursor.GetInstructionControlFlowKind(); 165 166 m_instruction_layer_up->AppendInstruction( 167 current_instruction_load_address); 168 cursor.Next(); 169 bool more_data_in_trace = cursor.HasValue(); 170 if (current_instruction_type & 171 lldb::eInstructionControlFlowKindCall) { 172 if (more_data_in_trace && !cursor.IsError()) { 173 m_instruction_layer_up->AddCallInstructionMetadata( 174 current_instruction_load_address, 175 function_name_from_load_address(cursor.GetLoadAddress())); 176 } else { 177 // Next instruction is not known - pass None to indicate the name 178 // of the function being called is not known 179 m_instruction_layer_up->AddCallInstructionMetadata( 180 current_instruction_load_address, llvm::None); 181 } 182 } 183 } 184 } 185 */ 186 } 187 188 void HTRBlockMetadata::MergeMetadata( 189 HTRBlockMetadata &merged_metadata, 190 HTRBlockMetadata const &metadata_to_merge) { 191 merged_metadata.m_num_instructions += metadata_to_merge.m_num_instructions; 192 for (const auto &it : metadata_to_merge.m_func_calls) { 193 ConstString name = it.first; 194 size_t num_calls = it.second; 195 merged_metadata.m_func_calls[name] += num_calls; 196 } 197 } 198 199 HTRBlock IHTRLayer::MergeUnits(size_t start_unit_index, size_t num_units) { 200 // TODO: make this function take `end_unit_index` as a parameter instead of 201 // unit and merge the range [start_unit_indx, end_unit_index] inclusive. 202 HTRBlockMetadata merged_metadata = GetMetadataByIndex(start_unit_index); 203 for (size_t i = start_unit_index + 1; i < start_unit_index + num_units; i++) { 204 // merge the new metadata into merged_metadata 205 HTRBlockMetadata::MergeMetadata(merged_metadata, GetMetadataByIndex(i)); 206 } 207 return {start_unit_index, num_units, merged_metadata}; 208 } 209 210 void TraceHTR::ExecutePasses() { 211 auto are_passes_done = [](IHTRLayer &l1, IHTRLayer &l2) { 212 return l1.GetNumUnits() == l2.GetNumUnits(); 213 }; 214 HTRBlockLayerUP current_block_layer_up = 215 BasicSuperBlockMerge(*m_instruction_layer_up); 216 HTRBlockLayer ¤t_block_layer = *current_block_layer_up; 217 if (are_passes_done(*m_instruction_layer_up, *current_block_layer_up)) 218 return; 219 220 AddNewBlockLayer(std::move(current_block_layer_up)); 221 while (true) { 222 HTRBlockLayerUP new_block_layer_up = 223 BasicSuperBlockMerge(current_block_layer); 224 if (are_passes_done(current_block_layer, *new_block_layer_up)) 225 return; 226 227 current_block_layer = *new_block_layer_up; 228 AddNewBlockLayer(std::move(new_block_layer_up)); 229 } 230 } 231 232 llvm::Error TraceHTR::Export(std::string outfile) { 233 std::error_code ec; 234 llvm::raw_fd_ostream os(outfile, ec, llvm::sys::fs::OF_Text); 235 if (ec) { 236 return llvm::make_error<llvm::StringError>( 237 "unable to open destination file: " + outfile, os.error()); 238 } else { 239 os << toJSON(*this); 240 os.close(); 241 if (os.has_error()) { 242 return llvm::make_error<llvm::StringError>( 243 "unable to write to destination file: " + outfile, os.error()); 244 } 245 } 246 return llvm::Error::success(); 247 } 248 249 HTRBlockLayerUP lldb_private::BasicSuperBlockMerge(IHTRLayer &layer) { 250 std::unique_ptr<HTRBlockLayer> new_block_layer = 251 std::make_unique<HTRBlockLayer>(layer.GetLayerId() + 1); 252 253 if (layer.GetNumUnits()) { 254 // Future Improvement: split this into two functions - one for finding heads 255 // and tails, one for merging/creating the next layer A 'head' is defined to 256 // be a block whose occurrences in the trace do not have a unique preceding 257 // block. 258 std::unordered_set<size_t> heads; 259 260 // The load address of the first instruction of a block is the unique ID for 261 // that block (i.e. blocks with the same first instruction load address are 262 // the same block) 263 264 // Future Improvement: no need to store all its preceding block ids, all we 265 // care about is that there is more than one preceding block id, so an enum 266 // could be used 267 std::unordered_map<lldb::addr_t, std::unordered_set<lldb::addr_t>> head_map; 268 lldb::addr_t prev_id = 269 layer.GetMetadataByIndex(0).GetFirstInstructionLoadAddress(); 270 size_t num_units = layer.GetNumUnits(); 271 // This excludes the first unit since it has no previous unit 272 for (size_t i = 1; i < num_units; i++) { 273 lldb::addr_t current_id = 274 layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress(); 275 head_map[current_id].insert(prev_id); 276 prev_id = current_id; 277 } 278 for (const auto &it : head_map) { 279 // ID of 0 represents an error - errors can't be heads or tails 280 lldb::addr_t id = it.first; 281 const std::unordered_set<lldb::addr_t> predecessor_set = it.second; 282 if (id && predecessor_set.size() > 1) 283 heads.insert(id); 284 } 285 286 // Future Improvement: identify heads and tails in the same loop 287 // A 'tail' is defined to be a block whose occurrences in the trace do 288 // not have a unique succeeding block. 289 std::unordered_set<lldb::addr_t> tails; 290 std::unordered_map<lldb::addr_t, std::unordered_set<lldb::addr_t>> tail_map; 291 292 // This excludes the last unit since it has no next unit 293 for (size_t i = 0; i < num_units - 1; i++) { 294 lldb::addr_t current_id = 295 layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress(); 296 lldb::addr_t next_id = 297 layer.GetMetadataByIndex(i + 1).GetFirstInstructionLoadAddress(); 298 tail_map[current_id].insert(next_id); 299 } 300 301 // Mark last block as tail so the algorithm stops gracefully 302 lldb::addr_t last_id = layer.GetMetadataByIndex(num_units - 1) 303 .GetFirstInstructionLoadAddress(); 304 tails.insert(last_id); 305 for (const auto &it : tail_map) { 306 lldb::addr_t id = it.first; 307 const std::unordered_set<lldb::addr_t> successor_set = it.second; 308 // ID of 0 represents an error - errors can't be heads or tails 309 if (id && successor_set.size() > 1) 310 tails.insert(id); 311 } 312 313 // Need to keep track of size of string since things we push are variable 314 // length 315 size_t superblock_size = 0; 316 // Each super block always has the same first unit (we call this the 317 // super block head) This gurantee allows us to use the super block head as 318 // the unique key mapping to the super block it begins 319 llvm::Optional<size_t> superblock_head = llvm::None; 320 auto construct_next_layer = [&](size_t merge_start, size_t n) -> void { 321 if (!superblock_head) 322 return; 323 if (new_block_layer->GetBlockById(*superblock_head)) { 324 new_block_layer->AppendRepeatedBlock(*superblock_head); 325 } else { 326 HTRBlock new_block = layer.MergeUnits(merge_start, n); 327 new_block_layer->AppendNewBlock(*superblock_head, std::move(new_block)); 328 } 329 }; 330 331 for (size_t i = 0; i < num_units; i++) { 332 lldb::addr_t unit_id = 333 layer.GetMetadataByIndex(i).GetFirstInstructionLoadAddress(); 334 auto isHead = heads.count(unit_id) > 0; 335 auto isTail = tails.count(unit_id) > 0; 336 337 if (isHead && isTail) { 338 // Head logic 339 if (superblock_size) { // this handles (tail, head) adjacency - 340 // otherwise an empty 341 // block is created 342 // End previous super block 343 construct_next_layer(i - superblock_size, superblock_size); 344 } 345 // Current id is first in next super block since it's a head 346 superblock_head = unit_id; 347 superblock_size = 1; 348 349 // Tail logic 350 construct_next_layer(i - superblock_size + 1, superblock_size); 351 // Reset the block_head since the prev super block has come to and end 352 superblock_head = llvm::None; 353 superblock_size = 0; 354 } else if (isHead) { 355 if (superblock_size) { // this handles (tail, head) adjacency - 356 // otherwise an empty 357 // block is created 358 // End previous super block 359 construct_next_layer(i - superblock_size, superblock_size); 360 } 361 // Current id is first in next super block since it's a head 362 superblock_head = unit_id; 363 superblock_size = 1; 364 } else if (isTail) { 365 if (!superblock_head) 366 superblock_head = unit_id; 367 superblock_size++; 368 369 // End previous super block 370 construct_next_layer(i - superblock_size + 1, superblock_size); 371 // Reset the block_head since the prev super block has come to and end 372 superblock_head = llvm::None; 373 superblock_size = 0; 374 } else { 375 if (!superblock_head) 376 superblock_head = unit_id; 377 superblock_size++; 378 } 379 } 380 } 381 return new_block_layer; 382 } 383 384 llvm::json::Value lldb_private::toJSON(const TraceHTR &htr) { 385 std::vector<llvm::json::Value> layers_as_json; 386 for (size_t i = 0; i < htr.GetInstructionLayer().GetInstructionTrace().size(); 387 i++) { 388 size_t layer_id = htr.GetInstructionLayer().GetLayerId(); 389 HTRBlockMetadata metadata = htr.GetInstructionLayer().GetMetadataByIndex(i); 390 lldb::addr_t load_address = metadata.GetFirstInstructionLoadAddress(); 391 392 std::string display_name; 393 394 std::stringstream stream; 395 stream << "0x" << std::hex << load_address; 396 std::string load_address_hex_string(stream.str()); 397 display_name.assign(load_address_hex_string); 398 399 // name: load address of the first instruction of the block and the name 400 // of the most frequently called function from the block (if applicable) 401 402 // ph: the event type - 'X' for Complete events (see link to documentation 403 // below) 404 405 // Since trace timestamps aren't yet supported in HTR, the ts (timestamp) is 406 // based on the instruction's offset in the trace and the dur (duration) is 407 // 1 since this layer contains single instructions. Using the instruction 408 // offset and a duration of 1 oversimplifies the true timing information of 409 // the trace, nonetheless, these approximate timestamps/durations provide an 410 // clear visualization of the trace. 411 412 // ts: offset from the beginning of the trace for the first instruction in 413 // the block 414 415 // dur: 1 since this layer contains single instructions. 416 417 // pid: the ID of the HTR layer the blocks belong to 418 419 // See 420 // https://docs.google.com/document/d/1CvAClvFfyA5R-PhYUmn5OOQtYMH4h6I0nSsKchNAySU/preview#heading=h.j75x71ritcoy 421 // for documentation on the Trace Event Format 422 layers_as_json.emplace_back(llvm::json::Object{ 423 {"name", display_name}, 424 {"ph", "X"}, 425 {"ts", (int64_t)i}, 426 {"dur", 1}, 427 {"pid", (int64_t)layer_id}, 428 }); 429 } 430 431 for (const auto &layer : htr.GetBlockLayers()) { 432 size_t start_ts = 0; 433 std::vector<size_t> block_id_trace = layer->GetBlockIdTrace(); 434 for (size_t i = 0; i < block_id_trace.size(); i++) { 435 size_t id = block_id_trace[i]; 436 // Guranteed that this ID is valid, so safe to dereference here. 437 HTRBlock block = *layer->GetBlockById(id); 438 llvm::json::Value block_json = toJSON(block); 439 size_t layer_id = layer->GetLayerId(); 440 441 HTRBlockMetadata metadata = block.GetMetadata(); 442 443 llvm::Optional<llvm::StringRef> most_freq_func = 444 metadata.GetMostFrequentlyCalledFunction(); 445 std::stringstream stream; 446 stream << "0x" << std::hex << metadata.GetFirstInstructionLoadAddress(); 447 std::string offset_hex_string(stream.str()); 448 std::string display_name = 449 most_freq_func ? offset_hex_string + ": " + most_freq_func->str() 450 : offset_hex_string; 451 452 // Since trace timestamps aren't yet supported in HTR, the ts (timestamp) 453 // and dur (duration) are based on the block's offset in the trace and 454 // number of instructions in the block, respectively. Using the block 455 // offset and the number of instructions oversimplifies the true timing 456 // information of the trace, nonetheless, these approximate 457 // timestamps/durations provide an understandable visualization of the 458 // trace. 459 auto duration = metadata.GetNumInstructions(); 460 layers_as_json.emplace_back(llvm::json::Object{ 461 {"name", display_name}, 462 {"ph", "X"}, 463 {"ts", (int64_t)start_ts}, 464 {"dur", (int64_t)duration}, 465 {"pid", (int64_t)layer_id}, 466 {"args", block_json}, 467 }); 468 start_ts += duration; 469 } 470 } 471 return layers_as_json; 472 } 473 474 llvm::json::Value lldb_private::toJSON(const HTRBlock &block) { 475 return llvm::json::Value( 476 llvm::json::Object{{"Metadata", block.GetMetadata()}}); 477 } 478 479 llvm::json::Value lldb_private::toJSON(const HTRBlockMetadata &metadata) { 480 std::vector<llvm::json::Value> function_calls; 481 for (const auto &it : metadata.GetFunctionCalls()) { 482 ConstString name = it.first; 483 size_t n_calls = it.second; 484 function_calls.emplace_back(llvm::formatv("({0}: {1})", name, n_calls)); 485 } 486 487 return llvm::json::Value(llvm::json::Object{ 488 {"Number of Instructions", (ssize_t)metadata.GetNumInstructions()}, 489 {"Functions", function_calls}}); 490 } 491