* 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.

2 files changed, 205 insertions, 8 deletions

diff --git a/bfd/ChangeLog b/bfd/ChangeLog
index 5e5e84e0fd..075895e330 100644
--- a/bfd/ChangeLog
+++ b/bfd/ChangeLog
@@ -1,3 +1,10 @@
+2005-12-19  David Heine  <dlheine@tensilica.com>
+
+	* 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.
+
 2005-12-16  Nathan Sidwell  <nathan@codesourcery.com>
 
 	Second part of ms1 to mt renaming.
diff --git a/bfd/elf32-xtensa.c b/bfd/elf32-xtensa.c
index e565942bff..2cafb3ed10 100644
--- a/bfd/elf32-xtensa.c
+++ b/bfd/elf32-xtensa.c
@@ -4756,6 +4756,19 @@ offset_with_removed_text (text_action_list *action_list, bfd_vma offset)
 }
 
 
+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_table)
 }
 
 
+/* 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;
 }