1 files changed, 282 insertions, 206 deletions

diff --git a/bfd/elf32-xtensa.c b/bfd/elf32-xtensa.c
index 51733ad..53af1c6 100644
--- a/bfd/elf32-xtensa.c
+++ b/bfd/elf32-xtensa.c
@@ -28,6 +28,7 @@
 #include "libbfd.h"
 #include "elf-bfd.h"
 #include "elf/xtensa.h"
+#include "splay-tree.h"
 #include "xtensa-isa.h"
 #include "xtensa-config.h"
 
@@ -5416,8 +5417,6 @@ struct text_action_struct
   bfd_vma virtual_offset;  /* Zero except for adding literals.  */
   int removed_bytes;
   literal_value value;	/* Only valid when adding literals.  */
-
-  text_action *next;
 };
 
 struct removal_by_action_entry_struct
@@ -5440,7 +5439,8 @@ typedef struct removal_by_action_map_struct removal_by_action_map;
 /* List of all of the actions taken on a text section.  */
 struct text_action_list_struct
 {
-  text_action *head;
+  unsigned count;
+  splay_tree tree;
   removal_by_action_map map;
 };
 
@@ -5448,20 +5448,18 @@ struct text_action_list_struct
 static text_action *
 find_fill_action (text_action_list *l, asection *sec, bfd_vma offset)
 {
-  text_action **m_p;
+  text_action a;
 
   /* It is not necessary to fill at the end of a section.  */
   if (sec->size == offset)
     return NULL;
 
-  for (m_p = &l->head; *m_p && (*m_p)->offset <= offset; m_p = &(*m_p)->next)
-    {
-      text_action *t = *m_p;
-      /* When the action is another fill at the same address,
-	 just increase the size.  */
-      if (t->offset == offset && t->action == ta_fill)
-	return t;
-    }
+  a.offset = offset;
+  a.action = ta_fill;
+
+  splay_tree_node node = splay_tree_lookup (l->tree, (splay_tree_key)&a);
+  if (node)
+    return (text_action *)node->value;
   return NULL;
 }
 
@@ -5509,6 +5507,49 @@ adjust_fill_action (text_action *ta, int fill_diff)
 }
 
 
+static int
+text_action_compare (splay_tree_key a, splay_tree_key b)
+{
+  text_action *pa = (text_action *)a;
+  text_action *pb = (text_action *)b;
+  static const int action_priority[] =
+    {
+      [ta_fill] = 0,
+      [ta_none] = 1,
+      [ta_convert_longcall] = 2,
+      [ta_narrow_insn] = 3,
+      [ta_remove_insn] = 4,
+      [ta_remove_longcall] = 5,
+      [ta_remove_literal] = 6,
+      [ta_widen_insn] = 7,
+      [ta_add_literal] = 8,
+    };
+
+  if (pa->offset == pb->offset)
+    {
+      if (pa->action == pb->action)
+	  return 0;
+      return action_priority[pa->action] - action_priority[pb->action];
+    }
+  else
+    return pa->offset < pb->offset ? -1 : 1;
+}
+
+static text_action *
+action_first (text_action_list *action_list)
+{
+  splay_tree_node node = splay_tree_min (action_list->tree);
+  return node ? (text_action *)node->value : NULL;
+}
+
+static text_action *
+action_next (text_action_list *action_list, text_action *action)
+{
+  splay_tree_node node = splay_tree_successor (action_list->tree,
+					       (splay_tree_key)action);
+  return node ? (text_action *)node->value : NULL;
+}
+
 /* Add a modification action to the text.  For the case of adding or
    removing space, modify any current fill and assume that
    "unreachable_space" bytes can be freely contracted.  Note that a
@@ -5521,8 +5562,8 @@ text_action_add (text_action_list *l,
 		 bfd_vma offset,
 		 int removed)
 {
-  text_action **m_p;
   text_action *ta;
+  text_action a;
 
   /* It is not necessary to fill at the end of a section.  */
   if (action == ta_fill && sec->size == offset)
