Background
BigInts are commonly represented as arrays of "digits" or "limbs", typically register-sized unsigned integers. So adding two BigInts means adding these digits and propagating carries; basically like elementary school math, just with bigger digits. In pseudo code, assuming identical length for simplicity, this is:
let carry = 0;
for (let i = 0; i < length; i++) {
result[i], new_carry = add3(a[i], b[i], carry);
carry = new_carry;
}
The code for the helper function add3 needs a way to express the carry it produces; languages like C++ or Rust typically accomplish that by using a type that's wider than the digit type:
u64 add3(u64 a, u64 b, u64 c_in, u64* c_out) {
u128 result = u128{a} + u128{b} + u128{c};
*c_out = result >> 64;
return cast<u64>(result);
}
Of course, today's common 64-bit CPUs don't have 128-bit addition instructions, so compilers compile this code to a sequence of 64-bit operations. It's easy for a compiler to realize that the upper half of 64-to-128 bit widenings like u128{a} is zero, and to optimize out this constant. That leads to a machine code sequence like the following (x86_64; actual Clang output; all the names are denoting registers):
mov result_low, carry_reg
xor carry_reg, carry_reg
add result_low, [src1 + 8*index]
setc carry_reg
add result_low, [src2 + 8*index]
adc carry_reg, 0
mov [dst + 8*index], result_low
Note that there are 3 additions in this sequence: one for adding c_in+a, one for adding b onto that, one for adding the two carry bits that the previous two additions might have produced. That's a correct translation for a context-free interpretation of the add3 function above: if all of a, b, c_in are sufficiently large values, then c_out could be 2, and all three additions perform nontrivial work.
Optimization opportunity
However, if we inline add3 into the for-loop above and take that context into account, we can generate a more optimal machine code sequence that needs only one or two additions. The reason is that carry starts out as 0, and in the loop's first iteration can at most become 1, and then in every following iteration is also guaranteed to remain in range 0..1: even if a and b are both maximal, at most one carry bit is produced by adding up all three values: 0xFFFF'FFFF'FFFF'FFFF + 0xFFFF'FFFF'FFFF'FFFF + 1 == 0x1'FFFF'FFFF'FFFF'FFFF. So there is no need for the third addition, and one of the other two can be replaced with a shift; we can get by with just this:
shr carry_reg, 1 ;; Shifts carry_reg into the carry flag
mov result_low, [src1 + 8*index]
adc result_low, [src2 + 8*index]
setc carry_reg ;; register was zeroed by initial `shr`
mov [dst + 8*index], result_low
Emitting this optimal machine code sequence hence requires analyzing the context and figuring out that one of the three inputs to add3 is guaranteed to remain in range 0..1. It is entirely possible to run this analysis in the optimizing JIT compiler of a Wasm engine. However, I argue that a design that allows moving this analysis work to AOT toolchains/optimizers would be a better fit for Wasm's philosophy: it would allow even simple engines to emit optimal machine code, without having to run fancy analysis passes first. This requires the Wasm wire bytes to carry more information than the add128 instruction in the current version of this proposal does.
Approach 1: Range annotation
One obvious approach would be to directly express the notion that c_in is in range 0..1. We could devise various range annotation schemes for this; one straightforward way to do it would be to introduce an i1 type. AOT toolchains (in particular: LLVM in Wasm mode) would detect the pattern discussed above, and would translate the entire add3 function to a single Wasm instruction add_with_carry with signature [i64, i64, i1] -> [i64, i1]. Engines could, with zero further analysis, translate that single Wasm instruction to the optimal machine code sequence; that's super simple to do even for a single-pass baseline compiler.
The i1 type would be a special tool for a special purpose; it would not be a general-purpose arithmetic type with a complete set of operations that process it. Like other scalar types, it would have no interaction with any other type (no subtyping/casting/…). It would not require any special hardware support, and would not be expected to be represented in the CPU's flags register. Recall its purpose, which is to annotate a register-sized integer with the fact that its value is guaranteed to be in range 0..1. So engines would be expected to represent it internally as exactly that: a conveniently-sized integer, with range information expressed by its type, which compilers can use to emit better code.
The only instructions required for an i1 type would be those that the loop above uses:
i1.const for initializing the local. (Technically, implicit zero-initialization might be enough, but it's probably nice to have an instruction for this.)add_with_carry and its mirror image sub_with_borrow- some way to inspect or convert the final carry after the end of the loop, perhaps
i64.extend_i1 and/or i1.eqz.
The only places where an i1 type must definitely be allowed to occur is in locals and on the value stack; however since it's just a "conveniently sized integer with attached range information", it is easy to allow it anywhere: function signatures, globals, structs, arrays.
Approach 2: "Special" instruction behavior
A possible alternative approach would be to only use existing types for add_with_carry's signature: [i64, i64, i64] -> [i64, i64], and add extra descriptions to the instruction's specified behavior.
Variant A: "the third input must be in range 0..1, and then the second output will also be in that range; otherwise the behavior is implementation-defined". That would allow engines to emit the optimal code sequence above, and simply not care about the weirdness that will happen if c_in > 1. (You may think "invalid inputs should trap", but as the assembly snippets in this post show, the whole endeavor is about shaving off every single machine instruction that we can get rid of, so adding a check for a trap would be way too costly to be worth it in comparison to the potential gains.)
Variant B: "the third input is treated like a boolean value: any value > 0 is treated as if it were 1. The second output is always in range 0..1". This idea of "treat it as a boolean" has precedent in the if instruction, which takes an i32 but only cares whether it is zero or non-zero. This variant would require a slightly different instruction sequence with distinct carry_in/carry_out registers, replacing the initial shr with an add to perform the "rounding" of any nonzero value to 1, and using an xor to clear carry_out:
xor carry_out, carry_out
add carry_in, -1 ;; sets carry flag iff carry_in != 0
mov result_low, [src1 + 8*index]
adc result_low, [src2 + 8*index]
setc carry_out
mov [dst + 8*index], result_low
While this seems at first like it would require an additional mov to move the value from carry_out to carry_in for the next iteration, this is often not the case in practice due to loop unrolling: for such a small loop, optimizing compilers will typically emit at least two copies of the loop body anyway, and can hence "ping-pong" the carry value between two registers without additional cost.
(You might consider replacing the xor before the setc with a zero-extending movzx after it, which would easily make it possible to use the same register for carry_in and carry_out, but that turns out to be slower due to CPU-internal data dependencies.)
It could make sense to use a different type for the third input just to make it clearer that the three are not interchangeable. The obvious choice for that would be i32, so we'd have [i64, i64, i32] -> [i64, i32] (with the same semantics as before).
Performance
It turns out that the two optimized machine code sequences above (the one with shr for "third input is in 0..1 range, either due to i1 type annotation or due to instruction semantics that ignore anything else", and the one with add -1 for "third input is treated as boolean") have practically the same performance.
In a loop that adds two BigInts (i.e. vectors of u64 digits stored in linear memory), the optimized sequences are consistently 9% faster than the original sequence on my machine (Zen 3). I think that speedup is worth having!
In Alex' i128 benchmarks, the largest impact is on "fib_10000" with around 3% improvement in my measurements. Considering that a Fibonacci benchmark should mostly be performing additions, I'm surprised that the impact is so much less there; I have not spent the time to figure out why that is.
Other thoughts
Adding an i1 type "just for this" might feel like a lot of effort, but considering that it would only need a very small instruction set, I argue that it would, in fact, not be a lot of effort. For engines it would be less implementation work than the add128 version of this proposal. And it could be a good investment in the sense that it could have other uses in the future.
In particular, it would be unfortunate if we accepted a slightly weird workaround now just to get by without an i1 type, only to introduce it next time it's useful. That said, aesthetics of the wire bytes don't really matter, and the approach of treating an i32 as a boolean works just as well to accomplish the performance goals here.
One conceivable future use for i1 is bit packing in struct fields, even denser than i8 fields. Of course the type would be just a hint and an engine's actual behavior unobservable, just like today it is up to engines to represent an i8 as an actual byte, rather than just treating it as an alias for "i32", and just like it is up to engines to reorder a field sequence like [i8, i32, i8] for better density.
Background
BigInts are commonly represented as arrays of "digits" or "limbs", typically register-sized unsigned integers. So adding two BigInts means adding these digits and propagating carries; basically like elementary school math, just with bigger digits. In pseudo code, assuming identical length for simplicity, this is:
The code for the helper function
add3needs a way to express the carry it produces; languages like C++ or Rust typically accomplish that by using a type that's wider than the digit type:Of course, today's common 64-bit CPUs don't have 128-bit addition instructions, so compilers compile this code to a sequence of 64-bit operations. It's easy for a compiler to realize that the upper half of 64-to-128 bit widenings like
u128{a}is zero, and to optimize out this constant. That leads to a machine code sequence like the following (x86_64; actual Clang output; all the names are denoting registers):Note that there are 3 additions in this sequence: one for adding
c_in+a, one for addingbonto that, one for adding the two carry bits that the previous two additions might have produced. That's a correct translation for a context-free interpretation of theadd3function above: if all ofa,b,c_inare sufficiently large values, thenc_outcould be 2, and all three additions perform nontrivial work.Optimization opportunity
However, if we inline
add3into thefor-loop above and take that context into account, we can generate a more optimal machine code sequence that needs only one or two additions. The reason is thatcarrystarts out as0, and in the loop's first iteration can at most become1, and then in every following iteration is also guaranteed to remain in range0..1: even ifaandbare both maximal, at most one carry bit is produced by adding up all three values:0xFFFF'FFFF'FFFF'FFFF + 0xFFFF'FFFF'FFFF'FFFF + 1 == 0x1'FFFF'FFFF'FFFF'FFFF. So there is no need for the third addition, and one of the other two can be replaced with a shift; we can get by with just this:Emitting this optimal machine code sequence hence requires analyzing the context and figuring out that one of the three inputs to
add3is guaranteed to remain in range0..1. It is entirely possible to run this analysis in the optimizing JIT compiler of a Wasm engine. However, I argue that a design that allows moving this analysis work to AOT toolchains/optimizers would be a better fit for Wasm's philosophy: it would allow even simple engines to emit optimal machine code, without having to run fancy analysis passes first. This requires the Wasm wire bytes to carry more information than theadd128instruction in the current version of this proposal does.Approach 1: Range annotation
One obvious approach would be to directly express the notion that
c_inis in range0..1. We could devise various range annotation schemes for this; one straightforward way to do it would be to introduce an i1 type. AOT toolchains (in particular: LLVM in Wasm mode) would detect the pattern discussed above, and would translate the entireadd3function to a single Wasm instructionadd_with_carrywith signature[i64, i64, i1] -> [i64, i1]. Engines could, with zero further analysis, translate that single Wasm instruction to the optimal machine code sequence; that's super simple to do even for a single-pass baseline compiler.The i1 type would be a special tool for a special purpose; it would not be a general-purpose arithmetic type with a complete set of operations that process it. Like other scalar types, it would have no interaction with any other type (no subtyping/casting/…). It would not require any special hardware support, and would not be expected to be represented in the CPU's flags register. Recall its purpose, which is to annotate a register-sized integer with the fact that its value is guaranteed to be in range
0..1. So engines would be expected to represent it internally as exactly that: a conveniently-sized integer, with range information expressed by its type, which compilers can use to emit better code.The only instructions required for an i1 type would be those that the loop above uses:
i1.constfor initializing the local. (Technically, implicit zero-initialization might be enough, but it's probably nice to have an instruction for this.)add_with_carryand its mirror imagesub_with_borrowi64.extend_i1and/ori1.eqz.The only places where an i1 type must definitely be allowed to occur is in locals and on the value stack; however since it's just a "conveniently sized integer with attached range information", it is easy to allow it anywhere: function signatures, globals, structs, arrays.
Approach 2: "Special" instruction behavior
A possible alternative approach would be to only use existing types for
add_with_carry's signature:[i64, i64, i64] -> [i64, i64], and add extra descriptions to the instruction's specified behavior.Variant A: "the third input must be in range 0..1, and then the second output will also be in that range; otherwise the behavior is implementation-defined". That would allow engines to emit the optimal code sequence above, and simply not care about the weirdness that will happen if
c_in > 1. (You may think "invalid inputs should trap", but as the assembly snippets in this post show, the whole endeavor is about shaving off every single machine instruction that we can get rid of, so adding a check for a trap would be way too costly to be worth it in comparison to the potential gains.)Variant B: "the third input is treated like a boolean value: any value > 0 is treated as if it were 1. The second output is always in range 0..1". This idea of "treat it as a boolean" has precedent in the
ifinstruction, which takes ani32but only cares whether it is zero or non-zero. This variant would require a slightly different instruction sequence with distinctcarry_in/carry_outregisters, replacing the initialshrwith anaddto perform the "rounding" of any nonzero value to 1, and using anxorto clearcarry_out:While this seems at first like it would require an additional
movto move the value fromcarry_outtocarry_infor the next iteration, this is often not the case in practice due to loop unrolling: for such a small loop, optimizing compilers will typically emit at least two copies of the loop body anyway, and can hence "ping-pong" the carry value between two registers without additional cost.(You might consider replacing the
xorbefore thesetcwith a zero-extendingmovzxafter it, which would easily make it possible to use the same register forcarry_inandcarry_out, but that turns out to be slower due to CPU-internal data dependencies.)It could make sense to use a different type for the third input just to make it clearer that the three are not interchangeable. The obvious choice for that would be
i32, so we'd have[i64, i64, i32] -> [i64, i32](with the same semantics as before).Performance
It turns out that the two optimized machine code sequences above (the one with
shrfor "third input is in0..1range, either due toi1type annotation or due to instruction semantics that ignore anything else", and the one withadd -1for "third input is treated as boolean") have practically the same performance.In a loop that adds two BigInts (i.e. vectors of u64 digits stored in linear memory), the optimized sequences are consistently 9% faster than the original sequence on my machine (Zen 3). I think that speedup is worth having!
In Alex' i128 benchmarks, the largest impact is on "fib_10000" with around 3% improvement in my measurements. Considering that a Fibonacci benchmark should mostly be performing additions, I'm surprised that the impact is so much less there; I have not spent the time to figure out why that is.
Other thoughts
Adding an i1 type "just for this" might feel like a lot of effort, but considering that it would only need a very small instruction set, I argue that it would, in fact, not be a lot of effort. For engines it would be less implementation work than the
add128version of this proposal. And it could be a good investment in the sense that it could have other uses in the future.In particular, it would be unfortunate if we accepted a slightly weird workaround now just to get by without an i1 type, only to introduce it next time it's useful. That said, aesthetics of the wire bytes don't really matter, and the approach of treating an i32 as a boolean works just as well to accomplish the performance goals here.
One conceivable future use for i1 is bit packing in struct fields, even denser than i8 fields. Of course the type would be just a hint and an engine's actual behavior unobservable, just like today it is up to engines to represent an i8 as an actual byte, rather than just treating it as an alias for "i32", and just like it is up to engines to reorder a field sequence like
[i8, i32, i8]for better density.