1 files changed, 156 insertions, 25 deletions

diff --git a/bfd/elf32-xtensa.c b/bfd/elf32-xtensa.c
index 872370b..21b2871 100644
--- a/bfd/elf32-xtensa.c
+++ b/bfd/elf32-xtensa.c
@@ -5420,11 +5420,28 @@ struct text_action_struct
   text_action *next;
 };
 
+struct removal_by_action_entry_struct
+{
+  bfd_vma offset;
+  int removed;
+  int eq_removed;
+  int eq_removed_before_fill;
+};
+typedef struct removal_by_action_entry_struct removal_by_action_entry;
+
+struct removal_by_action_map_struct
+{
+  unsigned n_entries;
+  removal_by_action_entry *entry;
+};
+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;
+  removal_by_action_map map;
 };
 
 
@@ -5636,6 +5653,101 @@ action_list_count (text_action_list *action_list)
   return count;
 }
 
+static void
+map_removal_by_action (text_action_list *action_list)
+{
+  text_action *r;
+  int removed = 0;
+  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;
+
+  for (r = action_list->head; r;)
+    {
+      removal_by_action_entry *ientry = map.entry + map.n_entries;
+
+      if (map.n_entries && (ientry - 1)->offset == r->offset)
+	{
+	  --ientry;
+	}
+      else
+	{
+	  ++map.n_entries;
+	  eq_complete = FALSE;
+	  ientry->offset = r->offset;
+	  ientry->eq_removed_before_fill = removed;
+	}
+
+      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;
+	}
+
+      removed += r->removed_bytes;
+      ientry->removed = removed;
+      r = r->next;
+    }
+  action_list->map = map;
+}
+
+static int
+removed_by_actions_map (text_action_list *action_list, bfd_vma offset,
+			bfd_boolean before_fill)
+{
+  unsigned a, b;
+
+  if (!action_list->map.entry)
+    map_removal_by_action (action_list);
+
+  if (!action_list->map.n_entries)
+    return 0;
+
+  a = 0;
+  b = action_list->map.n_entries;
+
+  while (b - a > 1)
+    {
+      unsigned c = (a + b) / 2;
+
+      if (action_list->map.entry[c].offset <= offset)
+	a = c;
+      else
+	b = c;
+    }
+
+  if (action_list->map.entry[a].offset < offset)
+    {
+      return action_list->map.entry[a].removed;
+    }
+  else if (action_list->map.entry[a].offset == offset)
+    {
+      return before_fill ?
+	action_list->map.entry[a].eq_removed_before_fill :
+	action_list->map.entry[a].eq_removed;
+    }
+  else
+    {
+      return 0;
+    }
+}
+
+static bfd_vma
+offset_with_removed_text_map (text_action_list *action_list, bfd_vma offset)
+{
+  int removed = removed_by_actions_map (action_list, offset, FALSE);
+  return offset - removed;
+}
+
 
 /* The find_insn_action routine will only find non-fill actions.  */
 
@@ -5909,6 +6021,9 @@ init_xtensa_relax_info (asection *sec)
 
   relax_info->action_list.head = NULL;
 
+  relax_info->action_list.map.n_entries = 0;
+  relax_info->action_list.map.entry = NULL;
+
   relax_info->fix_list = NULL;
   relax_info->fix_array = NULL;
   relax_info->fix_array_count = 0;
@@ -9218,7 +9333,7 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 		  if (elf_hash_table (link_info)->dynamic_sections_created)
 		    shrink_dynamic_reloc_sections (link_info, abfd, sec, irel);
 		  irel->r_info = ELF32_R_INFO (0, R_XTENSA_NONE);
-		  irel->r_offset = offset_with_removed_text
+		  irel->r_offset = offset_with_removed_text_map
 		    (&relax_info->action_list, irel->r_offset);
 		  continue;
 		}
@@ -9255,7 +9370,7 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 		    }
 		}
 
-	      source_offset = offset_with_removed_text
+	      source_offset = offset_with_removed_text_map
 		(&relax_info->action_list, irel->r_offset);
 	      irel->r_offset = source_offset;
 	    }
@@ -9352,7 +9467,7 @@ relax_section (bfd *abfd, asection *sec, struct bfd_link_info *link_info)
 		      break;
 		    }
 
-		  new_end_offset = offset_with_removed_text
+		  new_end_offset = offset_with_removed_text_map
 		    (&target_relax_info->action_list,
 		     r_rel.target_offset + diff_value);
 		  diff_value = new_end_offset - new_reloc.target_offset;
@@ -9750,7 +9865,6 @@ translate_reloc (const r_reloc *orig_rel, r_reloc *new_rel, asection *sec)
   xtensa_relax_info *relax_info;
   removed_literal *removed;
   bfd_vma target_offset, base_offset;
-  text_action *act;
 
   *new_rel = *orig_rel;
 
@@ -9803,19 +9917,26 @@ translate_reloc (const r_reloc *orig_rel, r_reloc *new_rel, asection *sec)
      offset.  */
 
   base_offset = r_reloc_get_target_offset (new_rel) - new_rel->rela.r_addend;
