[Bug middle-end/51752] trans-mem: publication safety violated
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.
[Bug middle-end/51752] trans-mem: publication safety violated
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=gccview=revrev=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
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
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
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
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
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
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
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
