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