<html><head></head><body><div class="ydpf968d0adyahoo-style-wrap" style="font-family:Helvetica Neue, Helvetica, Arial, sans-serif;font-size:13px;"><div></div>
<div><br></div><div>I was looking into ballot() and how if it is possible to keep a single-threaded</div><div>view of the code, but add some extra conditions that must hold after the <br></div><div>transformation. I had the initial idea that each call to ballot() in a</div><div> single-threaded program can be seen as a partial write to a memory <br></div><div>location, and each location memory location is unique for every call site,</div><div> plus there some externally observable side effect. We can abstract this</div><div> away by tagging the calls, e.g. by using aliases.</div><div><br> </div><div>For example:<br></div><div><br></div><div><span>if (...) {<br clear="none"> foo1 = ballot();<br clear="none">} else {<br clear="none"> foo2 = ballot();<br clear="none">}</span></div><div><br></div><div>simply becomes:<br></div><div><br></div><div><span><div><span>if (...) {<br clear="none"> foo1 = ballot_1();<br clear="none">} else {<br clear="none"> foo2 = ballot_2();<br clear="none">}</span></div><div><br></div></span><div><br></div><div>and</div><div><br></div><div>if (...) {</div><div>} else {</div><div>}</div><div>ballot();</div><div><br></div><div>becomes<br></div><div><br></div><div><span><div>if (...) {</div><div>} else {</div><div>}</div><div>ballot_1();</div></span></div><div><br></div><div>In the first case it would prevent combining the two calls into one</div><div>after the if. In the second example there is generally nothing that</div><div> says it could not be transformed into the first example with two</div><div> calls to ballot_1(), which should not be allowed.<br></div><div><br></div><div>Another form of duplication that we must allow are loop transforms,</div><div>like unrolling or peeling. These might seem similar to the example</div><div> above, since we are cloning code and with conditions etc. But</div><div>they are different since they calls are in different loop iterations. <br></div><div><br></div><div>The condition that needs to be met is that:</div><div><br></div><div>There must be a single path between all cloned ballot_n() functions.</div><div><br></div><div>The reason for this condition is that if we clone the same call, then</div><div>the copies must be mutually exclusive, but if they are cloned from</div><div> a loop, there must be a path, or we would skip iterations. <br></div><div><br></div><div>If we want to be more sophisticated we can add:<br></div><div><br></div><div>If there is no such path, the calls must be separated by uniform branches.</div><div><br></div><div>After the transform everything should be re-tagged, since we already</div><div> checked the calls and we don't want to check them again. Also, not all</div><div> transforms need (or should) have the tagging checked. One example is</div><div> inlining, where multiple copies are created, but they are clearly different</div><div> calls. The tagging can be done temporarily for a single pass, and then</div><div> eliminated. This could be a good tool for debugging as well, since it can</div><div> detect if a transform is suspect.<br></div><div><br></div><div>The code would of course have to make sense as far as control flow. If</div><div> we have:</div><div><br></div><div>for(;;) {</div><div> if(...) { <br></div><div> ballot();</div><div> break;<br></div><div> }<br></div><div>}<br></div><div><br></div><div>This would have to be translated to:</div><div><br></div><div>for(;;) {</div><div> if(...) {</div><div> ballot();</div><div> if(UnknownConstant) { // Not a uniform condition, but later on translated to "true"<br></div><div> break;<br></div><div> } </div><div>}<br></div><div><br></div><div>However, I think that this is the way the code is generated today anyway.</div><div> There would have to be some attribute that indicate that these calls (or functions)</div><div>contain ballot or other cross-lane operations so they could be tagged and</div><div> checked. The attribute would be used by the passes to know that the special</div><div>conditions exist for those calls.<br></div><div><br></div><div>As far as what it means to have a path, it could be complicated.</div><div>For example:</div><div><br></div><div>x = ...</div><div>ballot_1();</div><div><br></div><div>could be transformed to:</div><div><br></div><div>if (x < 4711) {</div><div> ballot_1();</div><div><br></div><div>if(x >= 4711) {</div><div> ballot_1();<br></div><div>}<br></div><div><br></div><div>So a simple path check would say there is a path, and the transform is legal,</div><div>but if we examine the conditions, there is no path, and the transform should not be legal.</div><div>It could be made even more obscure of course, but I don't see any optimizations really</div><div>doing this kind of thing,<br></div><div><br></div><div>- Jan<br></div><div><br></div></div>
</div><div id="ydp43cda87byahoo_quoted_9251906991" class="ydp43cda87byahoo_quoted">
<div style="font-family:'Helvetica Neue', Helvetica, Arial, sans-serif;font-size:13px;color:#26282a;">
<div>
On Saturday, December 29, 2018, 11:32:25 AM EST, Nicolai Hähnle via llvm-dev <llvm-dev@lists.llvm.org> wrote:
</div>
<div><br></div>
<div><br></div>
<div><div dir="ltr">On 20.12.18 18:03, Connor Abbott wrote:<br clear="none">> We already have the notion of "convergent" functions like<br clear="none">> syncthreads(), to which we cannot add control-flow dependencies. <br clear="none">> That is, it's legal to hoist syncthreads out of an "if", but it's<br clear="none">> not legal to sink it into an "if". It's not clear to me why we<br clear="none">> can't have "anticonvergent" (terrible name) functions which cannot<br clear="none">> have control-flow dependencies removed from them? ballot() would be<br clear="none">> both convergent and anticonvergent.<br clear="none">> <br clear="none">> Would that solve your problem?<br clear="none">> <br clear="none">> <br clear="none">> I think it's important to note that we already have such an attribute, <br clear="none">> although with the opposite sense - it's impossible to remove control <br clear="none">> flow dependencies from a call unless you mark it as "speculatable". <br clear="none"><br clear="none">This isn't actually true. If both sides of an if/else have the same <br clear="none">non-speculative function call, it can still be moved out of control flow.<br clear="none"><br clear="none">That's because doing so doesn't change anything at all from a <br clear="none">single-threaded perspective. Hence why I think we should model the <br clear="none">communication between threads honestly.<br clear="none"><br clear="none"><br clear="none">> However, this doesn't prevent<br clear="none">> <br clear="none">> if (...) {<br clear="none">> } else {<br clear="none">> }<br clear="none">> foo = ballot();<br clear="none">> <br clear="none">> from being turned into<br clear="none">> <br clear="none">> if (...) {<br clear="none">> foo1 = ballot();<br clear="none">> } else {<br clear="none">> foo2 = ballot();<br clear="none">> }<br clear="none">> foo = phi(foo1, foo2)<br clear="none">> <br clear="none">> and vice versa. We have a "noduplicate" attribute which prevents <br clear="none">> transforming the first into the second, but not the other way around. Of <br clear="none">> course we could keep going this way and add a "nocombine" attribute to <br clear="none">> complement noduplicate. But even then, there are even still problematic <br clear="none">> transforms. For example, take this program, which is simplified from a <br clear="none">> real game that doesn't work with the AMDGPU backend:<br clear="none">> <br clear="none">> while (cond1 /* uniform */) {<br clear="none">> ballot();<br clear="none">> ...<br clear="none">> if (cond2 /* non-uniform */) continue;<br clear="none">> ...<br clear="none">> }<br clear="none">> <br clear="none">> In SPIR-V, when using structured control flow, the semantics of this are <br clear="none">> pretty clearly defined. In particular, there's a continue block after <br clear="none">> the body of the loop where control flow re-converges, and the only back <br clear="none">> edge is from the continue block, so the ballot is in uniform control <br clear="none">> flow. But LLVM will get rid of the continue block since it's empty, and <br clear="none">> re-analyze the loop as two nested loops, splitting the loop header in <br clear="none">> two, producing a CFG which corresponds to this:<br clear="none">> <br clear="none">> while (cond1 /* uniform */) {<br clear="none">> do {<br clear="none">> ballot();<br clear="none">> ...<br clear="none">> } while (cond2 /* non-uniform */);<br clear="none">> ...<br clear="none">> }<br clear="none">> <br clear="none">> Now, in an implementation where control flow re-converges at the <br clear="none">> immediate post-dominator, this won't do the right thing anymore. In <br clear="none">> order to handle it correctly, you'd effectively need to always flatten <br clear="none">> nested loops, which will probably be really bad for performance if the <br clear="none">> programmer actually wanted the second thing. It also makes it impossible <br clear="none">> when translating a high-level language to LLVM to get the "natural" <br clear="none">> behavior which game developers actually expect. This is exactly the sort <br clear="none">> of "spooky action at a distance" which makes me think that everything <br clear="none">> we've done so far is really insufficient, and we need to add an explicit <br clear="none">> notion of control-flow divergence and reconvergence to the IR. We need a <br clear="none">> way to say that control flow re-converges at the continue block, so that <br clear="none">> LLVM won't eliminate it, and we can vectorize it correctly without <br clear="none">> penalizing cases where it's better for control flow not to re-converge.<br clear="none"><br clear="none">Well said!<br clear="none"><br clear="none">Cheers,<div class="ydp43cda87byqt3617305204" id="ydp43cda87byqtfd35117"><br clear="none">Nicolai<br clear="none">-- <br clear="none">Lerne, wie die Welt wirklich ist,<br clear="none">Aber vergiss niemals, wie sie sein sollte.<br clear="none">_______________________________________________<br clear="none">LLVM Developers mailing list<br clear="none"><a shape="rect" href="mailto:llvm-dev@lists.llvm.org" rel="nofollow" target="_blank">llvm-dev@lists.llvm.org</a><br clear="none"><a shape="rect" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="nofollow" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br clear="none"></div></div></div>
</div>
</div></body></html>