Integer Overflow

[jacob navia]

Le 29/12/10 19:24, christian.bau a écrit :

See, you are lacking _precision_.

If an implementation of calloc written in C just multiplies its two
arguments of type size_t, there _cannot_ be an overflow. The result
can be a number that is much too small for (count) elements of (size)
bytes each, but it's not an overflow.

Of course a cat isn't a cat. It is "felis domesticus".

How can you DARE just call it a cat?



YES, there is no overflow OF COURSE.

but... as you yourself said:

> The result
> can be a number that is much too small for (count) elements of (size)
> bytes each

jacob

P.S. your idea of an argument to _overflow() is quite clever.
Thanks for that, I think I will change lcc-win for it,
since the generated
code is exactly the same as if you write

c = a+b;
if (_overflow())

-->

if (_overflow(a+b))

Looks much better and generates the same code:
movl a,%eax
movl b,%ecx
addl %eax,%ecx
movl $0,%eax
seto %al

Now, eax contains either 1 or zero depending on
the value in the overflow flag.

The pseudofunction _overflow() will just generate the
conditional jump, and the arguments will be evaluated as
normal function arguments that aren't pushed in the stack

 

[BartC]

Le 29/12/10 19:24, christian.bau a écrit :
[

Better solution:

bool _overflow (int arg);

]

P.S. your idea of an argument to _overflow() is quite clever.
Thanks for that, I think I will change lcc-win for it,
since the generated
code is exactly the same as if you write

c = a+b;
if (_overflow())

-->

if (_overflow(a+b))

Looks much better and generates the same code:
movl a,%eax
movl b,%ecx
addl %eax,%ecx
movl $0,%eax
seto %al

Now, eax contains either 1 or zero depending on
the value in the overflow flag.

I thought the proposal was quite different: to be able to specify an
expression of any complexity, and perhaps to bail out as soon as any
overflow status is seen.

Keeping _overflow() distinct from the expression also makes it easier to
make it optional.

 

[jacob navia]

Le 29/12/10 22:29, BartC a écrit :

I thought the proposal was quite different: to be able to specify an
expression of any complexity, and perhaps to bail out as soon as any
overflow status is seen.

You obtain that if you set the

#pragma overflow on/off

construct.


But that will check ALL expressions and ALL concerned integer
operations. If you are interested in a few operations only,
this second form is much better.

Keeping _overflow() distinct from the expression also makes it easier to
make it optional.

Of course not.

Look:

#ifndef STDC_OVERFLOW_SUPPORT
#define _overflow(a) a
#endif

 

[Keith Thompson]

Le 28/12/10 22:46, Keith Thompson a écrit : [...]

I'm almost tempted to suggest that adding exception handling to
the language might not be a completely horrible idea.

lcc-win proposes:

Can you clarify what you mean by "lcc-win proposes"? If you're
proposing that this should be added to a future C standard, it would
make more sense to say that *you* propose it; if not, I suggest that
"lcc-win implements" would make more sense. (I'm not picking on you,
just trying to understand.)

int a,b,c;
// ...
c = a+b;
if (_overflow()) {
}

What's wrong with that?

I won't say there's something *wrong* with it, and it's better
than nothing, but the precise semantics of _overflow() are not
at all obvious. It shares the same problems we already have with
errno, except that it applies to operators with expressions rather
than function calls. For one thing, unlike C++-style exceptions,
it's not scoped. Suppose I write:

x = y * z;
c = a + b;
if (_overflow()) {
...
}

If the multiplication overflows and the addition doesn't, what does
_overflow() return? What if there are multiple operations within
an expression? If each operation clears the overflow flag, undefined
evaluation orders mean that you can't safely use _overflow() unless
you restrict yourself to very simple expressions. And if it's
"sticky", is there a separate operation that clears the flag?

You probably have specific answers to most or all of these questions.
My point is that it's not obvious at the language level what those
answers should be.

