This is the mail archive of the
binutils@sources.redhat.com
mailing list for the binutils project.
Re: PATCH: Use a double section list to speed up linker by 30%
- From: "H. J. Lu" <hjl at lucon dot org>
- To: binutils at sources dot redhat dot com
- Date: Sun, 1 May 2005 12:47:57 -0700
- Subject: Re: PATCH: Use a double section list to speed up linker by 30%
- References: <20050501165707.GA13713@lucon.org>
On Sun, May 01, 2005 at 09:57:07AM -0700, H. J. Lu wrote:
> Linker is very slow on input files with many sections. The 64k section
> test is only enabled for CRIS. I did a profile. 70% of linker time is
> spent in lang_check_section_addresses:
>
> Flat profile:
>
> Each sample counts as 0.01 seconds.
> % cumulative self self total
> time seconds seconds calls Ks/call Ks/call name
> 72.92 948.31 948.31 1 0.95 0.95 lang_check_section_addresses
> 22.37 1239.21 290.90 132089 0.00 0.00 lang_output_section_find_1
>
> The main problem is we use a single section list. We have to scan the
> whole list for anything. In case of address overlap check, we only
> need to check the previous section. There are many other places in
> bfd, assembler and linker where a double section list will help. With
> this patch, I got 30% linker speed up in 64k section test:
>
> The old linker:
>
> sh 1 502.74s user 0.90s system 99% cpu 8:23.73 total
>
> The new linker:
>
> sh 1 340.58s user 0.90s system 99% cpu 5:41.55 total
>
> The profile data shows:
>
> Flat profile:
>
> Each sample counts as 0.01 seconds.
> % cumulative self self total
> time seconds seconds calls s/call s/call name
> 81.20 256.42 256.42 132089 0.00 0.00 lang_output_section_find_1
> 13.27 298.33 41.91 673985 0.00 0.00 bfd_hash_lookup
>
This is the updated patch to fix build on MIPS and ia64.
H.J.
---
bfd/
2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
* bfd.c (bfd): Remove section_tail and add section_last.
(bfd_preserve): Likewise.
(bfd_preserve_save): Likewise.
(bfd_preserve_restore): Likewise.
* opncls.c (_bfd_new_bfd): Likewise.
* elfxx-ia64.c (elfNN_ia64_object_p): Use
bfd_section_double_list_remove to remove sections.
* section.c (bfd_section): Add prev.
(bfd_section_double_list_remove): New.
(bfd_section_list_remove): Updated.
(bfd_section_double_list_append): New.
(bfd_section_double_list_insert_after): New.
(bfd_section_list_insert): Updated.
(bfd_section_double_list_insert_before): New.
(bfd_section_removed_from_list): Updated.
(STD_SECTION): Initialize prev.
(bfd_section_init): Updated.
(bfd_section_list_clear): Updated.
* coffcode.h (coff_compute_section_file_positions): Updated.
* xcofflink.c (_bfd_xcoff_bfd_final_link): Updated.
* ecoff.c (bfd_debug_section): Initialize prev.
* bfd-in2.h: Regenerated.
gas/
2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
* write.c (write_object_file): Use bfd_section_double_list_remove
to remove sections.
ld/
2005-05-01 H.J. Lu <hongjiu.lu@intel.com>
* emultempl/elf32.em (gld${EMULATION_NAME}_strip_empty_section):
Use bfd_section_double_list_remove to remove sections.
* ldlang.c (lang_insert_orphan): Likewise.
(strip_excluded_or_unused_output_sections): Likewise.
(lang_check_section_addresses): Only check the previous section
for overlap.
--- binutils/bfd/bfd.c.dbl 2005-03-17 20:10:19.000000000 -0800
+++ binutils/bfd/bfd.c 2005-05-01 09:00:10.000000000 -0700
@@ -111,8 +111,8 @@ CODE_FRAGMENT
. {* Pointer to linked list of sections. *}
. struct bfd_section *sections;
.
-. {* The place where we add to the section list. *}
-. struct bfd_section **section_tail;
+. {* The last section on the section list. *}
+. struct bfd_section *section_last;
.
. {* The number of sections. *}
. unsigned int section_count;
@@ -1390,7 +1390,7 @@ CODE_FRAGMENT
. flagword flags;
. const struct bfd_arch_info *arch_info;
. struct bfd_section *sections;
-. struct bfd_section **section_tail;
+. struct bfd_section *section_last;
. unsigned int section_count;
. struct bfd_hash_table section_htab;
.};
@@ -1424,7 +1424,7 @@ bfd_preserve_save (bfd *abfd, struct bfd
preserve->arch_info = abfd->arch_info;
preserve->flags = abfd->flags;
preserve->sections = abfd->sections;
- preserve->section_tail = abfd->section_tail;
+ preserve->section_last = abfd->section_last;
preserve->section_count = abfd->section_count;
preserve->section_htab = abfd->section_htab;
@@ -1435,7 +1435,7 @@ bfd_preserve_save (bfd *abfd, struct bfd
abfd->arch_info = &bfd_default_arch_struct;
abfd->flags &= BFD_IN_MEMORY;
abfd->sections = NULL;
- abfd->section_tail = &abfd->sections;
+ abfd->section_last = NULL;
abfd->section_count = 0;
return TRUE;
@@ -1465,7 +1465,7 @@ bfd_preserve_restore (bfd *abfd, struct
abfd->flags = preserve->flags;
abfd->section_htab = preserve->section_htab;
abfd->sections = preserve->sections;
- abfd->section_tail = preserve->section_tail;
+ abfd->section_last = preserve->section_last;
abfd->section_count = preserve->section_count;
/* bfd_release frees all memory more recently bfd_alloc'd than
--- binutils/bfd/coffcode.h.dbl 2005-04-21 09:57:50.000000000 -0700
+++ binutils/bfd/coffcode.h 2005-05-01 09:00:10.000000000 -0700
@@ -3033,11 +3033,12 @@ coff_compute_section_file_positions (bfd
/* Rethread the linked list into sorted order; at the same time,
assign target_index values. */
target_index = 1;
- abfd->sections = section_list[0];
+ abfd->sections = NULL;
+ abfd->section_last = NULL;
for (i = 0; i < count; i++)
{
current = section_list[i];
- current->next = section_list[i + 1];
+ bfd_section_double_list_append (abfd, current);
/* Later, if the section has zero size, we'll be throwing it
away, so we don't want to number it now. Note that having
@@ -3056,7 +3057,6 @@ coff_compute_section_file_positions (bfd
else
current->target_index = target_index++;
}
- abfd->section_tail = ¤t->next;
free (section_list);
}
--- binutils/bfd/ecoff.c.dbl 2005-03-16 09:21:29.000000000 -0800
+++ binutils/bfd/ecoff.c 2005-05-01 12:12:40.000000000 -0700
@@ -52,8 +52,8 @@
/* This stuff is somewhat copied from coffcode.h. */
static asection bfd_debug_section =
{
- /* name, id, index, next, flags, user_set_vma, */
- "*DEBUG*", 0, 0, NULL, 0, 0,
+ /* name, id, index, next, prev, flags, user_set_vma, */
+ "*DEBUG*", 0, 0, NULL, NULL, 0, 0,
/* linker_mark, linker_has_input, gc_mark, segment_mark, */
0, 0, 0, 0,
/* sec_info_type, use_rela_p, has_tls_reloc, has_gp_reloc, */
--- binutils/bfd/elfxx-ia64.c.dbl 2005-04-28 12:00:14.000000000 -0700
+++ binutils/bfd/elfxx-ia64.c 2005-05-01 12:20:07.000000000 -0700
@@ -4885,7 +4885,6 @@ static bfd_boolean
elfNN_ia64_object_p (bfd *abfd)
{
asection *sec;
- asection **tail;
asection *group, *unwi, *unw;
flagword flags;
const char *name;
@@ -4926,8 +4925,6 @@ elfNN_ia64_object_p (bfd *abfd)
strcpy (stpcpy (unw_name, ".gnu.linkonce.ia64unw."), name);
unw = bfd_get_section_by_name (abfd, unw_name);
- tail = abfd->section_tail;
-
/* We need to create a fake group section for it and its
unwind sections. */
group = bfd_make_section_anyway (abfd, name);
@@ -4936,8 +4933,8 @@ elfNN_ia64_object_p (bfd *abfd)
return FALSE;
/* Move the fake group section to the beginning. */
- BFD_ASSERT (*tail == group);
- bfd_section_list_remove (abfd, tail);
+ BFD_ASSERT (abfd->section_last == group);
+ bfd_section_double_list_remove (abfd, group);
bfd_section_list_insert (abfd, &abfd->sections, group);
elf_next_in_group (group) = sec;
--- binutils/bfd/opncls.c.dbl 2005-03-09 02:51:55.000000000 -0800
+++ binutils/bfd/opncls.c 2005-05-01 09:00:10.000000000 -0700
@@ -77,7 +77,7 @@ _bfd_new_bfd (void)
return NULL;
}
nbfd->sections = NULL;
- nbfd->section_tail = &nbfd->sections;
+ nbfd->section_last = NULL;
nbfd->format = bfd_unknown;
nbfd->my_archive = NULL;
nbfd->origin = 0;
--- binutils/bfd/section.c.dbl 2005-04-12 12:16:43.000000000 -0700
+++ binutils/bfd/section.c 2005-05-01 09:00:10.000000000 -0700
@@ -164,6 +164,9 @@ CODE_FRAGMENT
. {* The next section in the list belonging to the BFD, or NULL. *}
. struct bfd_section *next;
.
+. {* The previous section in the list belonging to the BFD, or NULL. *}
+. struct bfd_section *prev;
+.
. {* The field flags contains attributes of the section. Some
. flags are read in from the object file, and some are
. synthesized from other information. *}
@@ -538,31 +541,87 @@ CODE_FRAGMENT
.{* Macros to handle insertion and deletion of a bfd's sections. These
. only handle the list pointers, ie. do not adjust section_count,
. target_index etc. *}
+.#define bfd_section_double_list_remove(ABFD, S) \
+. do \
+. { \
+. asection *_s = S; \
+. asection *_next = _s->next; \
+. asection *_prev = _s->prev; \
+. if (_prev) \
+. _prev->next = _next; \
+. else \
+. (ABFD)->sections = _next; \
+. if (_next) \
+. { \
+. _next->prev = _prev; \
+. _s->next = NULL; \
+. } \
+. else \
+. (ABFD)->section_last = _prev; \
+. } \
+. while (0)
.#define bfd_section_list_remove(ABFD, PS) \
+. bfd_section_double_list_remove ((ABFD), *(PS))
+.#define bfd_section_double_list_append(ABFD, S) \
+. do \
+. { \
+. asection *_s = S; \
+. bfd *_abfd = ABFD; \
+. _s->next = NULL; \
+. if (_abfd->section_last) \
+. { \
+. _s->prev = _abfd->section_last; \
+. _abfd->section_last->next = _s; \
+. } \
+. else \
+. _abfd->sections = _s; \
+. _abfd->section_last = _s; \
+. } \
+. while (0)
+.#define bfd_section_double_list_insert_after(ABFD, A, S) \
. do \
. { \
-. asection **_ps = PS; \
-. asection *_s = *_ps; \
-. *_ps = _s->next; \
-. if (_s->next == NULL) \
-. (ABFD)->section_tail = _ps; \
+. asection *_a = A; \
+. asection *_s = S; \
+. if (_a) \
+. { \
+. asection *_next = _a->next; \
+. _s->next = _next; \
+. _s->prev = _a; \
+. _a->next = _s; \
+. if (_next) \
+. _s->next->prev = _s; \
+. else \
+. (ABFD)->section_last = _s; \
+. } \
. else \
-. _s->next = NULL; \
+. bfd_section_double_list_append ((ABFD), (S)); \
. } \
. while (0)
-.#define bfd_section_list_insert(ABFD, PS, S) \
+.#define bfd_section_double_list_insert_before(ABFD, B, S) \
. do \
. { \
-. asection **_ps = PS; \
+. asection *_b = B; \
. asection *_s = S; \
-. _s->next = *_ps; \
-. *_ps = _s; \
-. if (_s->next == NULL) \
-. (ABFD)->section_tail = &_s->next; \
+. if (_b) \
+. { \
+. asection *_prev = _b->prev; \
+. _s->prev = _prev; \
+. _s->next = _b; \
+. _b->prev = _s; \
+. if (_prev) \
+. _prev->next = _s; \
+. else \
+. (ABFD)->sections = _s; \
+. } \
+. else \
+. bfd_section_double_list_append ((ABFD), (S)); \
. } \
. while (0)
-.#define bfd_section_removed_from_list(ABFD, S) \
-. ((S)->next == NULL && &(S)->next != (ABFD)->section_tail)
+.#define bfd_section_list_insert(ABFD, PS, S) \
+. bfd_section_double_list_insert_before ((ABFD), *(PS), (S))
+.#define bfd_section_removed_from_list(ABFD, S) \
+. ((S)->next == NULL && (S) != (ABFD)->section_last)
.
*/
@@ -592,8 +651,8 @@ static const asymbol global_syms[] =
#define STD_SECTION(SEC, FLAGS, SYM, NAME, IDX) \
const asymbol * const SYM = (asymbol *) &global_syms[IDX]; \
asection SEC = \
- /* name, id, index, next, flags, user_set_vma, */ \
- { NAME, IDX, 0, NULL, FLAGS, 0, \
+ /* name, id, index, next, prev, flags, user_set_vma, */ \
+ { NAME, IDX, 0, NULL, NULL, FLAGS, 0, \
\
/* linker_mark, linker_has_input, gc_mark, segment_mark, */ \
0, 0, 1, 0, \
@@ -705,8 +764,7 @@ bfd_section_init (bfd *abfd, asection *n
section_id++;
abfd->section_count++;
- *abfd->section_tail = newsect;
- abfd->section_tail = &newsect->next;
+ bfd_section_double_list_append (abfd, newsect);
return newsect;
}
@@ -736,7 +794,7 @@ void
bfd_section_list_clear (bfd *abfd)
{
abfd->sections = NULL;
- abfd->section_tail = &abfd->sections;
+ abfd->section_last = NULL;
abfd->section_count = 0;
memset (abfd->section_htab.table, 0,
abfd->section_htab.size * sizeof (struct bfd_hash_entry *));
--- binutils/bfd/xcofflink.c.dbl 2005-04-11 09:10:29.000000000 -0700
+++ binutils/bfd/xcofflink.c 2005-05-01 12:10:08.000000000 -0700
@@ -5454,19 +5454,17 @@ _bfd_xcoff_bfd_final_link (bfd *abfd, st
saw_contents = TRUE;
else
{
- asection *n, **st;
+ asection *n;
/* Create a pad section and place it before the section
that needs padding. This requires unlinking and
relinking the bfd's section list. */
- st = abfd->section_tail;
n = bfd_make_section_anyway (abfd, ".pad");
n->flags = SEC_HAS_CONTENTS;
n->alignment_power = 0;
- BFD_ASSERT (*st == n);
- bfd_section_list_remove (abfd, st);
+ bfd_section_double_list_remove (abfd, n);
bfd_section_list_insert (abfd, op, n);
op = &n->next;
--- binutils/gas/write.c.dbl 2005-04-27 08:28:38.000000000 -0700
+++ binutils/gas/write.c 2005-05-01 08:09:56.000000000 -0700
@@ -1471,20 +1471,11 @@ write_object_file (void)
#ifdef BFD_ASSEMBLER
/* Remove the sections created by gas for its own purposes. */
{
- asection **seclist;
int i;
- seclist = &stdoutput->sections;
- while (*seclist)
- {
- if (*seclist == reg_section || *seclist == expr_section)
- {
- bfd_section_list_remove (stdoutput, seclist);
- stdoutput->section_count--;
- }
- else
- seclist = &(*seclist)->next;
- }
+ bfd_section_double_list_remove (stdoutput, reg_section);
+ bfd_section_double_list_remove (stdoutput, expr_section);
+ stdoutput->section_count -= 2;
i = 0;
bfd_map_over_sections (stdoutput, renumber_sections, &i);
}
--- binutils/ld/emultempl/elf32.em.dbl 2005-04-30 15:00:46.000000000 -0700
+++ binutils/ld/emultempl/elf32.em 2005-05-01 08:09:56.000000000 -0700
@@ -1548,17 +1548,13 @@ gld${EMULATION_NAME}_strip_empty_section
if (os == abs_output_section || os->constraint == -1)
continue;
s = os->bfd_section;
- if (s != NULL && s->size == 0 && (s->flags & SEC_KEEP) == 0)
+ if (s != NULL
+ && s->size == 0
+ && (s->flags & SEC_KEEP) == 0
+ && !bfd_section_removed_from_list (output_bfd, s))
{
- asection **p;
-
- for (p = &output_bfd->sections; *p; p = &(*p)->next)
- if (*p == s)
- {
- bfd_section_list_remove (output_bfd, p);
- output_bfd->section_count--;
- break;
- }
+ bfd_section_double_list_remove (output_bfd, s);
+ output_bfd->section_count--;
}
}
}
--- binutils/ld/ldlang.c.dbl 2005-04-30 15:19:33.000000000 -0700
+++ binutils/ld/ldlang.c 2005-05-01 08:58:21.000000000 -0700
@@ -1203,7 +1203,6 @@ lang_insert_orphan (lang_input_statement
etree_type *load_base;
lang_output_section_statement_type *os;
lang_output_section_statement_type **os_tail;
- asection **bfd_tail;
/* Start building a list of statements for this section.
First save the current statement pointer. */
@@ -1257,7 +1256,6 @@ lang_insert_orphan (lang_input_statement
os_tail = ((lang_output_section_statement_type **)
lang_output_section_statement.tail);
- bfd_tail = output_bfd->section_tail;
os = lang_enter_output_section_statement (secname, address, 0, NULL, NULL,
load_base, 0);
@@ -1316,8 +1314,8 @@ lang_insert_orphan (lang_input_statement
place->section = &output_bfd->sections;
/* Unlink the section. */
- ASSERT (*bfd_tail == snew);
- bfd_section_list_remove (output_bfd, bfd_tail);
+ ASSERT (output_bfd->section_last == snew);
+ bfd_section_double_list_remove (output_bfd, snew);
/* Now tack it back on in the right place. */
bfd_section_list_insert (output_bfd, place->section, snew);
@@ -3051,8 +3049,6 @@ strip_excluded_or_unused_output_sections
&& s->linker_has_input == 0
&& (s->flags & (SEC_KEEP | SEC_HAS_CONTENTS)) == 0)))
{
- asection **p;
-
/* We don't set bfd_section to NULL since bfd_section of
the used output section may still be used. */
if (unused)
@@ -3060,13 +3056,11 @@ strip_excluded_or_unused_output_sections
else
os->bfd_section = NULL;
- for (p = &output_bfd->sections; *p; p = &(*p)->next)
- if (*p == s)
- {
- bfd_section_list_remove (output_bfd, p);
- output_bfd->section_count--;
- break;
- }
+ if (!bfd_section_removed_from_list (output_bfd, s))
+ {
+ bfd_section_double_list_remove (output_bfd, s);
+ output_bfd->section_count--;
+ }
}
}
}
@@ -3722,7 +3716,7 @@ lang_check_section_addresses (void)
/* Once we reach section 's' stop our seach. This prevents two
warning messages from being produced, one for 'section A overlaps
section B' and one for 'section B overlaps section A'. */
- for (os = output_bfd->sections; os != s; os = os->next)
+ for (os = s->prev; os != NULL; os = os->prev)
{
bfd_vma s_start;
bfd_vma s_end;
@@ -3742,15 +3736,14 @@ lang_check_section_addresses (void)
os_end = os_start + TO_ADDR (os->size) - 1;
/* Look for an overlap. */
- if ((s_end < os_start) || (s_start > os_end))
- continue;
-
- einfo (
-_("%X%P: section %s [%V -> %V] overlaps section %s [%V -> %V]\n"),
- s->name, s_start, s_end, os->name, os_start, os_end);
-
- /* Once we have found one overlap for this section,
- stop looking for others. */
+ if (s_end >= os_start && s_start <= os_end)
+
+ einfo (_("%X%P: section %s [%V -> %V] overlaps section %s [%V -> %V]\n"),
+ s->name, s_start, s_end, os->name, os_start, os_end);
+
+ /* We only need to check the previous section for overlap.
+ Once we have found one overlap for this section, stop
+ looking for others. */
break;
}
}