improve Xtensa link performance

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

improve Xtensa link performance

Bob Wilson
I'm committing this patch to improve link-time performance for the Xtensa port
of ld.  It replaces an unsorted list with a sorted array when the list length
exceeds a fixed threshold.  There are a few unexpected failures for the
xtensa-elf target, and I am working on fixing those, but this patch doesn't
cause any additional regressions.

2005-12-19  David Heine  <[hidden email]>

        * elf32-xtensa.c (action_list_count, xlate_map_entry, xlate_map,
        xlate_offset_with_removed_text, build_xlate_map, free_xlate_map): New.
        (check_section_ebb_pcrels_fit): Build new xlate_map, use it and free it
        when finished.


Index: elf32-xtensa.c
===================================================================
RCS file: /cvs/src/src/bfd/elf32-xtensa.c,v
retrieving revision 1.60
diff -u -p -r1.60 elf32-xtensa.c
--- elf32-xtensa.c 3 Oct 2005 21:49:17 -0000 1.60
+++ elf32-xtensa.c 19 Dec 2005 19:31:31 -0000
@@ -4756,6 +4756,19 @@ offset_with_removed_text (text_action_li
 }
 
 
+static unsigned
+action_list_count (text_action_list *action_list)
+{
+  text_action *r = action_list->head;
+  unsigned count = 0;
+  for (r = action_list->head; r != NULL; r = r->next)
+    {
+      count++;
+    }
+  return count;
+}
+
+
 static bfd_vma
 offset_with_removed_text_before_fill (text_action_list *action_list,
       bfd_vma offset)
@@ -6851,6 +6864,160 @@ compute_ebb_actions (ebb_constraint *ebb
 }
 
 
+/* The xlate_map is a sorted array of address mappings designed to
+   answer the offset_with_removed_text() query with a binary search instead
+   of a linear search through the section's action_list.  */
+
+typedef struct xlate_map_entry xlate_map_entry_t;
+typedef struct xlate_map xlate_map_t;
+
+struct xlate_map_entry
+{
+  unsigned orig_address;
+  unsigned new_address;
+  unsigned size;
+};
+
+struct xlate_map
+{
+  unsigned entry_count;
+  xlate_map_entry_t *entry;
+};
+
+
+static int
+xlate_compare (const void *a_v, const void *b_v)
+{
+  const xlate_map_entry_t *a = (const xlate_map_entry_t *) a_v;
+  const xlate_map_entry_t *b = (const xlate_map_entry_t *) b_v;
+  if (a->orig_address < b->orig_address)
+    return -1;
+  if (a->orig_address > (b->orig_address + b->size - 1))
+    return 1;
+  return 0;
+}
+
+
+static bfd_vma
+xlate_offset_with_removed_text (const xlate_map_t *map,
+ text_action_list *action_list,
+ bfd_vma offset)
+{
+  xlate_map_entry_t tmp;
+  void *r;
+  xlate_map_entry_t *e;
+
+  if (map == NULL)
+    return offset_with_removed_text (action_list, offset);
+
+  if (map->entry_count == 0)
+    return offset;
+
+  tmp.orig_address = offset;
+  tmp.new_address = offset;
+  tmp.size = 1;
+
+  r = bsearch (&offset, map->entry, map->entry_count,
+       sizeof (xlate_map_entry_t), &xlate_compare);
+  e = (xlate_map_entry_t *) r;
+  
+  BFD_ASSERT (e != NULL);
+  if (e == NULL)
+    return offset;
+  return e->new_address - e->orig_address + offset;
+}
+
+
+/* Build a binary searchable offset translation map from a section's
+   action list.  */
+
+static xlate_map_t *
+build_xlate_map (asection *sec, xtensa_relax_info *relax_info)
+{
+  xlate_map_t *map = (xlate_map_t *) bfd_malloc (sizeof (xlate_map_t));
+  text_action_list *action_list = &relax_info->action_list;
+  unsigned num_actions = 0;
+  text_action *r;
+  int removed;
+  xlate_map_entry_t *current_entry;
+
+  if (map == NULL)
+    return NULL;
+
+  num_actions = action_list_count (action_list);
+  map->entry = (xlate_map_entry_t *)
+    bfd_malloc (sizeof (xlate_map_entry_t) * (num_actions + 1));
+  if (map->entry == NULL)
+    {
+      free (map);
+      return NULL;
+    }
+  map->entry_count = 0;
+  
+  removed = 0;
+  current_entry = &map->entry[0];
+
+  current_entry->orig_address = 0;
+  current_entry->new_address = 0;
+  current_entry->size = 0;
+
+  for (r = action_list->head; r != NULL; r = r->next)
+    {
+      unsigned orig_size = 0;
+      switch (r->action)
+ {
+ case ta_none:
+ case ta_remove_insn:
+ case ta_convert_longcall:
+ case ta_remove_literal:
+ case ta_add_literal:
+  break;
+ case ta_remove_longcall:
+  orig_size = 6;
+  break;
+ case ta_narrow_insn:
+  orig_size = 3;
+  break;
+ case ta_widen_insn:
+  orig_size = 2;
+  break;
+ case ta_fill:
+  break;
+ }
+      current_entry->size =
+ r->offset + orig_size - current_entry->orig_address;
+      if (current_entry->size != 0)
+ {
+  current_entry++;
+  map->entry_count++;
+ }
+      current_entry->orig_address = r->offset + orig_size;
+      removed += r->removed_bytes;
+      current_entry->new_address = r->offset + orig_size - removed;
+      current_entry->size = 0;
+    }
+
+  current_entry->size = (bfd_get_section_limit (sec->owner, sec)
+ - current_entry->orig_address);
+  if (current_entry->size != 0)
+    map->entry_count++;
+
+  return map;
+}
+
+
+/* Free an offset translation map.  */
+
+static void
+free_xlate_map (xlate_map_t *map)
+{
+  if (map && map->entry)
+    free (map->entry);
+  if (map)
+    free (map);
+}
+
+
 /* Use check_section_ebb_pcrels_fit to make sure that all of the
    relocations in a section will fit if a proposed set of actions
    are performed.  */
