[PATCH 0/3] Performance tweaks for libdw

[Josh Stone]

I did some investigation into libdw performance hotspots, and came up
with a few tweaks that in total trim nearly 1/3 the running time.  I'm
running on Mark's recent empty-location patch, and I primarily used
"tests/varlocs -k >/dev/null" as a moderately long-running benchmark.
I'm using gcc-4.8.2-1.fc20.x86_64 and kernel-3.11.9-300.fc20.x86_64,
running on an i7-2600.

The perf profile initially looked like this:

Samples: 343K of event 'cycles', Event count (approx.): 318932712301
 33.69%  varlocs  libdw.so            [.] __libdw_find_attr
 16.47%  varlocs  libdw.so            [.] lookup.isra.0
 15.63%  varlocs  libdw.so            [.] __libdw_form_val_len
 13.11%  varlocs  libdw.so            [.] dwarf_siblingof
  4.84%  varlocs  libdw.so            [.] dwarf_tag
  4.62%  varlocs  libdw.so            [.] walk_children.4364
  2.35%  varlocs  libdw.so            [.] __libdw_findabbrev
  2.32%  varlocs  libdw.so            [.] Dwarf_Abbrev_Hash_find
  1.26%  varlocs  libdw.so            [.] dwarf_child

Patch 1 addresses form_val_len with an inlined fast path for forms with
constant length.  Patch 2 is a rework of get_uleb128 and get_sleb128,
which are significant in find_attr and elsewhere.  Patch 3 addresses the
hash lookup which is called often to find DIE abbreviations.

The perf profile now looks like this:

Samples: 229K of event 'cycles', Event count (approx.): 213925592727
 44.63%  varlocs  libdw.so            [.] __libdw_find_attr
 22.28%  varlocs  libdw.so            [.] dwarf_siblingof
  7.64%  varlocs  libdw.so            [.] walk_children.4388
  7.07%  varlocs  libdw.so            [.] dwarf_tag
  5.18%  varlocs  libdw.so            [.] __libdw_findabbrev
  2.88%  varlocs  libdw.so            [.] __libdw_form_val_compute_len
  2.11%  varlocs  libdw.so            [.] dwarf_child
  1.44%  varlocs  libdw.so            [.] __libdw_formref
  1.12%  varlocs  libdw.so            [.] scope_visitor

The remaining busy work is simply walking through attributes, from DIE
to DIE.  I believe optimizing this further will be hard without keeping
track of DIE lengths somewhere, which is a lot to cache.  Putting the
length in Dwarf_Die itself is not feasible, because those are short-
lived and frequently recreated.

Here's some summary information for how these patches change varloc -k:

             libdw  varlocs  varlocs
              text     time   maxres
    Base:   243072   84.42s  242360k
    P1:     243296   74.91s  242356k
    P2:     243184   70.61s  242360k
    P3:     243600   56.75s  243588k

My timings are not statistically rigorous measurements, but it still
seems a clear win across the board.  Other benchmarks I've tried, like
tests/allfcts and stap -l syscall.*, show similar improvement.

Feedback is always appreciated.

Thanks,
Josh

[PATCH 1/3] Add an inlined fast path for __libdw_form_val_len

[Josh Stone]

Quite a few DW_FORMs have a fixed length for their data, and we can
easily represent these in a small lookup table.  The rest of the forms
are left in the old function to compute as needed.  Combined with
inlining, this takes care of many forms with fewer branches and without
any call.  (It's conceivable that a smart compiler could make a similar
lookup transformation from the large switch itself, but GCC doesn't.)

Signed-off-by: Josh Stone <jistone(a)redhat.com&gt;
---
 libdw/ChangeLog    |  6 ++++++
 libdw/libdwP.h     | 39 ++++++++++++++++++++++++++++++++++++---
 libdw/libdw_form.c | 32 ++++----------------------------
 3 files changed, 46 insertions(+), 31 deletions(-)

diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index 79bb4b57fc4a..a2e4b142a107 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,3 +1,9 @@
[phone]  Josh Stone  <jistone(a)redhat.com&gt;
+
+	* libdw_form.c (__libdw_form_val_compute_len): Renamed function from
+	__libdw_form_val_len, now handling only non-constant form lengths.
+	* libdwP.h (__libdw_form_val_len): New inlined function.
+
 2013-12-09  Mark Wielaard  <mjw(a)redhat.com&gt;
 
 	* dwarf_getlocation.c (__libdw_intern_expression): Handle empty
diff --git a/libdw/libdwP.h b/libdw/libdwP.h
index 35ab6e79c3fa..bd668c710029 100644
--- a/libdw/libdwP.h
+++ b/libdw/libdwP.h
@@ -34,6 +34,7 @@
 #include <stdbool.h>
 
 #include <libdw.h>
+#include <dwarf.h>
 
 
 /* gettext helper macros.  */
@@ -403,11 +404,43 @@ extern Dwarf_Abbrev *__libdw_getabbrev (Dwarf *dbg, struct Dwarf_CU
*cu,
      __nonnull_attribute__ (1) internal_function;
 
 /* Helper functions for form handling.  */
-extern size_t __libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu,
-				    unsigned int form,
-				    const unsigned char *valp)
+extern size_t __libdw_form_val_compute_len (Dwarf *dbg, struct Dwarf_CU *cu,
+					    unsigned int form,
+					    const unsigned char *valp)
      __nonnull_attribute__ (1, 2, 4) internal_function;
 
+/* Find the length of a form attribute.  */
+static inline size_t
+__nonnull_attribute__ (1, 2, 4)
+__libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu,
+		      unsigned int form, const unsigned char *valp)
+{
+  /* Small lookup table of forms with fixed lengths.  */
+  static const uint8_t form_lengths[] =
+    {
+      [DW_FORM_data1] = 1, [DW_FORM_ref1] = 1, [DW_FORM_flag] = 1,
+      [DW_FORM_data2] = 2, [DW_FORM_ref2] = 2,
+      [DW_FORM_data4] = 4, [DW_FORM_ref4] = 4,
+      [DW_FORM_data8] = 8, [DW_FORM_ref8] = 8, [DW_FORM_ref_sig8] = 8,
+    };
+
+  /* Note that form_lengths[flag_present] is 0, like every other absent index.
+   * But since flag_present's length truly is 0, check for it explicitly.  */
+  if (form == DW_FORM_flag_present)
+    return 0;
+
+  /* Return immediately for forms with fixed lengths.  */
+  if (form < sizeof(form_lengths) / sizeof(form_lengths[0]))
+    {
+      size_t len = form_lengths[form];
+      if (len != 0)
+	return len;
+    }
+
+  /* Other forms require some computation.  */
+  return __libdw_form_val_compute_len (dbg, cu, form, valp);
+}
+
 /* Helper function for DW_FORM_ref* handling.  */
 extern int __libdw_formref (Dwarf_Attribute *attr, Dwarf_Off *return_offset)
      __nonnull_attribute__ (1, 2) internal_function;
diff --git a/libdw/libdw_form.c b/libdw/libdw_form.c
index c476a6e31f32..cf8e4d854fcb 100644
--- a/libdw/libdw_form.c
+++ b/libdw/libdw_form.c
@@ -39,13 +39,15 @@
 
 size_t
 internal_function
-__libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu, unsigned int form,
-		      const unsigned char *valp)
+__libdw_form_val_compute_len (Dwarf *dbg, struct Dwarf_CU *cu,
+			      unsigned int form, const unsigned char *valp)
 {
   const unsigned char *saved;
   Dwarf_Word u128;
   size_t result;
 
+  /* NB: This doesn't cover constant form lengths, which are
+   * already handled by the inlined __libdw_form_val_len.  */
   switch (form)
     {
     case DW_FORM_addr:
@@ -82,32 +84,6 @@ __libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu, unsigned int
form,
       result = u128 + (valp - saved);
       break;
 
-    case DW_FORM_flag_present:
-      result = 0;
-      break;
-
-    case DW_FORM_ref1:
-    case DW_FORM_data1:
-    case DW_FORM_flag:
-      result = 1;
-      break;
-
-    case DW_FORM_data2:
-    case DW_FORM_ref2:
-      result = 2;
-      break;
-
-    case DW_FORM_data4:
-    case DW_FORM_ref4:
-      result = 4;
-      break;
-
-    case DW_FORM_data8:
-    case DW_FORM_ref8:
-    case DW_FORM_ref_sig8:
-      result = 8;
-      break;
-
     case DW_FORM_string:
       result = strlen ((char *) valp) + 1;
       break;
-- 
1.8.4.2

[PATCH 1/3] Add an inlined fast path for __libdw_form_val_len

[Petr Machata]

Josh Stone <jistone(a)redhat.com&gt; writes:

>  +  /* Small lookup table of forms with fixed lengths.  */
>  +  static const uint8_t form_lengths[] =
>  +    {
>  +      [DW_FORM_data1] = 1, [DW_FORM_ref1] = 1, [DW_FORM_flag] = 1,
>  +      [DW_FORM_data2] = 2, [DW_FORM_ref2] = 2,
>  +      [DW_FORM_data4] = 4, [DW_FORM_ref4] = 4,
>  +      [DW_FORM_data8] = 8, [DW_FORM_ref8] = 8, [DW_FORM_ref_sig8] = 8,
>  +    };
>  +
>  +  /* Note that form_lengths[flag_present] is 0, like every other absent index.
>  +   * But since flag_present's length truly is 0, check for it explicitly.  */
>  +  if (form == DW_FORM_flag_present)
>  +    return 0; 
One way to get rid of this if would be to store X | 0x80 in the table
(including 0 | 0x80 for DW_FORM_flag_present), and then return
len ^ 0x80 later.  I don't feel strongly about this though, and
certainly not if it offsets the performance gains again ;)

>  +
>  +  /* Return immediately for forms with fixed lengths.  */
>  +  if (form < sizeof(form_lengths) / sizeof(form_lengths[0])) 
Space after sizeof

>  +    {
>  +      size_t len = form_lengths[form];
>  +      if (len != 0)
>  +	return len; 
Fine otherwise.

Thanks,
PM

[PATCH 1/3] Add an inlined fast path for __libdw_form_val_len

[Josh Stone]

On 12/12/2013 02:47 AM, Petr Machata wrote:
>  Josh Stone <jistone(a)redhat.com&gt; writes:
> > +  /* Note that form_lengths[flag_present] is 0, like every other absent index.
> > +   * But since flag_present's length truly is 0, check for it explicitly.  */
> > +  if (form == DW_FORM_flag_present)
> > +    return 0;
>  
>  One way to get rid of this if would be to store X | 0x80 in the table
>  (including 0 | 0x80 for DW_FORM_flag_present), and then return
>  len ^ 0x80 later.  I don't feel strongly about this though, and
>  certainly not if it offsets the performance gains again ;) 
That's a good idea, though I'd probably use len & 0x7f so the others
don't need to have 0x80.  I'll play with it.

> > +
> > +  /* Return immediately for forms with fixed lengths.  */
> > +  if (form < sizeof(form_lengths) / sizeof(form_lengths[0]))
>  
>  Space after sizeof 
The spaces in all of these will be the end of me... ;)

