llvm dev - Dec 2014 - [LLVMdev] [RFC][PATCH][OPENCL] synchronization scopes redux

Hi all,

Attached is a sequence of patches that changes the IR to support more 
than two synchronization scopes. This is still a work in progress, and 
these patches are only meant to start a more detailed discussion on the 
way forward.

One big issue is the absence of any backend that actually makes use of 
intermediate synchronization scopes. This work is meant to be just one 
part of the ground work required for landing the much-anticipated HSAIL 
backend. Also, more work might be needed for emitting atomic 
instructions via Clang.

The proposed syntax for synchronization scope is as follows:

 1. Synchronization scopes are of arbitrary width, but implemented as
    unsigned in the bitcode, just like address spaces.
 2. Cross-thread is default, but now encoded as 0.
 3. Keyword 'singlethread' is unchanged, but now encoded as the largest
    integer (which happens to be ~0U in bitcode).
 4. New syntax "synchscope(n)" for other scopes.
 5. There is no keyword for cross-thread, but it can be specified as
    "synchscope(0)".

This change breaks forward compatibility for the bitcode, since the 
meaning of the zero/one values are now changed.

  enum SynchronizationScope {
-  SingleThread = 0,
-  CrossThread = 1
+  CrossThread = 0,
+  SingleThread = ~0U
  };

The change passes almost all lit tests including one new test (see patch 
0005). The failing tests are specifically checking for forward 
compatibility:

Failing Tests (3):
     LLVM :: Bitcode/cmpxchg-upgrade.ll
     LLVM :: Bitcode/memInstructions.3.2.ll
     LLVM :: Bitcode/weak-cmpxchg-upgrade.ll

This breakage remains even if we reverse the order of synchronization 
scopes. One simple way to preserve compatibility is to retain 0 and 1 
with their current meanings, and specify that intermediate scopes are 
represented in an ordered way with numbers greater than one. But this is 
pretty ugly to work with. Would appreciate inputs on how to fix this!

Sameer.

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141211/5746b487/attachment.html>
-------------- next part --------------

On 12/11/2014 4:28 PM, Sahasrabuddhe, Sameer wrote:
>
> Attached is a sequence of patches that changes the IR to support more 
> than two synchronization scopes. This is still a work in progress, and 
> these patches are only meant to start a more detailed discussion on 
> the way forward.
>
Ping!

Found a simple way to preserve forward compatibility. See below.
> One big issue is the absence of any backend that actually makes use of 
> intermediate synchronization scopes. This work is meant to be just one 
> part of the ground work required for landing the much-anticipated 
> HSAIL backend. Also, more work might be needed for emitting atomic 
> instructions via Clang.
>
> The proposed syntax for synchronization scope is as follows:
>
>  1. Synchronization scopes are of arbitrary width, but implemented as
>     unsigned in the bitcode, just like address spaces.
>  2. Cross-thread is default, but now encoded as 0.
>  3. Keyword 'singlethread' is unchanged, but now encoded as the
>     largest integer (which happens to be ~0U in bitcode).
>  4. New syntax "synchscope(n)" for other scopes.
>  5. There is no keyword for cross-thread, but it can be specified as
>     "synchscope(0)".
>
> This change breaks forward compatibility for the bitcode, since the 
> meaning of the zero/one values are now changed.
>
>  enum SynchronizationScope {
> -  SingleThread = 0,
> -  CrossThread = 1
> +  CrossThread = 0,
> +  SingleThread = ~0U
>  };
>
> The change passes almost all lit tests including one new test (see 
> patch 0005). The failing tests are specifically checking for forward 
> compatibility:
>
> Failing Tests (3):
>     LLVM :: Bitcode/cmpxchg-upgrade.ll
>     LLVM :: Bitcode/memInstructions.3.2.ll
>     LLVM :: Bitcode/weak-cmpxchg-upgrade.ll
>
> This breakage remains even if we reverse the order of synchronization 
> scopes. One simple way to preserve compatibility is to retain 0 and 1 
> with their current meanings, and specify that intermediate scopes are 
> represented in an ordered way with numbers greater than one. But this 
> is pretty ugly to work with. Would appreciate inputs on how to fix this!
>
The issue here is purely in the bitcode, and we need an encoding that 
can represent new intermediate scopes while preserving the two known 
values of zero and one. Note that the earlier zero is now ~0U in the 
in-memory representation, and the earlier 1 is now zero. This mapping 
can be easily accomplished with a simple increment/decrement by one, 
ignoring overflow. So the bitreader now subtracts a one when decoding 
the synch scope, and bitwriter adds a one when encoding the synch scope. 
The attached change number 0006 is meant to replace changes 0003 and 
0005 in the previous list, since the assembly and the bitcode need to be 
updated simultaneously for this to work.

