Efficient detection of signed overflow?

Efficient detection of signed overflow?

[Mark Dickinson]

I've just found myself looking at a piece of C code like the
snippet given below.  It's supposed to be adding two longs
and doing something special when the sum overflows.
Here a and b could have any value, but are likely to be small
in the common case.  The snippet occurs in a fairly performance-
critical section of code.

long a, b, x;
...
x = a + b;
if ((x^a) < 0 && (x^b) < 0)
    goto deal_with_overflow;
...

This code is wrong, I think, because it depends on undefined
behaviour.  I'm wondering how best to rewrite it so that (a)
the replacement code is correct and portable C89, and (b)
there's a reasonable chance of gcc compiling it to efficient
assembler on common platforms.

A bullet-proof solution (valid even in the presence of ones'
complement machines, trap representations, etc.) is
something like:

if ((a >= 0 && 0UL + a > (unsigned long)LONG_MAX - b) ||
    (a < 0 && 0UL - a > b - (unsigned long)LONG_MIN))
    goto deal_with_overflow;
x = a + b;

but, not surprisingly, this generates rather inefficient assembler
(with gcc-4.4 -O3).

Any suggestions for improvements over this?

On x86 or x86-64, the optimal generated code would
presumably consist of just two instructions:  an addition
followed by a jump-on-overflow.  Unfortunately, using
inline assembly isn't really an option here.  Are there
any common C code constructs that gcc would compile
to a jump-on-overflow instruction on x86?

Mark

Re: Efficient detection of signed overflow?

[Florian Weimer]

* Mark Dickinson:

> long a, b, x;
> ...
> x = a + b;
> if ((x^a) < 0 && (x^b) < 0)
>     goto deal_with_overflow;
> ...

Would this test be better?  I think it's equivalent, and it saves a
comparison.

  if (((x ^ a) & (x ^ b)) < 0)

> Any suggestions for improvements over this?

Use -fwrapv and your first version.

> Are there any common C code constructs that gcc would compile to a
> jump-on-overflow instruction on x86?

I don't think so.  Without support throughout GCC, anything in this
area (like a builtin) would mostly act as an optimization barrier.

Re: Efficient detection of signed overflow?

[me22]

2009/11/29 Mark Dickinson <dickinsm@gmail.com>:
>
> This code is wrong, I think, because it depends on undefined
> behaviour.  I'm wondering how best to rewrite it so that (a)
> the replacement code is correct and portable C89, and (b)
> there's a reasonable chance of gcc compiling it to efficient
> assembler on common platforms.
>

What about using (long)((unsigned long)a + (unsigned long)b) or
something to get around the UB?

Re: Efficient detection of signed overflow?

[Mark Dickinson]

On Sun, Nov 29, 2009 at 8:53 PM, Florian Weimer <fw@deneb.enyo.de> wrote:
> * Mark Dickinson:
> [...]
>> if ((x^a) < 0 && (x^b) < 0)
>
> Would this test be better?  I think it's equivalent, and it saves a
> comparison.
>
>  if (((x ^ a) & (x ^ b)) < 0)

Mmm.  Quite possibly, yes.  I'll do some timings.

>> Any suggestions for improvements over this?
>
> Use -fwrapv and your first version.

gcc isn't the only compiler that's going to have to compile
this code, so it still needs to be fixed to avoid undefined
behaviour (and I'm worried about -fwrapv inhibiting optimizations
elsewhere in the codebase).  But I guess that casting everything in
sight to unsigned long and then casting the eventual result
back to long, as me22 suggests, would be pretty much equivalent.

On Sun, Nov 29, 2009 at 9:00 PM, me22 <me22.ca@gmail.com> wrote:
> What about using (long)((unsigned long)a + (unsigned long)b) or
> something to get around the UB?

Yep, that looks like the solution.  Thanks!

Mark

Re: Efficient detection of signed overflow?

[Florian Weimer]

* Mark Dickinson:

>>> Any suggestions for improvements over this?
>>
>> Use -fwrapv and your first version.
>
> gcc isn't the only compiler that's going to have to compile
> this code, so it still needs to be fixed to avoid undefined
> behaviour

Most compiler support something like -fwrapv.

> On Sun, Nov 29, 2009 at 9:00 PM, me22 <me22.ca@gmail.com> wrote:
>> What about using (long)((unsigned long)a + (unsigned long)b) or
>> something to get around the UB?
>
> Yep, that looks like the solution.  Thanks!

