[Bug middle-end/51752] New: trans-mem: publication safety violated

[Bug middle-end/51752] New: trans-mem: publication safety violated

[torvald at gcc dot gnu.org]

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

             Bug #: 51752
           Summary: trans-mem: publication safety violated
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: torvald@gcc.gnu.org


Created attachment 26238
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26238
publication safety test

Publication safety refers to transactions being able to safely publish data by
setting something like a shared flag (e.g., "data=23; __transaction_atomic {
flag = 1; }").  For that to work, programmers must access the data only if the
flag is true.  Second, the compiler must preserve program order in this case
and is not allowed to reorder the two loads (i.e., load data before loading the
flag).  Otherwise, there will be a race condition and the data load can return
an inconsistent value.

The attached test shows that this isn't working currently (e.g., look at
149t.optimized, the load of data is moved to out of the loop and before the
"flag" loads).

[Bug middle-end/51752] trans-mem: publication safety violated

[torvald at gcc dot gnu.org]

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

torvald at gcc dot gnu.org changed:

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

[Bug middle-end/51752] trans-mem: publication safety violated

[aldyh at gcc dot gnu.org]

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

--- Comment #1 from Aldy Hernandez <aldyh at gcc dot gnu.org> 2012-01-05 14:30:15 UTC ---
Ok, I'm a complete neophyte on this, but that seems very restrictive.  Does
that mean that basically we can't hoist any loads inside a transaction...ever?

  __transaction_atomic
    {
      for (i = 0; i < 10; i++)
        if (x[i])
          x[i] += data;
    }

[Bug middle-end/51752] trans-mem: publication safety violated

[torvald at gcc dot gnu.org]

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

torvald at gcc dot gnu.org changed:

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

--- Comment #2 from torvald at gcc dot gnu.org 2012-01-06 14:03:00 UTC ---
(In reply to comment #1)
> Ok, I'm a complete neophyte on this, but that seems very restrictive.  Does
> that mean that basically we can't hoist any loads inside a transaction...ever?
> 
>   __transaction_atomic
>     {
>       for (i = 0; i < 10; i++)
>         if (x[i])
>           x[i] += data;
>     }

We can hoist them if they are guaranteed to happen anyway.  However, if whether
the abstract machine would execute them is data-dependent on another load, the
other load must come first.  We can also hoist them if they are never published
by anyone else, or never written to nontransactionally by other threads
(constant data, thread-local data, etc.).

In the example, "data" might never be accessed.  But if it would be accessed
after the loop anyway, for example, then we can hoist it to before the loop. 
This is possible because we can assume that the program is data-race-free in
the first place, and if a load is going to happen anyway, we can assume that
the transaction could also run before the other thread's writes to x[i], the
other thread isn't publishing "data", and so there must be no race condition
(and thus, no difference) even if we hoist the load.

Note that if we would synchronize with atomics instead of transactions, the
programmer would need to specify at least acquire memory order for the load of
x[i] to prevent a data race.

[Bug middle-end/51752] trans-mem: publication safety violated

[aldyh at gcc dot gnu.org]

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

--- Comment #3 from Aldy Hernandez <aldyh at gcc dot gnu.org> 2012-02-09 16:23:57 UTC ---
Created attachment 26622
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26622
proposed (untested) patch

This is a first stab at the problem.  It is untested, and there are definitely
other places that will be perform loads behind our back, but this seems to work
for the test at hand.

The main gist is saving all blocks that appear in a transaction so later we can
know if the load being hoisted is inside a transaction.  Then we use ANTIC sets
to determine if all paths out of the loop header perform the load.  If so, the
load is permitted.

Again, untested WIP, but hopefully on the right track.

[Bug middle-end/51752] trans-mem: publication safety violated

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-02-09 16:43:40 UTC ---
But isn't with

  __transaction_atomic
    {
      for (i = 0; i < 10; i++)
        if (x[i])
          x[i] += data;
    }

and

  __transaction_atomic { x[9] = 1; }

occuring concurrently the loop transaction terminated?  Thus,

  __transaction_atomic
    {
      tem = data;
      for (i = 0; i < 10; i++)
        if (x[i])
          x[i] += tem;
    }

equivalent?  We don't hoist out of the transaction region (well, as far
as I can see - the transaction region seems to be specified in a very
weak way, without virtual operands or any IL barrier or such).

<bb 2>:
  # .MEM_2 = VDEF <.MEM_1(D)>
  data = 23;
  __transaction_atomic  // SUBCODE=[ GTMA_HAVE_STORE ]

<bb 3>:
  # .MEM_3 = VDEF <.MEM_2>
  x[9] = 1;
  # .MEM_4 = VDEF <.MEM_3>
  __builtin__ITM_commitTransaction ();

