[Bug lto/65536] LTO line number information garbled

["manu at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="UTF-8", Size: 14914 bytes --]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65536

--- Comment #49 from Manuel López-Ibáñez <manu at gcc dot gnu.org> ---
(In reply to Jan Hubicka from comment #46)
> Manuel,
> I will hopefully commit the cache patch today or tomorrow morning. It does
> not solve full issue. What we have is
> 1) we still drop columns for firefox&chromium pretty early

I think the current limits are too conservative. In particular, the limit in
linemap_position_for_column does not make sense to me. I would suggest trying
something like:

Index: line-map.c
===================================================================
--- line-map.c  (revision 221728)
+++ line-map.c  (working copy)
@@ -24,10 +24,22 @@ along with this program; see the file CO
 #include "line-map.h"
 #include "cpplib.h"
 #include "internal.h"
 #include "hashtab.h"

+/* Do not track column numbers higher than this one.  As a result, the
+   range of column_bits is [7, 18] (or 0 if column numbers are
+   disabled).  */
+#define LINE_MAP_MAX_COLUMN_NUMBER (1U << 17)
+
+/* Do not track column numbers if locations get higher than this.  */
+#define LINE_MAP_MAX_LOCATION_WITH_COLS 0x70000000
+
+/* Highest possible source location encoded within an ordinary or
+   macro map.  */
+#define LINE_MAP_MAX_SOURCE_LOCATION 0x7FFFFFF0
+
 static void trace_include (const struct line_maps *, const struct line_map *);
 static const struct line_map * linemap_ordinary_map_lookup (struct line_maps
*,
                                                            source_location);
 static const struct line_map* linemap_macro_map_lookup (struct line_maps *,
                                                        source_location);
@@ -528,26 +543,28 @@ linemap_line_start (struct line_maps *se
       || (line_delta > 10
          && line_delta * ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) > 1000)
       || (max_column_hint >= (1U << ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map)))
       || (max_column_hint <= 80
          && ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) >= 10)
