[rfc] btrace: change record instruction-history /m

[rfc] btrace: change record instruction-history /m

[Markus Metzger]

The /m modifier interleaves source lines with the disassembly of recorded
instructions.  This calls disasm.c's do_mixed_source_and_assembly once for
each recorded instruction to be printed.

The latter really does a source print with intermixed disassembly.  To that
purpose, it may reorder instructions to better match the source.  This is
nice for disassembling an entire function, but it doesn't work for printing
a single instruction.

Change record instruction-history /m to use its own simple source interleaving
algorithm.  The most important part is that instructions are printed in
the order in which they were executed.  Before each instruction, we print
a range of source lines that are attributed to the instruction's PC.  If the
source line range has already been printed (or skipped) for the previous
instruction, we skip it.

The algorithm would fill in the missing lines if a PC is attributed to more
than one source line.  I have not seen this.  There always seems to be at
most one source line per PC.

I don't think that there is an MI consumer of "record instruction-history"
and I have no idea if and how this might affect MI.

Alternatively, we could extend Doug Evan's new algorithm
https://sourceware.org/ml/gdb-patches/2015-08/msg00335.html to take a vector
of PCs.

2015-08-14  Markus Metzger <markus.t.metzger@intel.com>

gdb/
	* record-btrace.c (struct btrace_line_range): New.
	(btrace_mk_line_range, btrace_line_range_add)
	(btrace_line_range_is_empty, btrace_line_range_contains_range)
	(btrace_find_line_range, btrace_print_lines): New.
	(btrace_insn_history): Add source interleaving algorithm.
---
 gdb/record-btrace.c | 154 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 152 insertions(+), 2 deletions(-)

diff --git a/gdb/record-btrace.c b/gdb/record-btrace.c
index 2f43171..df03e50 100644
--- a/gdb/record-btrace.c
+++ b/gdb/record-btrace.c
@@ -530,6 +530,137 @@ ui_out_field_uint (struct ui_out *uiout, const char *fld, unsigned int val)
   ui_out_field_fmt (uiout, fld, "%u", val);
 }
 
+/* A range of source lines.  */
+
+struct btrace_line_range
+{
+  /* The symtab this line is from.  */
+  struct symtab *symtab;
+
+  /* The first line (inclusive).  */
+  int begin;
+
+  /* The last line (exclusive).  */
+  int end;
+};
+
+/* Construct a line range.  */
+
+static struct btrace_line_range
+btrace_mk_line_range (struct symtab *symtab, int begin, int end)
+{
+  struct btrace_line_range range;
+
+  range.symtab = symtab;
+  range.begin = begin;
+  range.end = end;
+
+  return range;
+}
+
+/* Add a line to a line range.  */
+
+static struct btrace_line_range
+btrace_line_range_add (struct btrace_line_range range, int line)
+{
+  if (range.end <= range.begin)
+    {
+      /* This is the first entry.  */
+      range.begin = line;
+      range.end = line + 1;
+    }
+  else if (line < range.begin)
+    range.begin = line;
+  else if (range.end < line)
+    range.end = line;
+
+  return range;
+}
+
+/* Return non-zero if RANGE is empty, zero otherwise.  */
+
+static int
+btrace_line_range_is_empty (struct btrace_line_range range)
+{
+  return (range.end <= range.begin);
+}
+
+/* Return non-zero if LHS contains RHS, zero otherwise.  */
+
+static int
+btrace_line_range_contains_range (struct btrace_line_range lhs,
+				  struct btrace_line_range rhs)
+{
+  return ((lhs.symtab == rhs.symtab)
+	  && (lhs.begin <= rhs.begin)
+	  && (rhs.end <= lhs.end));
+}
+
+/* Find the lange range associated with PC.  */
+
+static struct btrace_line_range
+btrace_find_line_range (CORE_ADDR pc)
+{
+  struct btrace_line_range range;
+  struct linetable_entry *lines;
+  struct linetable *ltable;
+  struct symtab *symtab;
+  int nlines, i;
+
+  symtab = find_pc_line_symtab (pc);
+  if (symtab == NULL)
+    return btrace_mk_line_range (NULL, 0, 0);
+
+  ltable = SYMTAB_LINETABLE (symtab);
+  if (ltable == NULL)
+    return btrace_mk_line_range (symtab, 0, 0);
+
+  nlines = ltable->nitems;
+  lines = ltable->item;
+  if (nlines <= 0)
+    return btrace_mk_line_range (symtab, 0, 0);
+
+  range = btrace_mk_line_range (symtab, 0, 0);
+  for (i = 0; i < nlines - 1; i++)
+    {
+      if ((lines[i].pc == pc) && (lines[i].line != 0))
+	range = btrace_line_range_add (range, lines[i].line);
+    }
+
+  return range;
+}
+
+/* Print source lines in LINES.  */
+
+static void
+btrace_print_lines (struct btrace_line_range lines, struct ui_out *uiout,
+		    int flags)
+{
+  enum print_source_lines_flags psl_flags;
+  int line;
+
+  psl_flags = 0;
+  if (flags & DISASSEMBLY_FILENAME)
+    psl_flags |= PRINT_SOURCE_LINES_FILENAME;
+
+  for (line = lines.begin; line < lines.end; ++line)
+    {
+      struct cleanup *ui_out_list_chain_line;
+      struct cleanup *ui_out_tuple_chain_line;
+
+      ui_out_tuple_chain_line
+	= make_cleanup_ui_out_tuple_begin_end (uiout, "src_and_asm_line");
+
+      print_source_lines (lines.symtab, line, line + 1, psl_flags);
+
+      ui_out_list_chain_line
+	= make_cleanup_ui_out_list_begin_end (uiout, "line_asm_insn");
+
+      do_cleanups (ui_out_list_chain_line);
+      do_cleanups (ui_out_tuple_chain_line);
+    }
+}
+
 /* Disassemble a section of the recorded instruction trace.  */
 
 static void
