Add support for artificial tail call frames

[vsk]

Summary

This patch teaches lldb to detect when there are missing frames in a
backtrace due to a sequence of tail calls, and to fill in the backtrace
with artificial tail call frames when this happens. This is only done
when the execution history can be determined from the call graph and
from the return PC addresses of calls on the stack. Ambiguous sequences
of tail calls (e.g anything involving tail calls and recursion) are
detected and ignored.

Depends on D49887.

[vsk]

Rebase, and update the patch to use DW_AT_call_return_pc information.

[vsk]

Ping.

[sgraenitz]

Interesting topic and very well-written patch. Semantics look reasonable, but can't say much about the details. Added a few minor notes inline.

lldb/include/lldb/Symbol/Function.h

456

Typo: tail-calling

lldb/packages/Python/lldbsuite/test/decorators.py

691

Two leading "" missing?

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

3761

Does any of the tests fail in case LLVM DWARFs change? Or is it very unlikely?

lldb/source/Symbol/Function.cpp

149

Easy to confuse with lambda assignment (although it wouldn't make any sense).

auto resolve = [&]() -> Function * {
   ...
};
lazy_callee.def = resolve();
resolved = true;

Maybe?

[aprantl]

lldb/include/lldb/Symbol/Function.h

331

llvm::PointerUnion ?

[vsk]

Thanks for the feedback!

lldb/include/lldb/Symbol/Function.h

331

It's not possible to use PointerUnion here because const char * has 1-byte alignment. There's no space in the pointer to store a discriminator bit.

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

3761

Yes, the tests in this patch would fail if TAG_call_site entries were nested within the nearest enclosing lexical block (as specified by DWARF 5). We would have a heads-up about such a breaking change. That said, it's unlikely to catch us by surprise, because we control the LLVM DWARF producer (see https://reviews.llvm.org/D49887).

[aprantl]

lldb/include/lldb/Symbol/Function.h

331

Good point!

[vsk]

I've added SB API support (SBFrame::IsArtificial), a SB API test, fleshed out the remaining tests, and rebased. PTAL, thanks!

[jingham]

Can you add a test that makes sure that when you stop in a frame that has artificial frames above it, and then you do "finish", or "step out" past the end of frame 0, the presence of the artificial frame doesn't confuse us? I am pretty sure that will just work, but it would be good to make sure that it actually does.

[jingham]

Really "step out past the end of the frame" isn't really necessary, since that doesn't pay any attention to the frames above it, it just runs the code till the frame ID changes. But "finish" does look at the parent frame, so it might get confused.

[vsk]

In D50478#1241264, @jingham wrote:

Can you add a test that makes sure that when you stop in a frame that has artificial frames above it, and then you do "finish", or "step out" past the end of frame 0, the presence of the artificial frame doesn't confuse us? I am pretty sure that will just work, but it would be good to make sure that it actually does.

Really "step out past the end of the frame" isn't really necessary, since that doesn't pay any attention to the frames above it, it just runs the code till the frame ID changes. But "finish" does look at the parent frame, so it might get confused.

Great suggestion. The 'finish' command doesn't appear to understand artificial frames, and allows program execution to continue past the point where a tail call is made. I'll try and teach it to "look past" artificial frames.

[vsk]

Teach SBThread::StepOut and SBThread::ReturnFromFrame to behave as-if artificial frames were not present.

This preserves the current behavior of "finish" and "thread return". The alternatives -- stepping out into an artificial frame or issuing errors -- don't appear to be better. The newly-added thread_step_out_or_return test covers this.

[vsk]

As discussed offline, print out a note when stepping out of a frame with artificial ancestors explaining that they were skipped while stepping out. See the added test: functionalities/tail_call_frames/thread_step_out_message.

[vsk]

While testing this out, I found an issue with CallEdge::GetReturnPCAddress. Getting the load address there adds an unnecessary slide to the PC. I'll try to have that worked out next week.

[vsk]

The bug I thought I saw in CallEdge::GetReturnPCAddress turned out to be an issue I introduced in dsymutil. It's not correct for dsymutil to relocate the return PC value in TAG_call_site entries, because the correct section slide offset can't be applied until we have a running process (and things like dylibs are mapped in).

Other changes:

• Add a test which requires both inline frame and tail call frame support.
• Require a call edge’s return PC attribute to match the register context’s PC exactly. Otherwise, we report incorrect frames.
• Improve logging and add more tests.

[aprantl]

lldb/source/Target/StackFrameList.cpp

331

On what path can this happen? Aren't all paths that set ambiguous=true returning immediately?

404

auto synth_frame = llvm::make_unique<StackFrame>(..) ?

[vsk]

• Use std::make_shared<StackFrame>(...), instead of StackFrameSP(new ...).

lldb/source/Target/StackFrameList.cpp

331

If a recursive call to dfs() sets ambiguous = true and returns early, we also want its caller to return early instead of visiting any additional edges. This is a small optimization: the code is correct without the early return.

[vsk]

Friendly ping.

[aprantl]

This looks pretty good! I have one last question about CallEdge inside.

lldb/include/lldb/Symbol/Function.h

304

Does this also work for C functions? If yes, would symbol_name be a more accurate description?

Is this pointer globally unique in the program, or can two mangled names appear in a legal C program that don't refer to the same function?

lldb/include/lldb/Target/StackFrame.h

65

e.g.,

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq2/TestAmbiguousTailCallSeq2.py

6

This test should be restricted to only run with clang as the compiler or the -glldb flag won't work.

I see. It is implicit in in skipUnlessHasCallSiteInfo — perhaps we should just generally add -glldb to CFLAGS? It's not a bug deal.

[vsk]

• Address feedback from Adrian.

lldb/include/lldb/Symbol/Function.h

304

Yes, C functions are handled. I'll use "symbol_name", hopefully that makes it clearer.

304

Great question. No, a symbol name is not necessarily globally unique. Prior to C11, the one-definition-rule doesn't apply. Even with the ODR, a private symbol in a shared library may have the same name as a strong definition in the main executable.

I haven't tried to disambiguate ODR conflicts in this patch. What happens when a conflict occurs is: FindFunctionSymbols prioritizes the symbol in the main executable, and if the call edge's return PC doesn't exactly match what's in the register state we decline to create any artificial frames. I.e. in the presence of ODR conflicts, we only present artificial frames when we're 100% sure they are accurate.

Handling ODR conflicts is a 'to do', though. I'll make an explicit note of that here.

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq2/TestAmbiguousTailCallSeq2.py

6

Yes, skipUnlessHasCallSiteInfo requires clang for now. I don't think we can add -glldb to a higher-level CFLAGS variable without breaking compiling with gcc?

[aprantl]

lldb/include/lldb/Symbol/Function.h

304

Thanks! It might be interesting to grep through an XNU dsym to see just how common conflicts are in typical C code.

[vsk]

lldb/include/lldb/Symbol/Function.h

304

Of a total of ~27,000 function names in xnu, 140 names were duplicates. In every case I spot-checked, a subprogram with a duplicate AT_name had a unique AT_linkage_name. So, well under 0.5% in that project.

[aprantl]

Thanks!

[stella.stamenova]

Unfortunately, the bots are broken because of the FileCheck issue, so I can't confirm with them, but I see a number of these tests fail in our local testing. Some fail on both Windows and Linux and some just fail on Linux. Here are the failing tests:

Linux:
lldb-Suite :: functionalities/tail_call_frames/disambiguate_call_site/TestDisambiguateCallSite.py
lldb-Suite :: functionalities/tail_call_frames/disambiguate_paths_to_common_sink/TestDisambiguatePathsToCommonSink.py
lldb-Suite :: functionalities/tail_call_frames/disambiguate_tail_call_seq/TestDisambiguateTailCallSeq.py
lldb-Suite :: functionalities/tail_call_frames/inlining_and_tail_calls/TestInliningAndTailCalls.py
lldb-Suite :: functionalities/tail_call_frames/sbapi_support/TestTailCallFrameSBAPI.py
lldb-Suite :: functionalities/tail_call_frames/thread_step_out_message/TestArtificialFrameStepOutMessage.py
lldb-Suite :: functionalities/tail_call_frames/unambiguous_sequence/TestUnambiguousTailCalls.py

Windows:
lldb-Suite :: functionalities/tail_call_frames/sbapi_support/TestTailCallFrameSBAPI.py
lldb-Suite :: functionalities/tail_call_frames/thread_step_out_or_return/TestSteppingOutWithArtificialFrames.py

Let me know what you need to investigate.

[vsk]

In D50478#1262710, @stella.stamenova wrote:

Unfortunately, the bots are broken because of the FileCheck issue, so I can't confirm with them, but I see a number of these tests fail in our local testing. Some fail on both Windows and Linux and some just fail on Linux. Here are the failing tests:

Linux:
lldb-Suite :: functionalities/tail_call_frames/disambiguate_call_site/TestDisambiguateCallSite.py
lldb-Suite :: functionalities/tail_call_frames/disambiguate_paths_to_common_sink/TestDisambiguatePathsToCommonSink.py
lldb-Suite :: functionalities/tail_call_frames/disambiguate_tail_call_seq/TestDisambiguateTailCallSeq.py
lldb-Suite :: functionalities/tail_call_frames/inlining_and_tail_calls/TestInliningAndTailCalls.py
lldb-Suite :: functionalities/tail_call_frames/sbapi_support/TestTailCallFrameSBAPI.py
lldb-Suite :: functionalities/tail_call_frames/thread_step_out_message/TestArtificialFrameStepOutMessage.py
lldb-Suite :: functionalities/tail_call_frames/unambiguous_sequence/TestUnambiguousTailCalls.py

Windows:
lldb-Suite :: functionalities/tail_call_frames/sbapi_support/TestTailCallFrameSBAPI.py
lldb-Suite :: functionalities/tail_call_frames/thread_step_out_or_return/TestSteppingOutWithArtificialFrames.py

Let me know what you need to investigate.

Strange, I didn't get any bot failure notifications in the days after this landed. Could you share the output from the failing tests?

[zturner]

See the other email thread. The bots have been broken since September, all
of them complain about missing FileCheck executable

[zturner]

https://reviews.llvm.org/D53002

Is the thread I'm referring to.

[stella.stamenova]

In D50478#1262717, @vsk wrote:

In D50478#1262710, @stella.stamenova wrote:

Unfortunately, the bots are broken because of the FileCheck issue, so I can't confirm with them, but I see a number of these tests fail in our local testing. Some fail on both Windows and Linux and some just fail on Linux. Here are the failing tests:

Linux:
lldb-Suite :: functionalities/tail_call_frames/disambiguate_call_site/TestDisambiguateCallSite.py
lldb-Suite :: functionalities/tail_call_frames/disambiguate_paths_to_common_sink/TestDisambiguatePathsToCommonSink.py
lldb-Suite :: functionalities/tail_call_frames/disambiguate_tail_call_seq/TestDisambiguateTailCallSeq.py
lldb-Suite :: functionalities/tail_call_frames/inlining_and_tail_calls/TestInliningAndTailCalls.py
lldb-Suite :: functionalities/tail_call_frames/sbapi_support/TestTailCallFrameSBAPI.py
lldb-Suite :: functionalities/tail_call_frames/thread_step_out_message/TestArtificialFrameStepOutMessage.py
lldb-Suite :: functionalities/tail_call_frames/unambiguous_sequence/TestUnambiguousTailCalls.py

Windows:
lldb-Suite :: functionalities/tail_call_frames/sbapi_support/TestTailCallFrameSBAPI.py
lldb-Suite :: functionalities/tail_call_frames/thread_step_out_or_return/TestSteppingOutWithArtificialFrames.py

Let me know what you need to investigate.

Strange, I didn't get any bot failure notifications in the days after this landed. Could you share the output from the failing tests?

All the failures on Windows are happening when validating the function name. For example:

======================================================================

FAIL: test_tail_call_frame_sbapi (TestTailCallFrameSBAPI.TestTailCallFrameSBAPI)

----------------------------------------------------------------------

Traceback (most recent call last):

  File "E:\_work\55\s\llvm\tools\lldb\packages\Python\lldbsuite\test\functionalities\tail_call_frames\sbapi_support\TestTailCallFrameSBAPI.py", line 19, in test_tail_call_frame_sbapi

    self.do_test()

  File "E:\_work\55\s\llvm\tools\lldb\packages\Python\lldbsuite\test\functionalities\tail_call_frames\sbapi_support\TestTailCallFrameSBAPI.py", line 64, in do_test

    self.assertTrue(frame.GetDisplayFunctionName() == name)

AssertionError: False is not True

Config=x86_64-E:\_work\55\b\LLVMBuild\Release\bin\clang.exe

----------------------------------------------------------------------

There are several different failures on Linux. Here's the first one:

FAIL: LLDB (/vstsdrive/_work/38/b/LLVMBuild/bin/clang-8-x86_64) :: test_dwarf (lldbsuite.test.lldbtest.TestDisambiguateCallSite)

--- FileCheck trace (code=1) ---
/vstsdrive/_work/38/b/LLVMBuild/bin/FileCheck /vstsdrive/_work/38/s/llvm/tools/lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_call_site/main.cpp -implicit-check-not=artificial

FileCheck input:
* thread #1, name = 'a.out', stop reason = breakpoint 1.1
  * frame #0: 0x0000000000400580 a.out`sink() at main.cpp:13:4 [opt]
    frame #1: 0x00000000004005b8 a.out`main(argc=1, (null)=<unavailable>) at main.cpp:28:3 [opt]
    frame #2: 0x00007f980aff7830 libc.so.6`__libc_start_main + 240
    frame #3: 0x00000000004004a9 a.out`_start + 41


FileCheck output:

/vstsdrive/_work/38/s/llvm/tools/lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_call_site/main.cpp:15:17: error: CHECK-NEXT: expected string not found in input
 // CHECK-NEXT: func2{{.*}} [opt] [artificial]
                ^
<stdin>:3:2: note: scanning from here
 frame #1: 0x00000000004005b8 a.out`main(argc=1, (null)=<unavailable>) at main.cpp:28:3 [opt]
 ^
<stdin>:3:80: note: possible intended match here
 frame #1: 0x00000000004005b8 a.out`main(argc=1, (null)=<unavailable>) at main.cpp:28:3 [opt]
                                                                              ^

Let me know if you need more logs.

lldb/include/lldb/API/SBFrame.h

public:
 
   /// Return true if this frame represents an inlined function.
   ///
   /// See also GetFunctionName().
   bool IsInlined();
 
   bool IsInlined() const;
 
+  bool IsArtificial();
+
+  bool IsArtificial() const;
+
   /// The version that doesn't supply a 'use_dynamic' value will use the
   /// target's default.
   lldb::SBValue EvaluateExpression(const char *expr);
 
   lldb::SBValue EvaluateExpression(const char *expr,
                                    lldb::DynamicValueType use_dynamic);
 
   lldb::SBValue EvaluateExpression(const char *expr,

lldb/include/lldb/Core/FormatEntity.h

enum class Type {
       Lang,
       FrameIndex,
       FrameNoDebug,
       FrameRegisterPC,
       FrameRegisterSP,
       FrameRegisterFP,
       FrameRegisterFlags,
       FrameRegisterByName,
+      FrameIsArtificial,
       ScriptFrame,
       FunctionID,
       FunctionDidChange,
       FunctionInitialFunction,
       FunctionName,
       FunctionNameWithArgs,
       FunctionNameNoArgs,
       FunctionAddrOffset,

lldb/include/lldb/Symbol/Block.h

public:
   /// @return
   ///     A const pointer to any inlined function information, or nullptr
   ///     if this is a regular block.
   //------------------------------------------------------------------
   const InlineFunctionInfo *GetInlinedFunctionInfo() const {
     return m_inlineInfoSP.get();
   }
 
+  //------------------------------------------------------------------
+  /// Get the symbol file which contains debug info for this block's
+  /// symbol context module.
+  ///
+  /// @return A pointer to the symbol file or nullptr.
+  //------------------------------------------------------------------
+  SymbolFile *GetSymbolFile();
+
   CompilerDeclContext GetDeclContext();
 
   //------------------------------------------------------------------
   /// Get the memory cost of this object.
   ///
   /// Returns the cost of this object plus any owned objects from the ranges,
   /// variables, and inline function information.
   ///

lldb/include/lldb/Symbol/Function.h

 #define liblldb_Function_h_
 
 #include "lldb/Core/AddressRange.h"
 #include "lldb/Core/Mangled.h"
 #include "lldb/Expression/DWARFExpression.h"
 #include "lldb/Symbol/Block.h"
 #include "lldb/Symbol/Declaration.h"
 #include "lldb/Utility/UserID.h"
+#include "llvm/ADT/ArrayRef.h"
 
 namespace lldb_private {
 
 //----------------------------------------------------------------------
 /// @class FunctionInfo Function.h "lldb/Symbol/Function.h"
 /// A class that contains generic function information.
 ///
 /// This provides generic function information that gets reused between inline
private:
   //------------------------------------------------------------------
   // Member variables.
   //------------------------------------------------------------------
   Mangled m_mangled; ///< Mangled inlined function name (can be empty if there
                      ///is no mangled information).
   Declaration m_call_decl;
 };
 
+class Function;
+
+//----------------------------------------------------------------------
+/// @class CallEdge Function.h "lldb/Symbol/Function.h"
+///
+/// Represent a call made within a Function. This can be used to find a path
+/// in the call graph between two functions.
+//----------------------------------------------------------------------
+class CallEdge {
+public:
+  CallEdge(const char *mangled_name, lldb::addr_t return_pc);
+
+  CallEdge(CallEdge &&) = default;
+  CallEdge &operator=(CallEdge &&) = default;
+
+  /// Get the callee's definition.
+  ///
+  /// Note that this might lazily invoke the DWARF parser.
+  Function *GetCallee(ModuleList &images);
+
+  /// Get the load PC address of the instruction which executes after the call
+  /// returns. Returns LLDB_INVALID_ADDRESS iff this is a tail call. \p caller
+  /// is the Function containing this call, and \p target is the Target which
+  /// made the call.
+  lldb::addr_t GetReturnPCAddress(Function &caller, Target &target) const;
+
+  /// Like \ref GetReturnPCAddress, but returns an unresolved file address.
+  lldb::addr_t GetUnresolvedReturnPCAddress() const { return return_pc; }
+
+private:
+  void ParseSymbolFileAndResolve(ModuleList &images);
+
+  /// Whether or not an attempt was made to find the callee's definition.
+  bool resolved;
+
+  /// Either the callee's mangled name or its definition, discriminated by
+  /// \ref resolved.
+  union {
+    const char *mangled_name;
+    Function *def;
+  } lazy_callee;
+
+  /// An invalid address if this is a tail call. Otherwise, the return PC for
+  /// the call. Note that this is a file address which must be resolved.
+  lldb::addr_t return_pc;
+
+  DISALLOW_COPY_AND_ASSIGN(CallEdge);
+};
+
 //----------------------------------------------------------------------
 /// @class Function Function.h "lldb/Symbol/Function.h"
 /// A class that describes a function.
 ///
 /// Functions belong to CompileUnit objects (Function::m_comp_unit), have
 /// unique user IDs (Function::UserID), know how to reconstruct their symbol
 /// context (Function::SymbolContextScope), have a specific function type
 /// (Function::m_type_uid), have a simple method name (FunctionInfo::m_name),
public:
   ///     The source file.
   ///
   /// @param[out] line_no
   ///     The line number.
   //------------------------------------------------------------------
   void GetEndLineSourceInfo(FileSpec &source_file, uint32_t &line_no);
 
   //------------------------------------------------------------------
+  /// Get the outgoing call edges from this function, sorted by their return
+  /// PC addresses (in increasing order).
+  //------------------------------------------------------------------
+  llvm::MutableArrayRef<CallEdge> GetCallEdges();
+
+  //------------------------------------------------------------------
+  /// Get the outgoing tail-calling edges from this function. If none exist,
+  /// return None.
+  //------------------------------------------------------------------
+  llvm::MutableArrayRef<CallEdge> GetTailCallingEdges();
+
+  //------------------------------------------------------------------
   /// Get accessor for the block list.
   ///
   /// @return
   ///     The block list object that describes all lexical blocks
   ///     in the function.
   ///
   /// @see BlockList
   //------------------------------------------------------------------
protected:
   Block m_block;     ///< All lexical blocks contained in this function.
   AddressRange m_range; ///< The function address range that covers the widest
                         ///range needed to contain all blocks
   DWARFExpression m_frame_base; ///< The frame base expression for variables
                                 ///that are relative to the frame pointer.
   Flags m_flags;
   uint32_t
       m_prologue_byte_size; ///< Compute the prologue size once and cache it
+
+  bool m_call_edges_resolved = false; ///< Whether call site info has been
+                                      ///  parsed.
+  std::vector<CallEdge> m_call_edges; ///< Outgoing call edges.
 private:
   DISALLOW_COPY_AND_ASSIGN(Function);
 };
 
 } // namespace lldb_private
 
 #endif // liblldb_Function_h_

lldb/include/lldb/Symbol/SymbolFile.h

 //===-- SymbolFile.h --------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef liblldb_SymbolFile_h_
 #define liblldb_SymbolFile_h_
 
 #include "lldb/Core/PluginInterface.h"
 #include "lldb/Symbol/CompilerDecl.h"
 #include "lldb/Symbol/CompilerDeclContext.h"
 #include "lldb/Symbol/CompilerType.h"
+#include "lldb/Symbol/Function.h"
 #include "lldb/Symbol/Type.h"
 #include "lldb/lldb-private.h"
 
 #include "llvm/ADT/DenseSet.h"
 
 namespace lldb_private {
 
 class SymbolFile : public PluginInterface {
public:
   FindNamespace(const SymbolContext &sc, const ConstString &name,
                 const CompilerDeclContext *parent_decl_ctx) {
     return CompilerDeclContext();
   }
 
   ObjectFile *GetObjectFile() { return m_obj_file; }
   const ObjectFile *GetObjectFile() const { return m_obj_file; }
 
+  virtual std::vector<CallEdge> ParseCallEdgesInFunction(UserID func_id) {
+    return {};
+  }
+
   //------------------------------------------------------------------
   /// Notify the SymbolFile that the file addresses in the Sections
   /// for this module have been changed.
   //------------------------------------------------------------------
   virtual void SectionFileAddressesChanged() {}
 
   virtual void Dump(Stream &s) {}
 

lldb/include/lldb/Target/StackFrame.h

 
 namespace lldb_private {
 
 /// @class StackFrame StackFrame.h "lldb/Target/StackFrame.h"
 ///
 /// This base class provides an interface to stack frames.
 ///
 /// StackFrames may have a Canonical Frame Address (CFA) or not.
-/// A frame may have a plain pc value or it may have a pc value + stop_id
-/// to indicate a specific point in the debug session so the correct section
-/// load list is used for symbolication.
+/// A frame may have a plain pc value or it may  indicate a specific point in
+/// the debug session so the correct section load list is used for
+/// symbolication.
 ///
 /// Local variables may be available, or not.  A register context may be
 /// available, or not.
 
 class StackFrame : public ExecutionContextScope,
                    public std::enable_shared_from_this<StackFrame> {
 public:
   enum ExpressionPathOption {
     eExpressionPathOptionCheckPtrVsMember = (1u << 0),
     eExpressionPathOptionsNoFragileObjcIvar = (1u << 1),
     eExpressionPathOptionsNoSyntheticChildren = (1u << 2),
     eExpressionPathOptionsNoSyntheticArrayRange = (1u << 3),
     eExpressionPathOptionsAllowDirectIVarAccess = (1u << 4),
     eExpressionPathOptionsInspectAnonymousUnions = (1u << 5)
   };
 
+  enum class Kind {
+    /// A regular stack frame with access to registers and local variables.
+    Regular,
+
+    /// A historical stack frame -- possibly without CFA or registers or
+    /// local variables.
+    History,
+
+    /// An artificial stack frame (e.g a synthesized result of inferring
+    /// missing tail call frames from a backtrace) with limited support for
+    /// local variables.
+    Artificial
+  };
+
   //------------------------------------------------------------------
   /// Construct a StackFrame object without supplying a RegisterContextSP.
   ///
   /// This is the one constructor that doesn't take a RegisterContext
   /// parameter.  This ctor may be called when creating a history StackFrame;
   /// these are used if we've collected a stack trace of pc addresses at some
-  /// point in the past.  We may only have pc values.  We may have pc values
-  /// and the stop_id when the stack trace was recorded.  We may have a CFA,
+  /// point in the past.  We may only have pc values. We may have a CFA,
   /// or more likely, we won't.
   ///
   /// @param [in] thread_sp
   ///   The Thread that this frame belongs to.
   ///
   /// @param [in] frame_idx
   ///   This StackFrame's frame index number in the Thread.  If inlined stack
   ///   frames are being created, this may differ from the concrete_frame_idx
public:
   /// @param [in] cfa_is_valid
   ///   A history stack frame may not have a CFA value collected.  We want to
   ///   distinguish between "no CFA available" and a CFA of
   ///   LLDB_INVALID_ADDRESS.
   ///
   /// @param [in] pc
   ///   The current pc value of this stack frame.
   ///
-  /// @param [in] stop_id
-  ///   The stop_id which should be used when looking up symbols for the pc
-  ///   value,
-  ///   if appropriate.  This argument is ignored if stop_id_is_valid is false.
-  ///
-  /// @param [in] stop_id_is_valid
-  ///   If the stop_id argument provided is not needed for this StackFrame, this
-  ///   should be false.  If this is a history stack frame and we know the
-  ///   stop_id
-  ///   when the pc value was collected, that stop_id should be provided and
-  ///   this
-  ///   will be true.
-  ///
-  /// @param [in] is_history_frame
-  ///   If this is a historical stack frame -- possibly without CFA or registers
-  ///   or
-  ///   local variables -- then this should be set to true.
+  /// @param [in] frame_kind
   ///
   /// @param [in] sc_ptr
   ///   Optionally seed the StackFrame with the SymbolContext information that
   ///   has
   ///   already been discovered.
   //------------------------------------------------------------------
   StackFrame(const lldb::ThreadSP &thread_sp, lldb::user_id_t frame_idx,
              lldb::user_id_t concrete_frame_idx, lldb::addr_t cfa,
-             bool cfa_is_valid, lldb::addr_t pc, uint32_t stop_id,
-             bool stop_id_is_valid, bool is_history_frame,
+             bool cfa_is_valid, lldb::addr_t pc, Kind frame_kind,
              const SymbolContext *sc_ptr);
 
   StackFrame(const lldb::ThreadSP &thread_sp, lldb::user_id_t frame_idx,
              lldb::user_id_t concrete_frame_idx,
              const lldb::RegisterContextSP &reg_context_sp, lldb::addr_t cfa,
              lldb::addr_t pc, const SymbolContext *sc_ptr);
 
   StackFrame(const lldb::ThreadSP &thread_sp, lldb::user_id_t frame_idx,
public:
   /// the debugger.
   ///
   /// @return
   ///   true if this is an inlined frame.
   //------------------------------------------------------------------
   bool IsInlined();
 
   //------------------------------------------------------------------
+  /// Query whether this frame is part of a historical backtrace.
+  //------------------------------------------------------------------
+  bool IsHistorical() const;
+
+  //------------------------------------------------------------------
+  /// Query whether this frame is artificial (e.g a synthesized result of
+  /// inferring missing tail call frames from a backtrace). Artificial frames
+  /// may have limited support for inspecting variables.
+  //------------------------------------------------------------------
+  bool IsArtificial() const;
+
+  //------------------------------------------------------------------
   /// Query this frame to find what frame it is in this Thread's
   /// StackFrameList.
   ///
   /// @return
   ///   StackFrame index 0 indicates the currently-executing function.  Inline
   ///   frames are included in this frame index count.
   //------------------------------------------------------------------
   uint32_t GetFrameIndex() const;
 
   //------------------------------------------------------------------
+  /// Set this frame's synthetic frame index.
+  //------------------------------------------------------------------
+  void SetFrameIndex(uint32_t index) { m_frame_index = index; }
+
+  //------------------------------------------------------------------
   /// Query this frame to find what frame it is in this Thread's
   /// StackFrameList, not counting inlined frames.
   ///
   /// @return
   ///   StackFrame index 0 indicates the currently-executing function.  Inline
   ///   frames are not included in this frame index count; their concrete
   ///   frame index will be the same as the concrete frame that they are
   ///   derived from.
Address m_frame_code_addr; // The frame code address (might not be the same as
                              // the actual PC for inlined frames) as a
                              // section/offset address
   SymbolContext m_sc;
   Flags m_flags;
   Scalar m_frame_base;
   Status m_frame_base_error;
   bool m_cfa_is_valid; // Does this frame have a CFA?  Different from CFA ==
                        // LLDB_INVALID_ADDRESS
-  uint32_t m_stop_id;
-  bool m_stop_id_is_valid; // Does this frame have a stop_id?  Use it when
-                           // referring to the m_frame_code_addr.
-  bool m_is_history_frame;
+  Kind m_stack_frame_kind;
   lldb::VariableListSP m_variable_list_sp;
   ValueObjectList m_variable_list_value_objects; // Value objects for each
                                                  // variable in
                                                  // m_variable_list_sp
   StreamString m_disassembly;
   std::recursive_mutex m_mutex;
 
   DISALLOW_COPY_AND_ASSIGN(StackFrame);
 };
 
 } // namespace lldb_private
 
 #endif // liblldb_StackFrame_h_

lldb/include/lldb/Target/StackFrameList.h

protected:
 
   static void Merge(std::unique_ptr<StackFrameList> &curr_ap,
                     lldb::StackFrameListSP &prev_sp);
 
   void GetFramesUpTo(uint32_t end_idx);
 
   void GetOnlyConcreteFramesUpTo(uint32_t end_idx, Unwind *unwinder);
 
+  void SynthesizeTailCallFrames(StackFrame &next_frame);
+
   bool GetAllFramesFetched() { return m_concrete_frames_fetched == UINT32_MAX; }
 
   void SetAllFramesFetched() { m_concrete_frames_fetched = UINT32_MAX; }
 
   bool DecrementCurrentInlinedDepth();
 
   void ResetCurrentInlinedDepth();
 

lldb/packages/Python/lldbsuite/test/decorators.py

def compiler_doesnt_support_struct_attribute(self):
         cmd = [self.getCompiler(), "-x", "c++", "-c", "-o", f.name, "-"]
         p = subprocess.Popen(cmd, stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.PIPE, universal_newlines=True)
         stdout, stderr = p.communicate('struct __attribute__((%s)) Test {};'%attr)
         if attr in stderr:
             return "Compiler does not support attribute %s"%(attr)
         return None
     return skipTestIfFn(compiler_doesnt_support_struct_attribute)
 
+def skipUnlessHasCallSiteInfo(func):
+    """Decorate the function to skip testing unless call site info from clang is available."""
+
+    def is_compiler_clang_with_call_site_info(self):
+        compiler_path = self.getCompiler()
+        compiler = os.path.basename(compiler_path)
+        if not compiler.startswith("clang"):
+            return "Test requires clang as compiler"
+
+        f = tempfile.NamedTemporaryFile()
+        cmd = "echo 'int main() {}' | " \
+              "%s -g -glldb -O1 -S -emit-llvm -x c -o %s -" % (compiler_path, f.name)
+        if os.popen(cmd).close() is not None:
+            return "Compiler can't compile with call site info enabled"
+
+        with open(f.name, 'r') as ir_output_file:
+            buf = ir_output_file.read()
+
+        if 'DIFlagAllCallsDescribed' not in buf:
+            return "Compiler did not introduce DIFlagAllCallsDescribed IR flag"
+
+        return None
+    return skipTestIfFn(is_compiler_clang_with_call_site_info)(func)
+
 def skipUnlessThreadSanitizer(func):
     """Decorate the item to skip test unless Clang -fsanitize=thread is supported."""
 
     def is_compiler_clang_with_thread_sanitizer(self):
         compiler_path = self.getCompiler()
         compiler = os.path.basename(compiler_path)
         if not compiler.startswith("clang"):
             return "Test requires clang as compiler"

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq1/Makefile

+LEVEL = ../../../make
+CXX_SOURCES := main.cpp
+include $(LEVEL)/Makefile.rules
+CXXFLAGS += -g -O1 -glldb

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq1/TestAmbiguousTailCallSeq1.py

+from lldbsuite.test import lldbinline
+from lldbsuite.test import decorators
+
+lldbinline.MakeInlineTest(__file__, globals(),
+        [decorators.skipUnlessHasCallSiteInfo])

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq1/main.cpp

+//===-- main.cpp ------------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+volatile int x;
+
+void __attribute__((noinline)) sink() {
+  x++; //% self.filecheck("bt", "main.cpp", "-implicit-check-not=func{{[23]}}_amb")
+}
+
+void __attribute__((noinline)) func3_amb() { sink(); /* tail */ }
+
+void __attribute__((noinline)) func2_amb() { sink(); /* tail */ }
+
+void __attribute__((noinline)) func1() {
+  if (x > 0)
+    func2_amb(); /* tail */
+  else
+    func3_amb(); /* tail */
+}
+
+int __attribute__((disable_tail_calls)) main(int argc, char **) {
+  // The sequences `main -> func1 -> f{2,3}_amb -> sink` are both plausible. Test
+  // that lldb doesn't attempt to guess which one occurred.
+  func1();
+  return 0;
+}

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq2/Makefile

+LEVEL = ../../../make
+CXX_SOURCES := main.cpp
+include $(LEVEL)/Makefile.rules
+CXXFLAGS += -g -O1 -glldb

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq2/TestAmbiguousTailCallSeq2.py

+from lldbsuite.test import lldbinline
+from lldbsuite.test import decorators
+
+lldbinline.MakeInlineTest(__file__, globals(),
+        [decorators.skipUnlessHasCallSiteInfo])

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq2/main.cpp

+//===-- main.cpp ------------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+volatile int x;
+
+void __attribute__((noinline)) sink() {
+  x++; //% self.filecheck("bt", "main.cpp", "-implicit-check-not=func{{[23]}}")
+}
+
+void func2();
+
+void __attribute__((noinline)) func1() {
+  if (x < 1)
+    func2();
+  else
+    sink();
+}
+
+void __attribute__((noinline)) func2() {
+  if (x < 1)
+    sink();
+  else
+    func1();
+}
+
+int main() {
+  // Tail recursion creates ambiguous execution histories.
+  x = 0;
+  func1();
+  return 0;
+}

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_call_site/Makefile

+LEVEL = ../../../make
+CXX_SOURCES := main.cpp
+include $(LEVEL)/Makefile.rules
+CXXFLAGS += -g -O1 -glldb

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_call_site/TestDisambiguateCallSite.py

+from lldbsuite.test import lldbinline
+from lldbsuite.test import decorators
+
+lldbinline.MakeInlineTest(__file__, globals(),
+        [decorators.skipUnlessHasCallSiteInfo])

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_call_site/main.cpp

+//===-- main.cpp ------------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+volatile int x;
+
+void __attribute__((noinline)) sink() {
+  x++; //% self.filecheck("bt", "main.cpp", "-implicit-check-not=artificial")
+  // CHECK: frame #0: 0x{{[0-9a-f]+}} a.out`sink() at main.cpp:[[@LINE-1]]:4 [opt]
+  // CHECK-NEXT: frame #1: 0x{{[0-9a-f]+}} a.out`func2{{.*}} [opt] [artificial]
+  // CHECK-NEXT: frame #2: 0x{{[0-9a-f]+}} a.out`main{{.*}} [opt]
+}
+
+void __attribute__((noinline)) func2() {
+  sink(); /* tail */
+}
+
+void __attribute__((noinline)) func1() { sink(); /* tail */ }
+
+int __attribute__((disable_tail_calls)) main(int argc, char **) {
+  // The sequences `main -> f{1,2} -> sink` are both plausible. Test that
+  // return-pc call site info allows lldb to pick the correct sequence.
+  func2();
+  if (argc == 100)
+    func1();
+  return 0;
+}

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_tail_call_seq/Makefile

+LEVEL = ../../../make
+CXX_SOURCES := main.cpp
+include $(LEVEL)/Makefile.rules
+CXXFLAGS += -g -O1 -glldb

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_tail_call_seq/TestDisambiguateTailCallSeq.py

+from lldbsuite.test import lldbinline
+from lldbsuite.test import decorators
+
+lldbinline.MakeInlineTest(__file__, globals(),
+        [decorators.skipUnlessHasCallSiteInfo])

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_tail_call_seq/main.cpp

+//===-- main.cpp ------------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+volatile int x;
+
+void __attribute__((noinline)) sink() {
+  x++; //% self.filecheck("bt", "main.cpp", "-implicit-check-not=artificial")
+  // CHECK: frame #0: 0x{{[0-9a-f]+}} a.out`sink() at main.cpp:[[@LINE-1]]:4 [opt]
+  // CHECK-NEXT: frame #1: 0x{{[0-9a-f]+}} a.out`func3{{.*}} [opt] [artificial]
+  // CHECK-NEXT: frame #2: 0x{{[0-9a-f]+}} a.out`func1{{.*}} [opt] [artificial]
+  // CHECK-NEXT: frame #3: 0x{{[0-9a-f]+}} a.out`main{{.*}} [opt]
+}
+
+void __attribute__((noinline)) func3() { sink(); /* tail */ }
+
+void __attribute__((noinline)) func2() { sink(); /* tail */ }
+
+void __attribute__((noinline)) func1() { func3(); /* tail */ }
+
+int __attribute__((disable_tail_calls)) main(int argc, char **) {
+  // The sequences `main -> func1 -> f{2,3} -> sink` are both plausible. Test
+  // that lldb picks the latter sequence.
+  func1();
+  return 0;
+}

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/sbapi_support/Makefile

+LEVEL = ../../../make
+CXX_SOURCES := main.cpp
+include $(LEVEL)/Makefile.rules
+CXXFLAGS += -g -O1 -glldb

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/sbapi_support/TestTailCallFrameSBAPI.py

+"""
+Test SB API support for identifying artificial (tail call) frames.
+"""
+
+import lldb
+import lldbsuite.test.lldbutil as lldbutil
+from lldbsuite.test.lldbtest import *
+
+class TestTailCallFrameSBAPI(TestBase):
+    mydir = TestBase.compute_mydir(__file__)
+
+    # If your test case doesn't stress debug info, the
+    # set this to true.  That way it won't be run once for
+    # each debug info format.
+    NO_DEBUG_INFO_TESTCASE = True
+
+    def test_tail_call_frame_sbapi(self):
+        self.build()
+        self.do_test()
+
+    def setUp(self):
+        # Call super's setUp().
+        TestBase.setUp(self)
+
+    def do_test(self):
+        exe = self.getBuildArtifact("a.out")
+
+        # Create a target by the debugger.
+        target = self.dbg.CreateTarget(exe)
+        self.assertTrue(target, VALID_TARGET)
+
+        breakpoint = target.BreakpointCreateBySourceRegex("break here",
+                lldb.SBFileSpec("main.cpp"))
+        self.assertTrue(breakpoint and
+                        breakpoint.GetNumLocations() == 1,
+                        VALID_BREAKPOINT)
+
+        error = lldb.SBError()
+        launch_info = lldb.SBLaunchInfo(None)
+        process = target.Launch(launch_info, error)
+        self.assertTrue(process, PROCESS_IS_VALID)
+
+        # Did we hit our breakpoint?
+        threads = lldbutil.get_threads_stopped_at_breakpoint(process,
+                breakpoint)
+        self.assertTrue(
+            len(threads) == 1,
+            "There should be a thread stopped at our breakpoint")
+
+        self.assertTrue(breakpoint.GetHitCount() == 1)
+
+        thread = threads[0]
+
+        # Here's what we expect to see in the backtrace:
+        #   frame #0: ... a.out`sink() at main.cpp:13:4 [opt]
+        #   frame #1: ... a.out`func3() at main.cpp:14:1 [opt] [artificial]
+        #   frame #2: ... a.out`func2() at main.cpp:18:62 [opt]
+        #   frame #3: ... a.out`func1() at main.cpp:18:85 [opt] [artificial]
+        #   frame #4: ... a.out`main at main.cpp:23:3 [opt]
+        names = ["sink()", "func3()", "func2()", "func1()", "main"]
+        artificiality = [False, True, False, True, False]
+        for idx, (name, is_artificial) in enumerate(zip(names, artificiality)):
+            frame = thread.GetFrameAtIndex(idx)
+            self.assertTrue(frame.GetDisplayFunctionName() == name)
+            self.assertTrue(frame.IsArtificial() == is_artificial)

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/sbapi_support/main.cpp

+//===-- main.cpp ------------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+volatile int x;
+
+void __attribute__((noinline)) sink() {
+  x++; /* break here */
+}
+
+void __attribute__((noinline)) func3() { sink(); /* tail */ }
+
+void __attribute__((disable_tail_calls, noinline)) func2() { func3(); /* regular */ }
+
+void __attribute__((noinline)) func1() { func2(); /* tail */ }
+
+int __attribute__((disable_tail_calls)) main() {
+  func1(); /* regular */
+  return 0;
+}

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/thread_step_out_or_return/Makefile

+LEVEL = ../../../make
+CXX_SOURCES := main.cpp
+include $(LEVEL)/Makefile.rules
+CXXFLAGS += -g -O1 -glldb

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/thread_step_out_or_return/TestSteppingOutWithArtificialFrames.py

+"""
+Test SB API support for identifying artificial (tail call) frames.
+"""
+
+import lldb
+import lldbsuite.test.lldbutil as lldbutil
+from lldbsuite.test.lldbtest import *
+
+class TestArtificialFrameThreadStepOut1(TestBase):
+    mydir = TestBase.compute_mydir(__file__)
+
+    # If your test case doesn't stress debug info, the
+    # set this to true.  That way it won't be run once for
+    # each debug info format.
+    NO_DEBUG_INFO_TESTCASE = True
+
+    def prepare_thread(self):
+        exe = self.getBuildArtifact("a.out")
+
+        # Create a target by the debugger.
+        target = self.dbg.CreateTarget(exe)
+        self.assertTrue(target, VALID_TARGET)
+
+        breakpoint = target.BreakpointCreateBySourceRegex("break here",
+                lldb.SBFileSpec("main.cpp"))
+        self.assertTrue(breakpoint and
+                        breakpoint.GetNumLocations() == 1,
+                        VALID_BREAKPOINT)
+
+        error = lldb.SBError()
+        launch_info = lldb.SBLaunchInfo(None)
+        process = target.Launch(launch_info, error)
+        self.assertTrue(process, PROCESS_IS_VALID)
+
+        # Did we hit our breakpoint?
+        threads = lldbutil.get_threads_stopped_at_breakpoint(process,
+                breakpoint)
+        self.assertTrue(
+            len(threads) == 1,
+            "There should be a thread stopped at our breakpoint")
+
+        self.assertTrue(breakpoint.GetHitCount() == 1)
+
+        thread = threads[0]
+
+        # Here's what we expect to see in the backtrace:
+        #   frame #0: ... a.out`sink() at main.cpp:13:4 [opt]
+        #   frame #1: ... a.out`func3() at main.cpp:14:1 [opt] [artificial]
+        #   frame #2: ... a.out`func2() at main.cpp:18:62 [opt]
+        #   frame #3: ... a.out`func1() at main.cpp:18:85 [opt] [artificial]
+        #   frame #4: ... a.out`main at main.cpp:23:3 [opt]
+        return thread
+
+    def test_stepping_out_past_artificial_frame(self):
+        self.build()
+        thread = self.prepare_thread()
+
+        # Frame #0's ancestor is artificial. Stepping out should move to
+        # frame #2, because we behave as-if artificial frames were not present.
+        thread.StepOut()
+        frame2 = thread.GetSelectedFrame()
+        self.assertTrue(frame2.GetDisplayFunctionName() == "func2()")
+        self.assertFalse(frame2.IsArtificial())
+
+        # Ditto: stepping out of frame #2 should move to frame #4.
+        thread.StepOut()
+        frame4 = thread.GetSelectedFrame()
+        self.assertTrue(frame4.GetDisplayFunctionName() == "main")
+        self.assertFalse(frame2.IsArtificial())
+
+    def test_return_past_artificial_frame(self):
+        self.build()
+        thread = self.prepare_thread()
+
+        value = lldb.SBValue()
+
+        # Frame #0's ancestor is artificial. Returning from frame #0 should move
+        # to frame #2.
+        thread.ReturnFromFrame(thread.GetSelectedFrame(), value)
+        frame2 = thread.GetSelectedFrame()
+        self.assertTrue(frame2.GetDisplayFunctionName() == "func2()")
+        self.assertFalse(frame2.IsArtificial())
+
+        # Ditto: stepping out of frame #2 should move to frame #4.
+        thread.ReturnFromFrame(thread.GetSelectedFrame(), value)
+        frame4 = thread.GetSelectedFrame()
+        self.assertTrue(frame4.GetDisplayFunctionName() == "main")
+        self.assertFalse(frame2.IsArtificial())
+
+    def setUp(self):
+        # Call super's setUp().
+        TestBase.setUp(self)

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/thread_step_out_or_return/main.cpp

+//===-- main.cpp ------------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+volatile int x;
+
+void __attribute__((noinline)) sink() {
+  x++; // break here
+}
+
+void __attribute__((noinline)) func3() { sink(); /* tail */ }
+
+void __attribute__((disable_tail_calls, noinline)) func2() { func3(); /* regular */ }
+
+void __attribute__((noinline)) func1() { func2(); /* tail */ }
+
+int __attribute__((disable_tail_calls)) main() {
+  func1(); /* regular */
+  return 0;
+}

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/unambiguous_sequence/Makefile

+LEVEL = ../../../make
+CXX_SOURCES := main.cpp
+include $(LEVEL)/Makefile.rules
+CXXFLAGS += -g -O1 -glldb

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/unambiguous_sequence/TestUnambiguousTailCalls.py

+from lldbsuite.test import lldbinline
+from lldbsuite.test import decorators
+
+lldbinline.MakeInlineTest(__file__, globals(),
+        [decorators.skipUnlessHasCallSiteInfo])

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/unambiguous_sequence/main.cpp

+//===-- main.cpp ------------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+volatile int x;
+
+void __attribute__((noinline)) sink() {
+  x++; //% self.filecheck("bt", "main.cpp", "-implicit-check-not=artificial")
+  // CHECK: frame #0: 0x{{[0-9a-f]+}} a.out`sink() at main.cpp:[[@LINE-1]]:4 [opt]
+  // CHECK-NEXT: frame #1: 0x{{[0-9a-f]+}} a.out`func3{{.*}} [opt] [artificial]
+  // CHECK-NEXT: frame #2: 0x{{[0-9a-f]+}} a.out`func2{{.*}} [opt]
+  // CHECK-NEXT: frame #3: 0x{{[0-9a-f]+}} a.out`func1{{.*}} [opt] [artificial]
+  // CHECK-NEXT: frame #4: 0x{{[0-9a-f]+}} a.out`main{{.*}} [opt]
+}
+
+void __attribute__((noinline)) func3() { sink(); /* tail */ }
+
+void __attribute__((disable_tail_calls, noinline)) func2() { func3(); /* regular */ }
+
+void __attribute__((noinline)) func1() { func2(); /* tail */ }
+
+int __attribute__((disable_tail_calls)) main() {
+  func1(); /* regular */
+  return 0;
+}

lldb/scripts/interface/SBFrame.i

~SBFrame();
     ") IsInlined;
     bool
     IsInlined();
 
     bool
     IsInlined() const;
 
     %feature("docstring", "
+    /// Return true if this frame is artificial (e.g a frame synthesized to
+    /// capture a tail call). Local variables may not be available in an artificial
+    /// frame.
+    ") IsArtificial;
+    bool
+    IsArtificial();
+
+    bool
+    IsArtificial() const;
+
+    %feature("docstring", "
     /// The version that doesn't supply a 'use_dynamic' value will use the
     /// target's default.
     ") EvaluateExpression;
     lldb::SBValue
     EvaluateExpression (const char *expr);    
 
     lldb::SBValue
     EvaluateExpression (const char *expr, lldb::DynamicValueType use_dynamic);

lldb/source/API/SBFrame.cpp

if (target && process) {
     } else {
       if (log)
         log->Printf("SBFrame::IsInlined () => error: process is running");
     }
   }
   return false;
 }
 
+bool SBFrame::IsArtificial() {
+  return static_cast<const SBFrame *>(this)->IsArtificial();
+}
+
+bool SBFrame::IsArtificial() const {
+  std::unique_lock<std::recursive_mutex> lock;
+  ExecutionContext exe_ctx(m_opaque_sp.get(), lock);
+
+  StackFrame *frame = exe_ctx.GetFramePtr();
+  if (frame)
+    return frame->IsArtificial();
+
+  return false;
+}
+
 const char *SBFrame::GetFunctionName() {
   return static_cast<const SBFrame *>(this)->GetFunctionName();
 }
 
 lldb::LanguageType SBFrame::GuessLanguage() const {
   std::unique_lock<std::recursive_mutex> lock;
   ExecutionContext exe_ctx(m_opaque_sp.get(), lock);
   

lldb/source/Core/Debugger.cpp

#define MODULE_WITH_FUNC_NO_ARGS                                               \
   "{ "                                                                         \
   "${module.file.basename}{`${function.name-without-args}"                     \
   "{${frame.no-debug}${function.pc-offset}}}}"
 
 #define FILE_AND_LINE                                                          \
   "{ at ${line.file.basename}:${line.number}{:${line.column}}}"
 #define IS_OPTIMIZED "{${function.is-optimized} [opt]}"
 
+#define IS_ARTIFICIAL "{${frame.is-artificial} [artificial]}"
+
 #define DEFAULT_THREAD_FORMAT                                                  \
   "thread #${thread.index}: tid = ${thread.id%tid}"                            \
   "{, ${frame.pc}}" MODULE_WITH_FUNC FILE_AND_LINE                             \
   "{, name = '${thread.name}'}"                                                \
   "{, queue = '${thread.queue}'}"                                              \
   "{, activity = '${thread.info.activity.name}'}"                              \
   "{, ${thread.info.trace_messages} messages}"                                 \
   "{, stop reason = ${thread.stop-reason}}"                                    \
   "{\\nReturn value: ${thread.return-value}}"                                  \
   "{\\nCompleted expression: ${thread.completed-expression}}"                  \
   "\\n"
 
 #define DEFAULT_THREAD_STOP_FORMAT                                             \
   "thread #${thread.index}{, name = '${thread.name}'}"                         \
   "{, queue = '${thread.queue}'}"                                              \
   "{, activity = '${thread.info.activity.name}'}"                              \
   "{, ${thread.info.trace_messages} messages}"                                 \
   "{, stop reason = ${thread.stop-reason}}"                                    \
   "{\\nReturn value: ${thread.return-value}}"                                  \
   "{\\nCompleted expression: ${thread.completed-expression}}"                  \
   "\\n"
 
 #define DEFAULT_FRAME_FORMAT                                                   \
   "frame #${frame.index}: ${frame.pc}" MODULE_WITH_FUNC FILE_AND_LINE          \
-      IS_OPTIMIZED "\\n"
+      IS_OPTIMIZED IS_ARTIFICIAL "\\n"
 
 #define DEFAULT_FRAME_FORMAT_NO_ARGS                                           \
   "frame #${frame.index}: ${frame.pc}" MODULE_WITH_FUNC_NO_ARGS FILE_AND_LINE  \
-      IS_OPTIMIZED "\\n"
+      IS_OPTIMIZED IS_ARTIFICIAL "\\n"
 
 // Three parts to this disassembly format specification:
 //   1. If this is a new function/symbol (no previous symbol/function), print
 //      dylib`funcname:\n
 //   2. If this is a symbol context change (different from previous
 //   symbol/function), print
 //      dylib`funcname:\n
 //   3. print

lldb/source/Core/FormatEntity.cpp

 static FormatEntity::Entry::Definition g_frame_child_entries[] = {
     ENTRY("index", FrameIndex, UInt32),
     ENTRY("pc", FrameRegisterPC, UInt64),
     ENTRY("fp", FrameRegisterFP, UInt64),
     ENTRY("sp", FrameRegisterSP, UInt64),
     ENTRY("flags", FrameRegisterFlags, UInt64),
     ENTRY("no-debug", FrameNoDebug, None),
     ENTRY_CHILDREN("reg", FrameRegisterByName, UInt64, g_string_entry),
+    ENTRY("is-artificial", FrameIsArtificial, UInt32),
 };
 
 static FormatEntity::Entry::Definition g_function_child_entries[] = {
     ENTRY("id", FunctionID, UInt64), ENTRY("name", FunctionName, CString),
     ENTRY("name-without-args", FunctionNameNoArgs, CString),
     ENTRY("name-with-args", FunctionNameWithArgs, CString),
     ENTRY("addr-offset", FunctionAddrOffset, UInt64),
     ENTRY("concrete-only-addr-offset-no-padding", FunctionAddrOffsetConcrete,
switch (t) {
     ENUM_TO_CSTR(Lang);
     ENUM_TO_CSTR(FrameIndex);
     ENUM_TO_CSTR(FrameNoDebug);
     ENUM_TO_CSTR(FrameRegisterPC);
     ENUM_TO_CSTR(FrameRegisterSP);
     ENUM_TO_CSTR(FrameRegisterFP);
     ENUM_TO_CSTR(FrameRegisterFlags);
     ENUM_TO_CSTR(FrameRegisterByName);
+    ENUM_TO_CSTR(FrameIsArtificial);
     ENUM_TO_CSTR(ScriptFrame);
     ENUM_TO_CSTR(FunctionID);
     ENUM_TO_CSTR(FunctionDidChange);
     ENUM_TO_CSTR(FunctionInitialFunction);
     ENUM_TO_CSTR(FunctionName);
     ENUM_TO_CSTR(FunctionNameWithArgs);
     ENUM_TO_CSTR(FunctionNameNoArgs);
     ENUM_TO_CSTR(FunctionAddrOffset);
if (exe_ctx) {
       if (frame) {
         if (DumpRegister(s, frame, entry.string.c_str(),
                          (lldb::Format)entry.number))
           return true;
       }
     }
     return false;
 
+  case Entry::Type::FrameIsArtificial: {
+    if (exe_ctx)
+      if (StackFrame *frame = exe_ctx->GetFramePtr())
+        return frame->IsArtificial();
+    return false;
+  }
+
   case Entry::Type::ScriptFrame:
     if (exe_ctx) {
       StackFrame *frame = exe_ctx->GetFramePtr();
       if (frame)
         return RunScriptFormatKeyword(s, sc, exe_ctx, frame,
                                       entry.string.c_str());
     }
     return false;

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h

public:
   // for the instances of the subclass SymbolFileDWARFDwo
   // the method returns a pointer to the base compile unit.
   virtual DWARFUnit *GetBaseCompileUnit();
 
   static bool
   DIEInDeclContext(const lldb_private::CompilerDeclContext *parent_decl_ctx,
                    const DWARFDIE &die);
 
+  std::vector<lldb_private::CallEdge>
+  ParseCallEdgesInFunction(UserID func_id) override;
+
   void Dump(lldb_private::Stream &s) override;
 
 protected:
   typedef llvm::DenseMap<const DWARFDebugInfoEntry *, lldb_private::Type *>
       DIEToTypePtr;
   typedef llvm::DenseMap<const DWARFDebugInfoEntry *, lldb::VariableSP>
       DIEToVariableSP;
   typedef llvm::DenseMap<const DWARFDebugInfoEntry *,

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

while (die) {
     if (parse_siblings)
       die = die.GetSibling();
     else
       die.Clear();
   }
   return vars_added;
 }
 
+/// Collect call graph edges present in a function DIE.
+static std::vector<lldb_private::CallEdge>
+CollectCallEdges(DWARFDIE function_die) {
+  // Check if the function has a supported call site-related attribute.
+  // TODO: In the future it may be worthwhile to support call_all_source_calls.
+  uint64_t has_call_edges =
+      function_die.GetAttributeValueAsUnsigned(DW_AT_call_all_calls, 0);
+  if (!has_call_edges)
+    return {};
+
+  Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_STEP));
+  LLDB_LOG(log, "CollectCallEdges: Found call site info in {0}",
+           function_die.GetPubname());
+
+  // Scan the DIE for TAG_call_site entries.
+  // TODO: A recursive scan of all blocks in the subprogram is needed in order
+  // to be DWARF5-compliant. This may need to be done lazily to be performant.
+  // For now, assume that all entries are nested directly under the subprogram
+  // (this is the kind of DWARF LLVM produces) and parse them eagerly.
+  std::vector<CallEdge> call_edges;
+  for (DWARFDIE child = function_die.GetFirstChild(); child.IsValid();
+       child = child.GetSibling()) {
+    if (child.Tag() != DW_TAG_call_site)
+      continue;
+
+    // Extract DW_AT_call_origin (the call target's DIE).
+    DWARFDIE call_origin = child.GetReferencedDIE(DW_AT_call_origin);
+    if (!call_origin.IsValid()) {
+      LLDB_LOG(log, "CollectCallEdges: Invalid call origin in {0}",
+               function_die.GetPubname());
+      continue;
+    }
+
+    // Extract DW_AT_call_return_pc (the PC the call returns to) if it's
+    // available.
+    addr_t return_pc = child.GetAttributeValueAsAddress(DW_AT_call_return_pc,
+                                                        LLDB_INVALID_ADDRESS);
+
+    LLDB_LOG(log, "CollectCallEdges: Found call origin: {0} (return PC = {1})",
+             call_origin.GetPubname(), return_pc);
+    call_edges.emplace_back(call_origin.GetMangledName(), return_pc);
+  }
+  return call_edges;
+}
+
+std::vector<lldb_private::CallEdge>
+SymbolFileDWARF::ParseCallEdgesInFunction(UserID func_id) {
+  DWARFDIE func_die = GetDIEFromUID(func_id.GetID());
+  if (func_die.IsValid())
+    return CollectCallEdges(func_die);
+  return {};
+}
+
 //------------------------------------------------------------------
 // PluginInterface protocol
 //------------------------------------------------------------------
 ConstString SymbolFileDWARF::GetPluginName() { return GetPluginNameStatic(); }
 
 uint32_t SymbolFileDWARF::GetPluginVersion() { return 1; }
 
 void SymbolFileDWARF::Dump(lldb_private::Stream &s) { m_index->Dump(s); }

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h

FindTypes(const lldb_private::SymbolContext &sc,
             lldb_private::TypeMap &types) override;
   lldb_private::CompilerDeclContext FindNamespace(
       const lldb_private::SymbolContext &sc,
       const lldb_private::ConstString &name,
       const lldb_private::CompilerDeclContext *parent_decl_ctx) override;
   size_t GetTypes(lldb_private::SymbolContextScope *sc_scope,
                   uint32_t type_mask,
                   lldb_private::TypeList &type_list) override;
+  std::vector<lldb_private::CallEdge>
+  ParseCallEdgesInFunction(lldb_private::UserID func_id) override;
 
   //------------------------------------------------------------------
   // PluginInterface protocol
   //------------------------------------------------------------------
   lldb_private::ConstString GetPluginName() override;
 
   uint32_t GetPluginVersion() override;
 

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp

if (sc_scope) {
     ForEachSymbolFile([&](SymbolFileDWARF *oso_dwarf) -> bool {
       oso_dwarf->GetTypes(sc_scope, type_mask, type_list);
       return false;
     });
   }
   return type_list.GetSize() - initial_size;
 }
 
+std::vector<lldb_private::CallEdge>
+SymbolFileDWARFDebugMap::ParseCallEdgesInFunction(UserID func_id) {
+  uint32_t oso_idx = GetOSOIndexFromUserID(func_id.GetID());
+  SymbolFileDWARF *oso_dwarf = GetSymbolFileByOSOIndex(oso_idx);
+  if (oso_dwarf)
+    return oso_dwarf->ParseCallEdgesInFunction(func_id);
+  return {};
+}
+
 TypeSP SymbolFileDWARFDebugMap::FindDefinitionTypeForDWARFDeclContext(
     const DWARFDeclContext &die_decl_ctx) {
   TypeSP type_sp;
   ForEachSymbolFile([&](SymbolFileDWARF *oso_dwarf) -> bool {
     type_sp = oso_dwarf->FindDefinitionTypeForDWARFDeclContext(die_decl_ctx);
     return ((bool)type_sp);
   });
   return type_sp;

lldb/source/Symbol/Block.cpp

if (get_parent_variables) {
     if (parent_block)
       num_variables_added += parent_block->AppendVariables(
           can_create, get_parent_variables, stop_if_block_is_inlined_function,
           filter, variable_list);
   }
   return num_variables_added;
 }
 
-CompilerDeclContext Block::GetDeclContext() {
-  ModuleSP module_sp = CalculateSymbolContextModule();
-
-  if (module_sp) {
-    SymbolVendor *sym_vendor = module_sp->GetSymbolVendor();
-
-    if (sym_vendor) {
-      SymbolFile *sym_file = sym_vendor->GetSymbolFile();
+SymbolFile *Block::GetSymbolFile() {
+  if (ModuleSP module_sp = CalculateSymbolContextModule())
+    if (SymbolVendor *sym_vendor = module_sp->GetSymbolVendor())
+      return sym_vendor->GetSymbolFile();
+  return nullptr;
+}
 
-      if (sym_file)
-        return sym_file->GetDeclContextForUID(GetID());
-    }
-  }
+CompilerDeclContext Block::GetDeclContext() {
+  if (SymbolFile *sym_file = GetSymbolFile())
   return CompilerDeclContext();
 }
 
 void Block::SetBlockInfoHasBeenParsed(bool b, bool set_children) {
   m_parsed_block_info = b;
   if (set_children) {
     m_parsed_child_blocks = true;
     collection::const_iterator pos, end = m_children.end();

lldb/source/Symbol/Function.cpp

 //===-- Function.cpp --------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "lldb/Symbol/Function.h"
 #include "lldb/Core/Disassembler.h"
 #include "lldb/Core/Module.h"
+#include "lldb/Core/ModuleList.h"
 #include "lldb/Core/Section.h"
 #include "lldb/Host/Host.h"
 #include "lldb/Symbol/CompileUnit.h"
 #include "lldb/Symbol/CompilerType.h"
 #include "lldb/Symbol/LineTable.h"
 #include "lldb/Symbol/SymbolFile.h"
 #include "lldb/Symbol/SymbolVendor.h"
 #include "lldb/Target/Language.h"
+#include "lldb/Utility/Log.h"
 #include "llvm/Support/Casting.h"
 
 using namespace lldb;
 using namespace lldb_private;
 
 //----------------------------------------------------------------------
 // Basic function information is contained in the FunctionInfo class. It is
 // designed to contain the name, linkage name, and declaration location.

 
 size_t InlineFunctionInfo::MemorySize() const {
   return FunctionInfo::MemorySize() + m_mangled.MemorySize();
 }
 
 //----------------------------------------------------------------------
 //
 //----------------------------------------------------------------------
+CallEdge::CallEdge(const char *mangled_name, lldb::addr_t return_pc)
+    : resolved(false), return_pc(return_pc) {
+  lazy_callee.mangled_name = mangled_name;
+}
+
+void CallEdge::ParseSymbolFileAndResolve(ModuleList &images) {
+  if (resolved)
+    return;
+
+  Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_STEP));
+  LLDB_LOG(log, "CallEdge: Lazily parsing the call graph for {0}",
+           lazy_callee.mangled_name);
+
+  auto resolve_lazy_callee = [&]() -> Function * {
+    ConstString callee_name{lazy_callee.mangled_name};
+    SymbolContextList sc_list;
+    size_t num_matches =
+        images.FindFunctionSymbols(callee_name, eFunctionNameTypeAuto, sc_list);
+    if (num_matches != 1 || !sc_list[0].symbol) {
+      LLDB_LOG(log, "CallEdge: Found {0} symbols for {1}, cannot resolve it",
+               num_matches, callee_name);
+      return nullptr;
+    }
+    Address callee_addr = sc_list[0].symbol->GetAddress();
+    if (!callee_addr.IsValid()) {
+      LLDB_LOG(log, "CallEdge: Invalid symbol address");
+      return nullptr;
+    }
+    Function *f = callee_addr.CalculateSymbolContextFunction();
+    if (!f) {
+      LLDB_LOG(log, "CallEdge: Could not find complete function");
+      return nullptr;
+    }
+    return f;
+  };
+  lazy_callee.def = resolve_lazy_callee();
+  resolved = true;
+}
+
+Function *CallEdge::GetCallee(ModuleList &images) {
+  ParseSymbolFileAndResolve(images);
+  return lazy_callee.def;
+}
+
+lldb::addr_t CallEdge::GetReturnPCAddress(Function &caller,
+                                          Target &target) const {
+  const Address &base = caller.GetAddressRange().GetBaseAddress();
+  Address return_pc_addr{base.GetSection(), return_pc};
+  return return_pc_addr.GetLoadAddress(&target);
+}
+
+//----------------------------------------------------------------------
+//
+//----------------------------------------------------------------------
 Function::Function(CompileUnit *comp_unit, lldb::user_id_t func_uid,
                    lldb::user_id_t type_uid, const Mangled &mangled, Type *type,
                    const AddressRange &range)
     : UserID(func_uid), m_comp_unit(comp_unit), m_type_uid(type_uid),
       m_type(type), m_mangled(mangled), m_block(func_uid), m_range(range),
       m_frame_base(nullptr), m_flags(), m_prologue_byte_size(0) {
   m_block.SetParentScope(this);
   assert(comp_unit != nullptr);
void Function::GetEndLineSourceInfo(FileSpec &source_file, uint32_t &line_no) {
 
   LineEntry line_entry;
   if (line_table->FindLineEntryByAddress(scratch_addr, line_entry, nullptr)) {
     line_no = line_entry.line;
     source_file = line_entry.file;
   }
 }
 
+llvm::MutableArrayRef<CallEdge> Function::GetCallEdges() {
+  if (m_call_edges_resolved)
+    return m_call_edges;
+
+  Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_STEP));
+  LLDB_LOG(log, "GetCallEdges: Attempting to parse call site info for {0}",
+           GetDisplayName());
+
+  m_call_edges_resolved = true;
+
+  // Find the SymbolFile which provided this function's definition.
+  Block &block = GetBlock(/*can_create*/true);
+  SymbolFile *sym_file = block.GetSymbolFile();
+  if (!sym_file)
+    return llvm::None;
+
+  // Lazily read call site information from the SymbolFile.
+  m_call_edges = sym_file->ParseCallEdgesInFunction(GetID());
+
+  // Sort the call edges to speed up return_pc lookups.
+  std::sort(m_call_edges.begin(), m_call_edges.end(),
+            [](const CallEdge &LHS, const CallEdge &RHS) {
+              return LHS.GetUnresolvedReturnPCAddress() <
+                     RHS.GetUnresolvedReturnPCAddress();
+            });
+
+  return m_call_edges;
+}
+
+llvm::MutableArrayRef<CallEdge> Function::GetTailCallingEdges() {
+  // Call edges are sorted by return PC, and tail calling edges have invalid
+  // return PCs. Find them at the end of the list.
+  return GetCallEdges().drop_until([](const CallEdge &edge) {
+    return edge.GetUnresolvedReturnPCAddress() == LLDB_INVALID_ADDRESS;
+  });
+}
+
 Block &Function::GetBlock(bool can_create) {
   if (!m_block.BlockInfoHasBeenParsed() && can_create) {
     SymbolContext sc;
     CalculateSymbolContext(&sc);
     if (sc.module_sp) {
       sc.module_sp->GetSymbolVendor()->ParseFunctionBlocks(sc);
     } else {
       Host::SystemLog(Host::eSystemLogError, "error: unable to find module "

lldb/source/Target/StackFrame.cpp

 #define RESOLVED_FRAME_CODE_ADDR (uint32_t(eSymbolContextEverything + 1))
 #define RESOLVED_FRAME_ID_SYMBOL_SCOPE (RESOLVED_FRAME_CODE_ADDR << 1)
 #define GOT_FRAME_BASE (RESOLVED_FRAME_ID_SYMBOL_SCOPE << 1)
 #define RESOLVED_VARIABLES (GOT_FRAME_BASE << 1)
 #define RESOLVED_GLOBAL_VARIABLES (RESOLVED_VARIABLES << 1)
 
 StackFrame::StackFrame(const ThreadSP &thread_sp, user_id_t frame_idx,
                        user_id_t unwind_frame_index, addr_t cfa,
-                       bool cfa_is_valid, addr_t pc, uint32_t stop_id,
-                       bool stop_id_is_valid, bool is_history_frame,
+                       bool cfa_is_valid, addr_t pc, StackFrame::Kind kind,
                        const SymbolContext *sc_ptr)
     : m_thread_wp(thread_sp), m_frame_index(frame_idx),
       m_concrete_frame_index(unwind_frame_index), m_reg_context_sp(),
       m_id(pc, cfa, nullptr), m_frame_code_addr(pc), m_sc(), m_flags(),
       m_frame_base(), m_frame_base_error(), m_cfa_is_valid(cfa_is_valid),
-      m_stop_id(stop_id), m_stop_id_is_valid(stop_id_is_valid),
-      m_is_history_frame(is_history_frame), m_variable_list_sp(),
+      m_stack_frame_kind(kind), m_variable_list_sp(),
       m_variable_list_value_objects(), m_disassembly(), m_mutex() {
   // If we don't have a CFA value, use the frame index for our StackID so that
   // recursive functions properly aren't confused with one another on a history
   // stack.
-  if (m_is_history_frame && !m_cfa_is_valid) {
+  if (IsHistorical() && !m_cfa_is_valid) {
     m_id.SetCFA(m_frame_index);
   }
 
   if (sc_ptr != nullptr) {
     m_sc = *sc_ptr;
     m_flags.Set(m_sc.GetResolvedMask());
   }
 }
 
 StackFrame::StackFrame(const ThreadSP &thread_sp, user_id_t frame_idx,
                        user_id_t unwind_frame_index,
                        const RegisterContextSP &reg_context_sp, addr_t cfa,
                        addr_t pc, const SymbolContext *sc_ptr)
     : m_thread_wp(thread_sp), m_frame_index(frame_idx),
       m_concrete_frame_index(unwind_frame_index),
       m_reg_context_sp(reg_context_sp), m_id(pc, cfa, nullptr),
       m_frame_code_addr(pc), m_sc(), m_flags(), m_frame_base(),
-      m_frame_base_error(), m_cfa_is_valid(true), m_stop_id(0),
-      m_stop_id_is_valid(false), m_is_history_frame(false),
-      m_variable_list_sp(), m_variable_list_value_objects(), m_disassembly(),
-      m_mutex() {
+      m_frame_base_error(), m_cfa_is_valid(true),
+      m_stack_frame_kind(StackFrame::Kind::Regular), m_variable_list_sp(),
+      m_variable_list_value_objects(), m_disassembly(), m_mutex() {
   if (sc_ptr != nullptr) {
     m_sc = *sc_ptr;
     m_flags.Set(m_sc.GetResolvedMask());
   }
 
   if (reg_context_sp && !m_sc.target_sp) {
     m_sc.target_sp = reg_context_sp->CalculateTarget();
     if (m_sc.target_sp)
       m_flags.Set(eSymbolContextTarget);
   }
 }
 
 StackFrame::StackFrame(const ThreadSP &thread_sp, user_id_t frame_idx,
                        user_id_t unwind_frame_index,
                        const RegisterContextSP &reg_context_sp, addr_t cfa,
                        const Address &pc_addr, const SymbolContext *sc_ptr)
     : m_thread_wp(thread_sp), m_frame_index(frame_idx),
       m_concrete_frame_index(unwind_frame_index),
       m_reg_context_sp(reg_context_sp),
       m_id(pc_addr.GetLoadAddress(thread_sp->CalculateTarget().get()), cfa,
            nullptr),
       m_frame_code_addr(pc_addr), m_sc(), m_flags(), m_frame_base(),
-      m_frame_base_error(), m_cfa_is_valid(true), m_stop_id(0),
-      m_stop_id_is_valid(false), m_is_history_frame(false),
-      m_variable_list_sp(), m_variable_list_value_objects(), m_disassembly(),
-      m_mutex() {
+      m_frame_base_error(), m_cfa_is_valid(true),
+      m_stack_frame_kind(StackFrame::Kind::Regular), m_variable_list_sp(),
+      m_variable_list_value_objects(), m_disassembly(), m_mutex() {
   if (sc_ptr != nullptr) {
     m_sc = *sc_ptr;
     m_flags.Set(m_sc.GetResolvedMask());
   }
 
   if (!m_sc.target_sp && reg_context_sp) {
     m_sc.target_sp = reg_context_sp->CalculateTarget();
     if (m_sc.target_sp)
if (m_flags.IsClear(RESOLVED_FRAME_CODE_ADDR) &&
     }
   }
   return m_frame_code_addr;
 }
 
 bool StackFrame::ChangePC(addr_t pc) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
   // We can't change the pc value of a history stack frame - it is immutable.
-  if (m_is_history_frame)
+  if (IsHistorical())
     return false;
   m_frame_code_addr.SetRawAddress(pc);
   m_sc.Clear(false);
   m_flags.Reset(0);
   ThreadSP thread_sp(GetThread());
   if (thread_sp)
     thread_sp->ClearStackFrames();
   return true;
VariableList *StackFrame::GetVariableList(bool get_file_globals) {
   return m_variable_list_sp.get();
 }
 
 VariableListSP
 StackFrame::GetInScopeVariableList(bool get_file_globals,
                                    bool must_have_valid_location) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
   // We can't fetch variable information for a history stack frame.
-  if (m_is_history_frame)
+  if (IsHistorical())
     return VariableListSP();
 
   VariableListSP var_list_sp(new VariableList);
   GetSymbolContext(eSymbolContextCompUnit | eSymbolContextBlock);
 
   if (m_sc.block) {
     const bool can_create = true;
     const bool get_parent_variables = true;
StackFrame::GetInScopeVariableList(bool get_file_globals,
   return var_list_sp;
 }
 
 ValueObjectSP StackFrame::GetValueForVariableExpressionPath(
     llvm::StringRef var_expr, DynamicValueType use_dynamic, uint32_t options,
     VariableSP &var_sp, Status &error) {
   llvm::StringRef original_var_expr = var_expr;
   // We can't fetch variable information for a history stack frame.
-  if (m_is_history_frame)
+  if (IsHistorical())
     return ValueObjectSP();
 
   if (var_expr.empty()) {
     error.SetErrorStringWithFormat("invalid variable path '%s'",
                                    var_expr.str().c_str());
     return ValueObjectSP();
   }
 
bool StackFrame::HasDebugInformation() {
   return m_sc.line_entry.IsValid();
 }
 
 ValueObjectSP
 StackFrame::GetValueObjectForFrameVariable(const VariableSP &variable_sp,
                                            DynamicValueType use_dynamic) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
   ValueObjectSP valobj_sp;
-  if (m_is_history_frame) {
+  if (IsHistorical()) {
     return valobj_sp;
   }
   VariableList *var_list = GetVariableList(true);
   if (var_list) {
     // Make sure the variable is a frame variable
     const uint32_t var_idx = var_list->FindIndexForVariable(variable_sp.get());
     const uint32_t num_variables = var_list->GetSize();
     if (var_idx < num_variables) {
if (dynamic_sp)
       return dynamic_sp;
   }
   return valobj_sp;
 }
 
 ValueObjectSP StackFrame::TrackGlobalVariable(const VariableSP &variable_sp,
                                               DynamicValueType use_dynamic) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
-  if (m_is_history_frame)
+  if (IsHistorical())
     return ValueObjectSP();
 
   // Check to make sure we aren't already tracking this variable?
   ValueObjectSP valobj_sp(
       GetValueObjectForFrameVariable(variable_sp, use_dynamic));
   if (!valobj_sp) {
     // We aren't already tracking this global
     VariableList *var_list = GetVariableList(true);

 bool StackFrame::IsInlined() {
   if (m_sc.block == nullptr)
     GetSymbolContext(eSymbolContextBlock);
   if (m_sc.block)
     return m_sc.block->GetContainingInlinedBlock() != nullptr;
   return false;
 }
 
+bool StackFrame::IsHistorical() const {
+  return m_stack_frame_kind == StackFrame::Kind::History;
+}
+
+bool StackFrame::IsArtificial() const {
+  return m_stack_frame_kind == StackFrame::Kind::Artificial;
+}
+
 lldb::LanguageType StackFrame::GetLanguage() {
   CompileUnit *cu = GetSymbolContext(eSymbolContextCompUnit).comp_unit;
   if (cu)
     return cu->GetLanguage();
   return lldb::eLanguageTypeUnknown;
 }
 
 lldb::LanguageType StackFrame::GuessLanguage() {

lldb/source/Target/StackFrameList.cpp

 #include "lldb/Target/Process.h"
 #include "lldb/Target/RegisterContext.h"
 #include "lldb/Target/StackFrame.h"
 #include "lldb/Target/StopInfo.h"
 #include "lldb/Target/Target.h"
 #include "lldb/Target/Thread.h"
 #include "lldb/Target/Unwind.h"
 #include "lldb/Utility/Log.h"
+#include "llvm/ADT/SmallPtrSet.h"
 
 //#define DEBUG_STACK_FRAMES 1
 
 using namespace lldb;
 using namespace lldb_private;
 
 //----------------------------------------------------------------------
 // StackFrameList constructor
if (num_frames <= end_idx + 1) {
     m_concrete_frames_fetched = UINT32_MAX;
   }
 
   // Don't create the frames eagerly. Defer this work to GetFrameAtIndex,
   // which can lazily query the unwinder to create frames.
   m_frames.resize(num_frames);
 }
 
+/// Find the unique path through the call graph from \p begin (at PC offset
+/// \p call_pc) to \p end. On success this path is stored into \p path, and on
+/// failure \p path is unchanged.
+static void FindInterveningFrames(Function &begin, Function &end,
+                                  Target &target, addr_t call_pc,
+                                  std::vector<Function *> &path,
+                                  ModuleList &images, Log *log) {
+  LLDB_LOG(log, "Finding frames between {0} and {1}, call-pc={2:x}",
+           begin.GetDisplayName(), end.GetDisplayName(), call_pc);
+
+  // Find a non-tail calling edge with the first return PC greater than the
+  // call PC.
+  auto first_level_edges = begin.GetCallEdges();
+  auto first_edge_it = std::lower_bound(
+      first_level_edges.begin(), first_level_edges.end(), call_pc,
+      [&](const CallEdge &edge, addr_t target_pc) {
+        return edge.GetReturnPCAddress(begin, target) < target_pc;
+      });
+  if (first_edge_it == first_level_edges.end())
+    return;
+  CallEdge &first_edge = const_cast<CallEdge &>(*first_edge_it);
+  if (first_edge.GetReturnPCAddress(begin, target) == LLDB_INVALID_ADDRESS)
+    return;
+
+  // The first callee may not be resolved, or there may be nothing to fill in.
+  Function *first_callee = first_edge.GetCallee(images);
+  if (!first_callee || first_callee == &end)
+    return;
+
+  // Run DFS on the tail-calling edges out of the first callee to find \p end.
+  // Fully explore the set of functions reachable from the first edge via tail
+  // calls in order to detect ambiguous executions.
+  struct DFS {
+    std::vector<Function *> active_path = {};
+    std::vector<Function *> solution_path = {};
+    llvm::SmallPtrSet<Function *, 2> visited_nodes = {};
+    bool ambiguous = false;
+    Function *end;
+    ModuleList &images;
+
+    DFS(Function *end, ModuleList &images) : end(end), images(images) {}
+
+    void search(Function *first_callee, std::vector<Function *> &path) {
+      dfs(first_callee);
+      if (!ambiguous)
+        path = std::move(solution_path);
+    }
+
+    void dfs(Function *callee) {
+      // Found a path to the target function.
+      if (callee == end) {
+        if (solution_path.empty())
+          solution_path = active_path;
+        else
+          ambiguous = true;
+        return;
+      }
+
+      // Terminate the search if tail recursion is found, or more generally if
+      // there's more than one way to reach a target. This errs on the side of
+      // caution: it conservatively stops searching when some solutions are
+      // still possible to save time in the average case.
+      if (!visited_nodes.insert(callee).second) {
+        ambiguous = true;
+        return;
+      }
+
+      // Search the calls made from this callee.
+      active_path.push_back(callee);
+      for (CallEdge &edge : callee->GetTailCallingEdges()) {
+        Function *next_callee = edge.GetCallee(images);
+        if (!next_callee)
+          continue;
+
+        dfs(next_callee);
+        if (ambiguous)
+          return;
+      }
+      active_path.pop_back();
+    }
+  };
+
+  DFS(&end, images).search(first_callee, path);
+}
+
+/// Given that \p next_frame will be appended to the frame list, synthesize
+/// tail call frames between the current end of the list and \p next_frame.
+/// If any frames are added, adjust the frame index of \p next_frame.
+///
+///   --------------
+///   |    ...     | <- Completed frames.
+///   --------------
+///   | prev_frame |
+///   --------------
+///   |    ...     | <- Artificial frames inserted here.
+///   --------------
+///   | next_frame |
+///   --------------
+///   |    ...     | <- Not-yet-visited frames.
+///   --------------
+void StackFrameList::SynthesizeTailCallFrames(StackFrame &next_frame) {
+  TargetSP target_sp = next_frame.CalculateTarget();
+  if (!target_sp)
+    return;
+
+  lldb::RegisterContextSP next_reg_ctx_sp = next_frame.GetRegisterContext();
+  if (!next_reg_ctx_sp)
+    return;
+
+  Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_STEP));
+
+  assert(!m_frames.empty() && "Cannot synthesize frames in an empty stack");
+  StackFrame &prev_frame = *m_frames.back().get();
+
+  // Find the functions prev_frame and next_frame are stopped in. The function
+  // objects are needed to search the lazy call graph for intervening frames.
+  Function *prev_func =
+      prev_frame.GetSymbolContext(eSymbolContextFunction).function;
+  if (!prev_func)
+    return;
+  Function *next_func =
+      next_frame.GetSymbolContext(eSymbolContextFunction).function;
+  if (!next_func)
+    return;
+
+  // Try to find the unique sequence of (tail) calls which led from next_frame
+  // to prev_frame.
+  std::vector<Function *> path;
+  addr_t call_pc = next_reg_ctx_sp->GetPC();
+  Target &target = *target_sp.get();
+  ModuleList &images = next_frame.CalculateTarget()->GetImages();
+  FindInterveningFrames(*next_func, *prev_func, target, call_pc, path, images,
+                        log);
+
+  // Push synthetic tail call frames.
+  for (Function *callee : llvm::reverse(path)) {
+    uint32_t frame_idx = m_frames.size();
+    uint32_t concrete_frame_idx = next_frame.GetConcreteFrameIndex();
+    addr_t cfa = LLDB_INVALID_ADDRESS;
+    bool cfa_is_valid = false;
+    addr_t pc =
+        callee->GetAddressRange().GetBaseAddress().GetLoadAddress(&target);
+    SymbolContext sc;
+    callee->CalculateSymbolContext(&sc);
+    StackFrameSP synth_frame{new StackFrame(
+        m_thread.shared_from_this(), frame_idx, concrete_frame_idx, cfa,
+        cfa_is_valid, pc, StackFrame::Kind::Artificial, &sc)};
+    m_frames.push_back(synth_frame);
+    LLDB_LOG(log, "Pushed frame {0}", callee->GetDisplayName());
+  }
+
+  // If any frames were created, adjust next_frame's index.
+  if (!path.empty())
+    next_frame.SetFrameIndex(m_frames.size());
+}
+
 void StackFrameList::GetFramesUpTo(uint32_t end_idx) {
   // Do not fetch frames for an invalid thread.
   if (!m_thread.IsValid())
     return;
 
   // We've already gotten more frames than asked for, or we've already finished
   // unwinding, return.
   if (m_frames.size() > end_idx || GetAllFramesFetched())
     return;
 
   Unwind *unwinder = m_thread.GetUnwinder();
 
   if (!m_show_inlined_frames) {
if (idx == 0) {
       const bool success =
           unwinder && unwinder->GetFrameInfoAtIndex(idx, cfa, pc);
       if (!success) {
         // We've gotten to the end of the stack.
         SetAllFramesFetched();
         break;
       }
       const bool cfa_is_valid = true;
-      const bool stop_id_is_valid = false;
-      const bool is_history_frame = false;
-      unwind_frame_sp.reset(new StackFrame(
-          m_thread.shared_from_this(), m_frames.size(), idx, cfa, cfa_is_valid,
-          pc, 0, stop_id_is_valid, is_history_frame, nullptr));
+      unwind_frame_sp.reset(
+          new StackFrame(m_thread.shared_from_this(), m_frames.size(), idx, cfa,
+                         cfa_is_valid, pc, StackFrame::Kind::Regular, nullptr));
+
+      // Create synthetic tail call frames between the previous frame and the
+      // newly-found frame. The new frame's index may change after this call,
+      // although its concrete index will stay the same.
+      SynthesizeTailCallFrames(*unwind_frame_sp.get());
+
       m_frames.push_back(unwind_frame_sp);
     }
 
     assert(unwind_frame_sp);
     SymbolContext unwind_sc = unwind_frame_sp->GetSymbolContext(
         eSymbolContextBlock | eSymbolContextFunction);
     Block *unwind_block = unwind_sc.block;
     if (unwind_block) {
if (m_show_inlined_frames) {
       // GetFramesUpTo.
       frame_sp = m_frames[idx];
     } else {
       Unwind *unwinder = m_thread.GetUnwinder();
       if (unwinder) {
         addr_t pc, cfa;
         if (unwinder->GetFrameInfoAtIndex(idx, cfa, pc)) {
           const bool cfa_is_valid = true;
-          const bool stop_id_is_valid = false;
-          const bool is_history_frame = false;
-          frame_sp.reset(new StackFrame(
-              m_thread.shared_from_this(), idx, idx, cfa, cfa_is_valid, pc, 0,
-              stop_id_is_valid, is_history_frame, nullptr));
+          frame_sp.reset(new StackFrame(m_thread.shared_from_this(), idx, idx,
+                                        cfa, cfa_is_valid, pc,
+                                        StackFrame::Kind::Regular, nullptr));
 
           Function *function =
               frame_sp->GetSymbolContext(eSymbolContextFunction).function;
           if (function) {
             // When we aren't showing inline functions we always use the top
             // most function block as the scope.
             frame_sp->SetSymbolContextScope(&function->GetBlock(false));
           } else {

lldb/source/Target/ThreadPlanStepOut.cpp

ThreadPlanStepOut::ThreadPlanStepOut(
     bool continue_to_next_branch, bool gather_return_value)
     : ThreadPlan(ThreadPlan::eKindStepOut, "Step out", thread, stop_vote,
                  run_vote),
       ThreadPlanShouldStopHere(this), m_step_from_insn(LLDB_INVALID_ADDRESS),
       m_return_bp_id(LLDB_INVALID_BREAK_ID),
       m_return_addr(LLDB_INVALID_ADDRESS), m_stop_others(stop_others),
       m_immediate_step_from_function(nullptr),
       m_calculate_return_value(gather_return_value) {
+  Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_STEP));
   SetFlagsToDefault();
   SetupAvoidNoDebug(step_out_avoids_code_without_debug_info);
 
   m_step_from_insn = m_thread.GetRegisterContext()->GetPC(0);
 
-  StackFrameSP return_frame_sp(m_thread.GetStackFrameAtIndex(frame_idx + 1));
+  uint32_t return_frame_index = frame_idx + 1;
+  StackFrameSP return_frame_sp(
+      m_thread.GetStackFrameAtIndex(return_frame_index));
   StackFrameSP immediate_return_from_sp(
       m_thread.GetStackFrameAtIndex(frame_idx));
 
   if (!return_frame_sp || !immediate_return_from_sp)
     return; // we can't do anything here.  ValidatePlan() will return false.
 
+  // While stepping out, behave as-if artificial frames are not present.
+  while (return_frame_sp->IsArtificial()) {
+    ++return_frame_index;
+    return_frame_sp = m_thread.GetStackFrameAtIndex(return_frame_index);
+
+    // We never expect to see an artificial frame without a regular ancestor.
+    // If this happens, log the issue and defensively refuse to step out.
+    if (!return_frame_sp) {
+      LLDB_LOG(log, "Can't step out of frame with artificial ancestors");
+      return;
+    }
+  }
+
   m_step_out_to_id = return_frame_sp->GetStackID();
   m_immediate_step_from_id = immediate_return_from_sp->GetStackID();
 
   // If the frame directly below the one we are returning to is inlined, we
   // have to be a little more careful.  It is non-trivial to determine the real
   // "return code address" for an inlined frame, so we have to work our way to
   // that frame and then step out.
-  if (immediate_return_from_sp && immediate_return_from_sp->IsInlined()) {
+  if (immediate_return_from_sp->IsInlined()) {
     if (frame_idx > 0) {
       // First queue a plan that gets us to this inlined frame, and when we get
       // there we'll queue a second plan that walks us out of this frame.
       m_step_out_to_inline_plan_sp.reset(new ThreadPlanStepOut(
           m_thread, nullptr, false, stop_others, eVoteNoOpinion, eVoteNoOpinion,
           frame_idx - 1, eLazyBoolNo, continue_to_next_branch));
       static_cast<ThreadPlanStepOut *>(m_step_out_to_inline_plan_sp.get())
           ->SetShouldStopHereCallbacks(nullptr, nullptr);
       m_step_out_to_inline_plan_sp->SetPrivate(true);
     } else {
       // If we're already at the inlined frame we're stepping through, then
       // just do that now.
       QueueInlinedStepPlan(false);
     }
-  } else if (return_frame_sp) {
+  } else {
     // Find the return address and set a breakpoint there:
     // FIXME - can we do this more securely if we know first_insn?
 
     Address return_address(return_frame_sp->GetFrameCodeAddress());
     if (continue_to_next_branch) {
       SymbolContext return_address_sc;
       AddressRange range;
       Address return_address_decr_pc = return_address;