#include "libbfd.h"
#include "elf-bfd.h"
#include "elf/xtensa.h"
+#include "splay-tree.h"
#include "xtensa-isa.h"
#include "xtensa-config.h"
{
if (is_plt)
{
+ /* If the symbol has been localized its plt.refcount got moved
+ to got.refcount. Handle it as GOT. */
if (h->plt.refcount > 0)
h->plt.refcount--;
+ else
+ is_got = TRUE;
}
- else if (is_got)
+ if (is_got)
{
if (h->got.refcount > 0)
h->got.refcount--;
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
/* 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;
};
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;
}
}
+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
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)
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;
}
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;
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;
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;
}
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)
{
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)
removed += r->removed_bytes;
- r = r->next;
+ r = action_next (action_list, r);
}
*p_start_action = r;
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)
+ {
+ --ientry;
+ }
+ else
{
- removal_by_action_entry *ientry = map.entry + map.n_entries;
+ ++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
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;
}
#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 */
by the "from" offset field. */
typedef struct removed_literal_struct removed_literal;
+typedef struct removed_literal_map_entry_struct removed_literal_map_entry;
typedef struct removed_literal_list_struct removed_literal_list;
struct removed_literal_struct
removed_literal *next;
};
+struct removed_literal_map_entry_struct
+{
+ bfd_vma addr;
+ removed_literal *literal;
+};
+
struct removed_literal_list_struct
{
removed_literal *head;
removed_literal *tail;
+
+ unsigned n_map;
+ removed_literal_map_entry *map;
};
}
}
+static void
+map_removed_literal (removed_literal_list *removed_list)
+{
+ unsigned n_map = 0;
+ unsigned i;
+ removed_literal_map_entry *map = NULL;
+ removed_literal *r = removed_list->head;
+
+ for (i = 0; r; ++i, r = r->next)
+ {
+ if (i == n_map)
+ {
+ n_map = (n_map * 2) + 2;
+ map = bfd_realloc (map, n_map * sizeof (*map));
+ }
+ map[i].addr = r->from.target_offset;
+ map[i].literal = r;
+ }
+ removed_list->map = map;
+ removed_list->n_map = i;
+}
+
+static int
+removed_literal_compare (const void *a, const void *b)
+{
+ const removed_literal_map_entry *pa = a;
+ const removed_literal_map_entry *pb = b;
+
+ if (pa->addr == pb->addr)
+ return 0;
+ else
+ return pa->addr < pb->addr ? -1 : 1;
+}
/* Check if the list of removed literals contains an entry for the
given address. Return the entry if found. */
static removed_literal *
find_removed_literal (removed_literal_list *removed_list, bfd_vma addr)
{
- removed_literal *r = removed_list->head;
- while (r && r->from.target_offset < addr)
- r = r->next;
- if (r && r->from.target_offset == addr)
- return r;
- return NULL;
+ removed_literal_map_entry *p;
+ removed_literal *r = NULL;
+
+ if (removed_list->map == NULL)
+ map_removed_literal (removed_list);
+
+ p = bsearch (&addr, removed_list->map, removed_list->n_map,
+ sizeof (*removed_list->map), removed_literal_compare);
+ if (p)
+ {
+ while (p != removed_list->map && (p - 1)->addr == addr)
+ --p;
+ r = p->literal;
+ }
+ return r;
}
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;
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
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. */
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;
}
\f
/* 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. */
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);
}
/* 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
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;
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);
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)
break;
}
- removed += action->removed_bytes;
BFD_ASSERT (dup_dot <= final_size);
BFD_ASSERT (orig_dot <= orig_size);
}
projects / deliverable / binutils-gdb.git / blobdiff