From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 12088 invoked by alias); 1 May 2005 19:48:08 -0000 Mailing-List: contact binutils-help@sources.redhat.com; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: binutils-owner@sources.redhat.com Received: (qmail 12036 invoked from network); 1 May 2005 19:47:59 -0000 Received: from unknown (HELO sccrmhc14.comcast.net) (204.127.202.59) by sourceware.org with SMTP; 1 May 2005 19:47:59 -0000 Received: from lucon.org ([24.6.212.230]) by comcast.net (sccrmhc14) with ESMTP id <20050501194758014009of1me>; Sun, 1 May 2005 19:47:58 +0000 Received: by lucon.org (Postfix, from userid 1000) id 0532E97E57; Sun, 1 May 2005 12:47:57 -0700 (PDT) Date: Sun, 01 May 2005 19:48:00 -0000 From: "H. J. Lu" To: binutils@sources.redhat.com Subject: Re: PATCH: Use a double section list to speed up linker by 30% Message-ID: <20050501194757.GA16309@lucon.org> References: <20050501165707.GA13713@lucon.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20050501165707.GA13713@lucon.org> User-Agent: Mutt/1.4.1i X-SW-Source: 2005-05/txt/msg00007.txt.bz2 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 * 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 * write.c (write_object_file): Use bfd_section_double_list_remove to remove sections. ld/ 2005-05-01 H.J. Lu * 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; } }