[trace] Add a new call graph reconstructor

[wallace]

Summary

The previous reconstructor was flawed and served well as prototype, but
this new one is meant to stay for a while. Some features

• Strictly typing of the different variants of calls (functions, inlined functions, symbols, etc).
• Special handling of inline function, including inlined functions that have no instructions of their own
• Better formatting for the dumper
• Extensible code structure. It's easy to create new call types and special handlers based on instruction types and symbol information
• Added better tests

As a note, the latest version of libipt included a new instruction kind "indirect" with is either an indirect jump or a call that libipt can't distinguish better. It used to be signaled as an error instruction but not anymore (see https://github.com/intel/libipt/commit/27513274c897851e15a46bb19a3861219d87c6cb). Besides that, the LLVM disassembler fails to disassembly some functions that libipt doesn't. I imagine Intel is doing a better job than LLVM at disassembling x86 instructions. So I decided to use the instruction kinds from libipt until we improve the disassembler.

In a following diff I'll add a JSON dumper for the graph.

[wallace]

nit

[jj10306]

lldb/source/Plugins/Trace/intel-pt/DecodedThread.h

296

do we need to store this or can this information be calculated on demand? just thinking about massive traces and want to make sure we're intentional about only storing what we absolutely need to for each instruction

lldb/source/Plugins/Trace/intel-pt/TraceIntelPT.cpp

317

what's the reason for this change?

[wallace]

lldb/source/Plugins/Trace/intel-pt/DecodedThread.h

296

I thought about it and it will help us have more correctness for now and a little bit more speed with little memory cost. The total size per instruction went from 9 bytes to 11, which is very decent.

Now some details: the Disassembler fails with some instructions. I was tracing dynolog and found many instances of the disassembler failing, but libipt doesn't fail. In other words, we can't get the control flow kind from LLDB but we can from libipt. Same for the byte size. That means that we need to fix the disassembler, but that will require a lot of work that I can hardly prioritize, so I'd rather use libipt for now.

lldb/source/Plugins/Trace/intel-pt/TraceIntelPT.cpp

317

wtf, i think this is from a previous commit i never intended to publish. I was playing with some stuff. I need to revert this

lldb/include/lldb/Target/Trace.h

 #define LLDB_TARGET_TRACE_H
 
 #include <unordered_map>
 
 #include "llvm/Support/JSON.h"
 
 #include "lldb/Core/PluginInterface.h"
 #include "lldb/Target/Thread.h"