Thanks,
Josh

[PATCH 1/3] Add an inlined fast path for __libdw_form_val_len

[Roland McGrath]

>  +  /* Note that form_lengths[flag_present] is 0, like every other
> absent index.
>  +   * But since flag_present's length truly is 0, check for it explicitly.  */
Extra * is bad comment formatting.

[PATCH 1/3] Add an inlined fast path for __libdw_form_val_len

[Josh Stone]

On 12/16/2013 02:18 PM, Roland McGrath wrote:
> > +  /* Note that form_lengths[flag_present] is 0, like every other
> absent index.
> > +   * But since flag_present's length truly is 0, check for it explicitly.  */
>  
>  Extra * is bad comment formatting. 
Right, Petr caught that on v2.  These are committed now, but of course
I'll still go back and address concerns if needed...

Thanks,
Josh

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Josh Stone]

This removes the IS_LIBDW distinction so LEB128 operations are now
always inlined, and the implementations are simplified, more direct.

Signed-off-by: Josh Stone <jistone(a)redhat.com&gt;
---
 libdw/ChangeLog       |  14 +++++++
 libdw/Makefile.am     |   3 +-
 libdw/memory-access.c |  50 -----------------------
 libdw/memory-access.h | 108 +++++++++++++++++++-------------------------------
 4 files changed, 56 insertions(+), 119 deletions(-)
 delete mode 100644 libdw/memory-access.c

diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index a2e4b142a107..93396e404d97 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,3 +1,17 @@
[phone]  Josh Stone  <jistone(a)redhat.com&gt;
+
+	* memory-access.h (get_uleb128_rest_return): Removed.
+	(get_sleb128_rest_return): Removed
+	(get_uleb128_step): Make this a self-contained block.
+	(get_sleb128_step): Ditto, and use a bitfield to extend signs.
+	(get_uleb128): Make this wholly implemented by __libdw_get_uleb128.
+	(get_sleb128): Make this wholly implemented by __libdw_get_sleb128.
+	(__libdw_get_uleb128): Simplify and inline for all callers.
+	(__libdw_get_sleb128): Ditto.
+	* memory-access.c: Delete file.
+	* Makefile.am (libdw_a_SOURCES): Remove it.
+	(DEFS): Remove the now unused -DIS_LIBDW.
+
 2013-12-09  Josh Stone  <jistone(a)redhat.com&gt;
 
 	* libdw_form.c (__libdw_form_val_compute_len): Renamed function from
diff --git a/libdw/Makefile.am b/libdw/Makefile.am
index a22166a99e73..cd9e31435317 100644
--- a/libdw/Makefile.am
+++ b/libdw/Makefile.am
@@ -28,7 +28,6 @@
 ## not, see <http://www.gnu.org/licenses/>;.
 ##
 include $(top_srcdir)/config/eu.am
-DEFS += -DIS_LIBDW
 if BUILD_STATIC
 AM_CFLAGS += -fpic
 endif
@@ -79,7 +78,7 @@ libdw_a_SOURCES = dwarf_begin.c dwarf_begin_elf.c dwarf_end.c
dwarf_getelf.c \
 		  dwarf_getfuncs.c  \
 		  dwarf_decl_file.c dwarf_decl_line.c dwarf_decl_column.c \
 		  dwarf_func_inline.c dwarf_getsrc_file.c \
-		  libdw_findcu.c libdw_form.c libdw_alloc.c memory-access.c \
+		  libdw_findcu.c libdw_form.c libdw_alloc.c \
 		  libdw_visit_scopes.c \
 		  dwarf_entry_breakpoints.c \
 		  dwarf_next_cfi.c \
diff --git a/libdw/memory-access.c b/libdw/memory-access.c
deleted file mode 100644
index 7666fb60a64c..000000000000
--- a/libdw/memory-access.c
+++ /dev/null
@@ -1,50 +0,0 @@
-/* Out of line functions for memory-access.h macros.
-   Copyright (C) 2005, 2006 Red Hat, Inc.
-   This file is part of elfutils.
-
-   This file is free software; you can redistribute it and/or modify
-   it under the terms of either
-
-     * the GNU Lesser General Public License as published by the Free
-       Software Foundation; either version 3 of the License, or (at
-       your option) any later version
-
-   or
-
-     * the GNU General Public License as published by the Free
-       Software Foundation; either version 2 of the License, or (at
-       your option) any later version
-
-   or both in parallel, as here.
-
-   elfutils is distributed in the hope that it will be useful, but
-   WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-   General Public License for more details.
-
-   You should have received copies of the GNU General Public License and
-   the GNU Lesser General Public License along with this program.  If
-   not, see <http://www.gnu.org/licenses/>;.  */
-
-#ifdef HAVE_CONFIG_H
-# include <config.h>
-#endif
-#include "libdwP.h"
-#include "memory-access.h"
-
-uint64_t
-internal_function
-__libdw_get_uleb128 (uint64_t acc, unsigned int i, const unsigned char **addrp)
-{
-  unsigned char __b;
-  get_uleb128_rest_return (acc, i, addrp);
-}
-
-int64_t
-internal_function
-__libdw_get_sleb128 (int64_t acc, unsigned int i, const unsigned char **addrp)
-{
-  unsigned char __b;
-  int64_t _v = acc;
-  get_sleb128_rest_return (acc, i, addrp);
-}
diff --git a/libdw/memory-access.h b/libdw/memory-access.h
index 16471990dfa0..0aa46c9994b9 100644
--- a/libdw/memory-access.h
+++ b/libdw/memory-access.h
@@ -37,90 +37,64 @@
 
 /* Number decoding macros.  See 7.6 Variable Length Data.  */
 
-#define get_uleb128_step(var, addr, nth, break)				      \
-    __b = *(addr)++;							      \
-    var |= (uintmax_t) (__b & 0x7f) << (nth * 7);			      \
-    if (likely ((__b & 0x80) == 0))					      \
-      break
+#define len_leb128(var) ((8 * sizeof (var) + 6) / 7)
 
-#define get_uleb128(var, addr)						      \
+#define get_uleb128_step(var, addr, nth)				      \
   do {									      \
-    unsigned char __b;							      \
-    var = 0;								      \
-    get_uleb128_step (var, addr, 0, break);				      \
-    var = __libdw_get_uleb128 (var, 1, &(addr));			      \
+    unsigned char __b = *(addr)++;					      \
+    (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7);		      \
+    if (likely ((__b & 0x80) == 0))					      \
+      return (var);							      \
   } while (0)
 
-#define get_uleb128_rest_return(var, i, addrp)				      \
+static inline uint64_t
+__libdw_get_uleb128 (const unsigned char **addrp)
+{
+  uint64_t acc = 0;
+  get_uleb128_step (acc, *addrp, 0);
+  for (unsigned int i = 1; i < len_leb128(acc); ++i)
+    get_uleb128_step (acc, *addrp, i);
+  /* Other implementations set VALUE to UINT_MAX in this
+     case.  So we better do this as well.  */
+  return UINT64_MAX;
+}
+
+#define get_uleb128(var, addr)						      \
   do {									      \
-    for (; i < 10; ++i)							      \
-      {									      \
-	get_uleb128_step (var, *addrp, i, return var);			      \
-      }									      \
-    /* Other implementations set VALUE to UINT_MAX in this		      \
-       case.  So we better do this as well.  */				      \
-    return UINT64_MAX;							      \
+    (var) = __libdw_get_uleb128(&(addr));				      \
+    (void)(var);							      \
   } while (0)
 
 /* The signed case is similar, but we sign-extend the result.  */
 
-#define get_sleb128_step(var, addr, nth, break)				      \
-    __b = *(addr)++;							      \
-    _v |= (uint64_t) (__b & 0x7f) << (nth * 7);				      \
-    if (likely ((__b & 0x80) == 0))					      \
-      {									      \
-	var = (_v << (64 - (nth * 7) - 7)) >> (64 - (nth * 7) - 7);	      \
-        break;					 			      \
-      }									      \
-    else do {} while (0)
-
-#define get_sleb128(var, addr)						      \
-  do {									      \
-    unsigned char __b;							      \
-    int64_t _v = 0;							      \
-    get_sleb128_step (var, addr, 0, break);				      \
-    var = __libdw_get_sleb128 (_v, 1, &(addr));				      \
-  } while (0)
-
-#define get_sleb128_rest_return(var, i, addrp)				      \
+#define get_sleb128_step(var, addr, nth)				      \
   do {									      \
-    for (; i < 9; ++i)							      \
+    unsigned char __b = *(addr)++;					      \
+    if (likely ((__b & 0x80) == 0))					      \
       {									      \
-	get_sleb128_step (var, *addrp, i, return var);			      \
+	struct { signed int i:7; } __s = { .i = __b };			      \
+	(var) |= (typeof (var)) __s.i << ((nth) * 7);			      \
+	return (var);							      \
       }									      \
-    __b = *(*addrp)++;							      \
-    if (likely ((__b & 0x80) == 0))					      \
-      return var | ((uint64_t) __b << 63);				      \
-    else								      \
-      /* Other implementations set VALUE to INT_MAX in this		      \
-	 case.  So we better do this as well.  */			      \
-      return INT64_MAX;							      \
+    (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7);		      \
   } while (0)
 
-#ifdef IS_LIBDW
-extern uint64_t __libdw_get_uleb128 (uint64_t acc, unsigned int i,
-				     const unsigned char **addrp)
-     internal_function attribute_hidden;
-extern int64_t __libdw_get_sleb128 (int64_t acc, unsigned int i,
-				    const unsigned char **addrp)
-     internal_function attribute_hidden;
-#else
-static inline uint64_t
-__attribute__ ((unused))
-__libdw_get_uleb128 (uint64_t acc, unsigned int i, const unsigned char **addrp)
-{
-  unsigned char __b;
-  get_uleb128_rest_return (acc, i, addrp);
-}
 static inline int64_t
