[10/10] Compress short ranges into source_location

The attached patch implements a bit-packing scheme so that short ranges
can be stored directly within a 32-bit source_location (aka location_t)
without needing to use the ad-hoc table.  The intent is to mitigate the
overhead introduced in the earlier patch that added ranges for all tokens
in libcpp: every token up to 2**N characters long can be stored without
needing the ad-hoc table.  Other short ranges for expressions can be
stored compactly, provided that caret==start.

N currently is 5.  This is somewhat arbitrary, but seems to work.
The default bits for columns remains 7, meaning that the low 12 bits of
ordinary location_t values are for columns&packed ranges.
More details of the packing scheme can be seen in the patch's change
to line-map.h.

default_range_bits == 5 entails a 32-fold reduction in the size of the
code we can compile before the various fallbacks take effect (stopping
tracking columns then stopping tracking locations altogether).
In the former case, when we stop tracking columns, we also stop packing
ranges.

The range_bits needs to be per-ordinary_map, to cope with the case where
an ordinary map's range_and_column bits could be zero (e.g. due to a very
long line).
This requires figuring out which ordinary map a source_location is in
when generating compact ranges.  Luckily, this seems to hit the cached
map when tokenizing, avoiding the somewhat expensive binary search
through the ordinary maps.

Some benchmarks can be seen in this post:
  https://gcc.gnu.org/ml/gcc-patches/2015-10/msg02283.html

gcc/ada/ChangeLog:
	* gcc-interface/trans.c (Sloc_to_locus): Add line_table param when
	calling linemap_position_for_line_and_column.

gcc/ChangeLog:
	* input.c (dump_line_table_statistics): Dump stats on how many
	ranges were optimized vs how many needed ad-hoc table.
	(write_digit_row): Add "map" param; use its range_bits
	to calculate the per-character offset.
	(dump_location_info): Print the range and column bits for each
	ordinary map.  Use the range bits to calculate the per-character
	offset.  Pass the map as a new param to the various calls to
	write_digit_row.  Eliminate uses of
	ORDINARY_MAP_NUMBER_OF_COLUMN_BITS.
	* toplev.c (general_init): Initialize line_table's
	default_range_bits.
	* tree.c (get_pure_location): New function.
	(set_block): Use the pure form of the location for the
	caret in the combined location.
	(set_source_range): Likewise.

gcc/testsuite/ChangeLog:
	* gcc.dg/plugin/diagnostic_plugin_test_show_locus.c (get_loc): Add
	line_table param when calling
	linemap_position_for_line_and_column.
	* gcc.dg/plugin/diagnostic_plugin_test_tree_expression_range.c
	(emit_warning): Remove restriction that "loc" must be ad-hoc.

libcpp/ChangeLog:
	* include/line-map.h (source_location): Update the descriptive
	comment to reflect the packing scheme for short ranges.
	(struct line_map_ordinary): Drop field "column_bits" in favor
	of field "m_column_and_range_bits"; add field "m_range_bits".
	(ORDINARY_MAP_NUMBER_OF_COLUMN_BITS): Delete.
	(struct line_maps): Add fields "default_range_bits",
	"num_optimized_ranges" and "num_unoptimized_ranges".
	(get_range_from_adhoc_loc): Delete prototype.
	(get_range_from_loc): Convert from an inline function to a
	prototype.
	(pure_location_p): New prototype.
	(SOURCE_LINE): Update for renaming of column_bits.
	(SOURCE_COLUMN): Likewise.  Shift the column right by the map's
	range_bits.
	(LAST_SOURCE_LINE_LOCATION): Update for renaming of column_bits.
	(linemap_position_for_line_and_column): Add line_maps * params.
	* lex.c (_cpp_lex_direct): Don't attempt to record token ranges
	for UNKNOWN_LOCATION and BUILTINS_LOCATION.
	* line-map.c (LINE_MAP_MAX_COLUMN_NUMBER): Reduce from 1U << 17 to
	1U << 9.
	(can_be_stored_compactly_p): New function.
	(get_combined_adhoc_loc): Implement bit-packing scheme for short
	ranges.
	(get_range_from_adhoc_loc): Make static.
	(get_range_from_loc): New function.
	(pure_location_p): New function.
	(linemap_add): Ensure that start_location has zero for the
	range_bits, unless we're past LINE_MAP_MAX_LOCATION_WITH_COLS.
	Initialize range_bits to zero.  Assert that the start_location
	is "pure".
	(linemap_line_start): Assert that the
	column_and_range_bits >= range_bits.
	Update determinination of whether we need to start a new map
	using the effective column bits, without the range bits.
	Use the set's default_range_bits in new maps, apart from
	those with column_bits == 0, which should also have 0 range_bits.
	Increase the column bits for new maps by the range bits.
	When adding lines to an existing map, use set->highest_line
	directly rather than offsetting highest by SOURCE_COLUMN.
	Add assertions to sanity-check the return value.
	(linemap_position_for_column): Offset to_column by range_bits.
	Update set->hightest_location if necessary.
	(linemap_position_for_line_and_column): Add line_maps * param.
	Update the calculation to offset the column by range_bits, and
	conditionalize it on being <= LINE_MAP_MAX_LOCATION_WITH_COLS.
	Bound it by LINEMAPS_MACRO_LOWEST_LOCATION.  Update
	set->highest_location if necessary.
	(linemap_position_for_loc_and_offset): Pass "set" to
	linemap_position_for_line_and_column.
	* location-example.txt: Regenerate, showing new representation.
---
 gcc/ada/gcc-interface/trans.c                      |   3 +-
 gcc/input.c                                        |  28 ++-
 .../plugin/diagnostic_plugin_test_show_locus.c     |   3 +-
 .../diagnostic_plugin_test_tree_expression_range.c |   8 +-
 gcc/toplev.c                                       |   1 +
 gcc/tree.c                                         |  25 ++-
 libcpp/include/line-map.h                          | 121 +++++++----
 libcpp/lex.c                                       |   9 +-
 libcpp/line-map.c                                  | 229 +++++++++++++++++++--
 libcpp/location-example.txt                        | 188 +++++++++--------
 10 files changed, 450 insertions(+), 165 deletions(-)

[10/10] Compress short ranges into source_location

Commit Message

Comments

Patch