[RFA/dwarf] Optimize partial DIE reading for uninteresting DIEs

[RFA/dwarf] Optimize partial DIE reading for uninteresting DIEs

[Daniel Jacobowitz]

read_partial_die is a pretty heavyweight function.  One of the largest
indicators of this is how high read_uleb128 shows up in startup profiles.
This patch provides an alternative for DIEs we know are uninteresting: we
can just read in the abbrev, and the sibling pointer if any.

Performancewise, on mainline this is a bit of a wash for typical code. 
That's because we read every file-scope or namespace-scope DIE using
read_partial_die before we decide if it's interesting.  A followup patch to
use peek_die_abbrev for that provides a several percent improvement in GDB
startup time.

OK to commit?

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

2004-02-24  Daniel Jacobowitz  <drow@mvista.com>

	* dwarf2read.c (skip_leb128, peek_die_abbrev, skip_one_die)
	(skip_children): New functions.
	(locate_pdi_sibling): Call skip_children.

Index: dwarf2read.c
===================================================================
RCS file: /big/fsf/rsync/src-cvs/src/gdb/dwarf2read.c,v
retrieving revision 1.135
diff -u -p -r1.135 dwarf2read.c
--- dwarf2read.c	21 Feb 2004 02:13:35 -0000	1.135
+++ dwarf2read.c	25 Feb 2004 03:05:54 -0000
@@ -720,6 +720,8 @@ static unsigned long read_unsigned_leb12
 
 static long read_signed_leb128 (bfd *, char *, unsigned int *);
 
