<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
As the discussion has progressed and I've spent more time thinking
about the topic, I find myself less and less enthused about the
current proposal. I'm in full support of having idiomatic ways to
express safe division, but I'm starting to doubt that using an
intrinsic is the right way at the moment.<br>
<br>
One case I find myself thinking about is how one would combine
profiling information and implicit div-by-zero/overflow checks with
this proposal. I don't really see a clean way. Ideally, for a
"safe div" which never has the exceptional paths taken, you'd like
to completely do away with the control flow entirely. (And rely on
hardware traps w/exceptions instead.) I don't really see a way to
represent that type of construct given the current proposal. <br>
<br>
Another point that is bothering me is how these intrinsics will
interact with loop invariant code motion, and other condition check
optimizations. We have the potential to hide control flow from
optimizations which would otherwise remove it. I'm not stating
these <i>aren't</i> beneficial. I'm simply stating that I remain
somewhat unconvinced. They seem like clear wins on some
architectures (i.e. ARM, where the hardware includes the specific
checks already), but not on others (i.e. x86 with it's exceptions).
<br>
<br>
Given the above, I'm going withdraw my active support from the
current proposal. (Note: This does not mean that I'm going to
actively oppose it either!)<br>
<br>
Let me make a counter proposal of my own.<br>
<br>
1) Let's not add generic intrinsics at this time. Instead, let's
add cpu specific intrinsics with the exact semantics of the
associated div instructions.<br>
a) for ARM, this would be the semantics of the current proposed
instruction (right?)<br>
b) for x86, this would be an instruction which is defined to fault
on the corner cases (the resume behaviour would <i>not</i> be
specified for the moment)<br>
1b) Teach the optimizer about the semantics of each - if we do go
with a unified safe.div instruction later, this effort could be
mostly reused.<br>
2) Add optimizations (fairly late) which fold generic-div+control
flow into machine specific div instructions.<br>
3) Frontends that want machine specific semantics (i.e. trap or
defined edge cases), can use the machine specific intrinsics
directly. <br>
4) We provide a set of IR helper functions which implement safe
division in what we believe to be the best way. This can be
different for each supported platform. This could either be the
form of sample IR, or even as functions on IRBuilder. <br>
5) We spend some time optimizing the IR generated by (4) and use
that to inform our discussion about what is truly necessary from a
performance standpoint. <br>
<br>
Once this is in place, we can come back to the discussion of what an
appropriate generic safe div intrinsic would look like. In
particular, we would have the performance data at hand to lay to
rest the concerns raised by myself and Eric. My strong suspicion is
that the counter proposal will be "good enough" in practice for most
users. <br>
<br>
p.s. If we do go ahead with the current proposal, I'm going to
*strongly* request they be marked experimental. I think we'll need
to iterate on these a few times. <br>
<br>
Philip<br>
<br>
<div class="moz-cite-prefix">On 04/29/2014 04:17 AM, Michael
Zolotukhin wrote:<br>
</div>
<blockquote
cite="mid:1DE341C4-5392-4063-B347-9405DBB71DB6@apple.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=ISO-8859-1">
Hi,
<div><br>
</div>
<div>
<blockquote type="cite">
<div dir="ltr">I am very much in favor of having a div
instruction with well defined div-by-zero and overflow
behavior.</div>
</blockquote>
</div>
<div>Actually, an interest in these intrinsics has been shown for
quite a long time, see for example thread [1].</div>
<div><br>
</div>
<div>I updated the patch, now the intrinsics return {iN, i1, i1}
to separately indicate division by zero and overflow events.
Though for unsigned version only division by zero is relevant, I
decided to keep three elements in return structure for
consistency (the last one is always 0 in this case). With this
change various front-ends can take advantage of the intrinsics,
depending on desired semantics.</div>
<div><br>
</div>
<div>Also I changed semantics of srem intrinsics to better match
semantics of, for instance, Go. The original proposal stated
that safe.srem(min<T>,-1) = min<T>, but it makes
more sense to return 0 here. Thus, we’ll keep invariant X =
div(X,Y)*Y + rem(X,Y).</div>
<div><br>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<meta http-equiv="Content-Type" content="text/html;
charset=ISO-8859-1">
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<meta http-equiv="Content-Type" content="text/html;
charset=ISO-8859-1">
<div><br>
</div>
<div>Does the patch look good? I’d be glad to hear any remarks and
comments regarding the patch, and adjust it correspondingly.</div>
<div><br>
</div>
<div>
<div>[1] <a moz-do-not-send="true"
href="http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-April/060955.html">http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-April/060955.html</a></div>
<div><br>
</div>
</div>
<div>Best regards,</div>
<div>Michael</div>
<div><br>
</div>
<div>
<div>
<div>On Apr 27, 2014, at 2:45 AM, Keno Fischer <<a
moz-do-not-send="true"
href="mailto:kfischer@college.harvard.edu">kfischer@college.harvard.edu</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<blockquote type="cite">
<div dir="ltr">I am very much in favor of having a div
instruction with well defined div-by-zero and overflow
behavior. The undefined behavior on certain values for
LLVM intrinsics has been a major pain point for us in
Julia, because adding the extra branches just kills
performance and we know that there is an X86 instruction
that just does what we want. Anyway, this was brought up
briefly above, but want to bring back the discussion of a
div instruction that reliably traps, as that seems to me
to be one of the only ways to get adequate performance in
the common case. This can probably be done as suggested
above with matching on the trap condition of this
instruction, but I think while we're at it, we should
tackle that case as well.
<div>
<br>
</div>
<div>Thanks,</div>
<div>Keno</div>
</div>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">On Sat, Apr 26, 2014 at 5:11 PM,
Michael Zolotukhin <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:mzolotukhin@apple.com" target="_blank">mzolotukhin@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; position: static; z-index: auto;"><br>
Hi,<br>
<br>
Thanks to everybody for the very informative feedback!
Due to difference in timezones, I usually miss the
most active time of discussions, however I’ll try to
cover the raised questions here and share my vision on
them.<br>
<br>
Generally speaking, we are trying to find answers to
the following two questions:<br>
o Are these intrinsics useful in general?<br>
o If yes, when to lower them to actual IR/DAG?<br>
<br>
In a nutshell, my answers are:<br>
o Yes, they are useful, and useful for all
targets. Not only for ARM64, where they are especially
useful.<br>
o After loop optimizations but before lowering
IR to DAG. Currently it’s in CodeGenPrepare, but we
might lower them before that if there is any need in
this.<br>
<br>
I'll try to explain why I think so. For the beginning,
let's consider a simple expression div=x/y in
different languages and write the corresponding IR
with use of the intrinsics (here I omit types for
conciseness, assuming result type of the safe.sdiv
intrinsic being {i32, i1, i1}) :<br>
<br>
*** C/C-like ***<br>
%div = sdiv %x, %y<br>
<br>
*** Java, Go ***<br>
%divr = call %safe.sdiv(%x, %y)<br>
%div = extractvalue %divr, 0<br>
%divbyzero_bit = extractvalue %divr, 1<br>
br i1 %divbyzero_bit, label %throw, label %normal<br>
<br>
*** JavaScript, with “|0” ***<br>
%divr = call %safe.sdiv(%x, %y)<br>
%div = extractvalue %divr, 0<br>
<br>
*** JavaScript without “|0”, Ruby and maybe others ***<br>
%divr = call %safe.sdiv(%x, %y)<br>
%div = extractvalue %divr, 0<br>
%divbyzero_bit = extractvalue %divr, 1<br>
%ovf_bit = extractvalue %divr, 2<br>
%exceptional_case_bit = or %ovf_bit, %divbyzero_bit<br>
br i1 %exceptional_case_bit, label
%handle_exceptional_case, label %normal<br>
<br>
<br>
Now let’s write the IR for the same expression without
the intrinsics:<br>
<br>
*** C/C-like ***<br>
%div = sdiv %x, %y<br>
<br>
*** Java, Go ***<br>
%divbyzero_bit = cmp %y, 0<br>
br i1 %divbyzero_bit, label %throw, label %normal<br>
normal:<br>
%div = sdiv %x, %y<br>
<br>
*** JavaScript, with “|0” ***<br>
%divbyzero_bit = cmp %y, 0<br>
br i1 %divbyzero_bit, label %division_by_zero, label
%chkovf<br>
division_by_zero:<br>
br label %end<br>
chkovf:<br>
%tmin_bit = cmp %x, min<T><br>
%minus_one_bit = cmp %y, -1<br>
%ovf_bit = and %tmin_bit, %minus_one_bit<br>
br i1 %ovf_bit, label %ovf, label %normal<br>
ovf:<br>
br label %end<br>
normal:<br>
%div.0 = sdiv %x, %y<br>
br label %end<br>
end:<br>
%div = phi [%div.0, %normal], [min<T>, %ovf],
[0, %division_by_zero]<br>
<br>
*** JavaScript without “|0”, Ruby and maybe others ***<br>
%divbyzero_bit = cmp %y, 0<br>
br i1 %divbyzero_bit, label %throw, label %chkovf<br>
chkovf:<br>
%tmin_bit = cmp %x, min<T><br>
%minus_one_bit = cmp %y, -1<br>
%ovf_bit = and %tmin_bit, %minus_one_bit<br>
br i1 %ovf_bit, label %ovf, label %normal<br>
ovf:<br>
; Special handling of min<T>/-1: converting to
BigInt, double or something other<br>
unreachable<br>
normal:<br>
%div.0 = sdiv %x, %y<br>
<br>
As one can see, if the intrinsic is lowered to some
CFG (i.e. on x86), there is nor loss neither win: due
to the implemented optimizations the final code would
be roughly the same as in the case with explicitly
written CFG.<br>
<br>
If the intrinsic could be directly lowered to a single
instruction (i.e. on ARM64 and if we don’t bother
about divz/ovf-flag), use of the intrinsic would
definitely be beneficial - that takes place for the
<JavaScript, with “|0”> case.<br>
<br>
That might make one think that the intrinsics are
useful only for ARM64, and in general aren’t that
useful at all. But in fact even when it can’t be
lowered to a single instruction, keeping the control
flow ‘inside’ the intrinsic till its lowering might be
beneficial. For instance, loop passes work much better
on loops without control flow: IndVars might be a good
example of such pass. And, for instance, it seems much
easier to vectorize a loop with call to one of these
intrinsics than vectorize a loop with explicitly
created control flow (and it could become even worse
if there are several calls to the intrinsics in the
same loop).<br>
<br>
In some cases we might want to lower these intrinsics
earlier than in CGP - as Reid mentioned, it could help
us to hoist checks out of loops. That’s true but we
need to keep in mind possible disadvantages of such
early lowering (see previous paragraph). But in
general I don’t see any problems with allowing earlier
lowering.<br>
<br>
As for extending the result structure to keep one more
flag (being that i2 instead of i1, or one more i1
flag) - that seems fine, and both options {iN, i2} and
{iN, i1, i1} look good to me.<br>
<br>
Now, why not to lower these intrinsics even later?
Almost for all targets we want to get very similar
CFG, and I don’t see any benefits of duplicating very
similar code all across different backends. Even on
ARM64 we need to have control flow in some cases (e.g.
for Java) - so we actually win nothing from making
lowering completely target-specific.<br>
<br>
I hope that covers the raised concerns, at least to
some extent. Does that sound reasonable enough? If so,
I’ll prepare and post here an updated version of the
patch.<br>
<br>
Thanks,<br>
Michael<br>
<div class="HOEnZb">
<div class="h5"><br>
<br>
On Apr 26, 2014, at 4:04 AM, Andrew Trick <<a
moz-do-not-send="true"
href="mailto:atrick@apple.com">atrick@apple.com</a>>
wrote:<br>
<br>
><br>
> On Apr 25, 2014, at 2:21 PM, Eric Christopher
<<a moz-do-not-send="true"
href="mailto:echristo@gmail.com">echristo@gmail.com</a>>
wrote:<br>
><br>
>>> In short, I agree with your
observations that these intrinsics are not an<br>
>>> obvious slam-dunk compared to making
the explicit control flow, but I think<br>
>>> that the intrinsics do give enough
flexibility on the LLVM side that it<br>
>>> would be great if front-ends used
them rather than rolling the control flow<br>
>>> themselves.<br>
>>><br>
>><br>
>> The problem is that then we have 2
problems: All targets (except for<br>
>> arm64) then have to lower the intrinsic
as the first thing they do<br>
>> (giving us a TTI pass as the first thing
in the pipeline) to take<br>
>> advantage of the information later during
optimization, _and_ we have<br>
>> to plumb all of the work optimizing the
intrinsic as well giving us a<br>
>> situation where we've now split our
optimization efforts as well as<br>
>> the pain of maintaining an intrinsic
that's useful for a single<br>
>> target.<br>
>><br>
>> I really think that this is just
solidifying my position that the<br>
>> intrinsic is a bad idea and that this
should be done as later<br>
>> optimizations.<br>
><br>
> The goal of the intrinsic wasn't stated
clearly.<br>
><br>
> This intrinsic isn't particularly necessary
for any specific frontend<br>
> or architecture. I think the LLVM community
would benefit from a<br>
> canonical way to represent well-defined
integer division. We don't<br>
> need to add an IR instruction, because it's
fine for most optimization<br>
> passes to ignore these operations. A target
independent intrinsic<br>
> works well as long as:<br>
><br>
> - It cleanly captures the language level
semantics.<br>
><br>
> - It facilitates mid-level optimization.<br>
><br>
> - It naturally lowers into ideal code both on
architectures that trap<br>
> (x86) and those that don't (arm).<br>
><br>
> To summarize my understanding of the
concerns:<br>
><br>
> (1) The semantics of the safe.div intrinsic
need to be useful for the<br>
> Language/ISA Matrix that LLVMers care about.<br>
><br>
> At canonical IR level, the intrinsic is
useful by eliminating control<br>
> flow merges and representing divide-by-zero
and/or signed overflow in<br>
> a canonical form:<br>
><br>
> %res = call {i32, i1}
@llvm.safe.sdiv.i32(i32 %a, i32 %b)<br>
> %bit = extractvalue {i32, i1} %res, 1<br>
> br i1 %bit, label %trap, label %continue<br>
> trap:<br>
> call ...<br>
> unreachable<br>
><br>
> continue:<br>
> %div = extractvalue {i32, i1} %res, 0<br>
><br>
> The original proposal fails to achieve this
because the common case of<br>
> Java/Go would require a check in the
slow-path to differentiate<br>
> divide-by-zero from signed overflow. That
should be fixed by<br>
> generalizing the intrinsic so that the two
conditions are distinct:<br>
><br>
> %res = call {i32, i1, i1}
@llvm.safe.sdiv.i32(i32 %a, i32 %b)<br>
> %div0 = extractvalue {i32, i1} %res, 1<br>
> br i1 %div0, label %trap, label %checkovf<br>
><br>
> checkovf:<br>
> %ovf = extractvalue {i32, i1} %res, 2<br>
> br i1 %div0, label %trap, label %continue<br>
><br>
> trap:<br>
> call ...<br>
> unreachable<br>
><br>
> continue:<br>
> %div = extractvalue {i32, i1} %res, 0<br>
><br>
> ...or some variation of the above. I don't
have a personal stake in this.<br>
><br>
> (2) The safe.div intrinsic inhibits generic
code motion and Correlated<br>
> Value Prop based optimization.<br>
><br>
> This goes both ways.<br>
><br>
> CVP could miss out on cases unless we teach
it about the semantics of<br>
> the intrinsics. Correct me if I'm wrong, but
I don't think this would<br>
> actually be too difficult.<br>
><br>
> OTOH, with the intrinsics, it would be easy
to write a simple<br>
> optimization pass that hoists and combines
checks along the domtree.<br>
><br>
> After divide-by-zero optimization, you would
have something like:<br>
><br>
> %res = call {i32, i1, i1}
@llvm.safe.sdiv.i32(i32 %a, i32 %b)<br>
> %div0 = extractvalue {i32, i1} %res, 1<br>
> br i1 %div0, label %trap, label %continue<br>
><br>
> trap:<br>
> # No call here!<br>
> unreachable<br>
><br>
> continue:<br>
> %div = extractvalue {i32, i1} %res, 0<br>
><br>
> And the branch to trap just goes away at some
point.<br>
><br>
> Now considering Reid's LICM example:<br>
><br>
> for (int i = 0; i < n; ++i) {<br>
> if (b == 0) c[i] = 0;<br>
> else if (b == -1 && a[i] == INT_MIN)
c[i] = INT_MIN;<br>
> else c[i] = a[i] / b;<br>
> }<br>
><br>
> Simply put, if we want to unswitch this code
for x86, then we need a<br>
> TTI pass to lower the intrinsic. On the other
hand, I believe it is<br>
> more important to eliminate the control flow
within the loop to aid<br>
> loop analysis and other optimizations. So we
still want the front end<br>
> to emit the intrinsic, we just may eventually
want it lowered earlier<br>
> than CGP. I don't think this issue has any
bearing on the intrinsic's<br>
> LangRef spec.<br>
><br>
> There was some comparison made to
iload/istore, which I don't<br>
> follow:<br>
> - subsuming loads and stores into another
instruction is really scary<br>
> considering how much logic we have for
analyzing the side effects of<br>
> memory access.<br>
> - there is no benefit to IR optimization to
the iload/istore intruction.<br>
> - it is easy to detect null checked
load/stores in IR at any point.<br>
> - it is very rare that a platform would want
to resume from trapping load/store.<br>
><br>
> (3) The safe.div intrinsic is a
target-specific codegen optimization.<br>
><br>
> Regardless of the target, we want to
eliminate control flow merges in<br>
> all cases, and completely eliminate control
flow when we don't have<br>
> trapping semantics. To do this, we need an
intrinsic at canonical IR<br>
> level. Clearly it should be a target
independent intrinsic<br>
> since *some* optimizations/analyses want to
be aware of it.<br>
><br>
> Even ignoring the rationale above, supporting
codegen with a<br>
> target-specific intrinsic would minimally
require the DAG builder to<br>
> match this<br>
> "if (b != 0) ? ((a != INT_MIN || b != -1) ? a
/ b : INT_MIN) : 0)"<br>
><br>
> after all optimizations have had their way
with it. A big problem here<br>
> is that there are actually many different
forms of this expression and<br>
> surrounding control flow, depending on the
frontend's integer division<br>
> semantics. We would have to recognize all the
variations of checking for<br>
> divide-by-zero and/or overflow, trapping
and/or producing a certain<br>
> constant, branching or selecting values. This
is obviously terrible<br>
> from an engineering standpoint.<br>
><br>
> -Andy<br>
>
_______________________________________________<br>
> LLVM Developers mailing list<br>
> <a moz-do-not-send="true"
href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>
<a moz-do-not-send="true"
href="http://llvm.cs.uiuc.edu/" target="_blank">http://llvm.cs.uiuc.edu</a><br>
> <a moz-do-not-send="true"
href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev"
target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a moz-do-not-send="true"
href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>
<a moz-do-not-send="true"
href="http://llvm.cs.uiuc.edu/" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a moz-do-not-send="true"
href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev"
target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</div>
</div>
</blockquote>
</div>
<br>
</div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a moz-do-not-send="true" href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>
<a moz-do-not-send="true"
href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br>
<a moz-do-not-send="true"
href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote>
</div>
<br>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a class="moz-txt-link-freetext" href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a>
<a class="moz-txt-link-freetext" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</pre>
</blockquote>
<br>
</body>
</html>