Why not return quotient and remainder in one instruction?

[KloudKoder]

Perhaps this due to instruction formatting constraints, but it seems silly not to provide both when computing one implies computing the other. I guess you could leave it to compiler optimization, but that seems painful. Intel's DIV and IDIV do this natively, although of course they only do it if the quotient fits in half the space available to the dividend.

Alternatively, I suppose you could provide performance guidance along the lines of: "please make sure there are no branch instructions or branch targets between the divide and remainder instructions (and have the divide first, maybe) so that the compiler can optimize them into a unified instruction under the hood".

[tlively]

The ability to return multivalue values from one instruction is a fairly recent development in WebAssembly, so it simply wasn't an option when the MVP arithmetic was designed. This would be fair game for a new proposal, though. It might be good to bundle it with other newly-possible instruction like add-with-carry, etc.

[KloudKoder]

@tlively I'm pleased to hear that. I don't know why most languages don't seem to provide this. And I think add-with-carry is another must as well, now that you mention it.

[wbl]

And I want a multiplication that provides the high and low as well, for many of the same applications.

[KloudKoder]

@wbl I second that. The high should be the true high including complete carry propagation, as opposed to an approximation.

[wbl]

There are several issues that make me want to keep it simple. One is CPU support. A doubling width multiply is very common, while variants that can add in a register into the product and carry out the result are much rarer: UMAL is the only one I can think of. Secondly the cost of properly propagating is two add with caries, because adding into a product doesn't carry out, so it's not that bad to have three instructions in a row, which is what you'd do in assembler anyway.

The bigger problem is the add with carry instruction: not all CPUs have a carry flag, and its frequently clobbered in uncomfortable ways. I've got to think hard about this one: ideally a compiler can do a good job without too much work, while making the usual usage simple and efficent.

[KloudKoder]