You'd also have to compare against (1 << (sizeof(long) * CHAR_BITS -
1)) instead of 0, pessimizing the code somewhat.

Re: Efficient detection of signed overflow?

[me22]

2009/11/30 Florian Weimer <fw@deneb.enyo.de>:
>
>> On Sun, Nov 29, 2009 at 9:00 PM, me22 <me22.ca@gmail.com> wrote:
>>> What about using (long)((unsigned long)a + (unsigned long)b) or
>>> something to get around the UB?
>
> You'd also have to compare against (1 << (sizeof(long) * CHAR_BITS -
> 1)) instead of 0, pessimizing the code somewhat.
>

Why?  If numbers are 2s-complement, the cast back to a signed type is
well-defined, isn't it?

Re: Efficient detection of signed overflow?

[Mark Dickinson]

On Mon, Nov 30, 2009 at 1:54 PM, me22 <me22.ca@gmail.com> wrote:
> 2009/11/30 Florian Weimer <fw@deneb.enyo.de>:
>>
>>> On Sun, Nov 29, 2009 at 9:00 PM, me22 <me22.ca@gmail.com> wrote:
>>>> What about using (long)((unsigned long)a + (unsigned long)b) or
>>>> something to get around the UB?
>>
>> You'd also have to compare against (1 << (sizeof(long) * CHAR_BITS -
>> 1)) instead of 0, pessimizing the code somewhat.
>>
>
> Why?  If numbers are 2s-complement, the cast back to a signed type is
> well-defined, isn't it?

In practice, yes, I think so.  In theory, no: the result of the conversion is
implementation defined for numbers outside the range of the signed type.
(C99 6.3.1.3).  But I'd be surprised if any implementation on a two's
complement machine does anything other than just preserve the bit
pattern, as you'd expect.

Mark

Re: Efficient detection of signed overflow?

[me22]

2009/11/30 Mark Dickinson <dickinsm@gmail.com>:
>
> In practice, yes, I think so.  In theory, no: the result of the conversion is
> implementation defined for numbers outside the range of the signed type.
> (C99 6.3.1.3).  But I'd be surprised if any implementation on a two's
> complement machine does anything other than just preserve the bit
> pattern, as you'd expect.
>

Thanks for clarifying.

I guess I was thinking of C++ aliasing rules (3.10/15), where reading
a signed through an unsigned or vice versa is allowed, but as you
point out, that doesn't define their value (4.7/3 does).

FWIW, though, I just checked in llvm-gcc, and both of these compile to
the same IR:

    int foo(int i) {
        return i < 0;
    }

    int foo(unsigned i) {
        return i >= (1 << (sizeof(unsigned)*CHAR_BIT-1));
    }

So it might not be a pessimization after all to be strictly portable.

~ Scott