-__attribute__ ((unused))
-__libdw_get_sleb128 (int64_t acc, unsigned int i, const unsigned char **addrp)
+__libdw_get_sleb128 (const unsigned char **addrp)
 {
-  unsigned char __b;
-  int64_t _v = acc;
-  get_sleb128_rest_return (acc, i, addrp);
+  int64_t acc = 0;
+  for (unsigned int i = 0; i < len_leb128(acc); ++i)
+    get_sleb128_step (acc, *addrp, i);
+  /* Other implementations set VALUE to INT_MAX in this
+     case.  So we better do this as well.  */
+  return INT64_MAX;
 }
-#endif
+
+#define get_sleb128(var, addr)						      \
+  do {									      \
+    (var) = __libdw_get_sleb128(&(addr));				      \
+    (void)(var);							      \
+  } while (0)
 
 
 /* We use simple memory access functions in case the hardware allows it.
-- 
1.8.4.2

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Petr Machata]

Josh Stone <jistone(a)redhat.com&gt; writes:

>  diff --git a/libdw/ChangeLog b/libdw/ChangeLog
>  index a2e4b142a107..93396e404d97 100644
>  --- a/libdw/ChangeLog
>  +++ b/libdw/ChangeLog
>  @@ -1,3 +1,17 @@
>  [phone]  Josh Stone  <jistone(a)redhat.com&gt;
>  +
>  +	* memory-access.h (get_uleb128_rest_return): Removed.
>  +	(get_sleb128_rest_return): Removed 
Period.

>  +static inline uint64_t
>  +__libdw_get_uleb128 (const unsigned char **addrp)
>  +{
>  +  uint64_t acc = 0;
>  +  get_uleb128_step (acc, *addrp, 0);
>  +  for (unsigned int i = 1; i < len_leb128(acc); ++i)
>  +    get_uleb128_step (acc, *addrp, i); 
Is there a reason not to use for (i = 0; ...) instead of the pre-step
followed by a for (i = 1; ...)?  The only difference would be for
len_leb128 of 0, where your code makes one step anyway, but that can't
happen.  Then you could just expand get_uleb128_step inline, and get rid
of it altogether.

Also, the len_leb128 call needs space before (...).

>  +  /* Other implementations set VALUE to UINT_MAX in this
>  +     case.  So we better do this as well.  */
>  +  return UINT64_MAX;
>  +}
>  +
>  +#define get_uleb128(var, addr)						      \
>     do {									      \
>  +    (var) = __libdw_get_uleb128(&(addr));				      \
>  +    (void)(var);							      \
>     } while (0) 
Space before (...).  Space after type cast operator.

Actually, could this actually be defined like this?

        #define get_uleb128(var, addr) ((var) = __libdw_get_uleb128 (&(addr)))

Then you wouldn't need the cast as the only set-but-not-used warnings
would come from sites that actually set but not use, and those could be
changed to simply call __libdw_get_uleb128.  But that's probably a
logically separate change.

>  +#define get_sleb128_step(var, addr, nth)				      \
>     do {									      \
>  +    unsigned char __b = *(addr)++;					      \
>  +    if (likely ((__b & 0x80) == 0))					      \
>         {									      \
>  +	   struct { signed int i:7; } __s = { .i = __b };			      \
>  +	   (var) |= (typeof (var)) __s.i << ((nth) * 7);			      \ 
Oh, the bitfield trick is clever!

>  +	   return (var);							      \
>         }									      \
>  +    (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7);		      \
>     } while (0) 
>   
>   static inline int64_t
>  +__libdw_get_sleb128 (const unsigned char **addrp)
>   {
>  +  int64_t acc = 0;
>  +  for (unsigned int i = 0; i < len_leb128(acc); ++i) 
Space before (...).

>  +    get_sleb128_step (acc, *addrp, i);
>  +  /* Other implementations set VALUE to INT_MAX in this
>  +     case.  So we better do this as well.  */
>  +  return INT64_MAX;
>   }
>  +
>  +#define get_sleb128(var, addr)						      \
>  +  do {									      \
>  +    (var) = __libdw_get_sleb128(&(addr));				      \
>  +    (void)(var);							      \
>  +  } while (0) 
Same comments as for get_uleb128.

This all looks fine to me.  I find the new code much clearer than the
original, which seemed to wind every which way and was hard to follow.

Thanks,
PM

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Josh Stone]

