Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Proposal: Improve overflow operations #20203

Open
Snektron opened this issue Jun 5, 2024 · 8 comments
Open

Proposal: Improve overflow operations #20203

Snektron opened this issue Jun 5, 2024 · 8 comments
Labels
accepted This proposal is planned. breaking Implementing this issue could cause existing code to no longer compile or have different behavior. proposal This issue suggests modifications. If it also has the "accepted" label then it is planned.
Milestone

Comments

@Snektron
Copy link
Collaborator

Snektron commented Jun 5, 2024

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
@Vexu Vexu added the proposal This issue suggests modifications. If it also has the "accepted" label then it is planned. label Jun 5, 2024
@Vexu Vexu added this to the 0.14.0 milestone Jun 5, 2024
@andrewrk andrewrk added accepted This proposal is planned. breaking Implementing this issue could cause existing code to no longer compile or have different behavior. labels Jun 5, 2024
@Rexicon226
Copy link
Contributor

Rexicon226 commented Jun 5, 2024

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
Copy link
Member

mlugg commented Jun 5, 2024

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
Copy link
Contributor

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
Copy link
Contributor

rohlem commented Jun 6, 2024

@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
Copy link
Collaborator Author

Snektron commented Jun 6, 2024

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
Copy link
Collaborator Author

Snektron commented Jun 8, 2024

Note that if we accept ranged ints (#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
Copy link

mhcerri commented Jul 22, 2024

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

@rohlem
Copy link
Contributor

rohlem commented Jul 22, 2024

@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 #2647), so such a change would move away from this current proposal of including more information about the overflow.

@andrewrk andrewrk modified the milestones: 0.14.0, 0.15.0 Jan 25, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
accepted This proposal is planned. breaking Implementing this issue could cause existing code to no longer compile or have different behavior. proposal This issue suggests modifications. If it also has the "accepted" label then it is planned.
Projects
None yet
Development

No branches or pull requests

7 participants