@@ -5532,34 +5573,30 @@ text_action_add (text_action_list *l,
   if (action == ta_fill && removed == 0)
     return;
 
-  for (m_p = &l->head; *m_p && (*m_p)->offset <= offset; m_p = &(*m_p)->next)
+  a.action = action;
+  a.offset = offset;
+
+  if (action == ta_fill)
     {
-      text_action *t = *m_p;
+      splay_tree_node node = splay_tree_lookup (l->tree, (splay_tree_key)&a);
 
-      if (action == ta_fill)
+      if (node)
 	{
-	  /* When the action is another fill at the same address,
-	     just increase the size.  */
-	  if (t->offset == offset && t->action == ta_fill)
-	    {
-	      t->removed_bytes += removed;
-	      return;
-	    }
-	  /* Fills need to happen before widens so that we don't
-	     insert fill bytes into the instruction stream.  */
-	  if (t->offset == offset && t->action == ta_widen_insn)
-	    break;
+	  ta = (text_action *)node->value;
+	  ta->removed_bytes += removed;
+	  return;
 	}
     }
+  else
+    BFD_ASSERT (splay_tree_lookup (l->tree, (splay_tree_key)&a) == NULL);
 
-  /* Create a new record and fill it up.  */
   ta = (text_action *) bfd_zmalloc (sizeof (text_action));
   ta->action = action;
   ta->sec = sec;
   ta->offset = offset;
   ta->removed_bytes = removed;
-  ta->next = (*m_p);
-  *m_p = ta;
+  splay_tree_insert (l->tree, (splay_tree_key)ta, (splay_tree_value)ta);
+  ++l->count;
 }
 
 
