* [gold patch] Add inlined fast path for LEB128 routines
@ 2012-01-25 1:25 Cary Coutant
2012-01-25 5:40 ` Ian Lance Taylor
0 siblings, 1 reply; 3+ messages in thread
From: Cary Coutant @ 2012-01-25 1:25 UTC (permalink / raw)
To: Ian Lance Taylor, Binutils
[-- Attachment #1: Type: text/plain, Size: 1213 bytes --]
This patch adds an inlined fast path for the common case of a
single-byte LEB128 number. This provides significant speed-ups for
DWARF processing (mostly for the as-yet-unsubmitted changes to
generate the .gdb-index section). In my testing,
read_unsigned_LEB_128() accounted for more than 5% of the link time
when generating a gdb index; with this change, the LEB128 routines are
negligible, resulting in a 5% improvement. This should also improve
line number lookup and ODR detection.
I've also added new unit tests for the LEB128 readers.
Tested on x86_64. OK?
-cary
2012-01-24 Cary Coutant <ccoutant@google.com>
* int_encoding.cc (read_unsigned_LEB_128): Replaced with inline
definition and ...
(read_unsigned_LEB_128_x): ... this new function.
(read_signed_LEB_128): Replaced with inline definition and ...
(read_signed_LEB_128_x): ... this new function.
* int_encoding.h (read_unsigned_LEB_128_x): New function.
(read_unsigned_LEB_128): Add inline definition.
(read_signed_LEB_128_x): New function.
(read_signed_LEB_128): Add inline definition.
* testsuite/Makefile.am (leb128_unittest): New unit test.
* testsuite/Makefile.in: Regenerate.
* testsuite/leb128_unittest.cc: New unit test.
[-- Attachment #2: gold-fast-leb128-patch.txt --]
[-- Type: text/plain, Size: 13276 bytes --]
2012-01-24 Cary Coutant <ccoutant@google.com>
* int_encoding.cc (read_unsigned_LEB_128): Replaced with inline
definition and ...
(read_unsigned_LEB_128_x): ... this new function.
(read_signed_LEB_128): Replaced with inline definition and ...
(read_signed_LEB_128_x): ... this new function.
* int_encoding.h (read_unsigned_LEB_128_x): New function.
(read_unsigned_LEB_128): Add inline definition.
(read_signed_LEB_128_x): New function.
(read_signed_LEB_128): Add inline definition.
* testsuite/Makefile.am (leb128_unittest): New unit test.
* testsuite/Makefile.in: Regenerate.
* testsuite/leb128_unittest.cc: New unit test.
commit 3fd7bd00cd8f3be29377b059d7ac7e7e4cbe601e
Author: Cary Coutant <ccoutant@google.com>
Date: Tue Jan 24 17:09:09 2012 -0800
Add inlined fast path for LEB128 routines.
diff --git a/gold/int_encoding.cc b/gold/int_encoding.cc
index 6d635ac..a0715bc 100644
--- a/gold/int_encoding.cc
+++ b/gold/int_encoding.cc
@@ -32,15 +32,16 @@ namespace gold {
// Read an unsigned LEB128 number. Each byte contains 7 bits of
// information, plus one bit saying whether the number continues or
-// not.
+// not. BYTE contains the first byte of the number, and is guaranteed
+// to have the continuation bit set.
uint64_t
-read_unsigned_LEB_128(const unsigned char* buffer, size_t* len)
+read_unsigned_LEB_128_x(const unsigned char* buffer, size_t* len,
+ unsigned char byte)
{
- uint64_t result = 0;
- size_t num_read = 0;
- unsigned int shift = 0;
- unsigned char byte;
+ uint64_t result = static_cast<uint64_t>(byte & 0x7f);
+ size_t num_read = 1;
+ unsigned int shift = 7;
do
{
@@ -64,14 +65,16 @@ read_unsigned_LEB_128(const unsigned char* buffer, size_t* len)
// Read a signed LEB128 number. These are like regular LEB128
// numbers, except the last byte may have a sign bit set.
+// BYTE contains the first byte of the number, and is guaranteed
+// to have the continuation bit set.
int64_t
-read_signed_LEB_128(const unsigned char* buffer, size_t* len)
+read_signed_LEB_128_x(const unsigned char* buffer, size_t* len,
+ unsigned char byte)
{
- int64_t result = 0;
- int shift = 0;
- size_t num_read = 0;
- unsigned char byte;
+ int64_t result = static_cast<uint64_t>(byte & 0x7f);
+ int shift = 7;
+ size_t num_read = 1;
do
{
diff --git a/gold/int_encoding.h b/gold/int_encoding.h
index 6485a93..c4dee38 100644
--- a/gold/int_encoding.h
+++ b/gold/int_encoding.h
@@ -38,16 +38,48 @@ namespace gold
//
// Read a ULEB 128 encoded integer from BUFFER. Return the length of the
-// encoded integer at the location PLEN.
+// encoded integer at the location PLEN. The common case of a single-byte
+// value is handled inline, and multi-byte values are processed by the _x
+// routine, where BYTE is the first byte of the value.
uint64_t
-read_unsigned_LEB_128(const unsigned char* buffer, size_t* plen);
+read_unsigned_LEB_128_x(const unsigned char* buffer, size_t* plen,
+ unsigned char byte);
+
+inline uint64_t
+read_unsigned_LEB_128(const unsigned char* buffer, size_t* plen)
+{
+ unsigned char byte = *buffer++;
+
+ if (byte & 0x80)
+ return read_unsigned_LEB_128_x(buffer, plen, byte);
+
+ *plen = 1;
+ return static_cast<uint64_t>(byte);
+}
// Read an SLEB 128 encoded integer from BUFFER. Return the length of the
-// encoded integer at the location PLEN.
+// encoded integer at the location PLEN. The common case of a single-byte
+// value is handled inline, and multi-byte values are processed by the _x
+// routine, where BYTE is the first byte of the value.
int64_t
-read_signed_LEB_128(const unsigned char* buffer, size_t* plen);
+read_signed_LEB_128_x(const unsigned char* buffer, size_t* plen,
+ unsigned char byte);
+
+inline int64_t
+read_signed_LEB_128(const unsigned char* buffer, size_t* plen)
+{
+ unsigned char byte = *buffer++;
+
+ if (byte & 0x80)
+ return read_signed_LEB_128_x(buffer, plen, byte);
+
+ *plen = 1;
+ if (byte & 0x40)
+ return -(static_cast<int64_t>(1) << 7) | static_cast<int64_t>(byte);
+ return static_cast<int64_t>(byte);
+}
// Write a ULEB 128 encoded VALUE to BUFFER.
diff --git a/gold/testsuite/Makefile.am b/gold/testsuite/Makefile.am
index 794dac8..c7209f3 100644
--- a/gold/testsuite/Makefile.am
+++ b/gold/testsuite/Makefile.am
@@ -94,6 +94,9 @@ object_unittest_SOURCES = object_unittest.cc
check_PROGRAMS += binary_unittest
binary_unittest_SOURCES = binary_unittest.cc
+check_PROGRAMS += leb128_unittest
+leb128_unittest_SOURCES = leb128_unittest.cc
+
endif NATIVE_OR_CROSS_LINKER
# ---------------------------------------------------------------------
diff --git a/gold/testsuite/Makefile.in b/gold/testsuite/Makefile.in
index af62c8d..c5c1ae6 100644
--- a/gold/testsuite/Makefile.in
+++ b/gold/testsuite/Makefile.in
@@ -54,7 +54,7 @@ check_PROGRAMS = $(am__EXEEXT_1) $(am__EXEEXT_2) $(am__EXEEXT_3) \
$(am__EXEEXT_34) $(am__EXEEXT_35) $(am__EXEEXT_36) \
$(am__EXEEXT_37) $(am__EXEEXT_38)
@NATIVE_OR_CROSS_LINKER_TRUE@am__append_1 = object_unittest \
-@NATIVE_OR_CROSS_LINKER_TRUE@ binary_unittest
+@NATIVE_OR_CROSS_LINKER_TRUE@ binary_unittest leb128_unittest
# Test --detect-odr-violations
@@ -646,7 +646,8 @@ am_libgoldtest_a_OBJECTS = test.$(OBJEXT) testmain.$(OBJEXT) \
testfile.$(OBJEXT)
libgoldtest_a_OBJECTS = $(am_libgoldtest_a_OBJECTS)
@NATIVE_OR_CROSS_LINKER_TRUE@am__EXEEXT_1 = object_unittest$(EXEEXT) \
-@NATIVE_OR_CROSS_LINKER_TRUE@ binary_unittest$(EXEEXT)
+@NATIVE_OR_CROSS_LINKER_TRUE@ binary_unittest$(EXEEXT) \
+@NATIVE_OR_CROSS_LINKER_TRUE@ leb128_unittest$(EXEEXT)
@GCC_TRUE@@NATIVE_LINKER_TRUE@am__EXEEXT_2 = icf_virtual_function_folding_test$(EXEEXT) \
@GCC_TRUE@@NATIVE_LINKER_TRUE@ basic_test$(EXEEXT) \
@GCC_TRUE@@NATIVE_LINKER_TRUE@ basic_pic_test$(EXEEXT)
@@ -1221,6 +1222,13 @@ justsyms_exec_LINK = $(CCLD) $(AM_CFLAGS) $(CFLAGS) \
large_OBJECTS = $(am_large_OBJECTS)
large_LINK = $(CCLD) $(large_CFLAGS) $(CFLAGS) $(large_LDFLAGS) \
$(LDFLAGS) -o $@
+@NATIVE_OR_CROSS_LINKER_TRUE@am_leb128_unittest_OBJECTS = \
+@NATIVE_OR_CROSS_LINKER_TRUE@ leb128_unittest.$(OBJEXT)
+leb128_unittest_OBJECTS = $(am_leb128_unittest_OBJECTS)
+leb128_unittest_LDADD = $(LDADD)
+leb128_unittest_DEPENDENCIES = libgoldtest.a ../libgold.a \
+ ../../libiberty/libiberty.a $(am__DEPENDENCIES_1) \
+ $(am__DEPENDENCIES_1) $(am__DEPENDENCIES_1)
local_labels_test_SOURCES = local_labels_test.c
local_labels_test_OBJECTS = local_labels_test.$(OBJEXT)
local_labels_test_LDADD = $(LDADD)
@@ -1701,7 +1709,8 @@ SOURCES = $(libgoldtest_a_SOURCES) basic_pic_test.c basic_pie_test.c \
incremental_test_3.c incremental_test_4.c incremental_test_5.c \
incremental_test_6.c $(initpri1_SOURCES) $(initpri2_SOURCES) \
$(initpri3a_SOURCES) $(initpri3b_SOURCES) $(justsyms_SOURCES) \
- $(justsyms_exec_SOURCES) $(large_SOURCES) local_labels_test.c \
+ $(justsyms_exec_SOURCES) $(large_SOURCES) \
+ $(leb128_unittest_SOURCES) local_labels_test.c \
many_sections_r_test.c $(many_sections_test_SOURCES) \
$(object_unittest_SOURCES) permission_test.c plugin_test_1.c \
plugin_test_2.c plugin_test_3.c plugin_test_4.c \
@@ -2014,6 +2023,7 @@ LDADD = libgoldtest.a ../libgold.a ../../libiberty/libiberty.a $(LIBINTL) \
@NATIVE_OR_CROSS_LINKER_TRUE@object_unittest_SOURCES = object_unittest.cc
@NATIVE_OR_CROSS_LINKER_TRUE@binary_unittest_SOURCES = binary_unittest.cc
+@NATIVE_OR_CROSS_LINKER_TRUE@leb128_unittest_SOURCES = leb128_unittest.cc
@GCC_TRUE@@NATIVE_LINKER_TRUE@constructor_test_SOURCES = constructor_test.cc
@GCC_TRUE@@NATIVE_LINKER_TRUE@constructor_test_DEPENDENCIES = gcctestdir/ld
@GCC_TRUE@@NATIVE_LINKER_TRUE@constructor_test_LDFLAGS = -Bgcctestdir/
@@ -2942,6 +2952,9 @@ justsyms_exec$(EXEEXT): $(justsyms_exec_OBJECTS) $(justsyms_exec_DEPENDENCIES)
large$(EXEEXT): $(large_OBJECTS) $(large_DEPENDENCIES)
@rm -f large$(EXEEXT)
$(large_LINK) $(large_OBJECTS) $(large_LDADD) $(LIBS)
+leb128_unittest$(EXEEXT): $(leb128_unittest_OBJECTS) $(leb128_unittest_DEPENDENCIES)
+ @rm -f leb128_unittest$(EXEEXT)
+ $(CXXLINK) $(leb128_unittest_OBJECTS) $(leb128_unittest_LDADD) $(LIBS)
@GCC_FALSE@local_labels_test$(EXEEXT): $(local_labels_test_OBJECTS) $(local_labels_test_DEPENDENCIES)
@GCC_FALSE@ @rm -f local_labels_test$(EXEEXT)
@GCC_FALSE@ $(LINK) $(local_labels_test_OBJECTS) $(local_labels_test_LDADD) $(LIBS)
@@ -3322,6 +3335,7 @@ distclean-compile:
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/justsyms_1.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/justsyms_exec.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/large-large.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/leb128_unittest.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/local_labels_test.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/many_sections_r_test.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/many_sections_test.Po@am__quote@
@@ -3749,6 +3763,8 @@ object_unittest.log: object_unittest$(EXEEXT)
@p='object_unittest$(EXEEXT)'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
binary_unittest.log: binary_unittest$(EXEEXT)
@p='binary_unittest$(EXEEXT)'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
+leb128_unittest.log: leb128_unittest$(EXEEXT)
+ @p='leb128_unittest$(EXEEXT)'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
icf_virtual_function_folding_test.log: icf_virtual_function_folding_test$(EXEEXT)
@p='icf_virtual_function_folding_test$(EXEEXT)'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
basic_test.log: basic_test$(EXEEXT)
diff --git a/gold/testsuite/leb128_unittest.cc b/gold/testsuite/leb128_unittest.cc
new file mode 100644
index 0000000..05c7093
--- /dev/null
+++ b/gold/testsuite/leb128_unittest.cc
@@ -0,0 +1,88 @@
+// leb_unittest.cc -- test read_signed_LEB_128 and read_unsigned_LEB_128
+
+// Copyright 2012 Free Software Foundation, Inc.
+// Written by Cary Coutant <ccoutant@google.com>.
+
+// This file is part of gold.
+
+// This program is free software; you can redistribute it and/or modify
+// it under the terms of the GNU General Public License as published by
+// the Free Software Foundation; either version 3 of the License, or
+// (at your option) any later version.
+
+// This program 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 a copy of the GNU General Public License
+// along with this program; if not, write to the Free Software
+// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+// MA 02110-1301, USA.
+
+#include "gold.h"
+
+#include <sys/types.h>
+
+#include "int_encoding.h"
+
+#include "test.h"
+
+namespace gold_testsuite
+{
+
+using namespace gold;
+
+bool
+Leb128_test(Test_report*)
+{
+ size_t len;
+
+ // Unsigned tests.
+ static unsigned char u1[] = { 0 }; // 0
+ static unsigned char u2[] = { 1 }; // 1
+ static unsigned char u3[] = { 126 }; // 126
+ static unsigned char u4[] = { 127 }; // 127
+ static unsigned char u5[] = { 0x80+0, 1 }; // 128
+ static unsigned char u6[] = { 0x80+1, 1 }; // 129
+ static unsigned char u7[] = { 0x80+57, 100 }; // 12857
+ static unsigned char u8[] = { 0x80, 0x80, 0x80, 0x80,
+ 0x80, 0x80, 0x80, 0x80,
+ 0x80, 1}; // 1ULL << 63
+
+ // Signed tests.
+ static unsigned char s1[] = { 0 }; // 0
+ static unsigned char s2[] = { 1 }; // 1
+ static unsigned char s3[] = { 0x7e }; // -2
+ static unsigned char s4[] = { 0x80+127, 0 }; // 127
+ static unsigned char s5[] = { 0x80+1, 0x7f }; // -127
+ static unsigned char s6[] = { 0x80+0, 1 }; // 128
+ static unsigned char s7[] = { 0x80+0, 0x7f }; // -128
+ static unsigned char s8[] = { 0x80+1, 1 }; // 129
+ static unsigned char s9[] = { 0xff, 0x7e }; // -129
+
+ CHECK(read_unsigned_LEB_128(u1, &len) == 0 && len == sizeof(u1));
+ CHECK(read_unsigned_LEB_128(u2, &len) == 1 && len == sizeof(u2));
+ CHECK(read_unsigned_LEB_128(u3, &len) == 126 && len == sizeof(u3));
+ CHECK(read_unsigned_LEB_128(u4, &len) == 127 && len == sizeof(u4));
+ CHECK(read_unsigned_LEB_128(u5, &len) == 128 && len == sizeof(u5));
+ CHECK(read_unsigned_LEB_128(u6, &len) == 129 && len == sizeof(u6));
+ CHECK(read_unsigned_LEB_128(u7, &len) == 12857 && len == sizeof(u7));
+ CHECK(read_unsigned_LEB_128(u8, &len) == (1ULL << 63) && len == sizeof(u8));
+
+ CHECK(read_signed_LEB_128(s1, &len) == 0 && len == sizeof(s1));
+ CHECK(read_signed_LEB_128(s2, &len) == 1 && len == sizeof(s2));
+ CHECK(read_signed_LEB_128(s3, &len) == -2 && len == sizeof(s3));
+ CHECK(read_signed_LEB_128(s4, &len) == 127 && len == sizeof(s4));
+ CHECK(read_signed_LEB_128(s5, &len) == -127 && len == sizeof(s5));
+ CHECK(read_signed_LEB_128(s6, &len) == 128 && len == sizeof(s6));
+ CHECK(read_signed_LEB_128(s7, &len) == -128 && len == sizeof(s7));
+ CHECK(read_signed_LEB_128(s8, &len) == 129 && len == sizeof(s8));
+ CHECK(read_signed_LEB_128(s9, &len) == -129 && len == sizeof(s9));
+
+ return true;
+}
+
+Register_test leb128_register("LEB128", Leb128_test);
+
+} // End namespace gold_testsuite.
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [gold patch] Add inlined fast path for LEB128 routines
2012-01-25 1:25 [gold patch] Add inlined fast path for LEB128 routines Cary Coutant
@ 2012-01-25 5:40 ` Ian Lance Taylor
2012-01-25 7:37 ` Cary Coutant
0 siblings, 1 reply; 3+ messages in thread
From: Ian Lance Taylor @ 2012-01-25 5:40 UTC (permalink / raw)
To: Cary Coutant; +Cc: Binutils
Cary Coutant <ccoutant@google.com> writes:
> 2012-01-24 Cary Coutant <ccoutant@google.com>
>
> * int_encoding.cc (read_unsigned_LEB_128): Replaced with inline
> definition and ...
> (read_unsigned_LEB_128_x): ... this new function.
> (read_signed_LEB_128): Replaced with inline definition and ...
> (read_signed_LEB_128_x): ... this new function.
> * int_encoding.h (read_unsigned_LEB_128_x): New function.
> (read_unsigned_LEB_128): Add inline definition.
> (read_signed_LEB_128_x): New function.
> (read_signed_LEB_128): Add inline definition.
> * testsuite/Makefile.am (leb128_unittest): New unit test.
> * testsuite/Makefile.in: Regenerate.
> * testsuite/leb128_unittest.cc: New unit test.
> + if (byte & 0x80)
> + return read_unsigned_LEB_128_x(buffer, plen, byte);
Write ((byte & 0x80) != 0)
> + if (byte & 0x80)
> + return read_signed_LEB_128_x(buffer, plen, byte);
Here too.
This is OK with those changes.
Thanks.
Ian
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [gold patch] Add inlined fast path for LEB128 routines
2012-01-25 5:40 ` Ian Lance Taylor
@ 2012-01-25 7:37 ` Cary Coutant
0 siblings, 0 replies; 3+ messages in thread
From: Cary Coutant @ 2012-01-25 7:37 UTC (permalink / raw)
To: Ian Lance Taylor; +Cc: Binutils
[-- Attachment #1: Type: text/plain, Size: 994 bytes --]
>> + if (byte & 0x80)
>> + return read_unsigned_LEB_128_x(buffer, plen, byte);
>
> Write ((byte & 0x80) != 0)
>
>> + if (byte & 0x80)
>> + return read_signed_LEB_128_x(buffer, plen, byte);
>
> Here too.
>
> This is OK with those changes.
Done and committed, thanks. The patch as committed is attached...
-cary
2012-01-24 Cary Coutant <ccoutant@google.com>
* int_encoding.cc (read_unsigned_LEB_128): Replaced with inline
definition and ...
(read_unsigned_LEB_128_x): ... this new function.
(read_signed_LEB_128): Replaced with inline definition and ...
(read_signed_LEB_128_x): ... this new function.
* int_encoding.h (read_unsigned_LEB_128_x): New function.
(read_unsigned_LEB_128): Add inline definition.
(read_signed_LEB_128_x): New function.
(read_signed_LEB_128): Add inline definition.
* testsuite/Makefile.am (leb128_unittest): New unit test.
* testsuite/Makefile.in: Regenerate.
* testsuite/leb128_unittest.cc: New unit test.
[-- Attachment #2: gold-fast-leb128-patch.txt --]
[-- Type: text/plain, Size: 13656 bytes --]
2012-01-24 Cary Coutant <ccoutant@google.com>
* int_encoding.cc (read_unsigned_LEB_128): Replaced with inline
definition and ...
(read_unsigned_LEB_128_x): ... this new function.
(read_signed_LEB_128): Replaced with inline definition and ...
(read_signed_LEB_128_x): ... this new function.
* int_encoding.h (read_unsigned_LEB_128_x): New function.
(read_unsigned_LEB_128): Add inline definition.
(read_signed_LEB_128_x): New function.
(read_signed_LEB_128): Add inline definition.
* testsuite/Makefile.am (leb128_unittest): New unit test.
* testsuite/Makefile.in: Regenerate.
* testsuite/leb128_unittest.cc: New unit test.
commit 839ec90a0a50a935305dbcee16ff0e97eeeb3af0
Author: Cary Coutant <ccoutant@google.com>
Date: Tue Jan 24 17:09:09 2012 -0800
Add inlined fast path for LEB128 routines.
diff --git a/gold/int_encoding.cc b/gold/int_encoding.cc
index 6d635ac..7887477 100644
--- a/gold/int_encoding.cc
+++ b/gold/int_encoding.cc
@@ -32,19 +32,20 @@ namespace gold {
// Read an unsigned LEB128 number. Each byte contains 7 bits of
// information, plus one bit saying whether the number continues or
-// not.
+// not. BYTE contains the first byte of the number, and is guaranteed
+// to have the continuation bit set.
uint64_t
-read_unsigned_LEB_128(const unsigned char* buffer, size_t* len)
+read_unsigned_LEB_128_x(const unsigned char* buffer, size_t* len,
+ unsigned char byte)
{
- uint64_t result = 0;
- size_t num_read = 0;
- unsigned int shift = 0;
- unsigned char byte;
+ uint64_t result = static_cast<uint64_t>(byte & 0x7f);
+ size_t num_read = 1;
+ unsigned int shift = 7;
do
{
- if (num_read >= 64 / 7)
+ if (num_read > 64 / 7 + 1)
{
gold_warning(_("Unusually large LEB128 decoded, "
"debug information may be corrupted"));
@@ -64,18 +65,20 @@ read_unsigned_LEB_128(const unsigned char* buffer, size_t* len)
// Read a signed LEB128 number. These are like regular LEB128
// numbers, except the last byte may have a sign bit set.
+// BYTE contains the first byte of the number, and is guaranteed
+// to have the continuation bit set.
int64_t
-read_signed_LEB_128(const unsigned char* buffer, size_t* len)
+read_signed_LEB_128_x(const unsigned char* buffer, size_t* len,
+ unsigned char byte)
{
- int64_t result = 0;
- int shift = 0;
- size_t num_read = 0;
- unsigned char byte;
+ int64_t result = static_cast<uint64_t>(byte & 0x7f);
+ int shift = 7;
+ size_t num_read = 1;
do
{
- if (num_read >= 64 / 7)
+ if (num_read > 64 / 7 + 1)
{
gold_warning(_("Unusually large LEB128 decoded, "
"debug information may be corrupted"));
diff --git a/gold/int_encoding.h b/gold/int_encoding.h
index 6485a93..467d224 100644
--- a/gold/int_encoding.h
+++ b/gold/int_encoding.h
@@ -38,16 +38,48 @@ namespace gold
//
// Read a ULEB 128 encoded integer from BUFFER. Return the length of the
-// encoded integer at the location PLEN.
+// encoded integer at the location PLEN. The common case of a single-byte
+// value is handled inline, and multi-byte values are processed by the _x
+// routine, where BYTE is the first byte of the value.
uint64_t
-read_unsigned_LEB_128(const unsigned char* buffer, size_t* plen);
+read_unsigned_LEB_128_x(const unsigned char* buffer, size_t* plen,
+ unsigned char byte);
+
+inline uint64_t
+read_unsigned_LEB_128(const unsigned char* buffer, size_t* plen)
+{
+ unsigned char byte = *buffer++;
+
+ if ((byte & 0x80) != 0)
+ return read_unsigned_LEB_128_x(buffer, plen, byte);
+
+ *plen = 1;
+ return static_cast<uint64_t>(byte);
+}
// Read an SLEB 128 encoded integer from BUFFER. Return the length of the
-// encoded integer at the location PLEN.
+// encoded integer at the location PLEN. The common case of a single-byte
+// value is handled inline, and multi-byte values are processed by the _x
+// routine, where BYTE is the first byte of the value.
int64_t
-read_signed_LEB_128(const unsigned char* buffer, size_t* plen);
+read_signed_LEB_128_x(const unsigned char* buffer, size_t* plen,
+ unsigned char byte);
+
+inline int64_t
+read_signed_LEB_128(const unsigned char* buffer, size_t* plen)
+{
+ unsigned char byte = *buffer++;
+
+ if ((byte & 0x80) != 0)
+ return read_signed_LEB_128_x(buffer, plen, byte);
+
+ *plen = 1;
+ if (byte & 0x40)
+ return -(static_cast<int64_t>(1) << 7) | static_cast<int64_t>(byte);
+ return static_cast<int64_t>(byte);
+}
// Write a ULEB 128 encoded VALUE to BUFFER.
diff --git a/gold/testsuite/Makefile.am b/gold/testsuite/Makefile.am
index 794dac8..c7209f3 100644
--- a/gold/testsuite/Makefile.am
+++ b/gold/testsuite/Makefile.am
@@ -94,6 +94,9 @@ object_unittest_SOURCES = object_unittest.cc
check_PROGRAMS += binary_unittest
binary_unittest_SOURCES = binary_unittest.cc
+check_PROGRAMS += leb128_unittest
+leb128_unittest_SOURCES = leb128_unittest.cc
+
endif NATIVE_OR_CROSS_LINKER
# ---------------------------------------------------------------------
diff --git a/gold/testsuite/Makefile.in b/gold/testsuite/Makefile.in
index af62c8d..c5c1ae6 100644
--- a/gold/testsuite/Makefile.in
+++ b/gold/testsuite/Makefile.in
@@ -54,7 +54,7 @@ check_PROGRAMS = $(am__EXEEXT_1) $(am__EXEEXT_2) $(am__EXEEXT_3) \
$(am__EXEEXT_34) $(am__EXEEXT_35) $(am__EXEEXT_36) \
$(am__EXEEXT_37) $(am__EXEEXT_38)
@NATIVE_OR_CROSS_LINKER_TRUE@am__append_1 = object_unittest \
-@NATIVE_OR_CROSS_LINKER_TRUE@ binary_unittest
+@NATIVE_OR_CROSS_LINKER_TRUE@ binary_unittest leb128_unittest
# Test --detect-odr-violations
@@ -646,7 +646,8 @@ am_libgoldtest_a_OBJECTS = test.$(OBJEXT) testmain.$(OBJEXT) \
testfile.$(OBJEXT)
libgoldtest_a_OBJECTS = $(am_libgoldtest_a_OBJECTS)
@NATIVE_OR_CROSS_LINKER_TRUE@am__EXEEXT_1 = object_unittest$(EXEEXT) \
-@NATIVE_OR_CROSS_LINKER_TRUE@ binary_unittest$(EXEEXT)
+@NATIVE_OR_CROSS_LINKER_TRUE@ binary_unittest$(EXEEXT) \
+@NATIVE_OR_CROSS_LINKER_TRUE@ leb128_unittest$(EXEEXT)
@GCC_TRUE@@NATIVE_LINKER_TRUE@am__EXEEXT_2 = icf_virtual_function_folding_test$(EXEEXT) \
@GCC_TRUE@@NATIVE_LINKER_TRUE@ basic_test$(EXEEXT) \
@GCC_TRUE@@NATIVE_LINKER_TRUE@ basic_pic_test$(EXEEXT)
@@ -1221,6 +1222,13 @@ justsyms_exec_LINK = $(CCLD) $(AM_CFLAGS) $(CFLAGS) \
large_OBJECTS = $(am_large_OBJECTS)
large_LINK = $(CCLD) $(large_CFLAGS) $(CFLAGS) $(large_LDFLAGS) \
$(LDFLAGS) -o $@
+@NATIVE_OR_CROSS_LINKER_TRUE@am_leb128_unittest_OBJECTS = \
+@NATIVE_OR_CROSS_LINKER_TRUE@ leb128_unittest.$(OBJEXT)
+leb128_unittest_OBJECTS = $(am_leb128_unittest_OBJECTS)
+leb128_unittest_LDADD = $(LDADD)
+leb128_unittest_DEPENDENCIES = libgoldtest.a ../libgold.a \
+ ../../libiberty/libiberty.a $(am__DEPENDENCIES_1) \
+ $(am__DEPENDENCIES_1) $(am__DEPENDENCIES_1)
local_labels_test_SOURCES = local_labels_test.c
local_labels_test_OBJECTS = local_labels_test.$(OBJEXT)
local_labels_test_LDADD = $(LDADD)
@@ -1701,7 +1709,8 @@ SOURCES = $(libgoldtest_a_SOURCES) basic_pic_test.c basic_pie_test.c \
incremental_test_3.c incremental_test_4.c incremental_test_5.c \
incremental_test_6.c $(initpri1_SOURCES) $(initpri2_SOURCES) \
$(initpri3a_SOURCES) $(initpri3b_SOURCES) $(justsyms_SOURCES) \
- $(justsyms_exec_SOURCES) $(large_SOURCES) local_labels_test.c \
+ $(justsyms_exec_SOURCES) $(large_SOURCES) \
+ $(leb128_unittest_SOURCES) local_labels_test.c \
many_sections_r_test.c $(many_sections_test_SOURCES) \
$(object_unittest_SOURCES) permission_test.c plugin_test_1.c \
plugin_test_2.c plugin_test_3.c plugin_test_4.c \
@@ -2014,6 +2023,7 @@ LDADD = libgoldtest.a ../libgold.a ../../libiberty/libiberty.a $(LIBINTL) \
@NATIVE_OR_CROSS_LINKER_TRUE@object_unittest_SOURCES = object_unittest.cc
@NATIVE_OR_CROSS_LINKER_TRUE@binary_unittest_SOURCES = binary_unittest.cc
+@NATIVE_OR_CROSS_LINKER_TRUE@leb128_unittest_SOURCES = leb128_unittest.cc
@GCC_TRUE@@NATIVE_LINKER_TRUE@constructor_test_SOURCES = constructor_test.cc
@GCC_TRUE@@NATIVE_LINKER_TRUE@constructor_test_DEPENDENCIES = gcctestdir/ld
@GCC_TRUE@@NATIVE_LINKER_TRUE@constructor_test_LDFLAGS = -Bgcctestdir/
@@ -2942,6 +2952,9 @@ justsyms_exec$(EXEEXT): $(justsyms_exec_OBJECTS) $(justsyms_exec_DEPENDENCIES)
large$(EXEEXT): $(large_OBJECTS) $(large_DEPENDENCIES)
@rm -f large$(EXEEXT)
$(large_LINK) $(large_OBJECTS) $(large_LDADD) $(LIBS)
+leb128_unittest$(EXEEXT): $(leb128_unittest_OBJECTS) $(leb128_unittest_DEPENDENCIES)
+ @rm -f leb128_unittest$(EXEEXT)
+ $(CXXLINK) $(leb128_unittest_OBJECTS) $(leb128_unittest_LDADD) $(LIBS)
@GCC_FALSE@local_labels_test$(EXEEXT): $(local_labels_test_OBJECTS) $(local_labels_test_DEPENDENCIES)
@GCC_FALSE@ @rm -f local_labels_test$(EXEEXT)
@GCC_FALSE@ $(LINK) $(local_labels_test_OBJECTS) $(local_labels_test_LDADD) $(LIBS)
@@ -3322,6 +3335,7 @@ distclean-compile:
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/justsyms_1.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/justsyms_exec.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/large-large.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/leb128_unittest.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/local_labels_test.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/many_sections_r_test.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/many_sections_test.Po@am__quote@
@@ -3749,6 +3763,8 @@ object_unittest.log: object_unittest$(EXEEXT)
@p='object_unittest$(EXEEXT)'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
binary_unittest.log: binary_unittest$(EXEEXT)
@p='binary_unittest$(EXEEXT)'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
+leb128_unittest.log: leb128_unittest$(EXEEXT)
+ @p='leb128_unittest$(EXEEXT)'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
icf_virtual_function_folding_test.log: icf_virtual_function_folding_test$(EXEEXT)
@p='icf_virtual_function_folding_test$(EXEEXT)'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
basic_test.log: basic_test$(EXEEXT)
diff --git a/gold/testsuite/leb128_unittest.cc b/gold/testsuite/leb128_unittest.cc
new file mode 100644
index 0000000..05c7093
--- /dev/null
+++ b/gold/testsuite/leb128_unittest.cc
@@ -0,0 +1,88 @@
+// leb_unittest.cc -- test read_signed_LEB_128 and read_unsigned_LEB_128
+
+// Copyright 2012 Free Software Foundation, Inc.
+// Written by Cary Coutant <ccoutant@google.com>.
+
+// This file is part of gold.
+
+// This program is free software; you can redistribute it and/or modify
+// it under the terms of the GNU General Public License as published by
+// the Free Software Foundation; either version 3 of the License, or
+// (at your option) any later version.
+
+// This program 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 a copy of the GNU General Public License
+// along with this program; if not, write to the Free Software
+// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+// MA 02110-1301, USA.
+
+#include "gold.h"
+
+#include <sys/types.h>
+
+#include "int_encoding.h"
+
+#include "test.h"
+
+namespace gold_testsuite
+{
+
+using namespace gold;
+
+bool
+Leb128_test(Test_report*)
+{
+ size_t len;
+
+ // Unsigned tests.
+ static unsigned char u1[] = { 0 }; // 0
+ static unsigned char u2[] = { 1 }; // 1
+ static unsigned char u3[] = { 126 }; // 126
+ static unsigned char u4[] = { 127 }; // 127
+ static unsigned char u5[] = { 0x80+0, 1 }; // 128
+ static unsigned char u6[] = { 0x80+1, 1 }; // 129
+ static unsigned char u7[] = { 0x80+57, 100 }; // 12857
+ static unsigned char u8[] = { 0x80, 0x80, 0x80, 0x80,
+ 0x80, 0x80, 0x80, 0x80,
+ 0x80, 1}; // 1ULL << 63
+
+ // Signed tests.
+ static unsigned char s1[] = { 0 }; // 0
+ static unsigned char s2[] = { 1 }; // 1
+ static unsigned char s3[] = { 0x7e }; // -2
+ static unsigned char s4[] = { 0x80+127, 0 }; // 127
+ static unsigned char s5[] = { 0x80+1, 0x7f }; // -127
+ static unsigned char s6[] = { 0x80+0, 1 }; // 128
+ static unsigned char s7[] = { 0x80+0, 0x7f }; // -128
+ static unsigned char s8[] = { 0x80+1, 1 }; // 129
+ static unsigned char s9[] = { 0xff, 0x7e }; // -129
+
+ CHECK(read_unsigned_LEB_128(u1, &len) == 0 && len == sizeof(u1));
+ CHECK(read_unsigned_LEB_128(u2, &len) == 1 && len == sizeof(u2));
+ CHECK(read_unsigned_LEB_128(u3, &len) == 126 && len == sizeof(u3));
+ CHECK(read_unsigned_LEB_128(u4, &len) == 127 && len == sizeof(u4));
+ CHECK(read_unsigned_LEB_128(u5, &len) == 128 && len == sizeof(u5));
+ CHECK(read_unsigned_LEB_128(u6, &len) == 129 && len == sizeof(u6));
+ CHECK(read_unsigned_LEB_128(u7, &len) == 12857 && len == sizeof(u7));
+ CHECK(read_unsigned_LEB_128(u8, &len) == (1ULL << 63) && len == sizeof(u8));
+
+ CHECK(read_signed_LEB_128(s1, &len) == 0 && len == sizeof(s1));
+ CHECK(read_signed_LEB_128(s2, &len) == 1 && len == sizeof(s2));
+ CHECK(read_signed_LEB_128(s3, &len) == -2 && len == sizeof(s3));
+ CHECK(read_signed_LEB_128(s4, &len) == 127 && len == sizeof(s4));
+ CHECK(read_signed_LEB_128(s5, &len) == -127 && len == sizeof(s5));
+ CHECK(read_signed_LEB_128(s6, &len) == 128 && len == sizeof(s6));
+ CHECK(read_signed_LEB_128(s7, &len) == -128 && len == sizeof(s7));
+ CHECK(read_signed_LEB_128(s8, &len) == 129 && len == sizeof(s8));
+ CHECK(read_signed_LEB_128(s9, &len) == -129 && len == sizeof(s9));
+
+ return true;
+}
+
+Register_test leb128_register("LEB128", Leb128_test);
+
+} // End namespace gold_testsuite.
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2012-01-25 7:37 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-01-25 1:25 [gold patch] Add inlined fast path for LEB128 routines Cary Coutant
2012-01-25 5:40 ` Ian Lance Taylor
2012-01-25 7:37 ` Cary Coutant
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).