[Bug tree-optimization/65177] New: [5 Regression]: extend jump thread for finite state automata causes miscompilation

[Bug tree-optimization/65177] New: [5 Regression]: extend jump thread for finite state automata causes miscompilation

[marxin at gcc dot gnu.org]

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

            Bug ID: 65177
           Summary: [5 Regression]: extend jump thread for finite state
                    automata causes miscompilation
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: marxin at gcc dot gnu.org
                CC: spop at gcc dot gnu.org

Hello.

Starting with r218451, http://hmmer.janelia.org/ started to be miscompiled.

Steps to reproduce:
wget
http://selab.janelia.org/software/hmmer3/3.1b1/hmmer-3.1b1-linux-intel-x86_64.tar.gz
tar xvzf hmmer-3.1b1-cygwin.tar.gz 
cd hmmer-3.1b1-cygwin
CFLAGS="-g -O1 -ftree-vrp -fexpensive-optimizations" ./configure
make
make check

and following test fails:
gdb src/impl_sse/optacc_utest 

Program received signal SIGSEGV, Segmentation fault.
0x0000000000406a2c in select_i (k=<optimized out>, i=0, gx=0x45ed60,
gm=0x470420) at generic_optacc.c:293
293      path[0] = TSCDELTA(p7P_MI, k) * MMX(i-1,k);
(gdb) bt
#0  0x0000000000406a2c in select_i (k=<optimized out>, i=0, gx=0x45ed60,
gm=0x470420) at generic_optacc.c:293
#1  p7_GOATrace (gm=0x470420, pp=pp@entry=0x466150, gx=gx@entry=0x45ed60,
tr=tr@entry=0x46e4e0) at generic_optacc.c:220
#2  0x000000000040322f in utest_optacc (go=go@entry=0x44e010,
r=r@entry=0x44e170, abc=abc@entry=0x44eb50, bg=bg@entry=0x44ed90, M=M@entry=45,
L=L@entry=50, N=19) at ./optacc.c:659
#3  0x0000000000403613 in main (argc=<optimized out>, argv=<optimized out>) at
./optacc.c:801

I really tried to reduce test case, but unfortunately it's very hard to do it
for the project.
Please tell me if you are capable of reproducing the issue?

Thanks,
Martin

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
           Priority|P3                          |P1
   Target Milestone|---                         |5.0

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[trippels at gcc dot gnu.org]

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

Markus Trippelsdorf <trippels at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |trippels at gcc dot gnu.org

--- Comment #1 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
-fsanitize=address shows:

markus@x4 impl_sse % ./optacc_utest
=================================================================
==25254==ERROR: AddressSanitizer: heap-buffer-overflow on address
0x61b00001f160 at pc 0x00000040e8a0 bp 0x7ffe6daa1620 sp 0x7ffe6daa1618
READ of size 4 at 0x61b00001f160 thread T0
    #0 0x40e89f in select_m
/home/markus/hmmer-3.1b1-linux-intel-x86_64/src/generic_optacc.c:267
    #1 0x40e89f in p7_GOATrace
/home/markus/hmmer-3.1b1-linux-intel-x86_64/src/generic_optacc.c:218
    #2 0x405d19 in utest_optacc optacc.c:659
    #3 0x406281 in main optacc.c:801
    #4 0x7f671f71e6cf in __libc_start_main (/lib/libc.so.6+0x206cf)
    #5 0x402448 in _start
(/home/markus/hmmer-3.1b1-linux-intel-x86_64/src/impl_sse/optacc_utest+0x402448)

0x61b00001f160 is located 32 bytes to the left of 1440-byte region
[0x61b00001f180,0x61b00001f720)
allocated by thread T0 here:
    #0 0x7f671ffaf502 in malloc
(/usr/lib/gcc/x86_64-pc-linux-gnu/5.0.0/libasan.so.2+0x9c502)
    #1 0x41c667 in p7_profile_Create
/home/markus/hmmer-3.1b1-linux-intel-x86_64/src/p7_profile.c:68

SUMMARY: AddressSanitizer: heap-buffer-overflow
/home/markus/hmmer-3.1b1-linux-intel-x86_64/src/generic_optacc.c:267 select_m
Shadow bytes around the buggy address:
  0x0c367fffbdd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c367fffbde0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c367fffbdf0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c367fffbe00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c367fffbe10: 00 07 fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0c367fffbe20: fa fa fa fa fa fa fa fa fa fa fa fa[fa]fa fa fa
  0x0c367fffbe30: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c367fffbe40: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c367fffbe50: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c367fffbe60: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c367fffbe70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
==25254==ABORTING

