Proposal: Make integer overflow a logic error

Mojo Language Design
1

In debug mode overflow would trap/unwind.

In release mode: The default would be wrapping, but overflow checks could be enabled with the flag -f overflow-checks.

This would be similar to Rust’s model.

See Profiles - The Cargo Book.

Reasoning: Although wrapped arithmetic is the fastest and simplest for a systems language, I find it difficult to reason about. It can also introduce subtle bugs.

Additionally, some clever programmers may attempt to use overflow semantics to optimize code, such as with ranged comparisons.

Adding overflow checks would be an incompatible change; this is the trap Go fell into.

2

I want to challenge the notion of overflow being a logical error. For example a hash function expects an operation to overflow. Hence disabling the behaviour with a flag is IMHO quite dangerous.

Also crashing an application as a result of an overflow is quite a tough decision, making __add__raise is IMHO better, but then we still need an unsafe addition for systems programming cases like hash computation.

Swift actually defaults to safe arithmetic operators and provides `&` prefixed operators for overflowing operations e.g. &+ (see Documentation ) I am not a big fan of this solution but I can live with that.

1 Like
3

Is there a way to provide enough customization here (without fragmenting the ecosystem) so that everyone’s happy?

4

I agree with you that we need ways to opt into wrapping behavior, but I think that in most cases wrapping is not the desired behavior and is likely to result in problems. I spoke a bit in the other Int thread about having a SIMD type parameterized on the overflow behavior, and make the main SIMD alias can be controlled by a compiler switch.

5

My concern with just a compiler flag is that a library in Mojo is non elaborated MLIR representation. Hence, if I understand it correctly, when I compile my application which contains libraries, the library code will be compiled as well. So if I say I want to compile in a safe mode, I also compile external libraries in safe mode, which might break expectations of the library creator. This is why I think having explicit rules for safe vs. overflow in arithmetic is very important.

3 Likes
6

I am short on time right now, but I can discuss this topic later.

The logic for saturation is not complex. 1cycle + #ALU thoughput should be possible.
ARM and x86 already provide partial support for saturating arithmetic through the QADD and PADDS/VPADDS instructions. Note that x86’s support is limited to 8/16-bit, and neither provides support for general-purpose registers (GRPs) only vector registers.

My preference: Until the hardware manufacturers take saturation seriously, we need one language that does saturation by default.

from sys.intrinsics import llvm_intrinsic, _RegisterPackType
from os import abort

@fieldwise_init
@register_passable("trivial")
struct OverflowError(ImplicitlyCopyable):
    var overflow_bits: Int

# --- Solution 1: Wrapper Types --- 

@fieldwise_init
@register_passable("trivial")
struct RaisingInt(ImplicitlyCopyable):
    var int: Int
    fn __add__(self, other: Self) raises OverflowError -> Self:
        res = llvm_intrinsic[
            "llvm.sadd.with.overflow",
            _RegisterPackType[Int, Bool],
            Int,
            Int,
        
        ](self.int, other.int)
        overflowed = res[1]
        res_bits = res[0]
        if overflowed:
            raise OverflowError(res_bits)
        return RaisingInt(res_bits)

@fieldwise_init
@register_passable("trivial")
struct SaturatingInt(ImplicitlyCopyable):
    var int: Int
    fn __add__(self, other: Self) -> Self:
        res = llvm_intrinsic[
            "llvm.sadd.sat",
            Int,
            Int,
            Int,
        
        ](self.int, other.int)
        return SaturatingInt(res)

@fieldwise_init
@register_passable("trivial")
struct TrappingInt(ImplicitlyCopyable):
    var int: Int
    fn __add__(self, other: Self) -> Self:
        try:
            return TrappingInt((RaisingInt(self.int) + RaisingInt(other.int)).int)
        except _overflowed:
            abort()


# --- Solution 2: Extended Arithmethic operations on Int --- 


struct ExtendedInt: 
    var int: Int
    fn sat_add(self, other: Self) -> Self: ...
    fn raise_add(self, other: Self) raises OverflowError -> Self: ...
    fn trap_add(self, other: Self) -> Self: ...



# --- Tests --- 

@export
fn test_raise_add(a: RaisingInt, b: RaisingInt) raises OverflowError -> RaisingInt:
    return a + b
@export
fn test_sat_add(a: SaturatingInt, b: SaturatingInt) -> SaturatingInt:
    return a + b
@export
fn test_trap_add(a: TrappingInt, b: TrappingInt) -> TrappingInt:
    return a + b



0000000000002060 <test_trap_add>:
    2060: 48 01 f7                     	add	rdi, rsi
    2063: 70 04                        	jo	0x2069 <test_trap_add+0x9>
    2065: 48 89 f8                     	mov	rax, rdi
    2068: c3                           	ret
    2069: 50                           	push	rax
    206a: e8 31 00 00 00               	call	0x20a0 <stdlib::os::os::abort()>

