[patch] Improve BFD line number table decoding

[Cary Coutant <ccoutant at google dot com>]

The attached patch reworks the way decode_line_info() in bfd/dwarf2.c
decodes the line table, in order to improve performance for large runs
of objdump -d -l or addr2line. For each compilation unit, instead of
using what was basically an insertion sort to enter the entire line
number table into one large linked list, it now forms individual line
sequences (each one a smaller linked list), and sorts the sequences
after the decoding is done, then uses a binary search to find the
right sequence before doing the linear traversal of the linked list.
(The DWARF spec imposes no ordering between one sequence and the next,
but it does impose a strict ordering of the address within a
sequence.) I left in the code that does an insertion sort within a
sequence just in case, but it shouldn't ever see out-of-order rows
within a sequence, so that code shouldn't run except when something is
broken in the compiler.

As far as performance goes, on x86_64, it seems to be pretty much a
wash for small disassembly runs and individual addr2line lookups,
where the overhead of sorting cancels out the improvement in lookup.
For larger runs, however -- especially with heavily optimized code
where the code can be wildly out of order -- it's noticeably faster.
(It was about 5x faster on programs compiled with -ffunction-sections
and linked with --gc-sections, where the compile_unit range list was
corrupted, but that was an anomaly, and I sent a gcc patch upstream to
fix that problem.)

-cary

	* dwarf2.c (struct line_sequence): New struct.
	(struct line_info_table): Add num_sequences, remove last_line,
	add sequences.
	(add_line_info): Add new sequences as necessary.
	(compare_sequences): New function.
	(sort_line_sequences): New function.
	(decode_line_info): Initialize new fields in line table.
	Call sort_line_sequences.
	(lookup_address_in_line_info_table): Binary search for proper
	sequence.

Attachment: bfd-line-table-sort-patch.txt
Description: Text document