valgrind:
markus@x4 impl_sse % valgrind ./optacc_utest
==32064== Memcheck, a memory error detector
==32064== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==32064== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==32064== Command: ./optacc_utest
==32064== 
==32064== Invalid read of size 4
==32064==    at 0x406851: select_m (generic_optacc.c:267)
==32064==    by 0x406851: p7_GOATrace (generic_optacc.c:218)
==32064==    by 0x4032B8: utest_optacc (optacc.c:659)
==32064==    by 0x40369C: main (optacc.c:801)
==32064==  Address 0x525c610 is 32 bytes before a block of size 1,440 in arena
"client"
==32064== 
==32064== Invalid read of size 4
==32064==    at 0x40689B: select_m (generic_optacc.c:268)
==32064==    by 0x40689B: p7_GOATrace (generic_optacc.c:218)
==32064==    by 0x4032B8: utest_optacc (optacc.c:659)
==32064==    by 0x40369C: main (optacc.c:801)
==32064==  Address 0x525c614 is 28 bytes before a block of size 1,440 in arena
"client"
==32064== 
==32064== Invalid read of size 4
==32064==    at 0x4068D1: select_m (generic_optacc.c:269)
==32064==    by 0x4068D1: p7_GOATrace (generic_optacc.c:218)
==32064==    by 0x4032B8: utest_optacc (optacc.c:659)
==32064==    by 0x40369C: main (optacc.c:801)
==32064==  Address 0x525c618 is 24 bytes before a block of size 1,440 alloc'd
==32064==    at 0x4028C70: malloc (vg_replace_malloc.c:296)
==32064==    by 0x40C05D: p7_profile_Create (p7_profile.c:68)
==32064==    by 0x416DAD: p7_oprofile_Sample (p7_oprofile.c:1579)
==32064==    by 0x402FCC: utest_optacc (optacc.c:621)
==32064==    by 0x40369C: main (optacc.c:801)
==32064== 
==32064== Invalid read of size 4
==32064==    at 0x4068FF: select_m (generic_optacc.c:270)
==32064==    by 0x4068FF: p7_GOATrace (generic_optacc.c:218)
==32064==    by 0x4032B8: utest_optacc (optacc.c:659)
==32064==    by 0x40369C: main (optacc.c:801)
==32064==  Address 0x525c61c is 20 bytes before a block of size 1,440 alloc'd
==32064==    at 0x4028C70: malloc (vg_replace_malloc.c:296)
==32064==    by 0x40C05D: p7_profile_Create (p7_profile.c:68)
==32064==    by 0x416DAD: p7_oprofile_Sample (p7_oprofile.c:1579)
==32064==    by 0x402FCC: utest_optacc (optacc.c:621)
==32064==    by 0x40369C: main (optacc.c:801)
==32064== 
==32064== Invalid read of size 4
==32064==    at 0x406877: select_m (generic_optacc.c:267)
==32064==    by 0x406877: p7_GOATrace (generic_optacc.c:218)
==32064==    by 0x4032B8: utest_optacc (optacc.c:659)
==32064==    by 0x40369C: main (optacc.c:801)
==32064==  Address 0x5275954 is 12 bytes after a block of size 440 alloc'd
==32064==    at 0x402B23E: realloc (vg_replace_malloc.c:692)
==32064==    by 0x411B2C: p7_omx_GrowTo (p7_omx.c:179)
==32064==    by 0x4030A1: utest_optacc (optacc.c:627)
==32064==    by 0x40369C: main (optacc.c:801)
==32064== 
==32064== Invalid read of size 4
==32064==    at 0x4068AD: select_m (generic_optacc.c:268)
==32064==    by 0x4068AD: p7_GOATrace (generic_optacc.c:218)
==32064==    by 0x4032B8: utest_optacc (optacc.c:659)
==32064==    by 0x40369C: main (optacc.c:801)
==32064==  Address 0x5275958 is 16 bytes after a block of size 440 alloc'd
==32064==    at 0x402B23E: realloc (vg_replace_malloc.c:692)
==32064==    by 0x411B2C: p7_omx_GrowTo (p7_omx.c:179)
==32064==    by 0x4030A1: utest_optacc (optacc.c:627)
==32064==    by 0x40369C: main (optacc.c:801)
==32064== 
==32064== Invalid read of size 4
==32064==    at 0x4068E3: select_m (generic_optacc.c:269)
==32064==    by 0x4068E3: p7_GOATrace (generic_optacc.c:218)
==32064==    by 0x4032B8: utest_optacc (optacc.c:659)
==32064==    by 0x40369C: main (optacc.c:801)
==32064==  Address 0x527595c is 20 bytes after a block of size 440 alloc'd
==32064==    at 0x402B23E: realloc (vg_replace_malloc.c:692)
==32064==    by 0x411B2C: p7_omx_GrowTo (p7_omx.c:179)
==32064==    by 0x4030A1: utest_optacc (optacc.c:627)
==32064==    by 0x40369C: main (optacc.c:801)
==32064== 
==32064== Invalid read of size 4
==32064==    at 0x406E57: p7_GOATrace (generic_optacc.c:231)
==32064==    by 0x4032B8: utest_optacc (optacc.c:659)
==32064==    by 0x40369C: main (optacc.c:801)
==32064==  Address 0x527d6c4 is 12 bytes after a block of size 440 alloc'd
==32064==    at 0x402B23E: realloc (vg_replace_malloc.c:692)
==32064==    by 0x4082FA: p7_gmx_GrowTo (p7_gmx.c:123)
==32064==    by 0x4030C5: utest_optacc (optacc.c:628)
==32064==    by 0x40369C: main (optacc.c:801)
==32064== 
==32064== Invalid read of size 8
==32064==    at 0x406874: select_m (generic_optacc.c:267)
==32064==    by 0x406874: p7_GOATrace (generic_optacc.c:218)
==32064==    by 0x4032B8: utest_optacc (optacc.c:659)
==32064==    by 0x40369C: main (optacc.c:801)
==32064==  Address 0x527d4f8 is 8 bytes before a block of size 440 alloc'd
==32064==    at 0x402B23E: realloc (vg_replace_malloc.c:692)
==32064==    by 0x4082FA: p7_gmx_GrowTo (p7_gmx.c:123)
==32064==    by 0x4030C5: utest_optacc (optacc.c:628)
==32064==    by 0x40369C: main (optacc.c:801)
==32064== 
==32064== 
==32064== Process terminating with default action of signal 11 (SIGSEGV)
==32064==  Access not within mapped region at address 0xFFFFFFFFFFFFFFB8
==32064==    at 0x406877: select_m (generic_optacc.c:267)
==32064==    by 0x406877: p7_GOATrace (generic_optacc.c:218)
==32064==    by 0x4032B8: utest_optacc (optacc.c:659)
==32064==    by 0x40369C: main (optacc.c:801)
==32064==  If you believe this happened as a result of a stack
==32064==  overflow in your program's main thread (unlikely but
==32064==  possible), you can try to increase the size of the
==32064==  main thread stack using the --main-stacksize= flag.
==32064==  The main thread stack size used in this run was 8388608.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[marxin at gcc dot gnu.org]

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

