[lldb/DWARF] Use DW_AT_call_pc to determine artificial frame address

[vsk]

Summary

lldb currently guesses the address to use when creating an artificial
frame (i.e., a frame constructed by determining the sequence of (tail)
calls which must have happened).

Guessing the address creates problems -- use the actual address provided
by the DW_AT_call_pc attribute instead.

Depends on D76336.

rdar://60307600

[jasonmolenda]

Nice fix, this looks good to me but I haven't been following this area of code too closely before now.

[vsk]

I'll land this shortly if there aren't any objections.

lldb/include/lldb/Symbol/Function.h

public:
   /// 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; }
 
+  /// Get the load PC address of the call instruction (or LLDB_INVALID_ADDRESS).
+  lldb::addr_t GetCallInstPC(Function &caller, Target &target) const;
+
   /// Get the call site parameters available at this call edge.
   llvm::ArrayRef<CallSiteParameter> GetCallSiteParameters() const {
     return parameters;
   }
 
 protected:
-  CallEdge(lldb::addr_t return_pc, CallSiteParameterArray &&parameters)
-      : return_pc(return_pc), parameters(std::move(parameters)) {}
+  CallEdge(lldb::addr_t return_pc, lldb::addr_t call_inst_pc,
+           CallSiteParameterArray &&parameters)
+      : return_pc(return_pc), call_inst_pc(call_inst_pc),
+        parameters(std::move(parameters)) {}
+
+  /// Helper that finds the load address of \p unresolved_pc, a file address
+  /// which refers to an instruction within \p caller.
+  static lldb::addr_t GetLoadAddress(lldb::addr_t unresolved_pc,
+                                     Function &caller, Target &target);
 
   /// 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;
 
