<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">Thanks for the writeup! It's very helpful.</div><div class="gmail_quote"><br></div><div class="gmail_quote">On Fri, Apr 25, 2014 at 11:49 AM, Filip Pizlo <span dir="ltr"><<a href="mailto:fpizlo@apple.com" target="_blank">fpizlo@apple.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div style="word-wrap:break-word"><div><div class="h5"><div style="font-family:Helvetica,Arial;font-size:13px;color:rgb(0,0,0);margin:0px">
<br></div><p style>On April 25, 2014 at 10:48:18 AM, Reid Kleckner (<a href="mailto:rnk@google.com" target="_blank">rnk@google.com</a>) wrote:</p> <div><blockquote type="cite" style="text-indent:0px;letter-spacing:normal;font-variant:normal;text-align:start;font-style:normal;font-weight:normal;line-height:normal;text-transform:none;font-size:13px;white-space:normal;font-family:Helvetica,Arial;word-spacing:0px">
<span><div><div></div><div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Apr 25, 2014 at 10:19 AM, Filip Pizlo<span> </span><span dir="ltr"><<a href="mailto:fpizlo@apple.com" target="_blank">fpizlo@apple.com</a>></span><span> </span>wrote:<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div style="word-wrap:break-word"><p>The sdiv operation in LLVM IR only makes sense for C and its very direct relatives. The amount of control flow necessary to represent a safe division for any other language is ghastly. (a/b) becomes something like (b != 0 ? ((a != INT_MIN || b != -1) ? a / b : INT_MIN) : 0). It's more useful to the optimizer to see this as the single operation that it really is.</p>
</div></blockquote><div>This argument makes sense to me. It would be hard for the arm64 backend to pattern match all this control flow back into a single instruction after optimizations.</div></div></div></div></div></div>
</span></blockquote></div></div></div></div></blockquote><div>I want to soften this statement a bit: while ISel can't look across basic blocks, we could probably pattern match away the branches in the SelectionDAGBuilder, because it can see the original use-def chain for the result of the division. This would take a little work, but I can see how it would work and I've only touched SelectionDAGBuilder a few times. </div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div style="word-wrap:break-word"><p>So, it seems that for JavaScript and Java on ARM - and probably any environment with emulated division, these intrinsics would result in tighter code without requiring target intrinsics. For all other language/hardware combinations, the main benefit here is to materialize the gnarly control flow later and so hopefully reveal more optimization opportunities. That seems like a pretty good sweet-spot for the systems that I know about.</p>
</div></blockquote><div>If we're going to emit the control flow anyway, then we actually want to expose the control flow to the mid-level optimizers as early as possible. For example, on a non-ARM64 ISA, if the user checked that the divisor was zero already, we can eliminate the zero check branch. We could also unswitch this loop:<br>
</div><div><br></div><div>int b = ...;</div><div>for (int i = 0; i < n; ++i)</div><div> c[i] = a[i] / b;<br></div><div><br></div><div>Lowering this with branches produces:</div><div><br></div><div><div>for (int i = 0; i < n; ++i) {</div>
<div> if (b == 0) c[i] = 0;</div><div> else if (b == -1 && a[i] == INT_MIN) c[i] = INT_MIN;</div><div> else c[i] = a[i] / b;</div></div><div>}</div><div><br></div><div>b is loop invariant, and we could unswitch this on non-AArch64:</div>
<div><br></div><div>if (b == 0) for (int i = 0; i < n; ++i) c[i] = 0;</div><div>else if (b == -1) for (int i = 0; i < n; ++i) c[i] = (a[i] == INT_MIN) ? INT_MIN : a[i] / b;<br></div><div>else for (int i = 0; i < n; ++i) c[i] = a[i] / b;</div>
<div><br></div><div>Note that the middle branch goes away for unsigned division. It seems to me that the branches are better all around, at least for other ISAs.</div><div><br></div><div>As for generality, every language except asm.js (or JS-with-i32-coercion-hints) has to branch on the "overflow" bit of the intrinsic anyway.</div>
<div><br></div><div>There's also the discussion of iload and istore, where the consensus was that we'd rather have explicit null checks and branches.</div><div><br></div><div>I'm also not excited by the prospect of teaching all the mid-level optimizers about the arithmetic properties of safe.[us]div, which has been a big drawback to the other overflow checked arithmetic intrinsics.</div>
<div><br></div><div>So, in conclusion, I think we should at least *try* to pattern match out the branches in SDAGBuilder for ARM64 before giving up and adding this intrinsic, or something like it. Does that sound reasonable?</div>
</div></div></div>