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

436

Typo: tail-calling

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

691 ↗

(On Diff #160666)

Two leading "" missing?

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

3757

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

3757

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

5 ↗

(On Diff #167148)

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

5 ↗

(On Diff #167148)

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/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 {
+  /// Whether or not an attempt was made to find the callee's definition.
+  bool resolved;
+
+  union {
+    const char *mangled_name; //< The mangled name of the callee.
+    Function *callee; //< The definition of the callee.
+  } lazy_target;
+
+  // TODO: Include the call return PC address here to disambiguate multiple
+  // paths from a caller to a leaf function.
+
+public:
+  CallEdge(const char *mangled_name);
+
+  /// Get the callee's definition.
+  ///
+  /// Note that this might lazily invoke the DWARF parser.
+  Function *GetCallee(ModuleList &images);
+};
+
 //----------------------------------------------------------------------
 /// @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),
 /// be declared at a specific location (FunctionInfo::m_declaration), possibly
 /// have mangled names (Function::m_mangled), an optional return type
 /// (Function::m_type), and contains lexical blocks (Function::m_blocks).
 ///
 /// The function information is split into a few pieces:
 ///     @li The concrete instance information
 ///     @li The abstract information
 ///
 /// The abstract information is found in the function type (Type) that
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.
+  ///
+  /// @return An immutable array reference with the same lifetime as `this`.
+  //------------------------------------------------------------------
+  llvm::ArrayRef<CallEdge> GetCallEdges();
+
+  //------------------------------------------------------------------
   /// 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

public:
   //------------------------------------------------------------------
   /// 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,
   /// 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
   ///   which is the frame index without any inlined stack frames.
public:
   ///
   /// @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.

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/functionalities/tail_call_frames/tail.cc

+volatile int x;
+
+void __attribute__((noinline)) sink() {
+  // The stack just contains a return address inside of main().
+  //
+  // Note that it wouldn't be possible to disambiguate sink() from another
+  // immediate callee of bar() without DW_AT_return_pc.
+  x++;
+}
+
+void __attribute__((noinline)) bar() {
+  // Note that no return address in sink() is pushed onto the stack.
+  sink(); // tail (`jmp _sink`)
+}
+
+int main() {
+  bar(); // tail (`callq _bar`)
+  bar(); // tail (`callq _bar`)
+  return 0;
+}

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/tail2.cc

+volatile int x;
+void __attribute__((noinline)) sink() { x++; }
+void __attribute__((noinline)) bar() { x++; }
+void __attribute__((noinline)) foo() {
+  bar(); /* tail */
+  sink(); /* tail */
+}
+int __attribute__((disable_tail_calls)) main() { foo(); /* regular */}

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/tail3.cc

+volatile int x;
+void __attribute__((noinline)) sink() { x++; }
+void __attribute__((disable_tail_calls, noinline)) bar() { sink(); /* regular */ }
+void __attribute__((noinline)) foo() { bar(); /* tail */ }
+int __attribute__((disable_tail_calls)) main() { foo(); /* regular */ }

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/tail4.cc

+volatile int x;
+void __attribute__((noinline)) sink() { x++; } // Two possible paths to sink.
+void __attribute__((noinline)) foo() { sink(); /* tail */ }
+void __attribute__((noinline)) bar() { sink(); /* tail */ }
+int __attribute__((disable_tail_calls)) main() { foo(); bar(); /* regular */ }

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/tail5.cc

+volatile int x;
+void __attribute__((noinline)) sink() { x++; }
+void __attribute__((noinline)) D() { sink(); /* tail */ }
+void __attribute__((disable_tail_calls, noinline)) C() { D(); /* regular */ }
+void __attribute__((noinline)) B() { C(); /* tail */ }
+int __attribute__((disable_tail_calls)) main() { B(); /* regular */ }

lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/test.sh

+#!/bin/bash -x
+
+BIN=/Users/vsk/src/builds/llvm-project-tailcall-RA/bin/
+CXX=$BIN/clang++
+LLDB=$BIN/lldb
+
+for F in $(ls *.cc); do
+  $CXX $F -o $F.out \
+    -g -mllvm -callsite-debuginfo-experimental=true -O2
+
+  xcrun lldb -o "b sink" -o "r" -o "bt" -o "quit" $F.out
+  $LLDB -o "b sink" -o "r" -o "log enable -f $F.log lldb step" -o "bt" -o "quit" $F.out
+done

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

     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;
+    }
+
+    LLDB_LOG(log, "CollectCallEdges: Found call origin -> {0}",
+             call_origin.GetPubname());
+    call_edges.emplace_back(call_origin.GetMangledName());
+  }
+  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/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) : resolved(false) {
+  lazy_target.mangled_name = mangled_name;
+}
+
+Function *CallEdge::GetCallee(ModuleList &images) {
+  if (resolved)
+    return lazy_target.callee;
+
+  Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_STEP));
+  LLDB_LOG(log, "CallEdge::GetCallee: Lazily parsing the call graph for {0}",
+           lazy_target.mangled_name);
+
+  lazy_target.callee = [&]() -> Function * {
+    ConstString callee_name{lazy_target.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::GetCallee: Found {0} matches for {1}, but needed "
+               "exactly 1 non-null match",
+               num_matches, callee_name);
+      return nullptr;
+    }
+    Address callee_addr = sc_list[0].symbol->GetAddress();
+    if (!callee_addr.IsValid()) {
+      LLDB_LOG(log, "CallEdge::GetCallee: Invalid symbol address");
+      return nullptr;
+    }
+    Function *f = callee_addr.CalculateSymbolContextFunction();
+    if (!f) {
+      LLDB_LOG(log, "CallEdge::GetCallee: Could not find complete function");
+      return nullptr;
+    }
+    return f;
+  }();
+  resolved = true;
+  return lazy_target.callee;
+}
+
+//----------------------------------------------------------------------
+//
+//----------------------------------------------------------------------
 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::ArrayRef<CallEdge> Function::GetCallEdges() {
+  if (m_call_edges_resolved)
+    return m_call_edges;
+
+  // Attempt to parse call edges at most once.
+  m_call_edges_resolved = true;
+
+  Block &block = GetBlock(/*can_create*/true);
+  SymbolFile *sym_file = block.GetSymbolFile();
+  if (!sym_file)
+    return llvm::None;
+
+  m_call_edges = sym_file->ParseCallEdgesInFunction(GetID());
+  return m_call_edges;
+}
+
 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/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 which led from \p begin 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,