I suggest that a mechanism that tells you whether an overflow
occurred anywhere within a specified chunk of code, perhaps
within the execution of a given expression, would be clearer.
Perhaps something like:

if (_overflow(c = a + b)) {
/* an overflow occurred */
}
else {
/* no overflow occurred */
}

Or just C++-like exception handling, for which we have ample existing
practice.

In i386asm:
addl %eax,%ecx
jo _overflowhandler

If this were to be added to the language, its semantics would have
to be defined in terms of actual program behavior, not in terms of
x86 instructions. Not all CPUs have overflow flags that behave
exactly like the x86 overflow flag.

 

[Keith Thompson]

On 12/28/2010 2:46 PM, Keith Thompson wrote: [...]

I'm almost tempted to suggest that adding exception handling to
the language might not be a completely horrible idea.

one could use thread-local storage for this...

AFAIK pretty much all (common?) OS's with threads also provide for TLS
and similar...

if errno was accessed via a function call, little would stop putting
this in TLS as well (however, as-is, doing so requires using compiler
specific extensions, such as the "__thread" modifier or similar for
MSVC, ...).

No compiler magic is needed. The standard specifically says that
errno is a macro that expands to a modifiable lvalue. For example,
on one implementation it expands to (*__errno_location ());
presumably the __errno_location function returns a pointer to an
object in thread-local storage, at least for programs that use
threading.

this way, one doesn't need to bother with providing a convoluted API to
manage status, ....

for example, AFAIK, OpenGL contexts are often handled via TLS, ...

or such...

Sure, and as we've seen over the last N decades this is usable. But
it's not terribly clean.

One consequence of the use of errno is that this expression:

sin(x) + cos(x)

may invoke undefined behavior. If sin() and cos() are both
implemented as macros, it could modify the object referred to
by errno twice between sequence points. (I suspect this doesn't
cause problems on any real-world implementations, but the potential
is there.)

 

[Keith Thompson]

There is no processor that hasn't an overflow flag.

[...]

I don't believe this is correct. In fact I seem to recall that
concrete counterexamples have been posted here.

And even if you're right, are you sure that all CPUs' overflow
flags behave the same way as the x86 overflow flag?

Performing a simple arithmetic operation with a check for overflow
is a fundamental operation, and I do find it frustrating that C
doesn't support it directly and makes it inordinately difficult to
support it indirectly. I'd love to see a good clean way to do this.
I just don't think that adding an intrinsic that queries the overflow
flag is the way to do it.

 

[Keith Thompson]

Le 29/12/10 15:34, christian.bau a écrit : [...]

What _precisely_ is the semantics of the "_overflow" function?

It returns 1 if the last operation overflowed, zero if not.
Concerned operations: signed +,-,*, and /.

What about shift operators? ++? --? Conversions? Array indexing?
Pointer arithmetic? What about division by 0? What *exactly*
does "the last operation" mean?

[...]

What bothers me is that you seem so upset that I offer a SOLUTION
instead of just allowing UB. Maybe you can offer a BETTER solution?

I am all ears.

Nobody is upset with you for offering a solution. We are offering
criticisms of the solution you're offering. If you don't want
criticism, I suggest not posting here. (That last was not meant
seriously; what I actually suggest is that you post here *and*
accept criticism.)

 

[BartC]

Le 29/12/10 22:29, BartC a écrit :

You obtain that if you set the

#pragma overflow on/off

construct.


But that will check ALL expressions and ALL concerned integer
operations. If you are interested in a few operations only,
this second form is much better.

OK. It's that clear exactly how _overflow() works. Your docs suggest that it
simply returns the processor's overflow flag, rather than a separate
'sticky' flag.

In what way does turning on this pragma change that?

And what would the new code look like when used as:

if (_overflow(a+b+c))... ?

Of course not.

Look:

#ifndef STDC_OVERFLOW_SUPPORT
#define _overflow(a) a
#endif