On 12/12/2013 04:13 AM, Petr Machata wrote:
>  Josh Stone <jistone(a)redhat.com&gt; writes:
> > +static inline uint64_t
> > +__libdw_get_uleb128 (const unsigned char **addrp)
> > +{
> > +  uint64_t acc = 0;
> > +  get_uleb128_step (acc, *addrp, 0);
> > +  for (unsigned int i = 1; i < len_leb128(acc); ++i)
> > +    get_uleb128_step (acc, *addrp, i);
>  
>  Is there a reason not to use for (i = 0; ...) instead of the pre-step
>  followed by a for (i = 1; ...)?  The only difference would be for
>  len_leb128 of 0, where your code makes one step anyway, but that can't
>  happen.  Then you could just expand get_uleb128_step inline, and get rid
>  of it altogether. 
Ah, yes, I should explain that a little.  I found that the code was
actually faster with the first step unrolled.  And you may have noticed
I didn't do this for sleb128, because I found that slightly slower.

It seems to work like an extra hint to the compiler.  There's already a
likely-return in the loop, but writing it this way seems to convince gcc
that the first step in particular is *really* likely to return.  Then
that step also gets to const-prop the zero.

I can only guess that the sign-extension for sleb128 is complicated
enough to nullify the gain of unrolling.

> > +#define get_uleb128(var, addr)						      \
> >    do {									      \
> > +    (var) = __libdw_get_uleb128(&(addr));				      \
> > +    (void)(var);							      \
> >    } while (0)
>  
>  Space before (...).  Space after type cast operator.
>  
>  Actually, could this actually be defined like this?
>  
>          #define get_uleb128(var, addr) ((var) = __libdw_get_uleb128 (&(addr)))
>  
>  Then you wouldn't need the cast as the only set-but-not-used warnings
>  would come from sites that actually set but not use, and those could be
>  changed to simply call __libdw_get_uleb128.  But that's probably a
>  logically separate change. 
Right, there are two reasons I kept it this way.  One is the cast for
set-but-not-used, as you note, which didn't trigger before because the
former macros did both read and write the value in place.  I think there
was only one caller affected though, so I could just change that.  The
do-while keeps the macro as a statement, vs your expression, but maybe
that doesn't matter much.

> > +#define get_sleb128_step(var, addr, nth)				      \
> >    do {									      \
> > +    unsigned char __b = *(addr)++;					      \
> > +    if (likely ((__b & 0x80) == 0))					      \
> >        {									      \
> > +	   struct { signed int i:7; } __s = { .i = __b };			      \
> > +	   (var) |= (typeof (var)) __s.i << ((nth) * 7);			      \
>  
>  Oh, the bitfield trick is clever! 
I should give credit, I found that trick here:
http://graphics.stanford.edu/~seander/bithacks.html#FixedSignExtend

The former code was trying to sign-extend after the value was shifted
and combined, which as a variable width is harder.  I really like that
this way the compiler is fully aware that this is a sign extension,
rather than being a side effect of ORing bits or left-right shifts.

>  This all looks fine to me.  I find the new code much clearer than
> the
>  original, which seemed to wind every which way and was hard to follow. 
I agree the original was convoluted, and I think it was actually broken
for some edge cases, though you almost have to look at it preprocessed
to make sense of it.  In particular, __libdw_get_sleb128 ORed with acc
in the final step, but only _v was kept updated throughout the loop.
(But it's unlikely any real DWARF had a 10-byte sleb128 to hit this.)

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Petr Machata]

Josh Stone <jistone(a)redhat.com&gt; writes:

>  On 12/12/2013 04:13 AM, Petr Machata wrote:
> > Josh Stone <jistone(a)redhat.com&gt; writes:
> >> +static inline uint64_t
> >> +__libdw_get_uleb128 (const unsigned char **addrp)
> >> +{
> >> +  uint64_t acc = 0;
> >> +  get_uleb128_step (acc, *addrp, 0);
> >> +  for (unsigned int i = 1; i < len_leb128(acc); ++i)
> >> +    get_uleb128_step (acc, *addrp, i);
> > 
> > Is there a reason not to use for (i = 0; ...) instead of the pre-step
> > followed by a for (i = 1; ...)?
>
>  Ah, yes, I should explain that a little.  I found that the code was
>  actually faster with the first step unrolled. 
Ah, I think that's fine then, but needs a comment.

Thanks,
PM

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Mark Wielaard]

On Thu, 2013-12-12 at 11:06 -0800, Josh Stone wrote:
>  On 12/12/2013 04:13 AM, Petr Machata wrote:
>  > Josh Stone <jistone(a)redhat.com&gt; writes:
>  >> +#define get_sleb128_step(var, addr, nth)			  \
>  >>    do {							  \
>  >> +    unsigned char __b = *(addr)++;				  \
>  >> +    if (likely ((__b & 0x80) == 0))				  \
>  >>        {							  \
>  >> +	   struct { signed int i:7; } __s = { .i = __b };	  \
>  >> +	   (var) |= (typeof (var)) __s.i << ((nth) * 7);	  \
>  > 
>  > Oh, the bitfield trick is clever!
>  
>  I should give credit, I found that trick here:
>  http://graphics.stanford.edu/~seander/bithacks.html#FixedSignExtend
>  
>  The former code was trying to sign-extend after the value was shifted
>  and combined, which as a variable width is harder.  I really like that
>  this way the compiler is fully aware that this is a sign extension,
>  rather than being a side effect of ORing bits or left-right shifts. 
Sadly the neat trick triggers undefined behavior since we are trying to
left shift a negative value. Even though it appears to work currently I
am slightly afraid a compiler optimization might take advantage of this
in the future (since it is undefined behavior it could just assume
negative values won't occur) especially since this code is inlined in a
lot of places, causing hard to diagnose errors.

The attached patch is very much not clever, but does what is intended in
a well-defined way (it is basically what the DWARF spec gives as pseudo
code). Does anybody see a better way?

Thanks,

Mark

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Richard Henderson]

On 04/22/2014 07:55 AM, Mark Wielaard wrote:
>  On Thu, 2013-12-12 at 11:06 -0800, Josh Stone wrote:
> > On 12/12/2013 04:13 AM, Petr Machata wrote:
> >> Josh Stone <jistone(a)redhat.com&gt; writes:
> >>> +#define get_sleb128_step(var, addr, nth)			  \
> >>>    do {							  \
> >>> +    unsigned char __b = *(addr)++;				  \
> >>> +    if (likely ((__b & 0x80) == 0))				  \
> >>>        {							  \
> >>> +	   struct { signed int i:7; } __s = { .i = __b };	  \
> >>> +	   (var) |= (typeof (var)) __s.i << ((nth) * 7);	  \
> >>
> >> Oh, the bitfield trick is clever!
> >
> > I should give credit, I found that trick here:
> > http://graphics.stanford.edu/~seander/bithacks.html#FixedSignExtend
> >
> > The former code was trying to sign-extend after the value was shifted
> > and combined, which as a variable width is harder.  I really like that
> > this way the compiler is fully aware that this is a sign extension,
> > rather than being a side effect of ORing bits or left-right shifts.
>  
>  Sadly the neat trick triggers undefined behavior since we are trying to
>  left shift a negative value. Even though it appears to work currently I
>  am slightly afraid a compiler optimization might take advantage of this
>  in the future (since it is undefined behavior it could just assume
>  negative values won't occur) especially since this code is inlined in a
>  lot of places, causing hard to diagnose errors.
>  
>  The attached patch is very much not clever, but does what is intended in
>  a well-defined way (it is basically what the DWARF spec gives as pseudo
>  code). Does anybody see a better way? 
Multiply instead of shift.  I.e.

  (typeof (var)) (__b & 0x7f) * (1 << ((nth) * 7));

With any luck the compiler will even notice it's a multiply by a value with one
bit set, and convert it back to a shift during optimization.


r~

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Richard Henderson]

On 04/22/2014 08:01 AM, Richard Henderson wrote:
>    (typeof (var)) (__b & 0x7f) * (1 << ((nth) * 7)); 
Bah.  That 1 needs to be typeof (var) too.


r~

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Josh Stone]

On 04/22/2014 08:01 AM, Richard Henderson wrote:
>  On 04/22/2014 07:55 AM, Mark Wielaard wrote:
> > On Thu, 2013-12-12 at 11:06 -0800, Josh Stone wrote:
> >> On 12/12/2013 04:13 AM, Petr Machata wrote:
> >>> Josh Stone <jistone(a)redhat.com&gt; writes:
> >>>> +#define get_sleb128_step(var, addr, nth)			  \
> >>>>    do {							  \
> >>>> +    unsigned char __b = *(addr)++;				  \
> >>>> +    if (likely ((__b & 0x80) == 0))				  \
> >>>>        {							  \
> >>>> +	   struct { signed int i:7; } __s = { .i = __b };	  \
> >>>> +	   (var) |= (typeof (var)) __s.i << ((nth) * 7);	  \
> >>>
> >>> Oh, the bitfield trick is clever!
> >>
> >> I should give credit, I found that trick here:
> >> http://graphics.stanford.edu/~seander/bithacks.html#FixedSignExtend
> >>
> >> The former code was trying to sign-extend after the value was shifted
> >> and combined, which as a variable width is harder.  I really like that
> >> this way the compiler is fully aware that this is a sign extension,
> >> rather than being a side effect of ORing bits or left-right shifts.
> >
> > Sadly the neat trick triggers undefined behavior since we are trying to
> > left shift a negative value. Even though it appears to work currently I
> > am slightly afraid a compiler optimization might take advantage of this
> > in the future (since it is undefined behavior it could just assume
> > negative values won't occur) especially since this code is inlined in a
> > lot of places, causing hard to diagnose errors.
> >
> > The attached patch is very much not clever, but does what is intended in
> > a well-defined way (it is basically what the DWARF spec gives as pseudo
> > code). Does anybody see a better way?
>  
>  Multiply instead of shift.  I.e.
>  
>    (typeof (var)) (__b & 0x7f) * (1 << ((nth) * 7));
>  
>  With any luck the compiler will even notice it's a multiply by a value with one
>  bit set, and convert it back to a shift during optimization. 
The trick in the original was that "(typeof (var)) __s.i" would extend
the sign from the 7th bit, which I don't your mask will do.  But if the
only UB is left-shifting negative, then I think we can combine them.

>  Bah.  That 1 needs to be typeof (var) too. 
So in total:

  struct { signed int i:7; } __s = { .i = __b };
  (var) |= (typeof (var)) __s.i * ((typeof (var)) 1 << ((nth) * 7));

Better?

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Richard Henderson]

On 04/22/2014 08:52 AM, Josh Stone wrote:
>  The trick in the original was that "(typeof (var)) __s.i"
> would extend
>  the sign from the 7th bit, which I don't your mask will do. 
Yes, that was another cut/paste error.
Not a great batting average this morning...  ;-)

>  So in total:
>  
>    struct { signed int i:7; } __s = { .i = __b };
>    (var) |= (typeof (var)) __s.i * ((typeof (var)) 1 << ((nth) * 7));
>  
>  Better? 
Yes, that's what I had in mind.


r~

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Mark Wielaard]

On Tue, 2014-04-22 at 08:58 -0700, Richard Henderson wrote:
>  On 04/22/2014 08:52 AM, Josh Stone wrote:
>  > So in total:
>  > 
>  >   struct { signed int i:7; } __s = { .i = __b };
>  >   (var) |= (typeof (var)) __s.i * ((typeof (var)) 1 << ((nth) * 7));
>  > 
>  > Better?
>  
>  Yes, that's what I had in mind. 
Excellent. I changed the patch as attached. No undefined behavior
detected, all tests PASS.

Thanks,

Mark

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Petr Machata]

Mark Wielaard <mjw(a)redhat.com&gt; writes:

>  Sadly the neat trick triggers undefined behavior since we are trying
> to
>  left shift a negative value. Even though it appears to work currently I
>  am slightly afraid a compiler optimization might take advantage of this
>  in the future (since it is undefined behavior it could just assume
>  negative values won't occur) especially since this code is inlined in a
>  lot of places, causing hard to diagnose errors. 
Ouch.  Yeah, I agree, it is essentially a matter of time before this
whole thing is optimized away or something.

>  diff --git a/libdw/memory-access.h b/libdw/memory-access.h
>  index d0ee63c..c6e4bdc 100644
>  --- a/libdw/memory-access.h
>  +++ b/libdw/memory-access.h
>  @@ -70,8 +70,9 @@ __libdw_get_uleb128 (const unsigned char **addrp)
>       unsigned char __b = *(addr)++;					      \
>       if (likely ((__b & 0x80) == 0))					      \
>         {									      \
>  -	struct { signed int i:7; } __s = { .i = __b };			      \
>  -	(var) |= (typeof (var)) __s.i << ((nth) * 7);			      \
>  +	(var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7);		      \
>  +	if ((((nth) + 1) < 8 * sizeof (var)) && (__b & 0x40))		      \
>  +	  (var) |= -(((uint64_t) 1) << (((nth) + 1) * 7));		      \
>   	return (var);							      \
>         }									      \
>       (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7);		      \ 
Wouldn't something like this get us off the hook as well?

-	(var) |= (typeof (var)) __s.i << ((nth) * 7);			      \
+	(var) |= (typeof (var))						      \
+	  (((uint64_t) (typeof (var)) __s.i) << ((nth) * 7));		      \

We are really only using the bitfield trick to avoid having to
sign-extend by hand, but we can shift unsigned without losing anything.

Thanks,
PM

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Richard Henderson]

On 04/23/2014 03:17 AM, Petr Machata wrote:
>  Wouldn't something like this get us off the hook as well?
>  
>  -	(var) |= (typeof (var)) __s.i << ((nth) * 7);			      \
>  +	(var) |= (typeof (var))						      \
>  +	  (((uint64_t) (typeof (var)) __s.i) << ((nth) * 7));		      \
>  
>  We are really only using the bitfield trick to avoid having to
>  sign-extend by hand, but we can shift unsigned without losing anything. 
It gets us off the hook, but might introduce a 64-bit shift where
only a 32-bit shift was required.

Sadly, (unsigned typeof(var)) doesn't work.  ;-)

But I gave the multiplication change a look, and the compiler is in fact
optimizing the multiplication by a power of 2 back into a shift.


r~

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Petr Machata]

Richard Henderson <rth(a)redhat.com&gt; writes:

>  On 04/23/2014 03:17 AM, Petr Machata wrote:
> > Wouldn't something like this get us off the hook as well?
> > 
> > -	(var) |= (typeof (var)) __s.i << ((nth) * 7);			      \
> > +	(var) |= (typeof (var))						      \
> > +	  (((uint64_t) (typeof (var)) __s.i) << ((nth) * 7));		      \
> > 
> > We are really only using the bitfield trick to avoid having to
> > sign-extend by hand, but we can shift unsigned without losing anything.
>
>  It gets us off the hook, but might introduce a 64-bit shift where
>  only a 32-bit shift was required. 
Good point, but get_sleb128_step is only used from __libdw_get_sleb128,
where the type is int64_t.  This macro is not safe for outside use
anyway, as it uses its parameters more than once.

Hmm, should we maybe #undef it after __libdw_get_sleb128, so that it's
clear that it's for local use only?

Thanks,
PM

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Richard Henderson]

On 04/23/2014 11:32 AM, Petr Machata wrote:
>  Richard Henderson <rth(a)redhat.com&gt; writes:
>  
> > On 04/23/2014 03:17 AM, Petr Machata wrote:
> >> Wouldn't something like this get us off the hook as well?
> >>
> >> -	(var) |= (typeof (var)) __s.i << ((nth) * 7);			      \
> >> +	(var) |= (typeof (var))						      \
> >> +	  (((uint64_t) (typeof (var)) __s.i) << ((nth) * 7));		      \
> >>
> >> We are really only using the bitfield trick to avoid having to
> >> sign-extend by hand, but we can shift unsigned without losing anything.
> >
> > It gets us off the hook, but might introduce a 64-bit shift where
> > only a 32-bit shift was required.
>  
>  Good point, but get_sleb128_step is only used from __libdw_get_sleb128,
>  where the type is int64_t.  This macro is not safe for outside use
>  anyway, as it uses its parameters more than once.
>  
>  Hmm, should we maybe #undef it after __libdw_get_sleb128, so that it's
>  clear that it's for local use only? 
In that case, why play around with the typeof at all?  Just merge the macro
into its only user.  At which point using uint64_t makes total sense in context.

Similarly with get_uleb128_step, I assume, at least wrt to the typeof.


r~

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Josh Stone]

On 04/23/2014 11:51 AM, Richard Henderson wrote:
>  On 04/23/2014 11:32 AM, Petr Machata wrote:
> > Richard Henderson <rth(a)redhat.com&gt; writes:
> >
> >> On 04/23/2014 03:17 AM, Petr Machata wrote:
> >>> Wouldn't something like this get us off the hook as well?
> >>>
> >>> -	(var) |= (typeof (var)) __s.i << ((nth) * 7);			      \
> >>> +	(var) |= (typeof (var))						      \
> >>> +	  (((uint64_t) (typeof (var)) __s.i) << ((nth) * 7));		      \
> >>>
> >>> We are really only using the bitfield trick to avoid having to
> >>> sign-extend by hand, but we can shift unsigned without losing anything.
> >>
> >> It gets us off the hook, but might introduce a 64-bit shift where
> >> only a 32-bit shift was required.
> >
> > Good point, but get_sleb128_step is only used from __libdw_get_sleb128,
> > where the type is int64_t.  This macro is not safe for outside use
> > anyway, as it uses its parameters more than once.
> >
> > Hmm, should we maybe #undef it after __libdw_get_sleb128, so that it's
> > clear that it's for local use only?
>  
>  In that case, why play around with the typeof at all?  Just merge the macro
>  into its only user.  At which point using uint64_t makes total sense in context.
>  
>  Similarly with get_uleb128_step, I assume, at least wrt to the typeof. 
The way these are macro'd is partly a legacy of earlier code.  It does
help for the uleb case since unrolling the first step proved to benefit
optimization.  Keeping sleb this way is helpful to maintain their
similarity as much as possible.

Sure, the typeof's are probably unnecessary anymore, but this is
splitting hairs IMO.  It doesn't help anything to drop this, and we
could decide to provide narrower _libdw_get... in the future for certain
callers.

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Petr Machata]

How's this for a counter-proposal?  I shamelessly reused your commit
message and ChangeLog wording, please let me know if that's overstepping
boundaries.

Thanks,
PM

> From 2ed5c470803d15c960a9a2574dc572ac1aa92b71 Mon Sep 17 00:00:00 2001
Message-Id:
<2ed5c470803d15c960a9a2574dc572ac1aa92b71.1398284498.git.pmachata(a)redhat.com&gt;
From: Petr Machata <pmachata(a)redhat.com&gt;
Date: Wed, 23 Apr 2014 22:19:57 +0200
Subject: [PATCH] libdw (get_sleb128_step): Remove undefined behavior.
Gcc: nnimap+mail.corp.redhat.com:Sent
To: elfutils-devel(a)lists.fedorahosted.org

As pointed out by gcc -fsanitize=undefined left shifting a negative
value is undefined. Replace it with an explicit sign extension step.

Signed-off-by: Petr Machata <pmachata(a)redhat.com&gt;
---
 libdw/ChangeLog       |    5 +++++
 libdw/memory-access.h |    3 ++-
 2 files changed, 7 insertions(+), 1 deletions(-)

diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index 49d70af..bd2f0e7 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,3 +1,8 @@
[phone]  Petr Machata  <pmachata(a)redhat.com&gt;
+
+	* memory-access.h (get_sleb128_step): Remove undefined behavior of
+	left shifting a signed value by casting through unsigned.
+
 2014-04-13  Mark Wielaard  <mjw(a)redhat.com&gt;
 
 	* Makefile.am: Remove !MUDFLAP conditions.
diff --git a/libdw/memory-access.h b/libdw/memory-access.h
index d0ee63c..647a2f3 100644
--- a/libdw/memory-access.h
+++ b/libdw/memory-access.h
@@ -71,7 +71,8 @@ __libdw_get_uleb128 (const unsigned char **addrp)
     if (likely ((__b & 0x80) == 0))					      \
       {									      \
 	struct { signed int i:7; } __s = { .i = __b };			      \
-	(var) |= (typeof (var)) __s.i << ((nth) * 7);			      \
+	(var) |= (typeof (var))						      \
+	  (((uint64_t) (typeof (var)) __s.i) << ((nth) * 7));		      \
 	return (var);							      \
       }									      \
     (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7);		      \
-- 
1.7.6.5

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Mark Wielaard]

