wasmtime / PR #9199 Remove `iadd_cin` and `isub_bin`, spl... · git-wasmtime

Stream: git-wasmtime

Topic: wasmtime / PR #9199 Remove `iadd_cin` and `isub_bin`, spl...

Wasmtime GitHub notifications bot (Sep 05 2024 at 15:04):

alexcrichton opened PR #9199 from alexcrichton:refactor-carries-and-borrows to bytecodealliance:main:

This commit refactors the opcodes the Cranelift supports for add-with-carry and subtract-with-borrow. None of these opcodes are currently in use by the wasm frontend nor supported by any backend. In that sense it's unlikely they have many users and the hope is that refactoring won't cause much impact.

The iadd_cin and isub_bin opcodes are the equivalent of *_borrow and *_carry except that they don't return the carry flag, they only return the result of the operation. While theoretically useful I've elected to remove them here in favor of only the borrow-returning operations. They can be added back in in the future though if necessary.

I've split the preexisting operations isub_borrow and iadd_carry additionally into signed/unsigned portions:

isub_borrow => usub_borrow and ssub_borrow

iadd_carry => uadd_carry and sadd_carry

This reflects how the condition needs to differ on the carry flag computation for signed/unsigned inputs. I've additionally fixed the interpreter's implementation of IsubBorrow when switching to the signed/unsigned opcodes.

Finally the documentation for these instructions now explicitly say that the incoming carry/borrow is zero-or-nonzero even though it's typed as i8. Additionally the tests have been refactored to make use of multi-return which may not have existed when they were first written.

Wasmtime GitHub notifications bot (Sep 05 2024 at 15:04):

alexcrichton requested cfallin for a review on PR #9199.

Wasmtime GitHub notifications bot (Sep 05 2024 at 15:04):

alexcrichton requested wasmtime-compiler-reviewers for a review on PR #9199.

Wasmtime GitHub notifications bot (Sep 05 2024 at 16:46):

cfallin submitted PR review:

Thanks for the PR -- I do have some questions however!

The main thing I'm wondering about is the signed/unsigned split for add/subtract-with-carry-out. My concern is that the definitions don't actually correspond to how two's-complement arithmetic works in arbitrary-precision implementations normally. Specifically: a signed addition/subtraction over a sequence of digits/limbs must use unsigned (normal two's-complement) additions/subtractions for all components, except perhaps the last if you want an overflow flag.