I was thinking of just commenting out the overflow checking lines...

 

[jacob navia]

Le 29/12/10 22:54, Keith Thompson a écrit :

Such implementations are non-conforming.

Bugs are non-conforming, Mr Thompson. And calling them names
will not make them go away.

 

[jacob navia]

Le 29/12/10 22:45, Keith Thompson a écrit :

There is no processor that hasn't an overflow flag.

[...]

I don't believe this is correct. In fact I seem to recall that
concrete counterexamples have been posted here.

Sure the DeathStar 9000... I know. But in that machine you can
always test for overflow as stated in the FAQ...

And even if you're right, are you sure that all CPUs' overflow
flags behave the same way as the x86 overflow flag?

I haven't come around a processor that couldn't test for overflow.

Maybe there are some micro-controllers that do not have that, but...

who cares?

Performing a simple arithmetic operation with a check for overflow
is a fundamental operation, and I do find it frustrating that C
doesn't support it directly and makes it inordinately difficult to
support it indirectly. I'd love to see a good clean way to do this.
I just don't think that adding an intrinsic that queries the overflow
flag is the way to do it.

I have never said that there should be "an intrinsic". That is how
it can be implemented it in the Power PC, for instance, or in the intel
machines, but it could be implemented differently in other machines.

You are reading things I did not write. Please keep centered in
what I actually said.

Thanks

 

[jacob navia]

Le 29/12/10 22:51, Keith Thompson a écrit :

Le 29/12/10 15:34, christian.bau a écrit : [...]

What _precisely_ is the semantics of the "_overflow" function?

It returns 1 if the last operation overflowed, zero if not.
Concerned operations: signed +,-,*, and /.

What about shift operators? ++?

Included if signed

--?
Included if signed

Conversions?

Overflow should be detected in conversions.

Array indexing?

Depends if the index is signed or not.

Pointer arithmetic?

Should be detected of course. If
0xFFFFE + 0x100 overflows it gives a bad address.

What about division by 0?

That is trapped anyway in most machines.

What *exactly*
does "the last operation" mean?

The last operation. Can't you understand english?

Last operation in this context means any of the four
operations where the operands are signed. I hope
I do not have to explain to you hat "last" means.

Note that it can be impossible to know how the compiler
will schedule operations in complex expressions,
so to have good results it is better to test operations
individually.

[...]

What bothers me is that you seem so upset that I offer a SOLUTION
instead of just allowing UB. Maybe you can offer a BETTER solution?

I am all ears.

Nobody is upset with you for offering a solution. We are offering
criticisms of the solution you're offering. If you don't want
criticism, I suggest not posting here. (That last was not meant
seriously; what I actually suggest is that you post here *and*
accept criticism.)

I have always accepted good ideas. Mr Bau proposed

int _overflow(int expr);

You would write:

if (_overflow(a+1000)) {
}

for instance. I think that is an even better solution than mine. If
I have time I will implement it.

 

[jacob navia]

Le 29/12/10 22:34, Keith Thompson a écrit :

Le 28/12/10 22:46, Keith Thompson a écrit : [...]

I'm almost tempted to suggest that adding exception handling to
the language might not be a completely horrible idea.

lcc-win proposes:

Can you clarify what you mean by "lcc-win proposes"? If you're
proposing that this should be added to a future C standard, it would
make more sense to say that *you* propose it; if not, I suggest that
"lcc-win implements" would make more sense. (I'm not picking on you,
just trying to understand.)

int a,b,c;
// ...
c = a+b;
if (_overflow()) {
}

What's wrong with that?

I won't say there's something *wrong* with it, and it's better
than nothing, but the precise semantics of _overflow() are not
at all obvious. It shares the same problems we already have with
errno, except that it applies to operators with expressions rather
than function calls. For one thing, unlike C++-style exceptions,
it's not scoped. Suppose I write:

