[Bug tree-optimization/59715] New: wrong code at -Os and above on x86_64-linux-gnu

[Bug tree-optimization/59715] New: wrong code at -Os and above on x86_64-linux-gnu

[su at cs dot ucdavis.edu]

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

            Bug ID: 59715
           Summary: wrong code at -Os and above 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 (as well as 4.8.x and 4.7.x) miscompiles the following
code on x86_64-linux at -Os and above in both 32-bit and 64-bit modes.

This is a regression from 4.6.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 20140107 (experimental) [trunk revision 206387] (GCC) 
$ 
$ gcc-trunk -O1 small.c; a.out
0
$ gcc-4.6 -Os small.c; a.out
0
$ gcc-trunk -Os small.c; a.out
2
$ gcc-4.8 -Os small.c; a.out
2
$ gcc-4.7 -Os small.c; a.out
2
$ 


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


int printf (const char *, ...);

int a = 2, b;

int
main ()
{
  int c;
  if (!b)
    {
      b = a;
      c = a == 0 ? 1 : 1 % a;
      if (c)
    b = 0;
    }
  printf ("%d\n", b);
  return 0;
}

[Bug tree-optimization/59715] wrong code at -Os and above on x86_64-linux-gnu

[steven at gcc dot gnu.org]

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

Steven Bosscher <steven at gcc dot gnu.org> changed:

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

--- Comment #1 from Steven Bosscher <steven at gcc dot gnu.org> ---
b is used uninitialized => undefined behavior

[Bug tree-optimization/59715] wrong code at -Os and above on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
   Last reconfirmed|                            |2014-01-08
                 CC|                            |jakub at gcc dot gnu.org
         Resolution|INVALID                     |---
     Ever confirmed|0                           |1

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Nope, b is initialized to 0.

[Bug tree-optimization/59715] [4.7/4.8/4.9 Regression] wrong code at -Os and above on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |vries at gcc dot gnu.org
   Target Milestone|---                         |4.7.4
            Summary|wrong code at -Os and above |[4.7/4.8/4.9 Regression]
                   |on x86_64-linux-gnu         |wrong code at -Os and above
                   |                            |on x86_64-linux-gnu

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r179275.

[Bug tree-optimization/59715] [4.7/4.8/4.9 Regression] wrong code at -Os and above on x86_64-linux-gnu

[steven at gcc dot gnu.org]

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

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |NEW

--- Comment #4 from Steven Bosscher <steven at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #2)
> Nope, b is initialized to 0.

Eh, right, sorry!

[Bug tree-optimization/59715] [4.7/4.8/4.9 Regression] wrong code at -Os and above on x86_64-linux-gnu

[vries at gcc dot gnu.org]

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

--- Comment #5 from vries at gcc dot gnu.org ---
The test passes with -fno-tree-tail-merge. But I don't see anything wrong with
the transformation (merging of empty blocks) done by the pass. 

AFAICT, the problem is introduced by pass_dominator. test.c.126t.slsr looks ok,
but test.c.127t.dom2 look wrong. The test passes with -fno-tree-dominator-opts.

test.c.126t.slsr:
...
  <bb 2>:
  b.0_4 = b;
  if (b.0_4 == 0)
    goto <bb 4>;
  else
    goto <bb 3>;

  <bb 3>:
  goto <bb 7>;

  <bb 4>:
  a.1_5 = a;
  if (a.1_5 != 0)
    goto <bb 5>;
  else
    goto <bb 6>;

  <bb 5>:
  b = a.1_5;
  c_7 = 1 % a.1_5;
  if (c_7 != 0)
    goto <bb 6>;
  else
    goto <bb 3>;

  <bb 6>:
  b = 0;

  <bb 7>:
  b.0_9 = b;
  printf ("%d\n", b.0_9);
  return 0;
...
we're taking the path bb2 -> bb4 -> bb5 (b = 2) -> bb6 (b = 0) -> bb7

test.c.127t.dom2:
...
  <bb 2>:
  b.0_4 = b;
  if (b.0_4 == 0)
    goto <bb 4>;
  else
    goto <bb 3>;

  <bb 3>:
  goto <bb 6>;

  <bb 4>:
  a.1_5 = a;
  if (a.1_5 != 0)
    goto <bb 5>;
  else
    goto <bb 6>;

  <bb 5>:
  b = a.1_5;
  c_7 = 1 % a.1_5;
  if (c_7 != 0)
    goto <bb 6>;
  else
    goto <bb 3>;

  <bb 6>:
  b.0_9 = b;
  printf ("%d\n", b.0_9);
  return 0;
...
we're taking the path bb2 -> bb4 -> bb5 (b = 2) -> bb6

[Bug tree-optimization/59715] [4.7/4.8/4.9 Regression] wrong code at -Os and above on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
           Priority|P3                          |P2

[Bug tree-optimization/59715] [4.7/4.8/4.9 Regression] wrong code at -Os and above on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Mine then.