@wbl Addition with carry (and subtract with borrow) could be implemented efficiently on nonIntel CPUs by introducing a virtual carry bit and a set of add and subtract instructions which set it according to the result, so that it can be propagated along. On Intel, this register comes directly from the carry flag. On other architectures, it would need to come from nonbranching predicates which implement set-on-wrap (slightly different logic for add and subtract, but you get the idea). Also, saving way the carry flag on Intel is easy: SETC AL. (Please don't PUSHF.)

For the sake of architectural elegance, I guess it would make sense to have a whole bunch of bit registers, any one of which might be used for the carry input or output in any given instruction, so you could have "Add X to Y to C0 and produce sum Z with carry C1".

[KloudKoder]

I think this still matters.

I would also like to point out one corner case to consider, which already has relevance with existing remainder computation in WASM: having zero as the dividend. (When the divisor is zero, the result is undefined. This makes sense (as long as the actual behavior is secure) because we shouldn't be wasting overhead checking for this. But I'm talking about the numerator.)

Some languages say that:

0 mod 5 = 5

while others say that:

0 mod 5 = 0

Both are true; it depends on exactly what you mean by "mod(ulo)". If you mean "the remainder when 0 is divided by 5", then it's the former. If you mean "0 expressed in base 5", then it's the latter.

I just bring this up because the spec indicates the former, but it's not clear to me that all supported silicon behaves identically in this regard.

Probably it's all fine, but someone might want to check.

[KloudKoder]

I have proposed a discussion of this issue at the May 11, 2021 community group meeting:

WebAssembly/meetings@master...KloudKoder:patch-2

Probably we should have:

1. Divide to produce quotient and remainder (perhaps with the limitation that neither may exceed half the dividend's width, as with classic X86). Consider carefully what happens when 0 is either dividend or divisor. Signed and unsigned results will differ, so we need separate instructions.
2. Multiply 2 factors to obtain a product at double the width, including proper carry propagation. Signed or unsigned.
3. Add-with-carry. (This always struck me as a silly name for an instruction. Of course you want to use a carry when you add! What it refers to is the addition of the carry bit as well. The carry bit would need to be provided in a register if in fact there is no carry flag on a given architecture, in which case it's "add 2 integers along with bit 0 of some other register".)
4. Subtract-with-borrow. Same as Essentialpostv1 future #3 but backwards.
5. Double-precision shift, allowing 2 integers to behave as one of double the size. By constant or variable distance.
6. Double-precision rotate by constant or variable distance. (Not critical but nice to have.)

[penzn]

I don't think you have proposed this yet (the link is a fork comparison, rather than PR). Also, what would those 6 instructions be for?

[KloudKoder]

@penzn Thanks for pointing that out. PR submitted.

"Also, what would those 6 instructions be for?"

• Divide and multiply from int(X) to or from int(2X) are used all the time in large integer libraries. They also come up all the time in practical programming, for example if you have an array where the length and width are both 32-bit, but the area might need 64-bits. For example, "allocate X objects of size Y" requires determining whether X*Y overflows the address width.

• Add-with-carry and subtract-with-borrow are important in large integer libraries as well. Even just dealing with 128-bit integers is a major problem in their absence. (I'm surprised that WASM has neither integer nor float support for them, but that's another discussion.)

• Double-precision shifts are important for data (de)compression performance. Because it's often rather serialized, (de)compression tends to constitute a major source of overhead and is thus worthy of optimization.

• Double-precision rotation is debatable. My intuition tells me that it's useful in gaming and crypto, but I admit that I don't have a compelling example.

There are native accelerating instructions for all of the above, other than the last one, in X86 and AMD64. Not sure about other architectures.

[lars-t-hansen]

Previous discussion: #1021

[KloudKoder]

Here's my design for today's CG meeting. No doubt it will be debated and revised.

ADD-WITH-CARRY (ADC) & SUBTRACT-WITH-BORROW (SBB):

Having read thread from @lars-t-hansen (thanks), and based on my experience writing written multiprecision functions, I note the following constraints:

1. We don't want to have multivalue inputs / outputs in use unless absolutely necessary. While I generally have no problem with them, in this case, they might be problematic because we don't want to burn an entire 64-bit register on a stupid carry flag -- at least not for transient carry propagation in, say, 128-bit addition.

2. We don't want to touch the actual flags register on any ISA, if we can avoid it. In other words, we don't want to define it as "the" virtual carry flag, and leave it there forever. It's far too fluid to dedicate for that purpose.

3. While it would be nice to have alternative flavors which only consume, or only produce, carries, they're not worth paying any complexity for. (The existing addition and subtraction instructions neither produce nor consume.)

4. There is a tradeoff here: On the one hand, we don't want to burn a whole register and create movement overhead between the flags register and the virtual carry register in order to just propagate a carry from some low part to its corresponding high part. On the other, we absolutely need a place to dump the carry in case it needs to be used sometime far later. What to do?

I would suggest:

1. You need to use produce-and-consume adds and subtracts if you want to do anything with the carry at all. In deference to efficiency, I'm actually in favor of supporting consume-only and produce-only, but it's not a big deal for me.

2. There is a virtual carry register. It starts as zero and is only altered by carry-aware instructions. At that point, it survives only until the next branch (including returns). The first carry-aware instruction following a jump or return target is defined to consume the carry as zero. This allows us to be lazy up front (just clear the carry prior to every branch, but only in the currently nonexistent situation that a given binary contains any carry-awareness at all) but efficient in the future (be aware of branch targets and only clear the carry when necessary). It's convenient, at least on X86, that logic instructions automatically clear the carry for us.

3. If the carry needs to survive long term, then we need to use CarryToInteger and CarryFromInteger. The former sets bit zero of an i32/i64 variable to the value of the carry flag. The second does the opposite. It's overkill to destroy the rest of the register contents, which the programmer might not want to do. But this is debatable because SETC AL, to cite an X86 example, would be a faster way to do this than manipulation of bit zero.

4. Parity, sign, and zero flags could be copied to or from the carry flag or an integer register via dedicated instructions. Parity is expensive and would benefit from optimization, but the other 2 are probably not worth the trouble. That said, I'm not sure where parity is really a bottleneck these days.

DOUBLE-PRECISION SHIFT LEFT (DSL) & DOUBLE-PRECISION SHIFT RIGHT (DSR):

This "just works" if we use multivalue instructions. Let's do it that way. We shouldn't support shift-through-carry because it's not enough bang for the buck.

DOUBLE-PRECISION ROTATE LEFT (DRL & DOUBLE-PRECISION ROTATE RIGHT (DRR):

My intuition tells me this should exist, and it's minimal trouble if we implement DSL and DSR. The only caveat is that we need one additional scratch register.

DIVIDE-TO-SMALLER (D2S) & MULTIPLY-TO-BIGGER (M2B):

1. D2S64 divides an i64 by an i32 to produce an i32 quotient and an i32 remainder. This will facilitate more optimization in future compilers. It can even afford performance gains retroactively, if someone detects the use of both quotient and remainder within the same scope. (WASM could also do so if it wanted to.) Division by zero should produce a defined result, even though it's inevitably nonsensical. If this is already moot by virtue of an exception, so be it, but merely defined behavior would be nice.

2. D2S32 dividends an i32 by the low 16 bits of another i32 in order to produce an i32 quotient and and i32 remainder (with 16 high zeroes in both cases). Optionally, we could leave the result as a packed i16:i16.

3. D2S16 dividends the low 16 bits of an i32 by the low 8 bits of another i32 in order to produce an i32 quotient and and i32 remainder (with 24 high zeroes in both cases). Optionally, we could leave the result as a packed i18:i18.

4. D2S128 divides an i128 encoded in a pair of i64 variables by an i64 in order to produce an i64 quotient and an i64 remainder. Optional but very helpful in bigint contexts.

5. M2B64 inputs a pair of i32 registers and outputs an i64 product (which is exactly correct including proper carry propagation).

6. M2B32 inputs the low 16 bits of a pair of i32 registers and outputs an i32 product. This is needed because it enables performance gains by explicitly utilizing a cheaper multiply.

7. M2B16 inputs the low 8 bits of a pair of i32 registers and outputs an i32 product.

8. M2B128 inputs a pair of i64 registers and outputs the product as an i128 encoded in another such pair. Optional but very helpful in bigint contexts.

[KloudKoder]

For the record, the presentation of this issue to the community group is being rescheduled, tentatively for June 8. This is due to cascading technical failures on my part which prevented me from participating today, despite a valiant attempt by the hosts to assist. I know how to prevent this from occurring next time.

[lars-t-hansen]

I'm having a hard time seeing that a "virtual carry register" fixes any actual problems. In an optimizing JIT, we'll build an SSA graph from the wasm input and then optimize that graph before allocating registers and pasting up the machine code. These optimization passes may merge and split and move blocks and may therefore change the semantics of the virtual carry unless they are careful to track that flag exactly; that is, with a virtual carry register the graph builder will just have to reconstruct the information about the carry flag that the program could have been providing in the first place. Representing the carry explicitly as an input and output of the carry-aware instructions seems much cleaner. This does not commit the JIT to "dedicating a 64-bit register" to the flag except when the flag is live at the end of the instruction that produces it (live in the sense that there is another instruction later that reads the output value) and cannot be kept in the flags register until it is consumed. Representing it explicitly has the nice side effect of getting rid of several instructions that manipulate that flag.

I was noodling around with some wasm bytecode sequences for MP arithmetic and it seems like there are several competing styles for instructions that take a carry in (due to the stack machine and no let to manipulate the stack yet): what is the order of inputs and results? An unrolled carry-aware loop that likes to push all the input operands first probably wants the carry as the last input argument:

   i32.load offset=0 (local.get $p)
   i32.load offset=0 (local.get $q)
   i32.load offset=4 (local.get $p)
   i32.load offset=4 (local.get $q)
   i32.load offset=8 (local.get $p)
   i32.load offset=8 (local.get $q)
   i32.const 0  ;; carry in
   i32.adc      ;; (carry-out, result) <- add-with-carry(x, y, carry-in)
   i32.store offset=0 (local.get $r)
   i32.adc
   i32.store offset=4 (local.get $r)
   i32.adc
   i32.store offset=8 (local.get $r)
   drop         ;; carry out

while a loop that likes to load operands as they come along would prefer the carry as the first input argument:

   i32.const 0   ;; carry in
   i32.load offset=0 (local.get $p)
   i32.load offset=0 (local.get $q)
   i32.adc       ;; (carry-out, result) <- add-with-carry(carry-in, x, y)
   i32.store offset=0 (local.get $r)
   i32.load offset=4 (local.get $p)
   i32.load offset=4 (local.get $q)
   i32.adc
   i32.store offset=4 (local.get $r)
   i32.load offset=8 (local.get $p)
   i32.load offset=8 (local.get $q)
   i32.adc
   i32.store offset=8 (local.get $r)
   drop         ;; carry out

and really the same question is there for the outputs: placing the carry-out on top of the stack forces a style where the results are processed after all the operations are done; placing it underneath (as above) forces the processing of the result after each operation.

Loading the inputs late and storing them early is kinder to register-poor architectures. It may be that multiple styles of instruction are desirable.

An enumeration of use cases for add-with-carry and subtract-with-borrow would be useful. If MP arithmetic is the main use case, perhaps MP arithmetic instructions would be a better choice.