x = y * z;
c = a + b;
if (_overflow()) {
...
}

If the multiplication overflows and the addition doesn't, what does
_overflow() return?

Zero since the last operation did not overflow. Note that the
behavior is NOT sticky. Note too that if you want to check complex
expressions you should use

#pragma overflow on/off

What if there are multiple operations within
an expression?

The last one wins.

If each operation clears the overflow flag, undefined
evaluation orders mean that you can't safely use _overflow() unless
you restrict yourself to very simple expressions.
Exactly

And if it's
"sticky", is there a separate operation that clears the flag?

That's why it should NOT be sticky. You would have to clear the flag.

You probably have specific answers to most or all of these questions.
My point is that it's not obvious at the language level what those
answers should be.

There can't be any BEST SOLUTION FOR ALL PRESENT PAST AND FUTURE
machines. There can only be a compromise solution that is easy
to implement in most machines and will need complex code in
others. In any case it can always be done with other operations
in C.

I suggest that a mechanism that tells you whether an overflow
occurred anywhere within a specified chunk of code, perhaps
within the execution of a given expression, would be clearer.
Perhaps something like:

if (_overflow(c = a + b)) {
/* an overflow occurred */
}
else {
/* no overflow occurred */
}

Yes, that was what Mr Bau proposed. It is a better idea.

Or just C++-like exception handling, for which we have ample existing
practice.

My compiler doesn't need exception handling. I generate a call to
a procedure with __FILE__ and __LINE__ as arguments. The procedure
prints an error message in stderr and the program exists. Other
solutions are possible. The standard should decide which ones.

I think the best would be to call a procedure with a standard
name (_overflowHandler() for instance), that the user can define

If the user doesn't define any, gthe compiler supplies a default
one that prints an error message and aborts.

If this were to be added to the language, its semantics would have
to be defined in terms of actual program behavior, not in terms of
x86 instructions. Not all CPUs have overflow flags that behave
exactly like the x86 overflow flag.

That was an example of implementation. Not a guideline.

 

[jacob navia]

Le 29/12/10 23:26, BGB a écrit :

granted, my vote is probably more for using TLS or similar, and probably
status clearing.

I think there is a misundertstanding here.

ALL flags are preserved across threads.

ALWAYS.

If not, threads would not work. Suppose:

cmpl %eax, $23
jne somelabel

Suppose that we have a thread switch after the compare instruction
and the conditional jump. If the flags weren't preserved across
context switches that would not work!!!

Actually NOTHING would work.

FLAGS ARE PRESERVED across thread switches, there is NO need
for TLS.

The OS MUST ensure that all flags and CPU context is preserved
across context and thread switches.

jacob

 

[BGB]

I'd suggest simply moving to C++ for the situations where you need to
fail explicitly rather than suffer the silent overflow. The mechanism
is there already -- and so is operator overloading, to make it
readable.

This was after all one of the reasons C++ got created in the first
place.

well, not always is moving to C++ in itself a reasonable option...

one example is, for example, when targeting a non-standard target
(uncommon CPU arch, or for a VM-based target) for which writing a C++
compiler would be an added hassle (vs C, which is at least a little
easier to write a compiler for).

 

[BartC]

Le 29/12/10 22:45, Keith Thompson a écrit :

I haven't come around a processor that couldn't test for overflow.

Maybe there are some micro-controllers that do not have that, but...

who cares?

Exactly. Why do languages have to care about the lowest common denominator
in processors?

I think C spreads itself too thinly. And if C implementations for
micro-controllers can have their own special, targeted version of the
language, why can't desktop versions?

 

[jacob navia]

Le 29/12/10 23:20, jacob navia a écrit :

Le 29/12/10 22:51, Keith Thompson a écrit :

Le 29/12/10 15:34, christian.bau a écrit : [...]
What _precisely_ is the semantics of the "_overflow" function?

