Fix line-maps wrt LTO

Hi,
I read linemap_line_start and I think I noticed few issues with respect
to overflows and lines being added randomly.

1) line_delta is computed as to_line SOURCE_LINE (map, set->highest_line)
   I think the last inserted line is not very releavnt.  What we care about is
   the base of the last location and to keep thing dense how much we are
   stretching the value range from highest inserted element (inserting into middle
   is cheap).

   For this reason I added base_line_delta and changed line_delta to be
   to_line - SOURCE_LINE (map, set->highest_location).

   Because things go in randomly, highest_line, which really is last inserted
   line, may be somewhere in between.
2) (line_delta > 10 && line_delta * ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) > 1000)
   ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) is in range 7... 15, so it never
   gets high enough to make this conditional trigger.  I changed it to:

      || line_delta > 1000
      || (line_delta << ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map)) > 1000

   I.e. we do not want to skip more than 1000 unused entries since highest
   inserted location.

3) (max_column_hint <= 80 && ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) >= 10)
   seems to intend to reduce the column range when it is no longer needed.
   Again, this is not really good idea when line inserted is not last.

4) the code deciding whether to do reuse seems worng:
      if (line_delta < 0
	  || last_line != ORDINARY_MAP_STARTING_LINE_NUMBER (map)
	  || SOURCE_COLUMN (map, highest) >= (1U << column_bits))

   line_delta really should be base_line_delta, we do not need to give up
   when map's line is 1, SOURCE_LINE (map, set->highest_line) is 5
   and we are requested to switch to line 3.

   Second last_line != ORDINARY_MAP_STARTING_LINE_NUMBER (map) tests whether
   location has only one line that does not work (at least with my changes)
   because we may switch to next line and back.

   This conditoinal also seems to be completely missing hanlding of overflows.

The following patch makes all line info and all but one carret to to be right
on chromium warnings

Bootstrapped/regtested x86_64-linux, OK?

	* line-map.c (linemap_line_start): Correct overflow tests.

Jan,
     It appears that
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61250 is due to a problem
in linemap_macro_map_lookup. It is hard to debug as the pch test
harness doesn't produce a simple logged compile failure to re-execute
but I can look at it from a core file in gdb. Unfortunately your
proposed patch doesn't eliminate PR61250 but I am wondering if it is
another related corner case with the linemaps overflows.
              Jack

On Wed, Mar 25, 2015 at 8:56 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> I read linemap_line_start and I think I noticed few issues with respect
> to overflows and lines being added randomly.
>
> 1) line_delta is computed as to_line SOURCE_LINE (map, set->highest_line)
>    I think the last inserted line is not very releavnt.  What we care about is
>    the base of the last location and to keep thing dense how much we are
>    stretching the value range from highest inserted element (inserting into middle
>    is cheap).
>
>    For this reason I added base_line_delta and changed line_delta to be
>    to_line - SOURCE_LINE (map, set->highest_location).
>
>    Because things go in randomly, highest_line, which really is last inserted
>    line, may be somewhere in between.
> 2) (line_delta > 10 && line_delta * ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) > 1000)
>    ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) is in range 7... 15, so it never
>    gets high enough to make this conditional trigger.  I changed it to:
>
>       || line_delta > 1000
>       || (line_delta << ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map)) > 1000
>
>    I.e. we do not want to skip more than 1000 unused entries since highest
>    inserted location.
>
> 3) (max_column_hint <= 80 && ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) >= 10)
>    seems to intend to reduce the column range when it is no longer needed.
>    Again, this is not really good idea when line inserted is not last.
>
> 4) the code deciding whether to do reuse seems worng:
>       if (line_delta < 0
>           || last_line != ORDINARY_MAP_STARTING_LINE_NUMBER (map)
>           || SOURCE_COLUMN (map, highest) >= (1U << column_bits))
>
>    line_delta really should be base_line_delta, we do not need to give up
>    when map's line is 1, SOURCE_LINE (map, set->highest_line) is 5
>    and we are requested to switch to line 3.
>
>    Second last_line != ORDINARY_MAP_STARTING_LINE_NUMBER (map) tests whether
>    location has only one line that does not work (at least with my changes)
>    because we may switch to next line and back.
>
>    This conditoinal also seems to be completely missing hanlding of overflows.
>
> The following patch makes all line info and all but one carret to to be right
> on chromium warnings
>
> Bootstrapped/regtested x86_64-linux, OK?
>
>         * line-map.c (linemap_line_start): Correct overflow tests.
> Index: line-map.c
> ===================================================================
> --- line-map.c  (revision 221568)
> +++ line-map.c  (working copy)
> @@ -519,25 +519,38 @@ linemap_line_start (struct line_maps *se
>    struct line_map *map = LINEMAPS_LAST_ORDINARY_MAP (set);
>    source_location highest = set->highest_location;
>    source_location r;
> -  linenum_type last_line =
> -    SOURCE_LINE (map, set->highest_line);
> -  int line_delta = to_line - last_line;
> +  int base_line_delta = to_line - ORDINARY_MAP_STARTING_LINE_NUMBER (map);
> +  int line_delta = to_line - SOURCE_LINE (map, set->highest_location);
>    bool add_map = false;
>
> -  if (line_delta < 0
> -      || (line_delta > 10
> -         && line_delta * ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) > 1000)
> -      || (max_column_hint >= (1U << ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map)))
> +  /* Single MAP entry can be used to encode multiple source lines.
> +     Look for situations when this is impossible or undesriable.  */
> +  if (base_line_delta < 0
> +      /* We want to keep maps resonably dense, so do not increase the range
> +        of this linemap entry by more than 1000.  */
> +      || line_delta > 1000
> +      || (line_delta << ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map)) > 1000
> +      /* If the max column is out of range and we are still not dropping line
> +        info.  */
> +      || (max_column_hint >= (1U << ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map))
> +         && highest < 0x60000000)
> +      /* If the prevoius line was long.  Ignore this problem is we already
> +        re-used the map for lines with greater indexes.  */
>        || (max_column_hint <= 80
> -         && ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) >= 10)
> +         && ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) >= 10 && line_delta > 0)
> +      /* If we are just started running out of locations (which makes us to drop
> +        column info), but current line map still has column info, create fresh
> +        one.  */
>        || (highest > 0x60000000
> -         && (set->max_column_hint || highest > 0x70000000)))
> +         && (ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map)
> +             || highest > 0x70000000)))
>      add_map = true;
>    else
>      max_column_hint = set->max_column_hint;
>    if (add_map)
>      {
>        int column_bits;
> +      bool reuse_map = true;
>        if (max_column_hint > 100000 || highest > 0x60000000)
>         {
>           /* If the column number is ridiculous or we've allocated a huge
> @@ -554,11 +567,38 @@ linemap_line_start (struct line_maps *se
>             column_bits++;
>           max_column_hint = 1U << column_bits;
>         }
> +
>        /* Allocate the new line_map.  However, if the current map only has a
>          single line we can sometimes just increase its column_bits instead. */
> -      if (line_delta < 0
> -         || last_line != ORDINARY_MAP_STARTING_LINE_NUMBER (map)
> -         || SOURCE_COLUMN (map, highest) >= (1U << column_bits))
> +      if (base_line_delta < 0 || base_line_delta != line_delta
> +         /* If we just started running out of locators, but current map still
> +            has column info, do not reuse it.  */
> +          || (highest > 0x60000000
> +             && ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map)
> +             && base_line_delta)
> +         /* If the line delta is too large.  */
> +         || line_delta > 1000)
> +       reuse_map = false;
> +
> +      /* When reusing, we must be sure that column_bits is high enough
> +        for already recorded locations.  */
> +      if (reuse_map)
> +       {
> +         unsigned int max_column = SOURCE_COLUMN (map, highest) + 1;
> +         int combined_column_bits = column_bits;
> +
> +         while (max_column >= (1U << combined_column_bits))
> +           combined_column_bits++;
> +
> +         if ((line_delta << combined_column_bits) > 1000)
> +           reuse_map = false;
> +         else
> +           {
> +             column_bits = combined_column_bits;
> +             max_column_hint = 1U << combined_column_bits;
> +           }
> +       }
> +      if (!reuse_map)
>         map = (struct line_map *) linemap_add (set, LC_RENAME,
>                                                ORDINARY_MAP_IN_SYSTEM_HEADER_P
>                                                (map),
> @@ -609,6 +649,9 @@ linemap_position_for_column (struct line
>         {
>           struct line_map *map = LINEMAPS_LAST_ORDINARY_MAP (set);
>           r = linemap_line_start (set, SOURCE_LINE (map, r), to_column + 50);
> +         /* We just got to overflow; disable column numbers.  */
> +         if (to_column >= set->max_column_hint)
> +           return r;
>         }
>      }
>    r = r + to_column;