@@ -5570,7 +5607,6 @@ text_action_add_literal (text_action_list *l,
 			 const literal_value *value,
 			 int removed)
 {
-  text_action **m_p;
   text_action *ta;
   asection *sec = r_reloc_get_section (loc);
   bfd_vma offset = loc->target_offset;
@@ -5578,14 +5614,6 @@ text_action_add_literal (text_action_list *l,
 
   BFD_ASSERT (action == ta_add_literal);
 
-  for (m_p = &l->head; *m_p != NULL; m_p = &(*m_p)->next)
-    {
-      if ((*m_p)->offset > offset
-	  && ((*m_p)->offset != offset
-	      || (*m_p)->virtual_offset > virtual_offset))
-	break;
-    }
-
   /* Create a new record and fill it up.  */
   ta = (text_action *) bfd_zmalloc (sizeof (text_action));
   ta->action = action;
@@ -5594,8 +5622,10 @@ text_action_add_literal (text_action_list *l,
   ta->virtual_offset = virtual_offset;
   ta->value = *value;
   ta->removed_bytes = removed;
-  ta->next = (*m_p);
-  *m_p = ta;
+
+  BFD_ASSERT (splay_tree_lookup (l->tree, (splay_tree_key)ta) == NULL);
+  splay_tree_insert (l->tree, (splay_tree_key)ta, (splay_tree_value)ta);
+  ++l->count;
 }
 
 
@@ -5606,7 +5636,8 @@ text_action_add_literal (text_action_list *l,
    so that each search may begin where the previous one left off.  */
 
 static int
-removed_by_actions (text_action **p_start_action,
+removed_by_actions (text_action_list *action_list,
+		    text_action **p_start_action,
 		    bfd_vma offset,
 		    bfd_boolean before_fill)
 {
@@ -5614,6 +5645,13 @@ removed_by_actions (text_action **p_start_action,
   int removed = 0;
 
   r = *p_start_action;
+  if (r)
+    {
+      splay_tree_node node = splay_tree_lookup (action_list->tree,
+						(splay_tree_key)r);
+      BFD_ASSERT (node != NULL && r == (text_action *)node->value);
+    }
+
   while (r)
     {
       if (r->offset > offset)
@@ -5625,7 +5663,7 @@ removed_by_actions (text_action **p_start_action,
 
       removed += r->removed_bytes;
 
-      r = r->next;
+      r = action_next (action_list, r);
     }
 
   *p_start_action = r;
@@ -5636,68 +5674,74 @@ removed_by_actions (text_action **p_start_action,
 static bfd_vma
 offset_with_removed_text (text_action_list *action_list, bfd_vma offset)
 {
-  text_action *r = action_list->head;
-  return offset - removed_by_actions (&r, offset, FALSE);
+  text_action *r = action_first (action_list);
+
+  return offset - removed_by_actions (action_list, &r, offset, FALSE);
 }
 
 
 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;
+  return action_list->count;
 }
 
-static void
-map_removal_by_action (text_action_list *action_list)
+typedef struct map_action_fn_context_struct map_action_fn_context;
+struct map_action_fn_context_struct
 {
-  text_action *r;
-  int removed = 0;
+  int removed;
   removal_by_action_map map;
   bfd_boolean eq_complete;
+};
 
-  map.n_entries = 0;
-  map.entry = bfd_malloc (action_list_count (action_list) *
-			  sizeof (removal_by_action_entry));
-  eq_complete = FALSE;
+static int
+map_action_fn (splay_tree_node node, void *p)
+{
+  map_action_fn_context *ctx = p;
+  text_action *r = (text_action *)node->value;
+  removal_by_action_entry *ientry = ctx->map.entry + ctx->map.n_entries;
 
-  for (r = action_list->head; r;)
+  if (ctx->map.n_entries && (ientry - 1)->offset == r->offset)
     {
-      removal_by_action_entry *ientry = map.entry + map.n_entries;
+      --ientry;
+    }
+  else
+    {
+      ++ctx->map.n_entries;
+      ctx->eq_complete = FALSE;
+      ientry->offset = r->offset;
+      ientry->eq_removed_before_fill = ctx->removed;
+    }
 
-      if (map.n_entries && (ientry - 1)->offset == r->offset)
+  if (!ctx->eq_complete)
+    {
+      if (r->action != ta_fill || r->removed_bytes >= 0)
 	{
-	  --ientry;
+	  ientry->eq_removed = ctx->removed;
+	  ctx->eq_complete = TRUE;
 	}
       else
-	{
-	  ++map.n_entries;
-	  eq_complete = FALSE;
-	  ientry->offset = r->offset;
-	  ientry->eq_removed_before_fill = removed;
-	}
+	ientry->eq_removed = ctx->removed + r->removed_bytes;
+    }
 
-      if (!eq_complete)
-	{
-	  if (r->action != ta_fill || r->removed_bytes >= 0)
-	    {
-	      ientry->eq_removed = removed;
-	      eq_complete = TRUE;
-	    }
-	  else
-	    ientry->eq_removed = removed + r->removed_bytes;
-	}
+  ctx->removed += r->removed_bytes;
+  ientry->removed = ctx->removed;
+  return 0;
+}
 
-      removed += r->removed_bytes;
-      ientry->removed = removed;
-      r = r->next;
-    }
-  action_list->map = map;
+static void
+map_removal_by_action (text_action_list *action_list)
+{
+  map_action_fn_context ctx;
+
+  ctx.removed = 0;
+  ctx.map.n_entries = 0;
+  ctx.map.entry = bfd_malloc (action_list_count (action_list) *
+			      sizeof (removal_by_action_entry));
+  ctx.eq_complete = FALSE;
+
+  splay_tree_foreach (action_list->tree, map_action_fn, &ctx);
+  action_list->map = ctx.map;
 }
 
 static int
@@ -5754,28 +5798,26 @@ offset_with_removed_text_map (text_action_list *action_list, bfd_vma offset)
 static text_action *
 find_insn_action (text_action_list *action_list, bfd_vma offset)
 {
-  text_action *t;
-  for (t = action_list->head; t; t = t->next)
+  static const text_action_t action[] =
     {
-      if (t->offset == offset)
-	{
-	  switch (t->action)
-	    {
-	    case ta_none:
-	    case ta_fill:
-	      break;
-	    case ta_remove_insn:
-	    case ta_remove_longcall:
-	    case ta_convert_longcall:
-	    case ta_narrow_insn:
-	    case ta_widen_insn:
-	      return t;
-	    case ta_remove_literal:
-	    case ta_add_literal:
-	      BFD_ASSERT (0);
-	      break;
-	    }
-	}
+      ta_convert_longcall,
+      ta_remove_longcall,
+      ta_widen_insn,
+      ta_narrow_insn,
+      ta_remove_insn,
+    };
+  text_action a;
+  unsigned i;
+
+  a.offset = offset;
+  for (i = 0; i < sizeof (action) / sizeof (*action); ++i)
+    {
+      splay_tree_node node;
+
+      a.action = action[i];
+      node = splay_tree_lookup (action_list->tree, (splay_tree_key)&a);
+      if (node)
+	return (text_action *)node->value;
     }
   return NULL;
 }
@@ -5784,40 +5826,50 @@ find_insn_action (text_action_list *action_list, bfd_vma offset)
 #if DEBUG
 
 static void
-print_action_list (FILE *fp, text_action_list *action_list)
+print_action (FILE *fp, text_action *r)
+{
+  const char *t = "unknown";
+  switch (r->action)
+    {
+    case ta_remove_insn:
+      t = "remove_insn"; break;
+    case ta_remove_longcall:
+      t = "remove_longcall"; break;
+    case ta_convert_longcall:
+      t = "convert_longcall"; break;
+    case ta_narrow_insn:
+      t = "narrow_insn"; break;
+    case ta_widen_insn:
+      t = "widen_insn"; break;
+    case ta_fill:
+      t = "fill"; break;
+    case ta_none:
+      t = "none"; break;
+    case ta_remove_literal:
+      t = "remove_literal"; break;
+    case ta_add_literal:
+      t = "add_literal"; break;
+    }
+
+  fprintf (fp, "%s: %s[0x%lx] \"%s\" %d\n",
+	   r->sec->owner->filename,
+	   r->sec->name, (unsigned long) r->offset, t, r->removed_bytes);
+}
+
+static int
+print_action_list_fn (splay_tree_node node, void *p)
 {
-  text_action *r;
+  text_action *r = (text_action *)node->value;
 
-  fprintf (fp, "Text Action\n");
-  for (r = action_list->head; r != NULL; r = r->next)
-    {
-      const char *t = "unknown";
-      switch (r->action)
-	{
-	case ta_remove_insn:
-	  t = "remove_insn"; break;
-	case ta_remove_longcall:
-	  t = "remove_longcall"; break;
-	case ta_convert_longcall:
-	  t = "convert_longcall"; break;
-	case ta_narrow_insn:
-	  t = "narrow_insn"; break;
-	case ta_widen_insn:
-	  t = "widen_insn"; break;
-	case ta_fill:
-	  t = "fill"; break;
-	case ta_none:
-	  t = "none"; break;
-	case ta_remove_literal:
-	  t = "remove_literal"; break;
-	case ta_add_literal:
-	  t = "add_literal"; break;
-	}
+  print_action (p, r);
+  return 0;
+}
 
-      fprintf (fp, "%s: %s[0x%lx] \"%s\" %d\n",
-	       r->sec->owner->filename,
-	       r->sec->name, (unsigned long) r->offset, t, r->removed_bytes);
-    }
+static void
+print_action_list (FILE *fp, text_action_list *action_list)
+{
+  fprintf (fp, "Text Action\n");
+  splay_tree_foreach (action_list->tree, print_action_list_fn, fp);
 }
 
 #endif /* DEBUG */
@@ -6071,8 +6123,8 @@ init_xtensa_relax_info (asection *sec)
   relax_info->removed_list.head = NULL;
   relax_info->removed_list.tail = NULL;
 
-  relax_info->action_list.head = NULL;
-
+  relax_info->action_list.tree = splay_tree_new (text_action_compare,
+						 NULL, NULL);
   relax_info->action_list.map.n_entries = 0;
   relax_info->action_list.map.entry = NULL;
 
@@ -7762,7 +7814,7 @@ compute_text_actions (bfd *abfd,
   free_reloc_range_list (&relevant_relocs);
 
 #if DEBUG
-  if (relax_info->action_list.head)
+  if (action_list_count (&relax_info->action_list))
     print_action_list (stderr, &relax_info->action_list);
 #endif
 
@@ -8263,6 +8315,54 @@ xlate_offset_with_removed_text (const xlate_map_t *map,
   return e->new_address - e->orig_address + offset;
 }
 
+typedef struct xlate_map_context_struct xlate_map_context;
+struct xlate_map_context_struct
+{
+  xlate_map_t *map;
+  xlate_map_entry_t *current_entry;
+  int removed;
+};
+
+static int
+xlate_map_fn (splay_tree_node node, void *p)
+{
+  text_action *r = (text_action *)node->value;
+  xlate_map_context *ctx = p;
+  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;
+    }
+  ctx->current_entry->size =
+    r->offset + orig_size - ctx->current_entry->orig_address;
+  if (ctx->current_entry->size != 0)
+    {
+      ctx->current_entry++;
+      ctx->map->entry_count++;
+    }
+  ctx->current_entry->orig_address = r->offset + orig_size;
+  ctx->removed += r->removed_bytes;
+  ctx->current_entry->new_address = r->offset + orig_size - ctx->removed;
+  ctx->current_entry->size = 0;
+  return 0;
+}
 
 /* Build a binary searchable offset translation map from a section's
    action list.  */
@@ -8270,75 +8370,40 @@ xlate_offset_with_removed_text (const xlate_map_t *map,
 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;
+  xlate_map_context ctx;
 
-  if (map == NULL)
+  ctx.map = (xlate_map_t *) bfd_malloc (sizeof (xlate_map_t));
+
+  if (ctx.map == NULL)
     return NULL;
 
   num_actions = action_list_count (action_list);
-  map->entry = (xlate_map_entry_t *)
+  ctx.map->entry = (xlate_map_entry_t *)
     bfd_malloc (sizeof (xlate_map_entry_t) * (num_actions + 1));
-  if (map->entry == NULL)
+  if (ctx.map->entry == NULL)
     {
-      free (map);
+      free (ctx.map);
       return NULL;
     }
-  map->entry_count = 0;
+  ctx.map->entry_count = 0;
 
-  removed = 0;
-  current_entry = &map->entry[0];
+  ctx.removed = 0;
+  ctx.current_entry = &ctx.map->entry[0];
 
-  current_entry->orig_address = 0;
-  current_entry->new_address = 0;
-  current_entry->size = 0;
+  ctx.current_entry->orig_address = 0;
+  ctx.current_entry->new_address = 0;
+  ctx.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;
-    }
+  splay_tree_foreach (action_list->tree, xlate_map_fn, &ctx);
 
-  current_entry->size = (bfd_get_section_limit (sec->owner, sec)
-			 - current_entry->orig_address);
-  if (current_entry->size != 0)
-    map->entry_count++;
+  ctx.current_entry->size = (bfd_get_section_limit (sec->owner, sec)
+			     - ctx.current_entry->orig_address);
+  if (ctx.current_entry->size != 0)
+    ctx.map->entry_count++;
 
-  return map;
+  return ctx.map;
 }
 
 
@@ -9302,6 +9367,16 @@ move_shared_literal (asection *sec,
 
 /* Second relaxation pass.  */
 
+static int
+action_remove_bytes_fn (splay_tree_node node, void *p)
+{
+  bfd_size_type *final_size = p;
+  text_action *action = (text_action *)node->value;
+
+  *final_size -= action->removed_bytes;
+  return 0;
+}
+
 /* Modify all of the relocations to point to the right spot, and if this
    is a relaxable section, delete the unwanted literals and fix the
    section size.  */
@@ -9334,7 +9409,7 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 
   internal_relocs = retrieve_internal_relocs (abfd, sec,
 					      link_info->keep_memory);
-  if (!internal_relocs && !relax_info->action_list.head)
+  if (!internal_relocs && !action_list_count (&relax_info->action_list))
     return TRUE;
 
   contents = retrieve_contents (abfd, sec, link_info->keep_memory);
@@ -9412,6 +9487,12 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 			}
 		      /* Update the action so that the code that moves
 			 the contents will do the right thing.  */
+		      /* ta_remove_longcall and ta_remove_insn actions are
+		         grouped together in the tree as well as
+			 ta_convert_longcall and ta_none, so that changes below
+			 can be done w/o removing and reinserting action into
+			 the tree.  */
+
 		      if (action->action == ta_remove_longcall)
 			action->action = ta_remove_insn;
 		      else
@@ -9584,13 +9665,12 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 
   if ((relax_info->is_relaxable_literal_section
        || relax_info->is_relaxable_asm_section)
-      && relax_info->action_list.head)
+      && action_list_count (&relax_info->action_list))
     {
       /* Walk through the planned actions and build up a table
 	 of move, copy and fill records.  Use the move, copy and
 	 fill records to perform the actions once.  */
 
-      int removed = 0;
       bfd_size_type final_size, copy_size, orig_insn_size;
       bfd_byte *scratch = NULL;
       bfd_byte *dup_contents = NULL;
@@ -9601,15 +9681,12 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
       bfd_vma orig_dot_vo = 0; /* Virtual offset from orig_dot.  */
       bfd_vma dup_dot = 0;
 
-      text_action *action = relax_info->action_list.head;
+      text_action *action;
 
       final_size = sec->size;
-      for (action = relax_info->action_list.head; action;
-	   action = action->next)
-	{
-	  final_size -= action->removed_bytes;
-	}
 
+      splay_tree_foreach (relax_info->action_list.tree,
+			  action_remove_bytes_fn, &final_size);
       scratch = (bfd_byte *) bfd_zmalloc (final_size);
       dup_contents = (bfd_byte *) bfd_zmalloc (final_size);
 
@@ -9618,8 +9695,8 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
       print_action_list (stderr, &relax_info->action_list);
 #endif
 
-      for (action = relax_info->action_list.head; action;
-	   action = action->next)
+      for (action = action_first (&relax_info->action_list); action;
+	   action = action_next (&relax_info->action_list, action))
 	{
 	  virtual_action = FALSE;
 	  if (action->offset > orig_dot)
@@ -9748,7 +9825,6 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 	      break;
 	    }
 
-	  removed += action->removed_bytes;
 	  BFD_ASSERT (dup_dot <= final_size);
 	  BFD_ASSERT (orig_dot <= orig_size);
 	}