-      || (highest > 0x60000000
-         && (set->max_column_hint || highest > 0x70000000)))
+      || (highest > LINE_MAP_MAX_LOCATION_WITH_COLS
+         && (set->max_column_hint || highest >=
LINE_MAP_MAX_SOURCE_LOCATION)))
     add_map = true;
   else
     max_column_hint = set->max_column_hint;
   if (add_map)
     {
       int column_bits;
-      if (max_column_hint > 100000 || highest > 0x60000000)
+      if (max_column_hint > LINE_MAP_MAX_COLUMN_NUMBER
+         || highest > LINE_MAP_MAX_LOCATION_WITH_COLS)
        {
          /* If the column number is ridiculous or we've allocated a huge
             number of source_locations, give up on column numbers. */
          max_column_hint = 0;
-         if (highest > 0x70000000)
-           return 0;
          column_bits = 0;
+
+         if (set->highest_location >= LINEMAPS_MACRO_LOWEST_LOCATION (set) -
1)
+           return 0;
        }
       else
        {
          column_bits = 7;
          while (max_column_hint >= (1U << column_bits))
@@ -598,19 +628,25 @@ linemap_position_for_column (struct line
   linemap_assert
     (!linemap_macro_expansion_map_p (LINEMAPS_LAST_ORDINARY_MAP (set)));

   if (to_column >= set->max_column_hint)
     {
-      if (r >= 0xC000000 || to_column > 100000)
+      if (r > LINE_MAP_MAX_LOCATION_WITH_COLS
+         || to_column > LINE_MAP_MAX_COLUMN_NUMBER)
        {
          /* Running low on source_locations - disable column numbers.  */
+         if (r >= LINEMAPS_MACRO_LOWEST_LOCATION (set) - 1)
+           return 0;
          return r;
        }
       else
        {
          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;
   if (r >= set->highest_location)
     set->highest_location = r;


Unfortunately, I cannot get a pristine lto-boostrap to succeed, it fails with:

/home/manuel/test1/221728/build/./prev-gcc/xg++
-B/home/manuel/test1/221728/build/./prev-gcc/
-B/home/manuel/test1/./221728/install/x86_64-unknown-linux-gnu/bin/ -nostdinc++
-B/home/manuel/test1/221728/build/prev-x86_64-unknown-linux-gnu/libstdc++-v3/src/.libs
-B/home/manuel/test1/221728/build/prev-x86_64-unknown-linux-gnu/libstdc++-v3/libsupc++/.libs

-I/home/manuel/test1/221728/build/prev-x86_64-unknown-linux-gnu/libstdc++-v3/include/x86_64-unknown-linux-gnu

-I/home/manuel/test1/221728/build/prev-x86_64-unknown-linux-gnu/libstdc++-v3/include
 -I/home/manuel/test1/pristine/libstdc++-v3/libsupc++
-L/home/manuel/test1/221728/build/prev-x86_64-unknown-linux-gnu/libstdc++-v3/src/.libs
-L/home/manuel/test1/221728/build/prev-x86_64-unknown-linux-gnu/libstdc++-v3/libsupc++/.libs
  -g -O2 -flto=jobserver -frandom-seed=1 -DIN_GCC    -fno-exceptions -fno-rtti
-fasynchronous-unwind-tables -W -Wall -Wno-narrowing -Wwrite-strings
-Wcast-qual -Wmissing-format-attribute -Woverloaded-virtual -pedantic
-Wno-long-long -Wno-variadic-macros -Wno-overlength-strings -Werror -fno-common
 -DHAVE_CONFIG_H -static-libstdc++ -static-libgcc  -o cc1 c/c-lang.o
c-family/stub-objc.o attribs.o c/c-errors.o c/c-decl.o c/c-typeck.o
c/c-convert.o c/c-aux-info.o c/c-objc-common.o c/c-parser.o
c/c-array-notation.o c-family/c-common.o c-family/c-cppbuiltin.o
c-family/c-dump.o c-family/c-format.o c-family/c-gimplify.o c-family/c-lex.o
c-family/c-omp.o c-family/c-opts.o c-family/c-pch.o c-family/c-ppoutput.o
c-family/c-pragma.o c-family/c-pretty-print.o c-family/c-semantics.o
c-family/c-ada-spec.o c-family/c-cilkplus.o c-family/array-notation-common.o
c-family/cilk.o c-family/c-ubsan.o i386-c.o glibc-c.o \
          cc1-checksum.o libbackend.a main.o tree-browser.o libcommon-target.a
libcommon.a ../libcpp/libcpp.a ../libdecnumber/libdecnumber.a libcommon.a
../libcpp/libcpp.a   ../libbacktrace/.libs/libbacktrace.a
../libiberty/libiberty.a ../libdecnumber/libdecnumber.a 
-L/opt/cfarm/isl-0.12.2/lib -lisl -L/opt/cfarm/gmp-4.3.2/lib
-L/opt/cfarm/mpfr-2.4.2/lib -L/opt/cfarm/mpc-0.8.1/lib -lmpc -lmpfr -lgmp
-rdynamic -ldl  -L../zlib -lz
/home/manuel/test1/pristine/gcc/c/c-lang.h:26:16: error: type ‘struct
lang_type’ violates one definition rule [-Werror=odr]
 struct GTY(()) lang_type {
                ^
/home/manuel/test1/pristine/gcc/cp/cp-tree.h:1566:16: note: a different type is
defined in another translation unit
 struct GTY(()) lang_type {
                ^
/home/manuel/test1/pristine/gcc/c/c-lang.h:28:72: note: the first difference of
corresponding definitions is field ‘s’
   struct sorted_fields_type * GTY ((reorder ("resort_sorted_fields"))) s;
                                                                        ^
/home/manuel/test1/pristine/gcc/cp/cp-tree.h:1572:45: note: a field with
different name is defined in another translation unit
   } GTY((desc ("%h.h.is_lang_type_class"))) u;
                                             ^

> 2) there is a bug that we sometimes output wrong line number.  I think it is
> caused by the logic reallocating ORDINARY_MAP_NUMBER_OF_COLUMN_BITS as
> described in original email.

Maybe but I do not see it yet. My guess is that it is caused either by
overflowing start_location in linemap_add, or when computing 'r' 
linemap_position_for_column after linemap_line_start starts returning 0 or
after column_hint has been truncated (your patch fixes this), or when the
computation of 'r' overflows in linemap_line_start. Any of those cases will
trigger a silent overflow and return a location for something else.

Contrary to what I said before, I think now that it really makes sense for
line-maps to return UNKNOWN_LOCATION rather than the location of something else
when overflow occurs, but then LTO has to detect this case and decide what to
do.

> > My guess is that the motivation here is that, if there is a large gap, it means that we didn't get asked any source_location since a lot of lines ago. thus it would save a lot of source_locations to simply start a new map now. Of course, this does not work for out-of-order, but why should we pessimize typical usage for something that should be fixed in LTO?
> 
> I do not think typical usage is pesimized here. Yes, code is trying to avoid
> case where we skip too many location indexes because we entered lines 1...30
> and now we want to insert line 1000. We do not want to fast forward by
> 970*80.

Yes, we want to. Because then set->highest_location goes up just by one and the
next map starts from that, thus we do not need to consume source_locations for
those 970*80 entries which will never be addressed (we jump directly from 30:80
to 1000:1).

> > > 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.
> >
> > If you insert a line out of order without creating a new map, then
> > linemap_position_for_column will return the wrong value.
> 
> I do not see why. If we insert first line 1 (80 columns), then we create a
> map 1.  Now we insert line 3, we do not create new map, but we offset
> highest_line by 80*2.  Now if we start line 2, all we need is to offset
> highest_line by -80 and linemap_position_for_column will still work well.

But then you do not know which is the source_location of the highest line
encoded in the line_table, which is used in several places. I'm not saying it
is not worth it or possible, but it is not as trivial as just offsetting
highest_line (and then, it should not be called highest_line but perhaps
last_line_location).

Note that I'm not discussing all this to be negative. I'm very much in favour
of supporting some kind of out-of-order insertion (in particular for PR52952),
but we should be careful to not pessimize the in-order case and we should get
all the details right. The line-maps are tricky and getting the details wrong
could be disaster.
>From gcc-bugs-return-482040-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Fri Mar 27 15:26:12 2015
Return-Path: <gcc-bugs-return-482040-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 4439 invoked by alias); 27 Mar 2015 15:26:12 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 4228 invoked by uid 48); 27 Mar 2015 15:26:08 -0000
From: "manu at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug web/65601] add bugzilla keyword "easyhack"
Date: Fri, 27 Mar 2015 15:47:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: web
X-Bugzilla-Version: unknown
X-Bugzilla-Keywords:
X-Bugzilla-Severity: enhancement
X-Bugzilla-Who: manu at gcc dot gnu.org
X-Bugzilla-Status: RESOLVED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_status resolution
Message-ID: <bug-65601-4-5DhJvcHITq@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-65601-4@http.gcc.gnu.org/bugzilla/>
References: <bug-65601-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-03/txt/msg03184.txt.bz2
Content-length: 604

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65601

Manuel López-Ibáñez <manu at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |FIXED

--- Comment #2 from Manuel López-Ibáñez <manu at gcc dot gnu.org> ---
(In reply to Andreas Schwab from comment #1)
> https://gcc.gnu.org/bugzilla/editkeywords.cgi?action=add

Ops, I missed that completely. Thanks!
>From gcc-bugs-return-482042-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Fri Mar 27 15:41:49 2015
Return-Path: <gcc-bugs-return-482042-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 74712 invoked by alias); 27 Mar 2015 15:41:49 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 74662 invoked by uid 48); 27 Mar 2015 15:41:42 -0000
From: "vries at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/65511] transform_to_exit_first_loop looses edge probabilities
Date: Fri, 27 Mar 2015 15:49:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: trivial
X-Bugzilla-Who: vries at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: attachments.created
Message-ID: <bug-65511-4-YQXcIXxu76@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-65511-4@http.gcc.gnu.org/bugzilla/>
References: <bug-65511-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-03/txt/msg03186.txt.bz2
Content-length: 238

https://gcc.gnu.org/bugzilla/show_bug.cgi?ide511

--- Comment #4 from vries at gcc dot gnu.org ---
Created attachment 35164
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id5164&actioníit
patch with test-case, currently testing