[Bug tree-optimization/59387] New: wrong code (hangs) at -Os on x86_64-linux-gnu

[Bug tree-optimization/59387] New: wrong code (hangs) at -Os on x86_64-linux-gnu

[su at cs dot ucdavis.edu]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59387

            Bug ID: 59387
           Summary: wrong code (hangs) at -Os on x86_64-linux-gnu
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: su at cs dot ucdavis.edu

The current gcc trunk miscompiles the following code on x86_64-linux at -Os
(but not at the other optimization levels) in both 32-bit and 64-bit modes. 

This is a regression from 4.8.x.

$ gcc-trunk -v
Using built-in specs.
COLLECT_GCC=gcc-trunk
COLLECT_LTO_WRAPPER=/usr/local/gcc-trunk/libexec/gcc/x86_64-unknown-linux-gnu/4.9.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: ../gcc-trunk/configure --prefix=/usr/local/gcc-trunk
--enable-languages=c,c++ --disable-werror --enable-multilib
Thread model: posix
gcc version 4.9.0 20131204 (experimental) [trunk revision 205673] (GCC) 
$ 
$ gcc-trunk -O1 small.c; a.out
$ gcc-trunk -O2 small.c; a.out
$ gcc-4.8 -Os small.c; a.out
$ 
$ gcc-trunk -Os small.c
$ a.out
^C
$ 


-------------------------


int a, *d, **e = &d, f;
char c;

struct
{
  int f1;
} b;

int
main ()
{
  for (a = -19; a; a++)
    {
      for (b.f1 = 0; b.f1 < 24; b.f1++)
    c--; 
      *e = &f;
      if (!d)
    return 0;
    }
  return 0;
}

[Bug tree-optimization/59387] wrong code (hangs) at -Os on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59387

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
           Priority|P3                          |P1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-12-05
   Target Milestone|---                         |4.9.0
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.

[Bug tree-optimization/59387] [4.9 Regression] wrong code (hangs) at -Os on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59387

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org
            Summary|wrong code (hangs) at -Os   |[4.9 Regression] wrong code
                   |on x86_64-linux-gnu         |(hangs) at -Os on
                   |                            |x86_64-linux-gnu

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r196792.  Looking at it.

[Bug tree-optimization/59387] [4.9 Regression] wrong code (hangs) at -Os on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59387

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Seems it is SCCP that breaks this.
We have a loop like:
  <bb 4>:
  c.2_10 = (unsigned char) c_lsm.11_20;
  _11 = c.2_10 + 255;
  c.3_12 = (char) _11;
  _14 = b_f1_lsm.12_7 + 1;

  <bb 5>:
  # c_lsm.11_20 = PHI <c_lsm.11_15(3), c.3_12(4)>
  # b_f1_lsm.12_7 = PHI <0(3), _14(4)>
  if (b_f1_lsm.12_7 <= 23)
    goto <bb 4>;
  else
    goto <bb 6>;

  <bb 6>:
  # b_f1_lsm.12_36 = PHI <b_f1_lsm.12_7(5)>
  # c_lsm.11_40 = PHI <c_lsm.11_20(5)>

where c.2/c.3/c_lsm.11 is signed char.  Note the c decrement done carefully in
unsigned char type.
But then comes sccp and does:
final value replacement:
  c_lsm.11_40 = PHI <c_lsm.11_20(5)>
  with
  c_lsm.11_40 = c_lsm.11_15 + -24;
which is invalid, because it is subtracted in signed type instead of the
unsigned type originally.  Dunno if scev remembers somewhere what type the
arithmetics has been actually performed in.  Richard, can you please have a
look?

[Bug tree-optimization/59387] [4.9 Regression] wrong code (hangs) at -Os on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59387

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Note already the chrec is {c_lsm.11_15, +, -1}_2 with char type everywhere (but
the 2 which is int, but that is irrelevant), so the information that the
decrement was performed carefully in non-wrapping type is lost at that point.
Dunno if we want and whether it would be possible to generate a chrec with
unsigned char type in that case instead
(i.e. (char) {(unsigned char)c_lsm.11_15, +, 255}_2 instead), or some special
bit on the chrec to tell us that it is wrapping.

[Bug tree-optimization/59387] [4.9 Regression] wrong code (hangs) at -Os on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59387

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 31777
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31777&action=edit
gcc49-pr59387.patch

So like this?  I'll bootstrap/regtest it with additional logging to see how
often we refuse to sccp because of this.

