[binutils-gdb] Change call_site_find_chain_1 to work recursively

[binutils-gdb] Change call_site_find_chain_1 to work recursively

[Tom Tromey]

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=206bedc2aa113eb3f7cb58668944eb7df82b8894

commit 206bedc2aa113eb3f7cb58668944eb7df82b8894
Author: Tom Tromey <tromey@adacore.com>
Date:   Fri Nov 19 09:23:09 2021 -0700

    Change call_site_find_chain_1 to work recursively
    
    call_site_find_chain_1 has a comment claiming that recursive calls
    would be too expensive.  However, I doubt this is so expensive; and
    furthermore the explicit state management approach here is difficult
    both to understand and to modify.  This patch changes this code to use
    explicit recursion, so that a subsequent patch can generalize this
    code without undue trauma.
    
    Additionally, I think this patch detects a latent bug in the recursion
    code.  (It's hard for me to be completely certain.)  The bug is that
    when a new target_call_site is entered, the code does:
    
              if (target_call_site)
                {
                  if (addr_hash.insert (target_call_site->pc ()).second)
                    {
                      /* Successfully entered TARGET_CALL_SITE.  */
    
                      chain.push_back (target_call_site);
                      break;
                    }
                }
    
    Here, if entering the target_call_site fails, then any tail_call_next
    elements in this call site are not visited.  However, if this code
    does happen to enter a call site, then the tail_call_next elements
    will be visited during backtracking.  This applies when doing the
    backtracking as well -- it will only continue through a given chain as
    long as each element in the chain can successfully be visited.
    
    I'd appreciate some review of this.  If this behavior is intentional,
    it can be added to the new implementation.

Diff:
---
 gdb/dwarf2/loc.c                             | 136 +++++++++++++--------------
 gdb/testsuite/gdb.arch/amd64-entry-value.exp |   2 +-
 2 files changed, 64 insertions(+), 74 deletions(-)

diff --git a/gdb/dwarf2/loc.c b/gdb/dwarf2/loc.c
index addf611d8f8..eb1312a5619 100644
--- a/gdb/dwarf2/loc.c
+++ b/gdb/dwarf2/loc.c
@@ -924,11 +924,65 @@ chain_candidate (struct gdbarch *gdbarch,
   gdb_assert ((*resultp)->callers + (*resultp)->callees <= (*resultp)->length);
 }
 
-/* Create and return call_site_chain for CALLER_PC and CALLEE_PC.  All the
-   assumed frames between them use GDBARCH.  Use depth first search so we can
-   keep single CHAIN of call_site's back to CALLER_PC.  Function recursion
-   would have needless GDB stack overhead.  Any unreliability results
-   in thrown NO_ENTRY_VALUE_ERROR.  */
+/* Recursively try to construct the call chain.  GDBARCH, RESULTP, and
+   CHAIN are passed to chain_candidate.  ADDR_HASH tracks which
+   addresses have already been seen along the current chain.
+   CALL_SITE is the call site to visit, and CALLEE_PC is the PC we're
+   trying to "reach".  Returns false if an error has already been
+   detected and so an early return can be done.  If it makes sense to
+   keep trying (even if no answer has yet been found), returns
+   true.  */
+
+static bool
+call_site_find_chain_2
+     (struct gdbarch *gdbarch,
+      gdb::unique_xmalloc_ptr<struct call_site_chain> *resultp,
+      std::vector<struct call_site *> &chain,
+      std::unordered_set<CORE_ADDR> &addr_hash,
+      struct call_site *call_site,
+      CORE_ADDR callee_pc)
+{
+  /* CALLER_FRAME with registers is not available for tail-call jumped
+     frames.  */
+  CORE_ADDR target_func_addr = call_site->address (gdbarch, nullptr);
+
+  if (target_func_addr == callee_pc)
+    {
+      chain_candidate (gdbarch, resultp, chain);
+      /* If RESULTP was reset, then chain_candidate failed, and so we
+	 can tell our callers to early-return.  */
+      return *resultp != nullptr;
+    }
+
+  struct symbol *target_func
+    = func_addr_to_tail_call_list (gdbarch, target_func_addr);
+  for (struct call_site *target_call_site
+	 = TYPE_TAIL_CALL_LIST (target_func->type ());
+       target_call_site != nullptr;
+       target_call_site = target_call_site->tail_call_next)
+    {
+      if (addr_hash.insert (target_call_site->pc ()).second)
+	{
+	  /* Successfully entered TARGET_CALL_SITE.  */
+	  chain.push_back (target_call_site);
+
+	  if (!call_site_find_chain_2 (gdbarch, resultp, chain,
+				       addr_hash, target_call_site,
+				       callee_pc))
+	    return false;
+
+	  size_t removed = addr_hash.erase (target_call_site->pc ());
+	  gdb_assert (removed == 1);
+	  chain.pop_back ();
+	}
+    }
+
+  return true;
+}
+
+/* Create and return call_site_chain for CALLER_PC and CALLEE_PC.  All
+   the assumed frames between them use GDBARCH.  Any unreliability
+   results in thrown NO_ENTRY_VALUE_ERROR.  */
 
 static gdb::unique_xmalloc_ptr<call_site_chain>
 call_site_find_chain_1 (struct gdbarch *gdbarch, CORE_ADDR caller_pc,
@@ -958,74 +1012,10 @@ call_site_find_chain_1 (struct gdbarch *gdbarch, CORE_ADDR caller_pc,
      target's function will get iterated as already pushed into CHAIN via their
      TAIL_CALL_NEXT.  */
   call_site = call_site_for_pc (gdbarch, caller_pc);
-
-  while (call_site)
-    {
-      CORE_ADDR target_func_addr;
-      struct call_site *target_call_site;
-
-      /* CALLER_FRAME with registers is not available for tail-call jumped
-	 frames.  */
-      target_func_addr = call_site->address (gdbarch, nullptr);
-
-      if (target_func_addr == callee_pc)
-	{
-	  chain_candidate (gdbarch, &retval, chain);
-	  if (retval == NULL)
-	    break;
-
-	  /* There is no way to reach CALLEE_PC again as we would prevent
-	     entering it twice as being already marked in ADDR_HASH.  */
-	  target_call_site = NULL;
-	}
-      else
-	{
-	  struct symbol *target_func;
-
-	  target_func = func_addr_to_tail_call_list (gdbarch, target_func_addr);
-	  target_call_site = TYPE_TAIL_CALL_LIST (target_func->type ());
-	}
-
-      do
-	{
-	  /* Attempt to visit TARGET_CALL_SITE.  */
-
-	  if (target_call_site)
-	    {
-	      if (addr_hash.insert (target_call_site->pc ()).second)
-		{
-		  /* Successfully entered TARGET_CALL_SITE.  */
-
-		  chain.push_back (target_call_site);
-		  break;
-		}
-	    }
-
-	  /* Backtrack (without revisiting the originating call_site).  Try the
-	     callers's sibling; if there isn't any try the callers's callers's
-	     sibling etc.  */
-
-	  target_call_site = NULL;
-	  while (!chain.empty ())
-	    {
-	      call_site = chain.back ();
-	      chain.pop_back ();
-
-	      size_t removed = addr_hash.erase (call_site->pc ());
-	      gdb_assert (removed == 1);
-
-	      target_call_site = call_site->tail_call_next;
-	      if (target_call_site)
-		break;
-	    }
-	}
-      while (target_call_site);
-
-      if (chain.empty ())
-	call_site = NULL;
-      else
-	call_site = chain.back ();
-    }
+  /* No need to check the return value here, because we no longer care
+     about possible early returns.  */
+  call_site_find_chain_2 (gdbarch, &retval, chain, addr_hash, call_site,
+			  callee_pc);
 
   if (retval == NULL)
     {
diff --git a/gdb/testsuite/gdb.arch/amd64-entry-value.exp b/gdb/testsuite/gdb.arch/amd64-entry-value.exp
index 4f06a303ab2..485d8a5cd1b 100644
--- a/gdb/testsuite/gdb.arch/amd64-entry-value.exp
+++ b/gdb/testsuite/gdb.arch/amd64-entry-value.exp
@@ -253,7 +253,7 @@ gdb_test "bt" "^bt\r\n#0 +d \\(i=<optimized out>, j=<optimized out>\\)\[^\r\n\]*
 
 gdb_continue_to_breakpoint "self: breakhere"
 
-gdb_test "bt" "^bt\r\n#0 +d \\(i=<optimized out>, j=<optimized out>\\)\[^\r\n\]*\r\n#1 +0x\[0-9a-f\]+ in self \\(i=<optimized out>\\)\[^\r\n\]*\r\n#2 +0x\[0-9a-f\]+ in main \\(\\)\[^\r\n\]*" \
+gdb_test "bt" "^bt\r\n#0 +d \\(i=<optimized out>, j=<optimized out>\\)\[^\r\n\]*\r\n#1 +0x\[0-9a-f\]+ in self \\(i=<optimized out>\\)\[^\r\n\]*\r\n#2 +0x\[0-9a-f\]+ in self2 \\(i=<optimized out>\\)\[^\r\n\]*\r\n#3 +0x\[0-9a-f\]+ in self \\(i=<optimized out>\\)\[^\r\n\]*\r\n#4 +0x\[0-9a-f\]+ in main \\(\\)\[^\r\n\]*" \
 	 "self: bt"
 
 gdb_test_no_output "set debug entry-values 1"