[LLVMdev] Proposal: add intrinsics for safe division
Philip Reames
listmail at philipreames.com
Fri Apr 25 11:06:56 PDT 2014
On 04/25/2014 10:19 AM, Filip Pizlo wrote:
>
>
> On April 25, 2014 at 9:52:35 AM, Eric Christopher (echristo at gmail.com
> <mailto:echristo at gmail.com>) wrote:
>
>> Hi Michael,
>>
>> > I'd like to propose to extend LLVM IR intrinsics set, adding new
>> ones for
>> > safe-division. There are intrinsics for detecting overflow errors, like
>> > sadd.with.overflow, and the intrinsics I'm proposing will augment
>> this set.
>> >
>> > The new intrinsics will return a structure with two elements
>> according to
>> > the following rules:
>> >
>> > safe.[us]div(x,0) = safe.[us]rem(x,0) = {0, 1}
>> > safe.sdiv(min<T>, -1) = safe.srem(min<T>, -1) = {min<T>, 1}
>> > In other cases: safe.op(x,y) = {x op y, 0}, where op is sdiv, udiv,
>> srem, or
>> > urem
>> >
>> >
>> > The use of these intrinsics would be quite the same as it was for
>> > arith.with.overflow intrinsics. For instance:
>> > %res = call {i32, i1} @llvm.safe.sdiv.i32(i32 %a, i32 %b)
>> > %div = extractvalue {i32, i1} %res, 0
>> > %bit = extractvalue {i32, i1} %res, 1
>> > br i1 %bit, label %trap, label %normal
>> >
>>
>> I notice that the patch is still in ToT even though we're now having a
>> discussion on whether it should go in. It should be reverted.
>>
>> That said, I don't see how this is anything except for an optimization
>> intrinsic and not necessary for correct behavior for any language.
>> I.e. You can do what the PNaCl people are doing and emit branches
>> instead. Since this will only happen on a single target and not on all
>> targets why not just make this a target intrinisic? I don't buy the
>> argument that it biases the target independent IR since any pass that
>> uses TTI in the IR level does the same.
>
> 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.
>
> Also, this isn't about just a single target. Any target that has to
> emulate integer division (like a lot of embedded systems would do)
> would benefit from this since the division emulation can most
> naturally be written to provide the "safe" semantics rather than
> LLVM's default semantics (i.e. undefined behavior on x/0 and INT_MIN/-1).
>
> I think adding these intrinics to the IR would be a great help for
> non-C clients of LLVM.
>
> -Filip
>
I agree with all of Filip's points above. I'm in support of including
these intrinsics in their current form.
I have two suggestions, but both of these can be incremental improvements:
1) On many targets, it might make sense to lower these much earlier than
codegenprepare. By lowering them that late, you loose a lot of
potentially to have branches eliminated. If there's no special hardware
support which makes those conditions cheap, getting rid of them early is
probably the best choice.
2) Extending Reid's suggestion (in a separate response) could we define
the intrinsics to take the (constant) values to be used in the boundary
conditions? llvm.safe.div(x,y, undef, undef) would give Reid's desired
semantics. llvm.safe.div(x,y, 0, min<T>) would give the original
proposed semantics. This would allow a variety of language semantics
with a shared implementation.
Philip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140425/35f11ce0/attachment.html>
More information about the llvm-dev
mailing list