From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 15369 invoked by alias); 23 Jun 2006 23:11:02 -0000 Received: (qmail 15223 invoked by uid 22791); 23 Jun 2006 23:11:01 -0000 X-Spam-Check-By: sourceware.org Received: from outbound-cpk.frontbridge.com (HELO outbound2-cpk-R.bigfish.com) (207.46.163.16) by sourceware.org (qpsmtpd/0.31) with ESMTP; Fri, 23 Jun 2006 23:10:58 +0000 Received: from outbound2-cpk.bigfish.com (localhost.localdomain [127.0.0.1]) by outbound2-cpk-R.bigfish.com (Postfix) with ESMTP id 0EC7CA7FC41; Fri, 23 Jun 2006 23:10:57 +0000 (UTC) Received: from mail60-cpk-R.bigfish.com (unknown [192.168.21.3]) (using TLSv1 with cipher EDH-RSA-DES-CBC3-SHA (168/168 bits)) (No client certificate requested) by outbound2-cpk.bigfish.com (Postfix) with ESMTP id 04F6CA7A3FF; Fri, 23 Jun 2006 23:10:57 +0000 (UTC) Received: from mail60-cpk.bigfish.com (localhost.localdomain [127.0.0.1]) by mail60-cpk-R.bigfish.com (Postfix) with ESMTP id B323C41F41C; Fri, 23 Jun 2006 23:10:56 +0000 (UTC) X-BigFish: VP Received: by mail60-cpk (MessageSwitch) id 1151104256651447_600; Fri, 23 Jun 2006 23:10:56 +0000 (UCT) Received: from newsgate.xilinx.com (newsgate.xilinx.com [149.199.60.204]) by mail60-cpk.bigfish.com (Postfix) with ESMTP id 7B87841F330; Fri, 23 Jun 2006 23:10:56 +0000 (UTC) Received: from cliff.xilinx.com (cliff [149.199.38.103]) by newsgate.xilinx.com (8.11.6p2/8.11.6) with ESMTP id k5NNAtl20072; Fri, 23 Jun 2006 16:10:55 -0700 (PDT) Received: from xsj-exchfesmtp1.xlnx.xilinx.com (localhost [127.0.0.1]) by cliff.xilinx.com (8.12.9/8.11.6) with ESMTP id k5NNAtdx029193; Fri, 23 Jun 2006 16:10:55 -0700 (PDT) Received: from xsj-exchfeca2.xlnx.xilinx.com ([172.19.80.2]) by xsj-exchfesmtp1.xlnx.xilinx.com with Microsoft SMTPSVC(6.0.3790.2499); Fri, 23 Jun 2006 16:10:54 -0700 Received: from [172.19.1.0] ([172.19.1.0]) by xsj-exchfeca2.xlnx.xilinx.com with Microsoft SMTPSVC(6.0.3790.2499); Fri, 23 Jun 2006 16:10:54 -0700 Message-ID: <449C74FD.9030806@xilinx.com> Date: Sat, 24 Jun 2006 09:58:00 -0000 From: Sonal Santan User-Agent: Thunderbird 1.5.0.4 (X11/20060614) MIME-Version: 1.0 To: Nick Clifton CC: binutils@sourceware.org Subject: Re: [PATCH] Speed up ld by about 5 times on Windows. References: <449092C1.1050603@xilinx.com> <449708C4.7060309@xilinx.com> <4497204C.3B3DA34C@dessent.net> <4499BED0.1070401@xilinx.com> <449AB99E.4000305@redhat.com> In-Reply-To: <449AB99E.4000305@redhat.com> Content-Type: multipart/mixed; boundary="------------030002050105000800020803" X-IsSubscribed: yes Mailing-List: contact binutils-help@sourceware.org; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: binutils-owner@sourceware.org X-SW-Source: 2006-06/txt/msg00372.txt.bz2 This is a multi-part message in MIME format. --------------030002050105000800020803 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-length: 1300 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 > --------------030002050105000800020803 Content-Type: text/x-patch; name="ldlang.c.diff" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="ldlang.c.diff" Content-length: 5257 *** 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) --------------030002050105000800020803--