[Bug rtl-optimization/51771] New: trans-mem: abnormal edges get lost or corrupted

[Bug rtl-optimization/51771] New: trans-mem: abnormal edges get lost or corrupted

[torvald at gcc dot gnu.org]

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

             Bug #: 51771
           Summary: trans-mem: abnormal edges get lost or corrupted
    Classification: Unclassified
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: torvald@gcc.gnu.org
                CC: aldyh@gcc.gnu.org, rth@gcc.gnu.org


For each call to libitm we create an abnormal edge back to the transaction's
begin, which models that libitm could restart.  Those edges seem to be intact
during the middle-end but get lost or corrupted somewhere after that.  This
leads to miscompilation of STAMP Genome on x86_64, for example.

For 4.7, we can mark _ITM_beginTransaction as returns-twice.  This seems to
work but isn't optimal, so we should fix the handling of abnormal edges for
4.8.

[Bug rtl-optimization/51771] trans-mem: abnormal edges get lost or corrupted

[torvald at gcc dot gnu.org]

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

--- Comment #1 from torvald at gcc dot gnu.org 2012-01-05 23:48:36 UTC ---
Author: torvald
Date: Thu Jan  5 23:48:30 2012
New Revision: 182937

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=182937
Log:
Mark transaction begin as returns-twice.

    PR rtl-optimization/51771
    gcc/
    * builtin-attrs.def (ATTR_RETURNS_TWICE, ATTR_TM_NOTHROW_RT_LIST):
    New.
    * gtm-builtins.def (BUILT_IN_TM_START): Add returns-twice attrib.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/builtin-attrs.def
    trunk/gcc/gtm-builtins.def

[Bug rtl-optimization/51771] trans-mem: abnormal edges get lost or corrupted

[patrick.marlier at gmail dot com]

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

Patrick Marlier <patrick.marlier at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |patrick.marlier at gmail
                   |                            |dot com

--- Comment #2 from Patrick Marlier <patrick.marlier at gmail dot com> 2012-01-17 22:09:58 UTC ---
Just to not forget, one thread about it is here:
http://gcc.gnu.org/ml/gcc/2012-01/msg00099.html

Patrick Marlier.

[Bug rtl-optimization/51771] trans-mem: abnormal edges get lost or corrupted

[torvald at gcc dot gnu.org]

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

--- Comment #3 from torvald at gcc dot gnu.org 2012-01-31 13:20:32 UTC ---
Created attachment 26532
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26532
test for false returns-twice warning

Attached a test that triggers a false warning due to the returns-twice hack
when -Wclobbered is used.  The transactions roll back updates properly.

[Bug rtl-optimization/51771] trans-mem: abnormal edges get lost or corrupted

[torvald at gcc dot gnu.org]

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

torvald at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.8.0

[Bug rtl-optimization/51771] trans-mem: abnormal edges get lost or corrupted

[luked at cs dot rochester.edu]

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

--- Comment #4 from Luke Dalessandro <luked at cs dot rochester.edu> 2012-05-03 15:06:57 UTC ---
Created attachment 27303
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27303
RBTree microbenchmark test case

I believe that I'm seeing this in the RSTM suite's RBTree microbenchmark as
well. It appears to be manifesting with the same symptoms as pr47530,
_ITM_commitTransaction is generated as a tail call. An abort in
_ITM_commitTransaction during multithreaded execution corrupts the stack slot
that is used to hold a "time" value.

I attached the TreeBench.ii test case so that a second, complex example of the
problem exists.

Static manifestation of bug is "jmp _ITM_commitTransaction" in asm output.

$ g++ -O3 -fgnu-tm -o /dev/stdout -S TreeBench.ii | grep _ITM_commitTransaction 
    call    _ITM_commitTransaction
    jmp    _ITM_commitTransaction
    jmp    _ITM_commitTransaction

Runtime manifestation is corrupted "time" output (and thus "throughput" output
as well) under multithreaded execution ("p" command line parameter) of the
optimized executable.

$ g++ -fgnu-tm -o TreeBench TreeBench.ii -lrt
$ ./TreeBench -p2
Verification: Passed
csv, ALG=gcc-tm, B=RBTree, R=34, d=1, p=2, X=0, m=256, S=1, O=1, txns=1251624,
time=1000001773, throughput=1251621

$ g++ -O3 -fgnu-tm -o TreeBench TreeBench.ii -lrt
$ ./TreeBench -p2
Verification: Passed
csv, ALG=gcc-tm, B=RBTree, R=34, d=1, p=2, X=0, m=256, S=1, O=1,
txns=391668795, time=1336057254755574655, throughput=0

Output from g++ -v -save-temps.