--- Comment #2 from Martin Liška <marxin at gcc dot gnu.org> ---
(In reply to Martin Liška from comment #0)
> Hello.
> 
> Starting with r218451, http://hmmer.janelia.org/ started to be miscompiled.
> 
> Steps to reproduce:
> wget
> http://selab.janelia.org/software/hmmer3/3.1b1/hmmer-3.1b1-linux-intel-
> x86_64.tar.gz
> tar xvzf hmmer-3.1b1-cygwin.tar.gz 
> cd hmmer-3.1b1-cygwin
> CFLAGS="-g -O1 -ftree-vrp -fexpensive-optimizations" ./configure
> make
> make check
> 
> and following test fails:
> gdb src/impl_sse/optacc_utest 
> 
> Program received signal SIGSEGV, Segmentation fault.
> 0x0000000000406a2c in select_i (k=<optimized out>, i=0, gx=0x45ed60,
> gm=0x470420) at generic_optacc.c:293
> 293	  path[0] = TSCDELTA(p7P_MI, k) * MMX(i-1,k);
> (gdb) bt
> #0  0x0000000000406a2c in select_i (k=<optimized out>, i=0, gx=0x45ed60,
> gm=0x470420) at generic_optacc.c:293

The reason for memory corruption is caused by select_i function called with i
== 0, which causes memory load for array[-1].

Martin

> #1  p7_GOATrace (gm=0x470420, pp=pp@entry=0x466150, gx=gx@entry=0x45ed60,
> tr=tr@entry=0x46e4e0) at generic_optacc.c:220
> #2  0x000000000040322f in utest_optacc (go=go@entry=0x44e010,
> r=r@entry=0x44e170, abc=abc@entry=0x44eb50, bg=bg@entry=0x44ed90,
> M=M@entry=45, L=L@entry=50, N=19) at ./optacc.c:659
> #3  0x0000000000403613 in main (argc=<optimized out>, argv=<optimized out>)
> at ./optacc.c:801
> 
> I really tried to reduce test case, but unfortunately it's very hard to do
> it for the project.
> Please tell me if you are capable of reproducing the issue?
> 
> Thanks,
> Martin
>From gcc-bugs-return-478193-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Mon Feb 23 16:45:18 2015
Return-Path: <gcc-bugs-return-478193-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 28149 invoked by alias); 23 Feb 2015 16:45:18 -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 28078 invoked by uid 48); 23 Feb 2015 16:45:13 -0000
From: "jakub at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug target/65032] [5 Regression] ICE in reload_combine_note_use, at postreload.c:1556 on i686-linux-gnu
Date: Mon, 23 Feb 2015 17:46:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: target
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords: ice-on-valid-code
X-Bugzilla-Severity: normal
X-Bugzilla-Who: jakub at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 5.0
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-65032-4-kE9AXyavg3@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-65032-4@http.gcc.gnu.org/bugzilla/>
References: <bug-65032-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-02/txt/msg02525.txt.bz2
Content-length: 2075

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
So, from what I can see, the problem is that we have during IRA:
(insn 48 47 49 6 (parallel [
            (set (reg:DI 93 [ D.2201 ])
                (sign_extend:DI (reg/v:SI 88 [ b ])))
            (clobber (reg:CC 17 flags))
            (clobber (scratch:SI))
        ]) pr65032.C:79 143 {extendsidi2_1}
     (expr_list:REG_UNUSED (reg:CC 17 flags)
        (nil)))
