[M3devel] integer overflow

[Jay K]

I didn't think many processors offered integer overflow "traps".
I'm so used to condition flags being the way, on x86, PowerPC, 6502, etc.
  (6502 it turns out is awful, but you don't realize you are in the insane asylum until you leave it; signed comparisons required doing an actual "destructive" subtract, the "compare" instruction only "works" for unsigned comparisons) 
 
 
Divide by zero and floating point I'm more familiar with.
  Though I think x86 and PowerPC vary on that point -- integer divide by zero.
  I think that was mentioned on the "let's change architectures yet again" guide.
 
 
The reason you'd check for overflow before you'd check if the thread cares about overflow, is that the first is probably *much* cheaper and yields "true" much less often. Checking if the thread cares about trapping overflow requires getting a thread local. Checking for overflow on x86 is typically one conditional branch I believe. Or maybe a "cmove", probably cheaper.
 
 
Granted, if you get the address of the thread locals only upon entry (such as in a function with TRY!) and you only check the bit when there hasn't been a function call (such as to possibly change the setting), then the check isn't too too bad. Still, one conditional branch, encoded to be predicted correctly (whichever way that is..), seems cheap. Plus there might be a reasonable way to "accumulate" overflow that is even cheaper. Like, having a local overflow variable and if you have e := a + b + c + d, do like:
 
 
  overflow = 0;  
  e = a + b;  
  overflow += carry;  
  e += c;  
  overflow += carry;  
  e += d;  
  overflow += carry;  
  if overflow raise 
 
 
might be cheaper than:
  overflow = 0;  
  e = a + b;  
  if overflow raise 
  e += c;  
  if overflow raise 
  e += d;  
  if overflow raise 
 
 
 
I really thought that detecting/trapping integer overflow was part of being safe. It seems I was very mistaken.
So I guess any work here is really not so important as I thought?
Someone convince me that it is actually important?
 
 
 - Jay



----------------------------------------
> From: hosking at cs.purdue.edu
> Date: Tue, 12 Jan 2010 17:09:36 -0500
> To: jay.krell at cornell.edu
> CC: m3devel at elegosoft.com
> Subject: Re: [M3devel] integer overflow
>
> On 12 Jan 2010, at 14:46, Jay K wrote:
>
>> I'm not against using "hardware traps", if they exist.
>> I'll have to do a bunch of research as to their existence.
>
> Their existence is why FloatMode was designed in the first place.
>
>> I don't think one should be able to turn this on or off.
>> I think it should be static per type or interface/library.
>
> I disagree. You are conflating language safety with what the semantics of arithmetic should be. The language spec is deliberately vague about whether overflow checking should take place or not for signed integers (as is C). Overflow doesn't create a "bad" value for an INTEGER. It is still an INTEGER value. It is just that the value is obtained by overflowed arithmetic in the hardware.
>
>
>> Even so, if it is a runtime configuration, I realize
>> that the implementation, on a system
>> without hardware traps, with a processor-specific
>> flag would look *like*:
>>
>>
>> check for overflow
>> if no overflow, continue on as usual
>> if overflow, call out to a function
>> that function:
>> fetch the thread local
>> depending on *that*, raise an exception or continue on
>
> Why do you assume we would even support thread-local handling of overflow? If we did, I would argue that the code would be more like:
>
> check if this thread cares about overflow
> if it does then check the overflow flag and raise an exception if it is set
>
>> I suspect I could easily quickly put in place a portable implementation, and..like *almost* everything else that isn't I/O bound (other than code size issue).
>>
>>
>> Hm. Actually another very good approach is probably to have the front end inline most of this logic, like everything except 64bit multiplication on 32bit platform. At first I though that'd be too bloating, but it's actually probably competitive. There is already inlining of the computation of the result, and merely passing three parameters won't be cheap.
>
> The inline sequence would be quite cheap if we really needed to go that route.
>
>> That can also be highly portable, mimicing the algorithms I showed.
>>
>>
>> The front end can also do the optimization where overflow isn't necessarily checked for every single operation.
>
> Correct. It is never needed for subranges that don't include the extremes of the integer representation.
>
>>
>>
>> - Jay
>>
>>
>>
>> ________________________________
>>> Subject: Re: [M3devel] integer overflow
>>> From: hosking at cs.purdue.edu
>>> Date: Tue, 12 Jan 2010 14:30:00 -0500
>>> CC: m3devel at elegosoft.com
>>> To: jay.krell at cornell.edu
>>>
>>>
>>>
>>> On 12 Jan 2010, at 04:23, Jay K wrote:
>>>
>>> I propose that integer signed overflow always raise an immediate exception.
>>> Word.T should either raise an exception for unsigned overflow, or maybe no exceptions at all.
>>> For folks that want silent wraparound, maybe a separate interface like UnsafeInt.
>>>
>>> That is going to pose a performance issue (that many C programmers may baulk at!).
>>>
>>> I propose that FloatMode's integer features not be the way forward.
>>>
>>> Why not?
>>>
>>> There are two implementation strategies.
>>>
>>>
>>> - "check the carry flag"
>>> A processor-specific thing, but possibly something easy for the gcc backend to do.
>>> And very likely easy for the integrated backend.
>>> Probably very efficient.
>>>
>>> Yes, doable.
>>>
>>> - internally generate function calls for every arithmetic operation
>>> like how sets are implemented
>>>
>>> Very bad for performance. We should rely on the processor support for arithmetic traps or condition variables.
>>>
>>>
>>> Implementing most such functions is easy enough in portable C.
>>> Or maybe using Modula-3 and interface Word.
>>>
>>> Not the best way going forward...
>>>
>>> e.g.
>>> void add(int a, int b, int* c, int* overflow)
>>> {
>>> int d = (a + b);
>>> /* overflow if input signs are equal and output sign is different;
>>> if input signs are unequal, overflow is not possible
>>> positive + positive: expect positive, else overflow
>>> negative + negative: expect negative, else overflow
>>> positive + negative: overflow not possible */
>>> *overflow = ((a < 0) == (b < 0) && (d < 0) != (a < 0));
>>> *c = d;
>>> }
>>>
>>>
>>> void sub(int a, int b, int* c, int* overflow)
>>> {
>>> int d = (a - b);
>>> /* overflow if input signs are unequal and output sign is different than first input;
>>> if input signs are equal, overflow is not possible;
>>> positive - negative: expect positive, overflow if negative
>>> negative - positive: expect negative, overflow if positive
>>> positive - positive, negative - negative: overflow not possible */
>>> *overflow = ((a < 0) != (b < 0) && (d < 0) != (a < 0));
>>> *c = d;
>>> }
>>>
>>> #include
>>>
>>> void mult(int a, int b, int* c, int* overflow)
>>> {
>>> /* do operation in higher precision and check if it fits */
>>> int64 d = (a * (int64)b);
>>> *c = (int)d;
>>> *overflow = (d>= INT_MIN && d <= INT_MAX);
>>> }
>>>
>>> /* for interface Word */
>>> typedef unsigned uint;
>>>
>>> void addu(uint a, uint b, uint* c, int* overflow)
>>> {
>>> uint d = (a + b);
>>> /* overflow if output less than either input */
>>> *overflow = (d < a);
>>> *c = d;
>>> }
>>>
>>> void subu(uint a, uint b, uint* c, int* overflow)
>>> {
>>> uint d = (a - b);
>>> /* overflow if output greater than first input */
>>> *overflow = (d> a);
>>> *c = d;
>>> }
>>>
>>> void multu(uint a, uint b, uint* c, int* overflow)
>>> {
>>> /* operate at higher precision and see if it fits */
>>> uint64 d = (a * (uint64)b);
>>> *overflow = (d <= UINT_MAX);
>>> *c = (uint)d;
>>> }
>>>
>>> void multLU(uint64 a, uint64 b, uint64* c, int* overflow)
>>> {
>>> /* break it down into smaller operations, not shown, but not difficult */
>>> }
>>>
>>>
>>> Yes I know this is inefficient, but such is a possible price of portable safety.
>>>
>>>
>>> A hybrid is probably possible if the gcc backend support must be processor specific and we gradually provide the implementations.
>>>
>>> FloatMode seems a perfectly reasonable way forward doesn't it? It allows both trap-based and (with compiler support) checked condition code implementations.
>>>
>>>
>>>
>>> - Jay
>>>
>>>
>>>
>>>
>>>
>>>
>