The new change passes all tests, including the ones checking for forward 
compatibility.

Sameer.

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141212/bcb5048a/attachment.html>
-------------- next part --------------

I've not had a good chance to look at the patches in detail, but just to
clarify one point:

I don't really care whether we number things going up or down from single
threaded to "every thread". I just think it makes sense to expose them
in
the in-memory IR interface as an enum with a particular ordering so that
code can use the obvious sorts of tests for comparing two orderings and not
have to worry (overly much) about edge cases. This doesn't really need to
be reflected in the bitcode encoding though, so I'm fine with whatever
steps are needed to keep the bitcode compatible and sane.

I also agree with having the text format use a symbolic thing for both
extremes. It doesn't seem super important, but it seems nice.

Regarding the bitcode encoding, I would consider whether one encoding is
more space efficient than another. I don't recall whether we default to
zero or whether we use a varint encoding in the bitcode here, but if we do,
it would make sense to optimize the encoding around cross thread being the
most common. I'm not really a bitcode expert, so I'd rather defer to
someone who has hacked on this part of LLVM more recently there.

I can try to take a look at the higher level patches soon though.

On Fri, Dec 12, 2014 at 10:25 AM, Sahasrabuddhe, Sameer <
sameer.sahasrabuddhe at amd.com> wrote:
>
> On 12/11/2014 4:28 PM, Sahasrabuddhe, Sameer wrote:
>
>
> Attached is a sequence of patches that changes the IR to support more than
> two synchronization scopes. This is still a work in progress, and these
> patches are only meant to start a more detailed discussion on the way
> forward.
>
>
> Ping!
>
> Found a simple way to preserve forward compatibility. See below.
>
>  One big issue is the absence of any backend that actually makes use of
> intermediate synchronization scopes. This work is meant to be just one part
> of the ground work required for landing the much-anticipated HSAIL backend.
> Also, more work might be needed for emitting atomic instructions via Clang.
>
> The proposed syntax for synchronization scope is as follows:
>
>    1. Synchronization scopes are of arbitrary width, but implemented as
>    unsigned in the bitcode, just like address spaces.
>    2. Cross-thread is default, but now encoded as 0.
>     3. Keyword 'singlethread' is unchanged, but now encoded as the
>    largest integer (which happens to be ~0U in bitcode).
>     4. New syntax "synchscope(n)" for other scopes.
>    5. There is no keyword for cross-thread, but it can be specified as
>    "synchscope(0)".
>
> This change breaks forward compatibility for the bitcode, since the
> meaning of the zero/one values are now changed.
>
>  enum SynchronizationScope {
> -  SingleThread = 0,
> -  CrossThread = 1
> +  CrossThread = 0,
> +  SingleThread = ~0U
>  };
>
> The change passes almost all lit tests including one new test (see patch
> 0005). The failing tests are specifically checking for forward
> compatibility:
>
> Failing Tests (3):
>     LLVM :: Bitcode/cmpxchg-upgrade.ll
>     LLVM :: Bitcode/memInstructions.3.2.ll
>     LLVM :: Bitcode/weak-cmpxchg-upgrade.ll
>
> This breakage remains even if we reverse the order of synchronization
> scopes. One simple way to preserve compatibility is to retain 0 and 1 with
> their current meanings, and specify that intermediate scopes are
> represented in an ordered way with numbers greater than one. But this is
> pretty ugly to work with. Would appreciate inputs on how to fix this!
>
>
> The issue here is purely in the bitcode, and we need an encoding that can
> represent new intermediate scopes while preserving the two known values of
> zero and one. Note that the earlier zero is now ~0U in the in-memory
> representation, and the earlier 1 is now zero. This mapping can be easily
> accomplished with a simple increment/decrement by one, ignoring overflow.
> So the bitreader now subtracts a one when decoding the synch scope, and
> bitwriter adds a one when encoding the synch scope. The attached change
> number 0006 is meant to replace changes 0003 and 0005 in the previous list,
> since the assembly and the bitcode need to be updated simultaneously for
> this to work.
>
> The new change passes all tests, including the ones checking for forward
> compatibility.
>
> Sameer.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141223/c884c0c6/attachment.html>