[lldb/DWARF] Fix PC value for artificial tail call frames for the "GNU" case

[labath]

Summary

The way that the support for the GNU dialect of tail call frames was
implemented in D80519 meant that the were reporting very bogus PC values
which pointed into the middle of an instruction: the -1 trick is
necessary for the address to resolve to the right function, but we
should still be reporting a more realistic PC value -- I say "realistic"
and not "real", because it's very debatable what should be the correct
PC value for frames like this.

This patch achieves that my moving the -1 from SymbolFileDWARF into the
stack frame computation code. The idea is that SymbolFileDWARF will
merely report whether it has provided an address of the instruction
after the tail call, or the address of the call instruction itself. The
StackFrameList machinery uses this information to set the "behaves like
frame zero" property of the artificial frames (the main thing this flag
does is it controls the -1 subtraction when looking up the function
address).

This required a moderate refactor of the CallEdge class, because it was
implicitly assuming that edges pointing after the call were real calls
and those pointing the the call insn were tail calls. The class now
carries this information explicitly -- it carries three mostly
independent pieces of information:

• an address of interest in the caller
• a bit saying whether this address points to the call insn or after it
• whether this is a tail call

[vsk]

Thanks, this ended up being a lot cleaner than I expected!

lldb/include/lldb/Symbol/Function.h

325–328

It seems like there's going to be around sizeof(void *) bytes worth of padding here. Maybe it'd be simpler to store these flags as AddrType and bool respectively? Alternatively, the struct can be marked 'packed'.

[labath]

lldb/include/lldb/Symbol/Function.h

325–328

Indeed. I was optimizing prematurely.

[labath]

• Unpack the CallEdge structure

[vsk]

Lgtm.

lldb/source/Symbol/Function.cpp

320–321

Could you please update this comment?

lldb/include/lldb/Symbol/Function.h

 using CallSiteParameterArray = llvm::SmallVector<CallSiteParameter, 0>;
 
 /// \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, or to evaluate DW_OP_entry_value.
 class CallEdge {
 public:
+  enum class AddrType : uint8_t { Call, AfterCall };
   virtual ~CallEdge() {}
 
   /// Get the callee's definition.
   ///
   /// Note that this might lazily invoke the DWARF parser. A register context
   /// from the caller's activation is needed to find indirect call targets.
   virtual Function *GetCallee(ModuleList &images,
                               ExecutionContext &exe_ctx) = 0;
 
   /// 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; }
+  /// Return an address in the caller. This can either be the address of the
+  /// call instruction, or the address of the instruction after the call.
+  std::pair<AddrType, lldb::addr_t> GetCallerAddress(Function &caller,
+                                                     Target &target) const {
+    return {caller_address_type,
+            GetLoadAddress(caller_address, caller, target)};
+  }
 
-  /// Get the load PC address of the call instruction (or LLDB_INVALID_ADDRESS).
-  lldb::addr_t GetCallInstPC(Function &caller, Target &target) const;
+  bool IsTailCall() const { return is_tail_call; }
 
   /// Get the call site parameters available at this call edge.
   llvm::ArrayRef<CallSiteParameter> GetCallSiteParameters() const {
     return parameters;
   }
 
+  /// Non-tail-calls go first, sorted by the return address. They are followed
+  /// by tail calls, which have no specific order.
+  std::pair<bool, lldb::addr_t> GetSortKey() const {
+    return {is_tail_call, GetUnresolvedReturnPCAddress()};
+  }
+
 protected:
-  CallEdge(lldb::addr_t return_pc, lldb::addr_t call_inst_pc,
-           CallSiteParameterArray &&parameters)
-      : return_pc(return_pc), call_inst_pc(call_inst_pc),
+  CallEdge(AddrType caller_address_type, lldb::addr_t caller_address,
+           bool is_tail_call, CallSiteParameterArray &&parameters)
+      : caller_address(caller_address),
+        caller_address_type(caller_address_type), is_tail_call(is_tail_call),
         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;
+  /// Like \ref GetReturnPCAddress, but returns an unresolved file address.
+  lldb::addr_t GetUnresolvedReturnPCAddress() const {
+    return caller_address_type == AddrType::AfterCall && !is_tail_call
+               ? caller_address
+               : LLDB_INVALID_ADDRESS;
+  }
+
+private:
+  lldb::addr_t caller_address;
+  AddrType caller_address_type;
+  bool is_tail_call;
 
   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,
-                 lldb::addr_t call_inst_pc, CallSiteParameterArray &&parameters)
-      : CallEdge(return_pc, call_inst_pc, std::move(parameters)) {
+  DirectCallEdge(const char *symbol_name, AddrType caller_address_type,
+                 lldb::addr_t caller_address, bool is_tail_call,
+                 CallSiteParameterArray &&parameters)
+      : CallEdge(caller_address_type, caller_address, is_tail_call,
+                 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,
+  IndirectCallEdge(DWARFExpression call_target, AddrType caller_address_type,
+                   lldb::addr_t caller_address, bool is_tail_call,
                    CallSiteParameterArray &&parameters)
-      : CallEdge(return_pc, call_inst_pc, std::move(parameters)),
+      : CallEdge(caller_address_type, caller_address, is_tail_call,
+                 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

for (size_t i = 0; i < num_attributes; ++i) {
         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 (child.Tag() == DW_TAG_GNU_call_site) {
-      // In DWARF v4 DW_AT_low_pc is always the address of the instruction after
-      // the call. For tail calls, approximate the address of the call
-      // instruction by subtracting 1.
-      if (tail_call)
-        call_inst_pc = low_pc - 1;
-      else
-        return_pc = low_pc;
-    }
-
     if (!call_origin && !call_target) {
       LLDB_LOG(log, "CollectCallEdges: call site without any call target");
       continue;
     }
 
+    addr_t caller_address;
+    CallEdge::AddrType caller_address_type;
+    if (return_pc != LLDB_INVALID_ADDRESS) {
+      caller_address = return_pc;
+      caller_address_type = CallEdge::AddrType::AfterCall;
+    } else if (low_pc != LLDB_INVALID_ADDRESS) {
+      caller_address = low_pc;
+      caller_address_type = CallEdge::AddrType::AfterCall;
+    } else if (call_inst_pc != LLDB_INVALID_ADDRESS) {
+      caller_address = call_inst_pc;
+      caller_address_type = CallEdge::AddrType::Call;
+    } else {
+      LLDB_LOG(log, "CollectCallEdges: No caller address");
+      continue;
+    }
     // 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);
+    caller_address = FixupAddress(caller_address);
 
     // 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-PC: {2:x})",
                call_origin->GetPubname(), return_pc, call_inst_pc);
-      edge = std::make_unique<DirectCallEdge>(call_origin->GetMangledName(),
-                                              return_pc, call_inst_pc,
-                                              std::move(parameters));
+      edge = std::make_unique<DirectCallEdge>(
+          call_origin->GetMangledName(), caller_address_type, caller_address,
+          tail_call, 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, call_inst_pc, std::move(parameters));
+          *call_target, caller_address_type, caller_address, tail_call,
+          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

lldb::addr_t CallEdge::GetLoadAddress(lldb::addr_t unresolved_pc,
 
   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);
+  return GetLoadAddress(GetUnresolvedReturnPCAddress(), 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}",
llvm::ArrayRef<std::unique_ptr<CallEdge>> Function::GetCallEdges() {
   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.
-  llvm::sort(m_call_edges.begin(), m_call_edges.end(),
-             [](const std::unique_ptr<CallEdge> &LHS,
+  llvm::sort(m_call_edges, [](const std::unique_ptr<CallEdge> &LHS,
                               const std::unique_ptr<CallEdge> &RHS) {
-               return LHS->GetUnresolvedReturnPCAddress() <
-                      RHS->GetUnresolvedReturnPCAddress();
-             });
+    return LHS->GetSortKey() < RHS->GetSortKey();
 
   return m_call_edges;
 }
 
 llvm::ArrayRef<std::unique_ptr<CallEdge>> 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 std::unique_ptr<CallEdge> &edge) {
-    return edge->GetUnresolvedReturnPCAddress() == LLDB_INVALID_ADDRESS;
-  });
+  // Tail calling edges are sorted at the end of the list. Find them by dropping
+  // all non-tail-calls.
+  return GetCallEdges().drop_until(
+      [](const std::unique_ptr<CallEdge> &edge) { return edge->IsTailCall(); });
 }
 
 CallEdge *Function::GetCallEdgeForReturnAddress(addr_t return_pc,
                                                 Target &target) {
   auto edges = GetCallEdges();
   auto edge_it =
-      std::lower_bound(edges.begin(), edges.end(), return_pc,
-                       [&](const std::unique_ptr<CallEdge> &edge, addr_t pc) {
-                         return edge->GetReturnPCAddress(*this, target) < pc;
-                       });
+      llvm::partition_point(edges, [&](const std::unique_ptr<CallEdge> &edge) {
+        return std::make_pair(edge->IsTailCall(),
+                              edge->GetReturnPCAddress(*this, target)) <
+               std::make_pair(false, return_pc);
   if (edge_it == edges.end() ||
       edge_it->get()->GetReturnPCAddress(*this, target) != return_pc)
     return nullptr;
-  return &const_cast<CallEdge &>(*edge_it->get());
+  return edge_it->get();
 }
 
 Block &Function::GetBlock(bool can_create) {
   if (!m_block.BlockInfoHasBeenParsed() && can_create) {
     ModuleSP module_sp = CalculateSymbolContextModule();
     if (module_sp) {
       module_sp->GetSymbolFile()->ParseBlocksRecursive(*this);
     } else {

lldb/source/Target/StackFrameList.cpp

void StackFrameList::GetOnlyConcreteFramesUpTo(uint32_t end_idx,
   // 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>>;
+struct CallDescriptor {
+  Function *func;
+  CallEdge::AddrType address_type;
+  addr_t address;
+};
+using CallSequence = std::vector<CallDescriptor>;
 
 /// 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, CallSequence &path,
                                   ModuleList &images, Log *log) {
void dfs(CallEdge &current_edge, Function &callee) {
       // 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.emplace_back(&callee, LLDB_INVALID_ADDRESS);
+      active_path.push_back(CallDescriptor{&callee});
       for (const auto &edge : callee.GetTailCallingEdges()) {
         Function *next_callee = edge->GetCallee(images, context);
         if (!next_callee)
           continue;
 
-        addr_t tail_call_pc = edge->GetCallInstPC(callee, target);
-        active_path.back().second = tail_call_pc;
+        std::tie(active_path.back().address_type, active_path.back().address) =
+            edge->GetCallerAddress(callee, target);
 
         dfs(*edge, *next_callee);
         if (ambiguous)
           return;
       }
       active_path.pop_back();
     }
   };
void StackFrameList::SynthesizeTailCallFrames(StackFrame &next_frame) {
   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 (auto calleeInfo : llvm::reverse(path)) {
-    Function *callee = calleeInfo.first;
+    Function *callee = calleeInfo.func;
     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 = calleeInfo.second;
-    // We do not want to subtract 1 from this PC, as it's the actual address
-    // of the tail-calling branch instruction. This address is provided by the
-    // compiler via DW_AT_call_pc.
-    constexpr bool behaves_like_zeroth_frame = true;
+    addr_t pc = calleeInfo.address;
+    // If the callee address refers to the call instruction, we do not want to
+    // subtract 1 from this value.
+    const bool behaves_like_zeroth_frame =
+        calleeInfo.address_type == CallEdge::AddrType::Call;
     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} at {1:x}", callee->GetDisplayName(), pc);

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
-  // CHECK-NEXT: frame #1: 0x{{[0-9a-f]+}} a.out`func3() at main.cpp:16:3
+  // CHECK-NEXT: frame #1: 0x{{[0-9a-f]+}} a.out`func3() at main.cpp:26:3
   // CHECK-SAME: [artificial]
   // CHECK-NEXT: frame #2: 0x{{[0-9a-f]+}} a.out`func2()
-  // CHECK-NEXT: frame #3: 0x{{[0-9a-f]+}} a.out`func1() at main.cpp:25:3
+  // CHECK-NEXT: frame #3: 0x{{[0-9a-f]+}} a.out`func1() at main.cpp:35:3
   // CHECK-SAME: [artificial]
   // CHECK-NEXT: frame #4: 0x{{[0-9a-f]+}} a.out`main
+  // In the GNU style, the artificial frames will point after the tail call
+  // instruction. In v5 they should point to the instruction itself.
+  //% frame1 = self.thread().GetFrameAtIndex(1)
+  //% func3 = frame1.GetFunction()
+  //% func3_insns = func3.GetInstructions(self.target())
+  //% self.trace("func3:\n%s"%func3_insns)
+  //% last_insn = func3_insns.GetInstructionAtIndex(func3_insns.GetSize()-1)
+  //% addr = last_insn.GetAddress()
+  //% if "GNU" in self.name: addr.OffsetAddress(last_insn.GetByteSize())
+  //% self.assertEquals(frame1.GetPCAddress(), addr)
 }
 
 void __attribute__((noinline)) func3() {
   x++;
   sink(); /* tail */
 }
 
 void __attribute__((disable_tail_calls, noinline)) func2() {