Compare against signed minimum/signed maximum by checking for overflow

[Kmeakin]

Instead of comparing against the constant, which may take more instructions (AArch64) or more bytes to encode (x86_64), add/subtract 1 and check for overflow:

https://godbolt.org/z/1scGEndG1

#include <limits>

template <typename T, typename V>
auto add_with_overflow(T x, V y) -> bool {
    T sum;
    return __builtin_add_overflow(x, y, &sum);
}

auto src1(int x) { return x == std::numeric_limits<int>::max(); }
auto tgt1(int x) { return add_with_overflow(x, 1); }

auto src2(int x) { return x == std::numeric_limits<int>::min(); }
auto tgt2(int x) { return add_with_overflow(x, -1); }

auto src3(long x) { return x == std::numeric_limits<long>::max(); }
auto tgt3(long x) { return add_with_overflow(x, 1); }

auto src4(long x) { return x == std::numeric_limits<long>::min(); }
auto tgt4(long x) { return add_with_overflow(x, -1); }

Assembly (AArch64)

src1(int):
        mov     w1, 2147483647
        cmp     w0, w1
        cset    w0, eq
        ret
tgt1(int):
        cmn     w0, 1
        cset    w0, vs
        ret
src2(int):
        mov     w1, -2147483648
        cmp     w0, w1
        cset    w0, eq
        ret
tgt2(int):
        cmp     w0, #1
        cset    w0, vs
        ret
src3(long):
        mov     x1, 9223372036854775807
        cmp     x0, x1
        cset    w0, eq
        ret
tgt3(long):
        cmn     x0, 1
        cset    w0, vs
        ret
src4(long):
        mov     x1, -9223372036854775808
        cmp     x0, x1
        cset    w0, eq
        ret
tgt4(long):
        cmp     x0, #1
        cset    w0, vs
        ret

Assembly (x86_64)

"src1(int)":
        cmp     edi, 2147483647
        sete    al
        ret
"tgt1(int)":
        add     edi, 1
        seto    al
        ret
"src2(int)":
        cmp     edi, -2147483648
        sete    al
        ret
"tgt2(int)":
        add     edi, -1
        seto    al
        ret
"src3(long)":
        movabs  rax, 9223372036854775807
        cmp     rdi, rax
        sete    al
        ret
"tgt3(long)":
        add     rdi, 1
        seto    al
        ret
"src4(long)":
        movabs  rax, -9223372036854775808
        cmp     rdi, rax
        sete    al
        ret
"tgt4(long)":
        add     rdi, -1
        seto    al
        ret

[llvmbot]

@llvm/issue-subscribers-backend-aarch64

Author: Karl Meakin (Kmeakin)

Instead of comparing against the constant, which may take more instructions (AArch64) or more bytes to encode (x86_64), add/subtract 1 and check for overflow:

https://godbolt.org/z/1scGEndG1

#include <limits>

template <typename T, typename V>
auto add_with_overflow(T x, V y) -> bool {
    T sum;
    return __builtin_add_overflow(x, y, &sum);
}

auto src1(int x) { return x == std::numeric_limits<int>::max(); }
auto tgt1(int x) { return add_with_overflow(x, 1); }

auto src2(int x) { return x == std::numeric_limits<int>::min(); }
auto tgt2(int x) { return add_with_overflow(x, -1); }

auto src3(long x) { return x == std::numeric_limits<long>::max(); }
auto tgt3(long x) { return add_with_overflow(x, 1); }

auto src4(long x) { return x == std::numeric_limits<long>::min(); }
auto tgt4(long x) { return add_with_overflow(x, -1); }

Assembly (AArch64)

src1(int):
        mov     w1, 2147483647
        cmp     w0, w1
        cset    w0, eq
        ret
tgt1(int):
        cmn     w0, 1
        cset    w0, vs
        ret
src2(int):
        mov     w1, -2147483648
        cmp     w0, w1
        cset    w0, eq
        ret
tgt2(int):
        cmp     w0, #<!-- -->1
        cset    w0, vs
        ret
src3(long):
        mov     x1, 9223372036854775807
        cmp     x0, x1
        cset    w0, eq
        ret
tgt3(long):
        cmn     x0, 1
        cset    w0, vs
        ret
src4(long):
        mov     x1, -9223372036854775808
        cmp     x0, x1
        cset    w0, eq
        ret
tgt4(long):
        cmp     x0, #<!-- -->1
        cset    w0, vs
        ret

Assembly (x86_64)

"src1(int)":
        cmp     edi, 2147483647
        sete    al
        ret
"tgt1(int)":
        add     edi, 1
        seto    al
        ret
"src2(int)":
        cmp     edi, -2147483648
        sete    al
        ret
"tgt2(int)":
        add     edi, -1
        seto    al
        ret
"src3(long)":
        movabs  rax, 9223372036854775807
        cmp     rdi, rax
        sete    al
        ret
"tgt3(long)":
        add     rdi, 1
        seto    al
        ret
"src4(long)":
        movabs  rax, -9223372036854775808
        cmp     rdi, rax
        sete    al
        ret
"tgt4(long)":
        add     rdi, -1
        seto    al
        ret

[llvmbot]

@llvm/issue-subscribers-backend-x86

