Speed up direct linking with DLLs on Windows (2/2).

This patch deals with the generation of the import library on the fly.

The implementation is inefficient because the linker makes a lot of
calls to realloc and memmove when importing the symbols in order to
maintain a sorted list of symbols.

This is fixable by relying on the fact that, for every linked DLL,
the list of symbols it exports is already sorted so you can import
them en masse once you have found the insertion point.

ld/
	* deffile.h (def_file_add_import_from): Declare.
	(def_file_add_import_at): Likewise.
	* deffilep.y (fill_in_import): New function extracted from...
	(def_file_add_import): ...here.  Call it.
	(def_file_add_import_from): New function.
	(def_file_add_import_at): Likewise.
	* pe-dll.c (pe_implied_import_dll): Use an optimized version of the
	insertion loop for imported symbols if possible.

4 files changed, 144 insertions, 12 deletions

diff --git a/ld/ChangeLog b/ld/ChangeLog
index b1a1dda..c6f85ff 100644
--- a/ld/ChangeLog
+++ b/ld/ChangeLog
@@ -1,5 +1,16 @@
 2018-04-04  Eric Botcazou  <ebotcazou@adacore.com>
 
+	* deffile.h (def_file_add_import_from): Declare.
+	(def_file_add_import_at): Likewise.
+	* deffilep.y (fill_in_import): New function extracted from...
+	(def_file_add_import): ...here.  Call it.
+	(def_file_add_import_from): New function.
+	(def_file_add_import_at): Likewise.
+	* pe-dll.c (pe_implied_import_dll): Use an optimized version of the
+	insertion loop for imported symbols if possible.
+
+2018-04-04  Eric Botcazou  <ebotcazou@adacore.com>
+
 	* emultempl/pe.em (U_SIZE): Delete.
 	(pe_data_import_dll): Likewise.
 	(make_import_fixup): Return void, take 4th parameter and pass it down
