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
