This is the mail archive of the
binutils@sources.redhat.com
mailing list for the binutils project.
Re: [patch] ld speedup 1/3 (suffix merge)
On Thu, Sep 18, 2003 at 06:29:19PM +0200, Jakub Jelinek wrote:
> On Thu, Sep 18, 2003 at 05:22:12PM +0200, Jakub Jelinek wrote:
> > This patch seems to do all the string merging as current CVS merge.c
> > only if alignment == entsize (well, in that case it might create the
> > section even entsize bytes smaller by merging '\0' into some string).
>
> I should note that alignment > entsize merging is important.
> On IA-32 just strings longer or equal to 32 bytes get alignment > 1,
> but on lots of other arches each string is aligned to typically 4 or 8
> bytes.
> .debug_str (ie. largest user of string merging these days) is entsize 1
> alignment 1 on all arches though.
Well, seems like there are 2 cases if alignment of strings is bigger
than entsize. Either all strings are aligned the same, or their alignment
varries. The former can normally happen in GCC output, the latter means
somebody is not using separate sections for the various entsize/alignment
combinations and cannot happen in GCC output.
The former is solvable quite easily (see the updated patch below,
the latter I don't care how much will be optimized).
The patch adds strrevcmp alternative (strrevcmp_align) which sorts each
len & (alignment - 1) class of strings into a separate bucket
(when all strings have the same alignment, only strings in the same
bucket can be ever merged together).
--- bfd/elf-strtab.c.jj 2003-08-10 15:56:08.000000000 -0400
+++ bfd/elf-strtab.c 2003-09-18 18:52:35.000000000 -0400
@@ -1,5 +1,5 @@
/* ELF strtab with GC and suffix merging support.
- Copyright 2001, 2002 Free Software Foundation, Inc.
+ Copyright 2001, 2002, 2003 Free Software Foundation, Inc.
Written by Jakub Jelinek <jakub@redhat.com>.
This file is part of BFD, the Binary File Descriptor library.
@@ -30,15 +30,14 @@
struct elf_strtab_hash_entry
{
struct bfd_hash_entry root;
- /* Length of this entry. */
- unsigned int len;
+ /* Length of this entry. This includes the zero terminator. */
+ int len;
unsigned int refcount;
union {
/* Index within the merged section. */
bfd_size_type index;
- /* Entry this is a suffix of (if len is 0). */
+ /* Entry this is a suffix of (if len < 0). */
struct elf_strtab_hash_entry *suffix;
- struct elf_strtab_hash_entry *next;
} u;
};
@@ -158,6 +157,8 @@ _bfd_elf_strtab_add (struct elf_strtab_h
if (entry->len == 0)
{
entry->len = strlen (str) + 1;
+ /* 2G strings lose. */
+ BFD_ASSERT (entry->len > 0);
if (tab->size == tab->alloced)
{
bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
@@ -235,14 +236,14 @@ _bfd_elf_strtab_emit (register bfd *abfd
for (i = 1; i < tab->size; ++i)
{
register const char *str;
- register size_t len;
+ register unsigned int len;
- str = tab->array[i]->root.string;
- len = tab->array[i]->len;
BFD_ASSERT (tab->array[i]->refcount == 0);
- if (len == 0)
+ len = tab->array[i]->len;
+ if ((int) len < 0)
continue;
+ str = tab->array[i]->root.string;
if (bfd_bwrite (str, len, abfd) != len)
return FALSE;
@@ -256,37 +257,38 @@ _bfd_elf_strtab_emit (register bfd *abfd
/* Compare two elf_strtab_hash_entry structures. This is called via qsort. */
static int
-cmplengthentry (const void *a, const void *b)
+strrevcmp (const void *a, const void *b)
{
struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
+ unsigned int lenA = A->len;
+ unsigned int lenB = B->len;
+ const unsigned char *s = A->root.string + lenA - 1;
+ const unsigned char *t = B->root.string + lenB - 1;
+ int l = lenA < lenB ? lenA : lenB;
- if (A->len < B->len)
- return 1;
- else if (A->len > B->len)
- return -1;
-
- return memcmp (A->root.string, B->root.string, A->len);
+ while (l)
+ {
+ if (*s != *t)
+ return (int) *s - (int) *t;
+ s--;
+ t--;
+ l--;
+ }
+ return lenA - lenB;
}
static int
-last4_eq (const void *a, const void *b)
+is_suffix (const struct elf_strtab_hash_entry *A,
+ const struct elf_strtab_hash_entry *B)
{
- const struct elf_strtab_hash_entry *A = a;
- const struct elf_strtab_hash_entry *B = b;
-
- if (memcmp (A->root.string + A->len - 5, B->root.string + B->len - 5, 4)
- != 0)
- /* This was a hashtable collision. */
- return 0;
-
if (A->len <= B->len)
/* B cannot be a suffix of A unless A is equal to B, which is guaranteed
not to be equal by the hash table. */
return 0;
return memcmp (A->root.string + (A->len - B->len),
- B->root.string, B->len - 5) == 0;
+ B->root.string, B->len - 1) == 0;
}
/* This function assigns final string table offsets for used strings,
@@ -295,10 +297,8 @@ last4_eq (const void *a, const void *b)
void
_bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
{
- struct elf_strtab_hash_entry **array, **a, **end, *e;
- htab_t last4tab = NULL;
+ struct elf_strtab_hash_entry **array, **a, *e;
bfd_size_type size, amt;
- struct elf_strtab_hash_entry *last[256], **last_ptr[256];
/* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
@@ -306,105 +306,71 @@ _bfd_elf_strtab_finalize (struct elf_str
cycles. */
size_t i;
- /* Now sort the strings by length, longest first. */
- array = NULL;
+ /* Sort the strings by suffix and length. */
amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
array = bfd_malloc (amt);
if (array == NULL)
goto alloc_failure;
- memset (last, 0, sizeof (last));
- for (i = 0; i < 256; ++i)
- last_ptr[i] = &last[i];
for (i = 1, a = array; i < tab->size; ++i)
- if (tab->array[i]->refcount)
- *a++ = tab->array[i];
- else
- tab->array[i]->len = 0;
+ {
+ e = tab->array[i];
+ if (e->refcount)
+ {
+ *a++ = e;
+ /* Adjust the length to not include the zero terminator. */
+ e->len -= 1;
+ }
+ else
+ e->len = 0;
+ }
size = a - array;
+ if (size != 0)
+ {
+ qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
- qsort (array, size, sizeof (struct elf_strtab_hash_entry *), cmplengthentry);
+ /* Loop over the sorted array and merge suffixes. Start from the
+ end because we want eg.
- last4tab = htab_create_alloc (size * 4, NULL, last4_eq, NULL, calloc, free);
- if (last4tab == NULL)
- goto alloc_failure;
+ s1 -> "d"
+ s2 -> "bcd"
+ s3 -> "abcd"
- /* Now insert the strings into hash tables (strings with last 4 characters
- and strings with last character equal), look for longer strings which
- we're suffix of. */
- for (a = array, end = array + size; a < end; a++)
- {
- register hashval_t hash;
- unsigned int c;
- unsigned int j;
- const unsigned char *s;
- void **p;
+ to end up as
- e = *a;
- if (e->len > 4)
- {
- s = e->root.string + e->len - 1;
- hash = 0;
- for (j = 0; j < 4; j++)
- {
- c = *--s;
- hash += c + (c << 17);
- hash ^= hash >> 2;
- }
- p = htab_find_slot_with_hash (last4tab, e, hash, INSERT);
- if (p == NULL)
- goto alloc_failure;
- if (*p)
- {
- struct elf_strtab_hash_entry *ent;
+ s3 -> "abcd"
+ s2 _____^
+ s1 _______^
- ent = *p;
- e->u.suffix = ent;
- e->len = 0;
- continue;
- }
- else
- *p = e;
- }
- else
+ ie. we don't want s1 pointing into the old s2. */
+ e = *--a;
+ e->len += 1;
+ while (--a >= array)
{
- struct elf_strtab_hash_entry *tem;
+ struct elf_strtab_hash_entry *cmp = *a;
- c = e->root.string[e->len - 2] & 0xff;
-
- for (tem = last[c]; tem; tem = tem->u.next)
- if (tem->len > e->len
- && memcmp (tem->root.string + (tem->len - e->len),
- e->root.string, e->len - 1) == 0)
- break;
- if (tem)
+ cmp->len += 1;
+ if (is_suffix (e, cmp))
{
- e->u.suffix = tem;
- e->len = 0;
- continue;
+ cmp->u.suffix = e;
+ cmp->len = -cmp->len;
}
+ else
+ e = cmp;
}
-
- c = e->root.string[e->len - 2] & 0xff;
- /* Put longest strings first. */
- *last_ptr[c] = e;
- last_ptr[c] = &e->u.next;
- e->u.next = NULL;
}
alloc_failure:
if (array)
free (array);
- if (last4tab)
- htab_delete (last4tab);
- /* Now assign positions to the strings we want to keep. */
+ /* Assign positions to the strings we want to keep. */
size = 1;
for (i = 1; i < tab->size; ++i)
{
e = tab->array[i];
- if (e->refcount && e->len)
+ if (e->refcount && e->len > 0)
{
e->u.index = size;
size += e->len;
@@ -413,12 +379,11 @@ alloc_failure:
tab->sec_size = size;
- /* And now adjust the rest. */
+ /* Adjust the rest. */
for (i = 1; i < tab->size; ++i)
{
e = tab->array[i];
- if (e->refcount && ! e->len)
- e->u.index = e->u.suffix->u.index
- + (e->u.suffix->len - strlen (e->root.string) - 1);
+ if (e->refcount && e->len < 0)
+ e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
}
}
--- bfd/merge.c.jj 2003-09-05 09:58:37.000000000 -0400
+++ bfd/merge.c 2003-09-18 18:55:44.000000000 -0400
@@ -34,7 +34,7 @@ struct sec_merge_sec_info;
struct sec_merge_hash_entry
{
struct bfd_hash_entry root;
- /* Length of this entry. */
+ /* Length of this entry. This includes the zero terminator. */
unsigned int len;
/* Start of this string needs to be aligned to
alignment octets (not 1 << align). */
@@ -43,8 +43,6 @@ struct sec_merge_hash_entry
{
/* Index within the merged section. */
bfd_size_type index;
- /* Entity size (if present in suffix hash tables). */
- unsigned int entsize;
/* Entry this is a suffix of (if alignment is 0). */
struct sec_merge_hash_entry *suffix;
} u;
@@ -205,9 +203,12 @@ sec_merge_hash_lookup (struct sec_merge_
alignment, we need to insert another copy. */
if (hashp->alignment < alignment)
{
- /* Mark the less aligned copy as deleted. */
- hashp->len = 0;
- hashp->alignment = 0;
+ if (create)
+ {
+ /* Mark the less aligned copy as deleted. */
+ hashp->len = 0;
+ hashp->alignment = 0;
+ }
break;
}
return hashp;
@@ -287,7 +288,7 @@ sec_merge_add (struct sec_merge_hash *ta
}
static bfd_boolean
-sec_merge_emit (register bfd *abfd, struct sec_merge_hash_entry *entry)
+sec_merge_emit (bfd *abfd, struct sec_merge_hash_entry *entry)
{
struct sec_merge_sec_info *secinfo = entry->secinfo;
asection *sec = secinfo->sec;
@@ -420,79 +421,6 @@ _bfd_merge_section (bfd *abfd, void **ps
return FALSE;
}
-/* Compare two sec_merge_hash_entry structures. This is called via qsort. */
-
-static int
-cmplengthentry (const void *a, const void *b)
-{
- struct sec_merge_hash_entry * A = *(struct sec_merge_hash_entry **) a;
- struct sec_merge_hash_entry * B = *(struct sec_merge_hash_entry **) b;
-
- if (A->len < B->len)
- return 1;
- else if (A->len > B->len)
- return -1;
-
- return memcmp (A->root.string, B->root.string, A->len);
-}
-
-static int
-last4_eq (const void *a, const void *b)
-{
- struct sec_merge_hash_entry * A = (struct sec_merge_hash_entry *) a;
- struct sec_merge_hash_entry * B = (struct sec_merge_hash_entry *) b;
-
- if (memcmp (A->root.string + A->len - 5 * A->u.entsize,
- B->root.string + B->len - 5 * A->u.entsize,
- 4 * A->u.entsize) != 0)
- /* This was a hashtable collision. */
- return 0;
-
- if (A->len <= B->len)
- /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
- not to be equal by the hash table. */
- return 0;
-
- if (A->alignment < B->alignment
- || ((A->len - B->len) & (B->alignment - 1)))
- /* The suffix is not sufficiently aligned. */
- return 0;
-
- return memcmp (A->root.string + (A->len - B->len),
- B->root.string, B->len - 5 * A->u.entsize) == 0;
-}
-
-static int
-last_eq (const void *a, const void *b)
-{
- struct sec_merge_hash_entry * A = (struct sec_merge_hash_entry *) a;
- struct sec_merge_hash_entry * B = (struct sec_merge_hash_entry *) b;
-
- if (B->len >= 5 * A->u.entsize)
- /* Longer strings are just pushed into the hash table,
- they'll be used when looking up for very short strings. */
- return 0;
-
- if (memcmp (A->root.string + A->len - 2 * A->u.entsize,
- B->root.string + B->len - 2 * A->u.entsize,
- A->u.entsize) != 0)
- /* This was a hashtable collision. */
- return 0;
-
- if (A->len <= B->len)
- /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
- not to be equal by the hash table. */
- return 0;
-
- if (A->alignment < B->alignment
- || ((A->len - B->len) & (B->alignment - 1)))
- /* The suffix is not sufficiently aligned. */
- return 0;
-
- return memcmp (A->root.string + (A->len - B->len),
- B->root.string, B->len - 2 * A->u.entsize) == 0;
-}
-
/* Record one section into the hash table. */
static bfd_boolean
record_section (struct sec_merge_info *sinfo,
@@ -576,18 +504,83 @@ error_return:
return FALSE;
}
+static int
+strrevcmp (const void *a, const void *b)
+{
+ struct sec_merge_hash_entry *A = *(struct sec_merge_hash_entry **) a;
+ struct sec_merge_hash_entry *B = *(struct sec_merge_hash_entry **) b;
+ int lenA = A->len;
+ int lenB = B->len;
+ const unsigned char *s = A->root.string + lenA - 1;
+ const unsigned char *t = B->root.string + lenB - 1;
+ int l = lenA < lenB ? lenA : lenB;
+
+ while (l)
+ {
+ if (*s != *t)
+ return (int) *s - (int) *t;
+ s--;
+ t--;
+ l--;
+ }
+ return lenA - lenB;
+}
+
+/* Like strrevcmp, but for the case where all strings have the same
+ alignment > entsize. */
+
+static int
+strrevcmp_align (const void *a, const void *b)
+{
+ struct sec_merge_hash_entry *A = *(struct sec_merge_hash_entry **) a;
+ struct sec_merge_hash_entry *B = *(struct sec_merge_hash_entry **) b;
+ int lenA = A->len;
+ int lenB = B->len;
+ const unsigned char *s = A->root.string + lenA - 1;
+ const unsigned char *t = B->root.string + lenB - 1;
+ int l = lenA < lenB ? lenA : lenB;
+
+ if ((lenA & (A->alignment - 1)) < (lenB & (A->alignment - 1)))
+ return -1;
+ if ((lenA & (A->alignment - 1)) > (lenB & (A->alignment - 1)))
+ return 1;
+
+ while (l)
+ {
+ if (*s != *t)
+ return (int) *s - (int) *t;
+ s--;
+ t--;
+ l--;
+ }
+ return lenA - lenB;
+}
+
+static INLINE int
+is_suffix (const struct sec_merge_hash_entry *A,
+ const struct sec_merge_hash_entry *B)
+{
+ if (A->len <= B->len)
+ /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
+ not to be equal by the hash table. */
+ return 0;
+
+ return memcmp (A->root.string + (A->len - B->len),
+ B->root.string, B->len) == 0;
+}
+
/* This is a helper function for _bfd_merge_sections. It attempts to
merge strings matching suffixes of longer strings. */
static void
merge_strings (struct sec_merge_info *sinfo)
{
- struct sec_merge_hash_entry **array, **a, **end, *e;
+ struct sec_merge_hash_entry **array, **a, *e;
struct sec_merge_sec_info *secinfo;
- htab_t lasttab = NULL, last4tab = NULL;
bfd_size_type size, amt;
+ unsigned int alignment = 0;
+ bfd_boolean equal_align = TRUE;
- /* Now sort the strings by length, longest first. */
- array = NULL;
+ /* Now sort the strings */
amt = sinfo->htab->size * sizeof (struct sec_merge_hash_entry *);
array = (struct sec_merge_hash_entry **) bfd_malloc (amt);
if (array == NULL)
@@ -595,90 +588,47 @@ merge_strings (struct sec_merge_info *si
for (e = sinfo->htab->first, a = array; e; e = e->next)
if (e->alignment)
- *a++ = e;
+ {
+ *a++ = e;
+ /* Adjust the length to not include the zero terminator. */
+ e->len -= sinfo->htab->entsize;
+ if (!alignment)
+ alignment = e->alignment;
+ else if (alignment != e->alignment)
+ equal_align = FALSE;
+ }
sinfo->htab->size = a - array;
-
- qsort (array, (size_t) sinfo->htab->size,
- sizeof (struct sec_merge_hash_entry *), cmplengthentry);
-
- last4tab = htab_create_alloc ((size_t) sinfo->htab->size * 4,
- NULL, last4_eq, NULL, calloc, free);
- lasttab = htab_create_alloc ((size_t) sinfo->htab->size * 4,
- NULL, last_eq, NULL, calloc, free);
- if (lasttab == NULL || last4tab == NULL)
- goto alloc_failure;
-
- /* Now insert the strings into hash tables (strings with last 4 characters
- and strings with last character equal), look for longer strings which
- we're suffix of. */
- for (a = array, end = array + sinfo->htab->size; a < end; a++)
- {
- register hashval_t hash;
- unsigned int c;
- unsigned int i;
- const unsigned char *s;
- void **p;
-
- e = *a;
- e->u.entsize = sinfo->htab->entsize;
- if (e->len <= e->u.entsize)
- break;
- if (e->len > 4 * e->u.entsize)
- {
- s = (const unsigned char *) (e->root.string + e->len - e->u.entsize);
- hash = 0;
- for (i = 0; i < 4 * e->u.entsize; i++)
- {
- c = *--s;
- hash += c + (c << 17);
- hash ^= hash >> 2;
- }
- p = htab_find_slot_with_hash (last4tab, e, hash, INSERT);
- if (p == NULL)
- goto alloc_failure;
- if (*p)
+ if (sinfo->htab->size != 0)
+ {
+ qsort (array, (size_t) sinfo->htab->size,
+ sizeof (struct sec_merge_hash_entry *),
+ (equal_align && alignment > sinfo->htab->entsize)
+ ? strrevcmp_align : strrevcmp);
+
+ /* Loop over the sorted array and merge suffixes */
+ e = *--a;
+ e->len += sinfo->htab->entsize;
+ while (--a >= array)
+ {
+ struct sec_merge_hash_entry *cmp = *a;
+
+ cmp->len += sinfo->htab->entsize;
+ if (e->alignment >= cmp->alignment
+ && !((e->len - cmp->len) & (cmp->alignment - 1))
+ && is_suffix (e, cmp))
{
- struct sec_merge_hash_entry *ent;
-
- ent = (struct sec_merge_hash_entry *) *p;
- e->u.suffix = ent;
- e->alignment = 0;
- continue;
+ cmp->u.suffix = e;
+ cmp->alignment = 0;
}
else
- *p = e;
- }
- s = (const unsigned char *) (e->root.string + e->len - e->u.entsize);
- hash = 0;
- for (i = 0; i < e->u.entsize; i++)
- {
- c = *--s;
- hash += c + (c << 17);
- hash ^= hash >> 2;
+ e = cmp;
}
- p = htab_find_slot_with_hash (lasttab, e, hash, INSERT);
- if (p == NULL)
- goto alloc_failure;
- if (*p)
- {
- struct sec_merge_hash_entry *ent;
-
- ent = (struct sec_merge_hash_entry *) *p;
- e->u.suffix = ent;
- e->alignment = 0;
- }
- else
- *p = e;
}
alloc_failure:
if (array)
free (array);
- if (lasttab)
- htab_delete (lasttab);
- if (last4tab)
- htab_delete (last4tab);
/* Now assign positions to the strings we want to keep. */
size = 0;
--- ld/testsuite/ld-elf/merge2.d.jj 2003-09-18 18:52:35.000000000 -0400
+++ ld/testsuite/ld-elf/merge2.d 2003-09-18 18:52:35.000000000 -0400
@@ -0,0 +1,15 @@
+#source: merge2.s
+#ld: -T merge.ld
+#objdump: -s
+
+.*: file format .*elf.*
+
+Contents of section .text:
+ 1000 (3010)?0000(1030)? (3210)?0000(1032)? (3110)?0000(1031)? (3410)?0000(1034)? .*
+ 1010 (4010)?0000(1040)? (3810)?0000(1038)? (4810)?0000(1048)? (3c10)?0000(103c)? .*
+ 1020 (5010)?0000(1050)? (5410)?0000(1054)? (5810)?0000(1058)? (5010)?0000(1050)? .*
+Contents of section .rodata:
+ 1030 61626300 62000000 (78563412|12345678) 99999999 .*
+ 1040 (78563412|12345678) 00000000 99999999 00000000 .*
+ 1050 (78563412|12345678) 99999999 00000000 .*
+#pass
--- ld/testsuite/ld-elf/merge2.s.jj 2003-09-18 18:52:35.000000000 -0400
+++ ld/testsuite/ld-elf/merge2.s 2003-09-18 18:52:35.000000000 -0400
@@ -0,0 +1,58 @@
+ .section .rodata.str,"aMS","progbits",1
+.LC0:
+ .asciz "abc"
+.LC1:
+ .asciz "c"
+.LC2:
+ .asciz "bc"
+.LC3:
+ .asciz "b"
+
+
+ .section .rodata.str2,"aMS","progbits",4
+ .align 4
+.LC4:
+ .long 0x12345678
+ .long 0
+.LC5:
+ .long 0x12345678
+ .long 0x99999999
+ .long 0x12345678
+ .long 0
+.LC6:
+ .long 0x99999999
+ .long 0
+.LC7:
+ .long 0x99999999
+ .long 0x12345678
+ .long 0
+
+
+ .section .rodata.m,"aM","progbits",4
+ .align 4
+.LC8:
+ .long 0x12345678
+.LC9:
+ .long 0x99999999
+.LC10:
+ .long 0
+.LC11:
+ .long 0x12345678
+
+
+ .text
+ .global _start
+_start:
+ .long .LC0
+.LT0:
+ .long .LC1
+ .long .LC2
+ .long .LC3
+ .long .LC4
+ .long .LC5
+ .long .LC6
+ .long .LC7
+ .long .LC8
+ .long .LC9
+ .long .LC10
+ .long .LC11
Jakub