@@ -6864,10 +7031,19 @@ check_section_ebb_pcrels_fit (bfd *abfd,
 {
   unsigned i, j;
   Elf_Internal_Rela *irel;
+  xlate_map_t *xmap = NULL;
+  bfd_boolean ok = TRUE;
   xtensa_relax_info *relax_info;
 
   relax_info = get_xtensa_relax_info (sec);
 
+  if (relax_info && sec->reloc_count > 100)
+    {
+      xmap = build_xlate_map (sec, relax_info);
+      /* NULL indicates out of memory, but the slow version
+ can still be used.  */
+    }
+
   for (i = 0; i < sec->reloc_count; i++)
     {
       r_reloc r_rel;
@@ -6903,10 +7079,12 @@ check_section_ebb_pcrels_fit (bfd *abfd,
 
       if (relax_info)
  {
-  self_offset = offset_with_removed_text (&relax_info->action_list,
-  orig_self_offset);
-  target_offset = offset_with_removed_text (&relax_info->action_list,
-    orig_target_offset);
+  self_offset =
+    xlate_offset_with_removed_text (xmap, &relax_info->action_list,
+    orig_self_offset);
+  target_offset =
+    xlate_offset_with_removed_text (xmap, &relax_info->action_list,
+    orig_target_offset);
  }
 
       self_removed_bytes = 0;
@@ -6942,18 +7120,30 @@ check_section_ebb_pcrels_fit (bfd *abfd,
 
   opcode = get_relocation_opcode (abfd, sec, contents, irel);
   if (opcode == XTENSA_UNDEFINED)
-    return FALSE;
+    {
+      ok = FALSE;
+      break;
+    }
 
   opnum = get_relocation_opnd (opcode, ELF32_R_TYPE (irel->r_info));
   if (opnum == XTENSA_UNDEFINED)
-    return FALSE;
+    {
+      ok = FALSE;
+      break;
+    }
 
   if (!pcrel_reloc_fits (opcode, opnum, self_offset, target_offset))
-    return FALSE;
+    {
+      ok = FALSE;
+      break;
+    }
  }
     }
 
-  return TRUE;
+  if (xmap)
+    free_xlate_map (xmap);
+
+  return ok;
 }