Fix line-maps wrt LTO

[Jack Howarth]

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;