xtensa: optimize check_section_ebb_pcrels_fit

The original check_section_ebb_pcrels_fit algorithm checks that text
actions proposed for current EBB are OK for every relocation in a
section. There's no need to check every relocation, because text actions
for EBB can only change size of that EBB, thus only affecting
relocations that in any way cross that EBB. In addition EBBs are
iterated in ascending order of their VMA, making it easier to track
relevant relocations.

Introduce a structure that can track relocations that cross the range of
VMAs of EBB and use it to only check relocations relevant to current EBB
in check_section_ebb_pcrels_fit.
It takes O(N log N) operations to build it and O(N) operations to move
current EBB VMA window through its entire range, where N is the number
of relocations in a section. The resulting complexity of
compute_text_actions is thus reduced from O(N^2) to O(N log N + N * M),
where M is the average number of relocations crossing each EBB.

Original profile:

% time    self  children    called     name
-----------------------------------------
         44.26   71.53    6429/6429        compute_text_actions
  50.2   44.26   71.53    6429         check_section_ebb_pcrels_fit
          1.16   20.12 347506666/347576152     pcrel_reloc_fits
          2.95   16.52 347506666/348104944     get_relocation_opnd
          2.01    9.74 347575100/361252208     r_reloc_init
          0.55    7.53 347575100/363381467     r_reloc_get_section
          5.76    0.02 695013332/695013332     xlate_offset_with_removed_text
          0.68    3.89 347575100/363483827     bfd_octets_per_byte
          0.32    0.00 347506666/349910253     is_alt_relocation
          0.18    0.11    6391/6391        build_xlate_map
          0.00    0.00    6429/19417168     get_xtensa_relax_info
          0.00    0.00    6391/6391        free_xlate_map
-----------------------------------------

Same data, after optimization:

% time    self  children    called     name
-----------------------------------------
          2.56    3.08    6429/6429        compute_text_actions
   8.2    2.56    3.08    6429         check_section_ebb_pcrels_fit
          0.08    0.91 17721075/17790561     pcrel_reloc_fits
          0.17    0.47 17721075/31685977     r_reloc_init
          0.43    0.00 35442150/35442150     xlate_offset_with_removed_text
          0.02    0.37 17721075/33815236     r_reloc_get_section
          0.22    0.11    6391/6391        build_xlate_map
          0.05    0.22 17721075/33917596     bfd_octets_per_byte
          0.03    0.00 17721075/20405299     is_alt_relocation
          0.01    0.00    6429/6429        reloc_range_list_update_range
          0.00    0.00    6429/19417168     get_xtensa_relax_info
          0.00    0.00    6391/6391        free_xlate_map
-----------------------------------------

2015-04-01  Max Filippov  <jcmvbkbc@gmail.com>
bfd/
	* elf32-xtensa.c (reloc_range_list, reloc_range_list_entry,
	reloc_range): new typedef.
	(reloc_range_list_struct, reloc_range_list_entry_struct,
	reloc_range_struct): new structures.
	(reloc_range_compare, build_reloc_ranges,
	reloc_range_list_append, reloc_range_list_remove,
	reloc_range_list_update_range, free_reloc_range_list): new
	functions.
	(compute_text_actions): precompute relocation opcodes before the
	loop. Add relevant_relocs variable, initialize it before the
	loop, pass it to the check_section_ebb_pcrels_fit.
	(check_section_ebb_pcrels_fit): add new parameter:
	relevant_relocs. Update address range in the relevant_relocs if
	it's non-NULL and iterate only over relevant relocations.

0 files changed, 0 insertions, 0 deletions