lldb/source/Target/TraceDumper.cpp

   1 //===-- TraceDumper.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 "lldb/Target/TraceDumper.h"
  10 #include "lldb/Core/Module.h"
  11 #include "lldb/Symbol/CompileUnit.h"
  12 #include "lldb/Symbol/Function.h"
  13 #include "lldb/Target/ExecutionContext.h"
  14 #include "lldb/Target/Process.h"
  15 #include "lldb/Target/SectionLoadList.h"
  16 #include <optional>
  17
  18 using namespace lldb;
  19 using namespace lldb_private;
  20 using namespace llvm;
  21
  22 /// \return
  23 ///   The given string or \b std::nullopt if it's empty.
  24 static std::optional<const char *> ToOptionalString(const char *s) {
  25   if (!s)
  26     return std::nullopt;
  27   return s;
  28 }
  29
  30 static const char *GetModuleName(const SymbolContext &sc) {
  31   if (!sc.module_sp)
  32     return nullptr;
  33   return sc.module_sp->GetFileSpec().GetFilename().AsCString();
  34 }
  35
  36 /// \return
  37 ///   The module name (basename if the module is a file, or the actual name if
  38 ///   it's a virtual module), or \b nullptr if no name nor module was found.
  39 static const char *GetModuleName(const TraceDumper::TraceItem &item) {
  40   if (!item.symbol_info)
  41     return nullptr;
  42   return GetModuleName(item.symbol_info->sc);
  43 }
  44
  45 // This custom LineEntry validator is neded because some line_entries have
  46 // 0 as line, which is meaningless. Notice that LineEntry::IsValid only
  47 // checks that line is not LLDB_INVALID_LINE_NUMBER, i.e. UINT32_MAX.
  48 static bool IsLineEntryValid(const LineEntry &line_entry) {
  49   return line_entry.IsValid() && line_entry.line > 0;
  50 }
  51
  52 /// \return
  53 ///     \b true if the provided line entries match line, column and source file.
  54 ///     This function assumes that the line entries are valid.
  55 static bool FileLineAndColumnMatches(const LineEntry &a, const LineEntry &b) {
  56   if (a.line != b.line)
  57     return false;
  58   if (a.column != b.column)
  59     return false;
  60   return a.file == b.file;
  61 }
  62
  63 /// Compare the symbol contexts of the provided \a SymbolInfo
  64 /// objects.
  65 ///
  66 /// \return
  67 ///     \a true if both instructions belong to the same scope level analized
  68 ///     in the following order:
  69 ///       - module
  70 ///       - symbol
  71 ///       - function
  72 ///       - inlined function
  73 ///       - source line info
  74 static bool
  75 IsSameInstructionSymbolContext(const TraceDumper::SymbolInfo &prev_insn,
  76                                const TraceDumper::SymbolInfo &insn,
  77                                bool check_source_line_info = true) {
  78   // module checks
  79   if (insn.sc.module_sp != prev_insn.sc.module_sp)
  80     return false;
  81
  82   // symbol checks
  83   if (insn.sc.symbol != prev_insn.sc.symbol)
  84     return false;
  85
  86   // function checks
  87   if (!insn.sc.function && !prev_insn.sc.function)
  88     return true; // This means two dangling instruction in the same module. We
  89                  // can assume they are part of the same unnamed symbol
  90   else if (insn.sc.function != prev_insn.sc.function)
  91     return false;
  92
  93   Block *inline_block_a =
  94       insn.sc.block ? insn.sc.block->GetContainingInlinedBlock() : nullptr;
  95   Block *inline_block_b = prev_insn.sc.block
  96                               ? prev_insn.sc.block->GetContainingInlinedBlock()
  97                               : nullptr;
  98   if (inline_block_a != inline_block_b)
  99     return false;
 100
 101   // line entry checks
 102   if (!check_source_line_info)
 103     return true;
 104
 105   const bool curr_line_valid = IsLineEntryValid(insn.sc.line_entry);
 106   const bool prev_line_valid = IsLineEntryValid(prev_insn.sc.line_entry);
 107   if (curr_line_valid && prev_line_valid)
 108     return FileLineAndColumnMatches(insn.sc.line_entry,
 109                                     prev_insn.sc.line_entry);
 110   return curr_line_valid == prev_line_valid;
 111 }
 112
 113 class OutputWriterCLI : public TraceDumper::OutputWriter {
 114 public:
 115   OutputWriterCLI(Stream &s, const TraceDumperOptions &options, Thread &thread)
 116       : m_s(s), m_options(options) {
 117     m_s.Format("thread #{0}: tid = {1}\n", thread.GetIndexID(), thread.GetID());
 118   };
 119
 120   void NoMoreData() override { m_s << "    no more data\n"; }
 121
 122   void FunctionCallForest(
 123       const std::vector<TraceDumper::FunctionCallUP> &forest) override {
 124     for (size_t i = 0; i < forest.size(); i++) {
 125       m_s.Format("\n[call tree #{0}]\n", i);
 126       DumpFunctionCallTree(*forest[i]);
 127     }
 128   }
 129
 130   void TraceItem(const TraceDumper::TraceItem &item) override {
 131     if (item.symbol_info) {
 132       if (!item.prev_symbol_info ||
 133           !IsSameInstructionSymbolContext(*item.prev_symbol_info,
 134                                           *item.symbol_info)) {
 135         m_s << "  ";
 136         const char *module_name = GetModuleName(item);
 137         if (!module_name)
 138           m_s << "(none)";
 139         else if (!item.symbol_info->sc.function && !item.symbol_info->sc.symbol)
 140           m_s.Format("{0}`(none)", module_name);
 141         else
 142           item.symbol_info->sc.DumpStopContext(
 143               &m_s, item.symbol_info->exe_ctx.GetTargetPtr(),
 144               item.symbol_info->address,
 145               /*show_fullpaths=*/false,
 146               /*show_module=*/true, /*show_inlined_frames=*/false,
 147               /*show_function_arguments=*/true,
 148               /*show_function_name=*/true);
 149         m_s << "\n";
 150       }
 151     }
 152
 153     if (item.error && !m_was_prev_instruction_an_error)
 154       m_s << "    ...missing instructions\n";
 155
 156     m_s.Format("    {0}: ", item.id);
 157
 158     if (m_options.show_timestamps) {
 159       m_s.Format("[{0}] ", item.timestamp
 160                                ? formatv("{0:3} ns", *item.timestamp).str()
 161                                : "unavailable");
 162     }
 163
 164     if (item.event) {
 165       m_s << "(event) " << TraceCursor::EventKindToString(*item.event);
 166       switch (*item.event) {
 167       case eTraceEventCPUChanged:
 168         m_s.Format(" [new CPU={0}]",
 169                    item.cpu_id ? std::to_string(*item.cpu_id) : "unavailable");
 170         break;
 171       case eTraceEventHWClockTick:
 172         m_s.Format(" [{0}]", item.hw_clock ? std::to_string(*item.hw_clock)
 173                                            : "unavailable");
 174         break;
 175       case eTraceEventDisabledHW:
 176       case eTraceEventDisabledSW:
 177         break;
 178       case eTraceEventSyncPoint:
 179         m_s.Format(" [{0}]", item.sync_point_metadata);
 180         break;
 181       }
 182     } else if (item.error) {
 183       m_s << "(error) " << *item.error;
 184     } else {
 185       m_s.Format("{0:x+16}", item.load_address);
 186       if (item.symbol_info && item.symbol_info->instruction) {
 187         m_s << "    ";
 188         item.symbol_info->instruction->Dump(
 189             &m_s, /*max_opcode_byte_size=*/0,
 190             /*show_address=*/false,
 191             /*show_bytes=*/false, m_options.show_control_flow_kind,
 192             &item.symbol_info->exe_ctx, &item.symbol_info->sc,
 193             /*prev_sym_ctx=*/nullptr,
 194             /*disassembly_addr_format=*/nullptr,
 195             /*max_address_text_size=*/0);
 196       }
 197     }
 198
 199     m_was_prev_instruction_an_error = (bool)item.error;
 200     m_s << "\n";
 201   }
 202
 203 private:
 204   void
 205   DumpSegmentContext(const TraceDumper::FunctionCall::TracedSegment &segment) {
 206     if (segment.GetOwningCall().IsError()) {
 207       m_s << "<tracing errors>";
 208       return;
 209     }
 210
 211     const SymbolContext &first_sc = segment.GetFirstInstructionSymbolInfo().sc;
 212     first_sc.DumpStopContext(
 213         &m_s, segment.GetFirstInstructionSymbolInfo().exe_ctx.GetTargetPtr(),
 214         segment.GetFirstInstructionSymbolInfo().address,
 215         /*show_fullpaths=*/false,
 216         /*show_module=*/true, /*show_inlined_frames=*/false,
 217         /*show_function_arguments=*/true,
 218         /*show_function_name=*/true);
 219     m_s << " to ";
 220     const SymbolContext &last_sc = segment.GetLastInstructionSymbolInfo().sc;
 221     if (IsLineEntryValid(first_sc.line_entry) &&
 222         IsLineEntryValid(last_sc.line_entry)) {
 223       m_s.Format("{0}:{1}", last_sc.line_entry.line, last_sc.line_entry.column);
 224     } else {
 225       last_sc.DumpStopContext(
 226           &m_s, segment.GetFirstInstructionSymbolInfo().exe_ctx.GetTargetPtr(),
 227           segment.GetLastInstructionSymbolInfo().address,
 228           /*show_fullpaths=*/false,
 229           /*show_module=*/false, /*show_inlined_frames=*/false,
 230           /*show_function_arguments=*/false,
 231           /*show_function_name=*/false);
 232     }
 233   }
 234
 235   void DumpUntracedContext(const TraceDumper::FunctionCall &function_call) {
 236     if (function_call.IsError()) {
 237       m_s << "tracing error";
 238     }
 239     const SymbolContext &sc = function_call.GetSymbolInfo().sc;
 240
 241     const char *module_name = GetModuleName(sc);
 242     if (!module_name)
 243       m_s << "(none)";
 244     else if (!sc.function && !sc.symbol)
 245       m_s << module_name << "`(none)";
 246     else
 247       m_s << module_name << "`" << sc.GetFunctionName().AsCString();
 248   }
 249
 250   void DumpFunctionCallTree(const TraceDumper::FunctionCall &function_call) {
 251     if (function_call.GetUntracedPrefixSegment()) {
 252       m_s.Indent();
 253       DumpUntracedContext(function_call);
 254       m_s << "\n";
 255
 256       m_s.IndentMore();
 257       DumpFunctionCallTree(function_call.GetUntracedPrefixSegment()->GetNestedCall());
 258       m_s.IndentLess();
 259     }
 260
 261     for (const TraceDumper::FunctionCall::TracedSegment &segment :
 262          function_call.GetTracedSegments()) {
 263       m_s.Indent();
 264       DumpSegmentContext(segment);
 265       m_s.Format("  [{0}, {1}]\n", segment.GetFirstInstructionID(),
 266                  segment.GetLastInstructionID());
 267
 268       segment.IfNestedCall([&](const TraceDumper::FunctionCall &nested_call) {
 269         m_s.IndentMore();
 270         DumpFunctionCallTree(nested_call);
 271         m_s.IndentLess();
 272       });
 273     }
 274   }
 275
 276   Stream &m_s;
 277   TraceDumperOptions m_options;
 278   bool m_was_prev_instruction_an_error = false;
 279 };
 280
 281 class OutputWriterJSON : public TraceDumper::OutputWriter {
 282   /* schema:
 283     error_message: string
 284     | {
 285       "event": string,
 286       "id": decimal,
 287       "tsc"?: string decimal,
 288       "cpuId"? decimal,
 289     } | {
 290       "error": string,
 291       "id": decimal,
 292       "tsc"?: string decimal,
 293     | {
 294       "loadAddress": string decimal,
 295       "id": decimal,
 296       "hwClock"?: string decimal,
 297       "syncPointMetadata"?: string,
 298       "timestamp_ns"?: string decimal,
 299       "module"?: string,
 300       "symbol"?: string,
 301       "line"?: decimal,
 302       "column"?: decimal,
 303       "source"?: string,
 304       "mnemonic"?: string,
 305       "controlFlowKind"?: string,
 306     }
 307   */
 308 public:
 309   OutputWriterJSON(Stream &s, const TraceDumperOptions &options)
 310       : m_s(s), m_options(options),
 311         m_j(m_s.AsRawOstream(),
 312             /*IndentSize=*/options.pretty_print_json ? 2 : 0) {
 313     m_j.arrayBegin();
 314   };
 315
 316   ~OutputWriterJSON() { m_j.arrayEnd(); }
 317
 318   void FunctionCallForest(
 319       const std::vector<TraceDumper::FunctionCallUP> &forest) override {
 320     for (size_t i = 0; i < forest.size(); i++) {
 321       m_j.object([&] { DumpFunctionCallTree(*forest[i]); });
 322     }
 323   }
 324
 325   void DumpFunctionCallTree(const TraceDumper::FunctionCall &function_call) {
 326     if (function_call.GetUntracedPrefixSegment()) {
 327       m_j.attributeObject("untracedPrefixSegment", [&] {
 328         m_j.attributeObject("nestedCall", [&] {
 329           DumpFunctionCallTree(
 330               function_call.GetUntracedPrefixSegment()->GetNestedCall());
 331         });
 332       });
 333     }
 334
 335     if (!function_call.GetTracedSegments().empty()) {
 336       m_j.attributeArray("tracedSegments", [&] {
 337         for (const TraceDumper::FunctionCall::TracedSegment &segment :
 338              function_call.GetTracedSegments()) {
 339           m_j.object([&] {
 340             m_j.attribute("firstInstructionId",
 341                           std::to_string(segment.GetFirstInstructionID()));
 342             m_j.attribute("lastInstructionId",
 343                           std::to_string(segment.GetLastInstructionID()));
 344             segment.IfNestedCall(
 345                 [&](const TraceDumper::FunctionCall &nested_call) {
 346                   m_j.attributeObject(
 347                       "nestedCall", [&] { DumpFunctionCallTree(nested_call); });
 348                 });
 349           });
 350         }
 351       });
 352     }
 353   }
 354
 355   void DumpEvent(const TraceDumper::TraceItem &item) {
 356     m_j.attribute("event", TraceCursor::EventKindToString(*item.event));
 357     switch (*item.event) {
 358     case eTraceEventCPUChanged:
 359       m_j.attribute("cpuId", item.cpu_id);
 360       break;
 361     case eTraceEventHWClockTick:
 362       m_j.attribute("hwClock", item.hw_clock);
 363       break;
 364     case eTraceEventDisabledHW:
 365     case eTraceEventDisabledSW:
 366       break;
 367     case eTraceEventSyncPoint:
 368       m_j.attribute("syncPointMetadata", item.sync_point_metadata);
 369       break;
 370     }
 371   }
 372
 373   void DumpInstruction(const TraceDumper::TraceItem &item) {
 374     m_j.attribute("loadAddress", formatv("{0:x}", item.load_address));
 375     if (item.symbol_info) {
 376       m_j.attribute("module", ToOptionalString(GetModuleName(item)));
 377       m_j.attribute(
 378           "symbol",
 379           ToOptionalString(item.symbol_info->sc.GetFunctionName().AsCString()));
 380
 381       if (lldb::InstructionSP instruction = item.symbol_info->instruction) {
 382         ExecutionContext exe_ctx = item.symbol_info->exe_ctx;
 383         m_j.attribute("mnemonic",
 384                       ToOptionalString(instruction->GetMnemonic(&exe_ctx)));
 385         if (m_options.show_control_flow_kind) {
 386           lldb::InstructionControlFlowKind instruction_control_flow_kind =
 387               instruction->GetControlFlowKind(&exe_ctx);
 388           m_j.attribute("controlFlowKind",
 389                         ToOptionalString(
 390                             Instruction::GetNameForInstructionControlFlowKind(
 391                                 instruction_control_flow_kind)));
 392         }
 393       }
 394
 395       if (IsLineEntryValid(item.symbol_info->sc.line_entry)) {
 396         m_j.attribute(
 397             "source",
 398             ToOptionalString(
 399                 item.symbol_info->sc.line_entry.file.GetPath().c_str()));
 400         m_j.attribute("line", item.symbol_info->sc.line_entry.line);
 401         m_j.attribute("column", item.symbol_info->sc.line_entry.column);
 402       }
 403     }
 404   }
 405
 406   void TraceItem(const TraceDumper::TraceItem &item) override {
 407     m_j.object([&] {
 408       m_j.attribute("id", item.id);
 409       if (m_options.show_timestamps)
 410         m_j.attribute("timestamp_ns", item.timestamp
 411                                           ? std::optional<std::string>(
 412                                                 std::to_string(*item.timestamp))
 413                                           : std::nullopt);
 414
 415       if (item.event) {
 416         DumpEvent(item);
 417       } else if (item.error) {
 418         m_j.attribute("error", *item.error);
 419       } else {
 420         DumpInstruction(item);
 421       }
 422     });
 423   }
 424
 425 private:
 426   Stream &m_s;
 427   TraceDumperOptions m_options;
 428   json::OStream m_j;
 429 };
 430
 431 static std::unique_ptr<TraceDumper::OutputWriter>
 432 CreateWriter(Stream &s, const TraceDumperOptions &options, Thread &thread) {
 433   if (options.json)
 434     return std::unique_ptr<TraceDumper::OutputWriter>(
 435         new OutputWriterJSON(s, options));
 436   else
 437     return std::unique_ptr<TraceDumper::OutputWriter>(
 438         new OutputWriterCLI(s, options, thread));
 439 }
 440
 441 TraceDumper::TraceDumper(lldb::TraceCursorSP cursor_sp, Stream &s,
 442                          const TraceDumperOptions &options)
 443     : m_cursor_sp(std::move(cursor_sp)), m_options(options),
 444       m_writer_up(CreateWriter(
 445           s, m_options, *m_cursor_sp->GetExecutionContextRef().GetThreadSP())) {
 446
 447   if (m_options.id)
 448     m_cursor_sp->GoToId(*m_options.id);
 449   else if (m_options.forwards)
 450     m_cursor_sp->Seek(0, lldb::eTraceCursorSeekTypeBeginning);
 451   else
 452     m_cursor_sp->Seek(0, lldb::eTraceCursorSeekTypeEnd);
 453
 454   m_cursor_sp->SetForwards(m_options.forwards);
 455   if (m_options.skip) {
 456     m_cursor_sp->Seek((m_options.forwards ? 1 : -1) * *m_options.skip,
 457                       lldb::eTraceCursorSeekTypeCurrent);
 458   }
 459 }
 460
 461 TraceDumper::TraceItem TraceDumper::CreatRawTraceItem() {
 462   TraceItem item = {};
 463   item.id = m_cursor_sp->GetId();
 464
 465   if (m_options.show_timestamps)
 466     item.timestamp = m_cursor_sp->GetWallClockTime();
 467   return item;
 468 }
 469
 470 /// Find the symbol context for the given address reusing the previous
 471 /// instruction's symbol context when possible.
 472 static SymbolContext
 473 CalculateSymbolContext(const Address &address,
 474                        const SymbolContext &prev_symbol_context) {
 475   AddressRange range;
 476   if (prev_symbol_context.GetAddressRange(eSymbolContextEverything, 0,
 477                                           /*inline_block_range*/ true, range) &&
 478       range.Contains(address))
 479     return prev_symbol_context;
 480
 481   SymbolContext sc;
 482   address.CalculateSymbolContext(&sc, eSymbolContextEverything);
 483   return sc;
 484 }
 485
 486 /// Find the disassembler for the given address reusing the previous
 487 /// instruction's disassembler when possible.
 488 static std::tuple<DisassemblerSP, InstructionSP>
 489 CalculateDisass(const TraceDumper::SymbolInfo &symbol_info,
 490                 const TraceDumper::SymbolInfo &prev_symbol_info,
 491                 const ExecutionContext &exe_ctx) {
 492   if (prev_symbol_info.disassembler) {
 493     if (InstructionSP instruction =
 494             prev_symbol_info.disassembler->GetInstructionList()
 495                 .GetInstructionAtAddress(symbol_info.address))
 496       return std::make_tuple(prev_symbol_info.disassembler, instruction);
 497   }
 498
 499   if (symbol_info.sc.function) {
 500     if (DisassemblerSP disassembler =
 501             symbol_info.sc.function->GetInstructions(exe_ctx, nullptr)) {
 502       if (InstructionSP instruction =
 503               disassembler->GetInstructionList().GetInstructionAtAddress(
 504                   symbol_info.address))
 505         return std::make_tuple(disassembler, instruction);
 506     }
 507   }
 508   // We fallback to a single instruction disassembler
 509   Target &target = exe_ctx.GetTargetRef();
 510   const ArchSpec arch = target.GetArchitecture();
 511   AddressRange range(symbol_info.address, arch.GetMaximumOpcodeByteSize());
 512   DisassemblerSP disassembler =
 513       Disassembler::DisassembleRange(arch, /*plugin_name*/ nullptr,
 514                                      /*flavor*/ nullptr, target, range);
 515   return std::make_tuple(
 516       disassembler,
 517       disassembler ? disassembler->GetInstructionList().GetInstructionAtAddress(
 518                          symbol_info.address)
 519                    : InstructionSP());
 520 }
 521
 522 static TraceDumper::SymbolInfo
 523 CalculateSymbolInfo(const ExecutionContext &exe_ctx, lldb::addr_t load_address,
 524                     const TraceDumper::SymbolInfo &prev_symbol_info) {
 525   TraceDumper::SymbolInfo symbol_info;
 526   symbol_info.exe_ctx = exe_ctx;
 527   symbol_info.address.SetLoadAddress(load_address, exe_ctx.GetTargetPtr());
 528   symbol_info.sc =
 529       CalculateSymbolContext(symbol_info.address, prev_symbol_info.sc);
 530   std::tie(symbol_info.disassembler, symbol_info.instruction) =
 531       CalculateDisass(symbol_info, prev_symbol_info, exe_ctx);
 532   return symbol_info;
 533 }
 534
 535 std::optional<lldb::user_id_t> TraceDumper::DumpInstructions(size_t count) {
 536   ThreadSP thread_sp = m_cursor_sp->GetExecutionContextRef().GetThreadSP();
 537
 538   SymbolInfo prev_symbol_info;
 539   std::optional<lldb::user_id_t> last_id;
 540
 541   ExecutionContext exe_ctx;
 542   thread_sp->GetProcess()->GetTarget().CalculateExecutionContext(exe_ctx);
 543
 544   for (size_t insn_seen = 0; insn_seen < count && m_cursor_sp->HasValue();
 545        m_cursor_sp->Next()) {
 546
 547     last_id = m_cursor_sp->GetId();
 548     TraceItem item = CreatRawTraceItem();
 549
 550     if (m_cursor_sp->IsEvent() && m_options.show_events) {
 551       item.event = m_cursor_sp->GetEventType();
 552       switch (*item.event) {
 553       case eTraceEventCPUChanged:
 554         item.cpu_id = m_cursor_sp->GetCPU();
 555         break;
 556       case eTraceEventHWClockTick:
 557         item.hw_clock = m_cursor_sp->GetHWClock();
 558         break;
 559       case eTraceEventDisabledHW:
 560       case eTraceEventDisabledSW:
 561         break;
 562       case eTraceEventSyncPoint:
 563         item.sync_point_metadata = m_cursor_sp->GetSyncPointMetadata();
 564         break;
 565       }
 566       m_writer_up->TraceItem(item);
 567     } else if (m_cursor_sp->IsError()) {
 568       item.error = m_cursor_sp->GetError();
 569       m_writer_up->TraceItem(item);
 570     } else if (m_cursor_sp->IsInstruction() && !m_options.only_events) {
 571       insn_seen++;
 572       item.load_address = m_cursor_sp->GetLoadAddress();
 573
 574       if (!m_options.raw) {
 575         SymbolInfo symbol_info =
 576             CalculateSymbolInfo(exe_ctx, item.load_address, prev_symbol_info);
 577         item.prev_symbol_info = prev_symbol_info;
 578         item.symbol_info = symbol_info;
 579         prev_symbol_info = symbol_info;
 580       }
 581       m_writer_up->TraceItem(item);
 582     }
 583   }
 584   if (!m_cursor_sp->HasValue())
 585     m_writer_up->NoMoreData();
 586   return last_id;
 587 }
 588
 589 void TraceDumper::FunctionCall::TracedSegment::AppendInsn(
 590     const TraceCursorSP &cursor_sp,
 591     const TraceDumper::SymbolInfo &symbol_info) {
 592   m_last_insn_id = cursor_sp->GetId();
 593   m_last_symbol_info = symbol_info;
 594 }
 595
 596 lldb::user_id_t
 597 TraceDumper::FunctionCall::TracedSegment::GetFirstInstructionID() const {
 598   return m_first_insn_id;
 599 }
 600
 601 lldb::user_id_t
 602 TraceDumper::FunctionCall::TracedSegment::GetLastInstructionID() const {
 603   return m_last_insn_id;
 604 }
 605
 606 void TraceDumper::FunctionCall::TracedSegment::IfNestedCall(
 607     std::function<void(const FunctionCall &function_call)> callback) const {
 608   if (m_nested_call)
 609     callback(*m_nested_call);
 610 }
 611
 612 const TraceDumper::FunctionCall &
 613 TraceDumper::FunctionCall::TracedSegment::GetOwningCall() const {
 614   return m_owning_call;
 615 }
 616
 617 TraceDumper::FunctionCall &
 618 TraceDumper::FunctionCall::TracedSegment::CreateNestedCall(
 619     const TraceCursorSP &cursor_sp,
 620     const TraceDumper::SymbolInfo &symbol_info) {
 621   m_nested_call = std::make_unique<FunctionCall>(cursor_sp, symbol_info);
 622   m_nested_call->SetParentCall(m_owning_call);
 623   return *m_nested_call;
 624 }
 625
 626 const TraceDumper::SymbolInfo &
 627 TraceDumper::FunctionCall::TracedSegment::GetFirstInstructionSymbolInfo()
 628     const {
 629   return m_first_symbol_info;
 630 }
 631
 632 const TraceDumper::SymbolInfo &
 633 TraceDumper::FunctionCall::TracedSegment::GetLastInstructionSymbolInfo() const {
 634   return m_last_symbol_info;
 635 }
 636
 637 const TraceDumper::FunctionCall &
 638 TraceDumper::FunctionCall::UntracedPrefixSegment::GetNestedCall() const {
 639   return *m_nested_call;
 640 }
 641
 642 TraceDumper::FunctionCall::FunctionCall(
 643     const TraceCursorSP &cursor_sp,
 644     const TraceDumper::SymbolInfo &symbol_info) {
 645   m_is_error = cursor_sp->IsError();
 646   AppendSegment(cursor_sp, symbol_info);
 647 }
 648
 649 void TraceDumper::FunctionCall::AppendSegment(
 650     const TraceCursorSP &cursor_sp,
 651     const TraceDumper::SymbolInfo &symbol_info) {
 652   m_traced_segments.emplace_back(cursor_sp, symbol_info, *this);
 653 }
 654
 655 const TraceDumper::SymbolInfo &
 656 TraceDumper::FunctionCall::GetSymbolInfo() const {
 657   return m_traced_segments.back().GetLastInstructionSymbolInfo();
 658 }
 659
 660 bool TraceDumper::FunctionCall::IsError() const { return m_is_error; }
 661
 662 const std::deque<TraceDumper::FunctionCall::TracedSegment> &
 663 TraceDumper::FunctionCall::GetTracedSegments() const {
 664   return m_traced_segments;
 665 }
 666
 667 TraceDumper::FunctionCall::TracedSegment &
 668 TraceDumper::FunctionCall::GetLastTracedSegment() {
 669   return m_traced_segments.back();
 670 }
 671
 672 const std::optional<TraceDumper::FunctionCall::UntracedPrefixSegment> &
 673 TraceDumper::FunctionCall::GetUntracedPrefixSegment() const {
 674   return m_untraced_prefix_segment;
 675 }
 676
 677 void TraceDumper::FunctionCall::SetUntracedPrefixSegment(
 678     TraceDumper::FunctionCallUP &&nested_call) {
 679   m_untraced_prefix_segment.emplace(std::move(nested_call));
 680 }
 681
 682 TraceDumper::FunctionCall *TraceDumper::FunctionCall::GetParentCall() const {
 683   return m_parent_call;
 684 }
 685
 686 void TraceDumper::FunctionCall::SetParentCall(
 687     TraceDumper::FunctionCall &parent_call) {
 688   m_parent_call = &parent_call;
 689 }
 690
 691 /// Given an instruction that happens after a return, find the ancestor function
 692 /// call that owns it. If this ancestor doesn't exist, create a new ancestor and
 693 /// make it the root of the tree.
 694 ///
 695 /// \param[in] last_function_call
 696 ///   The function call that performs the return.
 697 ///
 698 /// \param[in] symbol_info
 699 ///   The symbol information of the instruction after the return.
 700 ///
 701 /// \param[in] cursor_sp
 702 ///   The cursor pointing to the instruction after the return.
 703 ///
 704 /// \param[in,out] roots
 705 ///   The object owning the roots. It might be modified if a new root needs to
 706 ///   be created.
 707 ///
 708 /// \return
 709 ///   A reference to the function call that owns the new instruction
 710 static TraceDumper::FunctionCall &AppendReturnedInstructionToFunctionCallForest(
 711     TraceDumper::FunctionCall &last_function_call,
 712     const TraceDumper::SymbolInfo &symbol_info, const TraceCursorSP &cursor_sp,
 713     std::vector<TraceDumper::FunctionCallUP> &roots) {
 714
 715   // We omit the current node because we can't return to itself.
 716   TraceDumper::FunctionCall *ancestor = last_function_call.GetParentCall();
 717
 718   for (; ancestor; ancestor = ancestor->GetParentCall()) {
 719     // This loop traverses the tree until it finds a call that we can return to.
 720     if (IsSameInstructionSymbolContext(ancestor->GetSymbolInfo(), symbol_info,
 721                                        /*check_source_line_info=*/false)) {
 722       // We returned to this symbol, so we are assuming we are returning there
 723       // Note: If this is not robust enough, we should actually check if we
 724       // returning to the instruction that follows the last instruction from
 725       // that call, as that's the behavior of CALL instructions.
 726       ancestor->AppendSegment(cursor_sp, symbol_info);
 727       return *ancestor;
 728     }
 729   }
 730
 731   // We didn't find the call we were looking for, so we now create a synthetic
 732   // one that will contain the new instruction in its first traced segment.
 733   TraceDumper::FunctionCallUP new_root =
 734       std::make_unique<TraceDumper::FunctionCall>(cursor_sp, symbol_info);
 735   // This new root will own the previous root through an untraced prefix segment.
 736   new_root->SetUntracedPrefixSegment(std::move(roots.back()));
 737   roots.pop_back();
 738   // We update the roots container to point to the new root
 739   roots.emplace_back(std::move(new_root));
 740   return *roots.back();
 741 }
 742
 743 /// Append an instruction to a function call forest. The new instruction might
 744 /// be appended to the current segment, to a new nest call, or return to an
 745 /// ancestor call.
 746 ///
 747 /// \param[in] exe_ctx
 748 ///   The exeuction context of the traced thread.
 749 ///
 750 /// \param[in] last_function_call
 751 ///   The chronologically most recent function call before the new instruction.
 752 ///
 753 /// \param[in] prev_symbol_info
 754 ///   The symbol information of the previous instruction in the trace.
 755 ///
 756 /// \param[in] symbol_info
 757 ///   The symbol information of the new instruction.
 758 ///
 759 /// \param[in] cursor_sp
 760 ///   The cursor pointing to the new instruction.
 761 ///
 762 /// \param[in,out] roots
 763 ///   The object owning the roots. It might be modified if a new root needs to
 764 ///   be created.
 765 ///
 766 /// \return
 767 ///   A reference to the function call that owns the new instruction.
 768 static TraceDumper::FunctionCall &AppendInstructionToFunctionCallForest(
 769     const ExecutionContext &exe_ctx,
 770     TraceDumper::FunctionCall *last_function_call,
 771     const TraceDumper::SymbolInfo &prev_symbol_info,
 772     const TraceDumper::SymbolInfo &symbol_info, const TraceCursorSP &cursor_sp,
 773     std::vector<TraceDumper::FunctionCallUP> &roots) {
 774   if (!last_function_call || last_function_call->IsError()) {
 775     // We create a brand new root
 776     roots.emplace_back(
 777         std::make_unique<TraceDumper::FunctionCall>(cursor_sp, symbol_info));
 778     return *roots.back();
 779   }
 780
 781   AddressRange range;
 782   if (symbol_info.sc.GetAddressRange(
 783           eSymbolContextBlock | eSymbolContextFunction | eSymbolContextSymbol,
 784           0, /*inline_block_range*/ true, range)) {
 785     if (range.GetBaseAddress() == symbol_info.address) {
 786       // Our instruction is the first instruction of a function. This has
 787       // to be a call. This should also identify if a trampoline or the linker
 788       // is making a call using a non-CALL instruction.
 789       return last_function_call->GetLastTracedSegment().CreateNestedCall(
 790           cursor_sp, symbol_info);
 791     }
 792   }
 793   if (IsSameInstructionSymbolContext(prev_symbol_info, symbol_info,
 794                                      /*check_source_line_info=*/false)) {
 795     // We are still in the same function. This can't be a call because otherwise
 796     // we would be in the first instruction of the symbol.
 797     last_function_call->GetLastTracedSegment().AppendInsn(cursor_sp,
 798                                                           symbol_info);
 799     return *last_function_call;
 800   }
 801   // Now we are in a different symbol. Let's see if this is a return or a
 802   // call
 803   const InstructionSP &insn = last_function_call->GetLastTracedSegment()
 804                                   .GetLastInstructionSymbolInfo()
 805                                   .instruction;
 806   InstructionControlFlowKind insn_kind =
 807       insn ? insn->GetControlFlowKind(&exe_ctx)
 808            : eInstructionControlFlowKindOther;
 809
 810   switch (insn_kind) {
 811   case lldb::eInstructionControlFlowKindCall:
 812   case lldb::eInstructionControlFlowKindFarCall: {
 813     // This is a regular call
 814     return last_function_call->GetLastTracedSegment().CreateNestedCall(
 815         cursor_sp, symbol_info);
 816   }
 817   case lldb::eInstructionControlFlowKindFarReturn:
 818   case lldb::eInstructionControlFlowKindReturn: {
 819     // We should have caught most trampolines and linker functions earlier, so
 820     // let's assume this is a regular return.
 821     return AppendReturnedInstructionToFunctionCallForest(
 822         *last_function_call, symbol_info, cursor_sp, roots);
 823   }
 824   default:
 825     // we changed symbols not using a call or return and we are not in the
 826     // beginning of a symbol, so this should be something very artificial
 827     // or maybe a jump to some label in the middle of it section.
 828
 829     // We first check if it's a return from an inline method
 830     if (prev_symbol_info.sc.block &&
 831         prev_symbol_info.sc.block->GetContainingInlinedBlock()) {
 832       return AppendReturnedInstructionToFunctionCallForest(
 833           *last_function_call, symbol_info, cursor_sp, roots);
 834     }
 835     // Now We assume it's a call. We should revisit this in the future.
 836     // Ideally we should be able to decide whether to create a new tree,
 837     // or go deeper or higher in the stack.
 838     return last_function_call->GetLastTracedSegment().CreateNestedCall(
 839         cursor_sp, symbol_info);
 840   }
 841 }
 842
 843 /// Append an error to a function call forest. The new error might be appended
 844 /// to the current segment if it contains errors or will create a new root.
 845 ///
 846 /// \param[in] last_function_call
 847 ///   The chronologically most recent function call before the new error.
 848 ///
 849 /// \param[in] cursor_sp
 850 ///   The cursor pointing to the new error.
 851 ///
 852 /// \param[in,out] roots
 853 ///   The object owning the roots. It might be modified if a new root needs to
 854 ///   be created.
 855 ///
 856 /// \return
 857 ///   A reference to the function call that owns the new error.
 858 TraceDumper::FunctionCall &AppendErrorToFunctionCallForest(
 859     TraceDumper::FunctionCall *last_function_call, TraceCursorSP &cursor_sp,
 860     std::vector<TraceDumper::FunctionCallUP> &roots) {
 861   if (last_function_call && last_function_call->IsError()) {
 862     last_function_call->GetLastTracedSegment().AppendInsn(
 863         cursor_sp, TraceDumper::SymbolInfo{});
 864     return *last_function_call;
 865   } else {
 866     roots.emplace_back(std::make_unique<TraceDumper::FunctionCall>(
 867         cursor_sp, TraceDumper::SymbolInfo{}));
 868     return *roots.back();
 869   }
 870 }
 871
 872 static std::vector<TraceDumper::FunctionCallUP>
 873 CreateFunctionCallForest(TraceCursorSP &cursor_sp,
 874                          const ExecutionContext &exe_ctx) {
 875
 876   std::vector<TraceDumper::FunctionCallUP> roots;
 877   TraceDumper::SymbolInfo prev_symbol_info;
 878
 879   TraceDumper::FunctionCall *last_function_call = nullptr;
 880
 881   for (; cursor_sp->HasValue(); cursor_sp->Next()) {
 882     if (cursor_sp->IsError()) {
 883       last_function_call = &AppendErrorToFunctionCallForest(last_function_call,
 884                                                             cursor_sp, roots);
 885       prev_symbol_info = {};
 886     } else if (cursor_sp->IsInstruction()) {
 887       TraceDumper::SymbolInfo symbol_info = CalculateSymbolInfo(
 888           exe_ctx, cursor_sp->GetLoadAddress(), prev_symbol_info);
 889
 890       last_function_call = &AppendInstructionToFunctionCallForest(
 891           exe_ctx, last_function_call, prev_symbol_info, symbol_info, cursor_sp,
 892           roots);
 893       prev_symbol_info = symbol_info;
 894     } else if (cursor_sp->GetEventType() == eTraceEventCPUChanged) {
 895       // TODO: In case of a CPU change, we create a new root because we haven't
 896       // investigated yet if a call tree can safely continue or if interrupts
 897       // could have polluted the original call tree.
 898       last_function_call = nullptr;
 899       prev_symbol_info = {};
 900     }
 901   }
 902
 903   return roots;
 904 }
 905
 906 void TraceDumper::DumpFunctionCalls() {
 907   ThreadSP thread_sp = m_cursor_sp->GetExecutionContextRef().GetThreadSP();
 908   ExecutionContext exe_ctx;
 909   thread_sp->GetProcess()->GetTarget().CalculateExecutionContext(exe_ctx);
 910
 911   m_writer_up->FunctionCallForest(
 912       CreateFunctionCallForest(m_cursor_sp, exe_ctx));
 913 }