(insn 50 93 51 6 (parallel [
            (set (reg:DI 111 [ D.2201 ])
                (neg:DI (reg:DI 93 [ D.2201 ])))
            (clobber (reg:CC 17 flags))
        ]) pr65032.C:79 450 {*negdi2_doubleword}
     (expr_list:REG_UNUSED (reg:CC 17 flags)
        (nil)))
and LRA turns this into:
(insn 48 47 49 6 (parallel [
            (set (mem/c:DI (plus:SI (reg/f:SI 7 sp)
                        (const_int 8 [0x8])) [13 %sfp+-24 S8 A64])
                (sign_extend:DI (reg/v:SI 5 di [orig:88 b ] [88])))
            (clobber (reg:CC 17 flags))
            (clobber (reg:SI 0 ax [118]))
        ]) pr65032.C:79 143 {extendsidi2_1}
     (nil))
(insn 104 93 101 6 (parallel [
            (set (reg:DI 0 ax [orig:111 D.2201 ] [111])
                (sign_extend:DI (reg/v:SI 5 di [orig:88 b ] [88])))
            (clobber (reg:CC 17 flags))
            (clobber (reg:SI 118))
        ]) pr65032.C:79 143 {extendsidi2_1}
     (nil))
(insn 50 101 102 6 (parallel [
            (set (reg:DI 0 ax [orig:111 D.2201 ] [111])
                (neg:DI (reg:DI 0 ax [orig:111 D.2201 ] [111])))
            (clobber (reg:CC 17 flags))
        ]) pr65032.C:79 450 {*negdi2_doubleword}
     (nil))
and the problem is the (clobber (reg:SI 118)) kept in the IL.  The constraint
for it there is "=X", but despite that accepting anything, postreload really
doesn't like pseudos kept around in the instructions.
Dunno if (scratch:SI) instead would be still acceptable post-reload, or if we
need some other way to express we really don't care about the clobber (the insn
will be split during split2 pass).

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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

--- Comment #3 from Sebastian Pop <spop at gcc dot gnu.org> ---
The miscompile happens when compiling src/generic_optacc.c:
with -fdbg-cnt=registered_jump_thread:167 it passes, and with
-fdbg-cnt=registered_jump_thread:168 it segfaults.

The difference is:

--- /tmp/167    2015-02-23 17:46:45.061408277 +0100
+++ /tmp/168    2015-02-23 17:46:38.373407907 +0100
@@ -1,4 +1,4 @@
-dbg_cnt 'registered_jump_thread' set to 167
+dbg_cnt 'registered_jump_thread' set to 168
   Registering jump thread: (33, 35)  (35, 39)  (39, 41) 
   Registering jump thread: (44, 46)  (46, 50)  (50, 52) 
   Registering jump thread: (68, 70)  (70, 74)  (74, 76) 
@@ -182,6 +182,8 @@
   Registering FSM jump thread: (60, 64)  (64, 66)  (66, 69)  (69, 96)  (96,
95)  (95, 27) 
   Registering FSM jump thread: (61, 64)  (64, 66)  (66, 69)  (69, 96)  (96,
95)  (95, 27) 
   Registering FSM jump thread: (58, 64)  (64, 66)  (66, 69)  (69, 96)  (96,
95)  (95, 26) 
+  Registering FSM jump thread: (13, 53)  (53, 55)  (55, 64)  (64, 66)  (66,
67)  (67, 68)  (68, 69)  (69, 96)  (96, 95)  (95, 5) 
 generating code for:   Registering FSM jump thread: (60, 64)  (64, 66)  (66,
69)  (69, 96)  (96, 95)  (95, 27) 
+generating code for:   Registering FSM jump thread: (13, 53)  (53, 55)  (55,
64)  (64, 66)  (66, 67)  (67, 68)  (68, 69)  (69, 96)  (96, 95)  (95, 5) 
 generating code for:   Registering FSM jump thread: (58, 64)  (64, 66)  (66,
69)  (69, 96)  (96, 95)  (95, 26) 
 generating code for:   Registering FSM jump thread: (61, 64)  (64, 66)  (66,
69)  (69, 96)  (96, 95)  (95, 27)

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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

--- Comment #4 from Sebastian Pop <spop at gcc dot gnu.org> ---
command line:
cd src
gcc -g -O1 -ftree-vrp -fexpensive-optimizations -pthread -fPIC -msse2
-DHAVE_CONFIG_H  -I../easel -I../libdivsufsort -I../easel -I. -I. -o
generic_optacc.o -c generic_optacc.c  -fdbg-cnt=registered_jump_thread:168

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-02-25
                 CC|                            |mpolacek at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #5 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Thus confirmed.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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