$ g++ -fgnu-tm -O3 -m64 -DSTM_INST_STM -DSTM_API_GCCTM -DSTM_CC_GCC
-DSTM_OS_LINUX -DSTM_CPU_X86 -DSTM_BITS_64 -DSTM_OPT_O3 -DSTM_WS_BYTELOG
-DSINGLE_SOURCE_BUILD -I../include -I../lib -v -save-temps TreeBench.cpp -lrt
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/localdisk/luked/pub/gcc/4.8/bin/../libexec/gcc/x86_64-redhat-linux/4.8.0/lto-wrapper
Target: x86_64-redhat-linux
Configured with: ../gcc-4.8/configure --prefix=/u/luked/pub/gcc/4.8
--enable-bootstrap --enable-threads=posix --enable-checking=release
--with-system-zlib --enable-__cxa-atexit --disable-libunwind-exceptions
--enable-linker-build-id --enable-plugins --enable-lto --disable-nls
--enable-ld --enable-gold --with-gmp=/u/luked/pub/gmp-5.0.4-static
--with-mpfr=/u/luked/pub/mpfr-3.1.0-static
--with-mpc=/u/luked/pub/mpc-0.9-static
--with-ppl=/u/luked/pub/ppl-0.11.2-static
--with-cloog=/u/luked/pub/cloog-0.16.3-static --enable-cloog-backend=isl
--with-tune=generic --with-arch-32=i686 --with-gnu-ld --with-gnu-as
--with-plugin-ld=ld.gold --build=x86_64-redhat-linux
--with-host-libstdcxx='/usr/local/lib64/libstdc++.a -lm'
--enable-languages=c,c++,lto : (reconfigured) 
Thread model: posix
gcc version 4.8.0 20120502 (experimental) [trunk revision 187050] (GCC) 
COLLECT_GCC_OPTIONS='-fgnu-tm' '-O3' '-m64' '-D' 'STM_INST_STM' '-D'
'STM_API_GCCTM' '-D' 'STM_CC_GCC' '-D' 'STM_OS_LINUX' '-D' 'STM_CPU_X86' '-D'
'STM_BITS_64' '-D' 'STM_OPT_O3' '-D' 'STM_WS_BYTELOG' '-D'
'SINGLE_SOURCE_BUILD' '-I' '../include' '-I' '../lib' '-v' '-save-temps'
'-shared-libgcc' '-mtune=generic' '-march=x86-64' '-pthread'

/localdisk/luked/pub/gcc/4.8/bin/../libexec/gcc/x86_64-redhat-linux/4.8.0/cc1plus
-E -quiet -v -I ../include -I ../lib -iprefix
/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/
-D_GNU_SOURCE -D_REENTRANT -D STM_INST_STM -D STM_API_GCCTM -D STM_CC_GCC -D
STM_OS_LINUX -D STM_CPU_X86 -D STM_BITS_64 -D STM_OPT_O3 -D STM_WS_BYTELOG -D
SINGLE_SOURCE_BUILD TreeBench.cpp -m64 -mtune=generic -march=x86-64 -fgnu-tm
-O3 -fpch-preprocess -o TreeBench.ii
ignoring nonexistent directory
"/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../x86_64-redhat-linux/include"
ignoring duplicate directory
"/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/../../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../include/c++/4.8.0"
ignoring duplicate directory
"/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/../../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../include/c++/4.8.0/x86_64-redhat-linux"
ignoring duplicate directory
"/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/../../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../include/c++/4.8.0/backward"
ignoring duplicate directory
"/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/../../lib/gcc/x86_64-redhat-linux/4.8.0/include"
ignoring duplicate directory
"/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/../../lib/gcc/x86_64-redhat-linux/4.8.0/include-fixed"
ignoring nonexistent directory
"/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/../../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../x86_64-redhat-linux/include"
#include "..." search starts here:
#include <...> search starts here:
 ../include
 ../lib

/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../include/c++/4.8.0

/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../include/c++/4.8.0/x86_64-redhat-linux

/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../include/c++/4.8.0/backward
 /localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/include

/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/include-fixed
 /usr/local/include
 /localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/../../include
 /usr/include
End of search list.
COLLECT_GCC_OPTIONS='-fgnu-tm' '-O3' '-m64' '-D' 'STM_INST_STM' '-D'
'STM_API_GCCTM' '-D' 'STM_CC_GCC' '-D' 'STM_OS_LINUX' '-D' 'STM_CPU_X86' '-D'
'STM_BITS_64' '-D' 'STM_OPT_O3' '-D' 'STM_WS_BYTELOG' '-D'
'SINGLE_SOURCE_BUILD' '-I' '../include' '-I' '../lib' '-v' '-save-temps'
'-shared-libgcc' '-mtune=generic' '-march=x86-64' '-pthread'