(Sorry if using LLVM as an example is heresy here; it's easier for me
to test while I'm on a machine without GCC :P)

Re: Efficient detection of signed overflow?

[Florian Weimer]

* Mark Dickinson:

> In practice, yes, I think so.  In theory, no: the result of the conversion is
> implementation defined for numbers outside the range of the signed type.
> (C99 6.3.1.3).  But I'd be surprised if any implementation on a two's
> complement machine does anything other than just preserve the bit
> pattern, as you'd expect.

It really depends on your compiler writer's meaning of
"implementation-defined".  It's not too far-fetched that some think
that the comparison against zero should be replaced with 0 because it
can never be true.

Re: Efficient detection of signed overflow?

[Lawrence Crowl]

On 11/30/09, Florian Weimer <fw@deneb.enyo.de> wrote:
> * Mark Dickinson:
> > In practice, yes, I think so.  In theory, no: the result of the
> > conversion is implementation defined for numbers outside the
> > range of the signed type.  (C99 6.3.1.3).  But I'd be surprised
> > if any implementation on a two's complement machine does anything
> > other than just preserve the bit pattern, as you'd expect.
>
> It really depends on your compiler writer's meaning of
> "implementation-defined".  It's not too far-fetched that some
> think that the comparison against zero should be replaced with
> 0 because it can never be true.

Gcc does optimizations based on knowing that signed integer overflow
is undefined behavior.  It may not catch conversion right now,
but given time, it will.  Your best portability bet is to avoid the
overflow by first testing for the conditions under which overflow
will occur.

jmp_buf env;

long add( long a, long b )
{
    long x;
    if ( a > 0 )
        if ( LONG_MAX - a < b )
            longjmp( env, 1 );
        else
            x = a + b;
    else
        if ( LONG_MIN - a > b )
            longjmp( env, 1 );
        else
            x = a + b;
    return x;
}

Yes, it is more expensive than one would like.

-- 
Lawrence Crowl

Re: Efficient detection of signed overflow?

[Mark Dickinson]

On Tue, Dec 1, 2009 at 12:39 AM, Lawrence Crowl <crowl@google.com> wrote:
> Gcc does optimizations based on knowing that signed integer overflow
> is undefined behavior.  It may not catch conversion right now,
> but given time, it will.

This surprises me.  My understanding was that the result of
a conversion from an unsigned integer type to a signed
integer type, when the unsigned value doesn't fit into the
range of the signed type, is merely implementation defined
rather than undefined behaviour.  Section 4.5 of gcc's manual
seems to say that gcc chooses to wrap modulo 2**(width
of the signed type) in this case.  Is this likely to change
in future gcc versions?

Mark

Re: Efficient detection of signed overflow?

[Segher Boessenkool]

>> Gcc does optimizations based on knowing that signed integer overflow
>> is undefined behavior.  It may not catch conversion right now,
>> but given time, it will.
>
> This surprises me.  My understanding was that the result of
> a conversion from an unsigned integer type to a signed
> integer type, when the unsigned value doesn't fit into the
> range of the signed type, is merely implementation defined
> rather than undefined behaviour.

Your understanding is correct.

> Section 4.5 of gcc's manual
> seems to say that gcc chooses to wrap modulo 2**(width
> of the signed type) in this case.  Is this likely to change
> in future gcc versions?

It is documented behaviour, so it is unlikely to change any time
soon; it isn't likely to change until we all stop using two's
complement, anyway ;-)


Segher

Re: Efficient detection of signed overflow?

[Florian Weimer]

* Mark Dickinson:

> On Tue, Dec 1, 2009 at 12:39 AM, Lawrence Crowl <crowl@google.com> wrote:
>> Gcc does optimizations based on knowing that signed integer overflow
>> is undefined behavior.  It may not catch conversion right now,
>> but given time, it will.
>
> This surprises me.  My understanding was that the result of
> a conversion from an unsigned integer type to a signed
> integer type, when the unsigned value doesn't fit into the
> range of the signed type, is merely implementation defined
> rather than undefined behaviour.

There are some who think that, when properly documented,
implementation-defined behavior can result in arbitrary effects, just
as undefined behavior.

> Section 4.5 of gcc's manual seems to say that gcc chooses to wrap
> modulo 2**(width of the signed type) in this case.  Is this likely
> to change in future gcc versions?

I wouldn't rule it out.  Just use -fwrapv (perhaps after benchmarking
to make sure that it doesn't make a difference).  Other compilers will
have similar switches.

Re: Efficient detection of signed overflow?

[Andrew Haley]

Florian Weimer wrote:
> * Mark Dickinson:
> 
>> On Tue, Dec 1, 2009 at 12:39 AM, Lawrence Crowl <crowl@google.com> wrote:
>>> Gcc does optimizations based on knowing that signed integer overflow
>>> is undefined behavior.  It may not catch conversion right now,
>>> but given time, it will.
>> This surprises me.  My understanding was that the result of
>> a conversion from an unsigned integer type to a signed
>> integer type, when the unsigned value doesn't fit into the
>> range of the signed type, is merely implementation defined
>> rather than undefined behaviour.
> 
> There are some who think that, when properly documented,
> implementation-defined behavior can result in arbitrary effects, just
> as undefined behavior.
> 
>> Section 4.5 of gcc's manual seems to say that gcc chooses to wrap
>> modulo 2**(width of the signed type) in this case.  Is this likely
>> to change in future gcc versions?
> 
> I wouldn't rule it out.  Just use -fwrapv (perhaps after benchmarking
> to make sure that it doesn't make a difference).  Other compilers will
> have similar switches.

This is bad advice.  -fwrapv suppresses loop optimizations.  Given that
it's not difficult to detect overflow with perfectly compliant code, there's
no point.

Andrew.

Re: Efficient detection of signed overflow?

[Bob Plantz]

On Sun, 2009-11-29 at 16:00 -0500, me22 wrote:

> 
> What about using (long)((unsigned long)a + (unsigned long)b) or
> something to get around the UB?

Type casting may be ineffective. On x86-64 in 64-bit mode gcc (4.4.1)
generates unsigned addition. That is,

x = a + b;

is implemented as

leaq	(%rdx,%rax), %rbx

The leaq instruction has no effect on the rflags register. Hence, even
if we could test the overflow bit, it would not be accurate.

--Bob

Re: Efficient detection of signed overflow?

[Florian Weimer]

* Andrew Haley:

>> I wouldn't rule it out.  Just use -fwrapv (perhaps after benchmarking
>> to make sure that it doesn't make a difference).  Other compilers will
>> have similar switches.
>
> This is bad advice.  -fwrapv suppresses loop optimizations.

Some loop optimizations perhaps, which are likely not to be relevant
for the code base in the question.

> Given that it's not difficult to detect overflow with perfectly
> compliant code, there's no point.

The fully compliant solution has an additional performance overhead
compared to the one that assumes -fwrapv.  Instead of -fwrapv, you can
rely on additional guarantees from the documentation, but for someone
that ships code to be compiled with unknown GCC versions, this might
not be the best solution.

Re: Efficient detection of signed overflow?

[Andrew Haley]

Florian Weimer wrote:
> * Andrew Haley:
> 
>>> I wouldn't rule it out.  Just use -fwrapv (perhaps after benchmarking
>>> to make sure that it doesn't make a difference).  Other compilers will
>>> have similar switches.
>> This is bad advice.  -fwrapv suppresses loop optimizations.
> 
> Some loop optimizations perhaps, which are likely not to be relevant
> for the code base in the question.

Hmm...

>> Given that it's not difficult to detect overflow with perfectly
>> compliant code, there's no point.
> 
> The fully compliant solution has an additional performance overhead
> compared to the one that assumes -fwrapv.  Instead of -fwrapv, you can
> rely on additional guarantees from the documentation, but for someone
> that ships code to be compiled with unknown GCC versions, this might
> not be the best solution.

The test was, if I recall correctly

  x = a + b;
  if ((x ^ a) & (x ^ b)) < 0)

all you have to do is convert everything to unsigned values, then

  ux = ua + ub;
  if ((ux ^ ua) & (ux ^ ub)) & (unsigned)INT_MIN))
    goto deal_with_overflow;
  // we now know there is no overflow
  x = ux;

which is exactly the same test as before, but perfectly compliant.

Andrew.

Re: Efficient detection of signed overflow?

[Florian Weimer]

* Andrew Haley:

> The test was, if I recall correctly
>
>   x = a + b;
>   if ((x ^ a) & (x ^ b)) < 0)
>
> all you have to do is convert everything to unsigned values, then
>
>   ux = ua + ub;
>   if ((ux ^ ua) & (ux ^ ub)) & (unsigned)INT_MIN))
>     goto deal_with_overflow;
>   // we now know there is no overflow
>   x = ux;
>
> which is exactly the same test as before, but perfectly compliant.

The comment is wrong.  The code checks for signed overflow, but the
following assignment still overflwos when ux is larger than INT_MAX.
So this version is usable exactly under the same circumstances as the
first one.

And the comparison against 0 results in tighter code. 8-)

Re: Efficient detection of signed overflow?

[Andrew Haley]

Florian Weimer wrote:
> * Andrew Haley:
> 
>> The test was, if I recall correctly
>>
>>   x = a + b;
>>   if ((x ^ a) & (x ^ b)) < 0)
>>
>> all you have to do is convert everything to unsigned values, then
>>
>>   ux = ua + ub;
>>   if ((ux ^ ua) & (ux ^ ub)) & (unsigned)INT_MIN))
>>     goto deal_with_overflow;
>>   // we now know there is no overflow
>>   x = ux;
>>
>> which is exactly the same test as before, but perfectly compliant.
> 
> The comment is wrong.  The code checks for signed overflow, but the
> following assignment still overflwos when ux is larger than INT_MAX.
> So this version is usable exactly under the same circumstances as the
> first one.

Ahhh, I see.  Hmm, there must be a decent way to do this.

> And the comparison against 0 results in tighter code. 8-)

Heh.

Andrew.

Re: Efficient detection of signed overflow?

[Segher Boessenkool]