Sebastian Pop <spop at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |UNCONFIRMED
   Last reconfirmed|2015-02-25 00:00:00         |
     Ever confirmed|1                           |0

--- Comment #6 from Sebastian Pop <spop at gcc dot gnu.org> ---
The SEME region copier does not update the SSA correctly:

bb_53:
      # i_1 = PHI <i_126(13), i_250(52)>
      # sprv_5 = PHI <sprv_137(13), sprv_284(52)>
      # .MEM_7 = PHI <.MEM_331(13), .MEM_337(52)>
      # k_339 = PHI <k_84(13), k_285(52)>
      # sprv_780 = PHI <1(13), 7(52)>

bb_104 is a copy of bb_53:
      # i_672 = PHI <i_126(13)>
      # sprv_437 = PHI <sprv_137(13)>
      # .MEM_715 = PHI <.MEM_331(13)>
      # k_716 = PHI <k_84(13)>
      # sprv_717 = PHI <1(13)>


bb_64:
      # _319 = PHI <0.0(55), 0.0(58), _313(61)>
      # sprv_751 = PHI <sprv_5(55), 5(58), 8(61)>
      # i_769 = PHI <i_1(55), i_766(58), i_767(61)>
      # sprv_784 = PHI <sprv_780(55), sprv_781(58), 8(61)>
      # k_790 = PHI <k_339(55), k_787(58), k_788(61)>
      # .MEM_810 = PHI <.MEM_7(55), .MEM_807(58), .MEM_808(61)>

bb_106 a copy of bb_64:
      # _594 = PHI <0.0(105)>
      # sprv_515 = PHI <sprv_5(105)>
      # i_516 = PHI <i_1(105)>
      # sprv_567 = PHI <sprv_780(105)>
      # k_541 = PHI <k_339(105)>
      # .MEM_619 = PHI <.MEM_7(105)>


In bb_106, a copy of bb_64,
- # sprv_567 = PHI <sprv_780(105)>
  we use the old value sprv_780 instead of the new value sprv_717 set in
bb_105:

- # sprv_515 = PHI <sprv_5(105)>
  we use the old value sprv_5 instead of the new value sprv_437:

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Any progress on this?  I've tried to reproduce but have the miscompile vs.
compile dbg counter on ~ current trunk (221277) in a different spot (=198
works, =199 fails) and even with r210000 different bbs and SSA_NAME versions,
so it is hard to find out if we are looking at the same thing.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[law at redhat dot com]

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

--- Comment #8 from Jeffrey A. Law <law at redhat dot com> ---
There's not enough information in those comments to definitively say the SEME
copier isn't updating the SSA graph properly.  If I were looking at this, I'd
want the dump as we enter VRP or DOM (whichever is triggering the problematic
FSM thread), then a dump after that pass was done.  Preferably the dumps would
include the basic block information (-fdump-tree-<whatever>-blocks).  Knowing
the shape of the CFG is critical to proving or disproving the SEME copier is
mucking things up.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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

--- Comment #9 from Sebastian Pop <spop at gcc dot gnu.org> ---
I added a pass of update_ssa after each invocation of the SEME copier, and that
produced 26 extra fails (on top of the failing test) in the hmmer make check.
The problem with adding an update_ssa is that we have to also clean up the cfg
as update_ssa requires a rebuild of the dominators information.  I will attach
the patch adding update_ssa.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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

--- Comment #10 from Sebastian Pop <spop at gcc dot gnu.org> ---
Created attachment 35005
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35005&action=edit
add update_ssa to seme copier

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[law at redhat dot com]

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

--- Comment #11 from Jeffrey A. Law <law at redhat dot com> ---
>From a sequencing standpoint, you do your block copying & wire up the new
blocks.  Then you have to remove unreachable blocks, rebuild dominators then
update hte SSA graph.

That is unless the SEME copier tries to update SSA internally, but that's
painful.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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