On Wed, 2014-04-23 at 22:29 +0200, Petr Machata wrote:
>  How's this for a counter-proposal?  I shamelessly reused your
> commit
>  message and ChangeLog wording, please let me know if that's overstepping
>  boundaries. 
No it isn't. And thanks for the proposal.
But I think I prefer the fix using multiplication as posted here:
https://lists.fedorahosted.org/pipermail/elfutils-devel/2014-April/003991...
That one is also just a oneliner and more generic since it doesn't rely
on having to cast to uint64_t. And Richard checked it still just
generates a shift.

You are right that we don't really need the generic version, but just a
int64_t one. But if we make it non-generic than I think we should go all
the way and also do the other cleanups suggested to get rid of the
typeofs and just use the 64bit types everywhere (and maybe inline or
undef the macro). But please don't feel you need to clean it all up and
"ungenericize" it all. That would be nice, but the main thing is that we
get rid of the undefined behavior.

Thanks,

Mark

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Petr Machata]

Mark Wielaard <mjw(a)redhat.com&gt; writes:

>  On Wed, 2014-04-23 at 22:29 +0200, Petr Machata wrote:
> > How's this for a counter-proposal?  I shamelessly reused your commit
> > message and ChangeLog wording, please let me know if that's overstepping
> > boundaries.
>
>  No it isn't. And thanks for the proposal.
>  But I think I prefer the fix using multiplication as posted here:
>  https://lists.fedorahosted.org/pipermail/elfutils-devel/2014-April/003991...
>  That one is also just a oneliner and more generic since it doesn't rely
>  on having to cast to uint64_t. And Richard checked it still just
>  generates a shift. 
Ah, cool, I didn't notice that e-mail.

Thanks,
PM

[PATCH 2/3] Simplify and inline get_uleb128 and get_sleb128

[Mark Wielaard]

On Thu, 2014-04-24 at 00:32 +0200, Petr Machata wrote:
>  Mark Wielaard <mjw(a)redhat.com&gt; writes:
>  > But I think I prefer the fix using multiplication as posted here:
>  > https://lists.fedorahosted.org/pipermail/elfutils-devel/2014-April/003991...
>  > That one is also just a oneliner and more generic since it doesn't rely
>  > on having to cast to uint64_t. And Richard checked it still just
>  > generates a shift.
>  
>  Ah, cool, I didn't notice that e-mail. 
OK, I pushed that fix and the other undefined behavior fixes posted
earlier to master now:

  readelf: handle_core_item make sure variable length array isn't zero size.
  libdwfl: __libdwfl_frame_reg_[gs]et use uint64_t when checking bits.
  readelf.c (print_gdb_index_section): Use unsigned int for 31 bits left shift.
  libdw (get_sleb128_step): Remove undefined behavior.

make CFLAGS="-g -fsanitize=undefined" && \
make CFLAGS="-g -fsanitize=undefined" check
with gcc 4.9 should have zero FAILs now.

Cheers,

Mark

[PATCH 3/3] Add a simple array for CU abbreviations with low codes

[Josh Stone]

At the expense of some memory for a new static array in the CU, we can
now retrieve low abbrev codes directly, without any hash operation.
This relieves a hotspot from the modulus in hash lookup().

Signed-off-by: Josh Stone <jistone(a)redhat.com&gt;
---
 libdw/ChangeLog         |  7 +++++++
 libdw/dwarf_getabbrev.c | 17 ++++++++++++++---
 libdw/dwarf_tag.c       |  7 +++++--
 libdw/libdwP.h          |  6 +++++-
 libdw/libdw_findcu.c    |  2 ++
 5 files changed, 33 insertions(+), 6 deletions(-)

diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index 93396e404d97..397f0c253348 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,5 +1,12 @@
 2013-12-10  Josh Stone  <jistone(a)redhat.com&gt;
 
+	* libdwP.h (Dwarf_CU): Add abbrev_array.
+	* libdw_findcu.c (__libdw_intern_next_unit): Initialize it.
+	* dwarf_getabbrev.c (__libdw_getabbrev): Use it.
+	* dwarf_tag.c (__libdw_findabbrev): Use it.
+
[phone]  Josh Stone  <jistone(a)redhat.com&gt;
+
 	* memory-access.h (get_uleb128_rest_return): Removed.
 	(get_sleb128_rest_return): Removed
 	(get_uleb128_step): Make this a self-contained block.
diff --git a/libdw/dwarf_getabbrev.c b/libdw/dwarf_getabbrev.c
index 87d89c1b816b..75cfea27c1ba 100644
--- a/libdw/dwarf_getabbrev.c
+++ b/libdw/dwarf_getabbrev.c
@@ -85,8 +85,14 @@ __libdw_getabbrev (dbg, cu, offset, lengthp, result)
   /* Check whether this code is already in the hash table.  */
   bool foundit = false;
   Dwarf_Abbrev *abb = NULL;
