Polymorphic operators

[AndrewScheidecker]

I count 174 opcodes in use right now. It seems inevitable that there will eventually be more than 256, but in the mean time the number could be reduced substantially by making more operators polymorphic. In addition to freeing up some index space, making the opcodes polymorphic allows the operators to be extended to new types added in the future: e.g. f16, i8, or f32x4.

This would be ad-hoc polymorphism; a little bit different from the existing parametric operators like get_local and select. However, numeric, integer, and float type classes can be used to specify the domain of some of these operators.

Here's an example that replaces 125 of the opcodes with 56 (which would reduce the total to 105):

new (polymorphic)	old (i32)	old (i64)	old (f32)	old (f64)
num.add	i32.add	i64.add	f32.add	f64.add
num.sub	i32.sub	i64.sub	f32.sub	f64.sub
num.mul	i32.mul	i64.mul	f32.mul	f64.mul
num.div_s	i32.div_s	i64.div_s	f32.div_s	f64.div_s
num.neg	i32.neg	i64.neg	f32.neg	f64.neg
num.eq	i32.eq	i64.eq	f32.eq	f64.eq
num.ne	i32.ne	i64.ne	f32.ne	f64.ne
num.lt_s	i32.lt_s	i64.lt_s	f32.lt	f64.lt
num.le_s	i32.le_s	i64.le_s	f32.le	f64.le
num.gt_s	i32.gt_s	i64.gt_s	f32.gt	f64.gt
num.ge_s	i32.ge_s	i64.ge_s	f32.ge	f64.ge
int.div_u	i32.div_u	i64.div_u
int.rem_s	i32.rem_s	i64.rem_s
int.rem_u	i32.rem_u	i64.rem_u
int.and	i32.and	i64.and
int.or	i32.or	i64.or
int.xor	i32.xor	i64.xor
int.shl	i32.shl	i64.shl
int.shr_u	i32.shr_u	i64.shr_u
int.shr_s	i32.shr_s	i64.shr_s
int.rotr	i32.rotr	i64.rotr
int.rotl	i32.rotl	i64.rotl
int.lt_u	i32.lt_u	i64.lt_u
int.le_u	i32.le_u	i64.le_u
int.gt_u	i32.gt_u	i64.gt_u
int.ge_u	i32.ge_u	i64.ge_u
int.clz	i32.clz	i64.clz
int.ctz	i32.ctz	i64.ctz
int.eqz	i32.eqz	i64.eqz
int.popcnt	i32.popcnt	i64.popcnt
fp.min			f32.min	f64.min
fp.max			f32.max	f64.max
fp.abs			f32.abs	f64.abs
fp.copysign			f32.copysign	f64.copysign
fp.ceil			f32.ceil	f64.ceil
fp.floor			f32.floor	f64.floor
fp.trunc			f32.trunc	f64.trunc
fp.nearest			f32.nearest	f64.nearest
fp.sqrt			f32.sqrt	f64.sqrt
i32.trunc_s			i32.trunc_s/f32	i32.trunc_s/f64
i32.trunc_u			i32.trunc_u/f32	i32.trunc_u/f64
i64.trunc_s			i64.trunc_s/f32	i64.trunc_s/f64
i64.trunc_u			i64.trunc_u/f32	i64.trunc_u/f64
i32.wrap	i32.wrap/i64
i64.extend_s	i64.extend_s/i32
i64.extend_u	i64.extend_u/i32
f32.convert_s	f32.convert_s/i32	f32.convert_s/i64
f32.convert_u	f32.convert_u/i32	f32.convert_u/i64
f64.convert_s	f64.convert_s/i32	f64.convert_s/i64
f64.convert_u	f64.convert_u/i32	f64.convert_u/i64
f64.promote			f64.promote/f32
f32.demote				f32.demote/f64
f32.reinterpret	f32.reinterpret/i32
f64.reinterpret		f64.reinterpret/i64
i32.reinterpret			i32.reinterpret/f32
i64.reinterpret				i64.reinterpret/f64

See also #620 and #678

The counter argument might be that it adds a little to the decoder overhead, that it will need to dispatch on the type of arguments. Someone needs to prototype this in a high performance decoded and double check the overhead.

It might help the text format too, because then + can be used for num.add irrespective of the types. A text format might need to present i32.add rather than + if the types are not valid.

[sunfishcode]

One mitigating factor here is that potential future types such as f16 and f32x4 are expected to be relatively infrequent, relative to the MVP operators, even in programs that use them. It may make sense to put all SIMD opcodes somewhere safely into the multiple-byte opcode space anyway, because many programs don't use SIMD, and even in those that do it's often not a significant percentage of overall size.

It should help the compression too as it eliminates redundant information. A higher level compressor would be doing this anyway so would have the decoding overhead anyway.

[AndrewScheidecker]

As mentioned in #791, memory operators could be polymorphic in the address size. This could either be based on an explicit address-size in the type of the memory object, or by simply making work with either 32-bit or 64-bit addresses.

[AndrewScheidecker]

Here's a strawman encoding for a polymorphic operator set (I mean this to be illustrative rather than a concrete proposal): https://docs.google.com/spreadsheets/d/1vBiBjNfvoCy2ChGILA7xXe720iJTe_0Nzu5cBizVIzs/edit#gid=898725473

The top 4-5 bits of the first byte of the opcode are a category. If the top bit of the category is 1, then the signature of the operator (including immediates) is independent of the other bits of the opcode.

If the bottom 3 bits of the first opcode byte are 111, then it is followed by another opcode byte. If the top bit of the second byte is 1, then it is followed two more opcode bytes. This provides 224 1-byte opcodes, 4K 2-byte opcodes, and 268M 4-byte opcodes. I think that having a larger 1-byte opcode space is worth a departure from the use of LEB128 in other parts of the standard.

It may make sense to put all SIMD opcodes somewhere safely into the multiple-byte opcode space anyway, because many programs don't use SIMD, and even in those that do it's often not a significant percentage of overall size.

Yes; my proposed application of polymorphic operators in a SIMD extension is that a polymorphic operator like num.add could be extended to be an element-wise addition of two SIMD vectors. f32x4.load should probably be a 2-byte opcode, but f32x4.add doesn't need to be a distinct opcode from f32.add or i64.add. However, I can see that some of the current scalar operators wouldn't be worth implementing for SIMD types, so this would require a bit more precision than just extending all the polymorphic operators to vectors.

One interaction I did not realise is that (num.add (unreachable)) would then not have a specific type, or a union type, which would add a little more complexity to the validator, probably more than people want to take on, and probably an area for significant 'spec' challenges getting agreement!

Would this proposal also back out the typing on block signatures, bring them back to just an arity, as the type can be derived.

[AndrewScheidecker]

I don't think that this would interact with unreachable code or block signatures any differently than select, or even i32.add.

Would this proposal also back out the typing on block signatures, bring them back to just an arity, as the type can be derived.

I think the explicit signatures on control structures are justified, because they can otherwise only be derived from the code following the block start. Resolving polymorphic operators only needs to look at the types of values on the stack pushed by preceding code.

[pizlonator]

It's too late for this.