/localdisk/luked/pub/gcc/4.8/bin/../libexec/gcc/x86_64-redhat-linux/4.8.0/cc1plus
-fpreprocessed TreeBench.ii -quiet -dumpbase TreeBench.cpp -m64 -mtune=generic
-march=x86-64 -auxbase TreeBench -O3 -version -fgnu-tm -o TreeBench.s
GNU C++ (GCC) version 4.8.0 20120502 (experimental) [trunk revision 187050]
(x86_64-redhat-linux)
    compiled by GNU C version 4.8.0 20120502 (experimental) [trunk revision
187050], GMP version 5.0.4, MPFR version 3.1.0, MPC version 0.9
GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
GNU C++ (GCC) version 4.8.0 20120502 (experimental) [trunk revision 187050]
(x86_64-redhat-linux)
    compiled by GNU C version 4.8.0 20120502 (experimental) [trunk revision
187050], GMP version 5.0.4, MPFR version 3.1.0, MPC version 0.9
GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
Compiler executable checksum: c6589865671e480899c2bc410ddd1367
COLLECT_GCC_OPTIONS='-fgnu-tm' '-O3' '-m64' '-D' 'STM_INST_STM' '-D'
'STM_API_GCCTM' '-D' 'STM_CC_GCC' '-D' 'STM_OS_LINUX' '-D' 'STM_CPU_X86' '-D'
'STM_BITS_64' '-D' 'STM_OPT_O3' '-D' 'STM_WS_BYTELOG' '-D'
'SINGLE_SOURCE_BUILD' '-I' '../include' '-I' '../lib' '-v' '-save-temps'
'-shared-libgcc' '-mtune=generic' '-march=x86-64' '-pthread'

/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../x86_64-redhat-linux/bin/as
-v -I ../include -I ../lib --64 -o TreeBench.o TreeBench.s
GNU assembler version 2.22.52 (x86_64-redhat-linux) using BFD version (GNU
Binutils) 2.22.52.20120502
COMPILER_PATH=/localdisk/luked/pub/gcc/4.8/bin/../libexec/gcc/x86_64-redhat-linux/4.8.0/:/localdisk/luked/pub/gcc/4.8/bin/../libexec/gcc/:/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../x86_64-redhat-linux/bin/
LIBRARY_PATH=/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/:/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/:/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../lib64/:/lib/../lib64/:/usr/lib/../lib64/:/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../x86_64-redhat-linux/lib/:/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/../../../:/lib/:/usr/lib/
Reading specs from
/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../lib64/libitm.spec
COLLECT_GCC_OPTIONS='-fgnu-tm' '-O3' '-m64' '-D' 'STM_INST_STM' '-D'
'STM_API_GCCTM' '-D' 'STM_CC_GCC' '-D' 'STM_OS_LINUX' '-D' 'STM_CPU_X86' '-D'
'STM_BITS_64' '-D' 'STM_OPT_O3' '-D' 'STM_WS_BYTELOG' '-D'
'SINGLE_SOURCE_BUILD' '-I' '../include' '-I' '../lib' '-v' '-save-temps'
'-shared-libgcc' '-mtune=generic' '-march=x86-64' '-pthread'

/localdisk/luked/pub/gcc/4.8/bin/../libexec/gcc/x86_64-redhat-linux/4.8.0/collect2
--build-id --eh-frame-hdr -m elf_x86_64 -dynamic-linker
/lib64/ld-linux-x86-64.so.2 /usr/lib/../lib64/crt1.o /usr/lib/../lib64/crti.o
/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/crtbegin.o
-L/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0
-L/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc
-L/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../lib64
-L/lib/../lib64 -L/usr/lib/../lib64
-L/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/../../../../x86_64-redhat-linux/lib
-L/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/../../..
TreeBench.o -lrt -lstdc++ -lm -litm -lgcc_s -lgcc -lpthread -lc -lgcc_s -lgcc
/localdisk/luked/pub/gcc/4.8/bin/../lib/gcc/x86_64-redhat-linux/4.8.0/crtend.o
/usr/lib/../lib64/crtn.o

[Bug rtl-optimization/51771] trans-mem: abnormal edges get lost or corrupted

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-06-01
     Ever Confirmed|0                           |1

--- Comment #5 from Aldy Hernandez <aldyh at gcc dot gnu.org> 2012-06-01 16:39:12 UTC ---
This is a mental note for whenever we decide to pick this up again...

The current approach with the returns-twice patch is a bit heavy handed, as the
register allocator will more-or-less give up across returns-twice.  With the
appropriate abnormal edges, the allocator will get more exact info.  Whether or
not it's able to do anything extra with this info is a different story... 
That's why, we should drop this to ultra low priority-- the returns-twice
approach is good enough.

