btrace: change branch trace data structure

The branch trace is represented as 3 vectors:
  - a block vector
  - a instruction vector
  - a function vector

Each vector (except for the first) is computed from the one above.

Change this into a graph where a node represents a sequence of instructions
belonging to the same function and where we have three types of edges to connect
the function segments:
  - control flow
  - same function (instance)
  - call stack

This allows us to navigate in the branch trace.  We will need this for "record
goto" and reverse execution.

This patch introduces the data structure and computes the control flow edges.
It also introduces iterator structs to simplify iterating over the branch trace
in control-flow order.

It also fixes PR gdb/15240 since now recursive calls are handled correctly.
Fix the test that got the number of expected fib instances and also the
function numbers wrong.

The current instruction had been part of the branch trace.  This will look odd
once we start support for reverse execution.  Remove it.  We still keep it in
the trace itself to allow extending the branch trace more easily in the future.

2014-01-16  Markus Metzger  <markus.t.metzger@intel.com>

	* btrace.h (struct btrace_func_link): New.
	(enum btrace_function_flag): New.
	(struct btrace_inst): Rename to ...
	(struct btrace_insn): ...this. Update all users.
	(struct btrace_func) <ibegin, iend>: Remove.
	(struct btrace_func_link): New.
	(struct btrace_func): Rename to ...
	(struct btrace_function): ...this. Update all users.
	(struct btrace_function) <segment, flow, up, insn, insn_offset)
	(number, level, flags>: New.
	(struct btrace_insn_iterator): Rename to ...
	(struct btrace_insn_history): ...this.
	Update all users.
	(struct btrace_insn_iterator, btrace_call_iterator): New.
	(struct btrace_target_info) <btrace, itrace, ftrace>: Remove.
	(struct btrace_target_info) <begin, end, level>
	<insn_history, call_history>: New.
	(btrace_insn_get, btrace_insn_number, btrace_insn_begin)
	(btrace_insn_end, btrace_insn_prev, btrace_insn_next)
	(btrace_insn_cmp, btrace_find_insn_by_number, btrace_call_get)
	(btrace_call_number, btrace_call_begin, btrace_call_end)
	(btrace_call_prev, btrace_call_next, btrace_call_cmp)
	(btrace_find_function_by_number, btrace_set_insn_history)
	(btrace_set_call_history): New.
	* btrace.c (btrace_init_insn_iterator)
	(btrace_init_func_iterator, compute_itrace): Remove.
	(ftrace_print_function_name, ftrace_print_filename)
	(ftrace_skip_file): Change
	parameter to const.
	(ftrace_init_func): Remove.
	(ftrace_debug): Use new btrace_function fields.
	(ftrace_function_switched): Also consider gaining and
	losing symbol information).
	(ftrace_print_insn_addr, ftrace_new_call, ftrace_new_return)
	(ftrace_new_switch, ftrace_find_caller, ftrace_new_function)
	(ftrace_update_caller, ftrace_fixup_caller, ftrace_new_tailcall):
	New.
	(ftrace_new_function): Move. Remove debug print.
	(ftrace_update_lines, ftrace_update_insns): New.
	(ftrace_update_function): Check for call, ret, and jump.
	(compute_ftrace): Renamed to ...
	(btrace_compute_ftrace): ...this. Rewritten to compute call
	stack.
	(btrace_fetch, btrace_clear): Updated.
	(btrace_insn_get, btrace_insn_number, btrace_insn_begin)
	(btrace_insn_end, btrace_insn_prev, btrace_insn_next)
	(btrace_insn_cmp, btrace_find_insn_by_number, btrace_call_get)
	(btrace_call_number, btrace_call_begin, btrace_call_end)
	(btrace_call_prev, btrace_call_next, btrace_call_cmp)
	(btrace_find_function_by_number, btrace_set_insn_history)
	(btrace_set_call_history): New.
	* record-btrace.c (require_btrace): Use new btrace thread
	info fields.
	(record_btrace_info, btrace_insn_history)
	(record_btrace_insn_history, record_btrace_insn_history_range):
	Use new btrace thread info fields and new iterator.
	(btrace_func_history_src_line): Rename to ...
	(btrace_call_history_src_line): ...this. Use new btrace
	thread info fields.
	(btrace_func_history): Rename to ...
	(btrace_call_history): ...this. Use new btrace thread info
	fields and new iterator.
	(record_btrace_call_history, record_btrace_call_history_range):
	Use new btrace thread info fields and new iterator.

testsuite/
	* gdb.btrace/function_call_history.exp: Fix expected function
	trace.
	* gdb.btrace/instruction_history.exp: Initialize traced.
	Remove traced_functions.

3 files changed, 32 insertions, 17 deletions

diff --git a/gdb/testsuite/ChangeLog b/gdb/testsuite/ChangeLog
index 2749e90..52ed566 100644
--- a/gdb/testsuite/ChangeLog
+++ b/gdb/testsuite/ChangeLog
@@ -1,5 +1,12 @@
 2014-01-16  Markus Metzger  <markus.t.metzger@intel.com>
 