-  if (cu == NULL
-      || (abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL)) == NULL)
+  if (cu != NULL)
+    {
+      if (code < CU_ABBREV_ARRAY_SIZE)
+	abb = cu->abbrev_array[code];
+      else
+	abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL);
+    }
+  if (cu == NULL || abb == NULL)
     {
       if (result == NULL)
 	abb = libdw_typed_alloc (dbg, Dwarf_Abbrev);
@@ -130,7 +136,12 @@ __libdw_getabbrev (dbg, cu, offset, lengthp, result)
 
   /* Add the entry to the hash table.  */
   if (cu != NULL && ! foundit)
-    (void) Dwarf_Abbrev_Hash_insert (&cu->abbrev_hash, abb->code, abb);
+    {
+      if (abb->code < CU_ABBREV_ARRAY_SIZE)
+	cu->abbrev_array[abb->code] = abb;
+      else
+	(void) Dwarf_Abbrev_Hash_insert (&cu->abbrev_hash, abb->code, abb);
+    }
 
  out:
   return abb;
diff --git a/libdw/dwarf_tag.c b/libdw/dwarf_tag.c
index ff012cf4265c..f76a7fe33c93 100644
--- a/libdw/dwarf_tag.c
+++ b/libdw/dwarf_tag.c
@@ -44,8 +44,11 @@ __libdw_findabbrev (struct Dwarf_CU *cu, unsigned int code)
   if (unlikely (code == 0))
     return DWARF_END_ABBREV;
 
-  /* See whether the entry is already in the hash table.  */
-  abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL);
+  /* See whether the entry is already in the list or hash table.  */
+  if (code < CU_ABBREV_ARRAY_SIZE)
+    abb = cu->abbrev_array[code];
+  else
+    abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL);
   if (abb == NULL)
     while (cu->last_abbrev_offset != (size_t) -1l)
       {
diff --git a/libdw/libdwP.h b/libdw/libdwP.h
index bd668c710029..3cc94a3fc789 100644
--- a/libdw/libdwP.h
+++ b/libdw/libdwP.h
@@ -269,6 +269,8 @@ struct Dwarf_Aranges_s
 };
 
 
