* [Bug middle-end/51752] trans-mem: publication safety violated
2012-01-04 14:18 [Bug middle-end/51752] New: trans-mem: publication safety violated torvald at gcc dot gnu.org
@ 2012-01-04 19:18 ` torvald at gcc dot gnu.org
2012-01-05 14:30 ` aldyh at gcc dot gnu.org
` (7 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: torvald at gcc dot gnu.org @ 2012-01-04 19:18 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/51752] trans-mem: publication safety violated
2012-01-04 14:18 [Bug middle-end/51752] New: trans-mem: publication safety violated torvald at gcc dot gnu.org
2012-01-04 19:18 ` [Bug middle-end/51752] " torvald at gcc dot gnu.org
@ 2012-01-05 14:30 ` aldyh at gcc dot gnu.org
2012-01-06 14:03 ` torvald at gcc dot gnu.org
` (6 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: aldyh at gcc dot gnu.org @ 2012-01-05 14:30 UTC (permalink / raw)
To: gcc-bugs
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;
}
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/51752] trans-mem: publication safety violated
2012-01-04 14:18 [Bug middle-end/51752] New: trans-mem: publication safety violated torvald at gcc dot gnu.org
2012-01-04 19:18 ` [Bug middle-end/51752] " torvald at gcc dot gnu.org
2012-01-05 14:30 ` aldyh at gcc dot gnu.org
@ 2012-01-06 14:03 ` torvald at gcc dot gnu.org
2012-02-09 16:24 ` aldyh at gcc dot gnu.org
` (5 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: torvald at gcc dot gnu.org @ 2012-01-06 14:03 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/51752] trans-mem: publication safety violated
2012-01-04 14:18 [Bug middle-end/51752] New: trans-mem: publication safety violated torvald at gcc dot gnu.org
` (2 preceding siblings ...)
2012-01-06 14:03 ` torvald at gcc dot gnu.org
@ 2012-02-09 16:24 ` aldyh at gcc dot gnu.org
2012-02-09 16:44 ` rguenth at gcc dot gnu.org
` (4 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: aldyh at gcc dot gnu.org @ 2012-02-09 16:24 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/51752] trans-mem: publication safety violated
2012-01-04 14:18 [Bug middle-end/51752] New: trans-mem: publication safety violated torvald at gcc dot gnu.org
` (3 preceding siblings ...)
2012-02-09 16:24 ` aldyh at gcc dot gnu.org
@ 2012-02-09 16:44 ` rguenth at gcc dot gnu.org
2012-02-09 17:40 ` rth at gcc dot gnu.org
` (3 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: rguenth at gcc dot gnu.org @ 2012-02-09 16:44 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/51752] trans-mem: publication safety violated
2012-01-04 14:18 [Bug middle-end/51752] New: trans-mem: publication safety violated torvald at gcc dot gnu.org
` (4 preceding siblings ...)
2012-02-09 16:44 ` rguenth at gcc dot gnu.org
@ 2012-02-09 17:40 ` rth at gcc dot gnu.org
2012-02-09 18:41 ` torvald at gcc dot gnu.org
` (2 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: rth at gcc dot gnu.org @ 2012-02-09 17:40 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/51752] trans-mem: publication safety violated
2012-01-04 14:18 [Bug middle-end/51752] New: trans-mem: publication safety violated torvald at gcc dot gnu.org
` (5 preceding siblings ...)
2012-02-09 17:40 ` rth at gcc dot gnu.org
@ 2012-02-09 18:41 ` torvald at gcc dot gnu.org
2012-02-28 20:10 ` aldyh at gcc dot gnu.org
2012-03-16 19:15 ` aldyh at gcc dot gnu.org
8 siblings, 0 replies; 10+ messages in thread
From: torvald at gcc dot gnu.org @ 2012-02-09 18:41 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/51752] trans-mem: publication safety violated
2012-01-04 14:18 [Bug middle-end/51752] New: trans-mem: publication safety violated torvald at gcc dot gnu.org
` (6 preceding siblings ...)
2012-02-09 18:41 ` torvald at gcc dot gnu.org
@ 2012-02-28 20:10 ` aldyh at gcc dot gnu.org
2012-03-16 19:15 ` aldyh at gcc dot gnu.org
8 siblings, 0 replies; 10+ messages in thread
From: aldyh at gcc dot gnu.org @ 2012-02-28 20:10 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug middle-end/51752] trans-mem: publication safety violated
2012-01-04 14:18 [Bug middle-end/51752] New: trans-mem: publication safety violated torvald at gcc dot gnu.org
` (7 preceding siblings ...)
2012-02-28 20:10 ` aldyh at gcc dot gnu.org
@ 2012-03-16 19:15 ` aldyh at gcc dot gnu.org
8 siblings, 0 replies; 10+ messages in thread
From: aldyh at gcc dot gnu.org @ 2012-03-16 19:15 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 10+ messages in thread