+#include "lldb/Target/TraceCallGraph.h"
 #include "lldb/Target/TraceCursor.h"
 #include "lldb/Utility/ArchSpec.h"
 #include "lldb/Utility/TraceGDBRemotePackets.h"
 #include "lldb/Utility/UnimplementedError.h"
 #include "lldb/lldb-private.h"
 #include "lldb/lldb-types.h"
 
 namespace lldb_private {
public:
   /// Get a \a TraceCursor for the given thread's trace.
   ///
   /// \return
   ///     A \a TraceCursorSP. If the thread is not traced or its trace
   ///     information failed to load, an \a llvm::Error is returned.
   virtual llvm::Expected<lldb::TraceCursorSP>
   CreateNewCursor(Thread &thread) = 0;
 
+  llvm::Expected<lldb::TraceCallGraphSP>
+  CreateCallGraph(Thread &thread,
+                  llvm::Optional<lldb::user_id_t> from_id = llvm::None,
+                  llvm::Optional<lldb::user_id_t> to_id = llvm::None);
+
   /// Dump general info about a given thread's trace. Each Trace plug-in
   /// decides which data to show.
   ///
   /// \param[in] thread
   ///     The thread that owns the trace in question.
   ///
   /// \param[in] s
   ///     The stream object where the info will be printed printed.

lldb/include/lldb/Target/TraceCallGraph.h

+//===-- TraceCallGraph.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_TRACECALLTREE_H
+#define LLDB_TARGET_TRACECALLTREE_H
+
+#include "lldb/Symbol/SymbolContext.h"
+#include <variant>
+
+namespace lldb_private {
+
+class TraceCallBase;
+class TraceCallSegment;
+class TraceCallUnknownRegion;
+class TraceCallFunction;
+class TraceCallSection;
+class TraceCallInlinedFunction;
+class TraceCallSymbol;
+class TraceCallSegment;
+
+using TraceCall =
+    std::variant<TraceCallUnknownRegion, TraceCallFunction,
+                 TraceCallInlinedFunction, TraceCallSymbol, TraceCallSection>;
+using TraceCallUP = std::unique_ptr<TraceCall>;
+using TraceCallSegmentUP = std::unique_ptr<TraceCallSegment>;
+
+/// Function that should be invoked to create a new trace call. Its main
+/// objetive is making sure that actual call implementation are correctly set
+/// up.
+template <class T, class... Args> TraceCallUP CreateTraceCall(Args &&...args);
+
+/// A segment is a contiguous list of traced instructions that belong to the
+/// same call (or frame) and might end in a call. It cannot have two calls nor
+/// instructions after its single call. It might also have no instructions of
+/// its own, which can happen with inlined functions.
+///
+///  Example:
+///   We might have this piece of execution:
+///
+///     main() [offset 0x00 to 0x20] [traced instruction ids 1 to 4]
+///       foo()  [offset 0x00 to 0x80] [traced instruction ids 5 to 20]
+///     main() [offset 0x24 to 0x40] [traced instruction ids 21 to 30]
+///
+///   In this case, our function main invokes foo. We have 3 segments: main
+///   [offset 0x00 to 0x20], foo() [offset 0x00 to 0x80], and main() [offset
+///   0x24 to 0x40]. We also have the instruction ids from the corresponding
+///   linear instruction trace for each segment.
+///
+///   But what if we started tracing since the middle of foo? Then we'd have
+///   an incomplete trace
+///
+///       foo() [offset 0x30 to 0x80] [traced instruction ids 1 to 10]
+///     main() [offset 0x24 to 0x40] [traced instruction ids 11 to 20]
+///
+///   Notice that we changed the instruction ids because this is a new trace.
+///   Here, in order to have a somewhat complete tree with good traversal
+///   capabilities, we can have a segment with a child but without instruction
+///   of its own to signal the portion of main() that we didn't trace. We don't
+///   know if this segment was in fact multiple segments with many function
+///   calls. We'll never know. The resulting tree looks like the following:
+///
+///     main() [untraced]
+///       foo() [offset 0x30 to 0x80] [traced instruction ids 1 to 10]
+///     main() [offset 0x24 to 0x40] [traced instruction ids 11 to 20]
+///
+///  Returns:
+///   Code doesn't always behave intuitively. Some interesting functions
+///   might modify the stack and thus change the behavior of common
+///   instructions like CALL and RET. We try to identify these cases, and
+///   the result is that the return edge from a segment might connect with a
+///   function call very high the stack. For example, you might have
+///
+///     main()
+///       foo()
+///         bar()
+///         # here bar modifies the stack and pops foo() from it. Then it
+///         # finished the a RET (return)
+///     main() # we came back directly to main()
+///
+///   Trampolines and linkers do similar actions, So consumers should be aware
+///   of this.
+class TraceCallSegment {
+public:
+  TraceCallSegment(const TraceCursor &insn);
+
+  TraceCallSegment(TraceCallUP &&trace_call_up);
+
+  /// Append the given instruction if this segment doesn't have a child call.
+  ///
+  /// \param[in] insn
+  ///   The instruction to append.
+  ///
+  /// \return
+  ///   \b true if and only if the instruction was appended.
+  bool TryAppendInstruction(const TraceCursor &insn);
+
+  /// \return
+  ///   A pointer to the child call of this segment. It might be \b nullptr if
+  ///   there is no child.
+  TraceCall *GetChildCall();
+
+  /// Set a child for this segment, who takes ownership of the child.
+  ///
+  /// \return
+  ///   A reference to the child.
+  TraceCall &SetChildCall(TraceCallUP &&trace_call_up);
+
+  /// \return
+  ///   The optional range of instructions IDs that belong strictly to this
+  ///   segment.
+  llvm::Optional<std::pair<lldb::user_id_t, lldb::user_id_t>> GetRange() const;
+
+  /// \return
+  ///   The number of instructions that belong exclusively to this segment. It
+  ///   excludes children.
+  uint64_t GetExclusiveInsnCount() const;
+
+private:
+  friend class TraceCallBase;
+
+  llvm::Optional<std::pair<lldb::user_id_t, lldb::user_id_t>> m_insn_ids_range;
+  TraceCallUP m_child_call_up; // optional
+  uint64_t m_exclusive_insn_count = 0;
+};
+
+/// Base class for all kinds of calls. All concrete call classes are part of a
+/// variant \a TraceCall. This base class contains a reference to the wrapping
+/// \a TraceCall for convenience to use them almost interchangeably.
+class TraceCallBase {
+public:
+  /// \return
+  ///   The child call of the most recent segment of this call, or \b nullptr if
+  ///   it doesn't exist.
+  TraceCall *TryGetChildCallOfLastSegment();
+
+  /// \return
+  ///   The child call of the most recent segment of this call.
+  TraceCall &GetChildCallOfLastSegment();
+
+  /// \return
+  ///   The the most recent segment of this call, or \b nullptr if there are no
+  ///   segments.
+  TraceCallSegment *TryGetLastSegment();
+
+  /// \return
+  ///   The the most recent segment of this call.
+  TraceCallSegment &GetLastSegment();
+
+  /// Append the given instruction to the most recent segment if possible, or in
+  /// a new segment otherwise.
+  void AppendInstruction(const TraceCursor &insn);
+
+  /// Create a new segment without instructions but with a child call who is
+  /// created in place.
+  ///
+  /// \return
+  ///   A reference to the newly created child call.
+  template <class T, class... Args>
+  T &AppendSegmentWithNewChildCall(Args &&...args) {
+    m_segments.emplace_back(
+        std::make_unique<TraceCallSegment>(CreateTraceCall<T>(args...)));
+    T &new_call = std::get<T>(*TryGetChildCallOfLastSegment());
+    new_call.m_parent = m_wrapping_call;
+    return new_call;
+  }
+
+  /// Set the child call of the most recent segment. It is assumed that there is
+  /// such a segment and that it doesn't have a child.
+  ///
+  /// \return
+  ///   A reference to the child call.
+  TraceCall &SetLastSegmentChildCall(TraceCallUP &&trace_call_up);
+
+  /// Create a segment before all other existing segments of this call and
+  /// include the given child in it.
+  void PrependSyntheticSegmentWithChildCall(TraceCallUP &&trace_call_up);
+
+  /// Handy cast operator to get the wrapping variant call.
+  operator TraceCall &() { return *m_wrapping_call; }
+
+  /// \return
+  ///   The wrapping variant call.
+  TraceCall &GetWrappingCall() { return *m_wrapping_call; }
+
+  /// \return
+  ///   A non-mutable list of the segments of this call.
+  llvm::ArrayRef<TraceCallSegmentUP> GetSegments() const;
+
+  /// \return
+  ///   The parent of this call, or \b nullptr if this is the root of a call
+  ///   tree.
+  TraceCall *GetParent();
+
+  /// Set a new parent for this call.
+  void SetParent(TraceCall &parent);
+
+protected:
+  TraceCallBase() {}
+
+private:
+  template <class T, class... Args>
+  friend TraceCallUP CreateTraceCall(Args &&...args);
+
+  TraceCallBase(TraceCallBase const &);
+  TraceCallBase &operator=(TraceCallBase const &);
+
+  TraceCall *m_wrapping_call = nullptr;
+
+  TraceCall *m_parent = nullptr;
+
+protected:
+  std::vector<TraceCallSegmentUP> m_segments;
+};
+
+/// This kind of call refers to instructions that are correctly mapped to
+/// modules but lack debug or symbol information.
+class TraceCallSection : public TraceCallBase {
+public:
+  /// \return
+  ///   The section of a module this call belongs to.
+  const lldb::SectionSP &GetSection() const;
+
+  TraceCallSection(const lldb::SectionSP &section);
+
+  TraceCallSection(const lldb::SectionSP &section, const TraceCursor &insn);
+
+private:
+  lldb::SectionSP m_section_sp;
+};
+
+/// This is a base class for functions identified through debug info, including
+/// inlined functions.
+class TraceCallFunctionLike : public TraceCallBase {
+public:
+  /// Create recursively inlined function children based on the given hierarchy.
+  ///
+  /// \param[in] insn
+  ///   The instruction that is part of the deepest inlined function.
+  ///
+  /// \param[in] nested_inlined_blocks
+  ///   A hierarchiy of nested functions that lead to the given instruction. It
+  ///   has to be sorted so that the i-th element is the parent of the (i+1)-th
+  ///   element.
+  ///
+  /// \param[in] owning_function
+  ///   The function call that owns the inlined functions.
+  ///
+  /// \return
+  ///   A reference to the deepest inlined function.
+  TraceCall &
+  CreateNestedInlinedBlockCalls(const TraceCursor &insn,
+                                llvm::ArrayRef<Block *> nested_inlined_blocks,
+                                TraceCallFunction &owning_function);
+};
+
+/// This kind of call refers to instructions that are part of a non-inlined
+/// function.
+class TraceCallFunction : public TraceCallFunctionLike {
+public:
+  /// \return
+  ///   The function this call belongs to.
+  Function &GetFunction();
+
+  /// Create recursively inlined function children based on the hierarchy given
+  /// by the provided inlined block.
+  ///
+  /// \param[in] deepest_inlined_block
+  ///   The block whose parents will included recursively in this call.
+  ///
+  /// \param[in] insn
+  ///   The instruction that is part of the deepest block.
+  ///
+  /// \return
+  ///   A reference to the deepest inlined function.
+  TraceCall &CreateNestedInlinedBlockCalls(Block &deepest_inlined_block,
+                                           const TraceCursor &insn);
+
+  TraceCallFunction(Function &function);
+
+  TraceCallFunction(Function &function, const TraceCursor &insn);
+
+private:
+  Function &m_function;
+};
+
+/// This kind of call refers to instructions that are part of an inlined
+/// function. All inlined functions are part of an ancestor \a
+/// TraceCallFunction.
+class TraceCallInlinedFunction : public TraceCallFunctionLike {
+public:
+  /// \return
+  ///   The inlined function (or block) this call belongs to.
+  Block &GetInlinedBlock();
+
+  /// \return
+  ///   The ancestor function that owns this inlined function.
+  TraceCallFunction &GetOwningFunctionCall();
+
+  TraceCallInlinedFunction(Block &inlined_block,
+                           TraceCallFunction &owning_function_call);
+
+  TraceCallInlinedFunction(Block &inlined_block,
+                           TraceCallFunction &owning_function_call,
+                           const TraceCursor &insn);
+
+private:
+  Block &m_inlined_block;
+  TraceCallFunction &m_owning_function_call;
+};
+
+/// This kind of call refers to instructions that are part of a symbol
+/// identified from the symbol table but lacks further debug info.
+class TraceCallSymbol : public TraceCallBase {
+public:
+  /// \return
+  ///   The symbol this call belongs to.
+  Symbol &GetSymbol();
+
+  TraceCallSymbol(Symbol &symbol);
+
+  TraceCallSymbol(Symbol &symbol, const TraceCursor &insn);
+
+private:
+  /// We use a pointer just because using a reference member would disable move
+  /// constructors.
+  Symbol &m_symbol;
+};
+
+/// This kind of call refers to instructions that are somewhere in the memory
+/// but whose module is not known and lacks debug or symbol information.
+class TraceCallUnknownRegion : public TraceCallBase {
+public:
+  TraceCallUnknownRegion(const TraceCursor &insn);
+};
+
+/// A tree representing function calls from a contiguous trace. Given a node in
+/// this tree, it is posible to reconstruct its call stack.
+class TraceInstructionCallTree {
+public:
+  /// Create a new tree based on a single instruction.
+  TraceInstructionCallTree(const TraceCursor &insn, Target &target);
+
+  /// Append the given instruction to the tree.
+  void AppendInstruction(const TraceCursor &insn, Target &target);
+
+  /// \return
+  ///   The root call of this tree.
+  TraceCall &GetRootCall();
+
+private:
+  TraceCall &DoAppendInstruction(
+      const TraceCursor &insn, Target &target, TraceCall &active_call,
+      lldb::InstructionControlFlowKind active_insn_contrl_flow_kind);
+
+  /// Append to this tree an instruction that is being returned to.
+  TraceCall &AppendReturnedInstruction(const TraceCursor &insn,
+                                       SymbolContext &sc, Address &addr,
+                                       Target &target,
+                                       TraceCall &active_call_wrapper);
+
+  TraceCallUP m_root_up;
+  /// This contains the information of the most recent call in this tree (the
+  /// active one).
+  struct {
+    std::reference_wrapper<TraceCall> call;
+    lldb::InstructionControlFlowKind last_insn_control_flow_kind;
+  } m_active_call;
+};
+
+/// This represents a contiguous list of errors in a trace.
+class TraceErrorSegment {
+public:
+  TraceErrorSegment(const TraceCursor &error);
+
+  /// Append a given error to this segment.
+  void AppendError(const TraceCursor &error);
+
+  /// \return
+  ///   The number of items in this segment.
+  uint64_t GetErrorCount() const;
+
+  /// \return
+  ///   The range of error IDs in this segment.
+  std::pair<lldb::user_id_t, lldb::user_id_t> GetRange() const;
+
+private:
+  uint64_t m_error_count = 0;
+  std::pair<lldb::user_id_t, lldb::user_id_t> m_ids_range;
+};
+
+using TraceCallTree = std::variant<TraceInstructionCallTree, TraceErrorSegment>;
+using TraceCallTreeUP = std::unique_ptr<TraceCallTree>;
+
+/// Class that represents hierarchically function calls in a trace of a single
+/// thread.
+///
+/// It is composed of trees and error segments. In fact, ideally, if a trace was
+/// perfect, it could be represented as a single function call tree, but errors
+/// in the trace split this theorical single tree into multiple maximal trees,
+/// which results in a forest.
+class TraceCallGraph {
+public:
+  /// Create a new graph given a trace cursor of a thread and an optional range
+  /// of ids.
+  ///
+  /// \param[in] cursor
+  ///   A trace cursor of some thread.
+  ///
+  /// \param[in] from_id
+  ///   If not \b None, then the graph will include all instructions that come
+  ///   at \p from_id or later. Otherwise, it starts at the oldest instruction
+  ///   chronologically.
+  ///
+  /// \param[in] to_id
+  ///   If not \b None, then the graph will include all instructions that come
+  ///   at \p from_id or earlier. Otherwise, it ends at the most recent
+  ///   instruction chronologically.
+  static lldb::TraceCallGraphSP
+  Build(TraceCursor &cursor,
+        llvm::Optional<lldb::user_id_t> from_id = llvm::None,
+        llvm::Optional<lldb::user_id_t> to_id = llvm::None);
+
+  /// \return
+  ///   The list of instruction trees or error segments in this graph
+  ///   chronologically.
+  llvm::ArrayRef<TraceCallTreeUP> GetTrees() const { return m_trees; }
+
+private:
+  TraceCallGraph() {}
+
+  TraceCallTree *GetActiveTree();
+
+  void CloseActiveTree();
+
+  void CreateErrorSegment(const TraceCursor &error);
+
+  void CreateInstructionCallTree(const TraceCursor &insn, Target &target);
+
+  void AppendErrorItemToGraph(const TraceCursor &error);
+
+  void AppendInstructionItemToGraph(const TraceCursor &insn, Target &target);
+
+  std::vector<TraceCallTreeUP> m_trees;
+  /// Last tree added to the graph, unless it's been marked as closed.
+  TraceCallTree *m_active_tree = nullptr;
+};
+
+namespace TraceCallUtils {
+/// \return
+///   A string representation of a call. Useful for debugging.
+std::string ToDebugString(TraceCall &call_wrapper);
+
+/// \return
+///   The parent of a call, or \b nullptr if this call is a root.
+TraceCall *GetParent(TraceCall &call_wrapper);
+
+/// Set the new parent for a given child call.
+void SetParent(TraceCall &child, TraceCall &parent);
+
+/// \return
+///   The most recently call that is a descendant of the given call.
+TraceCall &GetRecursivelyMostRecentCall(TraceCall &call);
+} // namespace TraceCallUtils
+
+template <class T, class... Args> TraceCallUP CreateTraceCall(Args &&...args) {
+  TraceCallUP trace_call_up(new TraceCall(std::in_place_type<T>, args...));
+  std::visit([&](auto &&call) { call.m_wrapping_call = trace_call_up.get(); },
+             *trace_call_up);
+  return trace_call_up;
+}
+
+} // namespace lldb_private
+
+#endif // LLDB_TARGET_TRACECALLTREE_H

lldb/include/lldb/Target/TraceCursor.h

public:
   /// \return
   ///     Whether the cursor points to an instruction.
   bool IsInstruction() const;
 
   /// \return
   ///     The load address of the instruction the cursor is pointing at.
   virtual lldb::addr_t GetLoadAddress() const = 0;
 
+  virtual lldb::InstructionControlFlowKind
+  GetInstructionControlFlowKind() const;
+
   /// Get the CPU associated with the current trace item.
   ///
   /// This call might not be O(1), so it's suggested to invoke this method
   /// whenever an eTraceEventCPUChanged event is fired.
   ///
   /// \return
   ///    The requested CPU id, or LLDB_INVALID_CPU_ID if this information is
   ///    not available for the current item.

lldb/include/lldb/Target/TraceDumper.h

 //===-- TraceDumper.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
 //
 //===----------------------------------------------------------------------===//
 
 #include "lldb/Symbol/SymbolContext.h"
+#include "lldb/Target/TraceCallGraph.h"
 #include "lldb/Target/TraceCursor.h"
 #include <optional>
 
 #ifndef LLDB_TARGET_TRACE_INSTRUCTION_DUMPER_H
 #define LLDB_TARGET_TRACE_INSTRUCTION_DUMPER_H
 
 namespace lldb_private {
 
struct TraceItem {
     llvm::Optional<std::string> sync_point_metadata;
     llvm::Optional<llvm::StringRef> error;
     llvm::Optional<lldb::TraceEvent> event;
     llvm::Optional<SymbolInfo> symbol_info;
     llvm::Optional<SymbolInfo> prev_symbol_info;
     llvm::Optional<lldb::cpu_id_t> cpu_id;
   };
 
-  /// An object representing a traced function call.
-  ///
-  /// A function call is represented using segments and subcalls.
-  ///
-  /// TracedSegment:
-  ///   A traced segment is a maximal list of consecutive traced instructions
-  ///   that belong to the same function call. A traced segment will end in
-  ///   three possible ways:
-  ///     - With a call to a function deeper in the callstack. In this case,
-  ///     most of the times this nested call will return
-  ///       and resume with the next segment of this segment's owning function
-  ///       call. More on this later.
-  ///     - Abruptly due to end of trace. In this case, we weren't able to trace
-  ///     the end of this function call.
-  ///     - Simply a return higher in the callstack.
-  ///
-  ///   In terms of implementation details, as segment can be represented with
-  ///   the beginning and ending instruction IDs from the instruction trace.
-  ///
-  ///  UntracedPrefixSegment:
-  ///   It might happen that we didn't trace the beginning of a function and we
-  ///   saw it for the first time as part of a return. As a way to signal these
-  ///   cases, we have a placeholder UntracedPrefixSegment class that completes the
-  ///   callgraph.
-  ///
-  ///  Example:
-  ///   We might have this piece of execution:
-  ///
-  ///     main() [offset 0x00 to 0x20] [traced instruction ids 1 to 4]
-  ///       foo()  [offset 0x00 to 0x80] [traced instruction ids 5 to 20] # main
-  ///       invoked foo
-  ///     main() [offset 0x24 to 0x40] [traced instruction ids 21 to 30]
-  ///
-  ///   In this case, our function main invokes foo. We have 3 segments: main
-  ///   [offset 0x00 to 0x20], foo() [offset 0x00 to 0x80], and main() [offset
-  ///   0x24 to 0x40]. We also have the instruction ids from the corresponding
-  ///   linear instruction trace for each segment.
-  ///
-  ///   But what if we started tracing since the middle of foo? Then we'd have
-  ///   an incomplete trace
-  ///
-  ///       foo() [offset 0x30 to 0x80] [traced instruction ids 1 to 10]
-  ///     main() [offset 0x24 to 0x40] [traced instruction ids 11 to 20]
-  ///
-  ///   Notice that we changed the instruction ids because this is a new trace.
-  ///   Here, in order to have a somewhat complete tree with good traversal
-  ///   capabilities, we can create an UntracedPrefixSegment to signal the portion of
-  ///   main() that we didn't trace. We don't know if this segment was in fact
-  ///   multiple segments with many function calls. We'll never know. The
-  ///   resulting tree looks like the following:
-  ///
-  ///     main() [untraced]
-  ///       foo() [offset 0x30 to 0x80] [traced instruction ids 1 to 10]
-  ///     main() [offset 0x24 to 0x40] [traced instruction ids 11 to 20]
-  ///
-  ///   And in pseudo-code:
-  ///
-  ///     FunctionCall [
-  ///       UntracedPrefixSegment {
-  ///         symbol: main()
-  ///         nestedCall: FunctionCall [ # this untraced segment has a nested
-  ///         call
-  ///           TracedSegment {
-  ///             symbol: foo()
-  ///             fromInstructionId: 1
-  ///             toInstructionId: 10
-  ///             nestedCall: none # this doesn't have a nested call
-  ///           }
-  ///         }
-  ///       ],
-  ///       TracedSegment {
-  ///         symbol: main()
-  ///         fromInstructionId: 11
-  ///         toInstructionId: 20
-  ///         nestedCall: none # this also doesn't have a nested call
-  ///       }
-  ///   ]
-  ///
-  ///   We can see the nested structure and how instructions are represented as
-  ///   segments.
-  ///
-  ///
-  ///   Returns:
-  ///     Code doesn't always behave intuitively. Some interesting functions
-  ///     might modify the stack and thus change the behavior of common
-  ///     instructions like CALL and RET. We try to identify these cases, and
-  ///     the result is that the return edge from a segment might connect with a
-  ///     function call very high the stack. For example, you might have
-  ///
-  ///     main()
-  ///       foo()
-  ///         bar()
-  ///         # here bar modifies the stack and pops foo() from it. Then it
-  ///         finished the a RET (return)
-  ///     main() # we came back directly to main()
-  ///
-  ///     I have observed some trampolines doing this, as well as some std
-  ///     functions (like ostream functions). So consumers should be aware of
-  ///     this.
-  ///
-  ///     There are all sorts of "abnormal" behaviors you can see in code, and
-  ///     whenever we fail at identifying what's going on, we prefer to create a
-  ///     new tree.
-  ///
-  ///   Function call forest:
-  ///     A single tree would suffice if a trace didn't contain errors nor
-  ///     abnormal behaviors that made our algorithms fail. Sadly these
-  ///     anomalies exist and we prefer not to use too many heuristics and
-  ///     probably end up lying to the user. So we create a new tree from the
-  ///     point we can't continue using the previous tree. This results in
-  ///     having a forest instead of a single tree. This is probably the best we
-  ///     can do if we consumers want to use this data to perform performance
-  ///     analysis or reverse debugging.
-  ///
-  ///   Non-functions:
-  ///     Not everything in a program is a function. There are blocks of
-  ///     instructions that are simply labeled or even regions without symbol
-  ///     information that we don't what they are. We treat all of them as
-  ///     functions for simplicity.
-  ///
-  ///   Errors:
-  ///     Whenever an error is found, a new tree with a single segment is
-  ///     created. All consecutive errors after the original one are then
-  ///     appended to this segment. As a note, something that GDB does is to use
-  ///     some heuristics to merge trees that were interrupted by errors. We are
-  ///     leaving that out of scope until a feature like that one is really
-  ///     needed.
-
-  /// Forward declaration
-  class FunctionCall;
-  using FunctionCallUP = std::unique_ptr<FunctionCall>;
-
-  class FunctionCall {
-  public:
-    class TracedSegment {
-    public:
-      /// \param[in] cursor_sp
-      ///   A cursor pointing to the beginning of the segment.
-      ///
-      /// \param[in] symbol_info
-      ///   The symbol information of the first instruction of the segment.
-      ///
-      /// \param[in] call
-      ///   The FunctionCall object that owns this segment.
-      TracedSegment(const lldb::TraceCursorSP &cursor_sp,
-                    const SymbolInfo &symbol_info, FunctionCall &owning_call)
-          : m_first_insn_id(cursor_sp->GetId()),
-            m_last_insn_id(cursor_sp->GetId()),
-            m_first_symbol_info(symbol_info), m_last_symbol_info(symbol_info),
-            m_owning_call(owning_call) {}
-
-      /// \return
-      ///   The chronologically first instruction ID in this segment.
-      lldb::user_id_t GetFirstInstructionID() const;
-      /// \return
-      ///   The chronologically last instruction ID in this segment.
-      lldb::user_id_t GetLastInstructionID() const;
-
-      /// \return
-      ///   The symbol information of the chronologically first instruction ID
-      ///   in this segment.
-      const SymbolInfo &GetFirstInstructionSymbolInfo() const;
-
-      /// \return
-      ///   The symbol information of the chronologically last instruction ID in
-      ///   this segment.
-      const SymbolInfo &GetLastInstructionSymbolInfo() const;
-
-      /// \return
-      ///   Get the call that owns this segment.
-      const FunctionCall &GetOwningCall() const;
-
-      /// Append a new instruction to this segment.
-      ///
-      /// \param[in] cursor_sp
-      ///   A cursor pointing to the new instruction.
-      ///
-      /// \param[in] symbol_info
-      ///   The symbol information of the new instruction.
-      void AppendInsn(const lldb::TraceCursorSP &cursor_sp,
-                      const SymbolInfo &symbol_info);
-
-      /// Create a nested call at the end of this segment.
-      ///
-      /// \param[in] cursor_sp
-      ///   A cursor pointing to the first instruction of the nested call.
-      ///
-      /// \param[in] symbol_info
-      ///   The symbol information of the first instruction of the nested call.
-      FunctionCall &CreateNestedCall(const lldb::TraceCursorSP &cursor_sp,
-                                     const SymbolInfo &symbol_info);
-
-      /// Executed the given callback if there's a nested call at the end of
-      /// this segment.
-      void IfNestedCall(std::function<void(const FunctionCall &function_call)>
-                            callback) const;
-
-    private:
-      TracedSegment(const TracedSegment &) = delete;
-      TracedSegment &operator=(TracedSegment const &);
-
-      /// Delimiting instruction IDs taken chronologically.
-      /// \{
-      lldb::user_id_t m_first_insn_id;
-      lldb::user_id_t m_last_insn_id;
-      /// \}
-      /// An optional nested call starting at the end of this segment.
-      FunctionCallUP m_nested_call;
-      /// The symbol information of the delimiting instructions
-      /// \{
-      SymbolInfo m_first_symbol_info;
-      SymbolInfo m_last_symbol_info;
-      /// \}
-      FunctionCall &m_owning_call;
-    };
-
-    class UntracedPrefixSegment {
-    public:
-      /// Note: Untraced segments can only exist if have also seen a traced
-      /// segment of the same function call. Thus, we can use those traced
-      /// segments if we want symbol information and such.
-
-      UntracedPrefixSegment(FunctionCallUP &&nested_call)
-          : m_nested_call(std::move(nested_call)) {}
-
-      const FunctionCall &GetNestedCall() const;
-
-    private:
-      UntracedPrefixSegment(const UntracedPrefixSegment &) = delete;
-      UntracedPrefixSegment &operator=(UntracedPrefixSegment const &);
-      FunctionCallUP m_nested_call;
-    };
-
-    /// Create a new function call given an instruction. This will also create a
-    /// segment for that instruction.
-    ///
-    /// \param[in] cursor_sp
-    ///   A cursor pointing to the first instruction of that function call.
-    ///
-    /// \param[in] symbol_info
-    ///   The symbol information of that first instruction.
-    FunctionCall(const lldb::TraceCursorSP &cursor_sp,
-                 const SymbolInfo &symbol_info);
-
-    /// Append a new traced segment to this funciton call.
-    ///
-    /// \param[in] cursor_sp
-    ///   A cursor pointing to the first instruction of the new segment.
-    ///
-    /// \param[in] symbol_info
-    ///   The symbol information of that first instruction.
-    void AppendSegment(const lldb::TraceCursorSP &cursor_sp,
-                       const SymbolInfo &symbol_info);
-
-    /// \return
-    ///   The symbol info of some traced instruction of this call.
-    const SymbolInfo &GetSymbolInfo() const;
-
-    /// \return
-    ///   \b true if and only if the instructions in this function call are
-    ///   trace errors, in which case this function call is a fake one.
-    bool IsError() const;
-
-    /// \return
-    ///   The list of traced segments of this call.
-    const std::deque<TracedSegment> &GetTracedSegments() const;
-
-    /// \return
-    ///   A non-const reference to the most-recent traced segment.
-    TracedSegment &GetLastTracedSegment();
-
-    /// Create an untraced segment for this call that jumps to the provided
-    /// nested call.
-    void SetUntracedPrefixSegment(FunctionCallUP &&nested_call);
-
-    /// \return
-    ///   A optional to the untraced prefix segment of this call.
-    const llvm::Optional<UntracedPrefixSegment> &GetUntracedPrefixSegment() const;
-
-    /// \return
-    ///   A pointer to the parent call. It may be \b nullptr.
-    FunctionCall *GetParentCall() const;
-
-    void SetParentCall(FunctionCall &parent_call);
-
-  private:
-    /// An optional untraced segment that precedes all the traced segments.
-    llvm::Optional<UntracedPrefixSegment> m_untraced_prefix_segment;
-    /// The traced segments in order. We used a deque to prevent moving these
-    /// objects when appending to the list, which would happen with vector.
-    std::deque<TracedSegment> m_traced_segments;
-    /// The parent call, which might be null. Useful for reconstructing
-    /// callstacks.
-    FunctionCall *m_parent_call = nullptr;
-    /// Whether this call represents a list of consecutive errors.
-    bool m_is_error;
-  };
-
   /// Interface used to abstract away the format in which the instruction
   /// information will be dumped.
   class OutputWriter {
   public:
     virtual ~OutputWriter() = default;
 
     /// Notify this writer that the cursor ran out of data.
     virtual void NoMoreData() {}
 
     /// Dump a trace item (instruction, error or event).
     virtual void TraceItem(const TraceItem &item) = 0;
-
-    /// Dump a function call forest.
-    virtual void
-    FunctionCallForest(const std::vector<FunctionCallUP> &forest) = 0;
   };
 
   /// Create a instruction dumper for the cursor.
   ///
   /// \param[in] cursor
   ///     The cursor whose instructions will be dumped.
   ///
   /// \param[in] s
private:
   /// Create a trace item for the current position without symbol information.
   TraceItem CreatRawTraceItem();
 
   lldb::TraceCursorSP m_cursor_sp;
   TraceDumperOptions m_options;
   std::unique_ptr<OutputWriter> m_writer_up;
 };
 
+/// Dump the given call graph in textual format to the given stream.
+class TraceCallGraphDumper {
+public:
+  TraceCallGraphDumper(const lldb::TraceCursorSP &cursor_sp,
+                       const lldb::TraceCallGraphSP &call_graph_sp, Stream &s);
+
+  void Dump();
+
+private:
+  void DumpErrorSegment(TraceErrorSegment &error_segment);
+
+  void DumpCall(TraceCall &call);
+
+  void DumpFunctionCall(TraceCallFunction &call);
+
+  void DumpSymbolCall(TraceCallSymbol &call);
+
+  void DumpInlinedFunctionCall(TraceCallInlinedFunction &call);
+
+  void DumpSectionCall(TraceCallSection &call);
+
+  void DumpUnknownRegion(TraceCallUnknownRegion &call);
+
+  void DumpCallWrapper(
+      std::function<void()> call_description_dumper,
+      std::function<void(const TraceCursor &insn)> insn_description_dumper,
+      TraceCall &call_wrapper);
+
+  lldb::TraceCursorSP m_cursor_sp;
+  lldb::TraceCallGraphSP m_graph_sp;
+  Stream &m_s;
+  ExecutionContext m_exe_ctx;
+};
+
 } // namespace lldb_private
 
 #endif // LLDB_TARGET_TRACE_INSTRUCTION_DUMPER_H

