Handling integer overflow

In a previous article I showed that the Swift compiler checks for overflow after every mathematical operation, like this assembly fragment:

         imul    rdi, r8
         jo      .LBB1_10

That's part of the language; in C or C++ you have to do it yourself. Can we get the compiler to help out? Let's explore some options using the Compiler Explorer.

Detecting overflow with integer comparison

The code I'll work with is the following, which attempts to add two 64-bit values and add the carry in a second 64-bit output:

typedef unsigned long long u64;

// Add x to low, and add any carry to high
void add( u64 &high, u64 &low, u64 x ) {
    u64 orig = low;
    low += x;
    if ( orig > low ) {
        high += 1;
    }
}

GCC return compiles to this verison:

It successfully avoided an extra subtraction to do the comparison, and just checked the carry flag, but it used a branch to avoid the addition.

Clang manages to do it a little more simply, but still with a branch:

What's the best we can do? Well this case, we could be using the ADC (add-with-carry) instruction, which adds 1 to the result if the carry flag is set.

 clc    
 adc    QWORD PTR [rsi],rdx
 adc    QWORD PTR [rdi],0x0
 ret  

Or maybe even

 add    QWORD PTR [rsi],rdx   # no carry in, but carry out
 adc    QWORD PTR [rdi],0x0   # carry in *and* carry out
 ret  

I don't think we can convince the compiler to emit this version. In fact, the GNU MultiPrecision library (GMP) uses assembly for exactly this purpose, when it's adding two multi-word integers the inner loop looks like this (sorry for the switch away from Intel syntax):

L(top): ADCSBB  (vp), %r8
    ADCSBB  8(vp), %r9
    ADCSBB  16(vp), %r10
    ADCSBB  24(vp), %r11
    mov %r8, (rp)
    lea 32(up), up
    mov %r9, 8(rp)
    mov %r10, 16(rp)
    dec n
    mov %r11, 24(rp)
    lea 32(vp), vp
    mov (up), %r8
    mov 8(up), %r9
    lea 32(rp), rp
L(mid): mov 16(up), %r10
    mov 24(up), %r11
    jnz L(top)

The same code is used for both addition and subtraction, so ADDSBB is a macro. Source

A side node: the DEC instruction specifically doesn't touch the carry flag, so it can be used in cases like this one where we want to preserve the flag into the next iteration of the loop.

Detecting overflow directly with a builtin function

Both GCC and Clang support a builtin function which checks for overflow. To use it, we can write:

void add_ovf( u64 &high, u64 &low, u64 x ) {
    u64 out;
    if ( __builtin_add_overflow( low, x, &out ) ) {
        high += 1;
    }
    low = out;
}

GCC produces a little bit of a tangle:

While clang only jumps forward:

This gives the compiler a big hint that we are interested in the carry flag, which it successfully uses for the branch. But neither understands that the conditional branch could be replaced by ADC. I'm not quite sure why the compiler chose to add memory-to-register, then move the result back, rather than register-to-memory, It looks like ADD supports both.

Similar builtins exist for other operations subject to integer overflow.

Enabling runtime detection

The C and C++ standards explicitly state that there's no such thing as unsigned overflow! Unsigned integers are defined to wrap around modulo 2^N. But signed overflow is undefined behavior, and some compilers offer a flag that checks it. Let's simplify our function to:

void add( long long &low, long long x ) {
    low += x;
}

And compile with the command line flags -O3 -ftrapv. Sadly, the implementation of addition is now a function call!

So, we'd have to dig into GCC's runtime to figure out how they implemented it--- but because the integers are unsigned, the check is more complicated. I was easily able to find the LLVM version, which looks like this:

di_int
__addvdi3(di_int a, di_int b)
{
    di_int s = (du_int) a + (du_int) b;
    if (b >= 0)
    {
        if (s < a)
            compilerrt_abort();
    }
    else
    {
        if (s >= a)
            compilerrt_abort();
    }
    return s;
}