Bug 46675 - [4.6 Regression] profiledbootstrap failed
Summary: [4.6 Regression] profiledbootstrap failed
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.6.0
: P3 normal
Target Milestone: 4.6.0
Assignee: Zdenek Dvorak
URL: http://gcc.gnu.org/ml/gcc-patches/201...
Keywords: wrong-code
Depends on:
Blocks:
 
Reported: 2010-11-26 14:43 UTC by H.J. Lu
Modified: 2010-11-29 20:31 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2010-11-27 07:01:34


Attachments
preprocessed file (87.19 KB, application/x-gzip)
2010-11-27 10:21 UTC, Uroš Bizjak
Details
_.122t.reassoc2 and _.123t.vrp2 detailed dumps (539.12 KB, application/x-bzip2)
2010-11-27 16:33 UTC, Uroš Bizjak
Details
A patch (489 bytes, patch)
2010-11-28 21:18 UTC, H.J. Lu
Details | Diff
patch to fix overflow in # of iterations analysi (558 bytes, patch)
2010-11-29 09:16 UTC, Zdenek Dvorak
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description H.J. Lu 2010-11-26 14:43:05 UTC
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
Comment 1 Uroš Bizjak 2010-11-27 07:01:34 UTC
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
Comment 2 Uroš Bizjak 2010-11-27 09:32:47 UTC
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.
Comment 3 Uroš Bizjak 2010-11-27 10:21:20 UTC
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.
Comment 4 Uroš Bizjak 2010-11-27 11:14:56 UTC
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.
Comment 5 Uroš Bizjak 2010-11-27 12:15:12 UTC
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;
Comment 6 Richard Biener 2010-11-27 14:47:33 UTC
You don't by chance have a standalone testcase yet? ;)

Can you attach reassoc and vrp -details dumps with -fprofile-use?
Comment 7 Uroš Bizjak 2010-11-27 16:33:49 UTC
Created attachment 22547 [details]
_.122t.reassoc2 and _.123t.vrp2 detailed dumps
Comment 8 Uroš Bizjak 2010-11-27 16:35:51 UTC
(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.
Comment 9 Richard Biener 2010-11-27 20:12:44 UTC
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.
Comment 10 Richard Biener 2010-11-27 20:19:40 UTC
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.
Comment 11 H.J. Lu 2010-11-27 22:06:27 UTC
(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
Comment 12 Richard Biener 2010-11-27 22:20:13 UTC
(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.
Comment 13 Uroš Bizjak 2010-11-28 12:46:10 UTC
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
Comment 14 Uroš Bizjak 2010-11-28 15:07:39 UTC
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}.
Comment 15 Richard Biener 2010-11-28 15:54:57 UTC
(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.
Comment 16 H.J. Lu 2010-11-28 16:10:08 UTC
--
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.
Comment 17 H.J. Lu 2010-11-28 16:25:34 UTC
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
Comment 18 H.J. Lu 2010-11-28 17:09:17 UTC
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>;
Comment 19 H.J. Lu 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.
Comment 20 rguenther@suse.de 2010-11-28 17:22:58 UTC
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.
Comment 21 H.J. Lu 2010-11-28 17:58:49 UTC
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?
Comment 22 H.J. Lu 2010-11-28 18:12:14 UTC
fold_binary_loc turns

  npairs = n - -2147483648;
  if (npairs > 0)

into

  if (n != -2147483648)
Comment 23 H.J. Lu 2010-11-28 18:56:51 UTC
We check "op + 2147483648" for overflow. I don't think we properly
check "op - -2147483648" for overflow.
Comment 24 H.J. Lu 2010-11-28 21:04:10 UTC
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;
---
Comment 25 H.J. Lu 2010-11-28 21:18:39 UTC
Created attachment 22557 [details]
A patch

Does it look OK?
Comment 26 Richard Biener 2010-11-28 23:14:27 UTC
(In reply to comment #22)
> fold_binary_loc turns
> 
>   npairs = n - -2147483648;
>   if (npairs > 0)
> 
> into
> 
>   if (n != -2147483648)

That's ok.
Comment 27 Richard Biener 2010-11-28 23:16:05 UTC
(In reply to comment #25)
> Created attachment 22557 [details]
> A patch
> 
> Does it look OK?

It doesn't make any sense.
Comment 28 Zdenek Dvorak 2010-11-29 08:37:01 UTC
As far as I can tell, there is no overflow in the code.  So, this is indeed a bug in # of iterations analysis.
Comment 29 Zdenek Dvorak 2010-11-29 09:16:56 UTC
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.
Comment 30 Uroš Bizjak 2010-11-29 14:07:19 UTC
(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.
Comment 31 Richard Biener 2010-11-29 14:54:26 UTC
(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.
Comment 32 uros 2010-11-29 17:08:20 UTC
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
Comment 33 Uroš Bizjak 2010-11-29 17:21:31 UTC
Fixed.
Comment 34 uros 2010-11-29 20:31:25 UTC
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