lldb/include/lldb/lldb-enumerations.h

enum InstructionControlFlowKind {
   /// The instruction is a call-like far transfer.
   /// E.g. SYSCALL, SYSENTER, or FAR CALL.
   eInstructionControlFlowKindFarCall,
   /// The instruction is a return-like far transfer.
   /// E.g. SYSRET, SYSEXIT, IRET, or FAR RET.
   eInstructionControlFlowKindFarReturn,
   /// The instruction is a jump-like far transfer.
   /// E.g. FAR JMP.
-  eInstructionControlFlowKindFarJump
+  eInstructionControlFlowKindFarJump,
+  /// The instruction is an indirect jump or a far transfer.
+  eInstructionControlFlowKindIndirect
 };
 
 /// Watchpoint Kind.
 ///
 /// Indicates what types of events cause the watchpoint to fire. Used by Native
 /// *Protocol-related classes.
 FLAGS_ENUM(WatchpointKind){eWatchpointKindWrite = (1u << 0),
                            eWatchpointKindRead = (1u << 1)};

lldb/include/lldb/lldb-forward.h

 class ThreadPlanStepOverBreakpoint;
 class ThreadPlanStepRange;
 class ThreadPlanStepThrough;
 class ThreadPlanTracer;
 class ThreadSpec;
 class ThreadPostMortemTrace;
 class ThreadedCommunication;
 class Trace;
+class TraceCallGraph;
 class TraceCursor;
 class TraceExporter;
 class Type;
 class TypeAndOrName;
 class TypeCategoryImpl;
 class TypeCategoryMap;
 class TypeEnumMemberImpl;
 class TypeEnumMemberListImpl;

 typedef std::weak_ptr<lldb_private::Thread> ThreadWP;
 typedef std::shared_ptr<lldb_private::ThreadCollection> ThreadCollectionSP;
 typedef std::shared_ptr<lldb_private::ThreadPlan> ThreadPlanSP;
 typedef std::shared_ptr<lldb_private::ThreadPostMortemTrace>
     ThreadPostMortemTraceSP;
 typedef std::weak_ptr<lldb_private::ThreadPlan> ThreadPlanWP;
 typedef std::shared_ptr<lldb_private::ThreadPlanTracer> ThreadPlanTracerSP;
 typedef std::shared_ptr<lldb_private::Trace> TraceSP;
-typedef std::unique_ptr<lldb_private::TraceExporter> TraceExporterUP;
+typedef std::shared_ptr<lldb_private::TraceCallGraph> TraceCallGraphSP;
 typedef std::shared_ptr<lldb_private::TraceCursor> TraceCursorSP;
+typedef std::unique_ptr<lldb_private::TraceExporter> TraceExporterUP;
 typedef std::shared_ptr<lldb_private::Type> TypeSP;
 typedef std::weak_ptr<lldb_private::Type> TypeWP;
 typedef std::shared_ptr<lldb_private::TypeCategoryImpl> TypeCategoryImplSP;
 typedef std::shared_ptr<lldb_private::TypeImpl> TypeImplSP;
 typedef std::shared_ptr<lldb_private::TypeMemberFunctionImpl>
     TypeMemberFunctionImplSP;
 typedef std::shared_ptr<lldb_private::TypeEnumMemberImpl> TypeEnumMemberImplSP;
 typedef std::shared_ptr<lldb_private::TypeFilterImpl> TypeFilterImplSP;