[Bug tree-optimization/59387] [4.9 Regression] wrong code (hangs) at -Os on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59387

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Unfortunately it triggers (sccp no longer optimizes) on quite a few testcases:

gcc.c-torture/execute/pr58277-1.c
gcc.c-torture/execute/pr58831.c
gcc.c-torture/execute/pr59387.c
gcc.dg/pr58010.c
gcc.dg/torture/pr55481.c
gcc.dg/torture/pr56366.c
gcc.dg/torture/pr59058.c
gcc.dg/torture/pr59245.c
gcc.dg/tree-ssa/loop-32.c
gcc.dg/tree-ssa/loop-33.c
gcc.dg/tree-ssa/loop-35.c
gcc.dg/tree-ssa/scev-6.c

(the first test only for -m64, all the rest both -m32 and -m64, the last even
FAILs because of that).  Couldn't we just transform that somehow into an
unsigned type computation instead in that case, at least for simple cases?

[Bug tree-optimization/59387] [4.9 Regression] wrong code (hangs) at -Os on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59387

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #7)
> Unfortunately it triggers (sccp no longer optimizes) on quite a few
> testcases:
> 
> gcc.c-torture/execute/pr58277-1.c
> gcc.c-torture/execute/pr58831.c
> gcc.c-torture/execute/pr59387.c
> gcc.dg/pr58010.c
> gcc.dg/torture/pr55481.c
> gcc.dg/torture/pr56366.c
> gcc.dg/torture/pr59058.c
> gcc.dg/torture/pr59245.c
> gcc.dg/tree-ssa/loop-32.c
> gcc.dg/tree-ssa/loop-33.c
> gcc.dg/tree-ssa/loop-35.c
> gcc.dg/tree-ssa/scev-6.c
> 
> (the first test only for -m64, all the rest both -m32 and -m64, the last
> even FAILs because of that).  Couldn't we just transform that somehow into
> an unsigned type computation instead in that case, at least for simple cases?

You could leverage the code I added to LIM ... in the case where SCEV folded
casts, of course.

[Bug tree-optimization/59387] [4.9 Regression] wrong code (hangs) at -Os on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59387

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 31797
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31797&action=edit
gcc49-pr59387.patch

Untested fix.

[Bug tree-optimization/59387] [4.9 Regression] wrong code (hangs) at -Os on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59387

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Mon Jan 13 19:14:03 2014
New Revision: 206583

URL: http://gcc.gnu.org/viewcvs?rev=206583&root=gcc&view=rev
Log:
    PR tree-optimization/59387
    * tree-scalar-evolution.c: Include gimple-fold.h and gimplify-me.h.
    (scev_const_prop): If folded_casts and type has undefined overflow,
    use force_gimple_operand instead of force_gimple_operand_gsi and
    for each added stmt if it is assign with
    arith_code_with_undefined_signed_overflow, call
    rewrite_to_defined_overflow.
    * tree-ssa-loop-im.c: Don't include gimplify-me.h, include
    gimple-fold.h instead.
    (arith_code_with_undefined_signed_overflow,
    rewrite_to_defined_overflow): Moved to ...
    * gimple-fold.c (arith_code_with_undefined_signed_overflow,
    rewrite_to_defined_overflow): ... here.  No longer static.
    Include gimplify-me.h.
    * gimple-fold.h (arith_code_with_undefined_signed_overflow,
    rewrite_to_defined_overflow): New prototypes.

    * gcc.c-torture/execute/pr59387.c: New test.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/gimple-fold.c
    trunk/gcc/gimple-fold.h
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-scalar-evolution.c
    trunk/gcc/tree-ssa-loop-im.c

[Bug tree-optimization/59387] [4.9 Regression] wrong code (hangs) at -Os on x86_64-linux-gnu

[law at redhat dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59387

Jeffrey A. Law <law at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |law at redhat dot com
         Resolution|---                         |FIXED

--- Comment #11 from Jeffrey A. Law <law at redhat dot com> ---
Fixed by jakub's commit.

[Bug tree-optimization/59387] [4.9 Regression] wrong code (hangs) at -Os on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59387

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Thu Jan 16 19:14:49 2014
New Revision: 206678

URL: http://gcc.gnu.org/viewcvs?rev=206678&root=gcc&view=rev
Log:
    PR tree-optimization/59387
    * gcc.c-torture/execute/pr59387.c: New test.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr59387.c