change the location_t type, DECL_SOURCE_LINE etc

[Per Bothner <per at bothner dot com>]

I've been looking at the location_t type, which is used (primarily)
to represent the line-number of a tree_decl.  There are two problems
I'd like to address:
(1) Each location_t is 8 bytes (on 32-bit hosts) or 16 bytes (in
64-bit hosts).  This is a substantial amount of space when there
are many declarations.
(2) We don't store column numbers.

The following proposed change addresses both issues. It is somewhat
tentative, and I haven't finished the implementation.  However, I'd
like to explain the idea before I go much further.

To reduce space usage we have to replace the filename by an index
in a 'line_table'.  We also have to use bit fields in order to squeeze
everything into 32 bits.  This means a limited number of different
file names, and a limited range on line and column numbers.  However,
it is not quite a limited as the 14 and 8 suggest, since we can
have multiple 'line_table' entries for the same filename, but with
different line and column base values.  Thus:

/* The data structure used to record a location in a translation unit.  */
struct location_s GTY (())
{
  /* An index into line_table. */
  unsigned int file_index : 10;

  /* The source line, relative to line_table[file_index].line_base. */
  unsigned int rline : 14;

  /* The source column, relative to line_table[file_index].column_base. */
  unsigned int rcolumn : 8;
};
typedef struct location_s location_t;

#define LOCATION_FILE(LOCATION) (line_table[(LOCATION).file_index].file)
#define LOCATION_LINE(LOCATION) \
  (line_table[(LOCATION).file_index].line_base + (LOCATION).rline)
#define LOCATION_COLUMN(LOCATION) \
  (line_table[(LOCATION).file_index].column_base + (LOCATION).rcolumn)

struct line_table_entry
{
  /* The name of the source file for locations using this entry.  */
  const char *file;

  /* Value (normally 0) to add to rline for locations using this entry. */
  int line_base;

  /* Value (normally 0) to add to rcolumn for locations using this 
entry. */
  int column_base;

  /* Index of next element of line_table for file; -1 if none. */
  int next_entry;
};
struct line_table_entry line_table[1024] = {{NULL, 0, 0, -1}};

For simplicity this version uses a pre-allocated full-size line_table.
Since file_index is 10 bits, we can handle a maximum of 1024 entries,
I've used a statically allocated array.  This may not be a great
idea:  It uses 16kB of memory, which is trivial for large compilations,
but perhaps it is a bit wasteful.  (Also, the pre-allocation
of 'unknown_location_index' as line_table entry 0 forces the entire
table into data rather than bss; this is relatively easy to fix.)

The main function is 'get_location', which takes a file/line/column
triple and returns a location_t, finding a suitable 'line-table' entry.

/* Return a location_t for the given arguments. */

struct location_s
get_location (file, line, column)
     const char *file;
     int line;
     int column;
{
  struct location_s result;
  struct line_table_entry *entry = &line_table[most_recent_line_entry];
  if (ENTRY_MATCHES (entry, file, line, column))
    goto ok; /* Fast case. */
  else
    {
      /* Slow case - the most_recent_line_entry didn't match. */
      int next, step;
      int hash = PRIMARY_HASH (file);
      int start = hash & 1023;
      entry = &line_table[start];
      if (! (FILE_MATCHES (entry, file)))
	{
	  step = SEARCH_STEP (file, hash);
	  next = start;
	  for (;;)
	    {
	      if (ENTRY_AVAIL (entry))
		goto new;
	      next = (next + step) & 1023;
	      if (next == start)
		return get_nospace_location (file, line, column);
	      entry = &line_table[next];
	      if (FILE_MATCHES (entry, file))
		break;
	    }
	}
      /* At this point FILE_MATCH (entry, file) is true. */
      for (;;)
	{
	  if (LINE_COL_MATCHES (entry, line, column))
	    goto ok;
	  next = entry->next_entry;
	  if (next < 0) break;
	  entry = &line_table[next];
	}
      step = SEARCH_STEP (file, hash);
      next = start;
      for (;;)
	{
	  next = (next + step) & 1023;
	  if (ENTRY_AVAIL (&line_table[next]))
	    {
	      entry->next_entry = next;
	      entry = &line_table[next];
	      goto new;
	    }
	  if (next == start)
	    return get_nospace_location (file, line, column);
	}
    }
 new:
  entry->line_base = line & ~ LINE_MAX;
  entry->column_base = column & ~ COL_MAX;
  entry->next_entry = -1;
  entry->file = IDENTIFIER_POINTER (get_identifier (file));
 ok:
  most_recent_line_entry = entry - line_table;
  result.file_index = most_recent_line_entry;
  result.rline = line - entry->line_base;
  result.rcolumn = line - entry->column_base;
  return result;
}

