xtensa: replace action list with splay tree

text_action_add uses linear list search to order text actions list by
action VMA. The list is used at the first relaxation pass, when it's not
fixed yet.
Replace the list with splay tree from libiberty.

Original profile:

% time    self  children    called     name
-----------------------------------------
          0.00    0.00      14/158225      compute_text_actions
          3.62    0.00   25211/158225      remove_dead_literal
          8.42    0.00   58645/158225      coalesce_shared_literal
         10.68    0.00   74355/158225      text_action_add_proposed
  38.8   22.73    0.00  158225         text_action_add
          0.00    0.00  144527/293246      bfd_zmalloc
-----------------------------------------

Same data, after optimization:

% time    self  children    called     name
-----------------------------------------
          0.00    0.00      14/158225      compute_text_actions
          0.00    0.00   25211/158225      remove_dead_literal
          0.00    0.01   58645/158225      coalesce_shared_literal
          0.00    0.01   74355/158225      text_action_add_proposed
   0.1    0.00    0.02  158225         text_action_add
          0.01    0.00  144527/144527      splay_tree_insert
          0.00    0.00  144527/195130      splay_tree_lookup
          0.00    0.00  144527/293246      bfd_zmalloc
-----------------------------------------

2015-04-03  Max Filippov  <jcmvbkbc@gmail.com>
bfd/
	* elf32-xtensa.c (splay-tree.h): include header.
	(text_action_struct): drop next pointer.
	(text_action_list_struct): drop head pointer, add count and
	tree fields.
	(find_fill_action): instead of linear search in text_action_list
	search in the tree.
	(text_action_compare, action_first, action_next): new functions.
	(text_action_add, text_action_add_literal): instead of linear
	search and insertion insert new node into the tree.
	(removed_by_actions): pass additional parameter: action_list,
	use it to traverse the tree.
	(offset_with_removed_text): pass additional action_list parameter
	to removed_by_actions.
	(map_action_fn_context): new typedef.
	(map_action_fn_context_struct): new structure.
	(map_action_fn): new function.
	(map_removal_by_action): use splay_tree_foreach to build map.
	(find_insn_action): replace linear search in text_action_list
	with series of splay_tree_lookups.
	(print_action, print_action_list_fn): new functions.
	(print_action_list): use splay_tree_foreach.
	(init_xtensa_relax_info): drop action_list.head initialization.
	Initialize the tree.
	(compute_text_actions): use non-zero action_list_count instead of
	non-NULL action list.
	(xlate_map_context): new typedef.
	(xlate_map_context_struct): new structure.
	(xlate_map_fn): new function.
	(build_xlate_map): use splay_tree_foreach to build map.
	(action_remove_bytes_fn): new function.
	(relax_section): use zero action_list_count instead of NULL
	action list. Use splay_tree_foreach to count final section size.
	Drop unused variable 'removed'.

0 files changed, 0 insertions, 0 deletions