Index: lldb/include/lldb/API/SBFrame.h =================================================================== --- lldb/include/lldb/API/SBFrame.h +++ lldb/include/lldb/API/SBFrame.h @@ -90,6 +90,10 @@ bool IsInlined() const; + bool IsArtificial(); + + bool IsArtificial() const; + /// The version that doesn't supply a 'use_dynamic' value will use the /// target's default. lldb::SBValue EvaluateExpression(const char *expr); Index: lldb/include/lldb/Core/FormatEntity.h =================================================================== --- lldb/include/lldb/Core/FormatEntity.h +++ lldb/include/lldb/Core/FormatEntity.h @@ -88,6 +88,7 @@ FrameRegisterFP, FrameRegisterFlags, FrameRegisterByName, + FrameIsArtificial, ScriptFrame, FunctionID, FunctionDidChange, 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-calling 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 @@ -35,9 +35,9 @@ /// This base class provides an interface to stack frames. /// /// StackFrames may have a Canonical Frame Address (CFA) or not. -/// A frame may have a plain pc value or it may have a pc value + stop_id -/// to indicate a specific point in the debug session so the correct section -/// load list is used for symbolication. +/// A frame may have a plain pc value or it may indicate a specific point in +/// the debug session so the correct section load list is used for +/// symbolication. /// /// Local variables may be available, or not. A register context may be /// available, or not. @@ -54,14 +54,27 @@ eExpressionPathOptionsInspectAnonymousUnions = (1u << 5) }; + enum class Kind { + /// A regular stack frame with access to registers and local variables. + Regular, + + /// A historical stack frame -- possibly without CFA or registers or + /// local variables. + History, + + /// An artificial stack frame (e.g a synthesized result of inferring + /// missing tail call frames from a backtrace) with limited support for + /// local variables. + Artificial + }; + //------------------------------------------------------------------ /// Construct a StackFrame object without supplying a RegisterContextSP. /// /// This is the one constructor that doesn't take a RegisterContext /// parameter. This ctor may be called when creating a history StackFrame; /// these are used if we've collected a stack trace of pc addresses at some - /// point in the past. We may only have pc values. We may have pc values - /// and the stop_id when the stack trace was recorded. We may have a CFA, + /// point in the past. We may only have pc values. We may have a CFA, /// or more likely, we won't. /// /// @param [in] thread_sp @@ -92,23 +105,7 @@ /// @param [in] pc /// The current pc value of this stack frame. /// - /// @param [in] stop_id - /// The stop_id which should be used when looking up symbols for the pc - /// value, - /// if appropriate. This argument is ignored if stop_id_is_valid is false. - /// - /// @param [in] stop_id_is_valid - /// If the stop_id argument provided is not needed for this StackFrame, this - /// should be false. If this is a history stack frame and we know the - /// stop_id - /// when the pc value was collected, that stop_id should be provided and - /// this - /// will be true. - /// - /// @param [in] is_history_frame - /// If this is a historical stack frame -- possibly without CFA or registers - /// or - /// local variables -- then this should be set to true. + /// @param [in] frame_kind /// /// @param [in] sc_ptr /// Optionally seed the StackFrame with the SymbolContext information that @@ -117,8 +114,7 @@ //------------------------------------------------------------------ StackFrame(const lldb::ThreadSP &thread_sp, lldb::user_id_t frame_idx, lldb::user_id_t concrete_frame_idx, lldb::addr_t cfa, - bool cfa_is_valid, lldb::addr_t pc, uint32_t stop_id, - bool stop_id_is_valid, bool is_history_frame, + bool cfa_is_valid, lldb::addr_t pc, Kind frame_kind, const SymbolContext *sc_ptr); StackFrame(const lldb::ThreadSP &thread_sp, lldb::user_id_t frame_idx, @@ -402,6 +398,18 @@ //------------------------------------------------------------------ bool IsInlined(); + //------------------------------------------------------------------ + /// Query whether this frame is part of a historical backtrace. + //------------------------------------------------------------------ + bool IsHistorical() const; + + //------------------------------------------------------------------ + /// Query whether this frame is artificial (e.g a synthesized result of + /// inferring missing tail call frames from a backtrace). Artificial frames + /// may have limited support for inspecting variables. + //------------------------------------------------------------------ + bool IsArtificial() const; + //------------------------------------------------------------------ /// Query this frame to find what frame it is in this Thread's /// StackFrameList. @@ -412,6 +420,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. @@ -545,10 +558,7 @@ Status m_frame_base_error; bool m_cfa_is_valid; // Does this frame have a CFA? Different from CFA == // LLDB_INVALID_ADDRESS - uint32_t m_stop_id; - bool m_stop_id_is_valid; // Does this frame have a stop_id? Use it when - // referring to the m_frame_code_addr. - bool m_is_history_frame; + Kind m_stack_frame_kind; lldb::VariableListSP m_variable_list_sp; ValueObjectList m_variable_list_value_objects; // Value objects for each // variable in 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 -glldb -O1 -S -emit-llvm -x c -o %s -" % (compiler_path, f.name) + if os.popen(cmd).close() is not None: + return "Compiler can't compile with call site info enabled" + + with open(f.name, 'r') as ir_output_file: + buf = ir_output_file.read() + + if 'DIFlagAllCallsDescribed' not in buf: + return "Compiler did not introduce DIFlagAllCallsDescribed IR flag" + + return None + return skipTestIfFn(is_compiler_clang_with_call_site_info)(func) + def skipUnlessThreadSanitizer(func): """Decorate the item to skip test unless Clang -fsanitize=thread is supported.""" 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 += -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.filecheck("bt", "main.cpp", "-implicit-check-not=func{{[23]}}_amb") +} + +void __attribute__((noinline)) func3_amb() { sink(); /* tail */ } + +void __attribute__((noinline)) func2_amb() { sink(); /* tail */ } + +void __attribute__((noinline)) func1() { + if (x > 0) + func2_amb(); /* tail */ + else + func3_amb(); /* tail */ +} + +int __attribute__((disable_tail_calls)) main(int argc, char **) { + // The sequences `main -> func1 -> f{2,3}_amb -> sink` are both plausible. Test + // that lldb doesn't attempt to guess which one occurred. + func1(); + return 0; +} 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 += -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.filecheck("bt", "main.cpp", "-implicit-check-not=func{{[23]}}") +} + +void func2(); + +void __attribute__((noinline)) func1() { + if (x < 1) + func2(); + else + sink(); +} + +void __attribute__((noinline)) func2() { + if (x < 1) + sink(); + else + func1(); +} + +int main() { + // Tail recursion creates ambiguous execution histories. + x = 0; + func1(); + return 0; +} 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 += -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,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.filecheck("bt", "main.cpp", "-implicit-check-not=artificial") + // CHECK: frame #0: 0x{{[0-9a-f]+}} a.out`sink() at main.cpp:[[@LINE-1]]:4 [opt] + // CHECK-NEXT: frame #1: 0x{{[0-9a-f]+}} a.out`func2{{.*}} [opt] [artificial] + // CHECK-NEXT: frame #2: 0x{{[0-9a-f]+}} a.out`main{{.*}} [opt] +} + +void __attribute__((noinline)) func2() { + sink(); /* tail */ +} + +void __attribute__((noinline)) func1() { sink(); /* tail */ } + +int __attribute__((disable_tail_calls)) main(int argc, char **) { + // The sequences `main -> f{1,2} -> sink` are both plausible. Test that + // return-pc call site info allows lldb to pick the correct sequence. + func2(); + if (argc == 100) + func1(); + return 0; +} 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 += -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,31 @@ +//===-- main.cpp ------------------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +volatile int x; + +void __attribute__((noinline)) sink() { + x++; //% self.filecheck("bt", "main.cpp", "-implicit-check-not=artificial") + // CHECK: frame #0: 0x{{[0-9a-f]+}} a.out`sink() at main.cpp:[[@LINE-1]]:4 [opt] + // CHECK-NEXT: frame #1: 0x{{[0-9a-f]+}} a.out`func3{{.*}} [opt] [artificial] + // CHECK-NEXT: frame #2: 0x{{[0-9a-f]+}} a.out`func1{{.*}} [opt] [artificial] + // CHECK-NEXT: frame #3: 0x{{[0-9a-f]+}} a.out`main{{.*}} [opt] +} + +void __attribute__((noinline)) func3() { sink(); /* tail */ } + +void __attribute__((noinline)) func2() { sink(); /* tail */ } + +void __attribute__((noinline)) func1() { func3(); /* tail */ } + +int __attribute__((disable_tail_calls)) main(int argc, char **) { + // The sequences `main -> func1 -> f{2,3} -> sink` are both plausible. Test + // that lldb picks the latter sequence. + func1(); + return 0; +} Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/sbapi_support/Makefile =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/sbapi_support/Makefile @@ -0,0 +1,4 @@ +LEVEL = ../../../make +CXX_SOURCES := main.cpp +include $(LEVEL)/Makefile.rules +CXXFLAGS += -g -O1 -glldb Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/sbapi_support/TestTailCallFrameSBAPI.py =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/sbapi_support/TestTailCallFrameSBAPI.py @@ -0,0 +1,65 @@ +""" +Test SB API support for identifying artificial (tail call) frames. +""" + +import lldb +import lldbsuite.test.lldbutil as lldbutil +from lldbsuite.test.lldbtest import * + +class TestTailCallFrameSBAPI(TestBase): + mydir = TestBase.compute_mydir(__file__) + + # If your test case doesn't stress debug info, the + # set this to true. That way it won't be run once for + # each debug info format. + NO_DEBUG_INFO_TESTCASE = True + + def test_tail_call_frame_sbapi(self): + self.build() + self.do_test() + + def setUp(self): + # Call super's setUp(). + TestBase.setUp(self) + + def do_test(self): + exe = self.getBuildArtifact("a.out") + + # Create a target by the debugger. + target = self.dbg.CreateTarget(exe) + self.assertTrue(target, VALID_TARGET) + + breakpoint = target.BreakpointCreateBySourceRegex("break here", + lldb.SBFileSpec("main.cpp")) + self.assertTrue(breakpoint and + breakpoint.GetNumLocations() == 1, + VALID_BREAKPOINT) + + error = lldb.SBError() + launch_info = lldb.SBLaunchInfo(None) + process = target.Launch(launch_info, error) + self.assertTrue(process, PROCESS_IS_VALID) + + # Did we hit our breakpoint? + threads = lldbutil.get_threads_stopped_at_breakpoint(process, + breakpoint) + self.assertTrue( + len(threads) == 1, + "There should be a thread stopped at our breakpoint") + + self.assertTrue(breakpoint.GetHitCount() == 1) + + thread = threads[0] + + # Here's what we expect to see: + # frame #0: ... a.out`sink() at main.cpp:13:4 [opt] + # frame #1: ... a.out`func3() at main.cpp:14:1 [opt] [artificial] + # frame #2: ... a.out`func2() at main.cpp:18:62 [opt] + # frame #3: ... a.out`func1() at main.cpp:18:85 [opt] [artificial] + # frame #4: ... a.out`main at main.cpp:23:3 [opt] + names = ["sink()", "func3()", "func2()", "func1()", "main"] + artificiality = [False, True, False, True, False] + for idx, (name, is_artificial) in enumerate(zip(names, artificiality)): + frame = thread.GetFrameAtIndex(idx) + self.assertTrue(frame.GetDisplayFunctionName() == name) + self.assertTrue(frame.IsArtificial() == is_artificial) Index: lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/sbapi_support/main.cpp =================================================================== --- /dev/null +++ lldb/packages/Python/lldbsuite/test/functionalities/tail_call_frames/sbapi_support/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++; /* break here */ +} + +void __attribute__((noinline)) func3() { sink(); /* tail */ } + +void __attribute__((disable_tail_calls, noinline)) func2() { func3(); /* regular */ } + +void __attribute__((noinline)) func1() { func2(); /* tail */ } + +int __attribute__((disable_tail_calls)) main() { + func1(); /* regular */ + return 0; +} 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 += -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,30 @@ +//===-- main.cpp ------------------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +volatile int x; + +void __attribute__((noinline)) sink() { + x++; //% self.filecheck("bt", "main.cpp", "-implicit-check-not=artificial") + // CHECK: frame #0: 0x{{[0-9a-f]+}} a.out`sink() at main.cpp:[[@LINE-1]]:4 [opt] + // CHECK-NEXT: frame #1: 0x{{[0-9a-f]+}} a.out`func3{{.*}} [opt] [artificial] + // CHECK-NEXT: frame #2: 0x{{[0-9a-f]+}} a.out`func2{{.*}} [opt] + // CHECK-NEXT: frame #3: 0x{{[0-9a-f]+}} a.out`func1{{.*}} [opt] [artificial] + // CHECK-NEXT: frame #4: 0x{{[0-9a-f]+}} a.out`main{{.*}} [opt] +} + +void __attribute__((noinline)) func3() { sink(); /* tail */ } + +void __attribute__((disable_tail_calls, noinline)) func2() { func3(); /* regular */ } + +void __attribute__((noinline)) func1() { func2(); /* tail */ } + +int __attribute__((disable_tail_calls)) main() { + func1(); /* regular */ + return 0; +} Index: lldb/scripts/interface/SBFrame.i =================================================================== --- lldb/scripts/interface/SBFrame.i +++ lldb/scripts/interface/SBFrame.i @@ -153,6 +153,17 @@ bool IsInlined() const; + %feature("docstring", " + /// Return true if this frame is artificial (e.g a frame synthesized to + /// capture a tail call). Local variables may not be available in an artificial + /// frame. + ") IsArtificial; + bool + IsArtificial(); + + bool + IsArtificial() const; + %feature("docstring", " /// The version that doesn't supply a 'use_dynamic' value will use the /// target's default. Index: lldb/source/API/SBFrame.cpp =================================================================== --- lldb/source/API/SBFrame.cpp +++ lldb/source/API/SBFrame.cpp @@ -1366,6 +1366,21 @@ return false; } +bool SBFrame::IsArtificial() { + return static_cast(this)->IsArtificial(); +} + +bool SBFrame::IsArtificial() const { + std::unique_lock lock; + ExecutionContext exe_ctx(m_opaque_sp.get(), lock); + + StackFrame *frame = exe_ctx.GetFramePtr(); + if (frame) + return frame->IsArtificial(); + + return false; +} + const char *SBFrame::GetFunctionName() { return static_cast(this)->GetFunctionName(); } Index: lldb/source/Core/Debugger.cpp =================================================================== --- lldb/source/Core/Debugger.cpp +++ lldb/source/Core/Debugger.cpp @@ -125,6 +125,8 @@ "{ at ${line.file.basename}:${line.number}{:${line.column}}}" #define IS_OPTIMIZED "{${function.is-optimized} [opt]}" +#define IS_ARTIFICIAL "{${frame.is-artificial} [artificial]}" + #define DEFAULT_THREAD_FORMAT \ "thread #${thread.index}: tid = ${thread.id%tid}" \ "{, ${frame.pc}}" MODULE_WITH_FUNC FILE_AND_LINE \ @@ -149,11 +151,11 @@ #define DEFAULT_FRAME_FORMAT \ "frame #${frame.index}: ${frame.pc}" MODULE_WITH_FUNC FILE_AND_LINE \ - IS_OPTIMIZED "\\n" + IS_OPTIMIZED IS_ARTIFICIAL "\\n" #define DEFAULT_FRAME_FORMAT_NO_ARGS \ "frame #${frame.index}: ${frame.pc}" MODULE_WITH_FUNC_NO_ARGS FILE_AND_LINE \ - IS_OPTIMIZED "\\n" + IS_OPTIMIZED IS_ARTIFICIAL "\\n" // Three parts to this disassembly format specification: // 1. If this is a new function/symbol (no previous symbol/function), print Index: lldb/source/Core/FormatEntity.cpp =================================================================== --- lldb/source/Core/FormatEntity.cpp +++ lldb/source/Core/FormatEntity.cpp @@ -128,6 +128,7 @@ ENTRY("flags", FrameRegisterFlags, UInt64), ENTRY("no-debug", FrameNoDebug, None), ENTRY_CHILDREN("reg", FrameRegisterByName, UInt64, g_string_entry), + ENTRY("is-artificial", FrameIsArtificial, UInt32), }; static FormatEntity::Entry::Definition g_function_child_entries[] = { @@ -357,6 +358,7 @@ ENUM_TO_CSTR(FrameRegisterFP); ENUM_TO_CSTR(FrameRegisterFlags); ENUM_TO_CSTR(FrameRegisterByName); + ENUM_TO_CSTR(FrameIsArtificial); ENUM_TO_CSTR(ScriptFrame); ENUM_TO_CSTR(FunctionID); ENUM_TO_CSTR(FunctionDidChange); @@ -1489,6 +1491,13 @@ } return false; + case Entry::Type::FrameIsArtificial: { + if (exe_ctx) + if (StackFrame *frame = exe_ctx->GetFramePtr()) + return frame->IsArtificial(); + return false; + } + case Entry::Type::ScriptFrame: if (exe_ctx) { StackFrame *frame = exe_ctx->GetFramePtr(); Index: lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h =================================================================== --- lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h +++ lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h @@ -317,6 +317,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 @@ -3740,6 +3740,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,60 @@ return FunctionInfo::MemorySize() + m_mangled.MemorySize(); } +//---------------------------------------------------------------------- +// +//---------------------------------------------------------------------- +CallEdge::CallEdge(const char *mangled_name, lldb::addr_t return_pc) + : resolved(false), return_pc(return_pc) { + lazy_callee.mangled_name = mangled_name; +} + +void CallEdge::ParseSymbolFileAndResolve(ModuleList &images) { + if (resolved) + return; + + Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_STEP)); + LLDB_LOG(log, "CallEdge: Lazily parsing the call graph for {0}", + lazy_callee.mangled_name); + + auto resolve_lazy_callee = [&]() -> Function * { + ConstString callee_name{lazy_callee.mangled_name}; + SymbolContextList sc_list; + size_t num_matches = + images.FindFunctionSymbols(callee_name, eFunctionNameTypeAuto, sc_list); + if (num_matches != 1 || !sc_list[0].symbol) { + LLDB_LOG(log, "CallEdge: Found {0} symbols for {1}, cannot resolve it", + num_matches, callee_name); + return nullptr; + } + Address callee_addr = sc_list[0].symbol->GetAddress(); + if (!callee_addr.IsValid()) { + LLDB_LOG(log, "CallEdge: Invalid symbol address"); + return nullptr; + } + Function *f = callee_addr.CalculateSymbolContextFunction(); + if (!f) { + LLDB_LOG(log, "CallEdge: Could not find complete function"); + return nullptr; + } + return f; + }; + lazy_callee.def = resolve_lazy_callee(); + resolved = true; +} + +Function *CallEdge::GetCallee(ModuleList &images) { + ParseSymbolFileAndResolve(images); + return lazy_callee.def; +} + +lldb::addr_t CallEdge::GetReturnPCAddress(Function &caller, + Target &target) const { + const Address &base = caller.GetAddressRange().GetBaseAddress(); + Address return_pc_addr{base.GetSection(), return_pc}; + return return_pc_addr.GetLoadAddress(&target); +} + //---------------------------------------------------------------------- // //---------------------------------------------------------------------- @@ -192,6 +248,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/StackFrame.cpp =================================================================== --- lldb/source/Target/StackFrame.cpp +++ lldb/source/Target/StackFrame.cpp @@ -49,20 +49,18 @@ StackFrame::StackFrame(const ThreadSP &thread_sp, user_id_t frame_idx, user_id_t unwind_frame_index, addr_t cfa, - bool cfa_is_valid, addr_t pc, uint32_t stop_id, - bool stop_id_is_valid, bool is_history_frame, + bool cfa_is_valid, addr_t pc, StackFrame::Kind kind, const SymbolContext *sc_ptr) : m_thread_wp(thread_sp), m_frame_index(frame_idx), m_concrete_frame_index(unwind_frame_index), m_reg_context_sp(), m_id(pc, cfa, nullptr), m_frame_code_addr(pc), m_sc(), m_flags(), m_frame_base(), m_frame_base_error(), m_cfa_is_valid(cfa_is_valid), - m_stop_id(stop_id), m_stop_id_is_valid(stop_id_is_valid), - m_is_history_frame(is_history_frame), m_variable_list_sp(), + m_stack_frame_kind(kind), m_variable_list_sp(), m_variable_list_value_objects(), m_disassembly(), m_mutex() { // If we don't have a CFA value, use the frame index for our StackID so that // recursive functions properly aren't confused with one another on a history // stack. - if (m_is_history_frame && !m_cfa_is_valid) { + if (IsHistorical() && !m_cfa_is_valid) { m_id.SetCFA(m_frame_index); } @@ -80,10 +78,9 @@ m_concrete_frame_index(unwind_frame_index), m_reg_context_sp(reg_context_sp), m_id(pc, cfa, nullptr), m_frame_code_addr(pc), m_sc(), m_flags(), m_frame_base(), - m_frame_base_error(), m_cfa_is_valid(true), m_stop_id(0), - m_stop_id_is_valid(false), m_is_history_frame(false), - m_variable_list_sp(), m_variable_list_value_objects(), m_disassembly(), - m_mutex() { + m_frame_base_error(), m_cfa_is_valid(true), + m_stack_frame_kind(StackFrame::Kind::Regular), m_variable_list_sp(), + m_variable_list_value_objects(), m_disassembly(), m_mutex() { if (sc_ptr != nullptr) { m_sc = *sc_ptr; m_flags.Set(m_sc.GetResolvedMask()); @@ -106,10 +103,9 @@ m_id(pc_addr.GetLoadAddress(thread_sp->CalculateTarget().get()), cfa, nullptr), m_frame_code_addr(pc_addr), m_sc(), m_flags(), m_frame_base(), - m_frame_base_error(), m_cfa_is_valid(true), m_stop_id(0), - m_stop_id_is_valid(false), m_is_history_frame(false), - m_variable_list_sp(), m_variable_list_value_objects(), m_disassembly(), - m_mutex() { + m_frame_base_error(), m_cfa_is_valid(true), + m_stack_frame_kind(StackFrame::Kind::Regular), m_variable_list_sp(), + m_variable_list_value_objects(), m_disassembly(), m_mutex() { if (sc_ptr != nullptr) { m_sc = *sc_ptr; m_flags.Set(m_sc.GetResolvedMask()); @@ -210,7 +206,7 @@ bool StackFrame::ChangePC(addr_t pc) { std::lock_guard guard(m_mutex); // We can't change the pc value of a history stack frame - it is immutable. - if (m_is_history_frame) + if (IsHistorical()) return false; m_frame_code_addr.SetRawAddress(pc); m_sc.Clear(false); @@ -456,7 +452,7 @@ bool must_have_valid_location) { std::lock_guard guard(m_mutex); // We can't fetch variable information for a history stack frame. - if (m_is_history_frame) + if (IsHistorical()) return VariableListSP(); VariableListSP var_list_sp(new VariableList); @@ -490,7 +486,7 @@ VariableSP &var_sp, Status &error) { llvm::StringRef original_var_expr = var_expr; // We can't fetch variable information for a history stack frame. - if (m_is_history_frame) + if (IsHistorical()) return ValueObjectSP(); if (var_expr.empty()) { @@ -1135,7 +1131,7 @@ DynamicValueType use_dynamic) { std::lock_guard guard(m_mutex); ValueObjectSP valobj_sp; - if (m_is_history_frame) { + if (IsHistorical()) { return valobj_sp; } VariableList *var_list = GetVariableList(true); @@ -1164,7 +1160,7 @@ ValueObjectSP StackFrame::TrackGlobalVariable(const VariableSP &variable_sp, DynamicValueType use_dynamic) { std::lock_guard guard(m_mutex); - if (m_is_history_frame) + if (IsHistorical()) return ValueObjectSP(); // Check to make sure we aren't already tracking this variable? @@ -1194,6 +1190,14 @@ return false; } +bool StackFrame::IsHistorical() const { + return m_stack_frame_kind == StackFrame::Kind::History; +} + +bool StackFrame::IsArtificial() const { + return m_stack_frame_kind == StackFrame::Kind::Artificial; +} + lldb::LanguageType StackFrame::GetLanguage() { CompileUnit *cu = GetSymbolContext(eSymbolContextCompUnit).comp_unit; if (cu) 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,162 @@ 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. +/// +/// -------------- +/// | ... | <- Completed frames. +/// -------------- +/// | prev_frame | +/// -------------- +/// | ... | <- Artificial frames inserted here. +/// -------------- +/// | next_frame | +/// -------------- +/// | ... | <- Not-yet-visited frames. +/// -------------- +void StackFrameList::SynthesizeTailCallFrames(StackFrame &next_frame) { + TargetSP target_sp = next_frame.CalculateTarget(); + if (!target_sp) + return; + + lldb::RegisterContextSP next_reg_ctx_sp = next_frame.GetRegisterContext(); + if (!next_reg_ctx_sp) + return; + + Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_STEP)); + + assert(!m_frames.empty() && "Cannot synthesize frames in an empty stack"); + StackFrame &prev_frame = *m_frames.back().get(); + + // Find the functions prev_frame and next_frame are stopped in. The function + // objects are needed to search the lazy call graph for intervening frames. + Function *prev_func = + prev_frame.GetSymbolContext(eSymbolContextFunction).function; + if (!prev_func) + return; + Function *next_func = + next_frame.GetSymbolContext(eSymbolContextFunction).function; + if (!next_func) + return; + + // Try to find the unique sequence of (tail) calls which led from next_frame + // to prev_frame. + std::vector path; + addr_t call_pc = next_reg_ctx_sp->GetPC(); + Target &target = *target_sp.get(); + ModuleList &images = next_frame.CalculateTarget()->GetImages(); + FindInterveningFrames(*next_func, *prev_func, target, call_pc, path, images, + log); + + // Push synthetic tail call frames. + for (Function *callee : llvm::reverse(path)) { + uint32_t frame_idx = m_frames.size(); + uint32_t concrete_frame_idx = next_frame.GetConcreteFrameIndex(); + addr_t cfa = LLDB_INVALID_ADDRESS; + bool cfa_is_valid = false; + addr_t pc = + callee->GetAddressRange().GetBaseAddress().GetLoadAddress(&target); + SymbolContext sc; + callee->CalculateSymbolContext(&sc); + StackFrameSP synth_frame{new StackFrame( + m_thread.shared_from_this(), frame_idx, concrete_frame_idx, cfa, + cfa_is_valid, pc, StackFrame::Kind::Artificial, &sc)}; + m_frames.push_back(synth_frame); + LLDB_LOG(log, "Pushed frame {0}", callee->GetDisplayName()); + } + + // If any frames were created, adjust next_frame's index. + if (!path.empty()) + next_frame.SetFrameIndex(m_frames.size()); +} + void StackFrameList::GetFramesUpTo(uint32_t end_idx) { // Do not fetch frames for an invalid thread. if (!m_thread.IsValid()) @@ -315,11 +472,15 @@ break; } const bool cfa_is_valid = true; - const bool stop_id_is_valid = false; - const bool is_history_frame = false; - unwind_frame_sp.reset(new StackFrame( - m_thread.shared_from_this(), m_frames.size(), idx, cfa, cfa_is_valid, - pc, 0, stop_id_is_valid, is_history_frame, nullptr)); + unwind_frame_sp.reset( + new StackFrame(m_thread.shared_from_this(), m_frames.size(), idx, cfa, + cfa_is_valid, pc, StackFrame::Kind::Regular, nullptr)); + + // Create synthetic tail call frames between the previous frame and the + // newly-found frame. The new frame's index may change after this call, + // although its concrete index will stay the same. + SynthesizeTailCallFrames(*unwind_frame_sp.get()); + m_frames.push_back(unwind_frame_sp); } @@ -491,11 +652,9 @@ addr_t pc, cfa; if (unwinder->GetFrameInfoAtIndex(idx, cfa, pc)) { const bool cfa_is_valid = true; - const bool stop_id_is_valid = false; - const bool is_history_frame = false; - frame_sp.reset(new StackFrame( - m_thread.shared_from_this(), idx, idx, cfa, cfa_is_valid, pc, 0, - stop_id_is_valid, is_history_frame, nullptr)); + frame_sp.reset(new StackFrame(m_thread.shared_from_this(), idx, idx, + cfa, cfa_is_valid, pc, + StackFrame::Kind::Regular, nullptr)); Function *function = frame_sp->GetSymbolContext(eSymbolContextFunction).function;