+static char *skip_leb128 (bfd *, char *);
+
 static void set_cu_language (unsigned int, struct dwarf2_cu *);
 
 static struct attribute *dwarf2_attr (struct die_info *, unsigned int,
@@ -923,6 +925,9 @@ static void
 dwarf2_symbol_mark_computed (struct attribute *attr, struct symbol *sym,
 			     struct dwarf2_cu *cu);
 
+static char *skip_one_die (char *info_ptr, struct abbrev_info *abbrev,
+			   struct dwarf2_cu *cu);
+
 /* Try to locate the sections we need for DWARF 2 debugging
    information and return true if we have enough to do something.  */
 
@@ -1748,8 +1753,154 @@ add_partial_enumeration (struct partial_
   return info_ptr;
 }
 
-/* Locate ORIG_PDI's sibling; INFO_PTR should point to the next DIE
-   after ORIG_PDI.  */
+/* Read the initial uleb128 in the die at INFO_PTR in compilation unit CU.
+   Return the corresponding abbrev, or NULL if the number is zero (indicating
+   an empty DIE).  In either case *BYTES_READ will be set to the length of
+   the initial number.  */
+
+static struct abbrev_info *
+peek_die_abbrev (char *info_ptr, int *bytes_read, struct dwarf2_cu *cu)
+{
+  bfd *abfd = cu->objfile->obfd;
+  unsigned int abbrev_number;
+  struct abbrev_info *abbrev;
+
+  abbrev_number = read_unsigned_leb128 (abfd, info_ptr, bytes_read);
+
+  if (abbrev_number == 0)
+    return NULL;
+
+  abbrev = dwarf2_lookup_abbrev (abbrev_number, cu);
+  if (!abbrev)
+    {
+      error ("Dwarf Error: Could not find abbrev number %d [in module %s]", abbrev_number,
+		      bfd_get_filename (abfd));
+    }
+
+  return abbrev;
+}
+
+/* Scan the debug information for CU starting at INFO_PTR.  Returns a
+   pointer to the end of a series of DIEs, terminated by an empty
+   DIE.  Any children of the skipped DIEs will also be skipped.  */
+
+static char *
+skip_children (char *info_ptr, struct dwarf2_cu *cu)
+{
+  struct abbrev_info *abbrev;
+  unsigned int bytes_read;
+
+  while (1)
+    {
+      abbrev = peek_die_abbrev (info_ptr, &bytes_read, cu);
+      if (abbrev == NULL)
+	return info_ptr + bytes_read;
+      else
+	info_ptr = skip_one_die (info_ptr + bytes_read, abbrev, cu);
+    }
+}
+
+/* Scan the debug information for CU starting at INFO_PTR.  INFO_PTR
+   should point just after the initial uleb128 of a DIE, and the
+   abbrev corresponding to that skipped uleb128 should be passed in
+   ABBREV.  Returns a pointer to this DIE's sibling, skipping any
+   children.  */
+
+static char *
+skip_one_die (char *info_ptr, struct abbrev_info *abbrev,
+	      struct dwarf2_cu *cu)
+{
+  unsigned int bytes_read;
+  struct attribute attr;
+  bfd *abfd = cu->objfile->obfd;
+  unsigned int form, i;
+
+  for (i = 0; i < abbrev->num_attrs; i++)
+    {
+      /* The only abbrev we care about is DW_AT_sibling.  */
+      if (abbrev->attrs[i].name == DW_AT_sibling)
+	{
+	  read_attribute (&attr, &abbrev->attrs[i],
+			  abfd, info_ptr, cu);
+	  if (attr.form == DW_FORM_ref_addr)
+	    complaint (&symfile_complaints, "ignoring absolute DW_AT_sibling");
+	  else
+	    return dwarf_info_buffer + dwarf2_get_ref_die_offset (&attr, cu);
+	}
+
+      /* If it isn't DW_AT_sibling, skip this attribute.  */
+      form = abbrev->attrs[i].form;
+    skip_attribute:
+      switch (form)
+	{
+	case DW_FORM_addr:
+	case DW_FORM_ref_addr:
+	  info_ptr += cu->header.addr_size;
+	  break;
+	case DW_FORM_data1:
+	case DW_FORM_ref1:
+	case DW_FORM_flag:
+	  info_ptr += 1;
+	  break;
+	case DW_FORM_data2:
+	case DW_FORM_ref2:
+	  info_ptr += 2;
+	  break;
+	case DW_FORM_data4:
+	case DW_FORM_ref4:
+	  info_ptr += 4;
+	  break;
+	case DW_FORM_data8:
+	case DW_FORM_ref8:
+	  info_ptr += 8;
+	  break;
+	case DW_FORM_string:
+	  read_string (abfd, info_ptr, &bytes_read);
+	  info_ptr += bytes_read;
+	  break;
+	case DW_FORM_strp:
+	  info_ptr += cu->header.offset_size;
+	  break;
+	case DW_FORM_block:
+	  info_ptr += read_unsigned_leb128 (abfd, info_ptr, &bytes_read);
+	  info_ptr += bytes_read;
+	  break;
+	case DW_FORM_block1:
+	  info_ptr += 1 + read_1_byte (abfd, info_ptr);
+	  break;
+	case DW_FORM_block2:
+	  info_ptr += 2 + read_2_bytes (abfd, info_ptr);
+	  break;
+	case DW_FORM_block4:
+	  info_ptr += 4 + read_4_bytes (abfd, info_ptr);
+	  break;
+	case DW_FORM_sdata:
+	case DW_FORM_udata:
+	case DW_FORM_ref_udata:
+	  info_ptr = skip_leb128 (abfd, info_ptr);
+	  break;
+	case DW_FORM_indirect:
+	  form = read_unsigned_leb128 (abfd, info_ptr, &bytes_read);
+	  info_ptr += bytes_read;
+	  /* We need to continue parsing from here, so just go back to
+	     the top.  */
+	  goto skip_attribute;
+
+	default:
+	  error ("Dwarf Error: Cannot handle %s in DWARF reader [in module %s]",
+		 dwarf_form_name (form),
+		 bfd_get_filename (abfd));
+	}
+    }
+
+  if (abbrev->has_children)
+    return skip_children (info_ptr, cu);
+  else
+    return info_ptr;
+}
+
+/* Locate ORIG_PDI's sibling; INFO_PTR should point to the start of
+   the next DIE after ORIG_PDI.  */
 
 static char *
 locate_pdi_sibling (struct partial_die_info *orig_pdi, char *info_ptr,
@@ -1765,21 +1916,9 @@ locate_pdi_sibling (struct partial_die_i
   if (!orig_pdi->has_children)
     return info_ptr;
 
-  /* Okay, we don't know the sibling, but we have children that we
-     want to skip.  So read children until we run into one without a
-     tag; return whatever follows it.  */
-
-  while (1)
-    {
-      struct partial_die_info pdi;
-      
-      info_ptr = read_partial_die (&pdi, abfd, info_ptr, cu);
+  /* Skip the children the long way.  */
 
-      if (pdi.tag == 0)
-	return info_ptr;
-      else
-	info_ptr = locate_pdi_sibling (&pdi, info_ptr, abfd, cu);
-    }
+  return skip_children (info_ptr, cu);
 }
 
 /* Expand this partial symbol table into a full symbol table.  */
@@ -4925,6 +5064,22 @@ read_signed_leb128 (bfd *abfd, char *buf
     }
   *bytes_read_ptr = num_read;
   return result;
+}
+
+/* Return a pointer to just past the end of an LEB128 number in BUF.  */
+
+static char *
+skip_leb128 (bfd *abfd, char *buf)
+{
+  int byte;
+
+  while (1)
+    {
+      byte = bfd_get_8 (abfd, (bfd_byte *) buf);
+      buf++;
+      if ((byte & 128) == 0)
+	return buf;
+    }
 }
 
 static void

Re: [RFA/dwarf] Optimize partial DIE reading for uninteresting DIEs

[Jim Blandy]

Daniel Jacobowitz <drow@false.org> writes:

> read_partial_die is a pretty heavyweight function.  One of the largest
> indicators of this is how high read_uleb128 shows up in startup profiles.
> This patch provides an alternative for DIEs we know are uninteresting: we
> can just read in the abbrev, and the sibling pointer if any.
> 
> Performancewise, on mainline this is a bit of a wash for typical code. 
> That's because we read every file-scope or namespace-scope DIE using
> read_partial_die before we decide if it's interesting.  A followup patch to
> use peek_die_abbrev for that provides a several percent improvement in GDB
> startup time.

Hmm.  If I'm reading this right, the only real difference between
calling skip_children and calling locate_pdi_sibling is that the
former calls skip_one_die to get past the attributes, while the latter
calls read_partial_die.  Is that right?

skip_one_die:
- stops skipping attributes as soon as it sees a sibling pointer,
- doesn't read the attributes' values, and
- doesn't examine the attributes to fill in a partial_die_info
  structure.

But none of that really sounds too expensive, so I'm not surprised
that this change alone is a wash, and I'm curious to see the followup
patch.  You haven't posted that yet, right?

It bothers me that the patch would give us two separate form parsers.
It would be nicer if we could just have one function that knows how to
get the proper value of each attribute.  Would it be possible for
skip_one_die to call read_attribute, instead of writing out its own
switch?  Yes, that would allocate space for the blocks on
dwarf2_tmp_obstack, but I think there are comments in
dwarf2_build_psymtabs_hard explaining that this isn't significant.
For most everything, read_attribute_value just hands out pointers into
the info or string buffer.  And you're still not going to be reading
past any sibling attributes, so in the common case you'll never read
much anyway.

Re: [RFA/dwarf] Optimize partial DIE reading for uninteresting DIEs

[Daniel Jacobowitz]

On Thu, Feb 26, 2004 at 05:28:18PM -0500, Jim Blandy wrote:
> Daniel Jacobowitz <drow@false.org> writes:
> 
> > read_partial_die is a pretty heavyweight function.  One of the largest
> > indicators of this is how high read_uleb128 shows up in startup profiles.
> > This patch provides an alternative for DIEs we know are uninteresting: we
> > can just read in the abbrev, and the sibling pointer if any.
> > 
> > Performancewise, on mainline this is a bit of a wash for typical code. 
> > That's because we read every file-scope or namespace-scope DIE using
> > read_partial_die before we decide if it's interesting.  A followup patch to
> > use peek_die_abbrev for that provides a several percent improvement in GDB
> > startup time.
> 
> Hmm.  If I'm reading this right, the only real difference between
> calling skip_children and calling locate_pdi_sibling is that the
> former calls skip_one_die to get past the attributes, while the latter
> calls read_partial_die.  Is that right?
> 
> skip_one_die:
> - stops skipping attributes as soon as it sees a sibling pointer,
> - doesn't read the attributes' values, and
> - doesn't examine the attributes to fill in a partial_die_info
>   structure.
> 
> But none of that really sounds too expensive, so I'm not surprised
> that this change alone is a wash, and I'm curious to see the followup
> patch.  You haven't posted that yet, right?

Only the version for the intercu branch.  The reason this is a wash is,
as I said above, only because this function is not called as often as
it could be.  The followup is to use it in place of read_partial_die in
a more common case - when the DIE is something we won't build partial
symbols for.  For instance, types that we know will not have names.  We
can read just the abbrev and then skip everything else.  I could do
considerably better than the current implementation, too, though I'm
not sure it's worthwhile.

You're mistaken about the expense.  In particular read_unsigned_leb128
is much slower than skip_uleb128 because of the computations to build
the result; IIRC variable shifts are expensive.  Yes, this was measured
with an optimized build and a non-intrusive profiler.  There's also the
different memory access patterns.

> It bothers me that the patch would give us two separate form parsers.
> It would be nicer if we could just have one function that knows how to
> get the proper value of each attribute.  Would it be possible for
> skip_one_die to call read_attribute, instead of writing out its own
> switch?  Yes, that would allocate space for the blocks on
> dwarf2_tmp_obstack, but I think there are comments in
> dwarf2_build_psymtabs_hard explaining that this isn't significant.
> For most everything, read_attribute_value just hands out pointers into
> the info or string buffer.  And you're still not going to be reading
> past any sibling attributes, so in the common case you'll never read
> much anyway.

Most of the speedup comes from not reading in the attribute values,
though.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: [RFA/dwarf] Optimize partial DIE reading for uninteresting DIEs

[Jim Blandy]

Daniel Jacobowitz <drow@false.org> writes:
> You're mistaken about the expense.  In particular read_unsigned_leb128
> is much slower than skip_uleb128 because of the computations to build
> the result; IIRC variable shifts are expensive.  Yes, this was measured
> with an optimized build and a non-intrusive profiler.  There's also the
> different memory access patterns.

No kidding.  I'm amazed.  Okay.

> Most of the speedup comes from not reading in the attribute values,
> though.

If what you say above is so, then two distinct versions of the
attribute traversal are clearly called for.

It would be interesting to compare profiling results between two GDB's
that differ only in whether they use your attribute skipper or the
attribute value reader.

Re: [RFA/dwarf] Optimize partial DIE reading for uninteresting DIEs

[Daniel Jacobowitz]

On Thu, Feb 26, 2004 at 09:58:32PM -0500, Jim Blandy wrote:
> 
> Daniel Jacobowitz <drow@false.org> writes:
> > You're mistaken about the expense.  In particular read_unsigned_leb128
> > is much slower than skip_uleb128 because of the computations to build
> > the result; IIRC variable shifts are expensive.  Yes, this was measured
> > with an optimized build and a non-intrusive profiler.  There's also the
> > different memory access patterns.
> 
> No kidding.  I'm amazed.  Okay.
> 
> > Most of the speedup comes from not reading in the attribute values,
> > though.
> 
> If what you say above is so, then two distinct versions of the
> attribute traversal are clearly called for.
> 
> It would be interesting to compare profiling results between two GDB's
> that differ only in whether they use your attribute skipper or the
> attribute value reader.

For this patch, the changes were pretty small.  For the larger change,
with just partial symbol table reading, read_unsigned_leb128 dropped
way down and skip_leb128 didn't climb equally far up.

Let me reproduce those results, though.  Something seems suspicious.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: [RFA/dwarf] Optimize partial DIE reading for uninteresting DIEs

[Daniel Jacobowitz]

On Thu, Feb 26, 2004 at 10:03:10PM -0500, Daniel Jacobowitz wrote:
> On Thu, Feb 26, 2004 at 09:58:32PM -0500, Jim Blandy wrote:
> > 
> > Daniel Jacobowitz <drow@false.org> writes:
> > > You're mistaken about the expense.  In particular read_unsigned_leb128
> > > is much slower than skip_uleb128 because of the computations to build
> > > the result; IIRC variable shifts are expensive.  Yes, this was measured
> > > with an optimized build and a non-intrusive profiler.  There's also the
> > > different memory access patterns.
> > 
> > No kidding.  I'm amazed.  Okay.
> > 
> > > Most of the speedup comes from not reading in the attribute values,
> > > though.
> > 
> > If what you say above is so, then two distinct versions of the
> > attribute traversal are clearly called for.
> > 
> > It would be interesting to compare profiling results between two GDB's
> > that differ only in whether they use your attribute skipper or the
> > attribute value reader.
> 
> For this patch, the changes were pretty small.  For the larger change,
> with just partial symbol table reading, read_unsigned_leb128 dropped
> way down and skip_leb128 didn't climb equally far up.
> 
> Let me reproduce those results, though.  Something seems suspicious.

Nah, seems good, although the difference is just a few percent at most;
I trust from my earlier measurements that it will make more of a
difference down the road.  I've checked this in to HEAD.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: [RFA/dwarf] Optimize partial DIE reading for uninteresting DIEs

[Jim Blandy]

Daniel Jacobowitz <drow@false.org> writes:
> On Thu, Feb 26, 2004 at 10:03:10PM -0500, Daniel Jacobowitz wrote:
> > On Thu, Feb 26, 2004 at 09:58:32PM -0500, Jim Blandy wrote:
> > > It would be interesting to compare profiling results between two GDB's
> > > that differ only in whether they use your attribute skipper or the
> > > attribute value reader.
> > 
> > For this patch, the changes were pretty small.  For the larger change,
> > with just partial symbol table reading, read_unsigned_leb128 dropped
> > way down and skip_leb128 didn't climb equally far up.
> > 
> > Let me reproduce those results, though.  Something seems suspicious.
> 
> Nah, seems good, although the difference is just a few percent at most;
> I trust from my earlier measurements that it will make more of a
> difference down the road.  I've checked this in to HEAD.

Okay, sounds good.

Re: [RFA/dwarf] Optimize partial DIE reading for uninteresting DIEs

[Jim Blandy]

Daniel Jacobowitz <drow@false.org> writes:
> On Thu, Feb 26, 2004 at 10:03:10PM -0500, Daniel Jacobowitz wrote:
> > On Thu, Feb 26, 2004 at 09:58:32PM -0500, Jim Blandy wrote:
> > > It would be interesting to compare profiling results between two GDB's
> > > that differ only in whether they use your attribute skipper or the
> > > attribute value reader.
> > 
> > For this patch, the changes were pretty small.  For the larger change,
> > with just partial symbol table reading, read_unsigned_leb128 dropped
> > way down and skip_leb128 didn't climb equally far up.
> > 
> > Let me reproduce those results, though.  Something seems suspicious.
> 
> Nah, seems good, although the difference is just a few percent at most;
> I trust from my earlier measurements that it will make more of a
> difference down the road.  I've checked this in to HEAD.

Okay, sounds good.

Re: [RFA/dwarf] Optimize partial DIE reading for uninteresting DIEs

[Daniel Jacobowitz]

On Thu, Feb 26, 2004 at 10:03:10PM -0500, Daniel Jacobowitz wrote:
> On Thu, Feb 26, 2004 at 09:58:32PM -0500, Jim Blandy wrote:
> > 
> > Daniel Jacobowitz <drow@false.org> writes:
> > > You're mistaken about the expense.  In particular read_unsigned_leb128
> > > is much slower than skip_uleb128 because of the computations to build
> > > the result; IIRC variable shifts are expensive.  Yes, this was measured
> > > with an optimized build and a non-intrusive profiler.  There's also the
> > > different memory access patterns.
> > 
> > No kidding.  I'm amazed.  Okay.
> > 
> > > Most of the speedup comes from not reading in the attribute values,
> > > though.
> > 
> > If what you say above is so, then two distinct versions of the
> > attribute traversal are clearly called for.
> > 
> > It would be interesting to compare profiling results between two GDB's
> > that differ only in whether they use your attribute skipper or the
> > attribute value reader.
> 
> For this patch, the changes were pretty small.  For the larger change,
> with just partial symbol table reading, read_unsigned_leb128 dropped
> way down and skip_leb128 didn't climb equally far up.
> 
> Let me reproduce those results, though.  Something seems suspicious.

Nah, seems good, although the difference is just a few percent at most;
I trust from my earlier measurements that it will make more of a
difference down the road.  I've checked this in to HEAD.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer