llvm dev - Apr 2014 - [LLVMdev] [llvm] r206732 - Implement builtins for safe division: safe.sdiv.iN, safe.udiv.iN, safe.srem.iN,

On 04/25/2014 10:12 AM, Eric Christopher wrote:
> Hi Andrew,
>
> Replying in both places because this mail is a pretty good summary of
> issues and so it's worth replying to... my apologies for continuing in
> both places.
Responding to LLVMDev - I for one had missed this part of the
thread.
>
>> The only language aspect under discussion is integer division. Every
>> standardized language I'm aware of requires some form of check on
integer
>> division.
>>
>> Either the language is C-based, in which case we need to provide
compiler
>> options to achieve sanity:
>> -fsanitize=integer-divide-by-zero:
>> -fsanitize=signed-integer-overflow
>>
> I'm going to argue this one, this isn't part of language
conformance,
> unless you're optimizing your undefined behavior. :) I also haven't
> seen patches to have clang emit this intrinsic anywhere.
>
>> Or the language requires a check to determine whether to throw an
exception.
>>
> Like Java? Something else?
Java for one.
>
>> Or the language requires a check to determine whether the number needs
to be
>> promoted to a different representation.
>>
> Guessing JS here then? You could just actually state the kind of
> behavior you're trying to work with rather than handwaving it. How
> about show me some IR and how we'd like this to work? Michael started
> that, but I haven't seen something with a front end language and how
> we'd like to map such a thing onto IR.
Most any language which uses full integer types rather than machine 
integers.  (i.e. uses machine integers as an optimization)  I don't have 
an example off the top of my head.

You have a good point about spelling out desired semantics.  My 
particular semantics are (Java):
- INT_MIN/-1 = INT_MIN
- X/0 -> exception
- x/y = x/y (rounded towards zero as an integer)

See: 
http://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.17.2

Currently, we are using unoptimized checks for each of the corner cases 
emitted by our frontend.  We haven't even started to optimize this yet.  
Which is why I'm interested when others seem to be pursuing the same 
goal.  :)
>
>> Of course, these can all be implemented with explicit checks in the IR.
And
>> at IR level, this is exactly the same situation as checking overflow on
>> add/sub/mul. I have argued in the past just as you are now that there
is
>> already another way to represent the check. However, LLVM developers
are now
>> very heavily using the llvm.arith.with.overflow intrinsics and making
the
>> optimizer aware of them, I think we should be consistent. Anyway,
>> implementing explicit checks in the IR (before CodeGenPrepare) tends to
make
>> the target independent IR heavily biased toward a particular
architecture.
>>
> This is true, and we emit the IR with that instruction in the front
> end so that we can do that reasonably effectively. I don't necessarily
> know that the semantics of the divide instruction are as clear cut as
> the overflow on add. Why is this the correct set of things that we
> should be checking?
Because these are the corner cases which matter in practice.  Or to say 
it differently, no one has spoken up to request others. 
:)
> INT_MIN / -1 (or %) is definitely undefined
> behavior in C11/C++11 and could trap on various processors, but is
> apparently defined to ... something on ARM64?
You keep mentioning undefined behaviour in C++.  I'm not compiling C++.  
Why is this relevant?

Philip

> You keep mentioning undefined behaviour in C++.  I'm not compiling C++.
Why
> is this relevant?
>
This is actually my point. Everyone wants different semantics (see the
Go link I mentioned earlier) and so a huge "meta operation" node is
exactly the thing we don't want. It'll fit your needs, maybe
javascript (maybe not), but is not generally useful.

-eric

On 04/25/2014 04:49 PM, Eric Christopher wrote:
>> You keep mentioning undefined behaviour in C++.  I'm not compiling
C++.  Why
>> is this relevant?
>>
> This is actually my point. Everyone wants different semantics (see the
> Go link I mentioned earlier) and so a huge "meta operation" node
is
> exactly the thing we don't want. It'll fit your needs, maybe
> javascript (maybe not), but is not generally useful.
>
> -eric
Just to point out, the Go semantics seem to be quite similar to the Java 
semantics I posted earlier.  They are not the ones originally proposed 
in this thread, but the modified version I suggested in my original 
response would handle them as well.

(res, status) = safe.div(x,y, on_overflow_constant, on_divzero_constant)

For anyone else who lost the link like I did:
http://golang.org/ref/spec#Arithmetic_operators

Philip