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.

15

Hash functions don’t really operate on our everyday notion of integers. They operate on an opaque lump of bits (basically encrypted data). I think the right way to offer wrapping is to have a data type for opaque binary data, e.g. Bin64 or Bit64 where wrapping is the legitimate behaviour.

Then, for the integer types that are actually supposed to store everyday quantities (IntX etc), overflow should be considered erroneous behaviour, because in practice it will almost always be an error for an “everyday quantitiy” to wrap, and in debug mode it would be very helpful to detect these errors.

16

For me the main concern is predictable behavior. If I use a + in my hash function implementation and expect it to overflow as this is what a + operator does on the hardware (without sprinkled checks around it), I don’t want some one who uses my code to flip a compiler flag and unknowingly shot them selves in the foot.

for the integer types that are actually supposed to store everyday quantities (IntX etc), overflow should be considered erroneous behaviour, because in practice it will almost always be an error for an “everyday quantitiy” to wrap

When we are speaking everyday quantities, then going the Python route and have number promoted to a BigInt/BigDecimal value on arithmetic operation is the safe and most correct way to go.

Raising on the other hand means that we expect a programmer to be defensive and write their math operations in a recoverable block. Crashing on overflow is even worse as in this case we force double checking every value. The user should check the value for potential overflow if they don’t want to crash and burn their application, and the method itself is also checking for overflow in order to crash the application.

Crashing in debug mode is IMHO just security theater. The main problem is an unexpected high input value and the odds of developers hitting those values during development/debugging phase are … the fifty fifty scene from the war dogs movie comes to mind.

So from my perspective there are following options:

  1. The SIMD type and all its specializations should reflect the hardware (platform) you are running on, if the addition overflows on your platform, it should reflect that and do not sprinkle comparison and jump operations.

  2. We expect people to not understand that numeric operations can overflow, so the default math operation methods are all raising, which is a hint for a careful developer, to be defensive with math operations. In parallel we need to provide additional set of math operation methods, which will do the efficient thing and reflect the platform we are computing on

  3. We keep SIMD as in option 1. (as SIMD is actually a vector and a reflection of CPU registers) and we introduce explicit int scalar type which is up casted to 512 bit, or arbitrary precision if you will. No overflow possible, math operations are always correct at the expense of this type being complex and very slow on some platforms, but I think most of the developers who are not performance engineers will love it. Also there is no need for an unsigned version, one type to rule them all (or at least to represent the set of all integers ℤ).

PS: the floating point (real ℝ) numbers are even a more extreme example of people not understanding how simple arithmetics can give you a “wrong“, or unexpectedly approximated result. So one could also plead making math operations on floats raising in cases where the result is not exact. And generally all the options I described for integers would apply.

17

If I use a + in my hash function implementation and expect it to overflow as this is what a + operator does on the hardware

This is why my suggestion was to have a WrappingSIMD type that always wraps no matter what which is a free bitcast from the normal SIMD type. There’s a non-zero chance of some ML hardware out there doing int32 via fp64 denormals and having saturating semantics by default (I’ve actually seen this pitched as an idea for some HPC-focused hardware). In my opinion, unless you specify that you want a particular behavior, readers are likely to assume that you do not expect overflow.

Crashing in debug mode is IMHO just security theater.

I don’t propose it for security, but instead as a debugging aid. The debugger can intercept traps to help track down where overflows occur, instead of the first place they are checked. Once you move to production, that global switch can be used to specify what behavior is best for your application. Wrapping may be okay if you have a high confidence in the correctness of your code, but some applications may decide that the performance hit of checking every operation and crashing if it overflows is worth the correctness hit. Saturating math is a lower performance hit and still helps “save” an application in some situations.

Of those options you propose, I think that platform dependent behavior is a bad idea. It leads to portability issues. Raising math seems like a spectacularly bad UX decision to me, which is why I want to do trap=abort for checked math. We can have special raising versions of the checks that are explicitly called. I don’t think that using very big numbers will help, they hurt default performance by a lot and would inevitably bleed into fast-path operations if used by libraries. Doing that seems like a “bit-pack std::vector<bool>” level mistake to me.

I think that what the “error” handling behavior should be needs to be in control of the user. For some programs, they are carefully reviewed for correctness and are unlikely to ever overflow, so speed matters more. For some, crashing is unacceptable because it could kill people. For others, not crashing if in an invalid state is unacceptable because there is no safe way to continue to manipulate the data. I don’t see this as a decision we as language designers can make for users without deciding that some set of users shouldn’t use Mojo.

18

Andrew Kelley would be jealous if he had Python-style raises. Eliminating overflow is the most correct approach. Since we expect great software to be written in Mojo, we should consider correctness an achievement, not a hassle. If we raised by default, I could see an argument for introducing Swift-style wrapping operators.

19

I could agree with trapping by default for a “release-safe” preset, but raising by default would make the problems some people already have to my idea of making allocation able to fail 1000x worse because everything does math. For most code, I think that overflow is likely the result of a logic error, and is something that can only be handled by fixing the code and recompiling. Instead of raising by default, I would vote for using dependent types to push as many range checks as possible into the compiler and only raise on operations which can actually overflow.

20

Keeping the advancements in symbolic execution, targeted and whitebox fuzzing, path exploration etc in mind, I’m pretty sure one could make practical debugging tools to test these scenarios that don’t take too long to hit the edge cases (especially if we could reduce the problem to e.g. testing just a single function).