-  act = relax_info->action_list.head;
   if (base_offset <= target_offset)
     {
-      int base_removed = removed_by_actions (&act, base_offset, FALSE);
-      int addend_removed = removed_by_actions (&act, target_offset, FALSE);
+      int base_removed = removed_by_actions_map (&relax_info->action_list,
+						 base_offset, FALSE);
+      int addend_removed = removed_by_actions_map (&relax_info->action_list,
+						   target_offset, FALSE) -
+	base_removed;
+
       new_rel->target_offset = target_offset - base_removed - addend_removed;
       new_rel->rela.r_addend -= addend_removed;
     }
   else
     {
       /* Handle a negative addend.  The base offset comes first.  */
-      int tgt_removed = removed_by_actions (&act, target_offset, FALSE);
-      int addend_removed = removed_by_actions (&act, base_offset, FALSE);
+      int tgt_removed = removed_by_actions_map (&relax_info->action_list,
+						target_offset, FALSE);
+      int addend_removed = removed_by_actions_map (&relax_info->action_list,
+						   base_offset, FALSE) -
+	tgt_removed;
+
       new_rel->target_offset = target_offset - tgt_removed;
       new_rel->rela.r_addend += addend_removed;
     }
@@ -10138,9 +10259,10 @@ relax_property_section (bfd *abfd,
 	      bfd_vma old_offset = val.r_rel.target_offset;
 	      bfd_vma new_offset;
 	      long old_size, new_size;
-	      text_action *act = target_relax_info->action_list.head;
-	      new_offset = old_offset -
-		removed_by_actions (&act, old_offset, FALSE);
+	      int removed_by_old_offset =
+		removed_by_actions_map (&target_relax_info->action_list,
+					old_offset, FALSE);
+	      new_offset = old_offset - removed_by_old_offset;
 
 	      /* Assert that we are not out of bounds.  */
 	      old_size = bfd_get_32 (abfd, size_p);
@@ -10164,9 +10286,10 @@ relax_property_section (bfd *abfd,
 
 		      /* Recompute the new_offset, but this time don't
 			 include any fill inserted by relaxation.  */
-		      act = target_relax_info->action_list.head;
-		      new_offset = old_offset -
-			removed_by_actions (&act, old_offset, TRUE);
+		      removed_by_old_offset =
+			removed_by_actions_map (&target_relax_info->action_list,
+						old_offset, TRUE);
+		      new_offset = old_offset - removed_by_old_offset;
 
 		      /* If it is not unreachable and we have not yet
 			 seen an unreachable at this address, place it
@@ -10182,8 +10305,12 @@ relax_property_section (bfd *abfd,
 		    }
 		}
 	      else
-		new_size -=
-		    removed_by_actions (&act, old_offset + old_size, TRUE);
+		{
+		  int removed_by_old_offset_size =
+		    removed_by_actions_map (&target_relax_info->action_list,
+					    old_offset + old_size, TRUE);
+		  new_size -= removed_by_old_offset_size - removed_by_old_offset;
+		}
 
 	      if (new_size != old_size)
 		{
@@ -10441,14 +10568,16 @@ relax_section_symbols (bfd *abfd, asection *sec)
 
       if (isym->st_shndx == sec_shndx)
 	{
-	  text_action *act = relax_info->action_list.head;
 	  bfd_vma orig_addr = isym->st_value;
+	  int removed = removed_by_actions_map (&relax_info->action_list,
+						orig_addr, FALSE);
 
-	  isym->st_value -= removed_by_actions (&act, orig_addr, FALSE);
-
+	  isym->st_value -= removed;
 	  if (ELF32_ST_TYPE (isym->st_info) == STT_FUNC)
 	    isym->st_size -=
-	      removed_by_actions (&act, orig_addr + isym->st_size, FALSE);
+	      removed_by_actions_map (&relax_info->action_list,
+				      orig_addr + isym->st_size, FALSE) -
+	      removed;
 	}
     }
 
@@ -10466,15 +10595,17 @@ relax_section_symbols (bfd *abfd, asection *sec)
 	   || sym_hash->root.type == bfd_link_hash_defweak)
 	  && sym_hash->root.u.def.section == sec)
 	{
-	  text_action *act = relax_info->action_list.head;
 	  bfd_vma orig_addr = sym_hash->root.u.def.value;
+	  int removed = removed_by_actions_map (&relax_info->action_list,
+						orig_addr, FALSE);
 
-	  sym_hash->root.u.def.value -=
-	    removed_by_actions (&act, orig_addr, FALSE);
+	  sym_hash->root.u.def.value -= removed;
 
 	  if (sym_hash->type == STT_FUNC)
 	    sym_hash->size -=
-	      removed_by_actions (&act, orig_addr + sym_hash->size, FALSE);
+	      removed_by_actions_map (&relax_info->action_list,
+				      orig_addr + sym_hash->size, FALSE) -
+	      removed;
 	}
     }