Re: patch / RFD: speed up linker map file generation

[Joern Rennecke <joern dot rennecke at superh dot com>]

> There should definitely be an option.  There are users who run these 
> tools on small machines who will want the old behaviour.  I would 
> suggest making it a generalised switch  (eg --reduce-memory-overheads) 
> that can be used to trigger other (as yet unimplemented) tweaks to the 
> linker's behaviour.

I have merged my patch into the mainline from Sunday and implemented your
suggestions.

2004-05-18  J"orn Rennecke <joern.rennecke@superh.com>

	* ld.h (map_symbol_def): New struct.
	(struct user_section_struct): New members map_symbol_def_head
	and map_symbol_def_tail.
	(args_type): New member reduce_memory_overheads.
	* ldlang.c (map_obstack): New static variable.
	(init_map_userdata, print_all_symbols, sort_def_symbol): New functions.
	(lang_map): Unless command_line.reduce_memory_overheads is set,
	initialize lists of defined symbols for each section.
	(print_input_section): Unless command_line.reduce_memory_overheads
	is set, use print_all_symbols.
	* ldmain.c (main): Initialize command_line.reduce_memory_overheads.
	* lexsup.c (enum option_values): Add OPTION_REDUCE_MEMORY_OVERHEADS.
	(ld_options): Add entry for --reduce-memory-overheads.
	(parse_args): Handle OPTION_REDUCE_MEMORY_OVERHEADS.

Index: ld.h
===================================================================
RCS file: /cvs/src/src/ld/ld.h,v
retrieving revision 1.21
diff -p -r1.21 ld.h
*** ld.h	28 Jun 2003 05:28:54 -0000	1.21
--- ld.h	18 May 2004 15:02:27 -0000
*************** struct wildcard_list {
*** 78,87 ****
    struct wildcard_spec spec;
  };
  
  /* Extra information we hold on sections */
  typedef struct user_section_struct {
!   /* Pointer to the section where this data will go */
    struct lang_input_statement_struct *file;
  } section_userdata_type;
  
  #define get_userdata(x) ((x)->userdata)
--- 78,96 ----
    struct wildcard_spec spec;
  };
  
+ struct map_symbol_def {
+   struct bfd_link_hash_entry *entry;
+   struct map_symbol_def *next;
+ };
+ 
  /* Extra information we hold on sections */
  typedef struct user_section_struct {
!   /* For output sections: pointer to the section where this data will go.  */
    struct lang_input_statement_struct *file;
+   /* For input sections, when writing a map file: head / tail of a linked
+      list of hash table entries for symbols defined in this section.  */
+   struct map_symbol_def *map_symbol_def_head;
+   struct map_symbol_def **map_symbol_def_tail;
  } section_userdata_type;
  
  #define get_userdata(x) ((x)->userdata)
*************** typedef struct {
*** 153,158 ****
--- 162,171 ----
       behaviour of the linker.  The new default behaviour is to reject such
       input files.  */
    bfd_boolean accept_unknown_input_arch;
+ 
+   /* If TRUE reduce memory overheads, at the expense of speed.
+      This will cause map file generation to use an O(N^2) algorithm.  */
+   bfd_boolean reduce_memory_overheads;
  
  } args_type;
  
Index: ldlang.c
===================================================================
RCS file: /cvs/src/src/ld/ldlang.c,v
retrieving revision 1.145
diff -p -r1.145 ldlang.c
*** ldlang.c	11 May 2004 17:08:34 -0000	1.145
--- ldlang.c	18 May 2004 15:02:27 -0000
***************
*** 47,52 ****
--- 47,53 ----
  
  /* Locals variables.  */
  static struct obstack stat_obstack;
+ static struct obstack map_obstack;
  
  #define obstack_chunk_alloc xmalloc
  #define obstack_chunk_free free
*************** static struct bfd_hash_table lang_define
*** 65,70 ****
--- 66,72 ----
  
  /* Forward declarations.  */
  static void exp_init_os (etree_type *);
