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

[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

[Bug ipa/61393] [trans-mem] O3 optimization level constant propagation problem

[jamborm at gcc dot gnu.org]

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

--- Comment #1 from Martin Jambor <jamborm at gcc dot gnu.org> ---
Alexander, as a temporary workaround, you can use -fno-ipa-cp.

The problem (also present in the trunk) seems to be that the tm_clone
flag of cgrapn_node is not copied over to clones (of tm_clones).
Thus, the following patch "fixes" the testcase:

diff --git a/gcc/cgraphclones.c b/gcc/cgraphclones.c
index 4387b99..056d82b 100644
--- a/gcc/cgraphclones.c
+++ b/gcc/cgraphclones.c
@@ -562,6 +562,7 @@ cgraph_create_virtual_clone (struct cgraph_node *old_node,
   set_new_clone_decl_and_node_flags (new_node);
   new_node->clone.tree_map = tree_map;
   new_node->clone.args_to_skip = args_to_skip;
+  new_node->tm_clone = old_node->tm_clone;

   /* Clones of global symbols or symbols with unique names are unique.  */
   if ((TREE_PUBLIC (old_decl)

However, I do not really know what the semantics of that flag mean so
at least for now I am not going to propose this (I am also not quite
sure this is the best place for the copy).  What properties of a
function should be maintained in order to keep it flagged as a tm
clone?

[Bug ipa/61393] [trans-mem] O3 optimization level constant propagation problem

[jamborm at gcc dot gnu.org]

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

--- Comment #2 from Martin Jambor <jamborm at gcc dot gnu.org> ---
Thinking about this more, I've come to the conclusion that on the
release branches simply disabling IPA-CP of transactional memory
clones is the best solution to this bug.  Patches for the branches
have already reached the mailing list:

https://gcc.gnu.org/ml/gcc-patches/2014-06/msg00400.html
https://gcc.gnu.org/ml/gcc-patches/2014-06/msg00401.html

However, I would very much like to avoid such simple punting on trunk
so I would appreciate if someone commented on the implications of
properly copying the tm_clone flag during cgraph_node cloning.

[Bug ipa/61393] [trans-mem] O3 optimization level constant propagation problem

[jamborm at gcc dot gnu.org]

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

--- Comment #3 from Martin Jambor <jamborm at gcc dot gnu.org> ---
Author: jamborm
Date: Thu Jun  5 09:12:14 2014
New Revision: 211259

URL: http://gcc.gnu.org/viewcvs?rev=211259&root=gcc&view=rev
Log:
2014-06-05  Martin Jambor  <mjambor@suse.cz>

    PR ipa/61393
    * ipa-cp.c (determine_versionability): Pretend that tm_clones are
    not versionable.


Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/ipa-cp.c

[Bug ipa/61393] [trans-mem] O3 optimization level constant propagation problem

[jamborm at gcc dot gnu.org]

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

--- Comment #4 from Martin Jambor <jamborm at gcc dot gnu.org> ---
Author: jamborm
Date: Thu Jun  5 09:13:56 2014
New Revision: 211260

URL: http://gcc.gnu.org/viewcvs?rev=211260&root=gcc&view=rev
Log:
2014-06-05  Martin Jambor  <mjambor@suse.cz>

    PR ipa/61393
    * ipa-cp.c (determine_versionability): Pretend that tm_clones are
    not versionable.


Modified:
    branches/gcc-4_9-branch/gcc/ChangeLog
    branches/gcc-4_9-branch/gcc/ipa-cp.c

[Bug ipa/61393] [trans-mem] O3 optimization level constant propagation problem

[jamborm at gcc dot gnu.org]

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

Martin Jambor <jamborm at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|4.8.3                       |4.10.0

--- Comment #5 from Martin Jambor <jamborm at gcc dot gnu.org> ---
OK, so this is now "fixed" on release branches but still failing on
trunk.  On trunk we'd like to fix this properly, see my comments above
bout copying tm_clone flag during cgraph_node cloning.

[Bug ipa/61393] [trans-mem] O3 optimization level constant propagation problem

[jamborm at gcc dot gnu.org]

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

--- Comment #7 from Martin Jambor <jamborm at gcc dot gnu.org> ---
Author: jamborm
Date: Wed Aug  6 13:59:18 2014
New Revision: 213666

URL: https://gcc.gnu.org/viewcvs?rev=213666&root=gcc&view=rev
Log:
2014-08-06  Martin Jambor  <mjambor@suse.cz>

    PR ipa/61393
    * cgraphclones.c (cgraph_node::create_clone): Also copy tm_clone.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/cgraphclones.c

[Bug ipa/61393] [trans-mem] O3 optimization level constant propagation problem

[jamborm at gcc dot gnu.org]

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

Martin Jambor <jamborm at gcc dot gnu.org> changed:

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

--- Comment #8 from Martin Jambor <jamborm at gcc dot gnu.org> ---
Hopefully fixed even on trunk.

[Bug ipa/61393] [trans-mem] O3 optimization level constant propagation problem

[torvald at gcc dot gnu.org]

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

--- Comment #9 from torvald at gcc dot gnu.org ---
Alex, can you confirm that this is fixed?

[Bug ipa/61393] [trans-mem] O3 optimization level constant propagation problem

[jamborm at gcc dot gnu.org]

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

--- Comment #10 from Martin Jambor <jamborm at gcc dot gnu.org> ---
(In reply to torvald from comment #9)
> Alex, can you confirm that this is fixed?

If you are asking whether the patch makes the reported testcase work
as expected then yes, it does, I have verified that.