Index: lldb/include/lldb/Symbol/Block.h =================================================================== --- lldb/include/lldb/Symbol/Block.h +++ lldb/include/lldb/Symbol/Block.h @@ -327,6 +327,14 @@ 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(); //------------------------------------------------------------------ Index: lldb/include/lldb/Symbol/Function.h =================================================================== --- lldb/include/lldb/Symbol/Function.h +++ lldb/include/lldb/Symbol/Function.h @@ -16,6 +16,7 @@ #include "lldb/Symbol/Block.h" #include "lldb/Symbol/Declaration.h" #include "lldb/Utility/UserID.h" +#include "llvm/ADT/ArrayRef.h" namespace lldb_private { @@ -290,6 +291,35 @@ 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. @@ -396,6 +426,13 @@ //------------------------------------------------------------------ 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 GetCallEdges(); + //------------------------------------------------------------------ /// Get accessor for the block list. /// @@ -587,6 +624,10 @@ 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 m_call_edges; ///< Outgoing call edges. private: DISALLOW_COPY_AND_ASSIGN(Function); }; Index: lldb/include/lldb/Symbol/SymbolFile.h =================================================================== --- lldb/include/lldb/Symbol/SymbolFile.h +++ lldb/include/lldb/Symbol/SymbolFile.h @@ -14,6 +14,7 @@ #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" @@ -194,6 +195,10 @@ ObjectFile *GetObjectFile() { return m_obj_file; } const ObjectFile *GetObjectFile() const { return m_obj_file; } + virtual std::vector ParseCallEdgesInFunction(UserID func_id) { + return {}; + } + //------------------------------------------------------------------ /// Notify the SymbolFile that the file addresses in the Sections /// for this module have been changed. Index: lldb/include/lldb/Target/StackFrame.h =================================================================== --- lldb/include/lldb/Target/StackFrame.h +++ lldb/include/lldb/Target/StackFrame.h @@ -412,6 +412,11 @@ //------------------------------------------------------------------ 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. Index: lldb/include/lldb/Target/StackFrameList.h =================================================================== --- lldb/include/lldb/Target/StackFrameList.h +++ lldb/include/lldb/Target/StackFrameList.h @@ -99,6 +99,8 @@ 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; } Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/tail.cc =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/tail.cc @@ -0,0 +1,20 @@ +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; +} Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/tail2.cc =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/tail2.cc @@ -0,0 +1,8 @@ +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 */} Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/tail3.cc =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/tail3.cc @@ -0,0 +1,5 @@ +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 */ } Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/tail4.cc =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/tail4.cc @@ -0,0 +1,5 @@ +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 */ } Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/tail5.cc =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/tail5.cc @@ -0,0 +1,6 @@ +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 */ } Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/test.sh =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/test.sh @@ -0,0 +1,13 @@ +#!/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 Index: lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h =================================================================== --- lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h +++ lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h @@ -316,6 +316,9 @@ DIEInDeclContext(const lldb_private::CompilerDeclContext *parent_decl_ctx, const DWARFDIE &die); + std::vector + ParseCallEdgesInFunction(UserID func_id) override; + void Dump(lldb_private::Stream &s) override; protected: Index: lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp =================================================================== --- lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp +++ lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp @@ -3736,6 +3736,54 @@ return vars_added; } +/// Collect call graph edges present in a function DIE. +static std::vector +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 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 +SymbolFileDWARF::ParseCallEdgesInFunction(UserID func_id) { + DWARFDIE func_die = GetDIEFromUID(func_id.GetID()); + if (func_die.IsValid()) + return CollectCallEdges(func_die); + return {}; +} + //------------------------------------------------------------------ // PluginInterface protocol //------------------------------------------------------------------ Index: lldb/source/Symbol/Block.cpp =================================================================== --- lldb/source/Symbol/Block.cpp +++ lldb/source/Symbol/Block.cpp @@ -444,19 +444,16 @@ 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 sym_file->GetDeclContextForUID(GetID()); return CompilerDeclContext(); } Index: lldb/source/Symbol/Function.cpp =================================================================== --- lldb/source/Symbol/Function.cpp +++ lldb/source/Symbol/Function.cpp @@ -10,6 +10,7 @@ #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" @@ -18,6 +19,7 @@ #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; @@ -128,6 +130,49 @@ 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; +} + //---------------------------------------------------------------------- // //---------------------------------------------------------------------- @@ -192,6 +237,22 @@ } } +llvm::ArrayRef 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; Index: lldb/source/Target/StackFrameList.cpp =================================================================== --- lldb/source/Target/StackFrameList.cpp +++ lldb/source/Target/StackFrameList.cpp @@ -27,6 +27,7 @@ #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 @@ -240,6 +241,124 @@ 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 &path, + ModuleList &images, Log *log) { + LLDB_LOG(log, "SynthesizeTailCallFrames: Finding frames between {0} and {1}", + begin.GetDisplayName(), end.GetDisplayName()); + + struct dfs { + std::vector active_path; + std::vector solution_path; + llvm::SmallPtrSet 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 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()) @@ -320,6 +439,12 @@ 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); }