[Bug libitm/61393] New: GCC TM - O3 optimization level constant propagation problem

[amatveev at csail dot mit.edu]

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