lldb/source/Commands/CommandObjectThread.cpp

 }
 
 // CommandObjectTraceDumpFunctionCalls
 #define LLDB_OPTIONS_thread_trace_dump_function_calls
 #include "CommandOptions.inc"
 
 class CommandObjectTraceDumpFunctionCalls : public CommandObjectParsed {
 public:
+  enum class PrintStyle { Normal, JSON, PrettyJSON };
+
   class CommandOptions : public Options {
   public:
     CommandOptions() { 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 'j': {
-        m_dumper_options.json = true;
+        m_options.print_style = PrintStyle::JSON;
         break;
       }
       case 'J': {
-        m_dumper_options.json = true;
-        m_dumper_options.pretty_print_json = true;
+        m_options.print_style = PrintStyle::PrettyJSON;
         break;
       }
       case 'F': {
-        m_output_file.emplace(option_arg);
+        m_options.output_file.emplace(option_arg);
+        break;
+      }
+      case 'f': {
+        int32_t id;
+        if (option_arg.empty() || option_arg.getAsInteger(0, id) || id < 0)
+          error.SetErrorStringWithFormat(
+              "invalid integer value for option '%s'",
+              option_arg.str().c_str());
+        else
+          m_options.from_insn_id = id;
+        break;
+      }
+      case 't': {
+        int32_t id;
+        if (option_arg.empty() || option_arg.getAsInteger(0, id) || id < 0)
+          error.SetErrorStringWithFormat(
+              "invalid integer value for option '%s'",
+              option_arg.str().c_str());
+        else
+          m_options.to_insn_id = id;
         break;
       }
       default:
         llvm_unreachable("Unimplemented option");
       }
       return error;
     }
 
     void OptionParsingStarting(ExecutionContext *execution_context) override {
-      m_dumper_options = {};
-      m_output_file = llvm::None;
+      m_options = {};
     }
 
     llvm::ArrayRef<OptionDefinition> GetDefinitions() override {
       return llvm::makeArrayRef(g_thread_trace_dump_function_calls_options);
     }
 
-    static const size_t kDefaultCount = 20;
-
     // Instance variables to hold the values for command options.
-    TraceDumperOptions m_dumper_options;
-    llvm::Optional<FileSpec> m_output_file;
+    struct {
+      llvm::Optional<FileSpec> output_file;
+      PrintStyle print_style = PrintStyle::Normal;
+      llvm::Optional<lldb::user_id_t> from_insn_id;
+      llvm::Optional<lldb::user_id_t> to_insn_id;
+    } m_options;
   };
 
   CommandObjectTraceDumpFunctionCalls(CommandInterpreter &interpreter)
       : CommandObjectParsed(
             interpreter, "thread trace dump function-calls",
             "Dump the traced function-calls for one thread. If no "
             "thread is specified, the current thread is used.",
             nullptr,

 protected:
   bool DoExecute(Args &args, CommandReturnObject &result) override {
     ThreadSP thread_sp = GetSingleThreadFromArgs(m_exe_ctx, args, result);
     if (!thread_sp) {
       result.AppendError("invalid thread\n");
       return false;
     }
 
-    llvm::Expected<TraceCursorSP> cursor_or_error =
-        m_exe_ctx.GetTargetSP()->GetTrace()->CreateNewCursor(*thread_sp);
+    TraceSP trace_sp = m_exe_ctx.GetTargetSP()->GetTrace();
+    llvm::Expected<TraceCursorSP> cursor_sp =
+        trace_sp->CreateNewCursor(*thread_sp);
+    if (!cursor_sp) {
+      result.AppendError(llvm::toString(cursor_sp.takeError()));
+      return false;
+    }
 
-    if (!cursor_or_error) {
-      result.AppendError(llvm::toString(cursor_or_error.takeError()));
+    llvm::Expected<TraceCallGraphSP> graph_sp =
+        trace_sp->CreateCallGraph(*thread_sp, m_options.m_options.from_insn_id,
+                                  m_options.m_options.to_insn_id);
+
+    if (!graph_sp) {
+      result.AppendError(llvm::toString(graph_sp.takeError()));
       return false;
     }
-    TraceCursorSP &cursor_sp = *cursor_or_error;
 
     llvm::Optional<StreamFile> out_file;
-    if (m_options.m_output_file) {
-      out_file.emplace(m_options.m_output_file->GetPath().c_str(),
+    if (m_options.m_options.output_file) {
+      out_file.emplace(m_options.m_options.output_file->GetPath().c_str(),
                        File::eOpenOptionWriteOnly | File::eOpenOptionCanCreate |
                            File::eOpenOptionTruncate);
     }
+    TraceCallGraphDumper(*cursor_sp, *graph_sp,
+                         out_file ? *out_file : result.GetOutputStream())
+        .Dump();
 
-    m_options.m_dumper_options.forwards = true;
-
-    TraceDumper dumper(std::move(cursor_sp),
-                       out_file ? *out_file : result.GetOutputStream(),
-                       m_options.m_dumper_options);
-
-    dumper.DumpFunctionCalls();
     return true;
   }
 
   CommandOptions m_options;
 };
 
 // CommandObjectTraceDumpInstructions
 #define LLDB_OPTIONS_thread_trace_dump_instructions

lldb/source/Commands/Options.td

def thread_trace_dump_function_calls_file : Option<"file", "F">, Group<1>,
     Desc<"Dump the function calls to a file instead of the standard output.">;
   def thread_trace_dump_function_calls_json: Option<"json", "j">,
     Group<1>,
     Desc<"Dump in simple JSON format.">;
   def thread_trace_dump_function_calls_pretty_json: Option<"pretty-json", "J">,
     Group<1>,
     Desc<"Dump in JSON format but pretty printing the output for easier "
     "readability.">;
+  def thread_trace_dump_function_calls_from: Option<"from-id", "f">,
+    Group<1>,
+    Arg<"Index">,
+    Desc<"Create the call graph from scratch starting at the trace item specified by this argument>">;
+  def thread_trace_dump_function_calls_to: Option<"to-id", "t">,
+    Group<1>,
+    Arg<"Index">,
+    Desc<"Create the call graph from scratch ending inclusively at the trace item specified by this argument>">;
 }
 
 let Command = "thread trace dump instructions" in {
   def thread_trace_dump_instructions_forwards: Option<"forwards", "f">,
     Group<1>,
     Desc<"If specified, the trace is traversed forwards chronologically "
     "starting at the oldest instruction. Otherwise, it starts at the most "
     "recent one and the traversal is backwards.">;

lldb/source/Core/Disassembler.cpp

const char *Instruction::GetNameForInstructionControlFlowKind(
   case eInstructionControlFlowKindCondJump:
     return "cond jump";
   case eInstructionControlFlowKindFarCall:
     return "far call";
   case eInstructionControlFlowKindFarReturn:
     return "far return";
   case eInstructionControlFlowKindFarJump:
     return "far jump";
+  case eInstructionControlFlowKindIndirect:
+    return "indirect or far jump";
   }
   llvm_unreachable("Fully covered switch above!");
 }
 
 void Instruction::Dump(lldb_private::Stream *s, uint32_t max_opcode_byte_size,
                        bool show_address, bool show_bytes,
                        bool show_control_flow_kind,
                        const ExecutionContext *exe_ctx,

lldb/source/Plugins/Trace/intel-pt/DecodedThread.h

public:
   ///   The requested nanoseconds range, or \a llvm::None if not available.
   llvm::Optional<DecodedThread::NanosecondsRange>
   GetNanosecondsRangeByIndex(uint64_t item_index);
 
   /// \return
   ///     The load address of the instruction at the given index.
   lldb::addr_t GetInstructionLoadAddress(uint64_t item_index) const;
 
+  lldb::InstructionControlFlowKind
+  GetInstructionControlFlowKind(uint64_t item_index) const;
+
   /// \return
   ///     The number of instructions in this trace (not trace items).
   uint64_t GetTotalInstructionCount() const;
 
   /// Return an object with statistics of the trace events that happened.
   ///
   /// \return
   ///   The stats object of all the events.
union TraceItemStorage {
 
     /// The event kind of this item if it's an event
     lldb::TraceEvent event;
 
     /// The string message of this item if it's an error
     const char *error;
   };
 
+  struct TraceInstructionExtraInfo {
+    uint8_t control_flow_kind; // InstructionControlFlowKind
+    uint8_t byte_size;
+  };
+
   /// Create a new trace item.
   ///
   /// \return
   ///   The index of the new item.
   DecodedThread::TraceItemStorage &CreateNewTraceItem(lldb::TraceItemKind kind);
 
   /// Most of the trace data is stored here.
   std::vector<TraceItemStorage> m_item_data;
+  std::vector<TraceInstructionExtraInfo> m_insn_extra_info;
   /// The TraceItemKind for each trace item encoded as uint8_t. We don't include
   /// it in TraceItemStorage to avoid padding.
   std::vector<uint8_t> m_item_kinds;
 
   /// This map contains the TSCs of the decoded trace items. It maps
   /// `item index -> TSC`, where `item index` is the first index
   /// at which the mapped TSC first appears. We use this representation because
   /// TSCs are sporadic and we can think of them as ranges.

lldb/source/Plugins/Trace/intel-pt/DecodedThread.cpp

 
 uint64_t DecodedThread::GetItemsCount() const { return m_item_kinds.size(); }
 
 lldb::addr_t
 DecodedThread::GetInstructionLoadAddress(uint64_t item_index) const {
   return m_item_data[item_index].load_address;
 }
 
+InstructionControlFlowKind
+DecodedThread::GetInstructionControlFlowKind(uint64_t item_index) const {
+  return static_cast<InstructionControlFlowKind>(
+      m_insn_extra_info[item_index].control_flow_kind);
+}
+
 lldb::addr_t
 DecodedThread::GetSyncPointOffsetByIndex(uint64_t item_index) const {
   return m_psb_offsets.find(item_index)->second;
 }
 
 ThreadSP DecodedThread::GetThread() { return m_thread_sp; }
 
 DecodedThread::TraceItemStorage &
 DecodedThread::CreateNewTraceItem(lldb::TraceItemKind kind) {
   m_item_kinds.push_back(kind);
   m_item_data.emplace_back();
+  m_insn_extra_info.emplace_back();
   if (m_last_tsc)
     (*m_last_tsc)->second.items_count++;
   if (m_last_nanoseconds)
     (*m_last_nanoseconds)->second.items_count++;
   return m_item_data.back();
 }
 
 void DecodedThread::NotifySyncPoint(lldb::addr_t psb_offset) {
uint64_t DecodedThread::GetTotalInstructionCount() const {
   return m_insn_count;
 }
 
 void DecodedThread::AppendEvent(lldb::TraceEvent event) {
   CreateNewTraceItem(lldb::eTraceItemKindEvent).event = event;
   m_events_stats.RecordEvent(event);
 }
 
+static InstructionControlFlowKind ClassifyLibiptInsnKind(const pt_insn &insn) {
+  switch (insn.iclass) {
+  case ptic_other:
+  case ptic_ptwrite:
+    return eInstructionControlFlowKindOther;
+  case ptic_call:
+    return eInstructionControlFlowKindCall;
+  case ptic_far_call:
+    return eInstructionControlFlowKindFarCall;
+  case ptic_return:
+    return eInstructionControlFlowKindReturn;
+  case ptic_far_return:
+    return eInstructionControlFlowKindFarReturn;
+  case ptic_jump:
+    return eInstructionControlFlowKindJump;
+  case ptic_cond_jump:
+    return eInstructionControlFlowKindCondJump;
+  case ptic_far_jump:
+    return eInstructionControlFlowKindFarJump;
+  case ptic_indirect:
+    return eInstructionControlFlowKindIndirect;
+  case ptic_unknown:
+    return eInstructionControlFlowKindUnknown;
+  }
+}
+
 void DecodedThread::AppendInstruction(const pt_insn &insn) {
   CreateNewTraceItem(lldb::eTraceItemKindInstruction).load_address = insn.ip;
+  m_insn_extra_info.back().byte_size = insn.size;
+  m_insn_extra_info.back().control_flow_kind = ClassifyLibiptInsnKind(insn);
   m_insn_count++;
 }
 
 void DecodedThread::AppendError(const IntelPTError &error) {
   CreateNewTraceItem(lldb::eTraceItemKindError).error =
       ConstString(error.message()).AsCString();
   m_error_stats.RecordError(/*fatal=*/false);
 }

 
 DecodedThread::DecodedThread(
     ThreadSP thread_sp,
     const llvm::Optional<LinuxPerfZeroTscConversion> &tsc_conversion)
     : m_thread_sp(thread_sp), m_tsc_conversion(tsc_conversion) {}
 
 size_t DecodedThread::CalculateApproximateMemoryUsage() const {
   return sizeof(TraceItemStorage) * m_item_data.size() +
+         sizeof(TraceInstructionExtraInfo) * m_insn_extra_info.size() +
          sizeof(uint8_t) * m_item_kinds.size() +
          (sizeof(uint64_t) + sizeof(TSC)) * m_tscs.size() +
          (sizeof(uint64_t) + sizeof(uint64_t)) * m_nanoseconds.size() +
          (sizeof(uint64_t) + sizeof(lldb::cpu_id_t)) * m_cpus.size();
 }

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.h

public:
   lldb::user_id_t GetId() const override;
 
   bool HasId(lldb::user_id_t id) const override;
 
   llvm::Optional<double> GetWallClockTime() const override;
 
   llvm::Optional<std::string> GetSyncPointMetadata() const override;
 
+  lldb::InstructionControlFlowKind
+  GetInstructionControlFlowKind() const override;
+
 private:
   /// Clear the current TSC and nanoseconds ranges if after moving they are not
   /// valid anymore.
   void ClearTimingRangesIfInvalid();
 
   /// Get or calculate the TSC range that includes the current trace item.
   const llvm::Optional<DecodedThread::TSCRange> &GetTSCRange() const;
 

lldb/source/Plugins/Trace/intel-pt/TraceCursorIntelPT.cpp

 
 user_id_t TraceCursorIntelPT::GetId() const { return m_pos; }
 
 Optional<std::string> TraceCursorIntelPT::GetSyncPointMetadata() const {
   return formatv("offset = 0x{0:x}",
                  m_decoded_thread_sp->GetSyncPointOffsetByIndex(m_pos))
       .str();
 }
+
+InstructionControlFlowKind
+TraceCursorIntelPT::GetInstructionControlFlowKind() const {
+  return m_decoded_thread_sp->GetInstructionControlFlowKind(m_pos);
+}

lldb/source/Plugins/Trace/intel-pt/TraceIntelPT.cpp

void TraceIntelPT::DumpTraceInfo(Thread &thread, Stream &s, bool verbose,
 
   // Instruction events stats
   {
     const DecodedThread::EventsStats &events_stats =
         decoded_thread_sp->GetEventsStats();
     s << "\n  Events:\n";
     s.Format("    Number of individual events: {0}\n",
              events_stats.total_count);
-    for (const auto &event_to_count : events_stats.events_counts) {
-      s.Format("      {0}: {1}\n",
-               TraceCursor::EventKindToString(event_to_count.first),
-               event_to_count.second);
+    for (auto it = events_stats.events_counts.begin();
+         it != events_stats.events_counts.end(); ++it) {
+      s.Format("      {0}: {1}\n", TraceCursor::EventKindToString(it->first),
+               it->second);
     }
   }
   // Trace error stats
   {
     const DecodedThread::ErrorStats &error_stats =
         decoded_thread_sp->GetErrorStats();
     s << "\n  Errors:\n";
     s.Format("    Number of individual errors: {0}\n",

lldb/source/Target/CMakeLists.txt

add_lldb_library(lldbTarget
   ThreadPlanStepOverRange.cpp
   ThreadPlanStepRange.cpp
   ThreadPlanStepThrough.cpp
   ThreadPlanStepUntil.cpp
   ThreadPlanTracer.cpp
   ThreadPlanStack.cpp
   ThreadSpec.cpp
   Trace.cpp
+  TraceCallGraph.cpp
   TraceCursor.cpp
   TraceExporter.cpp
   TraceDumper.cpp
   UnixSignals.cpp
   UnwindAssembly.cpp
   UnwindLLDB.cpp
 
   LINK_LIBS

lldb/source/Target/Trace.cpp

std::vector<Process *> Trace::GetAllProcesses() {
   return GetPostMortemProcesses();
 }
 
 uint32_t Trace::GetStopID() {
   RefreshLiveProcessState();
   return m_stop_id;
 }
 
+Expected<TraceCallGraphSP>
+Trace::CreateCallGraph(Thread &thread, Optional<lldb::user_id_t> from_id,
+                       Optional<lldb::user_id_t> to_id) {
+  if (Expected<TraceCursorSP> cursor_sp = CreateNewCursor(thread)) {
+    TraceCallGraphSP graph_sp =
+        TraceCallGraph::Build(**cursor_sp, from_id, to_id);
+    return graph_sp;
+  } else {
+    return cursor_sp.takeError();
+  }
+}
+
 llvm::Expected<FileSpec>
 Trace::GetPostMortemThreadDataFile(lldb::tid_t tid, llvm::StringRef kind) {
   Storage &storage = GetUpdatedStorage();
   if (Optional<FileSpec> file =
           Lookup(storage.postmortem_thread_data, tid, ConstString(kind)))
     return *file;
   else
     return createStringError(

lldb/source/Target/TraceCallGraph.cpp

+//===-- TraceCallGraph.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/TraceCallGraph.h"
+#include "lldb/Core/Section.h"
+#include "lldb/Symbol/Block.h"
+#include "lldb/Symbol/Function.h"
+#include "lldb/Symbol/Symbol.h"
+#include "lldb/Target/Target.h"
+#include "lldb/Target/TraceCursor.h"
+
+using namespace lldb;
+using namespace lldb_private;
+using namespace lldb_private::TraceCallUtils;
+using namespace llvm;
+
+// Overload pattern-based syntax sugar for easier variant matching.
+template <typename... Ts> struct match : Ts... { using Ts::operator()...; };
+template <class... Ts> match(Ts...) -> match<Ts...>;
+
+std::string TraceCallUtils::ToDebugString(TraceCall &call_wrapper) {
+  return std::visit(match{[&](TraceCallInlinedFunction &call) {
+                            return std::string("inlined function: ") +
+                                   call.GetInlinedBlock()
+                                       .GetInlinedFunctionInfo()
+                                       ->GetName()
+                                       .AsCString();
+                          },
+                          [&](TraceCallFunction &call) {
+                            return std::string("function: ") +
+                                   call.GetFunction().GetName().AsCString();
+                          },
+                          [&](TraceCallSymbol &call) {
+                            return std::string("symbol: ") +
+                                   call.GetSymbol().GetName().AsCString();
+                          },
+                          [&](TraceCallSection &call) {
+                            std::string str;
+                            {
+                              raw_string_ostream raw_ostream(str);
+                              raw_ostream << "section: ";
+                              call.GetSection()->DumpName(raw_ostream);
+                            }
+                            return str;
+                          },
+                          [&](TraceCallUnknownRegion &call) {
+                            return std::string("unkonwn region");
+                          }},
+                    call_wrapper);
+}
+
+TraceCall *TraceCallUtils::GetParent(TraceCall &call_wrapper) {
+  return std::visit([&](auto &&call) { return call.GetParent(); },
+                    call_wrapper);
+}
+
+void TraceCallUtils::SetParent(TraceCall &child, TraceCall &parent) {
+  std::visit([&](auto &&call) { call.SetParent(parent); }, child);
+}
+
+TraceCall &TraceCallUtils::GetRecursivelyMostRecentCall(TraceCall &call) {
+  return std::visit(
+      [&](auto &&arg) -> TraceCall & {
+        if (TraceCall *child = arg.TryGetChildCallOfLastSegment())
+          return GetRecursivelyMostRecentCall(*child);
+        return call;
+      },
+      call);
+}
+
+static TraceCallInlinedFunction *
+TryGetInlinedFunction(TraceCall *call, const Block &inlined_block) {
+  if (TraceCallInlinedFunction *inlined_function =
+          std::get_if<TraceCallInlinedFunction>(call);
+      inlined_function &&
+      &inlined_function->GetInlinedBlock() == &inlined_block)
+    return inlined_function;
+  return nullptr;
+}
+
+TraceCallSegment::TraceCallSegment(const TraceCursor &insn) {
+  lldb::user_id_t id = insn.GetId();
+  m_insn_ids_range.emplace(id, id);
+  m_exclusive_insn_count++;
+}
+
+Optional<std::pair<lldb::user_id_t, lldb::user_id_t>>
+TraceCallSegment::GetRange() const {
+  return m_insn_ids_range;
+}
+
+uint64_t TraceCallSegment::GetExclusiveInsnCount() const {
+  return m_exclusive_insn_count;
+}
+
+TraceCall &TraceCallSegment::SetChildCall(TraceCallUP &&trace_call_up) {
+  assert(!m_child_call_up &&
+         "Can't set a child call for a segment that already has one. It would "
+         "create a dangling subtree.");
+  m_child_call_up = std::move(trace_call_up);
+  return *m_child_call_up;
+}
+
+TraceCallSegment::TraceCallSegment(TraceCallUP &&trace_call_up)
+    : m_child_call_up(std::move(trace_call_up)) {}
+
+TraceCall *TraceCallSegment::GetChildCall() { return m_child_call_up.get(); }
+
+bool TraceCallSegment::TryAppendInstruction(const TraceCursor &insn) {
+  if (GetChildCall()) {
+    // If a segment has a child call, then it has ended and we must resume in a
+    // new segment.
+    return false;
+  }
+  lldb::user_id_t id = insn.GetId();
+  m_exclusive_insn_count++;
+  if (!m_insn_ids_range)
+    m_insn_ids_range.emplace(id, id);
+  else
+    m_insn_ids_range->second = id;
+  return true;
+}
+
+TraceCall *TraceCallBase::TryGetChildCallOfLastSegment() {
+  if (TraceCallSegment *last_segment = TryGetLastSegment())
+    return last_segment->GetChildCall();
+  return nullptr;
+}
+
+TraceCall &TraceCallBase::GetChildCallOfLastSegment() {
+  return *TryGetChildCallOfLastSegment();
+}
+
+TraceCallSegment *TraceCallBase::TryGetLastSegment() {
+  return !m_segments.empty() ? m_segments.back().get() : nullptr;
+}
+
+TraceCallSegment &TraceCallBase::GetLastSegment() {
+  return *TryGetLastSegment();
+}
+
+ArrayRef<TraceCallSegmentUP> TraceCallBase::GetSegments() const {
+  return m_segments;
+}
+
+TraceCall *TraceCallBase::GetParent() { return m_parent; }
+
+void TraceCallBase::SetParent(TraceCall &parent) { m_parent = &parent; }
+
+TraceCall &TraceCallBase::SetLastSegmentChildCall(TraceCallUP &&trace_call_up) {
+  TraceCall &new_call = GetLastSegment().SetChildCall(std::move(trace_call_up));
+  TraceCallUtils::SetParent(new_call, GetWrappingCall());
+  return new_call;
+}
+
+void TraceCallBase::PrependSyntheticSegmentWithChildCall(
+    TraceCallUP &&trace_call_up) {
+  TraceCallUtils::SetParent(*trace_call_up, GetWrappingCall());
+  TraceCallSegmentUP new_segment_up =
+      std::make_unique<TraceCallSegment>(std::move(trace_call_up));
+  m_segments.insert(m_segments.begin(), std::move(new_segment_up));
+}
+
+void TraceCallBase::AppendInstruction(const TraceCursor &insn) {
+  // We try to append the instruction to the last segment of the tree call. If
+  // this fails, then we create a new segment with this instruction.
+  if (TraceCallSegment *last_segment = TryGetLastSegment();
+      !last_segment || !last_segment->TryAppendInstruction(insn))
+    m_segments.emplace_back(std::make_unique<TraceCallSegment>(insn));
+}
+
+TraceCallSection::TraceCallSection(const SectionSP &section)
+    : m_section_sp(section) {}
+
+TraceCallSection::TraceCallSection(const SectionSP &section,
+                                   const TraceCursor &cursor)
+    : TraceCallSection(section) {
+  AppendInstruction(cursor);
+}
+
+const SectionSP &TraceCallSection::GetSection() const { return m_section_sp; }
+
+TraceCallFunction::TraceCallFunction(Function &function)
+    : m_function(function) {}
+
+TraceCallFunction::TraceCallFunction(Function &function,
+                                     const TraceCursor &insn)
+    : TraceCallFunction(function) {
+  AppendInstruction(insn);
+}
+
+TraceCall &TraceCallFunctionLike::CreateNestedInlinedBlockCalls(
+    const TraceCursor &insn, ArrayRef<Block *> nested_inlined_blocks,
+    TraceCallFunction &owning_function) {
+  if (nested_inlined_blocks.empty()) {
+    // This is the base case in which we just append an instruction
+    AppendInstruction(insn);
+    return *this;
+  }
+
+  Block *inlined_block = nested_inlined_blocks[0];
+  ArrayRef<Block *> remaining_inlined_blocks = nested_inlined_blocks.slice(1);
+  // We first try to reuse the most recent child of this function, otherwise we
+  // create a new one
+  if (TraceCallInlinedFunction *inlined_call =
+          TryGetInlinedFunction(TryGetChildCallOfLastSegment(), *inlined_block))
+    return inlined_call->CreateNestedInlinedBlockCalls(
+        insn, remaining_inlined_blocks, owning_function);
+  // Here we'll create a new child
+  return AppendSegmentWithNewChildCall<TraceCallInlinedFunction>(
+             *inlined_block, owning_function)
+      .CreateNestedInlinedBlockCalls(insn, remaining_inlined_blocks,
+                                     owning_function);
+}
+
+TraceCall &
+TraceCallFunction::CreateNestedInlinedBlockCalls(Block &deepest_inlined_block,
+                                                 const TraceCursor &insn) {
+  std::vector<Block *> nested_inlined_blocks;
+  for (Block *block = &deepest_inlined_block; block;
+       block = block->GetInlinedParent()) {
+    nested_inlined_blocks.push_back(block);
+  }
+  std::reverse(nested_inlined_blocks.begin(), nested_inlined_blocks.end());
+  return TraceCallFunctionLike::CreateNestedInlinedBlockCalls(
+      insn, nested_inlined_blocks, *this);
+}
+
+Function &TraceCallFunction::GetFunction() { return m_function; }
+
+TraceCallInlinedFunction::TraceCallInlinedFunction(
+    Block &inlined_block, TraceCallFunction &owning_function_call)
+    : m_inlined_block(inlined_block),
+      m_owning_function_call(owning_function_call) {}
+
+TraceCallInlinedFunction::TraceCallInlinedFunction(
+    Block &inlined_block, TraceCallFunction &owning_function_call,
+    const TraceCursor &cursor)
+    : TraceCallInlinedFunction(inlined_block, owning_function_call) {
+  AppendInstruction(cursor);
+}
+
+Block &TraceCallInlinedFunction::GetInlinedBlock() { return m_inlined_block; }
+
+TraceCallFunction &TraceCallInlinedFunction::GetOwningFunctionCall() {
+  return m_owning_function_call;
+}
+
+TraceCallSymbol::TraceCallSymbol(Symbol &symbol) : m_symbol(symbol) {}
+
+TraceCallSymbol::TraceCallSymbol(Symbol &symbol, const TraceCursor &cursor)
+    : TraceCallSymbol(symbol) {
+  AppendInstruction(cursor);
+}
+
+Symbol &TraceCallSymbol::GetSymbol() { return m_symbol; }
+
+TraceCallUnknownRegion::TraceCallUnknownRegion(const TraceCursor &cursor) {
+  AppendInstruction(cursor);
+}
+
+static Block *TryGetInlinedBlock(const SymbolContext &sc) {
+  return sc.block ? sc.block->GetContainingInlinedBlock() : nullptr;
+}
+
+static TraceCallUP
+CreateTraceCallForInstruction(const TraceCursor &insn, Target &target,
+                              const Address &address,
+                              const SymbolContext &symbol_context) {
+  if (symbol_context.function) {
+    TraceCallUP trace_call_up =
+        CreateTraceCall<TraceCallFunction>(*symbol_context.function);
+    TraceCallFunction &function = std::get<TraceCallFunction>(*trace_call_up);
+    if (Block *inlined_block = TryGetInlinedBlock(symbol_context)) {
+      function.CreateNestedInlinedBlockCalls(*inlined_block, insn);
+    } else {
+      function.AppendInstruction(insn);
+    }
+    return trace_call_up;
+  } else if (symbol_context.symbol) {
+    return CreateTraceCall<TraceCallSymbol>(*symbol_context.symbol, insn);
+  } else if (const SectionSP &section_sp = address.GetSection()) {
+    return CreateTraceCall<TraceCallSection>(section_sp, insn);
+  }
+  return CreateTraceCall<TraceCallUnknownRegion>(insn);
+}
+
+static TraceCallUP CreateTraceCallForInstruction(const TraceCursor &insn,
+                                                 Target &target) {
+  Address address;
+  SymbolContext symbol_context;
+  if (address.SetLoadAddress(insn.GetLoadAddress(), &target)) {
+    address.CalculateSymbolContext(&symbol_context, eSymbolContextFunction |
+                                                        eSymbolContextBlock |
+                                                        eSymbolContextSymbol);
+  }
+  return CreateTraceCallForInstruction(insn, target, address, symbol_context);
+}
+
+TraceInstructionCallTree::TraceInstructionCallTree(const TraceCursor &insn,
+                                                   Target &target)
+    : m_root_up(CreateTraceCallForInstruction(insn, target)),
+      m_active_call{GetRecursivelyMostRecentCall(*m_root_up),
+                    insn.GetInstructionControlFlowKind()} {}
+
+void TraceInstructionCallTree::AppendInstruction(const TraceCursor &insn,
+                                                 Target &target) {
+  TraceCall &new_active_call = GetRecursivelyMostRecentCall(
+      DoAppendInstruction(insn, target, m_active_call.call,
+                          m_active_call.last_insn_control_flow_kind));
+  m_active_call = {new_active_call, insn.GetInstructionControlFlowKind()};
+}
+
+TraceCall &TraceInstructionCallTree::GetRootCall() { return *m_root_up; }
+
+static bool IsControlFlowKindAStrictCall(InstructionControlFlowKind kind) {
+  switch (kind) {
+  case lldb::eInstructionControlFlowKindCall:
+  case lldb::eInstructionControlFlowKindFarCall:
+    return true;
+  case lldb::eInstructionControlFlowKindUnknown:
+  case lldb::eInstructionControlFlowKindOther:
+  case lldb::eInstructionControlFlowKindReturn:
+  case lldb::eInstructionControlFlowKindJump:
+  case lldb::eInstructionControlFlowKindCondJump:
+  case lldb::eInstructionControlFlowKindFarReturn:
+  case lldb::eInstructionControlFlowKindFarJump:
+  case lldb::eInstructionControlFlowKindIndirect:
+    return false;
+  }
+}
+
+static bool IsSameNonInlineSymbolContext(TraceCall &call_wrapper,
+                                         SymbolContext &sc, Address &addr) {
+  return std::visit(
+      match{[&](TraceCallInlinedFunction &call) { return false; },
+            [&](TraceCallFunction &call) {
+              return &call.GetFunction() == sc.function;
+            },
+            [&](TraceCallSymbol &call) {
+              return !sc.function && &call.GetSymbol() == sc.symbol;
+            },
+            [&](TraceCallSection &call) {
+              return !sc.function && !sc.symbol &&
+                     call.GetSection() == addr.GetSection();
+            },
+            [&](TraceCallUnknownRegion &call) {
+              return !sc.function && !sc.symbol && !addr.GetSection();
+            }},
+      call_wrapper);
+}
+
+TraceCall &TraceInstructionCallTree::AppendReturnedInstruction(
+    const TraceCursor &insn, SymbolContext &sc, Address &addr, Target &target,
+    TraceCall &active_call_wrapper) {
+
+  // We omit the current node because we can't return to itself.
+  TraceCall *ancestor = GetParent(active_call_wrapper);
+
+  for (; ancestor; ancestor = GetParent(*ancestor)) {
+    // This loop traverses the tree until it finds a call that we can return to.
+    if (IsSameNonInlineSymbolContext(*ancestor, sc, addr)) {
+      // We returned to this symbol, so we are assuming we are returning there
+      // Note: If this is not robust enough, we should actually check if we
+      // returning to the instruction that follows the last instruction from
+      // that call, as that's the behavior of CALL instructions.
+      std::visit(
+          [&](auto &&ancestor_call) {
+            using T = std::decay_t<decltype(ancestor_call)>;
+            if constexpr (std::is_same_v<T, TraceCallFunction>) {
+              if (Block *inlined_block = TryGetInlinedBlock(sc)) {
+                ancestor_call.CreateNestedInlinedBlockCalls(*inlined_block,
+                                                            insn);
+                return;
+              }
+            }
+            ancestor_call.AppendInstruction(insn);
+          },
+          *ancestor);
+      return *ancestor;
+    }
+  }
+
+  // We didn't find the call we were looking for, so we now create a synthetic
+  // one that will contain the new instruction in its first traced segment.
+  // This kind of constructor will take care of inlined functions
+  TraceCallUP new_root = CreateTraceCallForInstruction(insn, target, addr, sc);
+  // This new root will own the previous root through an systhetic segment.
+  std::visit(
+      [&](auto &&new_call) {
+        new_call.PrependSyntheticSegmentWithChildCall(std::move(m_root_up));
+      },
+      *new_root);
+  m_root_up = std::move(new_root);
+  return *m_root_up;
+}
+
+TraceCall &TraceInstructionCallTree::DoAppendInstruction(
+    const TraceCursor &insn, Target &target, TraceCall &active_call_wrapper,
+    InstructionControlFlowKind active_insn_control_flow_kind) {
+  return std::visit(
+      [&](auto &&active_call) -> TraceCall & {
+        using T = std::decay_t<decltype(active_call)>;
+        // The active call must have at least one instruction, therefore it must
+        // have at least one segment
+        assert(!active_call.TryGetChildCallOfLastSegment() &&
+               "The active segment can't have a child call because otherwise "
+               "the child would be the active one.");
+
+        Address address;
+        SymbolContext symbol_context;
+        if (address.SetLoadAddress(insn.GetLoadAddress(), &target)) {
+          address.CalculateSymbolContext(
+              &symbol_context, eSymbolContextFunction | eSymbolContextBlock |
+                                   eSymbolContextSymbol);
+        }
+
+        // We first check if we are in an inline block, as they need to be
+        // handled in a very different way
+        if (Block *inlined_block = TryGetInlinedBlock(symbol_context)) {
+          // We need to create or find the owning function. If the active call
+          // is part of the same function, we are continuing there. Otherwise,
+          // we are returning somewhere in the call stack, which means that in
+          // the worst case we need to recreate the incomplete parent.
+          TraceCallFunction *owning_function = nullptr;
+          if constexpr (std::is_same_v<T, TraceCallInlinedFunction>) {
+            owning_function = &active_call.GetOwningFunctionCall();
+          } else if constexpr (std::is_same_v<T, TraceCallFunction>) {
+            owning_function = &active_call;
+          }
+          if (owning_function &&
+              &owning_function->GetFunction() == symbol_context.function) {
+            return owning_function->CreateNestedInlinedBlockCalls(
+                *inlined_block, insn);
+          }
+          // Now we need to handle this as a return, because there aren't
+          // calls into an inline function
+          return AppendReturnedInstruction(insn, symbol_context, address,
+                                           target, active_call_wrapper);
+        }
+
+        // If the last instruction was a call, we for sure need to push the new
+        // instruction to the stack
+        if (IsControlFlowKindAStrictCall(active_insn_control_flow_kind)) {
+          return active_call.SetLastSegmentChildCall(
+              CreateTraceCallForInstruction(insn, target, address,
+                                            symbol_context));
+        }
+
+        // We now check if we are at the beginning of a symbol or function,
+        // which would mean that we are in a new call. This helps handle some
+        // tail recursions and abnormal calls (like the ld linker calling the
+        // sought symbol using RET or instructions other than CALL).
+        AddressRange symbol_or_function_range;
+        symbol_context.GetAddressRange(
+            eSymbolContextFunction | eSymbolContextFunction, 0,
+            /*inlined_block_range*/ false, symbol_or_function_range);
+        if ((symbol_context.function || symbol_context.symbol) &&
+            symbol_or_function_range.GetBaseAddress() == address) {
+          return active_call.SetLastSegmentChildCall(
+              CreateTraceCallForInstruction(insn, target, address,
+                                            symbol_context));
+        }
+
+        switch (active_insn_control_flow_kind) {
+        case lldb::eInstructionControlFlowKindCall:
+        case lldb::eInstructionControlFlowKindFarCall:
+          llvm_unreachable("must have been handled before");
+        case lldb::eInstructionControlFlowKindFarReturn:
+        case lldb::eInstructionControlFlowKindReturn:
+          // If the last instruction was a return, we need to go back in the
+          // stack. Abnormal cases like the dynamic linker invoking a function
+          // using a RET should have already been handled above.
+          return AppendReturnedInstruction(insn, symbol_context, address,
+                                           target, active_call_wrapper);
+        case lldb::eInstructionControlFlowKindUnknown:
+        case lldb::eInstructionControlFlowKindOther:
+        case lldb::eInstructionControlFlowKindJump:
+        case lldb::eInstructionControlFlowKindCondJump:
+        case lldb::eInstructionControlFlowKindFarJump:
+        case lldb::eInstructionControlFlowKindIndirect:
+          // At this point our instruction is not an inline one
+
+          // The following code will try to append the current instruction to
+          // the previous segment.
+          if (IsSameNonInlineSymbolContext(active_call_wrapper, symbol_context,
+                                           address)) {
+            active_call.AppendInstruction(insn);
+            return active_call;
+          }
+
+          // We changed symbols not using a call or return and we are not in the
+          // beginning of a symbol, so this should be something very artificial
+          // or maybe a jump to some label in the middle of it section.
+
+          // We first check if we just finished an inline function, which means
+          // we are returning
+          if constexpr (std::is_same_v<T, TraceCallInlinedFunction>) {
+            return AppendReturnedInstruction(insn, symbol_context, address,
+                                             target, active_call_wrapper);
+          }
+
+          // Now we assume it's a call. We should revisit this in the future.
+          // Ideally we should be able to decide whether to create a new tree,
+          // or go deeper or higher in the stack.
+          return active_call.SetLastSegmentChildCall(
+              CreateTraceCallForInstruction(insn, target, address,
+                                            symbol_context));
+        };
+      },
+      active_call_wrapper);
+}
+
+void TraceErrorSegment::AppendError(const TraceCursor &error) {
+  m_ids_range.second = error.GetId();
+  m_error_count++;
+}
+
+TraceErrorSegment::TraceErrorSegment(const TraceCursor &error)
+    : m_ids_range(error.GetId(), error.GetId()) {
+  m_error_count++;
+}
+
+uint64_t TraceErrorSegment::GetErrorCount() const { return m_error_count; }
+
+std::pair<lldb::user_id_t, lldb::user_id_t>
+TraceErrorSegment::GetRange() const {
+  return m_ids_range;
+}
+
+TraceCallTree *TraceCallGraph::GetActiveTree() { return m_active_tree; }
+
+void TraceCallGraph::CloseActiveTree() { m_active_tree = nullptr; }
+
+void TraceCallGraph::CreateErrorSegment(const TraceCursor &error) {
+  m_trees.push_back(std::make_unique<TraceCallTree>(
+      std::in_place_type<TraceErrorSegment>, error));
+  m_active_tree = m_trees.back().get();
+}
+void TraceCallGraph::CreateInstructionCallTree(const TraceCursor &insn,
+                                               Target &target) {
+  m_trees.push_back(std::make_unique<TraceCallTree>(
+      std::in_place_type<TraceInstructionCallTree>, insn, target));
+  m_active_tree = m_trees.back().get();
+}
+
+void TraceCallGraph::AppendErrorItemToGraph(const TraceCursor &error) {
+  if (TraceErrorSegment *error_segment =
+          std::get_if<TraceErrorSegment>(GetActiveTree())) {
+    error_segment->AppendError(error);
+  } else {
+    CreateErrorSegment(error);
+  }
+}
+
+void TraceCallGraph::AppendInstructionItemToGraph(const TraceCursor &insn,
+                                                  Target &target) {
+  if (TraceInstructionCallTree *tree =
+          std::get_if<TraceInstructionCallTree>(GetActiveTree())) {
+    tree->AppendInstruction(insn, target);
+  } else {
+    CreateInstructionCallTree(insn, target);
+  }
+}
+
+TraceCallGraphSP TraceCallGraph::Build(TraceCursor &cursor,
+                                       Optional<lldb::user_id_t> from_id,
+                                       Optional<lldb::user_id_t> to_id) {
+  TraceCallGraphSP graph_sp(new TraceCallGraph());
+  TargetSP target_sp(cursor.GetExecutionContextRef().GetTargetSP());
+
+  cursor.SetForwards(true);
+  if (from_id)
+    cursor.GoToId(*from_id);
+  else
+    cursor.Seek(0, eTraceCursorSeekTypeBeginning);
+
+  for (; cursor.HasValue(); cursor.Next()) {
+    switch (cursor.GetItemKind()) {
+    case eTraceItemKindEvent:
+      if (cursor.GetEventType() == lldb::eTraceEventCPUChanged) {
+        // TODO: we havent explored yet how to merge subtraces from different
+        // CPUs. For now we are creating a new tree for each CPU.
+        graph_sp->CloseActiveTree();
+      }
+      break;
+    case eTraceItemKindError:
+      graph_sp->AppendErrorItemToGraph(cursor);
+      break;
+    case lldb::eTraceItemKindInstruction:
+      graph_sp->AppendInstructionItemToGraph(cursor, *target_sp);
+      break;
+    }
+
+    if (to_id && *to_id == cursor.GetId())
+      break;
+  }
+
+  return graph_sp;
+}

lldb/source/Target/TraceCursor.cpp

 //===-- TraceCursor.cpp -----------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "lldb/Target/TraceCursor.h"
-
 #include "lldb/Target/ExecutionContext.h"
+#include "lldb/Target/Target.h"
 #include "lldb/Target/Trace.h"
 
 using namespace lldb;
 using namespace lldb_private;
 using namespace llvm;
 
 TraceCursor::TraceCursor(lldb::ThreadSP thread_sp)
     : m_exe_ctx_ref(ExecutionContext(thread_sp)) {}
case lldb::eTraceEventCPUChanged:
     return "CPU core changed";
   case lldb::eTraceEventHWClockTick:
     return "HW clock tick";
   case lldb::eTraceEventSyncPoint:
     return "trace synchronization point";
   }
   llvm_unreachable("Fully covered switch above");
 }
+
+InstructionControlFlowKind TraceCursor::GetInstructionControlFlowKind() const {
+  TargetSP target_sp = m_exe_ctx_ref.GetTargetSP();
+  const ArchSpec arch = target_sp->GetArchitecture();
+  Address address;
+  if (!target_sp->ResolveLoadAddress(GetLoadAddress(), address))
+    return eInstructionControlFlowKindUnknown;
+  AddressRange range(address, arch.GetMaximumOpcodeByteSize());
+  DisassemblerSP disassembler =
+      Disassembler::DisassembleRange(arch, /*plugin_name*/ nullptr,
+                                     /*flavor*/ nullptr, *target_sp, range);
+
+  ExecutionContext exe_ctx;
+  target_sp->CalculateExecutionContext(exe_ctx);
+  if (InstructionSP insn_sp =
+          disassembler->GetInstructionList().GetInstructionAtAddress(address))
+    return insn_sp->GetControlFlowKind(&exe_ctx);
+  return eInstructionControlFlowKindUnknown;
+}

lldb/source/Target/TraceDumper.cpp

IsSameInstructionSymbolContext(const TraceDumper::SymbolInfo &prev_insn,
 
   // function checks
   if (!insn.sc.function && !prev_insn.sc.function)
     return true; // This means two dangling instruction in the same module. We
                  // can assume they are part of the same unnamed symbol
   else if (insn.sc.function != prev_insn.sc.function)
     return false;
 
-  Block *inline_block_a =
+  Block *inlined_block_a =
       insn.sc.block ? insn.sc.block->GetContainingInlinedBlock() : nullptr;
-  Block *inline_block_b = prev_insn.sc.block
+  Block *inlined_block_b = prev_insn.sc.block
                                ? prev_insn.sc.block->GetContainingInlinedBlock()
                                : nullptr;
-  if (inline_block_a != inline_block_b)
+  if (inlined_block_a != inlined_block_b)
     return false;
 
   // line entry checks
   if (!check_source_line_info)
     return true;
 
   const bool curr_line_valid = IsLineEntryValid(insn.sc.line_entry);
   const bool prev_line_valid = IsLineEntryValid(prev_insn.sc.line_entry);
   if (curr_line_valid && prev_line_valid)
     return FileLineAndColumnMatches(insn.sc.line_entry,
                                     prev_insn.sc.line_entry);
   return curr_line_valid == prev_line_valid;
 }
 
 class OutputWriterCLI : public TraceDumper::OutputWriter {
 public:
   OutputWriterCLI(Stream &s, const TraceDumperOptions &options, Thread &thread)
       : m_s(s), m_options(options) {
     m_s.Format("thread #{0}: tid = {1}\n", thread.GetIndexID(), thread.GetID());
   };
 
   void NoMoreData() override { m_s << "    no more data\n"; }
 
-  void FunctionCallForest(
-      const std::vector<TraceDumper::FunctionCallUP> &forest) override {
-    for (size_t i = 0; i < forest.size(); i++) {
-      m_s.Format("\n[call tree #{0}]\n", i);
-      DumpFunctionCallTree(*forest[i]);
-    }
-  }
-
   void TraceItem(const TraceDumper::TraceItem &item) override {
     if (item.symbol_info) {
       if (!item.prev_symbol_info ||
           !IsSameInstructionSymbolContext(*item.prev_symbol_info,
                                           *item.symbol_info)) {
         m_s << "  ";
         const char *module_name = GetModuleName(item);
         if (!module_name)
if (item.event) {
       }
     }
 
     m_was_prev_instruction_an_error = (bool)item.error;
     m_s << "\n";
   }
 
 private:
-  void
-  DumpSegmentContext(const TraceDumper::FunctionCall::TracedSegment &segment) {
-    if (segment.GetOwningCall().IsError()) {
-      m_s << "<tracing errors>";
-      return;
-    }
-
-    const SymbolContext &first_sc = segment.GetFirstInstructionSymbolInfo().sc;
-    first_sc.DumpStopContext(
-        &m_s, segment.GetFirstInstructionSymbolInfo().exe_ctx.GetTargetPtr(),
-        segment.GetFirstInstructionSymbolInfo().address,
-        /*show_fullpaths=*/false,
-        /*show_module=*/true, /*show_inlined_frames=*/false,
-        /*show_function_arguments=*/true,
-        /*show_function_name=*/true);
-    m_s << " to ";
-    const SymbolContext &last_sc = segment.GetLastInstructionSymbolInfo().sc;
-    if (IsLineEntryValid(first_sc.line_entry) &&
-        IsLineEntryValid(last_sc.line_entry)) {
-      m_s.Format("{0}:{1}", last_sc.line_entry.line, last_sc.line_entry.column);
-    } else {
-      last_sc.DumpStopContext(
-          &m_s, segment.GetFirstInstructionSymbolInfo().exe_ctx.GetTargetPtr(),
-          segment.GetLastInstructionSymbolInfo().address,
-          /*show_fullpaths=*/false,
-          /*show_module=*/false, /*show_inlined_frames=*/false,
-          /*show_function_arguments=*/false,
-          /*show_function_name=*/false);
-    }
-  }
-
-  void DumpUntracedContext(const TraceDumper::FunctionCall &function_call) {
-    if (function_call.IsError()) {
-      m_s << "tracing error";
-    }
-    const SymbolContext &sc = function_call.GetSymbolInfo().sc;
-
-    const char *module_name = GetModuleName(sc);
-    if (!module_name)
-      m_s << "(none)";
-    else if (!sc.function && !sc.symbol)
-      m_s << module_name << "`(none)";
-    else
-      m_s << module_name << "`" << sc.GetFunctionName().AsCString();
-  }
-
-  void DumpFunctionCallTree(const TraceDumper::FunctionCall &function_call) {
-    if (function_call.GetUntracedPrefixSegment()) {
-      m_s.Indent();
-      DumpUntracedContext(function_call);
-      m_s << "\n";
-
-      m_s.IndentMore();
-      DumpFunctionCallTree(function_call.GetUntracedPrefixSegment()->GetNestedCall());
-      m_s.IndentLess();
-    }
-
-    for (const TraceDumper::FunctionCall::TracedSegment &segment :
-         function_call.GetTracedSegments()) {
-      m_s.Indent();
-      DumpSegmentContext(segment);
-      m_s.Format("  [{0}, {1}]\n", segment.GetFirstInstructionID(),
-                 segment.GetLastInstructionID());
-
-      segment.IfNestedCall([&](const TraceDumper::FunctionCall &nested_call) {
-        m_s.IndentMore();
-        DumpFunctionCallTree(nested_call);
-        m_s.IndentLess();
-      });
-    }
-  }
-
   Stream &m_s;
   TraceDumperOptions m_options;
   bool m_was_prev_instruction_an_error = false;
 };
 
 class OutputWriterJSON : public TraceDumper::OutputWriter {
   /* schema:
     error_message: string
OutputWriterJSON(Stream &s, const TraceDumperOptions &options)
       : m_s(s), m_options(options),
         m_j(m_s.AsRawOstream(),
             /*IndentSize=*/options.pretty_print_json ? 2 : 0) {
     m_j.arrayBegin();
   };
 
   ~OutputWriterJSON() { m_j.arrayEnd(); }
 
-  void FunctionCallForest(
-      const std::vector<TraceDumper::FunctionCallUP> &forest) override {
-    for (size_t i = 0; i < forest.size(); i++) {
-      m_j.object([&] { DumpFunctionCallTree(*forest[i]); });
-    }
-  }
-
-  void DumpFunctionCallTree(const TraceDumper::FunctionCall &function_call) {
-    if (function_call.GetUntracedPrefixSegment()) {
-      m_j.attributeObject("untracedPrefixSegment", [&] {
-        m_j.attributeObject("nestedCall", [&] {
-          DumpFunctionCallTree(
-              function_call.GetUntracedPrefixSegment()->GetNestedCall());
-        });
-      });
-    }
-
-    if (!function_call.GetTracedSegments().empty()) {
-      m_j.attributeArray("tracedSegments", [&] {
-        for (const TraceDumper::FunctionCall::TracedSegment &segment :
-             function_call.GetTracedSegments()) {
-          m_j.object([&] {
-            m_j.attribute("firstInstructionId",
-                          std::to_string(segment.GetFirstInstructionID()));
-            m_j.attribute("lastInstructionId",
-                          std::to_string(segment.GetLastInstructionID()));
-            segment.IfNestedCall(
-                [&](const TraceDumper::FunctionCall &nested_call) {
-                  m_j.attributeObject(
-                      "nestedCall", [&] { DumpFunctionCallTree(nested_call); });
-                });
-          });
-        }
-      });
-    }
-  }
-
   void DumpEvent(const TraceDumper::TraceItem &item) {
     m_j.attribute("event", TraceCursor::EventKindToString(*item.event));
     switch (*item.event) {
     case eTraceEventCPUChanged:
       m_j.attribute("cpuId", item.cpu_id);
       break;
     case eTraceEventHWClockTick:
       m_j.attribute("hwClock", item.hw_clock);

 
 /// Find the symbol context for the given address reusing the previous
 /// instruction's symbol context when possible.
 static SymbolContext
 CalculateSymbolContext(const Address &address,
                        const SymbolContext &prev_symbol_context) {
   AddressRange range;
   if (prev_symbol_context.GetAddressRange(eSymbolContextEverything, 0,
-                                          /*inline_block_range*/ true, range) &&
+                                          /*inlined_block_range*/ true,
+                                          range) &&
       range.Contains(address))
     return prev_symbol_context;
 
   SymbolContext sc;
   address.CalculateSymbolContext(&sc, eSymbolContextEverything);
   return sc;
 }
 
if (m_cursor_sp->IsEvent() && m_options.show_events) {
       m_writer_up->TraceItem(item);
     }
   }
   if (!m_cursor_sp->HasValue())
     m_writer_up->NoMoreData();
   return last_id;
 }
 
-void TraceDumper::FunctionCall::TracedSegment::AppendInsn(
-    const TraceCursorSP &cursor_sp,
-    const TraceDumper::SymbolInfo &symbol_info) {
-  m_last_insn_id = cursor_sp->GetId();
-  m_last_symbol_info = symbol_info;
-}
-
-lldb::user_id_t
-TraceDumper::FunctionCall::TracedSegment::GetFirstInstructionID() const {
-  return m_first_insn_id;
-}
-
-lldb::user_id_t
-TraceDumper::FunctionCall::TracedSegment::GetLastInstructionID() const {
-  return m_last_insn_id;
-}
-
-void TraceDumper::FunctionCall::TracedSegment::IfNestedCall(
-    std::function<void(const FunctionCall &function_call)> callback) const {
-  if (m_nested_call)
-    callback(*m_nested_call);
-}
-
-const TraceDumper::FunctionCall &
-TraceDumper::FunctionCall::TracedSegment::GetOwningCall() const {
-  return m_owning_call;
-}
-
-TraceDumper::FunctionCall &
-TraceDumper::FunctionCall::TracedSegment::CreateNestedCall(
-    const TraceCursorSP &cursor_sp,
-    const TraceDumper::SymbolInfo &symbol_info) {
-  m_nested_call = std::make_unique<FunctionCall>(cursor_sp, symbol_info);
-  m_nested_call->SetParentCall(m_owning_call);
-  return *m_nested_call;
+TraceCallGraphDumper::TraceCallGraphDumper(
+    const TraceCursorSP &cursor_sp, const TraceCallGraphSP &call_graph_sp,
+    Stream &s)
+    : m_cursor_sp(cursor_sp), m_graph_sp(call_graph_sp), m_s(s),
+      m_exe_ctx(cursor_sp->GetExecutionContextRef()) {}
+
+// Overload pattern-based syntax sugar for easier variant matching.
+template <typename... Ts> struct match : Ts... { using Ts::operator()...; };
+template <class... Ts> match(Ts...) -> match<Ts...>;
+
+/// Utility for indenting and writing to a stream in one line.
+static Stream &WithIndent(Stream &s) {
+  s.Indent();
+  return s;
 }
 
-const TraceDumper::SymbolInfo &
-TraceDumper::FunctionCall::TracedSegment::GetFirstInstructionSymbolInfo()
-    const {
-  return m_first_symbol_info;
-}
+/// RAII-based utility for handling indentation and de-indentation of a stream.
+struct AddIndent {
+  AddIndent(Stream &s) : m_s(s) { m_s.IndentMore(); }
+  ~AddIndent() { m_s.IndentLess(); }
 
-const TraceDumper::SymbolInfo &
-TraceDumper::FunctionCall::TracedSegment::GetLastInstructionSymbolInfo() const {
-  return m_last_symbol_info;
-}
-
-const TraceDumper::FunctionCall &
-TraceDumper::FunctionCall::UntracedPrefixSegment::GetNestedCall() const {
-  return *m_nested_call;
-}
+private:
+  Stream &m_s;
+};
 
-TraceDumper::FunctionCall::FunctionCall(
-    const TraceCursorSP &cursor_sp,
-    const TraceDumper::SymbolInfo &symbol_info) {
-  m_is_error = cursor_sp->IsError();
-  AppendSegment(cursor_sp, symbol_info);
-}
+void TraceCallGraphDumper::Dump() {
+  Thread &thread = m_exe_ctx.GetThreadRef();
+  m_s.Format("thread #{0}: tid = {1}\n", thread.GetIndexID(), thread.GetID());
 
-void TraceDumper::FunctionCall::AppendSegment(
-    const TraceCursorSP &cursor_sp,
-    const TraceDumper::SymbolInfo &symbol_info) {
-  m_traced_segments.emplace_back(cursor_sp, symbol_info, *this);
+  llvm::ArrayRef<TraceCallTreeUP> trees = m_graph_sp->GetTrees();
+  AddIndent _(m_s);
+  for (size_t i = 0; i < trees.size(); i++) {
+    m_s << "\n";
+    std::visit(
+        match{[&](TraceErrorSegment &errors) {
+                WithIndent(m_s).Format("<subtrace #{0}: tracing errors>\n", i);
+                DumpErrorSegment(errors);
+              },
+              [&](TraceInstructionCallTree &tree) {
+                WithIndent(m_s).Format("<subtrace #{0}: instructions>\n", i);
+                DumpCall(tree.GetRootCall());
+              }},
+        *trees[i]);
   }
-
-const TraceDumper::SymbolInfo &
-TraceDumper::FunctionCall::GetSymbolInfo() const {
-  return m_traced_segments.back().GetLastInstructionSymbolInfo();
 }
 
-bool TraceDumper::FunctionCall::IsError() const { return m_is_error; }
-
-const std::deque<TraceDumper::FunctionCall::TracedSegment> &
-TraceDumper::FunctionCall::GetTracedSegments() const {
-  return m_traced_segments;
-}
+void TraceCallGraphDumper::DumpErrorSegment(TraceErrorSegment &error_segment) {
+  AddIndent _(m_s);
+
+  auto print_error = [&](lldb::user_id_t error_id) {
+    m_cursor_sp->GoToId(error_id);
+    WithIndent(m_s).Format("|{0}: {1}\n", error_id, m_cursor_sp->GetError());
+  };
 
-TraceDumper::FunctionCall::TracedSegment &
-TraceDumper::FunctionCall::GetLastTracedSegment() {
-  return m_traced_segments.back();
+  auto [from, to] = error_segment.GetRange();
+  print_error(from);
+  if (from != to) {
+    uint64_t remaining = error_segment.GetErrorCount() - 2;
+    if (remaining >= 2) {
+      WithIndent(m_s).Format("| ... {0} error{1}\n", remaining,
+                             remaining == 1 ? "" : "s");
     }
-
-const Optional<TraceDumper::FunctionCall::UntracedPrefixSegment> &
-TraceDumper::FunctionCall::GetUntracedPrefixSegment() const {
-  return m_untraced_prefix_segment;
+    print_error(to);
   }
-
-void TraceDumper::FunctionCall::SetUntracedPrefixSegment(
-    TraceDumper::FunctionCallUP &&nested_call) {
-  m_untraced_prefix_segment.emplace(std::move(nested_call));
 }
 
-TraceDumper::FunctionCall *TraceDumper::FunctionCall::GetParentCall() const {
-  return m_parent_call;
+static const char *ToDisplayString(const ModuleSP &module_sp) {
+  if (const char *str = module_sp->GetFileSpec().GetFilename().AsCString())
+    return str;
+  return "(none)";
 }
 
-void TraceDumper::FunctionCall::SetParentCall(
-    TraceDumper::FunctionCall &parent_call) {
-  m_parent_call = &parent_call;
-}
+void TraceCallGraphDumper::DumpCallWrapper(
+    std::function<void()> call_description_dumper,
+    std::function<void(const TraceCursor &cursor)> insn_description_dumper,
+    TraceCall &call_wrapper) {
 
-/// Given an instruction that happens after a return, find the ancestor function
-/// call that owns it. If this ancestor doesn't exist, create a new ancestor and
-/// make it the root of the tree.
-///
-/// \param[in] last_function_call
-///   The function call that performs the return.
-///
-/// \param[in] symbol_info
-///   The symbol information of the instruction after the return.
-///
-/// \param[in] cursor_sp
-///   The cursor pointing to the instruction after the return.
-///
-/// \param[in,out] roots
-///   The object owning the roots. It might be modified if a new root needs to
-///   be created.
-///
-/// \return
-///   A reference to the function call that owns the new instruction
-static TraceDumper::FunctionCall &AppendReturnedInstructionToFunctionCallForest(
-    TraceDumper::FunctionCall &last_function_call,
-    const TraceDumper::SymbolInfo &symbol_info, const TraceCursorSP &cursor_sp,
-    std::vector<TraceDumper::FunctionCallUP> &roots) {
-
-  // We omit the current node because we can't return to itself.
-  TraceDumper::FunctionCall *ancestor = last_function_call.GetParentCall();
-
-  for (; ancestor; ancestor = ancestor->GetParentCall()) {
-    // This loop traverses the tree until it finds a call that we can return to.
-    if (IsSameInstructionSymbolContext(ancestor->GetSymbolInfo(), symbol_info,
-                                       /*check_source_line_info=*/false)) {
-      // We returned to this symbol, so we are assuming we are returning there
-      // Note: If this is not robust enough, we should actually check if we
-      // returning to the instruction that follows the last instruction from
-      // that call, as that's the behavior of CALL instructions.
-      ancestor->AppendSegment(cursor_sp, symbol_info);
-      return *ancestor;
-    }
-  }
+  WithIndent(m_s) << "-> ";
+  call_description_dumper();
+  m_s << "\n";
 
-  // We didn't find the call we were looking for, so we now create a synthetic
-  // one that will contain the new instruction in its first traced segment.
-  TraceDumper::FunctionCallUP new_root =
-      std::make_unique<TraceDumper::FunctionCall>(cursor_sp, symbol_info);
-  // This new root will own the previous root through an untraced prefix segment.
-  new_root->SetUntracedPrefixSegment(std::move(roots.back()));
-  roots.pop_back();
-  // We update the roots container to point to the new root
-  roots.emplace_back(std::move(new_root));
-  return *roots.back();
-}
-
-/// Append an instruction to a function call forest. The new instruction might
-/// be appended to the current segment, to a new nest call, or return to an
-/// ancestor call.
-///
-/// \param[in] exe_ctx
-///   The exeuction context of the traced thread.
-///
-/// \param[in] last_function_call
-///   The chronologically most recent function call before the new instruction.
-///
-/// \param[in] prev_symbol_info
-///   The symbol information of the previous instruction in the trace.
-///
-/// \param[in] symbol_info
-///   The symbol information of the new instruction.
-///
-/// \param[in] cursor_sp
-///   The cursor pointing to the new instruction.
-///
-/// \param[in,out] roots
-///   The object owning the roots. It might be modified if a new root needs to
-///   be created.
-///
-/// \return
-///   A reference to the function call that owns the new instruction.
-static TraceDumper::FunctionCall &AppendInstructionToFunctionCallForest(
-    const ExecutionContext &exe_ctx,
-    TraceDumper::FunctionCall *last_function_call,
-    const TraceDumper::SymbolInfo &prev_symbol_info,
-    const TraceDumper::SymbolInfo &symbol_info, const TraceCursorSP &cursor_sp,
-    std::vector<TraceDumper::FunctionCallUP> &roots) {
-  if (!last_function_call || last_function_call->IsError()) {
-    // We create a brand new root
-    roots.emplace_back(
-        std::make_unique<TraceDumper::FunctionCall>(cursor_sp, symbol_info));
-    return *roots.back();
-  }
+  auto dump_insn = [&](lldb::user_id_t id) {
+    m_cursor_sp->GoToId(id);
+    WithIndent(m_s).Format(" |{0}: {1:x+16}", id,
+                           m_cursor_sp->GetLoadAddress());
+    insn_description_dumper(*m_cursor_sp);
+    m_s << "\n";
+  };
 
+  std::visit(
+      [&](auto &&call) {
+        for (const TraceCallSegmentUP &segment_up : call.GetSegments()) {
+          AddIndent _(m_s);
+          if (auto range = segment_up->GetRange()) {
+            auto [from, to] = *range;
+            dump_insn(from);
+            if (from != to) {
+              uint64_t mid_instructions =
+                  segment_up->GetExclusiveInsnCount() - 2;
+              if (mid_instructions >= 1) {
+                WithIndent(m_s).Format(" |... {0} instruction{1}\n",
+                                       mid_instructions,
+                                       mid_instructions == 1 ? "" : "s");
+              }
+              dump_insn(to);
+            }
+          }
+          if (TraceCall *child_call = segment_up->GetChildCall()) {
+            DumpCall(*child_call);
+          }
+        }
+      },
+      call_wrapper);
+}
+
+void TraceCallGraphDumper::DumpSectionCall(TraceCallSection &call) {
+  Target &target = m_exe_ctx.GetTargetRef();
+  lldb::addr_t inlined_function_base_address =
+      call.GetSection()->GetLoadBaseAddress(&target);
+
+  DumpCallWrapper([&] { call.GetSection()->DumpName(m_s.AsRawOstream()); },
+                  [&](const TraceCursor &insn) {
+                    if (inlined_function_base_address != LLDB_INVALID_ADDRESS)
+                      m_s.Format(" <+{0}>", insn.GetLoadAddress() -
+                                                inlined_function_base_address);
+                  },
+                  call.GetWrappingCall());
+}
+
+void TraceCallGraphDumper::DumpInlinedFunctionCall(
+    TraceCallInlinedFunction &call) {
+  Block &inlined_block = call.GetInlinedBlock();
+  Target &target = m_exe_ctx.GetTargetRef();
+
+  lldb::addr_t inlined_function_base_address = LLDB_INVALID_ADDRESS;
+  if (AddressRange range; inlined_block.GetRangeAtIndex(0, range))
+    inlined_function_base_address =
+        range.GetBaseAddress().GetLoadAddress(&target);
+
+  DumpCallWrapper(
+      [&] {
+        m_s.Format("[inlined] {0}`{1}",
+                   ToDisplayString(call.GetOwningFunctionCall()
+                                       .GetFunction()
+                                       .CalculateSymbolContextModule()),
+                   inlined_block.GetInlinedFunctionInfo()->GetName());
+      },
+      [&](const TraceCursor &insn) {
+        lldb::addr_t load_address = insn.GetLoadAddress();
         AddressRange range;
-  if (symbol_info.sc.GetAddressRange(
-          eSymbolContextBlock | eSymbolContextFunction | eSymbolContextSymbol,
-          0, /*inline_block_range*/ true, range)) {
-    if (range.GetBaseAddress() == symbol_info.address) {
-      // Our instruction is the first instruction of a function. This has
-      // to be a call. This should also identify if a trampoline or the linker
-      // is making a call using a non-CALL instruction.
-      return last_function_call->GetLastTracedSegment().CreateNestedCall(
-          cursor_sp, symbol_info);
-    }
-  }
-  if (IsSameInstructionSymbolContext(prev_symbol_info, symbol_info,
-                                     /*check_source_line_info=*/false)) {
-    // We are still in the same function. This can't be a call because otherwise
-    // we would be in the first instruction of the symbol.
-    last_function_call->GetLastTracedSegment().AppendInsn(cursor_sp,
-                                                          symbol_info);
-    return *last_function_call;
-  }
-  // Now we are in a different symbol. Let's see if this is a return or a
-  // call
-  const InstructionSP &insn = last_function_call->GetLastTracedSegment()
-                                  .GetLastInstructionSymbolInfo()
-                                  .instruction;
-  InstructionControlFlowKind insn_kind =
-      insn ? insn->GetControlFlowKind(&exe_ctx)
-           : eInstructionControlFlowKindOther;
-
-  switch (insn_kind) {
-  case lldb::eInstructionControlFlowKindCall:
-  case lldb::eInstructionControlFlowKindFarCall: {
-    // This is a regular call
-    return last_function_call->GetLastTracedSegment().CreateNestedCall(
-        cursor_sp, symbol_info);
-  }
-  case lldb::eInstructionControlFlowKindFarReturn:
-  case lldb::eInstructionControlFlowKindReturn: {
-    // We should have caught most trampolines and linker functions earlier, so
-    // let's assume this is a regular return.
-    return AppendReturnedInstructionToFunctionCallForest(
-        *last_function_call, symbol_info, cursor_sp, roots);
-  }
-  default:
-    // we changed symbols not using a call or return and we are not in the
-    // beginning of a symbol, so this should be something very artificial
-    // or maybe a jump to some label in the middle of it section.
-
-    // We first check if it's a return from an inline method
-    if (prev_symbol_info.sc.block &&
-        prev_symbol_info.sc.block->GetContainingInlinedBlock()) {
-      return AppendReturnedInstructionToFunctionCallForest(
-          *last_function_call, symbol_info, cursor_sp, roots);
-    }
-    // Now We assume it's a call. We should revisit this in the future.
-    // Ideally we should be able to decide whether to create a new tree,
-    // or go deeper or higher in the stack.
-    return last_function_call->GetLastTracedSegment().CreateNestedCall(
-        cursor_sp, symbol_info);
-  }
-}
-
-/// Append an error to a function call forest. The new error might be appended
-/// to the current segment if it contains errors or will create a new root.
-///
-/// \param[in] last_function_call
-///   The chronologically most recent function call before the new error.
-///
-/// \param[in] cursor_sp
-///   The cursor pointing to the new error.
-///
-/// \param[in,out] roots
-///   The object owning the roots. It might be modified if a new root needs to
-///   be created.
-///
-/// \return
-///   A reference to the function call that owns the new error.
-TraceDumper::FunctionCall &AppendErrorToFunctionCallForest(
-    TraceDumper::FunctionCall *last_function_call, TraceCursorSP &cursor_sp,
-    std::vector<TraceDumper::FunctionCallUP> &roots) {
-  if (last_function_call && last_function_call->IsError()) {
-    last_function_call->GetLastTracedSegment().AppendInsn(
-        cursor_sp, TraceDumper::SymbolInfo{});
-    return *last_function_call;
-  } else {
-    roots.emplace_back(std::make_unique<TraceDumper::FunctionCall>(
-        cursor_sp, TraceDumper::SymbolInfo{}));
-    return *roots.back();
-  }
-}
-
-static std::vector<TraceDumper::FunctionCallUP>
-CreateFunctionCallForest(TraceCursorSP &cursor_sp,
-                         const ExecutionContext &exe_ctx) {
-
-  std::vector<TraceDumper::FunctionCallUP> roots;
-  TraceDumper::SymbolInfo prev_symbol_info;
-
-  TraceDumper::FunctionCall *last_function_call = nullptr;
-
-  for (; cursor_sp->HasValue(); cursor_sp->Next()) {
-    if (cursor_sp->IsError()) {
-      last_function_call = &AppendErrorToFunctionCallForest(last_function_call,
-                                                            cursor_sp, roots);
-      prev_symbol_info = {};
-    } else if (cursor_sp->IsInstruction()) {
-      TraceDumper::SymbolInfo symbol_info = CalculateSymbolInfo(
-          exe_ctx, cursor_sp->GetLoadAddress(), prev_symbol_info);
-
-      last_function_call = &AppendInstructionToFunctionCallForest(
-          exe_ctx, last_function_call, prev_symbol_info, symbol_info, cursor_sp,
-          roots);
-      prev_symbol_info = symbol_info;
-    } else if (cursor_sp->GetEventType() == eTraceEventCPUChanged) {
-      // TODO: In case of a CPU change, we create a new root because we haven't
-      // investigated yet if a call tree can safely continue or if interrupts
-      // could have polluted the original call tree.
-      last_function_call = nullptr;
-      prev_symbol_info = {};
-    }
-  }
-
-  return roots;
-}
-
-void TraceDumper::DumpFunctionCalls() {
-  ThreadSP thread_sp = m_cursor_sp->GetExecutionContextRef().GetThreadSP();
-  ExecutionContext exe_ctx;
-  thread_sp->GetProcess()->GetTarget().CalculateExecutionContext(exe_ctx);
+        if (inlined_function_base_address != LLDB_INVALID_ADDRESS)
+          m_s.Format(" <+{0}>", load_address - inlined_function_base_address);
 
-  m_writer_up->FunctionCallForest(
-      CreateFunctionCallForest(m_cursor_sp, exe_ctx));
+        Address addr;
+        if (target.ResolveLoadAddress(load_address, addr)) {
+          LineEntry line_entry;
+          addr.CalculateSymbolContextLineEntry(line_entry);
+
+          if (line_entry.IsValid()) {
+            m_s << " at ";
+            line_entry.DumpStopContext(&m_s, /*show_fullpaths*/ false);
+          }
+        }
+      },
+      call.GetWrappingCall());
+}
+
+void TraceCallGraphDumper::DumpFunctionCall(TraceCallFunction &call) {
+  Function &function = call.GetFunction();
+  Target &target = m_exe_ctx.GetTargetRef();
+  lldb::addr_t function_base_address =
+      function.GetAddressRange().GetBaseAddress().GetLoadAddress(&target);
+
+  DumpCallWrapper(
+      [&] {
+        m_s.Format("{0}`{1}",
+                   ToDisplayString(function.CalculateSymbolContextModule()),
+                   function.GetName());
+      },
+      [&](const TraceCursor &insn) {
+        lldb::addr_t load_address = insn.GetLoadAddress();
+        if (function_base_address != LLDB_INVALID_ADDRESS)
+          m_s.Format(" <+{0}>", load_address - function_base_address);
+
+        Address addr;
+        if (target.ResolveLoadAddress(load_address, addr)) {
+          LineEntry line_entry;
+          addr.CalculateSymbolContextLineEntry(line_entry);
+          if (line_entry.IsValid()) {
+            m_s << " at ";
+            line_entry.DumpStopContext(&m_s, /*show_fullpaths*/ false);
+          }
+        }
+      },
+      call.GetWrappingCall());
+}
+
+void TraceCallGraphDumper::DumpSymbolCall(TraceCallSymbol &call) {
+  Symbol &symbol = call.GetSymbol();
+  Target &target = m_exe_ctx.GetTargetRef();
+
+  DumpCallWrapper(
+      [&] {
+        m_s.Format("{0}`{1}",
+                   ToDisplayString(symbol.CalculateSymbolContextModule()),
+                   symbol.GetName());
+      },
+      [&](const TraceCursor &insn) {
+        lldb::addr_t load_address = insn.GetLoadAddress();
+        lldb::addr_t symbol_offset =
+            load_address - symbol.GetLoadAddress(&target);
+        m_s.Format(" <+{0}>", symbol_offset);
+
+        Address addr;
+        if (target.ResolveLoadAddress(load_address, addr)) {
+          LineEntry line_entry;
+          addr.CalculateSymbolContextLineEntry(line_entry);
+          if (line_entry.IsValid()) {
+            m_s << " at ";
+            line_entry.DumpStopContext(&m_s, /*show_fullpaths*/ false);
+          }
+        }
+      },
+      call.GetWrappingCall());
+}
+
+void TraceCallGraphDumper::DumpUnknownRegion(TraceCallUnknownRegion &call) {
+  DumpCallWrapper([&] { m_s << "unknown region"; },
+                  [&](const TraceCursor &insn) {}, call.GetWrappingCall());
+}
+
+void TraceCallGraphDumper::DumpCall(TraceCall &call) {
+  AddIndent _(m_s);
+  std::visit(
+      match{[&](TraceCallInlinedFunction &call) {
+              DumpInlinedFunctionCall(call);
+            },
+            [&](TraceCallFunction &call) { DumpFunctionCall(call); },
+            [&](TraceCallSymbol &call) { DumpSymbolCall(call); },
+            [&](TraceCallSection &call) { DumpSectionCall(call); },
+            [&](TraceCallUnknownRegion &call) { DumpUnknownRegion(call); }},
+      call);
 }

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

def testDumpRawTraceSize(self):
             substrs=['''thread #1: tid = 3842849
 
   Trace technology: intel-pt
 
   Total number of trace items: 28
 
   Memory usage:
     Raw trace size: 4 KiB
-    Total approximate memory usage (excluding raw trace): 0.25 KiB
-    Average memory usage per item (excluding raw trace): 9.00 bytes
+    Total approximate memory usage (excluding raw trace): 0.30 KiB
+    Average memory usage per item (excluding raw trace): 11.00 bytes
 
   Timing for this thread:
     Decoding instructions: ''', '''
 
   Events:
     Number of individual events: 7
       software disabled tracing: 2
       hardware disabled tracing: 4
       trace synchronization point: 1'''],
             patterns=["Decoding instructions: \d.\d\ds"])
 
     def testDumpRawTraceSizeJSON(self):
         self.expect("trace load -v " +
         os.path.join(self.getSourceDir(), "intelpt-trace", "trace.json"),
         substrs=["intel-pt"])
 
         self.expect("thread trace dump info --json ",
             substrs=['''{
   "traceTechnology": "intel-pt",
   "threadStats": {
     "tid": 3842849,
     "traceItemsCount": 28,
     "memoryUsage": {
-      "totalInBytes": "252",
-      "avgPerItemInBytes": 9
+      "totalInBytes": "308",
+      "avgPerItemInBytes": 11
     },
     "timingInSeconds": {
       "Decoding instructions": 0''', '''
     },
     "events": {
       "totalCount": 7,
       "individualCounts": {
         "software disabled tracing": 2,

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

"totalContinuousExecutions": 153
 
         self.expect("thread trace dump info 2 --json",
           substrs=['''{
   "traceTechnology": "intel-pt",
   "threadStats": {
     "tid": 3497496,
     "traceItemsCount": 19533,
     "memoryUsage": {
-      "totalInBytes": "176065",
-      "avgPerItemInBytes": 9.''', '''},
+      "totalInBytes": "215131",
+      "avgPerItemInBytes": 11.''', '''},
     "timingInSeconds": {
       "Decoding instructions": ''', '''
     },
     "events": {
       "totalCount": 11,
       "individualCounts": {
         "software disabled tracing": 1,
         "trace synchronization point": 1,
def testLoadTrace(self):
         self.expect("thread trace dump info", substrs=['''thread #1: tid = 3842849
 
   Trace technology: intel-pt
 
   Total number of trace items: 28
 
   Memory usage:
     Raw trace size: 4 KiB
-    Total approximate memory usage (excluding raw trace): 0.25 KiB
-    Average memory usage per item (excluding raw trace): 9.00 bytes
+    Total approximate memory usage (excluding raw trace): 0.30 KiB
+    Average memory usage per item (excluding raw trace): 11.00 bytes
 
   Timing for this thread:
     Decoding instructions: ''', '''
 
   Events:
     Number of individual events: 7
       software disabled tracing: 2
       hardware disabled tracing: 4

lldb/test/API/commands/trace/function_calls/Makefile

+DYLIB_NAME := bar
+DYLIB_CXX_SOURCES := bar.cpp
+CXX_SOURCES := foo.cpp
+
+LD_EXTRAS := -Wl,-rpath "-Wl,$(shell pwd)"
+USE_LIBDL :=1
+
+include Makefile.rules
+
+all: a.out.stripped
+
+a.out.stripped:
+  strip -g -o a.out.stripped a.out

lldb/test/API/commands/trace/function_calls/TestTraceDumpFunctionCalls.py

+import lldb
+from intelpt_testcase import *
+from lldbsuite.test.lldbtest import *
+from lldbsuite.test.decorators import *
+
+class TestTraceDumpInfo(TraceIntelPTTestCaseBase):
+
+    def testDumpSingleItemSegments(self):
+      #We first try tracing single instructions of live processes
+
+      self.build()
+      program = self.getBuildArtifact("a.out.stripped")
+      self.expect("file " + program)
+      self.expect("b main")
+      self.expect("r")
+      self.expect("thread trace start")
+      self.expect("si")
+      self.expect("thread trace dump function-calls",
+        patterns=[f'''<subtrace #0: instructions>
+    -> a.out.stripped`main
+       |\d+ {ADDRESS_REGEX} <\+0>'''])
+
+      self.expect("thread trace stop")
+      self.expect("b bar")
+      self.expect("c")
+      self.expect("thread trace start")
+      self.expect("si")
+      self.expect("thread trace dump function-calls",
+        patterns=[f'''<subtrace #0: instructions>
+    -> libbar.so`bar\(int\)
+       |\d+ {ADDRESS_REGEX} <\+\d+> at bar.cpp:8:7'''])
+
+      #Now we proceed to trace post-mortem traces
+      self.expect("trace load -v " +
+        os.path.join(self.getSourceDir(), "..", "intelpt-multi-core-trace", "trace.json"))
+
+      self.expect("thread trace dump function-calls 2 --from-id 19532 --to-id 19532",
+        substrs=['''thread #2: tid = 3497496
+
+  <subtrace #0: tracing errors>
+    |19532: expected tracing enabled event'''])
+
+      self.expect("thread trace dump function-calls 2 --to-id 4",
+        substrs=['''thread #2: tid = 3497496
+
+  <subtrace #0: instructions>
+    -> m.out`foo()
+       |4: 0x0000000000400ba7 <+65> at multi_thread.cpp:12:21'''])
+
+      self.expect("trace load -v " +
+        os.path.join(self.getSourceDir(), "..", "intelpt-trace-multi-file", "multi-file-no-ld.json"))
+
+      self.expect("thread trace dump function-calls --from-id 10 --to-id 10",
+        substrs=['''thread #1: tid = 815455
+
+  <subtrace #0: instructions>
+    -> a.out.PT_LOAD[0]..plt
+       |10: 0x0000000000400510 <+0>'''])
+
+      self.expect("file " + os.path.join(self.getSourceDir(), "..", "inline-function", "a.out"))
+      self.expect("b 16")
+      self.expect("r")
+      self.expect("thread trace start")
+      self.expect("si")
+      self.expect("thread trace dump function-calls",
+        substrs=['''<subtrace #0: instructions>
+    -> a.out`foo(int)
+        -> [inlined] a.out`inlined_parent(int, int)
+            -> [inlined] a.out`inlined_1(int, int)
+               |2: 0x0000000000400583 <+0> at inline.cpp:16:7'''])
+      # As a way to test unknown regions, we can remove a module and symbolicate the trace again
+      target = self.dbg.GetSelectedTarget()
+      self.assertTrue(target.RemoveModule(target.modules[0]))
+      self.expect("thread trace dump function-calls",
+        substrs=['''<subtrace #0: instructions>
+    -> unknown region
+       |2: 0x0000000000400583'''])
+
+    def testDumpSimpleFunctionCalls(self):
+      self.expect("trace load -v " +
+        os.path.join(self.getSourceDir(), "..", "intelpt-trace", "trace.json"))
+
+      self.expect("thread trace dump function-calls 2",
+        error=True, substrs=['error: no thread with index: "2"'])
+
+      # TODO: support JSON
+      """
+      self.expect("thread trace dump function-calls 1 -j",
+        substrs=['[{"tracedSegments":[{"firstInstructionId":"3","lastInstructionId":"26"}]}]'])
+
+      self.expect("thread trace dump function-calls 1 -J",
+        substrs=['''[
+  {
+    "tracedSegments": [
+      {
+        "firstInstructionId": "3",
+        "lastInstructionId": "26"
+      }
+    ]
+  }
+]'''])
+      """
+
+      # We test first some code without function call
+      self.expect("thread trace dump function-calls 1",
+        substrs=['''thread #1: tid = 3842849
+
+  <subtrace #0: instructions>
+    -> a.out`main
+       |3: 0x0000000000400511 <+4> at main.cpp:2
+       |... 19 instructions
+       |26: 0x000000000040052d <+32> at main.cpp:4'''])
+
+    def testFunctionCallsWithErrors(self):
+      self.expect("trace load -v " +
+        os.path.join(self.getSourceDir(), "..", "intelpt-multi-core-trace", "trace.json"))
+
+      self.expect("thread trace dump function-calls 2",
+        substrs=['''thread #2: tid = 3497496
+
+  <subtrace #0: instructions>
+    -> m.out`foo()
+       |4: 0x0000000000400ba7 <+65> at multi_thread.cpp:12:21
+       |... 19519 instructions
+       |19524: 0x0000000000400ba7 <+65> at multi_thread.cpp:12:21
+
+  <subtrace #1: tracing errors>
+    |19532: expected tracing enabled event'''])
+
+      # TODO: support JSON
+      """
+      self.expect("thread trace dump function-calls 2 -J",
+        substrs=['''[
+  {
+    "tracedSegments": [
+      {
+        "firstInstructionId": "4",
+        "lastInstructionId": "19524"
+      }
+    ]
+  },
+  {
+    "tracedSegments": [
+      {
+        "firstInstructionId": "19532",
+        "lastInstructionId": "19532"
+      }
+    ]
+  }
+]'''])
+      """
+
+      self.expect("thread trace dump function-calls 3",
+        substrs=['''thread #3: tid = 3497497
+
+  <subtrace #0: instructions>
+    -> m.out`bar()
+       |5: 0x0000000000400bdb <+30> at multi_thread.cpp:19:3
+       |... 61823 instructions
+       |61831: 0x0000000000400bd7 <+26> at multi_thread.cpp:20:6
+
+  <subtrace #1: tracing errors>
+    |61834: expected tracing enabled event'''])
+
+      # TODO: support JSON
+      """
+      self.expect("thread trace dump function-calls 3 -J",
+        substrs=['''[
+  {
+    "tracedSegments": [
+      {
+        "firstInstructionId": "5",
+        "lastInstructionId": "61831"
+      }
+    ]
+  },
+  {
+    "tracedSegments": [
+      {
+        "firstInstructionId": "61834",
+        "lastInstructionId": "61834"
+      }
+    ]
+  }
+]'''])
+      """
+
+    def testInlineFunctionCalls(self):
+      self.expect("file " + os.path.join(self.getSourceDir(), "..", "inline-function", "a.out"))
+      self.expect("b main") # we'll trace from the beginning of main
+      self.expect("b 58")
+      self.expect("r")
+      self.expect("thread trace start")
+      self.expect("c")
+      self.expect("si")
+      self.expect("thread trace dump function-calls",
+        substrs=['''<subtrace #0: instructions>
+    -> a.out`main
+       |2: 0x0000000000400602 <+8> at inline.cpp:55:7
+       |... 2 instructions
+       |6: 0x000000000040060e <+20> at inline.cpp:56:14
+        -> a.out`foo(int)
+           |7: 0x0000000000400556 <+0> at inline.cpp:48:16
+           |... 7 instructions
+           |15: 0x000000000040056d <+23> at inline.cpp:49:25
+            -> [inlined] a.out`inlined_parent(int, int)
+               |16: 0x0000000000400570 <+0> at inline.cpp:40:7
+               |... 3 instructions
+               |20: 0x0000000000400580 <+16> at inline.cpp:40:7
+                -> [inlined] a.out`inlined_1(int, int)
+                   |21: 0x0000000000400583 <+0> at inline.cpp:16:7
+                   |... 7 instructions
+                   |29: 0x000000000040059b <+24> at inline.cpp:18:15
+                    -> a.out`never_inline(int, int)
+                       |30: 0x0000000000400621 <+0> at inline.cpp:8:65
+                       |... 9 instructions
+                       |40: 0x000000000040063d <+28> at inline.cpp:9:13
+                        -> [inlined] a.out`deep_inline(int, int)
+                           |41: 0x0000000000400640 <+0> at inline.cpp:2:7
+                           |... 6 instructions
+                           |48: 0x0000000000400658 <+24> at inline.cpp:5:10
+                       |49: 0x000000000040065b <+58> at inline.cpp:9:35
+                       |... 7 instructions
+                       |57: 0x0000000000400672 <+81> at inline.cpp:13:1
+                   |58: 0x00000000004005a0 <+29> at inline.cpp:19:5
+                   |... 2 instructions
+                   |61: 0x00000000004005aa <+39> at inline.cpp:20:10
+               |62: 0x00000000004005ad <+61> at inline.cpp:41:7
+               |... 3 instructions
+               |66: 0x00000000004005b9 <+73> at inline.cpp:41:7
+                -> [inlined] a.out`inlined_2(int, int)
+                   |67: 0x00000000004005bc <+0> at inline.cpp:24:15
+                   |... 3 instructions
+                   |71: 0x00000000004005c6 <+10> at inline.cpp:24:15
+                    -> a.out`never_inline(int, int)
+                       |72: 0x0000000000400621 <+0> at inline.cpp:8:65
+                       |... 9 instructions
+                       |82: 0x000000000040063d <+28> at inline.cpp:9:13
+                        -> [inlined] a.out`deep_inline(int, int)
+                           |83: 0x0000000000400640 <+0> at inline.cpp:2:7
+                           |... 6 instructions
+                           |90: 0x0000000000400658 <+24> at inline.cpp:5:10
+                       |91: 0x000000000040065b <+58> at inline.cpp:9:35
+                       |... 7 instructions
+                       |99: 0x0000000000400672 <+81> at inline.cpp:13:1
+                   |100: 0x00000000004005cb <+15> at inline.cpp:25:7
+                   |... 6 instructions
+                   |107: 0x00000000004005e3 <+39> at inline.cpp:28:10
+               |108: 0x00000000004005e6 <+118> at inline.cpp:42:7
+                -> [inlined] a.out`inlined_void()
+                    -> [inlined] a.out`inlined_nested_void()
+                       |109: 0x00000000004005e9 <+0> at inline.cpp:32:13
+                -> [inlined] a.out`inlined_void()
+                    -> [inlined] a.out`inlined_nested_void()
+                       |110: 0x00000000004005ea <+0> at inline.cpp:32:13
+               |111: 0x00000000004005eb <+123> at inline.cpp:45:10
+           |112: 0x00000000004005ee <+152> at inline.cpp:49:25
+           |... 3 instructions
+           |116: 0x00000000004005f9 <+163> at inline.cpp:52:1
+       |117: 0x0000000000400613 <+25> at inline.cpp:56:14
+        -> [inlined] a.out`inlined_void()
+            -> [inlined] a.out`inlined_nested_void()
+               |118: 0x0000000000400616 <+0> at inline.cpp:32:13
+       |120: 0x0000000000400617 <+29> at inline.cpp:58:14'''])
+
+      # TODO: support JSON
+      """
+      self.expect("thread trace dump function-calls -J",
+        substrs=['''[
+  {
+    "tracedSegments": [
+      {
+        "firstInstructionId": "2",
+        "lastInstructionId": "6",
+        "nestedCall": {
+          "tracedSegments": [
+            {
+              "firstInstructionId": "7",
+              "lastInstructionId": "14",
+              "nestedCall": {
+                "tracedSegments": [
+                  {
+                    "firstInstructionId": "15",
+                    "lastInstructionId": "22"
+                  }
+                ]
+              }
+            },
+            {
+              "firstInstructionId": "23",
+              "lastInstructionId": "27"
+            }
+          ]
+        }
+      },
+      {
+        "firstInstructionId": "28",
+        "lastInstructionId": "28"
+      }
+    ]
+  }
+]'''])
+      """
+
+    def testIncompleteInlineFunctionCalls(self):
+      self.expect("file " + os.path.join(self.getSourceDir(), "..", "inline-function", "a.out"))
+      self.expect("b 4") # we'll trace from the middle of the inline method
+      self.expect("r")
+      self.expect("breakpoint delete 1")
+      self.expect("thread trace start")
+      self.expect("b 57")
+      self.expect("c")
+      self.expect("si")
+      self.expect("thread trace dump function-calls --to-id 6",
+        substrs=['''<subtrace #0: instructions>
+    -> a.out`never_inline(int, int)
+        -> [inlined] a.out`deep_inline(int, int)
+           |2: 0x000000000040064e <+14> at inline.cpp:4:5
+           |... 2 instructions
+           |5: 0x0000000000400658 <+24> at inline.cpp:5:10
+       |6: 0x000000000040065b <+58> at inline.cpp:9:3'''])
+
+      self.expect("thread trace dump function-calls",
+        substrs=['''<subtrace #0: instructions>
+    -> a.out`main
+        -> a.out`foo(int)
+            -> a.out`never_inline(int, int)
+                -> [inlined] a.out`deep_inline(int, int)
+                   |2: 0x000000000040064e <+14> at inline.cpp:4:5
+                   |... 2 instructions
+                   |5: 0x0000000000400658 <+24> at inline.cpp:5:10
+               |6: 0x000000000040065b <+58> at inline.cpp:9:35
+               |... 7 instructions
+               |14: 0x0000000000400672 <+81> at inline.cpp:13:1
+            -> [inlined] a.out`inlined_parent(int, int)
+                -> [inlined] a.out`inlined_1(int, int)
+                   |15: 0x00000000004005a0 <+29> at inline.cpp:19:5
+                   |... 2 instructions
+                   |18: 0x00000000004005aa <+39> at inline.cpp:20:10
+               |19: 0x00000000004005ad <+61> at inline.cpp:41:7
+               |... 3 instructions
+               |23: 0x00000000004005b9 <+73> at inline.cpp:41:7
+                -> [inlined] a.out`inlined_2(int, int)
+                   |24: 0x00000000004005bc <+0> at inline.cpp:24:15
+                   |... 3 instructions
+                   |28: 0x00000000004005c6 <+10> at inline.cpp:24:15
+                    -> a.out`never_inline(int, int)
+                       |29: 0x0000000000400621 <+0> at inline.cpp:8:65
+                       |... 9 instructions
+                       |39: 0x000000000040063d <+28> at inline.cpp:9:13
+                        -> [inlined] a.out`deep_inline(int, int)
+                           |40: 0x0000000000400640 <+0> at inline.cpp:2:7
+                           |... 6 instructions
+                           |47: 0x0000000000400658 <+24> at inline.cpp:5:10
+                       |48: 0x000000000040065b <+58> at inline.cpp:9:35
+                       |... 7 instructions
+                       |56: 0x0000000000400672 <+81> at inline.cpp:13:1
+                   |57: 0x00000000004005cb <+15> at inline.cpp:25:7
+                   |... 6 instructions
+                   |64: 0x00000000004005e3 <+39> at inline.cpp:28:10
+               |65: 0x00000000004005e6 <+118> at inline.cpp:42:7
+                -> [inlined] a.out`inlined_void()
+                    -> [inlined] a.out`inlined_nested_void()
+                       |66: 0x00000000004005e9 <+0> at inline.cpp:32:13
+                -> [inlined] a.out`inlined_void()
+                    -> [inlined] a.out`inlined_nested_void()
+                       |67: 0x00000000004005ea <+0> at inline.cpp:32:13
+               |68: 0x00000000004005eb <+123> at inline.cpp:45:10
+           |69: 0x00000000004005ee <+152> at inline.cpp:49:25
+           |... 3 instructions
+           |73: 0x00000000004005f9 <+163> at inline.cpp:52:1
+       |74: 0x0000000000400613 <+25> at inline.cpp:56:14
+        -> [inlined] a.out`inlined_void()
+            -> [inlined] a.out`inlined_nested_void()
+               |75: 0x0000000000400616 <+0> at inline.cpp:32:13
+       |77: 0x0000000000400617 <+29> at inline.cpp:58:14'''])
+
+      # TODO: support JSON
+      """
+      self.expect("thread trace dump function-calls -J",
+        substrs=['''[
+  {
+    "untracedPrefixSegment": {
+      "nestedCall": {
+        "untracedPrefixSegment": {
+          "nestedCall": {
+            "tracedSegments": [
+              {
+                "firstInstructionId": "2",
+                "lastInstructionId": "6"
+              }
+            ]
+          }
+        },
+        "tracedSegments": [
+          {
+            "firstInstructionId": "7",
+            "lastInstructionId": "11"
+          }
+        ]
+      }
+    },
+    "tracedSegments": [
+      {
+        "firstInstructionId": "12",
+        "lastInstructionId": "12"
+      }
+    ]
+  }
+]'''])
+      """
+
+    def testMultifileFunctionCalls(self):
+      # This test is extremely important because it first calls the method foo() which requires going through the dynamic linking.
+      # You'll see the entry "a.out`symbol stub for: foo()" which will invoke the ld linker, which will in turn find the actual foo
+      # function and eventually invoke it.  However, we don't have the image of the linker in the trace bundle, so we'll see errors
+      # because the decoder couldn't find the linker binary! After those failures, the linker will resume right where we return to
+      # main after foo() finished.
+      # Then, we call foo() again, but because it has already been loaded by the linker, we don't invoke the linker anymore! And
+      # we'll see a nice tree without errors in this second invocation. Something interesting happens here. We still have an
+      # invocation to the symbol stub for foo(), but it modifies the stack so that when we return from foo() we don't stop again
+      # at the symbol stub, but instead we return directly to main. This is an example of returning several levels up in the
+      # call stack.
+      # Not only that, we also have an inline method in between.
+      self.expect("trace load " + os.path.join(self.getSourceDir(), "..", "intelpt-trace-multi-file", "multi-file-no-ld.json"))
+      self.expect("thread trace dump function-calls",
+        substrs=['''thread #1: tid = 815455
+
+  <subtrace #0: instructions>
+    -> a.out`main
+       |3: 0x000000000040066f <+15> at main.cpp:10
+        -> a.out`foo()
+           |7: 0x0000000000400540 <+0>
+           |... 1 instruction
+           |9: 0x000000000040054b <+11>
+            -> a.out.PT_LOAD[0]..plt
+               |10: 0x0000000000400510 <+0>
+               |11: 0x0000000000400516 <+6>
+
+  <subtrace #1: tracing errors>
+    |12: no memory mapped at this address: 0x00007ffff7df1950
+
+  <subtrace #2: instructions>
+    -> a.out`main
+       |16: 0x0000000000400674 <+20> at main.cpp:10
+       |... 2 instructions
+       |22: 0x000000000040067f <+31> at main.cpp:12
+        -> [inlined] a.out`inline_function()
+           |26: 0x0000000000400682 <+0> at main.cpp:4
+           |... 3 instructions
+           |30: 0x0000000000400694 <+18> at main.cpp:6
+       |31: 0x0000000000400697 <+55> at main.cpp:14
+       |... 2 instructions
+       |37: 0x000000000040069f <+63> at main.cpp:16
+        -> a.out`foo()
+           |38: 0x0000000000400540 <+0>
+            -> libfoo.so`foo()
+               |39: 0x00007ffff7bd96e0 <+0> at foo.cpp:3
+               |... 2 instructions
+               |42: 0x00007ffff7bd96e8 <+8> at foo.cpp:4
+                -> libfoo.so`bar()
+                   |43: 0x00007ffff7bd95d0 <+0>
+                    -> libbar.so`bar()
+                       |44: 0x00007ffff79d7690 <+0> at bar.cpp:1
+                       |... 7 instructions
+                       |52: 0x00007ffff79d76aa <+26> at bar.cpp:4
+               |53: 0x00007ffff7bd96ed <+13> at foo.cpp:4
+               |... 6 instructions
+               |60: 0x00007ffff7bd9703 <+35> at foo.cpp:6
+       |61: 0x00000000004006a4 <+68> at main.cpp:16
+       |... 1 instruction
+       |63: 0x00000000004006a9 <+73> at main.cpp:16'''])
+
+      # TODO: support JSON
+      """
+      self.expect("thread trace dump function-calls -J",
+        substrs=['''[
+  {
+    "tracedSegments": [
+      {
+        "firstInstructionId": "3",
+        "lastInstructionId": "3",
+        "nestedCall": {
+          "tracedSegments": [
+            {
+              "firstInstructionId": "7",
+              "lastInstructionId": "9",
+              "nestedCall": {
+                "tracedSegments": [
+                  {
+                    "firstInstructionId": "10",
+                    "lastInstructionId": "11"
+                  }
+                ]
+              }
+            }
+          ]
+        }
+      }
+    ]
+  },
+  {
+    "tracedSegments": [
+      {
+        "firstInstructionId": "12",
+        "lastInstructionId": "12"
+      }
+    ]
+  },
+  {
+    "tracedSegments": [
+      {
+        "firstInstructionId": "16",
+        "lastInstructionId": "22",
+        "nestedCall": {
+          "tracedSegments": [
+            {
+              "firstInstructionId": "26",
+              "lastInstructionId": "30"
+            }
+          ]
+        }
+      },
+      {
+        "firstInstructionId": "31",
+        "lastInstructionId": "37",
+        "nestedCall": {
+          "tracedSegments": [
+            {
+              "firstInstructionId": "38",
+              "lastInstructionId": "38",
+              "nestedCall": {
+                "tracedSegments": [
+                  {
+                    "firstInstructionId": "39",
+                    "lastInstructionId": "42",
+                    "nestedCall": {
+                      "tracedSegments": [
+                        {
+                          "firstInstructionId": "43",
+                          "lastInstructionId": "43",
+                          "nestedCall": {
+                            "tracedSegments": [
+                              {
+                                "firstInstructionId": "44",
+                                "lastInstructionId": "52"
+                              }
+                            ]
+                          }
+                        }
+                      ]
+                    }
+                  },
+                  {
+                    "firstInstructionId": "53",
+                    "lastInstructionId": "60"
+                  }
+                ]
+              }
+            }
+          ]
+        }
+      },
+      {
+        "firstInstructionId": "61",
+        "lastInstructionId": "63"
+      }
+    ]
+  }
+]'''])
+      """

lldb/test/API/commands/trace/function_calls/bar.h

+int bar(int);

lldb/test/API/commands/trace/function_calls/bar.cpp

+#include "bar.h"
+
+int zaz(int y) { return y * y; }
+
+int bar(int x) {
+  int res = 0;
+  res += zaz(x + 1);
+  res += zaz(x + 2);
+  return res;
+}

lldb/test/API/commands/trace/function_calls/foo.cpp

+#include "bar.h"
+
+int taz(int x) { return x * x * x; }
+
+int main() {
+  int x = 12;
+  int res = bar(x);
+  return taz(res);
+}

lldb/test/API/commands/trace/inline-function/inline.cpp

-__attribute__((always_inline)) inline int mult(int x, int y) {
+__attribute__((always_inline)) inline int deep_inline(int x, int y) {
   int f = x * y;
   f++;
   f *= f;
   return f;
 }
 
+__attribute__((noinline)) inline int never_inline(int x, int y) {
+  int f = x * y + deep_inline(x, y);
+  f++;
+  f *= f;
+  return f;
+}
+
+__attribute__((always_inline)) inline int inlined_1(int x, int y) {
+  int f = x * y;
+  f++;
+  never_inline(x, y);
+  f *= f;
+  return f;
+}
+
+__attribute__((always_inline)) inline int inlined_2(int x, int y) {
+  never_inline(x, y);
+  int f = x * y;
+  f++;
+  f *= f;
+  return f;
+}
+
+__attribute__((always_inline)) inline void inlined_nested_void() { asm("nop"); }
+
+__attribute__((always_inline)) inline void inlined_void() {
+  inlined_nested_void();
+}
+
+__attribute__((always_inline)) inline int inlined_parent(int x, int y) {
+  int res = 0;
+  res += inlined_1(x, y);
+  res += inlined_2(x, y);
+  inlined_void();
+  inlined_void();
+  return res;
+}
+
 int foo(int x) {
-  int z = mult(x, x - 1);
+  int z = inlined_parent(x, x - 1);
   z++;
   return z;
 }
 
 int main() {
   int x = 12;
   int z = foo(x);
+  inlined_void();
   return z + x;
 }

lldb/test/API/tools/lldb-vscode/module/TestVSCode_module.py

def run_test(self, symbol_basename, expect_debug_info_size):
 
         def checkSymbolsLoadedWithSize():
             active_modules = self.vscode.get_modules()
             program_module = active_modules[program_basename]
             self.assertIn('symbolFilePath', program_module)
             self.assertIn(symbols_path, program_module['symbolFilePath'])
             symbol_regex = re.compile(r"[0-9]+(\.[0-9]*)?[KMG]?B")
             return symbol_regex.match(program_module['symbolStatus'])
-                
         if expect_debug_info_size:
             self.waitUntil(checkSymbolsLoadedWithSize)
         active_modules = self.vscode.get_modules()
         program_module = active_modules[program_basename]
         self.assertEqual(program_basename, program_module['name'])
         self.assertEqual(program, program_module['path'])
         self.assertIn('addressRange', program_module)
 
     @skipIfWindows
-    @skipIfRemote  
+    @skipIfRemote
     def test_modules(self):
         '''
             Mac or linux.
 
             On mac, if we load a.out as our symbol file, we will use DWARF with .o files and we will
             have debug symbols, but we won't see any debug info size because all of the DWARF
             sections are in .o files.
 
             On other platforms, we expect a.out to have debug info, so we will expect a size.
         '''
         return self.run_test("a.out", expect_debug_info_size=platform.system() != 'Darwin')
 
     @skipUnlessDarwin
-    @skipIfRemote    
+    @skipIfRemote
     def test_modules_dsym(self):
         '''
             Darwin only test with dSYM file.
 
             On mac, if we load a.out.dSYM as our symbol file, we will have debug symbols and we
             will have DWARF sections added to the module, so we will expect a size.
         '''
         return self.run_test("a.out.dSYM", expect_debug_info_size=True)