However, when someone gets bored, the way to debug this is with any trivial
testcase:

  int glob;
  foo()
  {
    __transaction_atomic { glob=666; }
  }

If one reverts the returns-twice patch referenced in this PR, one sees the
abnormal edges all the way up to *.c.*t.optimized.  The edges get corrupted
somewhere in the RTL passes.

[Bug rtl-optimization/51771] trans-mem: abnormal edges get lost or corrupted

[aldyh at gcc dot gnu.org]

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

--- Comment #6 from Aldy Hernandez <aldyh at gcc dot gnu.org> 2012-06-01 16:46:27 UTC ---
Created attachment 27543
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27543
Proposed patch by Richard Henderson-- untested

This is an old, untested patch from rth that attempts to fix the problem
without the returns-twice hack.  There is some overlap with Patrick Marlier's
attempt here:

http://gcc.gnu.org/ml/gcc/2012-01/msg00099.html

Patch provided here so we don't have to reanalyze everything if/when we revisit
this issue.

[Bug rtl-optimization/51771] trans-mem: abnormal edges get lost or corrupted

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P4
           Severity|normal                      |enhancement

[Bug rtl-optimization/51771] trans-mem: abnormal edges get lost or corrupted

[aldyh at gcc dot gnu.org]

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

--- Comment #7 from Aldy Hernandez <aldyh at gcc dot gnu.org> 2012-06-04 16:08:30 UTC ---
(In reply to comment #4)
> Created attachment 27303 [details]
> RBTree microbenchmark test case
> 
> I believe that I'm seeing this in the RSTM suite's RBTree microbenchmark as
> well. It appears to be manifesting with the same symptoms as pr47530,
> _ITM_commitTransaction is generated as a tail call. An abort in
> _ITM_commitTransaction during multithreaded execution corrupts the stack slot
> that is used to hold a "time" value.

Luke, this is actually PR47530 and unrelated to this PR.  I am fixing it for
PR47530, and any further discussing will be in that PR.

[Bug rtl-optimization/51771] trans-mem: abnormal edges get lost or corrupted

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot       |aldyh at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #8 from Aldy Hernandez <aldyh at gcc dot gnu.org> 2012-11-29 17:05:16 UTC ---
This should get revisited now that we have redesigned how the back edges are
generated.

FWIW, all the back edges are removed prior to generating RTL in
gimple_expand_cfg():

      /* At the moment not all abnormal edges match the RTL
         representation.  It is safe to remove them here as
         find_many_sub_basic_blocks will rediscover them.
         In the future we should get this fixed properly.  */

I'll revisit this and see if we can resolve this.

[Bug rtl-optimization/51771] trans-mem: abnormal edges get lost or corrupted

[aldyh at gcc dot gnu.org]

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

--- Comment #9 from Aldy Hernandez <aldyh at gcc dot gnu.org> 2012-12-03 18:43:14 UTC ---
Created attachment 28862
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=28862
patch to revert the returns twice patch

[Bug rtl-optimization/51771] trans-mem: abnormal edges get lost or corrupted

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |WAITING

--- Comment #10 from Aldy Hernandez <aldyh at gcc dot gnu.org> 2012-12-03 18:51:44 UTC ---
I no longer see a Genome failure on trunk, even though we are stripping off the
abnormal edges as part of the expansion of gimple into RTL (as described in
comment 8).  Perhaps, this could be a nice side-effect of the abnormal edge
rewriting that went in with the uninstrumented path?

Can someone (Torvald or Patrick) verify this so we can close this PR if
appropriate?

For the record, this is what I've done.

I reverted the returns-twice patch by applying the patch in comment 9.

I seem to be running Stamp: 0.9.10 (8 Sept 2008) (from the VERSIONS file in the
STAMP distribution).

I am testing with current mainline as of trunk@194099.

And I am using a Makefile.local of:

CC=/build/trunk/install/bin/gcc
LDFLAGS="-Wl,-rpath=/build/trunk/install/lib64"
THREADS="4"
TESTS=test-genome

I do a "make clean && make test" and get:

cd genome && \
./genome -t "4"  && true
Creating gene and segments... done.
Gene length     = 16384
Segment length  = 64
Number segments = 16777216
Sequencing gene... done.
Time = 13.305184
Sequence matches gene: yes
Deallocating memory... done.

This seems correct.

[Bug rtl-optimization/51771] trans-mem: abnormal edges get lost or corrupted

[torvald at gcc dot gnu.org]

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

torvald at gcc dot gnu.org changed:

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

--- Comment #11 from torvald at gcc dot gnu.org 2012-12-05 19:18:42 UTC ---
I can't reproduce this anymore.  I also had a brief look at the binary code
that showed the problem previously and didn't see the problematic pattern
anymore.  So it seems that this is fixed.