public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libitm/61393] New: GCC TM - O3 optimization level constant propagation problem
@ 2014-06-02 20:44 amatveev at csail dot mit.edu
  2014-06-03 15:48 ` [Bug ipa/61393] [trans-mem] " jamborm at gcc dot gnu.org
                   ` (8 more replies)
  0 siblings, 9 replies; 10+ messages in thread
From: amatveev at csail dot mit.edu @ 2014-06-02 20:44 UTC (permalink / raw)
  To: gcc-bugs

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

            Bug ID: 61393
           Summary: GCC TM - O3 optimization level constant propagation
                    problem
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libitm
          Assignee: unassigned at gcc dot gnu.org
          Reporter: amatveev at csail dot mit.edu

Created attachment 32884
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=32884&action=edit
The basic code of reb-black tree benchmark. Only what is required to have the
problem

Hi,


First, I describe the general problem and then I show the execution
instructions to reproduce it.

The source code, execution binary, and the disassembly of the binary are
attached to the report.


The General Problem
===================

I implement a red-black tree benchmark that uses GCC TM default mechanism (gcc
(Debian 4.8.3-2) 4.8.3).

When compiling with -O3 and -fno-inline options set, the instrumented functions
for TM have calls to "constant propagation" functions that are NOT
instrumented, and this creates an inconsistent memory views for the underlying
red-black tree.

In this specific case, the following function sets the color of a node in the
tree:

static inline void _setColor_pure (node_t * n, int color) {
  if (n != NULL) n->c = color ;
}


The color parameter can be BLACK or RED (two defines, one is equal to 0, and
one is 1). GCC (with -O3 optimization) used this info and generated the
following two constant propagation functions (one for BLACK and one for RED):

0000000000401de0 <_ZGTt14_setColor_pure.constprop.4>:
  401de0:    48 85 ff                 test   %rdi,%rdi
  401de3:    74 08                    je     401ded
<_ZGTt14_setColor_pure.constprop.4+0xd>
  401de5:    48 c7 47 28 00 00 00     movq   $0x0,0x28(%rdi)
  401dec:    00 
  401ded:    f3 c3                    repz retq 
  401def:    90                       nop

0000000000401df0 <_ZGTt14_setColor_pure.constprop.5>:
  401df0:    48 85 ff                 test   %rdi,%rdi
  401df3:    74 08                    je     401dfd
<_ZGTt14_setColor_pure.constprop.5+0xd>
  401df5:    48 c7 47 28 01 00 00     movq   $0x1,0x28(%rdi)
  401dfc:    00 
  401dfd:    f3 c3                    repz retq 
  401dff:    90                       nop


==> The problem is that this functions are not instrumented with the ITM_W8U()
call.

==> The instrumented function (also generated) looks like this:

0000000000401c20 <_ZGTt14_setColor_pure>:
  401c20:    48 85 ff                 test   %rdi,%rdi
  401c23:    74 14                    je     401c39
<_ZGTt14_setColor_pure+0x19>
  401c25:    48 83 ec 08              sub    $0x8,%rsp
  401c29:    48 63 f6                 movslq %esi,%rsi
  401c2c:    48 83 c7 28              add    $0x28,%rdi
  401c30:    e8 6b ef ff ff           callq  400ba0 <_ITM_WU8@plt>
  401c35:    48 83 c4 08              add    $0x8,%rsp
  401c39:    f3 c3                    repz retq 
  401c3b:    0f 1f 44 00 00           nopl   0x0(%rax,%rax,1)


==> The following instrumented TM function: 

00000000004023a0 <_ZGTt29fixAfterInsertion_pure.isra.0>:

==> calls for "_ZGTt14_setColor_pure.constprop.5" function, instead to the
instrumented version of setColor(..)


Execution (How to reproduce) 
============================

1. Compile by executing: ./gcc-build , this generates the "rb-tree" file.
2. Execute as follows: ./rb-tree D1 u50 d50 s10000 r10000 t8
     - D = duration in seconds
     - u = updates percentage (insert operations to the tree)
     - d = deletes percentage
     - s = initial size of the tree (in nodes)
     - r = range of keys in the tree
     - t = number of threads

3. If I execute with ITM_DEFAULT_METHOD="serialirr" => all verifications work.
4. If I execute with ITM_DEFAULT_METHOD="gl_wt" => verification fails with 
....
[INTEGRITY] Imbalance @depth=6 : 11 6
[INTEGRITY] Imbalance @depth=5 : 10 12
[INTEGRITY] Imbalance @depth=4 : 11 10
[INTEGRITY] Imbalance @depth=3 : 5 12
[INTEGRITY] Imbalance @depth=2 : 8 6
....

==> The tree is not balanced, since the colors are not updated correctly.


If you have any questions, I'm available.

Alex


^ permalink raw reply	[flat|nested] 10+ messages in thread

end of thread, other threads:[~2014-08-07 13:06 UTC | newest]

Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-06-02 20:44 [Bug libitm/61393] New: GCC TM - O3 optimization level constant propagation problem amatveev at csail dot mit.edu
2014-06-03 15:48 ` [Bug ipa/61393] [trans-mem] " jamborm at gcc dot gnu.org
2014-06-04 21:32 ` jamborm at gcc dot gnu.org
2014-06-05  9:12 ` jamborm at gcc dot gnu.org
2014-06-05  9:14 ` jamborm at gcc dot gnu.org
2014-06-05 14:30 ` jamborm at gcc dot gnu.org
2014-08-06 13:59 ` jamborm at gcc dot gnu.org
2014-08-06 14:03 ` jamborm at gcc dot gnu.org
2014-08-06 16:04 ` torvald at gcc dot gnu.org
2014-08-07 13:06 ` jamborm at gcc dot gnu.org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).