On Linux/x86-64, revision 167173 gave libtool: compile: /export/gnu/import/svn/gcc-test-profile/bld/./gcc/gcj -B/export/gnu/import/svn/gcc-test-profile/bld/x86_64-unknown-linux-gnu/32/libjava/ -B/export/gnu/import/svn/gcc-test-profile/bld/x86_64-unknown-linux-gnu/32/libjava/ -B/export/gnu/import/svn/gcc-test-profile/bld/./gcc/ -B/usr/local/x86_64-unknown-linux-gnu/bin/ -B/usr/local/x86_64-unknown-linux-gnu/lib/ -isystem /usr/local/x86_64-unknown-linux-gnu/include -isystem /usr/local/x86_64-unknown-linux-gnu/sys-include -m32 -ffloat-store -fomit-frame-pointer -fclasspath= -fbootclasspath=../../../../src-trunk/libjava/classpath/lib --encoding=UTF-8 -Wno-deprecated -fbootstrap-classes -g -O2 -m32 -fsource-filename=/export/gnu/import/svn/gcc-test-profile/bld/x86_64-unknown-linux-gnu/32/libjava/classpath/lib/classes -fjni -findirect-dispatch -fno-indirect-classes -c @gnu-java-awt-dnd-peer-gtk.list -o gnu-java-awt-dnd-peer-gtk.o >/dev/null 2>&1 /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkComponentPeer.java: In class 'gnu.java.awt.peer.gtk.GtkComponentPeer': /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkComponentPeer.java: In method 'gnu.java.awt.peer.gtk.GtkComponentPeer.handleEvent(java.awt.AWTEvent)': In file included from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GdkPixbufDecoder.java:260:0, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkComponentPeer.java:457, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkMenuBarPeer.java:112, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkPopupMenuPeer.java:67, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkTextFieldPeer.java:198, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkMouseInfoPeer.java:63, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/AsyncImage.java:281, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkChoicePeer.java:141, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkWindowPeer.java:436, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkMenuPeer.java:125, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkMenuItemPeer.java:115, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkClipboard.java:423, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GdkScreenGraphicsDevice.java:357, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GdkScreenGraphicsDevice.java:284, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkContainerPeer.java:137, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/ComponentGraphics.java:940, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkLabelPeer.java:100, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GdkGraphicsEnvironment.java:170, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GdkPixbufDecoder.java:404, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkListPeer.java:186, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkSelection.java:656, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkCanvasPeer.java:58, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkGenericPeer.java:144, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GdkRobotPeer.java:98, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/FreetypeGlyphVector.java:629, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/CairoSurfaceGraphics.java:353, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/ComponentGraphicsCopy.java:121, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GdkPixbufDecoder.java:782, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkImageConsumer.java:168, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GdkGraphicsConfiguration.java:153, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkFramePeer.java:251, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkMenuComponentPeer.java:103, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/BufferedImageGraphics.java:536, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkVolatileImage.java:203, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkTextAreaPeer.java:221, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkEmbeddedWindowPeer.java:72, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkMainThread.java:187, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkScrollbarPeer.java:91, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/CairoGraphics2D.java:2174, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GdkPixbufDecoder.java:627, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/CairoSurface.java:424, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkCheckboxPeer.java:254, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkToolkit.java:342, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkScrollPanePeer.java:110, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GdkFontPeer.java:465, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GdkFontPeer.java:543, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkButtonPeer.java:92, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/AsyncImage.java:135, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GdkFontPeer.java:138, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkCheckboxMenuItemPeer.java:73, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkCursor.java:70, from /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkFileDialogPeer.java:228, from <built-in>:63: /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkComponentPeer.java:279:0: error: verification failed at PC=8: branch out of range /export/gnu/import/svn/gcc-test-profile/src-trunk/libjava/classpath/gnu/java/awt/peer/gtk/GtkComponentPeer.java:279:0: internal compiler error: Segmentation fault Please submit a full bug report, with preprocessed source if appropriate. See <http://gcc.gnu.org/bugs.html> for instructions. make[8]: *** [gnu-java-awt-peer-gtk.lo] Error 1
Continuing from [1]: >> Any info what this verification error means? > > Either > > a. A file (GtkComponentPeer.class) has been corrupted > > or > > b. verify-* in gcc/java has been miscompiled by gcc. > > or > > c. something used by verify-* in gcc/java has changed, and now > verify-* is broken. Right on spot, It is verify_instructions_0 from verify-impl.c that is miscompiled. Following patch avoids these failures and enables profiledbootstrap to finish: Index: gcc/java/verify-impl.c =================================================================== --- gcc/java/verify-impl.c (revision 167188) +++ gcc/java/verify-impl.c (working copy) @@ -2211,6 +2211,7 @@ initialize_stack (void) } static void +__attribute__((__optimize__(1))) verify_instructions_0 (void) { int i; [1] http://gcc.gnu.org/ml/gcc/2010-11/msg00615.html
The loop in following part of verify_instructions_0 is miscompiled: ----cut here---- case op_lookupswitch: { int i; jint npairs, lastkey; pop_type (int_type); skip_padding (); push_jump (get_int (), 7); npairs = get_int (); /* Already checked NPAIRS >= 0. */ lastkey = 0; for (i = 0; i < npairs; ++i) { jint key = get_int (); if (i > 0 && key <= lastkey) verify_fail_pc ("lookupswitch pairs unsorted", vfr->start_PC); lastkey = key; push_jump (get_int (), 8); } invalidate_pc (); } break; ----cut here---- The count variable (i) does not increase and stays at zero.
Created attachment 22545 [details] preprocessed file The problem is in -fprofile-use. Corresponding .gcda file is not needed to trigger the problem, so: ~/gcc-build/prev-gcc/cc1 -O2 verify-impl.i produces correct object file, while ~/gcc-build/prev-gcc/cc1 -O2 -fprofile-use verify-impl.i produces wrong object file (please note that execution counts are estimated). You can conveniently grep for "printf" in the dumps, since I have left a debugging printf in the loop: for (i = 0; i < npairs; ++i) { jint key = get_int (); if (i > 0 && key <= lastkey) verify_fail_pc ("lookupswitch pairs unsorted", vfr->start_PC); lastkey = key; push_jump (get_int ()); printf ("i = %i\n", i); } While the _.optimized dump without -fprofile-use has similar structure to the original source: --cut here-- <bb 164>: key_215 = get_int (); D.21282_216 = i_224 > 0; D.21283_217 = key_1 >= key_215; D.21284_218 = D.21283_217 & D.21282_216; if (D.21284_218 != 0) goto <bb 165>; else goto <bb 166>; <bb 165>: vfr.14_219 = vfr; D.21287_220 = vfr.14_219->start_PC; verify_fail_pc ("lookupswitch pairs unsorted", D.21287_220); <bb 166>: <bb 167>: # key_1 = PHI <key_215(166), key_1193(291)> # i_1121 = PHI <i_224(166), 0(291)> D.21288_222 = get_int (); push_jump (D.21288_222); printf (&"i = %i\n"[0], i_1121); i_224 = i_1121 + 1; if (i_224 != npairs_212) goto <bb 164>; else goto <bb 168>; <bb 168>: prephitmp.551_882 = vfr; prephitmp.551_882->PC = -1; goto <bb 21>; <L228>: D.21290 = vfy_pop_type (10); [return slot optimization] check_return_type (D.21290); prephitmp.551_883 = vfr; prephitmp.551_883->PC = -1; goto <bb 21>; --cut here-- And using -fprofile-use, it looks somehow strange: --cut here-- <bb 309>: # prephitmp.1170_3787 = PHI <prephitmp.1170_3781(307), prephitmp.1170_3786(308)> D.25872_2132 = prephitmp.1170_3787->current_state; merge_into (npc_2135, D.25872_2132); printf (&"i = %i\n"[0], 0); if (npairs_1969 > 1) goto <bb 290>; else goto <bb 310>; <bb 310>: prephitmp.1288_882 = vfr; prephitmp.1288_882->PC = -1; goto <bb 12>; --cut here-- And sure enough, npairs_1969 is nowhere incremented.
It is vrp2 pass that miscompiles attached preprocessed file. gcc-build/gcc/cc1 -O2 -fprofile-use ************* _.122t.reassoc2: --cut here-- <bb 291>: # i_1950 = PHI <i_224(312), 0(290)> # lastkey_1951 = PHI <key_1983(312), 0(290)> vfr.11_1984 = vfr; D.25742_1985 = vfr.11_1984->PC; D.25743_1987 = vfr.11_1984->current_method; D.25744_1988 = D.25743_1987->code_length; if (D.25742_1985 >= D.25744_1988) goto <bb 292>; else goto <bb 293>; ... <bb 312>: # prephitmp.1242_3787 = PHI <prephitmp.1236_3781(310), pretmp.1241_3786(311)> D.25872_2132 = prephitmp.1242_3787->current_state; merge_into (npc_2135, D.25872_2132); printf (&"i = %i\n"[0], i_1950); i_224 = i_1950 + 1; if (i_224 < npairs_1969) goto <bb 291>; else goto <bb 313>; <bb 313>: <bb 314>: vfr.56_882 = vfr; vfr.56_882->PC = -1; goto <bb 14> (<L386>); --cut here-- ************* _.123t.vrp: --cut here-- <bb 295>: # lastkey_1951 = PHI <0(294), key_1983(315)> i_1950 = 0; vfr.11_1984 = vfr; D.25742_1985 = vfr.11_1984->PC; D.25743_1987 = vfr.11_1984->current_method; D.25744_1988 = D.25743_1987->code_length; if (D.25742_1985 >= D.25744_1988) goto <bb 296>; else goto <bb 297>; ... <bb 315>: # prephitmp.1242_3787 = PHI <prephitmp.1236_3781(313), pretmp.1241_3786(314)> D.25872_2132 = prephitmp.1242_3787->current_state; merge_into (npc_2135, D.25872_2132); printf (&"i = %i\n"[0], 0); i_224 = 1; if (npairs_1969 > 1) goto <bb 295>; else goto <bb 316>; <bb 316>: --cut here-- See how i_1950 in _.123t.vrp dump gets assigned to zero and consequently i_224 to one.
To prove my claims, following change brings gcc back to profiledbootstrap land: Index: gcc/java/verify-impl.c =================================================================== --- gcc/java/verify-impl.c (revision 167188) +++ gcc/java/verify-impl.c (working copy) @@ -2211,6 +2211,7 @@ initialize_stack (void) } static void +__attribute__((__optimize__("no-tree-vrp"))) verify_instructions_0 (void) { int i;
You don't by chance have a standalone testcase yet? ;) Can you attach reassoc and vrp -details dumps with -fprofile-use?
Created attachment 22547 [details] _.122t.reassoc2 and _.123t.vrp2 detailed dumps
(In reply to comment #6) > You don't by chance have a standalone testcase yet? ;) Unfortunately, I was not able to create testcase - the function is a huge switch, but you don't need to use profiled gcc to trigger the problem. > Can you attach reassoc and vrp -details dumps with -fprofile-use? Done. Simply grep for printf, it is the only one.
The bug seems to be: Visiting PHI node: i_1950 = PHI <i_1028(291), i_224(510)> Argument #0 (291 -> 503 executable) i_1028 Value: [0, 0] Argument #1 (510 -> 503 executable) i_224 Value: [1, 2] (analyze_scalar_evolution (loop_nb = 16) (scalar = i_1950) (get_scalar_evolution (scalar = i_1950) (scalar_evolution = {0, +, 1}_16)) (set_scalar_evolution instantiated_below = 291 (scalar = i_1950) (scalar_evolution = {0, +, 1}_16)) ) (instantiate_scev (instantiate_below = 291) (evolution_loop = 16) (chrec = {0, +, 1}_16) (res = {0, +, 1}_16)) i_1950: loop information indicates does not overflow (analyze_scalar_evolution (loop_nb = 16) (scalar = i_1950) (get_scalar_evolution (scalar = i_1950) (scalar_evolution = {0, +, 1}_16)) (set_scalar_evolution instantiated_below = 291 (scalar = i_1950) (scalar_evolution = {0, +, 1}_16)) ) (instantiate_scev (instantiate_below = 291) (evolution_loop = 16) (chrec = {0, +, 1}_16) (res = {0, +, 1}_16)) Found new range for i_1950: [0, 0] while the previous range was i_1950: [0, 1] This means that number of iteration analysis has gone wrong. Analyzing # of iterations of loop 16 exit condition [1, + , 1](no_overflow) < n_1968 - -2147483648 bounds on difference of bases: 0 ... -2 result: # of iterations (unsigned int) n_1968 + 2147483647, bounded by 0 Statement (exit)if (i_224 < npairs_1969) is executed at most (unsigned int) n_1968 + 2147483647 (bounded by 0) + 1 times in loop 16. the "bounded by 0" is why things go wrong. The original statement defining the exit condition bound is npairs_1969 = n_1968 - -2147483648; Testcase: volatile int j; int __attribute__((noinline)) foo(int n) { int i = 0, npairs; npairs = n - (- __INT_MAX__ - 1); if (npairs > 0) { do { ++j; i = i + 1; } while (i < npairs); } return 0; } extern void abort (void); int main() { j = 0; foo (- __INT_MAX__ - 1 + 5); if (j != 5) abort (); return 0; } is optimized to an endless loop by the first VRP pass.
With the testcase we again see Analyzing # of iterations of loop 1 exit condition [1, + , 1](no_overflow) < n_3(D) - -2147483648 bounds on difference of bases: 0 ... -2 result: # of iterations (unsigned int) n_3(D) + 2147483647, bounded by 0 Statement (exit)if (i_7 < npairs_4) is executed at most (unsigned int) n_3(D) + 2147483647 (bounded by 0) + 1 times in loop 1. where the bound is bogus - it should be bounded by 2147483647.
(In reply to comment #9) > > Testcase: > > volatile int j; > int __attribute__((noinline)) > foo(int n) > { > int i = 0, npairs; > npairs = n - (- __INT_MAX__ - 1); > if (npairs > 0) > { > do > { > ++j; > i = i + 1; > } > while (i < npairs); > } > return 0; > } > extern void abort (void); > int main() > { > j = 0; > foo (- __INT_MAX__ - 1 + 5); > if (j != 5) > abort (); > return 0; > } > > is optimized to an endless loop by the first VRP pass. It is caused by revision 163724: http://gcc.gnu.org/ml/gcc-cvs/2010-09/msg00015.html
(In reply to comment #11) > (In reply to comment #9) > > > > > Testcase: > > > > volatile int j; > > int __attribute__((noinline)) > > foo(int n) > > { > > int i = 0, npairs; > > npairs = n - (- __INT_MAX__ - 1); > > if (npairs > 0) > > { > > do > > { > > ++j; > > i = i + 1; > > } > > while (i < npairs); > > } > > return 0; > > } > > extern void abort (void); > > int main() > > { > > j = 0; > > foo (- __INT_MAX__ - 1 + 5); > > if (j != 5) > > abort (); > > return 0; > > } > > > > is optimized to an endless loop by the first VRP pass. > > It is caused by revision 163724: > > http://gcc.gnu.org/ml/gcc-cvs/2010-09/msg00015.html It surely has exposed it - before that patch VRP didn't use number of iteration analysis. Wheter that was correct at any point remains an open question.
Whoa. Negative logic should be banned from sources. Index: tree-ssa-loop-niter.c =================================================================== --- tree-ssa-loop-niter.c (revision 167219) +++ tree-ssa-loop-niter.c (working copy) @@ -130,7 +130,7 @@ determine_value_range (tree type, tree v /* If the computation may wrap, we know nothing about the value, except for the range of the type. */ get_type_static_bounds (type, min, max); - if (!nowrap_type_p (type)) + if (nowrap_type_p (type)) return; /* Since the addition of OFF does not wrap, if OFF is positive, then we may
Hm, no. The patch in comment #13 is not correct fix. However, the comment of bound_difference says that no overflows are assumed: /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS. The subtraction is considered to be performed in arbitrary precision, without overflows. We do not attempt to be too clever regarding the value ranges of X and Y; most of the time, they are just integers or ssa names offsetted by integer. However, we try to use the information contained in the comparisons before the loop (usually created by loop header copying). */ static void bound_difference (struct loop *loop, tree x, tree y, bounds *bnds) And we have an overflow here (slightly modified test): --cut here-- #define OFFS 1 extern void abort (void); int j; void __attribute__((noinline)) foo (int n) { int npairs, i; npairs = n - (-__INT_MAX__ - OFFS); if (npairs > 0) for (i = 0; i < npairs; i++) j++; } int main () { foo (5 - __INT_MAX__ - OFFS); if (j != 5) abort (); return 0; } --cut here-- An interesting fact, the testcase is miscompiled only for OFFS={1,2,3}.
(In reply to comment #14) > Hm, no. The patch in comment #13 is not correct fix. > > However, the comment of bound_difference says that no overflows are assumed: > > /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS. > The subtraction is considered to be performed in arbitrary precision, > without overflows. > > We do not attempt to be too clever regarding the value ranges of X and > Y; most of the time, they are just integers or ssa names offsetted by > integer. However, we try to use the information contained in the > comparisons before the loop (usually created by loop header copying). */ > > static void > bound_difference (struct loop *loop, tree x, tree y, bounds *bnds) > > And we have an overflow here (slightly modified test): > > --cut here-- > #define OFFS 1 > > extern void abort (void); > > int j; > > void > __attribute__((noinline)) > foo (int n) > { > int npairs, i; > npairs = n - (-__INT_MAX__ - OFFS); > > if (npairs > 0) > for (i = 0; i < npairs; i++) > j++; > } > > int > main () > { > foo (5 - __INT_MAX__ - OFFS); > > if (j != 5) > abort (); > > return 0; > } > --cut here-- > > > An interesting fact, the testcase is miscompiled only for OFFS={1,2,3}. Note that for OFFS 2 and 3 you invoke undefined behavior as -__INT_MAX__ - OFFS overflows. It doesn't for OFFS == 1 though, and there is no overflow in the program in that case. But writing it as n + -(-__INT_MAX__ - 1) has an overflow, the negation. I didn't yet try to investigate the number of iterations code, but I'll have a look tomorrow.
-- void foo (int n) { int npairs, i; npairs = n - (-__INT_MAX__ - 1); if (npairs > 0) for (i = 0; i < npairs; i++) j++; } -- is miscompiled. But -- void foo (int n) { int npairs, i; npairs = n - -2147483648; if (npairs > 0) for (i = 0; i < npairs; i++) j++; } -- isn't.
For npairs = n - -2147483648; VRP1 concludes Value ranges after VRP: i_1: [0, 0] n_2(D): VARYING npairs_3: VARYING But for npairs = n + 2147483648; VRP1 concludes Value ranges after VRP: Value ranges after VRP: i_1: [0, +INF] n_2(D): VARYING n.0_3: [0, +INF] D.2691_4: [0, +INF] npairs_5: VARYING
Good gimple dump: unsigned int n.0; unsigned int D.2691; int j.1; int j.2; int npairs; int i; n.0 = (unsigned int) n; D.2691 = n.0 + 2147483648; npairs = (int) D.2691; if (npairs > 0) goto <D.2692>; else goto <D.2693>; Bad gimple dump: int j.0; int j.1; int npairs; int i; npairs = n - -2147483648; if (npairs > 0) goto <D.2690>; else goto <D.2691>;
Good original dump: int npairs; int i; int npairs; int i; npairs = (int) ((unsigned int) n + 2147483648); Bad dump: int npairs; int i; int npairs; int i; npairs = n - -2147483648; We seem to fail to handle overflow for - -2147483648 at very start.
On Sun, 28 Nov 2010, hjl.tools at gmail dot com wrote: > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46675 > > --- Comment #19 from H.J. Lu <hjl.tools at gmail dot com> 2010-11-28 17:20:23 UTC --- > Good original dump: > > int npairs; > int i; > > int npairs; > int i; > npairs = (int) ((unsigned int) n + 2147483648); > > Bad dump: > > int npairs; > int i; > > int npairs; > int i; > npairs = n - -2147483648; > > We seem to fail to handle overflow for - -2147483648 at very start. Both dumps are ok, but writing n - -2147483648 makes it unsigned (you can't literally write INT_MIN). You're on the wrong track. Richard.
Does this: [hjl@gnu-6 bad]$ cat x.c.083t.forwprop3 ;; Function foo (foo) Replaced 'npairs_3 > 0' with 'n_2(D) != -2147483648' foo (int n) { int npairs; int j.1; int j.0; <bb 2>: if (n_2(D) != -2147483648) goto <bb 3>; else goto <bb 4>; <bb 3>: Invalid sum of incoming frequencies 10900, should be 10000 j.0_5 = j; j.1_6 = j.0_5 + 1; j = j.1_6; goto <bb 3>; <bb 4>: Invalid sum of incoming frequencies 213, should be 1113 return; } look OK?
fold_binary_loc turns npairs = n - -2147483648; if (npairs > 0) into if (n != -2147483648)
We check "op + 2147483648" for overflow. I don't think we properly check "op - -2147483648" for overflow.
Does this patch make any senses? --- diff --git a/gcc/fold-const.c b/gcc/fold-const.c index c195073..4bcdd07 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -10225,6 +10225,22 @@ fold_binary_loc (location_t loc, fold_convert_loc (loc, type, negate_expr (arg1))); + /* A - B -> A + (-B) if B is negative integer constant. */ + if (TREE_CODE (arg1) == INTEGER_CST && !TYPE_UNSIGNED (type)) + { + double_int di = tree_to_double_int (arg1); + if (double_int_negative_p (di)) + { + tree unsigned_type = unsigned_type_for (type); + di = double_int_neg (di); + return fold_build2_loc (loc, PLUS_EXPR, unsigned_type, + fold_convert_loc (loc, unsigned_type, arg0 ), + fold_convert_loc (loc, + unsigned_type, + double_int_to_tree (type , di))); + } + } + /* Try folding difference of addresses. */ { HOST_WIDE_INT diff; ---
Created attachment 22557 [details] A patch Does it look OK?
(In reply to comment #22) > fold_binary_loc turns > > npairs = n - -2147483648; > if (npairs > 0) > > into > > if (n != -2147483648) That's ok.
(In reply to comment #25) > Created attachment 22557 [details] > A patch > > Does it look OK? It doesn't make any sense.
As far as I can tell, there is no overflow in the code. So, this is indeed a bug in # of iterations analysis.
Created attachment 22561 [details] patch to fix overflow in # of iterations analysi Fixes overflow in # of iterations analysis -- when splitting var - INT_MIN to a sum of a variable part and a constant offset, we performed the negation of the offset in the original type (which overflows for INT_MIN) instead of in full precision.
(In reply to comment #29) > Fixes overflow in # of iterations analysis -- when splitting var - INT_MIN to a > sum of a variable part and a constant offset, we performed the negation of the > offset in the original type (which overflows for INT_MIN) instead of in full > precision. This patch fixes profiledbootstrap as well. Also, there are no new testsuite failures on x86_64-pc-linux-gnu.
(In reply to comment #30) > (In reply to comment #29) > > > Fixes overflow in # of iterations analysis -- when splitting var - INT_MIN to a > > sum of a variable part and a constant offset, we performed the negation of the > > offset in the original type (which overflows for INT_MIN) instead of in full > > precision. > > This patch fixes profiledbootstrap as well. Also, there are no new testsuite > failures on x86_64-pc-linux-gnu. Looks obvious even ;) Thanks Zdenek.
Author: uros Date: Mon Nov 29 17:08:16 2010 New Revision: 167256 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=167256 Log: 2010-11-29 Zdenek Dvorak <rakdver@kam.uniff.cz> PR tree-optimization/46675 * tree-ssa-loop-niter.c (split_to_var_and_offset): Avoid overflow in offset calculation. testsuite/ChangeLog: 2010-11-29 Richard Guenther <rguenther@suse.de> Zdenek Dvorak <rakdver@kam.uniff.cz> PR tree-optimization/46675 * gcc.dg/pr46675.c: New test. Added: trunk/gcc/testsuite/gcc.dg/pr46675.c Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-ssa-loop-niter.c
Fixed.
Author: uros Date: Mon Nov 29 20:31:21 2010 New Revision: 167267 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=167267 Log: 2010-11-29 Zdenek Dvorak <rakdver@kam.uniff.cz> PR tree-optimization/46675 * tree-ssa-loop-niter.c (split_to_var_and_offset): Avoid overflow in offset calculation. testsuite/ChangeLog: 2010-11-29 Richard Guenther <rguenther@suse.de> Zdenek Dvorak <rakdver@kam.uniff.cz> PR tree-optimization/46675 * gcc.dg/pr46675.c: New test. Added: branches/gcc-4_5-branch/gcc/testsuite/gcc.dg/pr46675.c Modified: branches/gcc-4_5-branch/gcc/ChangeLog branches/gcc-4_5-branch/gcc/testsuite/ChangeLog branches/gcc-4_5-branch/gcc/tree-ssa-loop-niter.c