This is an archive of the discontinued LLVM Phabricator instance.

[OPENMP] Codegen for 'atomic capture'.
ClosedPublic

Authored by ABataev on Apr 16 2015, 2:47 AM.

Details

Summary

Adds codegen for 'atomic capture' constructs with the following forms of expressions/statements:

v = x binop= expr;
v = x++;
v = ++x;
v = x--;
v = --x;
v = x = x binop expr;
v = x = expr binop x;
{v = x; x = binop= expr;}
{v = x; x++;}
{v = x; ++x;}
{v = x; x--;}
{v = x; --x;}
{x = x binop expr; v = x;}
{x binop= expr; v = x;}
{x++; v = x;}
{++x; v = x;}
{x--; v = x;}
{--x; v = x;}
{x = x binop expr; v = x;}
{x = expr binop x; v = x;}
{v = x; x = expr;}

If x and expr are integer and binop is associative or x is a LHS in a RHS of the assignment expression, and atomics are allowed for type of x on the target platform atomicrmw instruction is emitted.
Otherwise compare-and-swap sequence is emitted.
Update of 'v' is not required to be be atomic with respect to the read or write of the 'x'.

bb:
...
atomic load <x>
cont:
<expected> = phi [ <x>, label %bb ], [ <new_failed>, %cont ]
<desired> = <expected> binop <expr>
<res> = cmpxchg atomic &<x>, desired, expected
<new_failed> = <res>.field1;
br <res>field2, label %exit, label %cont
exit:
atomic store <old/new x>, <v>
...

If 'x' was updated with `atomicrmw``` instruction and 'v' must be updated with the new value of 'x', an additional atomic load of 'x' is used to read the new value to be stored to 'v'. Otherwise previous value of 'x', returned by atomic instruction is used (if 'v' must be rewritten by the old value of 'x'), or newly calculated update value for 'x' is used (if 'v' must be rewritten by the new value of 'x').

Diff Detail

Event Timeline

ABataev updated this revision to Diff 23834.Apr 16 2015, 2:47 AM
ABataev retitled this revision from to [OPENMP] Codegen for 'atomic capture'..
ABataev updated this object.
ABataev edited the test plan for this revision. (Show Details)
ABataev added a subscriber: Unknown Object (MLST).
ABataev updated this object.Apr 16 2015, 2:57 AM
rjmccall edited edge metadata.Apr 21 2015, 10:29 AM

The code seems fine, but I'm pretty concerned about the semantics.

lib/CodeGen/CGStmtOpenMP.cpp
1685

Unfortunately, this makes the operation no longer atomic.

1700

So, this separate store makes the entire operation decidedly non-atomic. If the store to 'y' needs to be atomic with the rest, then this is an atomic operation across multiple locations and cannot be done locklessly. If it doesn't need to be — if only 'x' needs to be accessed atomically — then you should not do an atomic store here.

John, according to the standard 'Only the read and write of
the location designated by x are performed mutually atomically. Neither the evaluation
of expr or expr_list, nor the write to the location designated by v need be atomic with
respect to the read or write of the location designated by x.'
I think this means, that store to 'v' must be atomic too, but it does not required to be synchronized with read/update of 'x'. So, I think we can use atomic load of 'x' after atomicrmw for 'x' and we can use atomic store of old/new value of 'x' to 'v' after atomic update of 'x'.

John, according to the standard 'Only the read and write of
the location designated by x are performed mutually atomically. Neither the evaluation
of expr or expr_list, nor the write to the location designated by v need be atomic with
respect to the read or write of the location designated by x.'
I think this means, that store to 'v' must be atomic too, but it does not required to be synchronized with read/update of 'x'. So, I think we can use atomic load of 'x' after atomicrmw for 'x' and we can use atomic store of old/new value of 'x' to 'v' after atomic update of 'x'.

I pulled up the standard, and it doesn't make any atomicity guarantees about 'v' at all. That's what that paragraph is trying to say: that the only atomicity requirement here is that all of the operations on 'x' have to appear as if they were executed atomically. There's no reason to make the store to 'v' atomic.

The whole point of "atomic capture" is that 'v' gets either the result or the original value of x, atomically as part of the evaluation of the operation; otherwise you wouldn't need a separate form for this. That means it has to be evaluated as part of the actual operation, not as a separate load. If atomicrmw doesn't generate that information, you'll have to expand it to a compare-and-swap yourself.

John, I re-read the standard and I think you're right., store to 'v' must not be atomic. As to atomicrmw instruction, I think we can re-evaluate new value of 'x' variable using previous value, returned by atomicrmw instruction, and update expression for 'x'. I'll send and updated patch in a few minutes

ABataev updated this revision to Diff 24266.Apr 22 2015, 10:34 PM
ABataev edited edge metadata.

Fixed codegen for new value of 'x' after atomicrmw + store to 'v' now is not atomic

Thank you, looks good.

This revision was automatically updated to reflect the committed changes.