It returns 1 if the last operation overflowed, zero if not.
Concerned operations: signed +,-,*, and /.

What about shift operators? ++?

Included if signed

Sorry that is misleading.

Shift operations should NOT provoke any overflow

The ++ operator should.

 

[BGB]

Le 29/12/10 23:26, BGB a écrit :

I think there is a misundertstanding here.

ALL flags are preserved across threads.

ALWAYS.

If not, threads would not work. Suppose:

cmpl %eax, $23
jne somelabel

Suppose that we have a thread switch after the compare instruction
and the conditional jump. If the flags weren't preserved across
context switches that would not work!!!

Actually NOTHING would work.

FLAGS ARE PRESERVED across thread switches, there is NO need
for TLS.

The OS MUST ensure that all flags and CPU context is preserved
across context and thread switches.

only if using CPU status flags...

if one doesn't want to depend on CPU status flags as the definition,
then an alternate means of storing them is needed, such as putting them
in a TLS variable or similar...


one can think of it as, say:
add eax, ecx
pushfd
pop eax
mov fs:[...], eax ;non-sticky
or fs:[...], eax ;sticky
....
mov eax, fs:[...]
and eax, ...
....

possibly while giving the compiler special permission to not use TLS if
it can verify that it doesn't need to.


TLS is also needed if one wants to support a pure C fallback
implementation (and doesn't want cross-thread interference), say:

THREAD int su_status;
THREAD int su_stickystatus;

s32 suAddInt32(s32 a, s32 b)
{
su_status=0;
if(b>=0)
{
if(a>(2147483647-b))
su_status=SU_FL_OVERFLOW;
}else
{
if(a<(-2147483648-b))
su_status=SU_FL_OVERFLOW|SU_FL_SIGN;
}
su_stickystatus|=su_status;
return(a+b);
}

or similar...

 

[Keith Thompson]

Le 29/12/10 22:54, Keith Thompson a écrit :

Bugs are non-conforming, Mr Thompson.

Agreed; did I imply otherwise?

And calling them names
will not make them go away.

Agreed (unless it brings them to the attention of someone who's in a
position to fix them).

 

[Keith Thompson]

Le 29/12/10 22:45, Keith Thompson a écrit :

There is no processor that hasn't an overflow flag.

[...]

I don't believe this is correct. In fact I seem to recall that
concrete counterexamples have been posted here.

Sure the DeathStar 9000... I know. But in that machine you can
always test for overflow as stated in the FAQ...

No, I am not referring to the DeathStar 9000. I am referring to a
specific real-world microprocessor that does not have an overflow
flag. (The DEC/Compaq/HP Alpha, perhaps?) I don't remember the
details; perhaps someone else can dig them up.

I haven't come around a processor that couldn't test for overflow.

That wasn't the question. Are you sure that all CPUs' overflow
flags behave the same way as the x86 overflow flag? Is the flag
always set or cleared in the same circumstances?

Maybe there are some micro-controllers that do not have that, but...

who cares?

Anyone who either uses those micro-controllers or who care about
portable code.

I have never said that there should be "an intrinsic". That is how
it can be implemented it in the Power PC, for instance, or in the intel
machines, but it could be implemented differently in other machines.

You are reading things I did not write. Please keep centered in
what I actually said.

Ok. What you actually said is "There is no processor that hasn't an
overflow flag". As I said, I don't believe that's correct.

 

[Keith Thompson]

Exactly. Why do languages have to care about the lowest common denominator
in processors?

So that we can write portable code by following the C standard.

I think C spreads itself too thinly. And if C implementations for
micro-controllers can have their own special, targeted version of the
language, why can't desktop versions?

Because it's not necessary. Because the cost of losing portability
of standard-conforming code to desktop systems exceeds the benefit
of having different versions of the language for different systems.

We can certainly have *extensions* for particular systems, but the
core language should be portable to a wide range of systems. That's
the whole point of having a language standard.