+#define CU_ABBREV_ARRAY_SIZE 256
+
 /* CU representation.  */
 struct Dwarf_CU
 {
@@ -283,7 +285,9 @@ struct Dwarf_CU
   size_t type_offset;
   uint64_t type_sig8;
 
-  /* Hash table for the abbreviations.  */
+  /* Simple array for the abbreviations with low codes.  */
+  Dwarf_Abbrev *abbrev_array[CU_ABBREV_ARRAY_SIZE];
+  /* Hash table for the abbreviations with higher codes.  */
   Dwarf_Abbrev_Hash abbrev_hash;
   /* Offset of the first abbreviation.  */
   size_t orig_abbrev_offset;
diff --git a/libdw/libdw_findcu.c b/libdw/libdw_findcu.c
index c0bff2af2a69..831cc4d24b71 100644
--- a/libdw/libdw_findcu.c
+++ b/libdw/libdw_findcu.c
@@ -33,6 +33,7 @@
 
 #include <assert.h>
 #include <search.h>
+#include <string.h>
 #include "libdwP.h"
 
 static int
@@ -105,6 +106,7 @@ __libdw_intern_next_unit (dbg, debug_types)
   newp->version = version;
   newp->type_sig8 = type_sig8;
   newp->type_offset = type_offset;
+  memset(newp->abbrev_array, 0, sizeof(newp->abbrev_array));
   Dwarf_Abbrev_Hash_init (&newp->abbrev_hash, 41);
   newp->orig_abbrev_offset = newp->last_abbrev_offset = abbrev_offset;
   newp->lines = NULL;
-- 
1.8.4.2

[PATCH 3/3] Add a simple array for CU abbreviations with low codes

[Petr Machata]

Josh Stone <jistone(a)redhat.com&gt; writes:

>   struct Dwarf_CU
>   {
>  @@ -283,7 +285,9 @@ struct Dwarf_CU
>     size_t type_offset;
>     uint64_t type_sig8;
>   
>  -  /* Hash table for the abbreviations.  */
>  +  /* Simple array for the abbreviations with low codes.  */
>  +  Dwarf_Abbrev *abbrev_array[CU_ABBREV_ARRAY_SIZE]; 
This blows up Dwarf_CU from 100odd bytes to something like half the
page, I'm not entirely fond of that.  Especially since the hash table
that follows is an on-demand-growing structure, having half a page
reserved (possibly on stack) just in case seems wasteful.

I'm looking into some debuginfo files.  libc has an average of 28
abbreviations per CU (with 108 being the most), libstdc++ an average of
77 (with 108 the most), gcc 88 (142), libbost_python 206 (290), vmlinux
112 (185).  So reserving space for 256 seems overly generous.  I'd be
fine with a growable heap-allocated array capped at 256.  Hopefully that
would still be helpful performance-wise.

>  --- a/libdw/libdw_findcu.c
>  +++ b/libdw/libdw_findcu.c
>  @@ -105,6 +106,7 @@ __libdw_intern_next_unit (dbg, debug_types)
>     newp->version = version;
>     newp->type_sig8 = type_sig8;
>     newp->type_offset = type_offset;
>  +  memset(newp->abbrev_array, 0, sizeof(newp->abbrev_array)); 
Space after memset.  That sizeof either shouldn't have parens, or there
should be a space.

Thanks,
PM

[PATCH 3/3] Add a simple array for CU abbreviations with low codes

[Josh Stone]

On 12/12/2013 09:07 AM, Petr Machata wrote:
>  Josh Stone <jistone(a)redhat.com&gt; writes:
>  
> >  struct Dwarf_CU
> >  {
> > @@ -283,7 +285,9 @@ struct Dwarf_CU
> >    size_t type_offset;
> >    uint64_t type_sig8;
> >  
> > -  /* Hash table for the abbreviations.  */
> > +  /* Simple array for the abbreviations with low codes.  */
> > +  Dwarf_Abbrev *abbrev_array[CU_ABBREV_ARRAY_SIZE];
>  
>  This blows up Dwarf_CU from 100odd bytes to something like half the
>  page, I'm not entirely fond of that.  Especially since the hash table
>  that follows is an on-demand-growing structure, having half a page
>  reserved (possibly on stack) just in case seems wasteful.
>  
>  I'm looking into some debuginfo files.  libc has an average of 28
>  abbreviations per CU (with 108 being the most), libstdc++ an average of
>  77 (with 108 the most), gcc 88 (142), libbost_python 206 (290), vmlinux
>  112 (185).  So reserving space for 256 seems overly generous.  I'd be
>  fine with a growable heap-allocated array capped at 256.  Hopefully that
>  would still be helpful performance-wise. 
OK, I'll experiment with less generous static sizes, on the heap, as
well as dynamic/realloced size (still capped though).

I also had the idea that maybe lookup can sometimes skip the modulus,
which was by far the hotspot instruction in lookup() by ~72%.  Just
basically moving my "is-it-a-small-code" branch into hash lookup.  So
everything would stay in the hash table, hopefully just a bit faster.

More things to try, anyway...

[PATCH 3/3] Add a simple array for CU abbreviations with low codes

[Josh Stone]

On 12/12/2013 11:16 AM, Josh Stone wrote:
>  On 12/12/2013 09:07 AM, Petr Machata wrote:
> > Josh Stone <jistone(a)redhat.com&gt; writes:
> >
> >>  struct Dwarf_CU
> >>  {
> >> @@ -283,7 +285,9 @@ struct Dwarf_CU
> >>    size_t type_offset;
> >>    uint64_t type_sig8;
> >>  
> >> -  /* Hash table for the abbreviations.  */
> >> +  /* Simple array for the abbreviations with low codes.  */
> >> +  Dwarf_Abbrev *abbrev_array[CU_ABBREV_ARRAY_SIZE];
> >
> > This blows up Dwarf_CU from 100odd bytes to something like half the
> > page, I'm not entirely fond of that.  Especially since the hash table
> > that follows is an on-demand-growing structure, having half a page
> > reserved (possibly on stack) just in case seems wasteful.
> >
> > I'm looking into some debuginfo files.  libc has an average of 28
> > abbreviations per CU (with 108 being the most), libstdc++ an average of
> > 77 (with 108 the most), gcc 88 (142), libbost_python 206 (290), vmlinux
> > 112 (185).  So reserving space for 256 seems overly generous.  I'd be
> > fine with a growable heap-allocated array capped at 256.  Hopefully that
> > would still be helpful performance-wise.
>  
>  OK, I'll experiment with less generous static sizes, on the heap, as
>  well as dynamic/realloced size (still capped though).
>  
>  I also had the idea that maybe lookup can sometimes skip the modulus,
>  which was by far the hotspot instruction in lookup() by ~72%.  Just
>  basically moving my "is-it-a-small-code" branch into hash lookup.  So
>  everything would stay in the hash table, hopefully just a bit faster. 
This actually works pretty well:

diff --git a/lib/dynamicsizehash.c b/lib/dynamicsizehash.c
index 40f48d5ed119..eec9826c43be 100644
--- a/lib/dynamicsizehash.c
+++ b/lib/dynamicsizehash.c
@@ -50,7 +50,7 @@ lookup (htab, hval, val)
      TYPE val __attribute__ ((unused));
 {
   /* First hash function: simply take the modul but prevent zero.  */
-  size_t idx = 1 + hval % htab->size;
+  size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);

   if (htab->table[idx].hashval != 0)
     {
---

             libdw  varlocs  varlocs
              text     time   maxres
    Base:   243103   84.14s  237276k
    P1:     243295   74.90s  237276k
    P2:     243167   70.07s  237272k
    P3-old: 243583   57.14s  238464k
    P3-new: 243199   62.21s  237272k

This simple change (P3-new) is not quite as good as using the fixed
array (P3-old), but it's still a speedup and doesn't add to the memory
profile at all.

It's an improvement because well-behaved DWARF producers will use the
lowest abbrev codes to be more compact in uleb128 encoding.  Every file
I've seen also has codes ordered, so __libdw_findabbrev/getabbrev will
always build up the hash in increasing code order.  This dynamic hash
implementation already resizes itself to stay <90% full, which means
here hval is always less than htab->size.  A well-predicted branch
proves to be faster than hitting the 'div' for me.

So in this typical case, the hash table is acting like just a dynamic
array.  However, if some strange DWARF producer didn't use low abbrev
codes in order, the hash table will still do the right thing, no worse
than before.  And with other hash tables like sig8, where hval is large,
the branch in that version of lookup() should be well-predicted the
other way.

[PATCH v2 0/3] Performance tweaks for libdw

[Josh Stone]

Thanks to Petr for the reviews - I made these changes:

Patch 1: Use 0x80 to represent flag_present's 0 in the table.

Patch 2: Added a comment for the manually unrolled step 0 of uleb128,
and made both get_?leb128 macros into simple expressions.  Fixed the
one caller who was getting a set-but-unused warning from this.

Patch 3: Redid this as a smaller optimization directly on the hash
lookup function.  The performance gain is not as great, but it's a
simpler change and doesn't increase memory use.

And my spacing should be improved everywhere. :)

Thanks,
Josh

[PATCH v2 1/3] libdw: Add an inlined fast path for __libdw_form_val_len

[Josh Stone]

Quite a few DW_FORMs have a fixed length for their data, and we can
easily represent these in a small lookup table.  The rest of the forms
are left in the old function to compute as needed.  Combined with
inlining, this takes care of many forms with fewer branches and without
any call.  (It's conceivable that a smart compiler could make a similar
lookup transformation from the large switch itself, but GCC doesn't.)

Signed-off-by: Josh Stone <jistone(a)redhat.com&gt;
---
 libdw/ChangeLog    |  6 ++++++
 libdw/libdwP.h     | 36 +++++++++++++++++++++++++++++++++---
 libdw/libdw_form.c | 32 ++++----------------------------
 3 files changed, 43 insertions(+), 31 deletions(-)

diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index 79bb4b57fc4a..a2e4b142a107 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,3 +1,9 @@
[phone]  Josh Stone  <jistone(a)redhat.com&gt;
+
+	* libdw_form.c (__libdw_form_val_compute_len): Renamed function from
+	__libdw_form_val_len, now handling only non-constant form lengths.
+	* libdwP.h (__libdw_form_val_len): New inlined function.
+
 2013-12-09  Mark Wielaard  <mjw(a)redhat.com&gt;
 
 	* dwarf_getlocation.c (__libdw_intern_expression): Handle empty
diff --git a/libdw/libdwP.h b/libdw/libdwP.h
index 35ab6e79c3fa..e323ce34f66b 100644
--- a/libdw/libdwP.h
+++ b/libdw/libdwP.h
@@ -34,6 +34,7 @@
 #include <stdbool.h>
 
 #include <libdw.h>
+#include <dwarf.h>
 
 
 /* gettext helper macros.  */
@@ -403,11 +404,40 @@ extern Dwarf_Abbrev *__libdw_getabbrev (Dwarf *dbg, struct Dwarf_CU
*cu,
      __nonnull_attribute__ (1) internal_function;
 
 /* Helper functions for form handling.  */
-extern size_t __libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu,
-				    unsigned int form,
-				    const unsigned char *valp)
+extern size_t __libdw_form_val_compute_len (Dwarf *dbg, struct Dwarf_CU *cu,
+					    unsigned int form,
+					    const unsigned char *valp)
      __nonnull_attribute__ (1, 2, 4) internal_function;
 
+/* Find the length of a form attribute.  */
+static inline size_t
+__nonnull_attribute__ (1, 2, 4)
+__libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu,
+		      unsigned int form, const unsigned char *valp)
+{
+  /* Small lookup table of forms with fixed lengths.  Absent indexes are
+   * initialized 0, so any truly desired 0 is set to 0x80 and masked.  */
+  static const uint8_t form_lengths[] =
+    {
+      [DW_FORM_flag_present] = 0x80,
+      [DW_FORM_data1] = 1, [DW_FORM_ref1] = 1, [DW_FORM_flag] = 1,
+      [DW_FORM_data2] = 2, [DW_FORM_ref2] = 2,
+      [DW_FORM_data4] = 4, [DW_FORM_ref4] = 4,
+      [DW_FORM_data8] = 8, [DW_FORM_ref8] = 8, [DW_FORM_ref_sig8] = 8,
+    };
+
+  /* Return immediately for forms with fixed lengths.  */
+  if (form < sizeof form_lengths / sizeof form_lengths[0])
+    {
+      uint8_t len = form_lengths[form];
+      if (len != 0)
+	return len & 0x7f; /* Mask to allow 0x80 -> 0.  */
+    }
+
+  /* Other forms require some computation.  */
+  return __libdw_form_val_compute_len (dbg, cu, form, valp);
+}
+
 /* Helper function for DW_FORM_ref* handling.  */
 extern int __libdw_formref (Dwarf_Attribute *attr, Dwarf_Off *return_offset)
      __nonnull_attribute__ (1, 2) internal_function;
diff --git a/libdw/libdw_form.c b/libdw/libdw_form.c
index c476a6e31f32..cf8e4d854fcb 100644
--- a/libdw/libdw_form.c
+++ b/libdw/libdw_form.c
@@ -39,13 +39,15 @@
 
 size_t
 internal_function
-__libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu, unsigned int form,
-		      const unsigned char *valp)
+__libdw_form_val_compute_len (Dwarf *dbg, struct Dwarf_CU *cu,
+			      unsigned int form, const unsigned char *valp)
 {
   const unsigned char *saved;
   Dwarf_Word u128;
   size_t result;
 
+  /* NB: This doesn't cover constant form lengths, which are
+   * already handled by the inlined __libdw_form_val_len.  */
   switch (form)
     {
     case DW_FORM_addr:
@@ -82,32 +84,6 @@ __libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu, unsigned int
form,
       result = u128 + (valp - saved);
       break;
 
-    case DW_FORM_flag_present:
-      result = 0;
-      break;
-
-    case DW_FORM_ref1:
-    case DW_FORM_data1:
-    case DW_FORM_flag:
-      result = 1;
-      break;
-
-    case DW_FORM_data2:
-    case DW_FORM_ref2:
-      result = 2;
-      break;
-
-    case DW_FORM_data4:
-    case DW_FORM_ref4:
-      result = 4;
-      break;
-
-    case DW_FORM_data8:
-    case DW_FORM_ref8:
-    case DW_FORM_ref_sig8:
-      result = 8;
-      break;
-
     case DW_FORM_string:
       result = strlen ((char *) valp) + 1;
       break;
-- 
1.8.4.2

[PATCH v2 1/3] libdw: Add an inlined fast path for __libdw_form_val_len

[Petr Machata]

Josh Stone <jistone(a)redhat.com&gt; writes:

>  +  /* Small lookup table of forms with fixed lengths.  Absent indexes
> are
>  +   * initialized 0, so any truly desired 0 is set to 0x80 and masked.  */ 
/* GNU coding style has comments that go
   without continuation asterisks.  */

Sorry, I didn't notice this before.  Or maybe it wasn't there, I don't
know.  The patch is fine otherwise, so it can be committed without
re-posting after this is corrected.

>  +  /* NB: This doesn't cover constant form lengths, which are
>  +   * already handled by the inlined __libdw_form_val_len.  */ 
Here as well.

Thanks,
PM

[PATCH v2 2/3] libdw: Simplify and inline get_uleb128 and get_sleb128

[Josh Stone]

This removes the IS_LIBDW distinction so LEB128 operations are now
always inlined, and the implementations are simplified, more direct.

Signed-off-by: Josh Stone <jistone(a)redhat.com&gt;
---
 libdw/ChangeLog           |  15 +++++++
 libdw/Makefile.am         |   3 +-
 libdw/dwarf_getlocation.c |   3 +-
 libdw/memory-access.c     |  50 ----------------------
 libdw/memory-access.h     | 107 ++++++++++++++++------------------------------
 5 files changed, 55 insertions(+), 123 deletions(-)
 delete mode 100644 libdw/memory-access.c

diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index a2e4b142a107..aa7b9ca486c2 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,3 +1,18 @@
[phone]  Josh Stone  <jistone(a)redhat.com&gt;
+
+	* memory-access.h (get_uleb128_rest_return): Removed.
+	(get_sleb128_rest_return): Removed.
+	(get_uleb128_step): Make this a self-contained block.
+	(get_sleb128_step): Ditto, and use a bitfield to extend signs.
+	(get_uleb128): Make this wholly implemented by __libdw_get_uleb128.
+	(get_sleb128): Make this wholly implemented by __libdw_get_sleb128.
+	(__libdw_get_uleb128): Simplify and inline for all callers.
+	(__libdw_get_sleb128): Ditto.
+	* dwarf_getlocation.c (store_implicit_value): Void the unused uleb128.
+	* memory-access.c: Delete file.
+	* Makefile.am (libdw_a_SOURCES): Remove it.
+	(DEFS): Remove the now unused -DIS_LIBDW.
+
 2013-12-09  Josh Stone  <jistone(a)redhat.com&gt;
 
 	* libdw_form.c (__libdw_form_val_compute_len): Renamed function from
diff --git a/libdw/Makefile.am b/libdw/Makefile.am
index a22166a99e73..cd9e31435317 100644
--- a/libdw/Makefile.am
+++ b/libdw/Makefile.am
@@ -28,7 +28,6 @@
 ## not, see <http://www.gnu.org/licenses/>;.
 ##
 include $(top_srcdir)/config/eu.am
-DEFS += -DIS_LIBDW
 if BUILD_STATIC
 AM_CFLAGS += -fpic
 endif
@@ -79,7 +78,7 @@ libdw_a_SOURCES = dwarf_begin.c dwarf_begin_elf.c dwarf_end.c
dwarf_getelf.c \
 		  dwarf_getfuncs.c  \
 		  dwarf_decl_file.c dwarf_decl_line.c dwarf_decl_column.c \
 		  dwarf_func_inline.c dwarf_getsrc_file.c \
-		  libdw_findcu.c libdw_form.c libdw_alloc.c memory-access.c \
+		  libdw_findcu.c libdw_form.c libdw_alloc.c \
 		  libdw_visit_scopes.c \
 		  dwarf_entry_breakpoints.c \
 		  dwarf_next_cfi.c \
diff --git a/libdw/dwarf_getlocation.c b/libdw/dwarf_getlocation.c
index 4124ae36b84f..8dffb83f496f 100644
--- a/libdw/dwarf_getlocation.c
+++ b/libdw/dwarf_getlocation.c
@@ -100,8 +100,7 @@ store_implicit_value (Dwarf *dbg, void **cache, Dwarf_Op *op)
   struct loc_block_s *block = libdw_alloc (dbg, struct loc_block_s,
 					   sizeof (struct loc_block_s), 1);
   const unsigned char *data = (const unsigned char *) (uintptr_t) op->number2;
-  Dwarf_Word blength; // Ignored, equal to op->number.
-  get_uleb128 (blength, data);
+  (void) __libdw_get_uleb128 (&data); // Ignored, equal to op->number.
   block->addr = op;
   block->data = (unsigned char *) data;
   block->length = op->number;
diff --git a/libdw/memory-access.c b/libdw/memory-access.c
deleted file mode 100644
index 7666fb60a64c..000000000000
--- a/libdw/memory-access.c
+++ /dev/null
@@ -1,50 +0,0 @@
-/* Out of line functions for memory-access.h macros.
-   Copyright (C) 2005, 2006 Red Hat, Inc.
-   This file is part of elfutils.
-
-   This file is free software; you can redistribute it and/or modify
-   it under the terms of either
-
-     * the GNU Lesser General Public License as published by the Free
-       Software Foundation; either version 3 of the License, or (at
-       your option) any later version
-
-   or
-
-     * the GNU General Public License as published by the Free
-       Software Foundation; either version 2 of the License, or (at
-       your option) any later version
-
-   or both in parallel, as here.
-
-   elfutils is distributed in the hope that it will be useful, but
-   WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-   General Public License for more details.
-
-   You should have received copies of the GNU General Public License and
-   the GNU Lesser General Public License along with this program.  If
-   not, see <http://www.gnu.org/licenses/>;.  */
-
-#ifdef HAVE_CONFIG_H
-# include <config.h>
-#endif
-#include "libdwP.h"
-#include "memory-access.h"
-
-uint64_t
-internal_function
-__libdw_get_uleb128 (uint64_t acc, unsigned int i, const unsigned char **addrp)
-{
-  unsigned char __b;
-  get_uleb128_rest_return (acc, i, addrp);
-}
-
-int64_t
-internal_function
-__libdw_get_sleb128 (int64_t acc, unsigned int i, const unsigned char **addrp)
-{
-  unsigned char __b;
-  int64_t _v = acc;
-  get_sleb128_rest_return (acc, i, addrp);
-}
diff --git a/libdw/memory-access.h b/libdw/memory-access.h
index 16471990dfa0..d0ee63c53f99 100644
--- a/libdw/memory-access.h
+++ b/libdw/memory-access.h
@@ -37,90 +37,59 @@
 
 /* Number decoding macros.  See 7.6 Variable Length Data.  */
 
-#define get_uleb128_step(var, addr, nth, break)				      \
-    __b = *(addr)++;							      \
-    var |= (uintmax_t) (__b & 0x7f) << (nth * 7);			      \
-    if (likely ((__b & 0x80) == 0))					      \
-      break
-
-#define get_uleb128(var, addr)						      \
-  do {									      \
-    unsigned char __b;							      \
-    var = 0;								      \
-    get_uleb128_step (var, addr, 0, break);				      \
-    var = __libdw_get_uleb128 (var, 1, &(addr));			      \
-  } while (0)
+#define len_leb128(var) ((8 * sizeof (var) + 6) / 7)
 
-#define get_uleb128_rest_return(var, i, addrp)				      \
+#define get_uleb128_step(var, addr, nth)				      \
   do {									      \
-    for (; i < 10; ++i)							      \
-      {									      \
-	get_uleb128_step (var, *addrp, i, return var);			      \
-      }									      \
-    /* Other implementations set VALUE to UINT_MAX in this		      \
-       case.  So we better do this as well.  */				      \
-    return UINT64_MAX;							      \
+    unsigned char __b = *(addr)++;					      \
+    (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7);		      \
+    if (likely ((__b & 0x80) == 0))					      \
+      return (var);							      \
   } while (0)
 
-/* The signed case is similar, but we sign-extend the result.  */
+static inline uint64_t
+__libdw_get_uleb128 (const unsigned char **addrp)
+{
+  uint64_t acc = 0;
+  /* Unroll the first step to help the compiler optimize
+     for the common single-byte case.  */
+  get_uleb128_step (acc, *addrp, 0);
+  for (unsigned int i = 1; i < len_leb128 (acc); ++i)
+    get_uleb128_step (acc, *addrp, i);
+  /* Other implementations set VALUE to UINT_MAX in this
+     case.  So we better do this as well.  */
+  return UINT64_MAX;
+}
 
-#define get_sleb128_step(var, addr, nth, break)				      \
-    __b = *(addr)++;							      \
-    _v |= (uint64_t) (__b & 0x7f) << (nth * 7);				      \
-    if (likely ((__b & 0x80) == 0))					      \
-      {									      \
-	var = (_v << (64 - (nth * 7) - 7)) >> (64 - (nth * 7) - 7);	      \
-        break;					 			      \
-      }									      \
-    else do {} while (0)
+#define get_uleb128(var, addr) ((var) = __libdw_get_uleb128 (&(addr)))
 
-#define get_sleb128(var, addr)						      \
-  do {									      \
-    unsigned char __b;							      \
-    int64_t _v = 0;							      \
-    get_sleb128_step (var, addr, 0, break);				      \
-    var = __libdw_get_sleb128 (_v, 1, &(addr));				      \
-  } while (0)
+/* The signed case is similar, but we sign-extend the result.  */
 
-#define get_sleb128_rest_return(var, i, addrp)				      \
+#define get_sleb128_step(var, addr, nth)				      \
   do {									      \
-    for (; i < 9; ++i)							      \
+    unsigned char __b = *(addr)++;					      \
+    if (likely ((__b & 0x80) == 0))					      \
       {									      \
-	get_sleb128_step (var, *addrp, i, return var);			      \
+	struct { signed int i:7; } __s = { .i = __b };			      \
+	(var) |= (typeof (var)) __s.i << ((nth) * 7);			      \
+	return (var);							      \
       }									      \
-    __b = *(*addrp)++;							      \
-    if (likely ((__b & 0x80) == 0))					      \
-      return var | ((uint64_t) __b << 63);				      \
-    else								      \
-      /* Other implementations set VALUE to INT_MAX in this		      \
-	 case.  So we better do this as well.  */			      \
-      return INT64_MAX;							      \
+    (var) |= (typeof (var)) (__b & 0x7f) << ((nth) * 7);		      \
   } while (0)
 
-#ifdef IS_LIBDW
-extern uint64_t __libdw_get_uleb128 (uint64_t acc, unsigned int i,
-				     const unsigned char **addrp)
-     internal_function attribute_hidden;
-extern int64_t __libdw_get_sleb128 (int64_t acc, unsigned int i,
-				    const unsigned char **addrp)
-     internal_function attribute_hidden;
-#else
-static inline uint64_t
-__attribute__ ((unused))
-__libdw_get_uleb128 (uint64_t acc, unsigned int i, const unsigned char **addrp)
-{
-  unsigned char __b;
-  get_uleb128_rest_return (acc, i, addrp);
-}
 static inline int64_t
-__attribute__ ((unused))
-__libdw_get_sleb128 (int64_t acc, unsigned int i, const unsigned char **addrp)
+__libdw_get_sleb128 (const unsigned char **addrp)
 {
-  unsigned char __b;
-  int64_t _v = acc;
-  get_sleb128_rest_return (acc, i, addrp);
+  int64_t acc = 0;
+  /* Unrolling 0 like uleb128 didn't prove to benefit optimization.  */
+  for (unsigned int i = 0; i < len_leb128 (acc); ++i)
+    get_sleb128_step (acc, *addrp, i);
+  /* Other implementations set VALUE to INT_MAX in this
+     case.  So we better do this as well.  */
+  return INT64_MAX;
 }
-#endif
+
+#define get_sleb128(var, addr) ((var) = __libdw_get_sleb128 (&(addr)))
 
 
 /* We use simple memory access functions in case the hardware allows it.
-- 
1.8.4.2

[PATCH v2 2/3] libdw: Simplify and inline get_uleb128 and get_sleb128

[Petr Machata]

Josh Stone <jistone(a)redhat.com&gt; writes:

>  This removes the IS_LIBDW distinction so LEB128 operations are now
>  always inlined, and the implementations are simplified, more direct. 
This looks fine.

Thanks,
PM

[PATCH v2 3/3] lib: Avoid the hash-lookup division if possible

[Josh Stone]

For Dwarf_Abbrev codes, the most common case is that they're packed at
the low end, saving uleb128 encoding size.  Since the hash table is
always resized to be no more than 90% full, those codes are always less
than the table size, and dividing for the remainder is unnecessary.

Dwarf_Dies are frequently created anew, and need to find abbrev each
time, so even that one division becomes a noticeable hotspot.  This
patch adds a branch to avoid it, which is very predictable for the CPU.

Signed-off-by: Josh Stone <jistone(a)redhat.com&gt;
---
 lib/ChangeLog         | 4 ++++
 lib/dynamicsizehash.c | 5 +++--
 2 files changed, 7 insertions(+), 2 deletions(-)

diff --git a/lib/ChangeLog b/lib/ChangeLog
index 6ce3168f0ae6..9b8899e2ca5c 100644
--- a/lib/ChangeLog
+++ b/lib/ChangeLog
@@ -1,3 +1,7 @@
[phone]  Josh Stone  <jistone(a)redhat.com&gt;
+
+	* dynamicsizehash.c (lookup): Add a shortcut around division.
+
 2013-04-30  Jan Kratochvil  <jan.kratochvil(a)redhat.com&gt;
 
 	* eu-config.h (COMPAT_VERSION_NEWPROTO): New.  Twice.
diff --git a/lib/dynamicsizehash.c b/lib/dynamicsizehash.c
index 40f48d5ed119..acb360030376 100644
--- a/lib/dynamicsizehash.c
+++ b/lib/dynamicsizehash.c
@@ -49,8 +49,9 @@ lookup (htab, hval, val)
      HASHTYPE hval;
      TYPE val __attribute__ ((unused));
 {
-  /* First hash function: simply take the modul but prevent zero.  */
-  size_t idx = 1 + hval % htab->size;
+  /* First hash function: simply take the modul but prevent zero.  Small values
+   * can skip the division, which helps performance when this is common.  */
+  size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
 
   if (htab->table[idx].hashval != 0)
     {
-- 
1.8.4.2

[PATCH v2 3/3] lib: Avoid the hash-lookup division if possible

[Petr Machata]

Josh Stone <jistone(a)redhat.com&gt; writes:

>  -  /* First hash function: simply take the modul but prevent zero. 
> */
>  -  size_t idx = 1 + hval % htab->size;
>  +  /* First hash function: simply take the modul but prevent zero.  Small values
>  +   * can skip the division, which helps performance when this is common.  */
>  +  size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size); 
Again the continuation *.  Otherwise this is fine, feel free to commit
after correcting this nit.

Thanks,
PM

[PATCH v2 0/3] Performance tweaks for libdw

[Josh Stone]

With fixed comment formatting, these patches are now pushed.

Thanks!
Josh