diff --git a/ld/deffile.h b/ld/deffile.h
index 9a1e539..4275e71 100644
--- a/ld/deffile.h
+++ b/ld/deffile.h
@@ -108,6 +108,16 @@ extern def_file_export *def_file_add_export (def_file *, const char *,
 extern def_file_import *def_file_add_import (def_file *, const char *,
 					     const char *, int, const char *,
 					     const char *, int *);
+extern int def_file_add_import_from (def_file *fdef,
+				     int num_imports,
+				     const char *name,
+				     const char *module,
+				     int ordinal,
+				     const char *internal_name,
+				     const char *its_name);
+extern def_file_import *def_file_add_import_at (def_file *, int, const char *,
+						const char *, int, const char *,
+					        const char *);
 extern void def_file_add_directive (def_file *, const char *, int);
 extern def_file_module *def_get_module (def_file *, const char *);
 #ifdef DEF_FILE_PRINT
diff --git a/ld/deffilep.y b/ld/deffilep.y
index 1931c00..1aebdf6 100644
--- a/ld/deffilep.y
+++ b/ld/deffilep.y
@@ -816,6 +816,26 @@ find_import_in_list (def_file_import *b, int max,
   return l;
 }
 
+static void
+fill_in_import (def_file_import *i,
+		const char *name,
+		def_file_module *module,
+		int ordinal,
+		const char *internal_name,
+		const char *its_name)
+{
+  memset (i, 0, sizeof (def_file_import));
+  if (name)
+    i->name = xstrdup (name);
+  i->module = module;
+  i->ordinal = ordinal;
+  if (internal_name)
+    i->internal_name = xstrdup (internal_name);
+  else
+    i->internal_name = i->name;
+  i->its_name = (its_name ? xstrdup (its_name) : NULL);
+}
+
 def_file_import *
 def_file_add_import (def_file *fdef,
 		     const char *name,
@@ -850,18 +870,74 @@ def_file_add_import (def_file *fdef,
     }
   i = fdef->imports + pos;
   if (pos != fdef->num_imports)
-    memmove (&i[1], i, (sizeof (def_file_import) * (fdef->num_imports - pos)));
-  memset (i, 0, sizeof (def_file_import));
-  if (name)
-    i->name = xstrdup (name);
-  if (module)
-    i->module = def_stash_module (fdef, module);
-  i->ordinal = ordinal;
-  if (internal_name)
-    i->internal_name = xstrdup (internal_name);
-  else
-    i->internal_name = i->name;
-  i->its_name = (its_name ? xstrdup (its_name) : NULL);
+    memmove (i + 1, i, sizeof (def_file_import) * (fdef->num_imports - pos));
+
+  fill_in_import (i, name, def_stash_module (fdef, module), ordinal,
+		  internal_name, its_name);
+  fdef->num_imports++;
+
+  return i;
+}
+
+int
+def_file_add_import_from (def_file *fdef,
+			  int num_imports,
+			  const char *name,
+			  const char *module,
+			  int ordinal,
+			  const char *internal_name,
+			  const char *its_name ATTRIBUTE_UNUSED)
+{
+  def_file_import *i;
+  int is_dup;
+  int pos;
+  int max_imports = ROUND_UP (fdef->num_imports, 16);
+
+  /* We need to avoid here duplicates.  */
+  is_dup = 0;
+  pos = find_import_in_list (fdef->imports, fdef->num_imports,
+			     name, internal_name ? internal_name : name,
+			     module, ordinal, &is_dup);
+  if (is_dup != 0)
+    return -1;
+  if (fdef->imports && pos != fdef->num_imports)
+    {
+      i = fdef->imports + pos;
+      if (i->module && strcmp (i->module->name, module) == 0)
+	return -1;
+    }
+
+  if (fdef->num_imports + num_imports - 1 >= max_imports)
+    {
+      max_imports = ROUND_UP (fdef->num_imports + num_imports, 16);
+
+      if (fdef->imports)
+	fdef->imports = xrealloc (fdef->imports,
+				 max_imports * sizeof (def_file_import));
+      else
+	fdef->imports = xmalloc (max_imports * sizeof (def_file_import));
+    }
+  i = fdef->imports + pos;
+  if (pos != fdef->num_imports)
+    memmove (i + num_imports, i,
+	     sizeof (def_file_import) * (fdef->num_imports - pos));
+
+  return pos;
+}
+
+def_file_import *
+def_file_add_import_at (def_file *fdef,
+			int pos,
+			const char *name,
+			const char *module,
+			int ordinal,
+			const char *internal_name,
+			const char *its_name)
+{
+  def_file_import *i = fdef->imports + pos;
+
+  fill_in_import (i, name, def_stash_module (fdef, module), ordinal,
+		  internal_name, its_name);
   fdef->num_imports++;
 
   return i;
diff --git a/ld/pe-dll.c b/ld/pe-dll.c
index ad0ffcf..efb75f2 100644
--- a/ld/pe-dll.c
+++ b/ld/pe-dll.c
@@ -3317,6 +3317,7 @@ pe_implied_import_dll (const char *filename)
   bfd_vma rdata_end = 0;
   bfd_vma bss_start = 1;
   bfd_vma bss_end = 0;
+  int from;
 
   /* No, I can't use bfd here.  kernel32.dll puts its export table in
      the middle of the .rdata section.  */
@@ -3457,6 +3458,40 @@ pe_implied_import_dll (const char *filename)
       return TRUE;
     }
 
+  /* This is an optimized version of the insertion loop, which avoids lots of
+     calls to realloc and memmove from def_file_add_import.  */
+  if ((from = def_file_add_import_from (pe_def_file, nexp,
+					erva + pe_as32 (erva + name_rvas),
+					dllname, 0, NULL, NULL)) >= 0)
+    {
+      for (i = 0; i < nexp; i++)
+	{
+	  /* Pointer to the names vector.  */
+	  bfd_vma name_rva = pe_as32 (erva + name_rvas + i * 4);
+	  def_file_import *imp;
+	  /* Pointer to the function address vector.  */
+	  bfd_vma func_rva = pe_as32 (erva + exp_funcbase + i * 4);
+	  /* is_data is true if the address is in the data, rdata or bss
+	     segment.  */
+	  const int is_data =
+	    (func_rva >= data_start && func_rva < data_end)
+	    || (func_rva >= rdata_start && func_rva < rdata_end)
+	    || (func_rva >= bss_start && func_rva < bss_end);
+
+	  imp = def_file_add_import_at (pe_def_file, from + i, erva + name_rva,
+					dllname, i, NULL, NULL);
+	  /* Mark symbol type.  */
+	  imp->data = is_data;
+
+	  if (pe_dll_extra_pe_debug)
+	    printf ("%s dll-name: %s sym: %s addr: 0x%lx %s\n",
+		    __FUNCTION__, dllname, erva + name_rva,
+		    (unsigned long) func_rva, is_data ? "(data)" : "");
+	}
+
+      return TRUE;
+    }
+
   /* Iterate through the list of symbols.  */
   for (i = 0; i < nexp; i++)
     {