It uses various (non-public) helper macros:

/* The index of the most recently uses line_table entry.  A cache. */
static int most_recent_line_entry;

#define LINE_MAX ((1<<14)-1)
#define COL_MAX ((1<<8)-1)

#define ENTRY_MATCHES(entry, file, line, column) \
  (FILE_MATCHES (entry, file) && LINE_COL_MATCHES (entry, line, column))
#define FILE_MATCHES(entry, file) \
  (entry->file == file \
   || (entry->file != NULL && file != NULL && strcmp (entry->file, 
file) == 0))
#define LINE_COL_MATCHES(entry, line, column) \
  (entry->line_base <= line && line - entry->line_base <= LINE_MAX \
   && entry->column_base <= column && column - entry->column_base <= 
COL_MAX)

#define ENTRY_AVAIL(entry) ((entry)->next_entry == 0)

There is a slight chance the line_table will fill up; the function
get_nospace_location sort-of handles this case, by using
the pre-allocated entry for "unknown location".

static int unknown_location_index = 0;

/* Emergency handling if line_table is full. */

static struct location_s
get_nospace_location (const char *file, int line, int column)
{
  static int emitted_too_many_files_warning;
  struct location_s result;
  if (! emitted_too_many_files_warning)
    {
      emitted_too_many_files_warning = 1;
      warning ("too many files or lines for line number information");
    }
  /* See if ignoring column number helps. */
  if (column < 0 || column > COL_MAX)
    return get_location (file, line, 0);
  result.file_index = unknown_location_index;
  result.rline = line >= 0 && line <= LINE_MAX ? line : 0;
  result.rcolumn = column;
  return result;
}

Then of course we need to modify these definitions in tree.h:

#define DECL_SOURCE_LOCATION(NODE) (DECL_CHECK (NODE)->decl.locus)
#define DECL_SOURCE_FILE(NODE) LOCATION_FILE ((DECL_SOURCE_LOCATION (NODE)))
#define DECL_SOURCE_LINE(NODE) LOCATION_LINE ((DECL_SOURCE_LOCATION (NODE)))
#define DECL_SOURCE_COLUMN(NODE) LOCATION_COLUMN ((DECL_SOURCE_LOCATION 
(NODE)))
#define SET_DECL_SOURCE_FILE_LINE(NODE, FILE, LINE) \
  (DECL_CHECK (NODE)->decl.locus = get_location (FILE, LINE, 0))
#define INPUT_LOCATION() get_location (input_filename, lineno, 0)

At which point it's just a tedious matter of fixing places in the source
that use DECL_SOURCE_FILE and DECL_SOURCE_LINE as lvalues ...  I've
mostly done that.

This patch does not change EXPR_WITH_FILE_LOCATION or the related
EXPR_WFL macros (which use an expression's complexity node).  I
haven't dealt with Java's DECL_SOURCE_LINE_FIRST and DECL_SOURCE_LINE_LAST.
It doesn't actually set the column numbers - that's up to each front-end.

Comments?  Is this a good idea?

--
	--Per Bothner
per@bothner.com   http://www.bothner.com/per/