[Bug tree-optimization/59715] [4.7/4.8/4.9 Regression] wrong code at -Os and above on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
virtual SSA form is broken, we have overlapping life-ranges - a virtual PHI
node is missing in bb 6, seems to be broken by store sinking (-fno-tree-sink
fixes it).  The virtual SSA form updating is too simple:

      /* Update virtual operands of statements in the path we
         do not sink to.  */
      if (gimple_vdef (stmt))
        {
          imm_use_iterator iter;
          use_operand_p use_p;
          gimple vuse_stmt;

          FOR_EACH_IMM_USE_STMT (vuse_stmt, iter, gimple_vdef (stmt))
            if (gimple_code (vuse_stmt) != GIMPLE_PHI)
              FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
                SET_USE (use_p, gimple_vuse (stmt));
        }

as in this case we sink

    store
     |  \
     x   |
    / \  |
   /   \ y ---
  /           \
needed-here    \
              but not here

sinking assumes that critical edges are split - but tail-merging breaks this
assumption, breaking sinking.  With critical edges split we can insert
on the edge to needed-here.

Either dumb down sinking (detect the critical edge case and don't sink),
make it insert on edges instead, or restore previous behavior to have
critical edges split after PRE (note it may be already partly broken
before as cfg-cleanup unsplits edges again).

So it is tail-merging introducing this after all, but not necessarily
tail-mergings fault.

[Bug tree-optimization/59715] [4.7/4.8/4.9 Regression] wrong code at -Os and above on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 31774
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31774&action=edit
untested patch

Like with the attached patch which performs edge-insertion.  But it doesn't
work that way because incrementally sinking then isn't able to figure out
a destination gsi (we can't do gsi_for_stmt on an edge-insertion-queued stmt,
bah).

But otherwise it fixes the bug ...

Leaves to disable the sinking, it's not the optimal insertion place anyway
(if not inserting on the edge).  Or to re-run critical edge splitting.

[Bug tree-optimization/59715] [4.7/4.8/4.9 Regression] wrong code at -Os and above on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 31775
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31775&action=edit
alternative patch

Alternative patch splitting critical edges again.  I'm going to test that, it
fixes optimization regressions from at least 4.3 where critical edges were
still
split reliably.

[Bug tree-optimization/59715] [4.7/4.8/4.9 Regression] wrong code at -Os and above on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Thu Jan  9 09:21:02 2014
New Revision: 206460

URL: http://gcc.gnu.org/viewcvs?rev=206460&root=gcc&view=rev
Log:
2014-01-09  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/59715
    * tree-cfg.h (split_critical_edges): Declare.
    * tree-cfg.c (split_critical_edges): Export.
    * tree-ssa-sink.c (execute_sink_code): Split critical edges.

    * gcc.dg/torture/pr59715.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr59715.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-cfg.c
    trunk/gcc/tree-cfg.h
    trunk/gcc/tree-ssa-sink.c

[Bug tree-optimization/59715] [4.7/4.8 Regression] wrong code at -Os and above on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.9.0
            Summary|[4.7/4.8/4.9 Regression]    |[4.7/4.8 Regression] wrong
                   |wrong code at -Os and above |code at -Os and above on
                   |on x86_64-linux-gnu         |x86_64-linux-gnu
      Known to fail|                            |4.8.2

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk sofar.

[Bug tree-optimization/59715] [4.7/4.8 Regression] wrong code at -Os and above on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Fri Jan 10 08:37:07 2014
New Revision: 206511

URL: http://gcc.gnu.org/viewcvs?rev=206511&root=gcc&view=rev
Log:
2014-01-10  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/59715
    * tree-flow.h (split_critical_edges): Declare.
    * tree-cfg.c (split_critical_edges): Export.
    * tree-ssa-sink.c (execute_sink_code): Split critical edges.

    * gcc.dg/torture/pr59715.c: New testcase.

Added:
    branches/gcc-4_8-branch/gcc/testsuite/gcc.dg/torture/pr59715.c
Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_8-branch/gcc/tree-cfg.c
    branches/gcc-4_8-branch/gcc/tree-flow.h
    branches/gcc-4_8-branch/gcc/tree-ssa-sink.c

[Bug tree-optimization/59715] [4.7 Regression] wrong code at -Os and above on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED
      Known to fail|                            |4.7.3

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.

[Bug tree-optimization/59715] [4.7 Regression] wrong code at -Os and above on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Wed May  7 10:07:09 2014
New Revision: 210147

URL: http://gcc.gnu.org/viewcvs?rev=210147&root=gcc&view=rev
Log:
2014-05-07  Richard Biener  <rguenther@suse.de>

    Backport from mainline
    2013-11-29  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/59334
    * tree-ssa-dce.c (eliminate_unnecessary_stmts): Fix bug
    in previous commit.

    2013-11-28  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/59330
    * tree-ssa-dce.c (eliminate_unnecessary_stmts): Simplify
    and fix delayed marking of free calls not necessary.

    * gcc.dg/torture/pr59330.c: New testcase.

    2014-01-09  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/59715
    * tree-cfg.h (split_critical_edges): Declare.
    * tree-cfg.c (split_critical_edges): Export.
    * tree-ssa-sink.c (execute_sink_code): Split critical edges.

    * gcc.dg/torture/pr59715.c: New testcase.

Modified:
    branches/gcc-4_7-branch/gcc/tree-flow.h