[PATCH 4/6] Change call_site_find_chain_1 to work recursively

[Tom Tromey <tromey@adacore.com>]

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.
---
 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 e793bbffd05..398538b54f8 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 (SYMBOL_TYPE (target_func));
+       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 (SYMBOL_TYPE (target_func));
-	}
-
-      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 fdfa4a01b58..386388d71b4 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"
-- 
2.31.1