@@ -540,11 +671,17 @@ btrace_insn_history (struct ui_out *uiout,
 {
   struct gdbarch *gdbarch;
   struct btrace_insn_iterator it;
+  struct btrace_line_range last_lines;
+  int disas_flags;
 
   DEBUG ("itrace (0x%x): [%u; %u)", flags, btrace_insn_number (begin),
 	 btrace_insn_number (end));
 
   gdbarch = target_gdbarch ();
+  disas_flags = ((flags
+		  & ~(DISASSEMBLY_SOURCE | DISASSEMBLY_FILENAME))
+		 | DISASSEMBLY_OMIT_PC);
+  last_lines = btrace_mk_line_range (NULL, 0, 0);
 
   for (it = *begin; btrace_insn_cmp (&it, end) != 0; btrace_insn_next (&it, 1))
     {
@@ -569,6 +706,19 @@ btrace_insn_history (struct ui_out *uiout,
 	{
 	  char prefix[4];
 
+	  if ((flags & DISASSEMBLY_SOURCE) != 0)
+	    {
+	      struct btrace_line_range lines;
+
+	      lines = btrace_find_line_range (insn->pc);
+	      if (!btrace_line_range_is_empty (lines)
+		  && !btrace_line_range_contains_range (last_lines, lines))
+		{
+		  btrace_print_lines (lines, uiout, flags);
+		  last_lines = lines;
+		}
+	    }
+
 	  /* We may add a speculation prefix later.  We use the same space
 	     that is used for the pc prefix.  */
 	  if ((flags & DISASSEMBLY_OMIT_PC) == 0)
@@ -594,8 +744,8 @@ btrace_insn_history (struct ui_out *uiout,
 
 	  /* Disassembly with '/m' flag may not produce the expected result.
 	     See PR gdb/11833.  */
-	  gdb_disassembly (gdbarch, uiout, NULL, flags | DISASSEMBLY_OMIT_PC,
-			   1, insn->pc, insn->pc + 1);
+	  gdb_disassembly (gdbarch, uiout, NULL, disas_flags, 1, insn->pc,
+			   insn->pc + 1);
 	}
     }
 }
-- 
1.8.3.1

Re: [rfc] btrace: change record instruction-history /m

[Eli Zaretskii]

> From: Markus Metzger <markus.t.metzger@intel.com>
> Cc: gdb-patches@sourceware.org, dje@google.com
> Date: Fri, 14 Aug 2015 13:37:52 +0200
> 
> Change record instruction-history /m to use its own simple source interleaving
> algorithm.  The most important part is that instructions are printed in
> the order in which they were executed.

What does "order in which they were executed" mean with today's
multi-core and multi-execution unit CPUs?

Thanks.

Re: [rfc] btrace: change record instruction-history /m

[Doug Evans]

On Fri, Aug 14, 2015 at 4:37 AM, Markus Metzger
<markus.t.metzger@intel.com> wrote:
> The /m modifier interleaves source lines with the disassembly of recorded
> instructions.  This calls disasm.c's do_mixed_source_and_assembly once for
> each recorded instruction to be printed.
>
> The latter really does a source print with intermixed disassembly.  To that
> purpose, it may reorder instructions to better match the source.  This is
> nice for disassembling an entire function, but it doesn't work for printing
> a single instruction.

Even for an entire function "source centric" disassembly can be a pain.
If some find it useful, great, but I never do.

> Change record instruction-history /m to use its own simple source interleaving
> algorithm.  The most important part is that instructions are printed in
> the order in which they were executed.  Before each instruction, we print
> a range of source lines that are attributed to the instruction's PC.  If the
> source line range has already been printed (or skipped) for the previous
> instruction, we skip it.
>
> The algorithm would fill in the missing lines if a PC is attributed to more
> than one source line.  I have not seen this.  There always seems to be at
> most one source line per PC.

One can imagine such a think happening more often with an LIW ISA.
[assuming the compiler cares to provide such info]

> I don't think that there is an MI consumer of "record instruction-history"
> and I have no idea if and how this might affect MI.

Good question. Dunno either.

> Alternatively, we could extend Doug Evan's new algorithm
> https://sourceware.org/ml/gdb-patches/2015-08/msg00335.html to take a vector
> of PCs.
>
> 2015-08-14  Markus Metzger <markus.t.metzger@intel.com>
>
> gdb/
>         * record-btrace.c (struct btrace_line_range): New.
>         (btrace_mk_line_range, btrace_line_range_add)
>         (btrace_line_range_is_empty, btrace_line_range_contains_range)
>         (btrace_find_line_range, btrace_print_lines): New.
>         (btrace_insn_history): Add source interleaving algorithm.

Yeah, I'd like to avoid having multiple copies of code
doing basically the same thing.
Plus, no one is going to look in record-btrace.c for
"smart disassembly support".
disasm.c should be providing the necessary API
that the rest of gdb an use.

Re: [rfc] btrace: change record instruction-history /m

[Doug Evans]

On Fri, Aug 14, 2015 at 6:45 AM, Eli Zaretskii <eliz@gnu.org> wrote:
>> From: Markus Metzger <markus.t.metzger@intel.com>
>> Cc: gdb-patches@sourceware.org, dje@google.com
>> Date: Fri, 14 Aug 2015 13:37:52 +0200
>>
>> Change record instruction-history /m to use its own simple source interleaving
>> algorithm.  The most important part is that instructions are printed in
>> the order in which they were executed.
>
> What does "order in which they were executed" mean with today's
> multi-core and multi-execution unit CPUs?
>
> Thanks.

"multi-core" doesn't enter into the picture here.
The context is a single thread of control.
And "multi-execution unit" doesn't either because
that's just an underlying implementation detail
of the CPU - the program must behave "as if"
each instruction is executed serially
(or as otherwise defined by the ISA).

Re: [rfc] btrace: change record instruction-history /m

[Doug Evans]

On Fri, Aug 14, 2015 at 10:01 AM, Doug Evans <dje@google.com> wrote:
> disasm.c should be providing the necessary API
> that the rest of gdb an use.

And, while it's on my mind, it should do so in a way that not
only gdb can use it.

The gnu tools can grow far more quickly and more usefully
if we build them out of collections of application independent APIs.

Re: [rfc] btrace: change record instruction-history /m

[Eli Zaretskii]

> From: Doug Evans <dje@google.com>
> Date: Fri, 14 Aug 2015 10:06:15 -0700
> Cc: Markus Metzger <markus.t.metzger@intel.com>, Pedro Alves <palves@redhat.com>, 
> 	gdb-patches <gdb-patches@sourceware.org>
> 
> On Fri, Aug 14, 2015 at 6:45 AM, Eli Zaretskii <eliz@gnu.org> wrote:
> >> From: Markus Metzger <markus.t.metzger@intel.com>
> >> Cc: gdb-patches@sourceware.org, dje@google.com
> >> Date: Fri, 14 Aug 2015 13:37:52 +0200
> >>
> >> Change record instruction-history /m to use its own simple source interleaving
> >> algorithm.  The most important part is that instructions are printed in
> >> the order in which they were executed.
> >
> > What does "order in which they were executed" mean with today's
> > multi-core and multi-execution unit CPUs?
> >
> > Thanks.
> 
> "multi-core" doesn't enter into the picture here.
> The context is a single thread of control.
> And "multi-execution unit" doesn't either because
> that's just an underlying implementation detail
> of the CPU - the program must behave "as if"
> each instruction is executed serially
> (or as otherwise defined by the ISA).

You and I know that, but the text makes it sound as if each
instruction was somehow stamped with its execution time, and then the
instruction stream presented in that order, after annotating each
instruction with its source.  And that's misleading, IMO, because
evidently that's not what will happen.

RE: [rfc] btrace: change record instruction-history /m

[Metzger, Markus T]

> -----Original Message-----
> From: Eli Zaretskii [mailto:eliz@gnu.org]
> Sent: Friday, August 14, 2015 10:32 PM
> To: Doug Evans
> Cc: Metzger, Markus T; palves@redhat.com; gdb-patches@sourceware.org
> Subject: Re: [rfc] btrace: change record instruction-history /m
> 
> > From: Doug Evans <dje@google.com>
> > Date: Fri, 14 Aug 2015 10:06:15 -0700
> > Cc: Markus Metzger <markus.t.metzger@intel.com>, Pedro Alves
> <palves@redhat.com>,
> > 	gdb-patches <gdb-patches@sourceware.org>
> >
> > On Fri, Aug 14, 2015 at 6:45 AM, Eli Zaretskii <eliz@gnu.org> wrote:
> > >> From: Markus Metzger <markus.t.metzger@intel.com>
> > >> Cc: gdb-patches@sourceware.org, dje@google.com
> > >> Date: Fri, 14 Aug 2015 13:37:52 +0200
> > >>
> > >> Change record instruction-history /m to use its own simple source
> interleaving
> > >> algorithm.  The most important part is that instructions are printed in
> > >> the order in which they were executed.
> > >
> > > What does "order in which they were executed" mean with today's
> > > multi-core and multi-execution unit CPUs?
> > >
> > > Thanks.
> >
> > "multi-core" doesn't enter into the picture here.
> > The context is a single thread of control.
> > And "multi-execution unit" doesn't either because
> > that's just an underlying implementation detail
> > of the CPU - the program must behave "as if"
> > each instruction is executed serially
> > (or as otherwise defined by the ISA).
> 
> You and I know that, but the text makes it sound as if each
> instruction was somehow stamped with its execution time, and then the
> instruction stream presented in that order, after annotating each
> instruction with its source.  And that's misleading, IMO, because
> evidently that's not what will happen.

It's not a per-instruction timestamp but it's h/w supported execution tracing.
The h/w generates a trace of executed instructions (per h/w thread), the OS
switches buffers to collect the trace per s/w thread, and GDB presents this to
the user as execution-order disassembly (per thread).

Now we need to interleave sources into this stream of instructions.

Regards,
Markus.

Intel Deutschland GmbH
Registered Address: Am Campeon 10-12, 85579 Neubiberg, Germany
Tel: +49 89 99 8853-0, www.intel.de
Managing Directors: Christin Eisenschmid, Prof. Dr. Hermann Eul
Chairperson of the Supervisory Board: Tiffany Doon Silva
Registered Office: Munich
Commercial Register: Amtsgericht Muenchen HRB 186928

RE: [rfc] btrace: change record instruction-history /m

[Metzger, Markus T]

> -----Original Message-----
> From: Doug Evans [mailto:dje@google.com]
> Sent: Friday, August 14, 2015 7:02 PM
> To: Metzger, Markus T
> Cc: Pedro Alves; gdb-patches
> Subject: Re: [rfc] btrace: change record instruction-history /m


> > Alternatively, we could extend Doug Evan's new algorithm
> > https://sourceware.org/ml/gdb-patches/2015-08/msg00335.html to take a
> vector
> > of PCs.
> >
> > 2015-08-14  Markus Metzger <markus.t.metzger@intel.com>
> >
> > gdb/
> >         * record-btrace.c (struct btrace_line_range): New.
> >         (btrace_mk_line_range, btrace_line_range_add)
> >         (btrace_line_range_is_empty, btrace_line_range_contains_range)
> >         (btrace_find_line_range, btrace_print_lines): New.
> >         (btrace_insn_history): Add source interleaving algorithm.
> 
> Yeah, I'd like to avoid having multiple copies of code
> doing basically the same thing.
> Plus, no one is going to look in record-btrace.c for
> "smart disassembly support".
> disasm.c should be providing the necessary API
> that the rest of gdb an use.

OK, I'll look into it.  I have a few other things to do first.

I wouldn't get too fancy, though, and simply replace the low/high
PC pair with a vector of PCs.  We may have a small wrapper that
generates the vector out of a low/high pair to keep the original
API.

Regards,
Markus.
Intel Deutschland GmbH
Registered Address: Am Campeon 10-12, 85579 Neubiberg, Germany
Tel: +49 89 99 8853-0, www.intel.de
Managing Directors: Christin Eisenschmid, Prof. Dr. Hermann Eul
Chairperson of the Supervisory Board: Tiffany Doon Silva
Registered Office: Munich
Commercial Register: Amtsgericht Muenchen HRB 186928

Re: [rfc] btrace: change record instruction-history /m

[Eli Zaretskii]

> From: "Metzger, Markus T" <markus.t.metzger@intel.com>
> CC: "palves@redhat.com" <palves@redhat.com>, "gdb-patches@sourceware.org"
> 	<gdb-patches@sourceware.org>
> Date: Mon, 17 Aug 2015 07:15:37 +0000
> 
> > > >> Change record instruction-history /m to use its own simple source
> > interleaving
> > > >> algorithm.  The most important part is that instructions are printed in
> > > >> the order in which they were executed.
> > > >
> > > > What does "order in which they were executed" mean with today's
> > > > multi-core and multi-execution unit CPUs?
> > > >
> > > > Thanks.
> > >
> > > "multi-core" doesn't enter into the picture here.
> > > The context is a single thread of control.
> > > And "multi-execution unit" doesn't either because
> > > that's just an underlying implementation detail
> > > of the CPU - the program must behave "as if"
> > > each instruction is executed serially
> > > (or as otherwise defined by the ISA).
> > 
> > You and I know that, but the text makes it sound as if each
> > instruction was somehow stamped with its execution time, and then the
> > instruction stream presented in that order, after annotating each
> > instruction with its source.  And that's misleading, IMO, because
> > evidently that's not what will happen.
> 
> It's not a per-instruction timestamp but it's h/w supported execution tracing.
> The h/w generates a trace of executed instructions (per h/w thread), the OS
> switches buffers to collect the trace per s/w thread, and GDB presents this to
> the user as execution-order disassembly (per thread).

So I suggest to tell that in the manual, and in general avoid saying
anything as definitive as "in the order they were executed", and
instead tell something like "in the order the hardware support for
execution tracing collects them".  This at least will point interested
readers to the vendor of the hardware if they want to ask specific
questions about the order.

Thanks.

RE: [rfc] btrace: change record instruction-history /m

[Metzger, Markus T]

> -----Original Message-----
> From: Eli Zaretskii [mailto:eliz@gnu.org]
> Sent: Monday, August 17, 2015 5:10 PM
> To: Metzger, Markus T
> Cc: dje@google.com; palves@redhat.com; gdb-patches@sourceware.org
> Subject: Re: [rfc] btrace: change record instruction-history /m
> 
> > From: "Metzger, Markus T" <markus.t.metzger@intel.com>
> > CC: "palves@redhat.com" <palves@redhat.com>, "gdb-
> patches@sourceware.org"
> > 	<gdb-patches@sourceware.org>
> > Date: Mon, 17 Aug 2015 07:15:37 +0000
> >
> > > > >> Change record instruction-history /m to use its own simple source
> > > interleaving
> > > > >> algorithm.  The most important part is that instructions are printed in
> > > > >> the order in which they were executed.
> > > > >
> > > > > What does "order in which they were executed" mean with today's
> > > > > multi-core and multi-execution unit CPUs?
> > > > >
> > > > > Thanks.
> > > >
> > > > "multi-core" doesn't enter into the picture here.
> > > > The context is a single thread of control.
> > > > And "multi-execution unit" doesn't either because
> > > > that's just an underlying implementation detail
> > > > of the CPU - the program must behave "as if"
> > > > each instruction is executed serially
> > > > (or as otherwise defined by the ISA).
> > >
> > > You and I know that, but the text makes it sound as if each
> > > instruction was somehow stamped with its execution time, and then the
> > > instruction stream presented in that order, after annotating each
> > > instruction with its source.  And that's misleading, IMO, because
> > > evidently that's not what will happen.
> >
> > It's not a per-instruction timestamp but it's h/w supported execution
> tracing.
> > The h/w generates a trace of executed instructions (per h/w thread), the
> OS
> > switches buffers to collect the trace per s/w thread, and GDB presents this
> to
> > the user as execution-order disassembly (per thread).
> 
> So I suggest to tell that in the manual, and in general avoid saying
> anything as definitive as "in the order they were executed", and
> instead tell something like "in the order the hardware support for
> execution tracing collects them".  This at least will point interested
> readers to the vendor of the hardware if they want to ask specific
> questions about the order.

How about "in the order they were recorded"?

Markus.
Intel Deutschland GmbH
Registered Address: Am Campeon 10-12, 85579 Neubiberg, Germany
Tel: +49 89 99 8853-0, www.intel.de
Managing Directors: Christin Eisenschmid, Prof. Dr. Hermann Eul
Chairperson of the Supervisory Board: Tiffany Doon Silva
Registered Office: Munich
Commercial Register: Amtsgericht Muenchen HRB 186928

Re: [rfc] btrace: change record instruction-history /m

[Eli Zaretskii]

> From: "Metzger, Markus T" <markus.t.metzger@intel.com>
> CC: "dje@google.com" <dje@google.com>, "palves@redhat.com"
> 	<palves@redhat.com>, "gdb-patches@sourceware.org"
> 	<gdb-patches@sourceware.org>
> Date: Tue, 18 Aug 2015 06:30:11 +0000
> 
> > So I suggest to tell that in the manual, and in general avoid saying
> > anything as definitive as "in the order they were executed", and
> > instead tell something like "in the order the hardware support for
> > execution tracing collects them".  This at least will point interested
> > readers to the vendor of the hardware if they want to ask specific
> > questions about the order.
> 
> How about "in the order they were recorded"?

Fine with me, but sounds almost trivial, no?

Re: [rfc] btrace: change record instruction-history /m

[Pedro Alves]

On 08/14/2015 12:37 PM, Markus Metzger wrote:
> I don't think that there is an MI consumer of "record instruction-history"
> and I have no idea if and how this might affect MI.

I think Eclipse has support for reverse debugging, but AFAIK, there
are no MI commands for getting at the instruction history.
I see that it issues the CLI "record" and "record stop" stop commands, but
that's it, AFAICS.  Unless it plays tricks with CLI commands that are
escaping my greps, it shouldn't be affected.

Thanks,
Pedro Alves

RE: [rfc] btrace: change record instruction-history /m

[Marc Khouzam]

> From: gdb-patches-owner@sourceware.org [gdb-patches-owner@sourceware.org] on behalf of Pedro Alves [palves@redhat.com]
> Sent: August 18, 2015 10:57 AM
> To: Markus Metzger
> Cc: gdb-patches@sourceware.org; dje@google.com; Simon Marchi
> Subject: Re: [rfc] btrace: change record instruction-history /m
> 
> On 08/14/2015 12:37 PM, Markus Metzger wrote:
> > I don't think that there is an MI consumer of "record instruction-history"
> > and I have no idea if and how this might affect MI.
> 
> I think Eclipse has support for reverse debugging, but AFAIK, there
> are no MI commands for getting at the instruction history.
> I see that it issues the CLI "record" and "record stop" stop commands, but
> that's it, AFAICS.  Unless it plays tricks with CLI commands that are
> escaping my greps, it shouldn't be affected.

You're right, all Eclipse uses now is "record" and "record stop" which we use
in CLI form (there is no MI version to my knowledge).
We also use the MI events "=record-started" and "=record-stopped".

Marc