+  /// The address of the call instruction. Usually an invalid address, unless
+  /// this is a tail call.
+  lldb::addr_t call_inst_pc;
+
   CallSiteParameterArray parameters;
 };
 
 /// A direct call site. Used to represent call sites where the address of the
 /// callee is fixed (e.g. a function call in C in which the call target is not
 /// a function pointer).
 class DirectCallEdge : public CallEdge {
 public:
   /// Construct a call edge using a symbol name to identify the callee, and a
   /// return PC within the calling function to identify a specific call site.
   DirectCallEdge(const char *symbol_name, lldb::addr_t return_pc,
-                 CallSiteParameterArray &&parameters)
-      : CallEdge(return_pc, std::move(parameters)) {
+                 lldb::addr_t call_inst_pc, CallSiteParameterArray &&parameters)
+      : CallEdge(return_pc, call_inst_pc, std::move(parameters)) {
     lazy_callee.symbol_name = symbol_name;
   }
 
   Function *GetCallee(ModuleList &images, ExecutionContext &exe_ctx) override;
 
 private:
   void ParseSymbolFileAndResolve(ModuleList &images);
 

 /// An indirect call site. Used to represent call sites where the address of
 /// the callee is not fixed, e.g. a call to a C++ virtual function (where the
 /// address is loaded out of a vtable), or a call to a function pointer in C.
 class IndirectCallEdge : public CallEdge {
 public:
   /// Construct a call edge using a DWARFExpression to identify the callee, and
   /// a return PC within the calling function to identify a specific call site.
   IndirectCallEdge(DWARFExpression call_target, lldb::addr_t return_pc,
+                   lldb::addr_t call_inst_pc,
                    CallSiteParameterArray &&parameters)
-      : CallEdge(return_pc, std::move(parameters)),
+      : CallEdge(return_pc, call_inst_pc, std::move(parameters)),
         call_target(std::move(call_target)) {}
 
   Function *GetCallee(ModuleList &images, ExecutionContext &exe_ctx) override;
 
 private:
   // Used to describe an indirect call.
   //
   // Specifies the location of the callee address in the calling frame.

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

SymbolFileDWARF::CollectCallEdges(ModuleSP module, DWARFDIE function_die) {
   for (DWARFDIE child = function_die.GetFirstChild(); child.IsValid();
        child = child.GetSibling()) {
     if (child.Tag() != DW_TAG_call_site)
       continue;
 
     llvm::Optional<DWARFDIE> call_origin;
     llvm::Optional<DWARFExpression> call_target;
     addr_t return_pc = LLDB_INVALID_ADDRESS;
+    addr_t call_inst_pc = LLDB_INVALID_ADDRESS;
 
     DWARFAttributes attributes;
     const size_t num_attributes = child.GetAttributes(attributes);
     for (size_t i = 0; i < num_attributes; ++i) {
       DWARFFormValue form_value;
       if (!attributes.ExtractFormValueAtIndex(i, form_value)) {
         LLDB_LOG(log, "CollectCallEdges: Could not extract TAG_call_site form");
         break;
for (size_t i = 0; i < num_attributes; ++i) {
       }
 
       // Extract DW_AT_call_return_pc (the PC the call returns to) if it's
       // available. It should only ever be unavailable for tail call edges, in
       // which case use LLDB_INVALID_ADDRESS.
       if (attr == DW_AT_call_return_pc)
         return_pc = form_value.Address();
 
+      // Extract DW_AT_call_pc (the PC at the call/branch instruction). It
+      // should only ever be unavailable for non-tail calls, in which case use
+      // LLDB_INVALID_ADDRESS.
+      if (attr == DW_AT_call_pc)
+        call_inst_pc = form_value.Address();
+
       // Extract DW_AT_call_target (the location of the address of the indirect
       // call).
       if (attr == DW_AT_call_target) {
         if (!DWARFFormValue::IsBlockForm(form_value.Form())) {
           LLDB_LOG(log,
                    "CollectCallEdges: AT_call_target does not have block form");
           break;
         }
 
         auto data = child.GetData();
         uint32_t block_offset = form_value.BlockData() - data.GetDataStart();
         uint32_t block_length = form_value.Unsigned();
         call_target = DWARFExpression(
             module, DataExtractor(data, block_offset, block_length),
             child.GetCU());
       }
     }
     if (!call_origin && !call_target) {
       LLDB_LOG(log, "CollectCallEdges: call site without any call target");
       continue;
     }
 
-    // Adjust the return PC. It needs to be fixed up if the main executable
+    // Adjust any PC forms. It needs to be fixed up if the main executable
     // contains a debug map (i.e. pointers to object files), because we need a
     // file address relative to the executable's text section.
     return_pc = FixupAddress(return_pc);
+    call_inst_pc = FixupAddress(call_inst_pc);
 
     // Extract call site parameters.
     CallSiteParameterArray parameters =
         CollectCallSiteParameters(module, child);
 
     std::unique_ptr<CallEdge> edge;
     if (call_origin) {
-      LLDB_LOG(log, "CollectCallEdges: Found call origin: {0} (retn-PC: {1:x})",
-               call_origin->GetPubname(), return_pc);
+      LLDB_LOG(log,
+               "CollectCallEdges: Found call origin: {0} (retn-PC: {1:x}) "
+               "(call-PC: {2:x})",
+               call_origin->GetPubname(), return_pc, call_inst_pc);
       edge = std::make_unique<DirectCallEdge>(call_origin->GetMangledName(),
-                                              return_pc, std::move(parameters));
+                                              return_pc, call_inst_pc,
+                                              std::move(parameters));
     } else {
       if (log) {
         StreamString call_target_desc;
         call_target->GetDescription(&call_target_desc, eDescriptionLevelBrief,
                                     LLDB_INVALID_ADDRESS, nullptr);
         LLDB_LOG(log, "CollectCallEdges: Found indirect call target: {0}",
                  call_target_desc.GetString());
       }
-      edge = std::make_unique<IndirectCallEdge>(*call_target, return_pc,
-                                                std::move(parameters));
+      edge = std::make_unique<IndirectCallEdge>(
+          *call_target, return_pc, call_inst_pc, std::move(parameters));
     }
 
     if (log && parameters.size()) {
       for (const CallSiteParameter &param : parameters) {
         StreamString callee_loc_desc, caller_loc_desc;
         param.LocationInCallee.GetDescription(&callee_loc_desc,
                                               eDescriptionLevelBrief,
                                               LLDB_INVALID_ADDRESS, nullptr);

lldb/source/Symbol/Function.cpp

 
 size_t InlineFunctionInfo::MemorySize() const {
   return FunctionInfo::MemorySize() + m_mangled.MemorySize();
 }
 
 /// @name Call site related structures
 /// @{
 
-lldb::addr_t CallEdge::GetReturnPCAddress(Function &caller,
-                                          Target &target) const {
+lldb::addr_t CallEdge::GetLoadAddress(lldb::addr_t unresolved_pc,
+                                      Function &caller, Target &target) {
   Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_STEP));
 
   const Address &caller_start_addr = caller.GetAddressRange().GetBaseAddress();
 
   ModuleSP caller_module_sp = caller_start_addr.GetModule();
   if (!caller_module_sp) {
-    LLDB_LOG(log, "GetReturnPCAddress: cannot get Module for caller");
+    LLDB_LOG(log, "GetLoadAddress: cannot get Module for caller");
     return LLDB_INVALID_ADDRESS;
   }
 
   SectionList *section_list = caller_module_sp->GetSectionList();
   if (!section_list) {
-    LLDB_LOG(log, "GetReturnPCAddress: cannot get SectionList for Module");
+    LLDB_LOG(log, "GetLoadAddress: cannot get SectionList for Module");
     return LLDB_INVALID_ADDRESS;
   }
 
-  Address return_pc_addr = Address(return_pc, section_list);
-  lldb::addr_t ret_addr = return_pc_addr.GetLoadAddress(&target);
-  return ret_addr;
+  Address the_addr = Address(unresolved_pc, section_list);
+  lldb::addr_t load_addr = the_addr.GetLoadAddress(&target);
+  return load_addr;
+}
+
+lldb::addr_t CallEdge::GetReturnPCAddress(Function &caller,
+                                          Target &target) const {
+  return GetLoadAddress(return_pc, caller, target);
+}
+
+lldb::addr_t CallEdge::GetCallInstPC(Function &caller, Target &target) const {
+  return GetLoadAddress(call_inst_pc, caller, target);
 }
 
 void DirectCallEdge::ParseSymbolFileAndResolve(ModuleList &images) {
   if (resolved)
     return;
 
   Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_STEP));
   LLDB_LOG(log, "DirectCallEdge: Lazily parsing the call graph for {0}",

lldb/source/Target/StackFrameList.cpp

if (num_frames <= end_idx + 1) {
     m_concrete_frames_fetched = UINT32_MAX;
   }
 
   // Don't create the frames eagerly. Defer this work to GetFrameAtIndex,
   // which can lazily query the unwinder to create frames.
   m_frames.resize(num_frames);
 }
 
+/// A sequence of calls that comprise some portion of a backtrace. Each frame
+/// is represented as a pair of a callee (Function *) and an address within the
+/// callee.
+using CallSequence = std::vector<std::pair<Function *, addr_t>>;
+
 /// Find the unique path through the call graph from \p begin (with return PC
 /// \p return_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,
                                   ExecutionContext &exe_ctx, Target &target,
-                                  addr_t return_pc,
-                                  std::vector<Function *> &path,
+                                  addr_t return_pc, CallSequence &path,
                                   ModuleList &images, Log *log) {
   LLDB_LOG(log, "Finding frames between {0} and {1}, retn-pc={2:x}",
            begin.GetDisplayName(), end.GetDisplayName(), return_pc);
 
   // Find a non-tail calling edge with the correct return PC.
   if (log)
     for (const auto &edge : begin.GetCallEdges())
       LLDB_LOG(log, "FindInterveningFrames: found call with retn-PC = {0:x}",
LLDB_LOG(log, "Not searching further, first callee is {0} (retn-PC: {1:x})",
              end.GetDisplayName(), return_pc);
     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<Function *> active_path = {};
-    std::vector<Function *> solution_path = {};
+    CallSequence active_path = {};
+    CallSequence solution_path = {};
     llvm::SmallPtrSet<Function *, 2> visited_nodes = {};
     bool ambiguous = false;
     Function *end;
     ModuleList &images;
+    Target &target;
     ExecutionContext &context;
 
-    DFS(Function *end, ModuleList &images, ExecutionContext &context)
-        : end(end), images(images), context(context) {}
-
-    void search(Function &first_callee, std::vector<Function *> &path) {
-      dfs(first_callee);
+    DFS(Function *end, ModuleList &images, Target &target,
+        ExecutionContext &context)
+        : end(end), images(images), target(target), context(context) {}
+
+    void search(CallEdge &first_edge, Function &first_callee,
+                CallSequence &path) {
+      dfs(first_edge, first_callee);
       if (!ambiguous)
         path = std::move(solution_path);
     }
 
-    void dfs(Function &callee) {
+    void dfs(CallEdge &current_edge, 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);
+      active_path.emplace_back(&callee, LLDB_INVALID_ADDRESS);
       for (const auto &edge : callee.GetTailCallingEdges()) {
         Function *next_callee = edge->GetCallee(images, context);
         if (!next_callee)
           continue;
 
-        dfs(*next_callee);
+        addr_t tail_call_pc = edge->GetCallInstPC(callee, target);
+        active_path.back().second = tail_call_pc;
+
+        dfs(*edge, *next_callee);
         if (ambiguous)
           return;
       }
       active_path.pop_back();
     }
   };
 
-  DFS(&end, images, exe_ctx).search(*first_callee, path);
+  DFS(&end, images, target, exe_ctx).search(*first_edge, *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.
Function *next_func =
       next_frame.GetSymbolContext(eSymbolContextFunction).function;
   if (!next_func) {
     LLDB_LOG(log, "SynthesizeTailCallFrames: can't find next function");
     return;
   }
 
   // Try to find the unique sequence of (tail) calls which led from next_frame
   // to prev_frame.
-  std::vector<Function *> path;
+  CallSequence path;
   addr_t return_pc = next_reg_ctx_sp->GetPC();
   Target &target = *target_sp.get();
   ModuleList &images = next_frame.CalculateTarget()->GetImages();
   ExecutionContext exe_ctx(target_sp, /*get_process=*/true);
   exe_ctx.SetFramePtr(&next_frame);
   FindInterveningFrames(*next_func, *prev_func, exe_ctx, target, return_pc,
                         path, images, log);
 
   // Push synthetic tail call frames.
-  for (Function *callee : llvm::reverse(path)) {
+  for (auto calleeInfo : llvm::reverse(path)) {
+    Function *callee = calleeInfo.first;
     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);
+    addr_t pc = calleeInfo.second;
     constexpr bool behaves_like_zeroth_frame = false;
     SymbolContext sc;
     callee->CalculateSymbolContext(&sc);
     auto synth_frame = std::make_shared<StackFrame>(
         m_thread.shared_from_this(), frame_idx, concrete_frame_idx, cfa,
         cfa_is_valid, pc, StackFrame::Kind::Artificial,
         behaves_like_zeroth_frame, &sc);
     m_frames.push_back(synth_frame);
-    LLDB_LOG(log, "Pushed frame {0}", callee->GetDisplayName());
+    LLDB_LOG(log, "Pushed frame {0} at {1:x}", callee->GetDisplayName(), pc);
   }
 
   // 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) {

lldb/test/API/functionalities/tail_call_frames/unambiguous_sequence/main.cpp

 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 #1: 0x{{[0-9a-f]+}} a.out`func3() at main.cpp:14:3 [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() at main.cpp:23:3 [opt] [artificial]
   // CHECK-NEXT: frame #4: 0x{{[0-9a-f]+}} a.out`main{{.*}} [opt]
 }
 
-void __attribute__((noinline)) func3() { sink(); /* tail */ }
+void __attribute__((noinline)) func3() {
+  x++;
+  sink(); /* tail */
+}
 
-void __attribute__((disable_tail_calls, noinline)) func2() { func3(); /* regular */ }
+void __attribute__((disable_tail_calls, noinline)) func2() {
+  func3(); /* regular */
+}
 
-void __attribute__((noinline)) func1() { func2(); /* tail */ }
+void __attribute__((noinline)) func1() {
+  x++;
+  func2(); /* tail */
+}
 
 int __attribute__((disable_tail_calls)) main() {
+  // DEBUG: self.runCmd("log enable lldb step -f /tmp/lldbstep.log")
   func1(); /* regular */
   return 0;
 }