+	* gdb.btrace/function_call_history.exp: Fix expected function
+	trace.
+	* gdb.btrace/instruction_history.exp: Initialize traced.
+	Remove traced_functions.
+
+2014-01-16  Markus Metzger  <markus.t.metzger@intel.com>
+
 	* gdb.btrace/function_call_history.exp: Update
 	* gdb.btrace/instruction_history.exp: Update.
 
diff --git a/gdb/testsuite/gdb.btrace/function_call_history.exp b/gdb/testsuite/gdb.btrace/function_call_history.exp
index 7ee4e66..bf2458b 100644
--- a/gdb/testsuite/gdb.btrace/function_call_history.exp
+++ b/gdb/testsuite/gdb.btrace/function_call_history.exp
@@ -187,16 +187,18 @@ set bp_location [gdb_get_line_number "bp.2" $testfile.c]
 gdb_breakpoint $bp_location
 gdb_continue_to_breakpoint "cont to $bp_location" ".*$testfile.c:$bp_location.*"
 
-# at this point we expect to have main, fib, ..., fib, main, where fib occurs 8 times,
-# so we limit the output to only show the latest 10 function calls
-gdb_test_no_output "set record function-call-history-size 10"
-set message "recursive"
-gdb_test_multiple "record function-call-history" $message {
-    -re "13\tmain\r\n14\tfib\r\n15\tfib\r\n16\tfib\r\n17\tfib\r\n18\tfib\r\n19\tfib\r\n20\tfib\r\n21\tfib\r\n22	 main\r\n$gdb_prompt $" {
-        pass $message
-    }
-    -re "13\tinc\r\n14\tmain\r\n15\tinc\r\n16\tmain\r\n17\tinc\r\n18\tmain\r\n19\tinc\r\n20\tmain\r\n21\tfib\r\n22\tmain\r\n$gdb_prompt $" {
-        # recursive function calls appear only as 1 call
-        kfail "gdb/15240" $message
-    }
-}
+# at this point we expect to have main, fib, ..., fib, main, where fib occurs 9 times,
+# so we limit the output to only show the latest 11 function calls
+gdb_test_no_output "set record function-call-history-size 11"
+gdb_test "record function-call-history" [join [list \
+  "20\tmain" \
+  "21\tfib" \
+  "22\tfib" \
+  "23\tfib" \
+  "24\tfib" \
+  "25\tfib" \
+  "26\tfib" \
+  "27\tfib" \
+  "28\tfib" \
+  "29\tfib" \
+  "30\tmain"] "\r\n"] "recursive"
diff --git a/gdb/testsuite/gdb.btrace/instruction_history.exp b/gdb/testsuite/gdb.btrace/instruction_history.exp
index 6048ba1..c6f6500 100644
--- a/gdb/testsuite/gdb.btrace/instruction_history.exp
+++ b/gdb/testsuite/gdb.btrace/instruction_history.exp
@@ -47,18 +47,18 @@ gdb_continue_to_breakpoint "cont to $bp_location" ".*$srcfile2:$bp_location.*"
 # it is necessary to count the number of lines that are
 # shown by the "record instruction-history" command.
 
+set traced {}
 set testname "determine number of recorded instructions"
 gdb_test_multiple "info record" $testname {
     -re "Active record target: record-btrace\r\nRecorded \(\[0-9\]*\) instructions in \(\[0-9\]*\) functions for thread 1 .*\\.\r\n$gdb_prompt $" {
         set traced $expect_out(1,string)
-        set traced_functions $expect_out(2,string)
         pass $testname
     }
 }
 
-# we have exactly 7 instructions here
-set message "exactly 7 instructions"
-if { $traced != 7 } {
+# we have exactly 6 instructions here
+set message "exactly 6 instructions"
+if { $traced != 6 } {
     fail $message
 } else {
     pass $message
@@ -147,6 +147,8 @@ if { $lines != $history_size } {
     pass $message
 }
 
+set history_size 2
+gdb_test_no_output "set record instruction-history-size $history_size"
 set message "browse history forward middle"
 set lines [test_lines_length "record instruction-history +" $message]
 if { $lines != $history_size } {
@@ -168,6 +170,8 @@ gdb_test "record instruction-history" "At the end of the branch trace record\\."
 # make sure we cannot move further
 gdb_test "record instruction-history" "At the end of the branch trace record\\." "browse history forward beyond 2"
 
+set history_size 3
+gdb_test_no_output "set record instruction-history-size $history_size"
 set message "browse history backward last"
 set lines [test_lines_length "record instruction-history -" $message]
 if { $lines != $history_size } {
@@ -176,6 +180,8 @@ if { $lines != $history_size } {
     pass $message
 }
 
+set history_size 2
+gdb_test_no_output "set record instruction-history-size $history_size"
 set message "browse history backward middle"
 set lines [test_lines_length "record instruction-history -" $message]
 if { $lines != $history_size } {