Author: Karl Meakin (Kmeakin)

Instead of comparing against the constant, which may take more instructions (AArch64) or more bytes to encode (x86_64), add/subtract 1 and check for overflow:

https://godbolt.org/z/1scGEndG1

#include <limits>

template <typename T, typename V>
auto add_with_overflow(T x, V y) -> bool {
    T sum;
    return __builtin_add_overflow(x, y, &sum);
}

auto src1(int x) { return x == std::numeric_limits<int>::max(); }
auto tgt1(int x) { return add_with_overflow(x, 1); }

auto src2(int x) { return x == std::numeric_limits<int>::min(); }
auto tgt2(int x) { return add_with_overflow(x, -1); }

auto src3(long x) { return x == std::numeric_limits<long>::max(); }
auto tgt3(long x) { return add_with_overflow(x, 1); }

auto src4(long x) { return x == std::numeric_limits<long>::min(); }
auto tgt4(long x) { return add_with_overflow(x, -1); }

Assembly (AArch64)

src1(int):
        mov     w1, 2147483647
        cmp     w0, w1
        cset    w0, eq
        ret
tgt1(int):
        cmn     w0, 1
        cset    w0, vs
        ret
src2(int):
        mov     w1, -2147483648
        cmp     w0, w1
        cset    w0, eq
        ret
tgt2(int):
        cmp     w0, #<!-- -->1
        cset    w0, vs
        ret
src3(long):
        mov     x1, 9223372036854775807
        cmp     x0, x1
        cset    w0, eq
        ret
tgt3(long):
        cmn     x0, 1
        cset    w0, vs
        ret
src4(long):
        mov     x1, -9223372036854775808
        cmp     x0, x1
        cset    w0, eq
        ret
tgt4(long):
        cmp     x0, #<!-- -->1
        cset    w0, vs
        ret

Assembly (x86_64)

"src1(int)":
        cmp     edi, 2147483647
        sete    al
        ret
"tgt1(int)":
        add     edi, 1
        seto    al
        ret
"src2(int)":
        cmp     edi, -2147483648
        sete    al
        ret
"tgt2(int)":
        add     edi, -1
        seto    al
        ret
"src3(long)":
        movabs  rax, 9223372036854775807
        cmp     rdi, rax
        sete    al
        ret
"tgt3(long)":
        add     rdi, 1
        seto    al
        ret
"src4(long)":
        movabs  rax, -9223372036854775808
        cmp     rdi, rax
        sete    al
        ret
"tgt4(long)":
        add     rdi, -1
        seto    al
        ret

[Explorer09]

For comparing with std::numeric_limits<long>::min() case, perhaps there's a much easier way (for x86).

tgt4_b(long):
    neg    %rdi
    seto   %al
    ret

I think you can get it. The similar can apply to the std::numeric_limits<int>::min() case.

[Kmeakin]

This trick can also be used for sge and sle comparisons:

auto src1(int x) { return x >= std::numeric_limits<int>::max() - 2; }
auto tgt1(int x) { return add_with_overflow(x, 3); }

auto src2(int x) { return x <= std::numeric_limits<int>::min() + 2; }
auto tgt2(int x) { return add_with_overflow(x, -3); }

[Explorer09]

Thanks to this report, I also reported it to GCC (with a clearer example code).
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=122004

Quote the full report:

When x is a signed integer, and the conditional is (x > INT_MAX - c) (c is a compile time constant and 0 < c <= 0x7F), it's possible to check whether (x + c) will overflow. This can save code size by using a one-byte immediate operand instead of four-byte operand.

The conditional (x < INT_MIN + c) (1 < c <= 0x7F) can optimize in a similar way, by checking whether (x - c) will overflow. (If c == 1, the (x == INT_MIN) case can use even smaller code by using the NEG instruction - see the example code below.)

Although I file this optimization request for x86, I'm sure such optimization is possible also for ARM and AArch64 targets (where there are CMP (immediate) instructions).

#include <stdbool.h>
#include <stdint.h>

bool func1a(int32_t x) {
    return x > 0x7FFFFFFF - 0x7F;
}
bool func1b(int32_t x) {
    int32_t res;
    return __builtin_sub_overflow(x, -0x7F, &res);
}

bool func2a(int32_t x) {
    return x < (-0x7FFFFFFF - 1) + 0x7F;
}
bool func2b(int32_t x) {
    int32_t res;
    return __builtin_sub_overflow(x, 0x7F, &res);
}

bool func3a(int32_t x) {
    return x < (-0x7FFFFFFF - 1) + 1;
}
bool func3b(int32_t x) {
    int32_t res;
    return __builtin_sub_overflow(x, 1, &res);
}
bool func3c(int32_t x) {
    int32_t res;
    return __builtin_sub_overflow(0, x, &res);
}

func1a:
    cmpl $2147483520, %edi
    setg %al
    ret
func1b:
    addl $127, %edi
    seto %al
    ret
func2a:
    cmpl $-2147483521, %edi
    setl %al
    ret
func2b:
    addl $-127, %edi
    seto %al
    ret
func3a:
    cmpl $-2147483648, %edi
    sete %al
    ret
func3b:
    addl $-1, %edi
    seto %al
    ret
func3c:
    negl %edi
    seto %al
    ret