--- Comment #12 from Sebastian Pop <spop at gcc dot gnu.org> ---
(In reply to Jeffrey A. Law from comment #11)
> That is unless the SEME copier tries to update SSA internally, but that's
> painful.

I have also tried to update the SSA only in the copied basic blocks: graphite's
code generator in sese.c does exactly that only on the path that has been
duplicated.  sese.c has its own rename_map. In SEME I was not able to access
easily the rename maps set by copy_bb: when copying statements, it sets a map
of (old_def, new_def) that are used to rename all the uses dominated by the new
definition.  We could use this rename map to rename all uses in the copied bbs.

I think it would be less painful to fix the SSA in a local way than what the
patch that I just sent out does:

> From a sequencing standpoint, you do your block copying & wire up the new
> blocks.  Then you have to remove unreachable blocks, rebuild dominators then
> update hte SSA graph.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[law at redhat dot com]

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

--- Comment #13 from Jeffrey A. Law <law at redhat dot com> ---
But you can need updates that extend beyond the scope of the SEME I would
think.  That was my recollection from looking at ways to minimize the number of
blocks the renamer had to examine after threading.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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

--- Comment #14 from Sebastian Pop <spop at gcc dot gnu.org> ---
(In reply to Jeffrey A. Law from comment #13)
> But you can need updates that extend beyond the scope of the SEME I would
> think.  That was my recollection from looking at ways to minimize the number
> of blocks the renamer had to examine after threading.

You are right, we need to update all uses of ssa_names defined in the SEME.

We currently only fix all the phi nodes on all the exits of the SEME by adding
one more operand to the phis.  I think we would also need to add phi nodes for
all the definitions that we copied as now we may reach the destination of an
SEME exit through at least two paths: the original path and the copied one.

I do not know whether update_ssa has enough information to correctly add these
phi nodes.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[law at redhat dot com]

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

--- Comment #15 from Jeffrey A. Law <law at redhat dot com> ---
Basically the way this works is we record the SSA_NAMEs that are being
duplicated during block copying.  For any duplicated SSA_NAME, if > 1 instance
of it is live at a join point in the CFG, then update_ssa will create a PHI and
merge the values.  

I can't offhand think of any reason why it wouldn't work here if the names were
properly marked.  But I haven't looked at the before/after CFGs to see if
there's something unique in this case.  In fact, I haven't looked at it at all
at this point.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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

--- Comment #16 from Sebastian Pop <spop at gcc dot gnu.org> ---
Created attachment 35030
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35030&action=edit
IR before and after for failing FSM jump thread

After updating the sources of GCC, I now see the fail as Jakub has reported at
dbgctr=199.

The difference between 198 and 199 is this jump thread path:

FSM jump thread: (13, 53) incoming edge;  (53, 55)  (55, 64)  (64, 66)  (66,
67)  (67, 68)  (68, 69)  (69, 95)  (95, 94)  (94, 5) nocopy; (94, 5)

The attached file is a dump of the IR just before and after SEME code
generation of this path.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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

--- Comment #17 from Sebastian Pop <spop at gcc dot gnu.org> ---
Trying to figure out why we FSM jump thread this path: (13, 53) (53, 55)  (55,
64)  (64, 66)  (66, 67)  (67, 68)  (68, 69)  (69, 95)  (95, 94)  (94, 5) (94,
5)

In BB_94 we have this code:

      switch (sprv_49) <default: <L13>, case 1: <L5>, case 2: <L6>, case 3:
<L7>, case 5: <L28>, case 6: <L29>, case 7: <L38>, case 8: <L36>, case 10:
<L37>>

at this point FSM infers that sprv_49 == 1 and we jump to bb_5.  Why?
Following the FSM jump thread path backward from 94 to 13, we have these SSA
definitions:

      # sprv_49 = PHI <8(4), sprv_737(95)>
      # sprv_737 = PHI <sprv_735(66), sprv_735(67), sprv_736(68), sprv_739(92),
10(88)>
      # sprv_736 = PHI <sprv_768(67), sprv_738(90)>
      # sprv_768 = PHI <sprv_764(55), 8(61), sprv_765(58), sprv_766(60)>
      # sprv_764 = PHI <1(13), 7(52)>

So if we are coming from bb_13, we are guaranteed to have a value of 1.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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

Sebastian Pop <spop at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2015-03-16
     Ever confirmed|0                           |1

--- Comment #18 from Sebastian Pop <spop at gcc dot gnu.org> ---
Before all FSM jump threads the representation looks correct: we would not jump
thread from sprv_137 that is a value read from memory:

# sprv_49 = PHI <8(4), sprv_14(78)>
# sprv_14 = PHI <sprv_5(58), sprv_43(76)>
# sprv_5 = PHI <sprv_137(14), sprv_284(49), -1(42)>
sprv_137 = state[_136];

After update_ssa in the dom1 pass, the representation looks bogus:
# sprv_49 = PHI <8(4), sprv_737(95)>
# sprv_737 = PHI <sprv_735(66), sprv_735(67), sprv_736(68), sprv_739(92),
10(88)>
# sprv_736 = PHI <sprv_768(67), sprv_738(90)>
# sprv_768 = PHI <sprv_764(55), 5(26), sprv_765(58), sprv_766(60), 8(61)>
# sprv_764 = PHI <1(13), 7(52)>
This representation is incorrect because we would jump thread the value "1"
coming from bb 13 into the "switch (sprv_49)".

After installing the patch to update the SSA after each FSM jump thread, the
representation gets corrupted on generating code for this FSM path:
(43, 76) (76, 60)  (60, 69)  (69, 70)  (70, 71)  (71, 72)  (72, 73)  (73, 78) 
(78, 5) (5, 6)

Before we jump thread:

;; basic block 58, loop depth 1, count 0, freq 0
;; Invalid sum of incoming frequencies 1580, should be 0
;;  prev block 57, next block 59, flags: (NEW, REACHABLE)
;;  pred:       14 [100.0%]  (FALLTHRU,EXECUTABLE)
;;              49 [9.0%]  (FALSE_VALUE,EXECUTABLE)
# i_1 = PHI <i_126(14), i_250(49)>
# sprv_5 = PHI <sprv_137(14), sprv_284(49)>
# .MEM_7 = PHI <.MEM_331(14), .MEM_337(49)>
# k_339 = PHI <k_84(14), k_285(49)>
if (sprv_5 == -1)
  goto <bb 59>;
else
  goto <bb 60>;
;;  succ:       59 [12.0%]  (TRUE_VALUE,EXECUTABLE)
;;              60 [88.0%]  (FALSE_VALUE,EXECUTABLE)

After update_ssa, we now have two phi nodes sprv_5 and a new phi sprv_450 that
will in turn be folded into "1":

;; basic block 58, loop depth 1, count 0, freq 0
;; Invalid sum of incoming frequencies 1580, should be 0
;;  prev block 57, next block 59, flags: (NEW, REACHABLE)
;;  pred:       14 [100.0%]  (FALLTHRU,EXECUTABLE)
;;              49 [9.0%]  (FALSE_VALUE,EXECUTABLE)
# i_1 = PHI <i_126(14), i_250(49)>
# sprv_5 = PHI <sprv_137(14), sprv_284(49)>
# .MEM_7 = PHI <.MEM_331(14), .MEM_337(49)>
# k_339 = PHI <k_84(14), k_285(49)>
# sprv_450 = PHI <sprv_449(14), sprv_49(49)>
if (sprv_5 == -1)
  goto <bb 59>;
else
  goto <bb 60>;
;;  succ:       59 [12.0%]  (TRUE_VALUE,EXECUTABLE)
;;              60 [88.0%]  (FALSE_VALUE,EXECUTABLE)

On the jump thread
(43, 76) (76, 60)  (60, 69)  (69, 70)  (70, 71)  (71, 72)  (72, 73)  (73, 78) 
(78, 5)  (5, 6)
there is a diamond on the jump threaded path: (70, 71) (71, 72) (72, 73) and
(70, 73).
When using copy_bbs we first copy all the bbs in the path, and then update all
the edges:

if (!(e->dest->flags & BB_DUPLICATED))
  continue;
redirect_edge_and_branch_force (e, get_bb_copy (e->dest));

And so this will redirect the edges of the copied region to the copied blocks,
creating a diamond in the copied region.  This invalidates the single entry
property we want for an SEME region.

We need to keep the exits from the jump thread path as they are, going to the
original code, and not to the copied blocks: these exits are exceptions that do
not carry the same state which guarantes the property we are propagating.

In a jump thread path all nodes have to be walked through in order for the
propagated property to be still holding.  In this case we have a diamond that
may shortcut the execution of some basic blocks on the jump thread path, and
instead of taking the exception edge outside the jump thread, it lands back
again on the copied region invalidating the assumption we were propagating from
the beginning of the jump thread.

We want the jump thread code generator to create a SEME region: that is a
Single Entry Multiple Exits region.  In the case of a diamond, with the current
version of copy_bbs we would end up with a diamond on the copied region, and
that invalidates the single entry of the SEME.

Jeff, there are two ways to fix this:
- one way is to discard jump threads with diamonds,
- or we can fix seme_copier to only redirect edges that are on the jump thread
path.
Which one do you like most?

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[law at redhat dot com]

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

--- Comment #19 from Jeffrey A. Law <law at redhat dot com> ---
I'm still getting up to speed here, but this sounds vaguely familiar to
something we've run into before.

https://gcc.gnu.org/ml/gcc-patches/2013-11/msg01073.html

Is when the code moved to a later point, but that should at least give you an
idea of the issue the code is trying to resolve.   I'm hoping to dig deeper
into this BZ in the next day or so, but figured I'd pass that along since a
quick scan of your comments reminded me of that issue.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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

--- Comment #20 from Sebastian Pop <spop at gcc dot gnu.org> ---
Created attachment 35046
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35046&action=edit
fix

The attached patch fixes the problem by not creating diamonds in the copied
jump-thread.

I'm bootstrapping and regtesting this on x86_64-linux and I will send the patch
for review after it passes.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[law at redhat dot com]

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

--- Comment #21 from Jeffrey A. Law <law at redhat dot com> ---
Isn't the real issue here that the test for redirecting the edge is wrong?

If we're leaving the jump thread path, then we want those edges to reach their
original targets.  Thus merely testing if the destination is a duplicate block
isn't the right test, we'd need to have the thread path and check if the
outgoing edge is on the path or not.

That may not be terribly easy to do in the current framework.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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

--- Comment #22 from Sebastian Pop <spop at gcc dot gnu.org> ---
(In reply to Jeffrey A. Law from comment #21)
> Isn't the real issue here that the test for redirecting the edge is wrong?

You are right, the test for redirecting edges in copy_bbs is not sufficient for
jump-threading: it will redirect all edges pointing to copied blocks, whereas
what jump-threading expects is only redirect edges between consecutive blocks
on the path to be jump-threaded.

> If we're leaving the jump thread path, then we want those edges to reach
> their original targets.  Thus merely testing if the destination is a
> duplicate block isn't the right test,

Right.  Richi asked to let copy_bbs do its default behavior, redirecting edges
to all copied bbs, and fix up the edges that we don't want to redirect just
after the call to copy_bbs: that is implemented in the second patch I sent to
gcc-patches.

> we'd need to have the thread path and check if the outgoing edge is on the path or not.
> 
> That may not be terribly easy to do in the current framework.

Note that the "region" of blocks we are passing to copy_bbs is the jump-thread
path in order of its execution: here is the code that creates the "region" just
before the call to copy_bbs:

      for (unsigned int j = 0; j < len - 1; j++)
    region[j] = (*path)[j]->e->dest;

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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

--- Comment #23 from Sebastian Pop <spop at gcc dot gnu.org> ---
Author: spop
Date: Wed Mar 25 22:49:47 2015
New Revision: 221675

URL: https://gcc.gnu.org/viewcvs?rev=221675&root=gcc&view=rev
Log:
diamonds are not valid execution threads for jump threading

    PR tree-optimization/65177
    * tree-ssa-threadupdate.c (verify_seme): Renamed verify_jump_thread.
    (bb_in_bbs): New.
    (duplicate_seme_region): Renamed duplicate_thread_path.  Redirect all
    edges not adjacent on the path to the original code.

    * gcc.dg/tree-ssa/ssa-dom-thread-10.c: New.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-threadupdate.c

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[spop at gcc dot gnu.org]

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

Sebastian Pop <spop at gcc dot gnu.org> changed:

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

--- Comment #24 from Sebastian Pop <spop at gcc dot gnu.org> ---
Fixed in trunk.

[Bug tree-optimization/65177] [5 Regression]: extend jump thread for finite state automata causes miscompilation

[yroux at gcc dot gnu.org]

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

--- Comment #25 from Yvan Roux <yroux at gcc dot gnu.org> ---
Author: yroux
Date: Wed Oct 28 09:00:47 2015
New Revision: 229478

URL: https://gcc.gnu.org/viewcvs?rev=229478&root=gcc&view=rev
Log:
gcc/
2015-10-28 Yvan Roux  <yvan.roux@linaro.org>
           Sebastian Pop  <s.pop@samsung.com>

        Backport from trunk r221007, r221675, r222011.
        2015-04-11  Jakub Jelinek  <jakub@redhat.com>

        PR tree-optimization/65735
        * tree-ssa-threadedge.c (fsm_find_control_statement_thread_paths):
        Remove visited_phis argument, add visited_bbs, avoid recursing into the
        same bb rather than just into the same phi node.
        (thread_through_normal_block): Adjust caller.

        2015-03-25  Sebastian Pop  <s.pop@samsung.com>

        PR tree-optimization/65177
        * tree-ssa-threadupdate.c (verify_seme): Renamed verify_jump_thread.
        (bb_in_bbs): New.
        (duplicate_seme_region): Renamed duplicate_thread_path.  Redirect all
        edges not adjacent on the path to the original code.

        2015-02-26  Sebastian Pop  <s.pop@samsung.com>

        PR tree-optimization/65048
        * tree-ssa-threadupdate.c (valid_jump_thread_path): New.
        (thread_through_all_blocks): Call valid_jump_thread_path.
        Remove invalid FSM jump-thread paths.

gcc/testsuite/
2015-10-28 Yvan Roux  <yvan.roux@linaro.org>
           Sebastian Pop  <s.pop@samsung.com>

        Backport from trunk r221007, r221675, r222011.
        2015-04-11  Jakub Jelinek  <jakub@redhat.com>

        PR tree-optimization/65735
        * gcc.c-torture/compile/pr65735.c: New test.

        2015-03-25  Sebastian Pop  <s.pop@samsung.com>

        PR tree-optimization/65177
        * gcc.dg/tree-ssa/ssa-dom-thread-10.c: New.

        2015-02-26  Sebastian Pop  <s.pop@samsung.com>

        PR tree-optimization/65048
        * gcc.dg/tree-ssa/ssa-dom-thread-9.c: New.


Added:
   
branches/linaro/gcc-4_9-branch/gcc/testsuite/gcc.c-torture/compile/pr65735.c
   
branches/linaro/gcc-4_9-branch/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-10.c
   
branches/linaro/gcc-4_9-branch/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-9.c
Modified:
    branches/linaro/gcc-4_9-branch/gcc/ChangeLog.linaro
    branches/linaro/gcc-4_9-branch/gcc/testsuite/ChangeLog.linaro
    branches/linaro/gcc-4_9-branch/gcc/tree-ssa-threadedge.c
    branches/linaro/gcc-4_9-branch/gcc/tree-ssa-threadupdate.c