Arithmetic with carry

[ghost]

(This is an expanded version of issue (WebAssembly/spec#446))

Multi-precision arithmetic requires special handling. This is available in some form in all ISAs, but not currently available in webasm.

There are basically three ways of doing this (it seems to me), none of which is especially palatable in the context of the current design:

Option 1. Add a special flags register, together with instructions that do arithmetic with that register.

This is the traditional approach in mainstream hardware.

You get instructions like

addc

which will add two numbers, and the value of the carry flag, and set the carry flag on the result.

This is not pleasant because it adds a special register.

Option 2.
Support a form of 60bit arithmetic with 4 bits for flags.

Option 3.
Support multi-word arithmetic: addition takes 3 arguments and produces 2 outputs.

This approach will do the least damage to the existing ISA and register architecture. However, this will be hard to map to existing hardware efficiently (not all hardware ISAs support loading the flags register directly.

However it is done, multi-precision arithmetic is quite important and very hard to emulate without some simple hardware support.

[lars-t-hansen]

Seems to me that for option 3 there are plausible optimizations that would make this practical. Suppose {i32,i64}.addc takes three inputs, op2 on the top, op1 below, carry at the bottom and produces two outputs, result on top and carry below it. For the sake of argument assume the carry is always the same type as the other operands. Define addc only to use the low bit of the carry and for the carry left after the operation to be zero or one. Things are now reasonably set up for a multi-word add, say. In a suitably unrolled loop a JIT/Wasm compiler really ought to be able to see that it is the carry that is being propagated, and generate good code. (And if the loop is not unrolled then loop overhead will dilute the carry extraction/insertion anyway.) I think worst-case branch-free code for carry extraction should be mov rd, 0; adc rd, 0; for insertion, something like and rc, 1; add rc, ~0 where rc is a register that contains a value to be treated as a carry.

On ARM, consuming a carry is separate from producing a carry: ADC consumes, ADC.S consumes and produces, ADD.S only produces. Would we want all these variants? And what about overflow?

(There might be a fourth option, where we add a operate-and-branch-on-condition operation which both produces a result and branches to a label or not, eg, i32.addc op1 op2 carry L would branch to L on carry set and fall through on carry clear, and either way leave a result on the stack, but it seems harder to use in general than the three options you suggested.)

[jfbastien]

Is there someone willing to champion this proposal? We'd need proposed semantics, binary encoding, and I'd like at least a least of usecases and an implementation with performance numbers for these usecases (compare current MVP WebAssembly, with this proposed addition, and native code).

[ghost]

In principle, I would be willing to champion this. However, personal changes mean that I have limited resources for at least the next few months. ——— Frank McCabe Senior Software Architect Phone: 650-740 6673 | Email: [email protected] <mailto:[email protected]> Instart Logic | 450 Lambert Ave, Palo Alto, CA 94306 | instartlogic.com <http://instartlogic.com/>

…

On May 11, 2017, at 10:14 AM, JF Bastien ***@***.***> wrote: Is there someone willing to champion this proposal? We'd need proposed semantics, binary encoding, and I'd like at least a least of usecases and an implementation with performance numbers for these usecases (compare current MVP WebAssembly, with this proposed addition, and native code). — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#1021 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ADfCzd9le4ufXm6DSsArpfXCYsGdV7UIks5r40H5gaJpZM4MrKma>.

[lars-t-hansen]

I'll likely have time to devote to this though not very much until June or so, and then into the fall. IMO this functionality is fairly important, and I think the overflow flag is as important as the carry flag though with different use cases (dynamic languages' fixnum -> bignum transition).

[lars-t-hansen]

Discussed this with some Mozilla folk today. In summary:

• We probably do want dedicated instructions here because emulating the behavior will be slowish and we don't generally want to do magic pattern-matching to recognize emulation and turn it into efficient machine code behind the scenes
• We care about carry/borrow and overflow, for sure; other flags TBD
• We care about add and subtract for sure; multiply, divide, rotate (rotate-through-carry is common but is it useful for Wasm?) TBD
• The common case is that we only care about one flag at a time and it's probably adequate to cover that case, not a general "capture flags A, B, and C" situation
• For carry, an instruction that always consumes a carry-in and always produces a carry-out is sufficient; variants that consume but do not produce or vice versa are not necessary, and not having them probably won't affect the output of a good compiler
• We want to motivate this work with data from existing good MP libraries (such as Gnu MP); this could be facts (library X does/does not have assembler subroutines or use intrinsics to make use of flags; it uses instructions A and B) or performance data (library Y can use assembler subroutines or emulate in C; perf difference is N%) or use cases (general bignum arithmetic, crypto, whatever else comes to mind)
• We may want to wait with proposing specific instructions until we start discussing multiple-value producing instructions in general, eg, multiple-value returns

[mpfau]

Has there been any progress on this issue? Carry and borrow are needed to implementing modern cryptograpy (e.g. SIDH) efficiently. Big number addition without ADDC is multiple factors slower than with. The same applies to subtraction and multiplication.

[lars-t-hansen]

I think we're at least waiting for multi-value to be finished so that we can easily express an operation with more than one result. Multi-value is "almost there".

[dmlloyd]

What if, instead of multi-value, there's a separate instruction that only yields the "carry" of an add operation? Surely the backend JIT or compiler (if any) could easily coalesce the instructions based on their identical inputs using the same logic that it would use to coalesce identical adds. And in the interpreter case, an extra add is not going to be significantly more expensive I would think.

Additionally (pun not intended) it is important to consider the case of signed-overflow as well, which could be modelled as a different instruction.

[dschuff]

A new proposal has been started that covers this: https://github.com/WebAssembly/128-bit-arithmetic
The use cases for arithmetic with carry are in-scope for the proposal (despite the limited-sounding name).