<bb 4>:
  # VUSE <.MEM_4>
  return;

the __transaction_atomic  // SUBCODE=[ GTMA_HAVE_STORE ] statement
looks like an overly optimistic way to start a transaction in my quick view.

[Bug middle-end/51752] trans-mem: publication safety violated

[rth at gcc dot gnu.org]

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

--- Comment #5 from Richard Henderson <rth at gcc dot gnu.org> 2012-02-09 17:39:51 UTC ---
(In reply to comment #4)
> But isn't with
> 
>   __transaction_atomic
>     {
>       for (i = 0; i < 10; i++)
>         if (x[i])
>           x[i] += data;
>     }
> 
> and
> 
>   __transaction_atomic { x[9] = 1; }
> 
> occuring concurrently the loop transaction terminated?

The problem we want to fix is not wrt x[], but data.

Consider x[0..10] == 0, and another thread with

  while (1)
    __transaction_atomic { data += 1; }

If we hoist data in the first transaction, then we're very
likely to restart the transaction based on stale contents
of data, even when we ought not have touched data at all.

I.e. we can wind up looping even when we ought to be making
forward progress.

> We don't hoist out of the transaction region (well, as far
> as I can see - the transaction region seems to be specified in a very
> weak way, without virtual operands or any IL barrier or such).

It was supposed to have virtual operands.  It really did at one
time, but that seems to have gotten lost.  I noticed this with
another PR a week or so ago, but havn't gotten around to fixing it.

[Bug middle-end/51752] trans-mem: publication safety violated

[torvald at gcc dot gnu.org]

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

--- Comment #6 from torvald at gcc dot gnu.org 2012-02-09 18:40:49 UTC ---
(In reply to comment #4)
> But isn't with
> 
>   __transaction_atomic
>     {
>       for (i = 0; i < 10; i++)
>         if (x[i])
>           x[i] += data;
>     }
> 
> and
> 

prepend with the following for thread B:

  data = 123;

>   __transaction_atomic { x[9] = 1; }
> 
> occuring concurrently the loop transaction terminated?  Thus,
> 
>   __transaction_atomic
>     {
>       tem = data;
>       for (i = 0; i < 10; i++)
>         if (x[i])
>           x[i] += tem;
>     }
> 
> equivalent?

No.  It might be for typical HTMs, but we can't expect this in the general
case.  The interleaving that can then happen is (with A and B being the two
concurrent threads):

  B: tem = data;  // reads initial value of zero
  A: data = 123;
  A: __transaction_atomic { x[9] = 1; }
  B: if (x[i])
  B:   x[i] += tem;  // adds zero, not 123.

The problem here is that B's store to data is nontransactional, and we cannot
add synchronization code for those (it might be library code, for example).

We could add a partial workaround to libitm that would reduce this case here to
"just" a racing load.  However, that would kill performance because basically,
B's transaction would have to wait for all earlier-started transactions before
it can start executing.  The racing load can still be a problem if we hoist
dereferencing a pointer.

We don't see this example with other concurrent code because there, the load of
x[] would have to be a synchronizing operation, and we don't hoist across
these.

[Bug middle-end/51752] trans-mem: publication safety violated

[aldyh at gcc dot gnu.org]

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

--- Comment #7 from Aldy Hernandez <aldyh at gcc dot gnu.org> 2012-02-28 20:08:44 UTC ---
Author: aldyh
Date: Tue Feb 28 20:08:39 2012
New Revision: 184638

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=184638
Log:
        PR middle-end/51752
        * gimple.h (gimple_in_transaction): New.
        (gimple_set_in_transaction): New.
        (struct gimple_statement_base): Add in_transaction field.
        * tree-ssa-loop-im.c: (movement_possibility): Restrict movement of
        transaction loads.
        (tree_ssa_lim_initialize): Compute transaction bits.
        * tree.h (compute_transaction_bits): Protoize.
        * trans-mem.c (tm_region_init): Use the heap to store BB
        auxilliary data.
        (compute_transaction_bits): New.


Added:
    trunk/gcc/testsuite/gcc.dg/tm/pub-safety-1.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/gimple.h
    trunk/gcc/trans-mem.c
    trunk/gcc/tree-ssa-loop-im.c

[Bug middle-end/51752] trans-mem: publication safety violated

[aldyh at gcc dot gnu.org]

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

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

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

--- Comment #8 from Aldy Hernandez <aldyh at gcc dot gnu.org> 2012-03-16 18:44:53 UTC ---
The committed patch on trunk and on the 4.7 branch resolves all the known
issues.  I can't come up with any more reproducible testcases for publication
safety.  If we find any, let's open a new PR naming the offending pass.