+ static void init_map_userdata (bfd *, asection *, void *);
  static bfd_boolean wildcardp (const char *);
  static lang_input_statement_type *lookup_name (const char *);
  static bfd_boolean load_symbols (lang_input_statement_type *,
*************** static bfd_boolean load_symbols (lang_in
*** 72,77 ****
--- 74,81 ----
  static struct bfd_hash_entry *lang_definedness_newfunc
   (struct bfd_hash_entry *, struct bfd_hash_table *, const char *);
  static void insert_undefined (const char *);
+ static void print_all_symbols (asection *);
+ static bfd_boolean sort_def_symbol (struct bfd_link_hash_entry *, void *);
  static void print_statement (lang_statement_union_type *,
  			     lang_output_section_statement_type *);
  static void print_statement_list (lang_statement_union_type *,
*************** void
*** 673,678 ****
--- 677,683 ----
  lang_map (void)
  {
    lang_memory_region_type *m;
+   bfd *p;
  
    minfo (_("\nMemory Configuration\n\n"));
    fprintf (config.map_file, "%-16s %-18s %-18s %s\n",
*************** lang_map (void)
*** 718,726 ****
--- 723,781 ----
  
    fprintf (config.map_file, _("\nLinker script and memory map\n\n"));
  
+   if (! command_line.reduce_memory_overheads)
+     {
+       obstack_begin (&map_obstack, 1000);
+       for (p = link_info.input_bfds; p != (bfd *) NULL; p = p->link_next)
+ 	bfd_map_over_sections (p, init_map_userdata, 0);
+       bfd_link_hash_traverse (link_info.hash, sort_def_symbol, 0);
+     }
    print_statements ();
  }
  
+ static void
+ init_map_userdata (abfd, sec, data)
+      bfd *abfd ATTRIBUTE_UNUSED;
+      asection *sec;
+      void *data ATTRIBUTE_UNUSED;
+ {
+   section_userdata_type *new_data
+     = ((section_userdata_type *) stat_alloc (sizeof (section_userdata_type)));
+ 
+   ASSERT (get_userdata (sec) == NULL);
+   get_userdata (sec) = new_data;
+   new_data->map_symbol_def_tail = &new_data->map_symbol_def_head;
+ }
+ 
+ static bfd_boolean
+ sort_def_symbol (hash_entry, info)
+      struct bfd_link_hash_entry *hash_entry;
+      void *info ATTRIBUTE_UNUSED;
+ {
+   if (hash_entry->type == bfd_link_hash_defined
+       || hash_entry->type == bfd_link_hash_defweak)
+     {
+       struct user_section_struct *ud;
+       struct map_symbol_def *def;
+ 
+       ud = get_userdata (hash_entry->u.def.section);
+       if  (! ud)
+ 	{
+ 	  /* ??? What do we have to do to initialize this beforehand?  */
+ 	  /* The first time we get here is bfd_abs_section...  */
+ 	  init_map_userdata (0, hash_entry->u.def.section, 0);
+ 	  ud = get_userdata (hash_entry->u.def.section);
+ 	}
+       else if  (!ud->map_symbol_def_tail)
+ 	ud->map_symbol_def_tail = &ud->map_symbol_def_head;
+       def = (struct map_symbol_def *) obstack_alloc (&map_obstack, sizeof *def);
+       def->entry = hash_entry;
+       *ud->map_symbol_def_tail = def;
+       ud->map_symbol_def_tail = &def->next;
+     }
+   return TRUE;
+ }
+ 
  /* Initialize an output section.  */
  
  static void
*************** print_input_statement (lang_input_statem
*** 2275,2281 ****
  }
  
  /* Print all symbols defined in a particular section.  This is called
!    via bfd_link_hash_traverse.  */
  
  static bfd_boolean
  print_one_symbol (struct bfd_link_hash_entry *hash_entry, void *ptr)
--- 2330,2336 ----
  }
  
  /* Print all symbols defined in a particular section.  This is called
!    via bfd_link_hash_traverse, or by print_all_symbols.  */
  
  static bfd_boolean
  print_one_symbol (struct bfd_link_hash_entry *hash_entry, void *ptr)
*************** print_one_symbol (struct bfd_link_hash_e
*** 2301,2306 ****
--- 2356,2373 ----
    return TRUE;
  }
  
+ static void
+ print_all_symbols (sec)
+      asection *sec;
+ {
+   struct user_section_struct *ud = get_userdata (sec);
+   struct map_symbol_def *def;
+ 
+   *ud->map_symbol_def_tail = 0;
+   for (def = ud->map_symbol_def_head; def; def = def->next)
+     print_one_symbol (def->entry, sec);
+ }
+ 
  /* Print information about an input section to the map file.  */
  
  static void
*************** print_input_section (lang_input_section_
*** 2353,2359 ****
  	      minfo (_("%W (size before relaxing)\n"), i->_raw_size);
  	    }
  
! 	  bfd_link_hash_traverse (link_info.hash, print_one_symbol, i);
  
  	  print_dot = (i->output_section->vma + i->output_offset
  		       + TO_ADDR (size));
--- 2420,2429 ----
  	      minfo (_("%W (size before relaxing)\n"), i->_raw_size);
  	    }
  
! 	  if (command_line.reduce_memory_overheads)
! 	    bfd_link_hash_traverse (link_info.hash, print_one_symbol, i);
! 	  else
! 	    print_all_symbols (i);
  
  	  print_dot = (i->output_section->vma + i->output_offset
  		       + TO_ADDR (size));
Index: ldmain.c
===================================================================
RCS file: /cvs/src/src/ld/ldmain.c,v
retrieving revision 1.80
diff -p -r1.80 ldmain.c
*** ldmain.c	11 May 2004 17:08:34 -0000	1.80
--- ldmain.c	18 May 2004 15:02:27 -0000
*************** main (int argc, char **argv)
*** 274,279 ****
--- 274,280 ----
    command_line.warn_mismatch = TRUE;
    command_line.check_section_addresses = TRUE;
    command_line.accept_unknown_input_arch = FALSE;
+   command_line.reduce_memory_overheads = FALSE;
  
    /* We initialize DEMANGLING based on the environment variable
       COLLECT_NO_DEMANGLE.  The gcc collect2 program will demangle the
Index: lexsup.c
===================================================================
RCS file: /cvs/src/src/ld/lexsup.c,v
retrieving revision 1.72
diff -p -r1.72 lexsup.c
*** lexsup.c	20 Mar 2004 23:16:43 -0000	1.72
--- lexsup.c	18 May 2004 15:02:28 -0000
*************** enum option_values
*** 142,148 ****
    OPTION_PIE,
    OPTION_UNRESOLVED_SYMBOLS,
    OPTION_WARN_UNRESOLVED_SYMBOLS,
!   OPTION_ERROR_UNRESOLVED_SYMBOLS
  };
  
  /* The long options.  This structure is used for both the option
--- 142,149 ----
    OPTION_PIE,
    OPTION_UNRESOLVED_SYMBOLS,
    OPTION_WARN_UNRESOLVED_SYMBOLS,
!   OPTION_ERROR_UNRESOLVED_SYMBOLS,
!   OPTION_REDUCE_MEMORY_OVERHEADS
  };
  
  /* The long options.  This structure is used for both the option
*************** static const struct ld_option ld_options
*** 445,451 ****
    { {"no-as-needed", no_argument, NULL, OPTION_NO_AS_NEEDED},
        '\0', NULL, N_("Always set DT_NEEDED for following dynamic libs"), TWO_DASHES },
    { {"wrap", required_argument, NULL, OPTION_WRAP},
!       '\0', N_("SYMBOL"), N_("Use wrapper functions for SYMBOL"), TWO_DASHES }
  };
  
  #define OPTION_COUNT ARRAY_SIZE (ld_options)
--- 446,454 ----
    { {"no-as-needed", no_argument, NULL, OPTION_NO_AS_NEEDED},
        '\0', NULL, N_("Always set DT_NEEDED for following dynamic libs"), TWO_DASHES },
    { {"wrap", required_argument, NULL, OPTION_WRAP},
!       '\0', N_("SYMBOL"), N_("Use wrapper functions for SYMBOL"), TWO_DASHES },
!   { {"reduce-memory-overheads", no_argument, NULL, OPTION_REDUCE_MEMORY_OVERHEADS},
!       '\0', NULL, N_("reduce memory overheads, possibly taking much longer"), TWO_DASHES },
  };
  
  #define OPTION_COUNT ARRAY_SIZE (ld_options)
*************** parse_args (unsigned argc, char **argv)
*** 1220,1225 ****
--- 1223,1231 ----
  
  	case OPTION_FINI:
  	  link_info.fini_function = optarg;
+ 	  break;
+ 	case OPTION_REDUCE_MEMORY_OVERHEADS:
+ 	  command_line.reduce_memory_overheads = TRUE;
  	  break;
  	}
      }