+struct reloc_range_struct
+{
+ bfd_vma addr;
+ bfd_boolean add; /* TRUE if start of a range, FALSE otherwise. */
+ /* Original irel index in the array of relocations for a section. */
+ unsigned irel_index;
+};
+typedef struct reloc_range_struct reloc_range;
+
+typedef struct reloc_range_list_entry_struct reloc_range_list_entry;
+struct reloc_range_list_entry_struct
+{
+ reloc_range_list_entry *next;
+ reloc_range_list_entry *prev;
+ Elf_Internal_Rela *irel;
+ xtensa_opcode opcode;
+ int opnum;
+};
+
+struct reloc_range_list_struct
+{
+ /* The rest of the structure is only meaningful when ok is TRUE. */
+ bfd_boolean ok;
+
+ unsigned n_range; /* Number of range markers. */
+ reloc_range *range; /* Sorted range markers. */
+
+ unsigned first; /* Index of a first range element in the list. */
+ unsigned last; /* One past index of a last range element in the list. */
+
+ unsigned n_list; /* Number of list elements. */
+ reloc_range_list_entry *reloc; /* */
+ reloc_range_list_entry list_root;
+};
+
+static int
+reloc_range_compare (const void *a, const void *b)
+{
+ const reloc_range *ra = a;
+ const reloc_range *rb = b;
+
+ if (ra->addr != rb->addr)
+ return ra->addr < rb->addr ? -1 : 1;
+ if (ra->add != rb->add)
+ return ra->add ? -1 : 1;
+ return 0;
+}
+
+static void
+build_reloc_ranges (bfd *abfd, asection *sec,
+ bfd_byte *contents,
+ Elf_Internal_Rela *internal_relocs,
+ xtensa_opcode *reloc_opcodes,
+ reloc_range_list *list)
+{
+ unsigned i;
+ size_t n = 0;
+ size_t max_n = 0;
+ reloc_range *ranges = NULL;
+ reloc_range_list_entry *reloc =
+ bfd_malloc (sec->reloc_count * sizeof (*reloc));
+
+ memset (list, 0, sizeof (*list));
+ list->ok = TRUE;
+
+ for (i = 0; i < sec->reloc_count; i++)
+ {
+ Elf_Internal_Rela *irel = &internal_relocs[i];
+ int r_type = ELF32_R_TYPE (irel->r_info);
+ reloc_howto_type *howto = &elf_howto_table[r_type];
+ r_reloc r_rel;
+
+ if (r_type == R_XTENSA_ASM_SIMPLIFY
+ || r_type == R_XTENSA_32_PCREL
+ || !howto->pc_relative)
+ continue;
+
+ r_reloc_init (&r_rel, abfd, irel, contents,
+ bfd_get_section_limit (abfd, sec));
+
+ if (r_reloc_get_section (&r_rel) != sec)
+ continue;
+
+ if (n + 2 > max_n)
+ {
+ max_n = (max_n + 2) * 2;
+ ranges = bfd_realloc (ranges, max_n * sizeof (*ranges));
+ }
+
+ ranges[n].addr = irel->r_offset;
+ ranges[n + 1].addr = r_rel.target_offset;
+
+ ranges[n].add = ranges[n].addr < ranges[n + 1].addr;
+ ranges[n + 1].add = !ranges[n].add;
+
+ ranges[n].irel_index = i;
+ ranges[n + 1].irel_index = i;
+
+ n += 2;
+
+ reloc[i].irel = irel;
+
+ /* Every relocation won't possibly be checked in the optimized version of
+ check_section_ebb_pcrels_fit, so this needs to be done here. */
+ if (is_alt_relocation (ELF32_R_TYPE (irel->r_info)))
+ {
+ /* None of the current alternate relocs are PC-relative,
+ and only PC-relative relocs matter here. */
+ }
+ else
+ {
+ xtensa_opcode opcode;
+ int opnum;
+
+ if (reloc_opcodes)
+ opcode = reloc_opcodes[i];
+ else
+ opcode = get_relocation_opcode (abfd, sec, contents, irel);
+
+ if (opcode == XTENSA_UNDEFINED)
+ {
+ list->ok = FALSE;
+ break;
+ }
+
+ opnum = get_relocation_opnd (opcode, ELF32_R_TYPE (irel->r_info));
+ if (opnum == XTENSA_UNDEFINED)
+ {
+ list->ok = FALSE;
+ break;
+ }
+
+ /* Record relocation opcode and opnum as we've calculated them
+ anyway and they won't change. */
+ reloc[i].opcode = opcode;
+ reloc[i].opnum = opnum;
+ }
+ }
+
+ if (list->ok)
+ {
+ ranges = bfd_realloc (ranges, n * sizeof (*ranges));
+ qsort (ranges, n, sizeof (*ranges), reloc_range_compare);
+
+ list->n_range = n;
+ list->range = ranges;
+ list->reloc = reloc;
+ list->list_root.prev = &list->list_root;
+ list->list_root.next = &list->list_root;
+ }
+ else
+ {
+ free (ranges);
+ free (reloc);
+ }
+}
+
+static void reloc_range_list_append (reloc_range_list *list,
+ unsigned irel_index)
+{
+ reloc_range_list_entry *entry = list->reloc + irel_index;
+
+ entry->prev = list->list_root.prev;
+ entry->next = &list->list_root;
+ entry->prev->next = entry;
+ entry->next->prev = entry;
+ ++list->n_list;
+}
+
+static void reloc_range_list_remove (reloc_range_list *list,
+ unsigned irel_index)
+{
+ reloc_range_list_entry *entry = list->reloc + irel_index;
+
+ entry->next->prev = entry->prev;
+ entry->prev->next = entry->next;
+ --list->n_list;
+}
+
+/* Update relocation list object so that it lists all relocations that cross
+ [first; last] range. Range bounds should not decrease with successive
+ invocations. */
+static void reloc_range_list_update_range (reloc_range_list *list,
+ bfd_vma first, bfd_vma last)
+{
+ /* This should not happen: EBBs are iterated from lower addresses to higher.
+ But even if that happens there's no need to break: just flush current list
+ and start from scratch. */
+ if ((list->last > 0 && list->range[list->last - 1].addr > last) ||
+ (list->first > 0 && list->range[list->first - 1].addr >= first))
+ {
+ list->first = 0;
+ list->last = 0;
+ list->n_list = 0;
+ list->list_root.next = &list->list_root;
+ list->list_root.prev = &list->list_root;
+ fprintf (stderr, "%s: move backwards requested\n", __func__);
+ }
+
+ for (; list->last < list->n_range &&
+ list->range[list->last].addr <= last; ++list->last)
+ if (list->range[list->last].add)
+ reloc_range_list_append (list, list->range[list->last].irel_index);
+
+ for (; list->first < list->n_range &&
+ list->range[list->first].addr < first; ++list->first)
+ if (!list->range[list->first].add)
+ reloc_range_list_remove (list, list->range[list->first].irel_index);
+}
+
+static void free_reloc_range_list (reloc_range_list *list)
+{
+ free (list->range);
+ free (list->reloc);
+}