[M3devel] integer overflow

[Jay K]

Range checking and overflow checking I think are different.
 
 
TYPE T1 = [1..6];
a:T1 := 7; (* range check error *)
b:T1 := 6;
c:T1 := 1;
d:T1 := b + c; (* range check error *)
e:T1 := c - b; (* range check error *)
f:ARRAY [1..4] OF INTEGER;
f[b] := 0; (* range check error *)
g:INTEGER := LAST(INTEGER) - 5 + a; (* overflow *)
 
 
But anyway, yes it will be slower, but I believe it should be mandatory, at least in safe modules, it is needed for safety, and I doubt it'll be *noticably* slower for the vast majority of code.
 
 
Initially it'll probably be a command line option or such.
 
 
Or maybe it isn't a safety issue?
As long as one has checks on array indexing? Which I'm sure we do.
 
 
 - Jay


----------------------------------------
> To: jay.krell at cornell.edu
> Date: Tue, 12 Jan 2010 11:57:52 -0800
> From: mika at async.async.caltech.edu
> CC: m3devel at elegosoft.com
> Subject: Re: [M3devel] integer overflow
>
>
> Are you actually proposing making range checking mandatory for integer
> arithmetic?
>
> I think that's a bad idea... the performance hit could be very high
> (especially on some architectures).
>
> The language should already guarantee that problems in this area can't
> cause unchecked runtime errors.
>
> Mika
>
> Jay K writes:
>>
>>I'm not against using "hardware traps"=2C if they exist.
>>I'll have to do a bunch of research as to their existance.
>>=20
>>=20
>>=20
>>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.
>>=20
>>=20
>>Even so=2C if it is a runtime configuration=2C I realize
>>that the implementation=2C on a system
>>without hardware traps=2C with a processor-specific
>>flag would look *like*:
>>=20
>>=20
>> check for overflow=20
>> if no overflow=2C continue on as usual
>> if overflow=2C call out to a function
>> that function:
>> fetch the thread local
>> depending on *that*=2C raise an exception or continue on=20
>>=20
>>=20
>>I suspect I could easily quickly put in place a portable implementation=2C =
>>and..like *almost* everything else that isn't I/O bound (other than code si=
>>ze issue).
>>=20
>>=20
>>Hm. Actually another very good approach is probably to have the front end i=
>>nline most of this logic=2C like everything except 64bit multiplication on =
>>32bit platform. At first I though that'd be too bloating=2C but it's actual=
>>ly probably competitive. There is already inlining of the computation of th=
>>e result=2C and merely passing three parameters won't be cheap.
>>=20
>>=20
>>That can also be highly portable=2C mimicing the algorithms I showed.
>>=20
>>=20
>>The front end can also do the optimization where overflow isn't necessarily=
>> checked for every single operation.
>>=20
>>=20
>>- Jay
>>
>>
>>
>>________________________________
>>> Subject: Re: [M3devel] integer overflow
>>> From: hosking at cs.purdue.edu
>>> Date: Tue=2C 12 Jan 2010 14:30:00 -0500
>>> CC: m3devel at elegosoft.com
>>> To: jay.krell at cornell.edu
>>>
>>>
>>>
>>> On 12 Jan 2010=2C at 04:23=2C Jay K wrote:
>>>
>>> I propose that integer signed overflow always raise an immediate exceptio=
>>n.
>>> Word.T should either raise an exception for unsigned overflow=2C or maybe=
>> no exceptions at all.
>>> For folks that want silent wraparound=2C maybe a separate interface like =
>>UnsafeInt.
>>>
>>> That is going to pose a performance issue (that many C programmers may ba=
>>ulk 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=2C but possibly something easy for the gcc bac=
>>kend to do.
>>> And very likely easy for the integrated backend.
>>> Probably very efficient.
>>>
>>> Yes=2C 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 ari=
>>thmetic 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=2C int b=2C int* c=2C int* overflow)
>>> {
>>> int d =3D (a + b)=3B
>>> /* overflow if input signs are equal and output sign is different=3B
>>> if input signs are unequal=2C overflow is not possible
>>> positive + positive: expect positive=2C else overflow
>>> negative + negative: expect negative=2C else overflow
>>> positive + negative: overflow not possible */
>>> *overflow =3D ((a < 0) =3D=3D (b < 0) && (d < 0) !=3D (a < 0))=3B
>>> *c =3D d=3B
>>> }
>>>
>>>
>>> void sub(int a=2C int b=2C int* c=2C int* overflow)
>>> {
>>> int d =3D (a - b)=3B
>>> /* overflow if input signs are unequal and output sign is different than =
>>first input=3B
>>> if input signs are equal=2C overflow is not possible=3B
>>> positive - negative: expect positive=2C overflow if negative
>>> negative - positive: expect negative=2C overflow if positive
>>> positive - positive=2C negative - negative: overflow not possible */
>>> *overflow =3D ((a < 0) !=3D (b < 0) && (d < 0) !=3D (a < 0))=3B
>>> *c =3D d=3B
>>> }
>>>
>>> #include
>>>
>>> void mult(int a=2C int b=2C int* c=2C int* overflow)
>>> {
>>> /* do operation in higher precision and check if it fits */
>>> int64 d =3D (a * (int64)b)=3B
>>> *c =3D (int)d=3B
>>> *overflow =3D (d>=3D INT_MIN && d <=3D INT_MAX)=3B
>>> }
>>>
>>> /* for interface Word */
>>> typedef unsigned uint=3B
>>>
>>> void addu(uint a=2C uint b=2C uint* c=2C int* overflow)
>>> {
>>> uint d =3D (a + b)=3B
>>> /* overflow if output less than either input */
>>> *overflow =3D (d < a)=3B
>>> *c =3D d=3B
>>> }
>>>
>>> void subu(uint a=2C uint b=2C uint* c=2C int* overflow)
>>> {
>>> uint d =3D (a - b)=3B
>>> /* overflow if output greater than first input */
>>> *overflow =3D (d> a)=3B
>>> *c =3D d=3B
>>> }
>>>
>>> void multu(uint a=2C uint b=2C uint* c=2C int* overflow)
>>> {
>>> /* operate at higher precision and see if it fits */
>>> uint64 d =3D (a * (uint64)b)=3B
>>> *overflow =3D (d <=3D UINT_MAX)=3B
>>> *c =3D (uint)d=3B
>>> }
>>>
>>> void multLU(uint64 a=2C uint64 b=2C uint64* c=2C int* overflow)
>>> {
>>> /* break it down into smaller operations=2C not shown=2C but not difficul=
>>t */
>>> }
>>>
>>>
>>> Yes I know this is inefficient=2C but such is a possible price of portabl=
>>e safety.
>>>
>>>
>>> A hybrid is probably possible if the gcc backend support must be processo=
>>r 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 implemen=
>>tations.
>>>
>>>
>>>
>>> - Jay
>>>
>>>
>>>
>>>
>>>
>>> =