To work it out with an example: say we have two 8-bit signed values 127 and 1; we add them, get 128 === -128 (mod 256), and we want to know we had an overflow; then the definition here makes sense. But if these are the low bytes of a multibyte number, we want a carry of 0, because [0 0 0 127] + [0 0 0 1] = [0 0 0 128] is a perfectly fine representation of positive-128. (And in cases where one might want to add a narrow-width negative number, sign extension will carry the sign bit left to produce a bunch of 0xff limbs if necessary; carry doesn't handle that case.)

To tie it to hardware/computer-arithmetic logic: "carry" is the carry-out of the MSB full-adder, while "overflow" (what you're calling "carry" for signed ops) is the XOR of the carry-in and carry-out of the MSB full-adder. (See Wikipedia for more.)

The change in the interpreter, where SaddCarry simply invokes the implementation of SaddOverflow, is another hint here that something is a bit amiss with our definitions IMHO.

So: I guess I want to understand better what these ops are for, and then want to make sure we name them appropriately according to standard flags nomenclature, so we don't mislead users doing multi-part additions.

Wasmtime GitHub notifications bot (Sep 05 2024 at 16:46):

cfallin created PR review comment:

s/signed/unsigned/ ?

Wasmtime GitHub notifications bot (Sep 05 2024 at 16:46):

cfallin created PR review comment:

Does this formula need to be updated now that we're computing a signed carry?

Wasmtime GitHub notifications bot (Sep 05 2024 at 16:51):

cfallin submitted PR review:

Thanks for the PR -- I do have some questions however!

The main thing I'm wondering about is the signed/unsigned split for add/subtract-with-carry-out. My concern is that the definitions don't actually correspond to how two's-complement arithmetic works in arbitrary-precision implementations normally. Specifically: a signed addition/subtraction over a sequence of digits/limbs must use unsigned (normal two's-complement) additions/subtractions for all components, except perhaps the last if you want an overflow flag.

To work it out with an example: say we have two 8-bit signed values 127 and 1; we add them, get 128 ≡ -128 (mod 256), and we want to know we had an overflow; then the definition here makes sense. But if these are the low bytes of a multibyte number, we want a carry of 0, because [0 0 0 127] + [0 0 0 1] = [0 0 0 128] is a perfectly fine representation of positive-128. (And in cases where one might want to add a narrow-width negative number, sign extension will carry the sign bit left to produce a bunch of 0xff limbs if necessary; carry doesn't handle that case.)

To tie it to hardware/computer-arithmetic logic: "carry" is the carry-out of the MSB full-adder, while "overflow" (what you're calling "carry" for signed ops) is the XOR of the carry-in and carry-out of the MSB full-adder. (See Wikipedia for more.)

The change in the interpreter, where SaddCarry simply invokes the implementation of SaddOverflow, is another hint here that something is a bit amiss with our definitions IMHO.

So: I guess I want to understand better what these ops are for, and then want to make sure we name them appropriately according to standard flags nomenclature, so we don't mislead users doing multi-part additions.

Wasmtime GitHub notifications bot (Sep 05 2024 at 18:00):

alexcrichton commented on PR #9199:

As for the precise motivations, I'm not actually sure myself. I was mostly copying LLVM how it's got {S,U}{SUB,ADD}O_CARRY opcodes and I assumed there was a reason why.

As for the actual semantics I can perhaps clarify that the addition/subtraction here is still 2's complement and is implemented the exact same way whether it's signed or unsigned. For example *add_carry both implement a + b + (c != 0) for the first result. The difference of signed/unsigned is the second result (whether or not the computation overflowed) and the computation for that is different whether if it's signed or unsigned. For example 0x7f + 0x01 + 0x00 always produces 0x80 but uadd_carry returns "no overflow" while sadd_carry returns "yes overflow".

I'm not actually sure what signed overflow is used for in practice. I just added it because it felt symmetrical. I also wasn't sure of the condition of overflow for iadd_cin from before because it wasn't clear from the docs whether it was signed or unsigned overflow that was tested for the output.

Wasmtime GitHub notifications bot (Sep 05 2024 at 19:50):

cfallin commented on PR #9199:

Ah, so there's a subtle (one letter!) difference with the LLVM opcodes: UADDO_CARRY, i.e., "add with overflow"; and the "carry" indicates a carry input.

If we keep these opcodes I'd prefer to call them something like (for example) uadd_overflow_cin -- like uadd_overflow, also takes a carry input.

Wasmtime GitHub notifications bot (Sep 05 2024 at 20:11):

alexcrichton updated PR #9199.

Wasmtime GitHub notifications bot (Sep 05 2024 at 20:12):

alexcrichton commented on PR #9199:

Oh for sure happy to rename!

I should also probably elaborate that the reason for me personally doing this is that this is part of the investigation I'm doing for https://github.com/WebAssembly/128-bit-arithmetic. The size of the patches I was carrying locally was getting a bit large so I wanted to upstream some of the smaller bits. In a branch I've got lowerings of these opcodes for aarch64 and x64, but they're very inefficient lowerings. I'm not certain I'll upstream the lowerings because I'm not sure it's worth it, but I figured that in the meantime it might be worth at least straightening out the CLIF side of things.

Wasmtime GitHub notifications bot (Sep 05 2024 at 20:13):

alexcrichton edited PR #9199:

This commit refactors the opcodes the Cranelift supports for add-with-carry and subtract-with-borrow. None of these opcodes are currently in use by the wasm frontend nor supported by any backend. In that sense it's unlikely they have many users and the hope is that refactoring won't cause much impact.

The iadd_cin and isub_bin opcodes are the equivalent of *_borrow and *_carry except that they don't return the carry flag, they only return the result of the operation. While theoretically useful I've elected to remove them here in favor of only the borrow-returning operations. They can be added back in in the future though if necessary.

I've split the preexisting operations isub_borrow and iadd_carry additionally into signed/unsigned portions:

isub_borrow => usub_overflow_bin and ssub_overflow_bin

iadd_carry => uadd_overflow_cin and sadd_overflow_cin

This reflects how the condition needs to differ on the carry flag computation for signed/unsigned inputs. I've additionally fixed the interpreter's implementation of IsubBorrow when switching to the signed/unsigned opcodes.

Finally the documentation for these instructions now explicitly say that the incoming carry/borrow is zero-or-nonzero even though it's typed as i8. Additionally the tests have been refactored to make use of multi-return which may not have existed when they were first written.

Wasmtime GitHub notifications bot (Sep 06 2024 at 17:46):

alexcrichton updated PR #9199.

Wasmtime GitHub notifications bot (Sep 06 2024 at 18:20):

cfallin submitted PR review:

Cool, given the new names I'm happy otherwise -- thanks for the patience! One tweak to the description below then LGTM.

Wasmtime GitHub notifications bot (Sep 06 2024 at 18:20):

cfallin created PR review comment:

s/and out/and overflow out/ (and three more times below)

Wasmtime GitHub notifications bot (Sep 06 2024 at 19:15):

alexcrichton updated PR #9199.

Wasmtime GitHub notifications bot (Sep 06 2024 at 19:15):

alexcrichton has enabled auto merge for PR #9199.

Wasmtime GitHub notifications bot (Sep 06 2024 at 19:44):

alexcrichton merged PR #9199.

Last updated: Oct 23 2024 at 20:03 UTC