>> The test was, if I recall correctly
>>
>>   x = a + b;
>>   if ((x ^ a) & (x ^ b)) < 0)
>>
>> all you have to do is convert everything to unsigned values, then
>>
>>   ux = ua + ub;
>>   if ((ux ^ ua) & (ux ^ ub)) & (unsigned)INT_MIN))
>>     goto deal_with_overflow;
>>   // we now know there is no overflow
>>   x = ux;
>>
>> which is exactly the same test as before, but perfectly compliant.
>
> The comment is wrong.  The code checks for signed overflow, but the
> following assignment still overflwos when ux is larger than INT_MAX.

No, it doesn't.  This conversion is implementation-defined (6.3.1.3/3),
and GCC does the obvious two's complement thing.  This code is fine.


Segher

Re: Efficient detection of signed overflow?

[Florian Weimer]

* Segher Boessenkool:

>> The comment is wrong.  The code checks for signed overflow, but the
>> following assignment still overflwos when ux is larger than INT_MAX.
>
> No, it doesn't.  This conversion is implementation-defined (6.3.1.3/3),
> and GCC does the obvious two's complement thing.  This code is fine.

It's fine with GCC 4.4, and likely with GCC 4.5 as well.  But what
about GCC 4.6?  And how will a user compiling third-party software
notice the discrepancy (if it ever arises)?

Re: Efficient detection of signed overflow?

[Segher Boessenkool]

>>> The comment is wrong.  The code checks for signed overflow, but the
>>> following assignment still overflwos when ux is larger than INT_MAX.
>>
>> No, it doesn't.  This conversion is implementation-defined (6.3.1.3/3),
>> and GCC does the obvious two's complement thing.  This code is fine.
>
> It's fine with GCC 4.4, and likely with GCC 4.5 as well.  But what
> about GCC 4.6?  And how will a user compiling third-party software
> notice the discrepancy (if it ever arises)?

Implementation-defined means the implementation defines
the behaviour, and GCC defines it like this:

   * `The result of, or the signal raised by, converting an integer to a
     signed integer type when the value cannot be represented in an
     object of that type (C90 6.2.1.2, C99 6.3.1.3).'

     For conversion to a type of width N, the value is reduced modulo
     2^N to be within range of the type; no signal is raised.

If this is ever to change, I'm sure you will hear about it.
Paranoid users can check the manual at every compiler release.


Segher

Re: Efficient detection of signed overflow?

[Segher Boessenkool]

>>> The test was, if I recall correctly
>>>
>>>   x = a + b;
>>>   if ((x ^ a) & (x ^ b)) < 0)
>>>
>>> all you have to do is convert everything to unsigned values, then
>>>
>>>   ux = ua + ub;
>>>   if ((ux ^ ua) & (ux ^ ub)) & (unsigned)INT_MIN))
>>>     goto deal_with_overflow;
>>>   // we now know there is no overflow
>>>   x = ux;
>>>
>>> which is exactly the same test as before, but perfectly compliant.
>>
>> The comment is wrong.  The code checks for signed overflow, but the
>> following assignment still overflwos when ux is larger than INT_MAX.
>> So this version is usable exactly under the same circumstances as the
>> first one.
>
> Ahhh, I see.  Hmm, there must be a decent way to do this.

Oh, it needs to be absolutely portable?  Well, you're already
assuming two's complement.

if (ux <= LONG_MAX) /* or whatever the type was */
  x = ux;
else {
  x = ux + LONG_MIN;
  x += LONG_MIN;
}

should do the trick I think?


Segher

Re: Efficient detection of signed overflow?

[Andrew Haley]

Segher Boessenkool wrote:
>>>> The comment is wrong.  The code checks for signed overflow, but the
>>>> following assignment still overflwos when ux is larger than INT_MAX.
>>> No, it doesn't.  This conversion is implementation-defined (6.3.1.3/3),
>>> and GCC does the obvious two's complement thing.  This code is fine.
>> It's fine with GCC 4.4, and likely with GCC 4.5 as well.  But what
>> about GCC 4.6?  And how will a user compiling third-party software
>> notice the discrepancy (if it ever arises)?
> 
> Implementation-defined means the implementation defines
> the behaviour, and GCC defines it like this:

We know, we already discussed this upthread.  The question is not
whether it works, but how to do it portably, not just for gcc.
Depending on 2's complement is fine, but depending on a particular
compiler is less so.

Andrew.