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
andisub_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
andiadd_carry
additionally into signed/unsigned portions:
isub_borrow
=>usub_borrow
andssub_borrow
iadd_carry
=>uadd_carry
andsadd_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.<!--
Please make sure you include the following information:
If this work has been discussed elsewhere, please include a link to that
conversation. If it was discussed in an issue, just mention "issue #...".Explain why this change is needed. If the details are in an issue already,
this can be brief.Our development process is documented in the Wasmtime book:
https://docs.wasmtime.dev/contributing-development-process.htmlPlease ensure all communication follows the code of conduct:
https://github.com/bytecodealliance/wasmtime/blob/main/CODE_OF_CONDUCT.md
-->
alexcrichton requested cfallin for a review on PR #9199.
alexcrichton requested wasmtime-compiler-reviewers for a review on PR #9199.
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 ofSaddOverflow
, 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.
cfallin created PR review comment:
s/signed/unsigned/ ?
cfallin created PR review comment:
Does this formula need to be updated now that we're computing a signed carry?
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 ofSaddOverflow
, 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.
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 implementa + 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 example0x7f + 0x01 + 0x00
always produces0x80
butuadd_carry
returns "no overflow" whilesadd_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.
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
-- likeuadd_overflow
, also takes a carry input.
alexcrichton updated PR #9199.
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.
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
andisub_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
andiadd_carry
additionally into signed/unsigned portions:
isub_borrow
=>usub_overflow_bin
andssub_overflow_bin
iadd_carry
=>uadd_overflow_cin
andsadd_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.<!--
Please make sure you include the following information:
If this work has been discussed elsewhere, please include a link to that
conversation. If it was discussed in an issue, just mention "issue #...".Explain why this change is needed. If the details are in an issue already,
this can be brief.Our development process is documented in the Wasmtime book:
https://docs.wasmtime.dev/contributing-development-process.htmlPlease ensure all communication follows the code of conduct:
https://github.com/bytecodealliance/wasmtime/blob/main/CODE_OF_CONDUCT.md
-->
alexcrichton updated PR #9199.
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.
cfallin created PR review comment:
s/and out/and overflow out/ (and three more times below)
alexcrichton updated PR #9199.
alexcrichton has enabled auto merge for PR #9199.
alexcrichton merged PR #9199.
Last updated: Dec 23 2024 at 13:07 UTC