[LLVMdev] RFC: Convergent attribute

[Mehdi Amini]

> On May 14, 2015, at 8:33 AM, Mehdi Amini <mehdi.amini at apple.com> wrote:
> 
>> 
>> On May 13, 2015, at 6:00 PM, Philip Reames <listmail at philipreames.com> wrote:
>> 
>> LGTM.  Please put pretty much everything in this email into a documentation page.  Doesn't have to be LangRef, but definitely something linked from there.
>> 
>> Also, it would be good to explicitly say that this is working around a limitation in the register allocator.  Just because it's a limitation which would be very hard to address doesn't mean it isn't a limitation.  :)
> 
> Only a subset of the problem (architecture specific) can be addressed by a “clever” register allocator I think. The general problem goes beyond.

Thinking more about it, the example I had in mind was wrong and I can’t find one right now, I retract what I said :)

— 
Mehdi


>> 
>> Philip
>> 
>> On 05/13/2015 01:17 PM, Owen Anderson wrote:
>>> Below is a proposal for a new "convergent" intrinsic attribute and MachineInstr property, needed for correctly modeling many SPMD/SIMT programming models in LLVM.  Comments and feedback welcome.
>>> 
>>> —Owen
>>> 
>>> 
>>> 
>>> 
>>> 
>>> In order to make LLVM more suitable for programming models variously called SPMD
>>> and SIMT, we would like to propose a new intrinsic and MachineInstr annotation
>>> called "convergent", which will be used to impose certain control flow and/or
>>> code motion constraints that are necessary for the correct compilation of some
>>> common constructs in these programming models.
>>> 
>>> Our proposal strives to define the semantics of these annotations *without*
>>> introducing a definition of SPMD/SIMT programming models into LLVM IR.  Rather,
>>> the properties that must be preserved are specified purely in terms of single
>>> thread semantics.  This allows pass authors to reason about the constraints
>>> without having to consider alternative programming models.  The downside to
>>> this approach is that the motivation and necessity of these constraints in not
>>> easily understood without understanding the programming model from which they
>>> derive.
>>> 
>>> *** WHAT ***
>>> 
>>> (Thanks to Phil Reames for input on this definition.)
>>> 
>>> An operation marked convergent may be transformed or moved within the program
>>> if and only the post-transform placement of the convergent operation is
>>> control equivalent (A dominated B, B post-dominates A, or vice-versa) to
>>> its original position.
>>> 
>>> This definition is overly strict with respect to some SPMD/SIMT models,
>>> but cannot be relaxed without introducing a specific model into LLVM IR. We
>>> believe it is important for LLVM itself to remain agnostic to any specific
>>> model.  This allows core passes to preserve correctness for stricter models,
>>> while more relaxed models can implement additional transforms that use
>>> weaker constraints on top of core LLVM.
>>> 
>>> *** HOW ***
>>> 
>>> Once the attribute has been added, we anticipate the following changes to
>>> optimization passes will be required:
>>>  - Restrict Sink and MachineSink for convergent operations
>>>  - Disabling PRE for convergent operations
>>>  - Disabling jump threading of convergent operations
>>>  - Auditing SimplifyCFG for additional transforms that break convergent guarantees
>>> 
>>> *** WHY ***
>>> 
>>> SPMD/SIMT programming models are a family of related programming models in
>>> which multiple threads execute in a per-instruction lockstep fashion.
>>> Predication is typically used to implement acyclic control flow that would
>>> otherwise diverge the PC address of the lockstep threads.
>>> 
>>> In these models, each thread's register set is typically indepedent, but there
>>> exist a small number of important circumstances in which a thread may access
>>> register storage from one of its lockstep neighbors.  Examples include gradient
>>> computation for texture lookups, as well a cross-thread broadcast and shuffle
>>> operations.
>>> 
>>> These operations that provide access to another thread's register storage pose
>>> a particular challenge to the compiler, particularly when combined with the
>>> use of predication for control flow.  Consider the following example:
>>> 
>>> // texture lookup that computes gradient of r0, last use of r0
>>> r1 = texture2D(..., r0, ...)
>>> if (...) {
>>>  // r0 used as temporary here
>>>  r0 = ...
>>>  r2 = r0 + ...
>>> } else {
>>>  // only use of r1
>>>  r2 = r1 + ...
>>> }
>>> 
>>> In this example, various optimizations might try to sink the texture2D operation
>>> into the else block, like so:
>>> 
>>> if (...) {
>>>  r0 = ...
>>>  r2 = r0 + ...
>>> } else {
>>>  r1 = texture2D(..., r0, ...)
>>>  r2 = r1 + ...
>>> }
>>> 
>>> At this point, it starts to become clear that a problem can occur when two
>>> neighbor threads want to take different paths through the if-else construct.
>>> Logically, the thread that wishes to execute the texture2D races with its
>>> neighbor to reads the neighbor's value of r0 before it gets overridden.
>>> 
>>> In most SPMD/SIMT implementations, the fallout of this races is exposed via
>>> the predicated expression of acyclic control flow:
>>> 
>>> pred0 <- cmp ...
>>> if (pred0)  r0 = ...
>>> if (pred0)  r2 = r0 + ...
>>> if (!pred0) r1 = texture2D(..., r0, ...)
>>> if (!pred0) r2 = r1 + ...
>>> 
>>> If thread 0 takes the else path and perform the texture2D operation, but
>>> its neighbor thread 1 takes the then branch, then the texture2D will fail
>>> because thread 1 has already overwritten its value of r0 before thread 0 has
>>> a chance to read it.
>>> 
>>> 
>>> 
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev