[binutils-gdb] btrace: Use binary search to find instruction.

[Tim Wiederhake]

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

commit fdd2bd920bd67e6a1e877baf52b9c138c00da13f
Author: Tim Wiederhake <tim.wiederhake@intel.com>
Date:   Mon Nov 21 16:39:57 2016 +0100

    btrace: Use binary search to find instruction.
    
    Currently, btrace_find_insn_by_number will iterate over all function call
    segments to find the one that contains the needed instruction.  This linear
    search is too slow for the upcoming Python bindings that will use this
    function to access instructions.  This patch introduces a vector in struct
    btrace_thread_info that holds pointers to all recorded function segments and
    allows to use binary search.
    
    The proper solution is to turn the underlying tree into a vector of objects
    and use indices for access.  This requires more work.  A patch set is
    currently being worked on and will be published later.
    
    Signed-off-by: Tim Wiederhake <tim.wiederhake@intel.com>
    
    gdb/ChangeLog:
    	* btrace.c (btrace_fetch): Copy function call segments pointer
    	into a vector.
    	(btrace_clear): Clear the vector.
    	(btrace_find_insn_by_number): Use binary search to find the correct
    	function call segment.
    	* btrace.h (brace_fun_p): New typedef.
    	(struct btrace_thread_info) <functions>: New field.
    
    Change-Id: I8a7f67e80bfe4ff62c4192f74a2153a70bf2a035

Diff:
---
 gdb/btrace.c | 45 +++++++++++++++++++++++++++++++++++++++------
 gdb/btrace.h |  7 +++++++
 2 files changed, 46 insertions(+), 6 deletions(-)

diff --git a/gdb/btrace.c b/gdb/btrace.c
index 06122cd..95dc7ab 100644
--- a/gdb/btrace.c
+++ b/gdb/btrace.c
@@ -1839,13 +1839,19 @@ btrace_fetch (struct thread_info *tp)
   /* Compute the trace, provided we have any.  */
   if (!btrace_data_empty (&btrace))
     {
+      struct btrace_function *bfun;
+
       /* Store the raw trace data.  The stored data will be cleared in
 	 btrace_clear, so we always append the new trace.  */
       btrace_data_append (&btinfo->data, &btrace);
       btrace_maint_clear (btinfo);
 
+      VEC_truncate (btrace_fun_p, btinfo->functions, 0);
       btrace_clear_history (btinfo);
       btrace_compute_ftrace (tp, &btrace);
+
+      for (bfun = btinfo->begin; bfun != NULL; bfun = bfun->flow.next)
+	VEC_safe_push (btrace_fun_p, btinfo->functions, bfun);
     }
 
   do_cleanups (cleanup);
@@ -1868,6 +1874,8 @@ btrace_clear (struct thread_info *tp)
 
   btinfo = &tp->btrace;
 
+  VEC_free (btrace_fun_p, btinfo->functions);
+
   it = btinfo->begin;
   while (it != NULL)
     {
@@ -2458,20 +2466,45 @@ btrace_find_insn_by_number (struct btrace_insn_iterator *it,
 			    unsigned int number)
 {
   const struct btrace_function *bfun;
+  unsigned int upper, lower;
 
-  for (bfun = btinfo->end; bfun != NULL; bfun = bfun->flow.prev)
-    if (bfun->insn_offset <= number)
-      break;
+  if (VEC_empty (btrace_fun_p, btinfo->functions))
+      return 0;
 
-  if (bfun == NULL)
+  lower = 0;
+  bfun = VEC_index (btrace_fun_p, btinfo->functions, lower);
+  if (number < bfun->insn_offset)
     return 0;
 
-  if (bfun->insn_offset + ftrace_call_num_insn (bfun) <= number)
+  upper = VEC_length (btrace_fun_p, btinfo->functions) - 1;
+  bfun = VEC_index (btrace_fun_p, btinfo->functions, upper);
+  if (number >= bfun->insn_offset + ftrace_call_num_insn (bfun))
     return 0;
 
+  /* We assume that there are no holes in the numbering.  */
+  for (;;)
+    {
+      const unsigned int average = lower + (upper - lower) / 2;
+
+      bfun = VEC_index (btrace_fun_p, btinfo->functions, average);
+
+      if (number < bfun->insn_offset)
+	{
+	  upper = average - 1;
+	  continue;
+	}
+
+      if (number >= bfun->insn_offset + ftrace_call_num_insn (bfun))
+	{
+	  lower = average + 1;
+	  continue;
+	}
+
+      break;
+    }
+
   it->function = bfun;
   it->index = number - bfun->insn_offset;
-
   return 1;
 }
 
diff --git a/gdb/btrace.h b/gdb/btrace.h
index 1c0b6b3..07ed10c 100644
--- a/gdb/btrace.h
+++ b/gdb/btrace.h
@@ -187,6 +187,9 @@ struct btrace_function
   btrace_function_flags flags;
 };
 
+typedef struct btrace_function *btrace_fun_p;
+DEF_VEC_P (btrace_fun_p);
+
 /* A branch trace instruction iterator.  */
 struct btrace_insn_iterator
 {
@@ -337,6 +340,10 @@ struct btrace_thread_info
   struct btrace_function *begin;
   struct btrace_function *end;
 
+  /* Vector of pointer to decoded function segments.  These are in execution
+     order with the first element == BEGIN and the last element == END.  */
+  VEC (btrace_fun_p) *functions;
+
   /* The function level offset.  When added to each function's LEVEL,
      this normalizes the function levels such that the smallest level
      becomes zero.  */