0000000000002070 <test_raise_add>:
    2070: 48 89 f8                     	mov	rax, rdi
    2073: 48 01 f0                     	add	rax, rsi
    2076: 0f 91 c2                     	setno	dl
    2079: c3                           	ret

0000000000002080 <test_sat_add>:
    2080: 48 8d 0c 37                  	lea	rcx, [rdi + rsi]
    2084: 48 c1 f9 3f                  	sar	rcx, 0x3f
    2088: 48 b8 00 00 00 00 00 00 00 80	movabs	rax, -0x8000000000000000
    2092: 48 31 c8                     	xor	rax, rcx
    2095: 48 01 f7                     	add	rdi, rsi
    2098: 48 0f 41 c7                  	cmovno	rax, rdi
    209c: c3                           	ret

00000000000020a0 <stdlib::os::os::abort()>:
    20a0: 0f 0b                        	ud2
7

This requirement of some code to always run under a particular model, such as wrapping or saturating, is why we can have WrappingSIMD/SaturatingSIMD/etc. Cryptographic code will almost always use wrapping in all cases since having data dependent branches in cryptographic code is not acceptable, and that’s fine. In my opinion, if you require a particular type of arithmetic to be correct then that should be explicitly specified. Also, in the case of code where overflow is intentional checking for it isn’t really helpful so I don’t see a reason for that code to be subject to the global switch.

8

In my opinion, it would be much clearer to add a “wadd” or “wrap_add” function for the few niche cases that use wrapping semantics or require a random bit layout.

I consider a new operator to be too costly for such a niche use case when a simple function would suffice.

fn future_add(a: Int, b: Int) -> Int:
    """
    The only difference for now is the docstring.

    The bit layout is not currently defined and may change in the future, e.g., if saturating becomes as efficient as wrapping due to hardware instructions.

    If all architectures support it, the layout would be defined as saturating, and the debug check would be removed.
    """
    if env_get_bool["__overflow_checks"]():
        abort()
    return a + b

fn wrap_add(a: Int, b: Int) -> Int:
    """ 
    The only difference for now is the docstring.

    The bit layout is defined as wrapping.
    """
    return a + b

I don’t see the benefit of constraining the language by defining the bit layout for overflowing addition.

ARM managed to add min/max in probably 1cycle plus + full ALU: Arm CSSC quick reference. I don’t see why this should not be possible for saturating arithmetic.

Before “add”, “sub”, and “mul” are stabilized, it should be specified that the overflowing bit layout is unspecified, and debug checks should be added.

9

I’d much prefer to have named extensions, so we could have a.wrapping.add(b), and similarly for saturation arithmetic, etc.

Related, we could organise unsafe methods this way as well, instead of prefixing them with unsafe_.

10

@property, there you are, my little friend!
a.wrap + b.wrap * c.wrap + 2
Nice operator precedence and even nicer-looking assignments:
a.wrap += 1_000_000

By the way, this is just a convenience for my first solution: the arithmetic wrappers.

11

Arithmetic property wrapper interface:
.to_wrap, .wrap, .to_sat, .sat, .to_raise, .raise, .to_trap, .trap

The signature for * is fn(Self, Self | IntLiteral) -> Int.
The signature for to_* is fn(Self, Self | IntLiteral) -> Self.

Applying to add, sub, and mul.

Objections?

12

My preference would be to generate saturating bit patterns in release for all types other than Int and Int64. This is because they are more likely to overflow, which justifies the extra min/max instructions they generate. You should really only use these types if you know what you’re doing.

13

In practice, this would look something like this: -f overflow-bit-layout='saturating:UInt-8:UInt64,UInt64,Int8-Int32&wrapping:Int,Int64'.

14

I’m with Maxim, I don’t view this as a logical error. Incuring additional costs

tail += 1

Or having to pollute basic operations e.g.

tail.wrap += 1

I would much prefer a function in the rare cases I want protected behaviour:

saturating_add(tail, 1)
trapping_add(tail, 1)

Rust’s stance of always-check-at-debug is too defensive and leads to very bad ergonomics in math heavy code. I’d also argue it has a terrible impact on readability as

a + b / c

VS

a.wrapping_add(b.wrapping_div(c))

All that just to opt out of expensive checks I didn’t need here? Leaving it up to the programmer to opt into defensive behaviours strikes me as the best solution here, it’s not complex and it’s explicit in places where it needs to be. Although semantically wrapping is probably not what you want, likely all options are equally bad in those places if you, as the programmer, don’t account for them anyway. Handing out incrementing tickets in a queue, wrapping is actually ideal. Doing arithmetic and multiplying by a large number? Probably don’t want wrapping, but saturating is also wrong, do you trap? These decisions are too complex to pin down a singular ‘best option’ and in my mind, putting performance first gives you the best ergonomics, the least unexpected behaviour, and the most freedom as the programmer.