Alternative or addition: instructions with overflow/carry flags

[alexcrichton]

Perhaps the primary alternative to this proposal that would try to solve the same original problem would be to add instructions that manipulate/expose the overflow flag directly from native hardware. This is lower level than 128-bit operations themselves and the theory is that 128-bit operations could be built from these lower level instructions. The original proposal explicitly did not propose this due to complexity of optimizing these instructions and the ease of achieving performance on desired benchmarks with 128-bit operations. In the CG meeting however it was brought up that these lower-level primitives might be a better choice.

This issue is intended to be a discussion location for continuing to flesh out the flags-vs-128-bit-ops story. More thorough rationale will be needed in later phases to either explicitly use flag-based ops or not. This will likely be informed through experience in implementations in other engines in addition to performance numbers of relevant benchmarks.

[alexcrichton]

I've opened #10 with some more discussion behind the background of this proposal. It notably outlines the possible shape of these instructions plus why they had bad performance in Wasmtime with the initial implementation.

[alexcrichton]

One concern I might have with going exclusively with overflow/carry flags is that platforms like RISC-V don't have the same instructions as x86/aarch64 and they might be slower. For example implementing i64.add_with_carry_u on RISC-V to achieve 128-bit addition might end up being slower than what RISC-V already generates today. I'm not aware of other platforms missing these instructions, though, so RISC-V may be the only one affected and I additionally do not have a machine to benchmark on to confirm this hypothesis one way or another.

[waterlens]

One concern I might have with going exclusively with overflow/carry flags is that platforms like RISC-V don't have the same instructions as x86/aarch64 and they might be slower. For example implementing i64.add_with_carry_u on RISC-V to achieve 128-bit addition might end up being slower than what RISC-V already generates today. I'm not aware of other platforms missing these instructions, though, so RISC-V may be the only one affected and I additionally do not have a machine to benchmark on to confirm this hypothesis one way or another.

It is more likely to be a problem with the design of RISC-V ISA itself, as suggested by this discussion. It could be a big sacrifice for WASM if we give up such common operations on other hardware platforms, just because RISC-V people currently don't care about this.

[alexcrichton]

That's a good point! I should clarify that it's something I think is worth measuring, but I don't think it's a showstopper preventing such an alternative such as this.

---

Orthogonally I wanted to flesh out some more numbers on this of what I'm measuring locally. Using the benchmarks in https://github.com/alexcrichton/wasm-benchmark-i128 I measured the slowdown relative-to-native of wasm today, with this proposal as-is with 128-bit ops, and then with this alternative instead of overflow/carry flags (plus i64.mul_wide_*). Each column in the table is a different wasm binary benchmarked and each row is a benchmark. Lower is better as it means it's closer to native. This was collected with Wasmtime 25ish and on Linux x86_64.

Benchmark	Wasm Today	Wasm + 128-bit-arithmetic	Wasm + overflow/carry/mul_wide
blind-sig	617%	74%	79%
lehmer	362%	12%	-7%
mul-bignum	391%	30%	111%
fib_10000	122%	15%	100%
shl	93%	92%	93%
shr	98%	98%	95%
div-bignum	345%	160%	234%
sort signed	63%	64%	64%
sort unsigned	72%	72%	69%

Summary,:

• blind-sig - both approaches are roughly equivalent as this is a multiplication-heavy benchmark
• lehmer - this shows mostly that mul_wide can sometimes optimize better than mul128. I'll note this in Is mul128 going to be as fast as widening multiplication? #11.
• mul-bignum / div-bignum - these benchmarks have more addition than previous ones and show that the overflow/carry approach is significantly slower than add128
• fib_10000 - this shows add128 performing much better than overflow/carry
• others - not affected

The most notable result is that add128 is performing much better in addition operations than overflow/carry operations. This may be counterintuitive to expectation. I've outlined the reason as to why in the explainer a bit but to summarize that here the most general lowerings of overflow/carry ops require moving the carry flag out of the EFLAGS register and back into it. That in turn causes significant slowdown if it's not optimized away, and Wasmtime/Cranelift do not have a means of optimizing it away. In the 128-bit op case that more closely matches the original program semantics

[alexcrichton]

I've posted some more thoughts to record in the overview in #18

[waterlens]

Basically, I agree with your opinion. The correct modeling of how the carry flag works in the compiler is rare. There is a trade-off between less effort and optimal performance. The instructions to be added can not be perfect semantically, especially considering there aren't many people dedicated to the work. The current speedup is already considerable, so please go ahead and push this proposal upstream!

[sparker-arm]

Hi @alexcrichton

most general lowerings of overflow/carry ops require moving the carry flag out of the EFLAGS register and back into it

I'm not an x86 person, so could you clarify how your are lowering these operations? Can't a 'wide' add be lowered to add and adc, without having to explicitly move data from flags? Or do you just mean this is happening an a micro-arch level?

I mainly ask because the mul_wide operations sound good, but I expected to see add/sub with the same signature.

[alexcrichton]

Hello! And sure! I might also point towards the overview docs which is a summary of the phase 2 presentation I last gave to the CG.

You're correct that i64.add128 gets lowered to add + adc (and add + adds on aarch64). The problem that I was describing there was i64.add_overflow_s, a separate instruction, which produces two values: the addition result + overflow bit. That overflow bit, in the most general case, needs to be put in a general purpose register which is the "move out of EFLAGS". Later if that's then combined with i64.add_with_carry_s which takes three inputs (e.g. lhs/rhs/overflow bit) then to use adc (or adds) then the overflow bit needs to be "put back in EFLAGS" somehow since adc and adds don't actually take three register input operands, only 2 and one is implicitly in the flags register.

