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,49 @@ 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 PC address of the instruction which executes after the call + /// returns. Returns LLDB_INVALID_ADDRESS iff this is a tail call. + lldb::addr_t GetReturnPCAddress() const; + +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. + lldb::addr_t return_pc; + + DISALLOW_COPY_AND_ASSIGN(CallEdge); +}; + //---------------------------------------------------------------------- /// @class Function Function.h "lldb/Symbol/Function.h" /// A class that describes a function. @@ -396,6 +440,20 @@ //------------------------------------------------------------------ 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). + /// + /// @return A mutable array reference with the same lifetime as `this`. + //------------------------------------------------------------------ + llvm::MutableArrayRef GetCallEdges(); + + //------------------------------------------------------------------ + /// Get the outgoing tail-callling edges from this function. If none exist, + /// return None. + //------------------------------------------------------------------ + llvm::MutableArrayRef GetTailCallingEdges(); + //------------------------------------------------------------------ /// Get accessor for the block list. /// @@ -587,6 +645,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/TODO =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/TODO @@ -0,0 +1,4 @@ +I've updated this to use DW_AT_call_return_pc information. Now, the missing +pieces are tests and better pretty-printing of synthetic frames. Re: testing, +particular emphasis is needed on tail recursion, and for functions with more +than one tail call (e.g https://godbolt.org/g/24DSdH). 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,12 @@ +#!/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 + + $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,59 @@ 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; + } + + // 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 +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,54 @@ 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); + + lazy_callee.def = [&]() -> 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; + }(); + resolved = true; +} + +Function *CallEdge::GetCallee(ModuleList &images) { + ParseSymbolFileAndResolve(images); + return lazy_callee.def; +} + +lldb::addr_t CallEdge::GetReturnPCAddress() const { return return_pc; } + //---------------------------------------------------------------------- // //---------------------------------------------------------------------- @@ -192,6 +242,38 @@ } } +llvm::MutableArrayRef Function::GetCallEdges() { + if (m_call_edges_resolved) + return m_call_edges; + + 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.GetReturnPCAddress() < RHS.GetReturnPCAddress(); + }); + + return m_call_edges; +} + +llvm::MutableArrayRef 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.GetReturnPCAddress() == LLDB_INVALID_ADDRESS; + }); +} + 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,134 @@ 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, + addr_t call_pc, std::vector &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() < target_pc; + }); + if (first_edge_it == first_level_edges.end()) + return; + CallEdge &first_edge = const_cast(*first_edge_it); + if (first_edge.GetReturnPCAddress() == 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. + struct DFS { + std::vector active_path = {}; + llvm::SmallPtrSet 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 &path) { + if (dfs(first_callee) && !ambiguous) + path = std::move(active_path); + } + + bool dfs(Function *callee) { + if (callee == end) + return true; + + // Terminate the search when tail recursion is detected. + if (!visited_nodes.insert(callee).second) { + ambiguous = true; + return false; + } + + active_path.push_back(callee); + for (CallEdge &edge : callee->GetTailCallingEdges()) { + Function *next_callee = edge.GetCallee(images); + if (!next_callee) + continue; + + if (dfs(next_callee) && !ambiguous) + return true; + + if (ambiguous) + return false; + } + active_path.pop_back(); + return false; + } + }; + + 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. +void StackFrameList::SynthesizeTailCallFrames(StackFrame &next_frame) { + 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 path; + addr_t call_pc = next_reg_ctx_sp->GetPC(); + ModuleList &images = next_frame.CalculateTarget()->GetImages(); + FindInterveningFrames(*next_func, *prev_func, 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().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, "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()) @@ -320,6 +449,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); }