add splay tree for info_ptr -> CU mapping
While using perf top for MozillaThunderbird I noticed quite some slow
dissably call with source code involved. E.g.
time ./objdump --start-address=0x0000000004e0dcd0 --stop-address=0x0000000004e0df8b -l -d --no-show-raw-insn -S -C /usr/lib64/thunderbird/libxul.so
took 2.071s and I noticed quite some time is spent in
find_abstract_instance:
33.46% objdump objdump [.] find_abstract_instance
18.22% objdump objdump [.] arange_add
13.77% objdump objdump [.] read_attribute_value
4.82% objdump objdump [.] comp_unit_maybe_decode_line_info
3.10% objdump libc.so.6 [.] __memset_avx2_unaligned_erms
where linked list of CU is iterated when searing for where info_ptr
belongs to:
: 3452 for (u = unit->prev_unit; u != NULL; u = u->prev_unit)
0.00 : 4c61f7: mov 0x10(%rbx),%rax
0.00 : 4c61fb: test %rax,%rax
0.00 : 4c61fe: je 4c6215 <find_abstract_instance+0x365>
: 3453 if (info_ptr >= u->info_ptr_unit && info_ptr < u->end_ptr)
0.00 : 4c6200: cmp 0x60(%rax),%rdx
83.20 : 4c6204: jb 4c620c <find_abstract_instance+0x35c>
0.00 : 4c6206: cmp 0x78(%rax),%rdx
6.89 : 4c620a: jb 4c6270 <find_abstract_instance+0x3c0>
: 3452 for (u = unit->prev_unit; u != NULL; u = u->prev_unit)
0.00 : 4c620c: mov 0x10(%rax),%rax
7.90 : 4c6210: test %rax,%rax
0.00 : 4c6213: jne 4c6200 <find_abstract_instance+0x350>
The following scan can be replaced with search in a splay tree and with
that I can get to 1.5s and there are other symbols where the difference
is even bigger.
bfd/ChangeLog:
PR 29081
* dwarf2.c (struct addr_range): New.
(addr_range_intersects): Likewise.
(splay_tree_compare_addr_range): Likewise.
(splay_tree_free_addr_range): Likewise.
(struct dwarf2_debug_file): Add comp_unit_tree.
(find_abstract_instance): Use the splay tree when searching
for a info_ptr.
(stash_comp_unit): Insert to the splay tree.
(_bfd_dwarf2_cleanup_debug_info): Clean up the splay tree.