[sparker-arm]

Ah yes, I understand now. Flags are a pain... :)

Thanks.

[jakobkummerow]

While I'm strongly in favor of making wide arithmetic faster in Wasm, I continue to be unconvinced by the claim that "add128 is faster than add_with_overflow", and I believe that the experimental numbers that "prove" it only reflect prototype implementation deficiencies that could be ironed out (and wouldn't even be hard to iron out). Let me explain:

The "bignum" use case is, in general and regardless of specific library or language, an addition loop: given two vectors A, B of integers, add them element-by-element, propagating the carry, storing each result element in a result vector S (much like we all did by hand in elementary school). The integers will typically have register width, i.e. be uint64 on 64-bit hardware, because that's most efficient. The heavy lifting will be done by some loop, in pseudocode roughly:

carry = 0;
for each pair of items a=A[i], b=B[i] {
  [sum, next_carry] = add_snowman(a, b, carry)
  S[i] = sum
  carry = next_carry
}
S[A.length] = carry

So, how can we represent add_snowman in Wasm? It must take three inputs (at a minimum: two in 64-bit range, one in 1-bit range), and produce two outputs: the low 64 bits of the addition, and the overflow (=carry) bit (which is guaranteed to be either 0 or 1, and could have any type large enough to represent these). Let's consider a few hypothetical possibilities:

A. add128 as currently proposed. We actually need two of them:

[temp_low, temp_high] = add128(a, 0, b, 0)  // The two '0' are the "high parts" of a and b.
[sum, next_carry] = add128(temp_low, temp_high, carry, 0)

For easier comparison with the following options, let's write this in one line and with abbreviated names:

[s, nc] = add128(add128(a, 0, b, 0), c, 0)

That works fine, but the nesting is unsightly, leading to an idea to streamline that:

B. add128_three taking three (lo, hi) pairs of i64 inputs and producing a (lo, hi) pair of i64 outputs:

[s, nc] = add128_three(a, 0, b, 0, c, 0)

That's more elegant, but why should we have to emit so many zero-constants? Let's streamline those too, leading to the next idea:

C. add64_three taking three i64 "low halves" and returning a (lo, hi) pair:

[s, nc] = add64_three(a, b, c)

D. add_with_carry: That's actually the same as (C), just with a different name, and a degree of freedom whether the type of the third summand should be i64 like the others, or something smaller -- doesn't really matter.

Notably, all four options should get compiled to the same machine instruction sequence. In fact, engines have the hardest job for (A): they need to special-case the fact that two add128 instructions are immediately following each other, and they need to special-case the fact that half of the inputs are constant zeros; only then can they emit the most efficient machine code sequence. In the fully generic case of arbitrary inputs, they'll have to emit a lot more code. Engines have it easiest with (C)/(D), where no pattern recognition is necessary and even simple baseline/single-pass compilers can do a good job (i.e. emit an add/adc pair internally).
Also notably, an engine that has implemented (A) can trivially map (C) onto that implementation by filling in the 0 constants for the high parts. That's why the claim that (D) is necessarily slower than (A) is absolutely unconvincing.

I think all options are implementable. I do think that (A) is significantly more complex, because it has to be prepared to handle the case where none of the inputs are constant 0, while also needing a bunch of pattern-matching to make the common case as fast as possible (i.e. as fast as (C)). And I also think that for the bignum use case, there is no way (A) would have a fundamental performance benefit over either (B) or (C).

Of course, if you pick addition of two 128-bit integers with ignored/truncated overflow into the 129th bit as the example you study, then (A) will be the best fit, because it does exactly that. But for the "bignum" use case (as exemplified in the "fib_10000" benchmark quoted above), there should be no performance difference between all four options -- if there is one, then something's wrong with the implementation(s) of toolchains or engines or both.

In summary, I see a pleasing symmetry here:
For multiplication, it's uncontentious that we want an instruction that does [a:i64, b:i64] -> [low:i64, high:i64]. And for addition, the simplest equivalent would be an instruction with the same signature. A more efficient (for the primary use case) alternative would be a 3-summand addition with wide output [a:i64, b:i64, c:i64] -> [low:i64, high:i64] because grouping two 2-summand additions like that makes it easier for simple engines to use the most-efficient machine instruction (adc) more often.

My pseudocode example above assumed for simplicity that both inputs have the same vector length. If they have unequal lengths, then a two-operand addition with wide output is useful too. So, my suggestion for maximum performance and simplicity would be to add the following six instructions:

i64.add_wide:   [i64, i64] ->      [i64, i64]  ;; a + b -> (low, high=carry)
i64.add3_wide:  [i64, i64, i64] -> [i64, i64]  ;; a + b + c -> (low, high=carry)
i64.sub_wide:   [i64, i64] ->      [i64, i64]  ;; a - b -> (difference, borrow)
i64.sub2_wide:  [i64, i64, i64] -> [i64, i64]  ;; a - b - c -> (difference, borrow)
i64.mul_wide_u: [i64, i64] ->      [i64, i64]  ;; a * b -> (low, high)
i64.mul_wide_s: [i64, i64] ->      [i64, i64]  ;; a * b -> (low, high)

(I didn't see any detailed discussion of sub128 in this repo. Having "wide input" semantics there is probably workable but weird, because you'd normally have to pass constant 1 as the high part, and then the result's high part is the inverse of the "borrow bit", i.e. it's 0 if the borrow is 1 and vice versa, and you'd have to flip it before being able to use it in the vector processing loop's next iteration. I think it's easier for everyone to just return the borrow bit as the second result.)