This is the mail archive of the
binutils@sourceware.org
mailing list for the binutils project.
Re: [PATCH] Speed up ld by about 5 times on Windows.
Hello Nick,
Thanks for trying my patch. I have fixed the regressions seen for ELF
based toolchains. An updated patch is attached with this mail.
Thanks,
Sonal
Nick Clifton wrote:
Hi Sonal,
I have attached an updated patch for ldlang.c (against revision
1.226). I have tried to follow GNU coding standards in my changes.
Please review my changes.
Thanks for submitting this patch. I am looking at it now, but I have
encountered a problem. It appears that the patch breaks a couple of
tests in the linker testsuite, at least for ELF based toolchains:
Running
/work/sources/binutils/current/ld/testsuite/ld-scripts/sort.exp ...
FAIL: SORT_BY_NAME(SORT_BY_NAME())
FAIL: SORT_BY_NAME(SORT_BY_NAME()) --sort-section name
These tests are not run for PE based toolchains, including the mingw32
toolchain, which may be why you did not encounter it in your own testing.
The tests are expecting the input sections to be sorted into this order:
texta
textb
text1a
text1b
text2a
text2b
text3a
text3b
But instead the (patched) linker is sorting them into this order:
texta
text1a
text2a
text3a
textb
text1b
text2b
text3b
Perhaps you could look into this ?
Cheers
Nick
*** ldlang.1.226.c 2006-06-21 13:28:36.000000000 -0700
--- ldlang.c 2006-06-23 15:37:23.000000000 -0700
***************
*** 45,50 ****
--- 45,59 ----
#define offsetof(TYPE, MEMBER) ((size_t) & (((TYPE*) 0)->MEMBER))
#endif
+ /* Binary search tree structure to efficiently sort
+ sections by name */
+ typedef struct lang_section_bst
+ {
+ asection *section;
+ struct lang_section_bst *left;
+ struct lang_section_bst *right;
+ } lang_section_bst_type;
+
/* Locals variables. */
static struct obstack stat_obstack;
static struct obstack map_obstack;
*************** static void print_input_section (asectio
*** 83,88 ****
--- 92,105 ----
static bfd_boolean lang_one_common (struct bfd_link_hash_entry *, void *);
static void lang_record_phdrs (void);
static void lang_do_version_exports_section (void);
+ static void
+ output_section_callback (lang_wild_statement_type *ptr,
+ struct wildcard_list *sec,
+ asection *section,
+ lang_input_statement_type *file,
+ void *output);
+ static int
+ compare_section (sort_type sort, asection *asec, asection *bsec);
/* Exported variables. */
lang_output_section_statement_type *abs_output_section;
*************** match_simple_wild (const char *pattern,
*** 316,321 ****
--- 333,405 ----
return TRUE;
}
+ /* Build a Binary Search Tree to sort sections, unlike insertion sort
+ used in wild_sort(). BST is considerably faster if the number of
+ of sections are large. */
+
+ static lang_section_bst_type **
+ wild_sort_fast (lang_wild_statement_type *wild,
+ struct wildcard_list *sec,
+ lang_input_statement_type *file ATTRIBUTE_UNUSED,
+ asection *section)
+ {
+ lang_section_bst_type **tree
+ = (lang_section_bst_type **) (&(wild->handler_data[1]));
+ if (!wild->filenames_sorted
+ && (sec == NULL || sec->spec.sorted == none))
+ {
+ /* Append at the right end of tree */
+ while (*tree)
+ tree = &((*tree)->right);
+ return tree;
+ }
+ while (*tree)
+ {
+ /* Find the correct node to append this section */
+ if (compare_section (sec->spec.sorted, section, (*tree)->section) < 0)
+ tree = &((*tree)->left);
+ else
+ tree = &((*tree)->right);
+ }
+ return tree;
+ }
+
+ /* Use wild_sort_fast to build a BST to sort sections. */
+
+ static void
+ output_section_callback_fast (lang_wild_statement_type *ptr,
+ struct wildcard_list *sec,
+ asection *section,
+ lang_input_statement_type *file,
+ void *output ATTRIBUTE_UNUSED)
+ {
+ if (unique_section_p (section))
+ return;
+
+ lang_section_bst_type *node = xmalloc (sizeof (lang_section_bst_type));
+ node->left = 0;
+ node->right = 0;
+ node->section = section;
+ lang_section_bst_type **tree = wild_sort_fast (ptr, sec, file, section);
+ *tree = node;
+ }
+
+ /* Convert a sorted sections' BST back to list form */
+
+ static void
+ output_section_callback_tree_to_list (lang_wild_statement_type *ptr,
+ lang_section_bst_type *tree,
+ void *output)
+ {
+ if (tree->left)
+ output_section_callback_tree_to_list (ptr, tree->left, output);
+ lang_add_section (&ptr->children, tree->section,
+ (lang_output_section_statement_type *) output);
+ if (tree->right)
+ output_section_callback_tree_to_list (ptr, tree->right, output);
+ free (tree);
+ }
+
/* Specialized, optimized routines for handling different kinds of
wildcards */
*************** analyze_walk_wild_section_handler (lang_
*** 608,613 ****
--- 692,701 ----
given order, because we've already determined that no section
will match more than one spec. */
data_counter = 0;
+ ptr->handler_data[0] = NULL;
+ ptr->handler_data[1] = NULL;
+ ptr->handler_data[2] = NULL;
+ ptr->handler_data[3] = NULL;
for (sec = ptr->section_list; sec != NULL; sec = sec->next)
if (!wildcardp (sec->spec.name))
ptr->handler_data[data_counter++] = sec;
*************** wild (lang_wild_statement_type *s,
*** 2461,2467 ****
{
struct wildcard_list *sec;
! walk_wild (s, output_section_callback, output);
if (default_common_section == NULL)
for (sec = s->section_list; sec != NULL; sec = sec->next)
--- 2549,2566 ----
{
struct wildcard_list *sec;
! if (s->handler_data[0] && (s->handler_data[0]->spec.sorted == by_name)
! && !s->filenames_sorted)
! {
! walk_wild (s, output_section_callback_fast, output);
! if (s->handler_data[1])
! output_section_callback_tree_to_list (s,
! (lang_section_bst_type *) s->handler_data[1],
! output);
! s->handler_data[1] = NULL;
! }
! else
! walk_wild (s, output_section_callback, output);
if (default_common_section == NULL)
for (sec = s->section_list; sec != NULL; sec = sec->next)