[M3devel] integer overflow

[Mika Nystrom]

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
>>
>>
>>
>>
>>
>> 		 	   		  =