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,55 @@ 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. @@ -396,6 +446,18 @@ //------------------------------------------------------------------ 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 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 +649,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/decorators.py =================================================================== --- lldb/packages/Python/lldbsuite/test/decorators.py +++ lldb/packages/Python/lldbsuite/test/decorators.py @@ -687,6 +687,30 @@ 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 -O1 -S -emit-llvm -mllvm -callsite-debuginfo-experimental=true -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.""" Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq1/Makefile =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq1/Makefile @@ -0,0 +1,4 @@ +LEVEL = ../../../make +CXX_SOURCES := main.cpp +include $(LEVEL)/Makefile.rules +CXXFLAGS += -mllvm -callsite-debuginfo-experimental=true -g -O1 -glldb Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq1/TestAmbiguousTailCallSeq1.py =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq1/TestAmbiguousTailCallSeq1.py @@ -0,0 +1,5 @@ +from lldbsuite.test import lldbinline +from lldbsuite.test import decorators + +lldbinline.MakeInlineTest(__file__, globals(), + [decorators.skipUnlessHasCallSiteInfo]) Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq1/main.cpp =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq1/main.cpp @@ -0,0 +1,32 @@ +//===-- 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.expect("bt", substrs = ["_amb"], matching = False) +} + +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; +} Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq2/Makefile =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq2/Makefile @@ -0,0 +1,4 @@ +LEVEL = ../../../make +CXX_SOURCES := main.cpp +include $(LEVEL)/Makefile.rules +CXXFLAGS += -mllvm -callsite-debuginfo-experimental=true -g -O1 -glldb Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq2/TestAmbiguousTailCallSeq2.py =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq2/TestAmbiguousTailCallSeq2.py @@ -0,0 +1,5 @@ +from lldbsuite.test import lldbinline +from lldbsuite.test import decorators + +lldbinline.MakeInlineTest(__file__, globals(), + [decorators.skipUnlessHasCallSiteInfo]) Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq2/main.cpp =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/ambiguous_tail_call_seq2/main.cpp @@ -0,0 +1,37 @@ +//===-- 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.expect("bt", substrs = ["func1", "func2"], matching = False) +} + +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; +} Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_call_site/Makefile =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_call_site/Makefile @@ -0,0 +1,4 @@ +LEVEL = ../../../make +CXX_SOURCES := main.cpp +include $(LEVEL)/Makefile.rules +CXXFLAGS += -mllvm -callsite-debuginfo-experimental=true -g -O1 -glldb Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_call_site/TestDisambiguateCallSite.py =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_call_site/TestDisambiguateCallSite.py @@ -0,0 +1,5 @@ +from lldbsuite.test import lldbinline +from lldbsuite.test import decorators + +lldbinline.MakeInlineTest(__file__, globals(), + [decorators.skipUnlessHasCallSiteInfo]) Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_call_site/main.cpp =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_call_site/main.cpp @@ -0,0 +1,27 @@ +//===-- 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.expect("bt", substrs = ['main', 'func2', 'sink']) +} + +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; +} Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_tail_call_seq/Makefile =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_tail_call_seq/Makefile @@ -0,0 +1,4 @@ +LEVEL = ../../../make +CXX_SOURCES := main.cpp +include $(LEVEL)/Makefile.rules +CXXFLAGS += -mllvm -callsite-debuginfo-experimental=true -g -O1 -glldb Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_tail_call_seq/TestDisambiguateTailCallSeq.py =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_tail_call_seq/TestDisambiguateTailCallSeq.py @@ -0,0 +1,5 @@ +from lldbsuite.test import lldbinline +from lldbsuite.test import decorators + +lldbinline.MakeInlineTest(__file__, globals(), + [decorators.skipUnlessHasCallSiteInfo]) Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_tail_call_seq/main.cpp =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/disambiguate_tail_call_seq/main.cpp @@ -0,0 +1,27 @@ +//===-- 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.expect("bt", substrs = ['main', 'func1', 'func3', 'sink']) +} + +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; +} Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/unambiguous_sequence/Makefile =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/unambiguous_sequence/Makefile @@ -0,0 +1,4 @@ +LEVEL = ../../../make +CXX_SOURCES := main.cpp +include $(LEVEL)/Makefile.rules +CXXFLAGS += -mllvm -callsite-debuginfo-experimental=true -g -O1 -glldb Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/unambiguous_sequence/TestUnambiguousTailCalls.py =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/unambiguous_sequence/TestUnambiguousTailCalls.py @@ -0,0 +1,5 @@ +from lldbsuite.test import lldbinline +from lldbsuite.test import decorators + +lldbinline.MakeInlineTest(__file__, globals(), + [decorators.skipUnlessHasCallSiteInfo]) Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/unambiguous_sequence/main.cpp =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/unambiguous_sequence/main.cpp @@ -0,0 +1,25 @@ +//===-- 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.expect("bt", substrs = ['main', 'func1', 'func2', 'func3', 'sink']) +} + +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; +} 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/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h =================================================================== --- lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h +++ lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h @@ -122,6 +122,8 @@ size_t GetTypes(lldb_private::SymbolContextScope *sc_scope, uint32_t type_mask, lldb_private::TypeList &type_list) override; + std::vector + ParseCallEdgesInFunction(lldb_private::UserID func_id) override; //------------------------------------------------------------------ // PluginInterface protocol Index: lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp =================================================================== --- lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp +++ lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp @@ -1060,6 +1060,15 @@ return type_list.GetSize() - initial_size; } +std::vector +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; 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,59 @@ 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(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); +} + //---------------------------------------------------------------------- // //---------------------------------------------------------------------- @@ -192,6 +247,43 @@ } } +llvm::MutableArrayRef 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 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; 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,152 @@ 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 &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(*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 active_path = {}; + std::vector solution_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) { + 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. +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 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 = LLDB_INVALID_ADDRESS; + 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 +467,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); }