+                                  std::vector<Function *> &path,
+                                  ModuleList &images, Log *log) {
+  LLDB_LOG(log, "SynthesizeTailCallFrames: Finding frames between {0} and {1}",
+           begin.GetDisplayName(), end.GetDisplayName());
+
+  struct dfs {
+    std::vector<Function *> active_path;
+    std::vector<Function *> solution_path;
+    llvm::SmallPtrSet<Function *, 8> visited;
+    bool ambiguous = false;
+    Function &end;
+    ModuleList &images;
+    Log *log;
+
+    dfs(Function &end, ModuleList &images, Log *log)
+        : end(end), images(images), log(log) {}
+
+    void search(Function &caller) {
+      if (&caller == &end) {
+        // Found a solution path. If a solution path has already been found, it
+        // must be ambiguous. If not, store the path.
+        if (!solution_path.empty())
+          ambiguous = true;
+        else
+          solution_path = active_path;
+        return;
+      }
+
+      // Scan the outgoing call edges from the caller.
+      for (CallEdge edge : caller.GetCallEdges()) {
+        Function *callee = edge.GetCallee(images);
+        if (!callee) {
+          LLDB_LOG(log, "SynthesizeTailCallFrames: Incomplete call edge");
+          continue;
+        }
+
+        // Recursively search unvisited callees.
+        bool unvisited = visited.insert(callee).second;
+        if (unvisited) {
+          LLDB_LOG(log, "SynthesizeTailCallFrames: Visiting edge {0} -> {1}",
+                   caller.GetDisplayName(), callee->GetDisplayName());
+
+          active_path.push_back(callee);
+          search(*callee);
+          if (ambiguous)
+            return;
+          active_path.pop_back();
+        } else {
+          ambiguous = true;
+          return;
+        }
+      }
+    }
+  };
+
+  dfs dfs{end, images, log};
+  dfs.search(begin);
+
+  // Return an unambiguous solution if one exists.
+  if (!dfs.ambiguous && !dfs.solution_path.empty()) {
+    path = std::move(dfs.solution_path);
+
+    // Pop off the end node, as it's already on the stack frame list.
+    path.pop_back();
+  }
+}
+
+/// 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.
+void StackFrameList::SynthesizeTailCallFrames(StackFrame &next_frame) {
+  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 access the lazy call graph for intervening frames.
+  Function *prev_func =
+      prev_frame.GetSymbolContext(eSymbolContextFunction).function;
+  Function *next_func =
+      next_frame.GetSymbolContext(eSymbolContextFunction).function;
+  if (!prev_func || !next_func) {
+    LLDB_LOG(log, "SynthesizeTailCallFrames: Function lookup failed");
+    return;
+  }
+
+  // Try to find the unique sequence of (tail) calls which led from next_frame
+  // to prev_frame.
+  std::vector<Function *> path;
+  ModuleList &images = next_frame.CalculateTarget()->GetImages();
+  FindInterveningFrames(*next_func, *prev_func, path, images, log);
+  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().GetOffset();
+    uint32_t stop_id = 0;
+    bool stop_id_is_valid = false;
+    bool is_history_frame = false;
+    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, stop_id, stop_id_is_valid, is_history_frame, &sc)};
+    m_frames.push_back(synth_frame);
+    LLDB_LOG(log, "SynthesizeTailCallFrames: Pushed frame {0}",
+             callee->GetDisplayName());
+  }
+  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())
#endif
 
   StackFrameSP unwind_frame_sp;
   do {
     uint32_t idx = m_concrete_frames_fetched++;
     lldb::addr_t pc = LLDB_INVALID_ADDRESS;
     lldb::addr_t cfa = LLDB_INVALID_ADDRESS;
     if (idx == 0) {
       // We might have already created frame zero, only create it if we need
       // to.
       if (m_frames.empty()) {
         RegisterContextSP reg_ctx_sp(m_thread.GetRegisterContext());
 
         if (reg_ctx_sp) {
           const bool success =
               unwinder && unwinder->GetFrameInfoAtIndex(idx, cfa, pc);
           // There shouldn't be any way not to get the frame info for frame
           // 0. But if the unwinder can't make one, lets make one by hand
if (idx == 0) {
         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));
+
+      // 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) {