Proposal: Improve overflow operations

[Snektron]

Context

The current overflow operations (@addWithOverflow, @subWithOverflow, @mulWithOverflow, @shlWithOverflow) do currently not spark joy in my opinion: These seem initially just designed from the corresponding LLVM instruction, however, they have some problems in reality:

• @subWithOverflow returns a bool whether overflow happened, while in my opinion a carry would be more useful. This would work cleanly with returning an i1 instead of a u1: A carry returns -1 and no carry returns 0. In this case carries can be naively added to the next word instead of with an awkward cast.
• Why is the "overflow" bit a u1 instead of a bool if its intended as flag? If its meant to be overflow, then why are the other overflow parts not as described above?
• @mulWithOverflow returning a u1 is even less useful. In many situations, the CPU already gives you the high words. This also ties into wide multiplication: Currently, the primary way to do that is to cast to a larger word size, but the CPU already has a native T * T -> {T, T} instruction in many cases. Trying to detect an upcast from the backend is difficult from a compiler backend perspective, and emitting a full 2T multiplication operation is often much less efficient.
• @shlWithOverflow would be much more useful if it also returns the overflow bits in my opinion. I don't think it would be much more expensive in code either.

Proposal

My proposal is to change the overflow builtins to return the full overflow value too. The interface would largely remain the same, only the return types need to be modified:

• @addWithOverflow remains the same
• @subWithOverflow(a, b) would return struct{@TypeOf(a, b), i1}.
• @mulWithOverflow(a, b) would return struct{@TypeOf(a, b), @TypeOf(a, b)}.
  • Unresolved: Which types should be used for signed multiply overflow? I think the sanes posibilities are to return either to return a pair of signed numbers, or make the low-order bits unsigned. I'm not sure.
• @shlWithOverflow(a, b) would return struct(@TypeOf(a, b), @TypeOf(a, b)}.
  • Unresolved: Similar to the above

[Rexicon226]

I think that @shlWithOverflow should return struct{ @TypeOf(a), std.meta.Int(.unsigned, b) } instead.

In an example such as @shlWithOverflow(@as(u64, x), 32), the maximum amount the overflow could be is u32. This would remove a potential cast that needs to be done.

[mlugg]

Note that if we accept ranged ints (#3806), then @{add,sub,mul}WithOverflow become kind of redundant, and even more so under this proposal. So, if that's accepted, perhaps those builtins should be eliminated entirely, and implemented in userspace? e.g.

fn addWithOverflow(comptime T: type, a: T, b: T) struct { u1, T } {
    const result = a + b;
    const overflow = result < minInt(T) or result > maxInt(T);
    return .{ overflow, @truncate(result) };
}

[Rexicon226]

I think that @shlWithOverflow should return struct{ @TypeOf(a), std.meta.Int(.unsigned, b) } instead.

In an example such as @shlWithOverflow(@as(u64, x), 32), the maximum amount the overflow could be is u32. This would remove a potential cast that needs to be done.

My brain woke up. b is not required to be comptime known, so this doesn't make sense. Proposal makes sense as is.

[rohlem]

@subWithOverflow [...] would work cleanly with returning an i1 instead of a u1: A carry returns -1 and no carry returns 0. In this case carries can be naively added to the next word [...] .

I was initially quite confused by this: I assume this was formulated only for unsigned numbers, right? Because f.e. @as(i2, -2) - @as(i2, 1) does overflow negatively, while @as(i2, 1) - @as(i2, -2) instead overflows positively. So for signed numbers an i1 doesn't seem more clear to me. To allow "naively adding" the result we would have to allow overflow of -1, 0, and 1, extending the result type to i2. (Which I think would be undesired because it's more work?) But maybe signed operations simply aren't as frequently used here, or I'm missing some other bit-fiddling insight that makes this a moot point.

EDIT: Actually, for the use case of "adding it to the next word", i.e. when implementing a big integer out of several segments/limbs, the sign information (I assume) won't be stored at each segment individually anyway. The more I think about it, the more I'd probably implement a - b as a + (-b), and individually add limbs as unsigned numbers, in which case the signed variants don't even apply. For other use cases of signed number subtraction, knowing the sign of the overflow might still be helpful I assume, though I'm not sure.

[Snektron]

I was initially quite confused by this: I assume this was formulated only for unsigned numbers, right? Because f.e. @as(i2, -2) - @as(i2, 1) does overflow negatively, while @as(i2, 1) - @as(i2, -2) instead overflows positively.

Yep, youre right, I didnt think about that. I think it would still make sense to return the complete carry, and both addWithOverflow and subWithOverflow would return {T, i2}.

[Snektron]

Note that if we accept ranged ints (https://github.com/ziglang/zig/issues/3806), then @{add,sub,mul}WithOverflow become kind of redundant, and even more so under this proposal.

It seems to me that if we want those operations, then it would still be useful to have a wide_mul AIR instruction rather than upcast-and-mul, so internally the proposed changes would still be useful imo.

[mhcerri]

Sorry for the naive question, but is there any reason for those overflow operations to not return an error union?

[rohlem]

@mhcerri Error unions use error values, which under-the-hood are a program-wide enum (to allow easier coercion from any smaller error set to the global error set anyerror). So every time you do an overflow operation, the compiler would have to insert a lookup of the error value. To gain back speed, the optimizer would then have to elide that lookup again. Also, error unions currently don't have a payload in the error case (proposed and rejected in https://github.com/ziglang/zig/issues/2647), so such a change would move away from this current proposal of including more information about the overflow.

[WeeBull]

I've just been trying to use the @addWithOverflow built-in on 0.15.1 in order to implement large integers >64kbit. One problem I've hit is that although the operations have a "carry-out" in the form of the overflow, they do not have a "carry-in". That means you end up with twice as many addWithOverflows as you need an extra one for the carry which can also overflow.

...or have I missed an idiomatic way of doing what I described?