SIMD binary encoding

[arunetm-zz]

It helps to understand how to encode the simd ops in wasm binary format.

Multi byte encoding scheme will be necessary to capture the 200+ new simd opcodes. As we need to encode the type info for interpreting operands along with the opcodes can it be that the first byte encodes the opcode followed by an immediate (byte) describing the type of operands when its needed?

[AndrewScheidecker]

Do you mean a type immediate to designate the scalar type (e.g. v128.add i8 ...), or..?

Something that would help with the explosion in SIMD operators is to use a smaller number of polymorphic operators. The strongest form of this would overload some subset of the base operators to work with v128 as well as scalars (and add vector-only operators only where there isn't a scalar equivalent): e.g. i32.add would replace i32x4.add. A weaker form that might still be beneficial would be to distinguish scalar and vector operators, but make the vector operators work on all vector widths: e.g. i8xN.add would replace both the i8x16.add and the i8x32.add operators. That doesn't help this initial SIMD proposal, but it would reduce the number of new operators necessary for a 256-bit SIMD extension to ~20.

I previously made an operator table for the stronger form of polymorphism (both i32x4.add and i32.add collapsed to i32.add). These are the numbers I came up with:

	scalar	scalar + SIMD128	scalar + SIMD128 + SIMD256
current	172	385	589
polymorphic	244	302	323

The increase in scalar operators for the polymorphic scheme is due to the addition of i8 and i16 scalar arithmetic and comparison operators. I think there's strong opposition to adding i8 and i16 scalar operators, so those operators would likely have to be vector-only in a serious proposal, but I wanted to illustrate that more than half of the remaining operators added for SIMD128 would be operators on vectors of i8 and i16 scalars that don't have a scalar equivalent.

My conclusion from that investigation was that yes, hundreds of SIMD operators are painful, and polymorphic operators would reduce the number quite a bit, but it would add complexity elsewhere. It's not an unqualified win.

Polymorphic operators also have the downside that verification is more complicated: their signature cannot be determined from the opcode alone. call and a few other operators have an immediate-dependent signature, and select has an operand-dependent signature, but doing it for 200+ SIMD operators is more of a burden. That complication is similar whether you make the opcode work on any vector width, or add immediates for vector width.

Keeping vector width-specific opcodes, but adding a scalar type immediate wouldn't have that complication, but it isn't something I thought of in my previous investigation. It might be worth digging into further.

I do think it makes sense to separate the opcode index space from multi-byte encoding issues. So e.g. SIMD128 would be allocated some contiguous range of indices that has a convenient encoding, but it would use the same scheme to map between opcode indices and multi-byte encodings as the threading extension, and all other WASM extensions.

[rossberg]

The idea is to follow the same approach as for the threads proposal: use a single designated SIMD prefix opcode. That creates plenty of room for individual SIMD opcodes, including future extensions.

[arunetm-zz]

@AndrewScheidecker Thanks for the analysis. The polymorphic scheme will help to reduce the number of opcodes in the expense of few added complexities. I am a little concerned about these validation costs though. The single designated prefix for simd, threads etc has the benefit of simplicity and better flexibility imo. There won't be any size savings in either schemes.

@rossberg-chromium, has there been a final decision on the designated prefix scheme for these post mvp features? (The link failed for me when i tried). Should there be a concern about the explosion of opcode count?

[stoklund]

I propose that we use a 0xf1 prefix byte followed by a varuint32 SIMD-specific opcode. This leaves room for future extensions.

[jfbastien]

0xc4 and 0xc5 seem most natural 🤡

[rossberg]

Guys, let me ask again, can we please be sane and allocate 0xff, 0xfe, and so on for prefix opcodes? There is nothing natural nor compelling about random Intel artifacts. Moreover, reserving 16 prefix opcodes is excessive, I doubt we'll ever have more than a handful.

[lukewagner]

Having opcodes "grow up" and prefixes "grow down" (so starting at 0xff) makes sense to me; that way we don't have to pick an up-front number of prefixes and we can course-correct as we see the gap closing. That seems better than having prefixes randomly scattered through the 1-byte space.

[aardappel]

I'd like to second @AndrewScheidecker's suggestion of polymorhic vector instructions, and maybe take it further. I think "hard-coding" all our ops to 128 now, and then later iterate to add 256, 512, and whatever else hardware will support next is going to be messy for everyone involved.

Ideally, I think it be great if wasm users can implement their vector code with the largest possible width that is practical for them, with implementations translating those into multiple ops if needed. Then, if your code runs on hardware with wider SIMD, it will automatically run faster without code changes.

Better yet, in an imaginary future world where a lot of the worlds number crunching code runs on wasm, hardware vendors can decide to support wider bit-widths and instantly get benefits, without having to wait many years for everyone to update their code to support it, or having to wait for a significant install-base.

This could generate undesirable register pressure, and would complicate instructions that don't operate pure lane-wise (reduction operations), but I personally think that is worth it. Again, it can be understood that such ops generate slightly more complexity if you choose >128-wide and you may run on hardware that is 128-wide only. It can be a choice by the programmer to limit themselves to 128 to be "safe", but certainly we don't have to make that choice for them.

[jfbastien]

Ideally, I think it be great if wasm users can implement their vector code with the largest possible width that is practical for them, with implementations translating those into multiple ops if needed. Then, if your code runs on hardware with wider SIMD, it will automatically run faster without code changes.

Do you know this to be true, or is it a theory? In my experience, narrowing or widening SIMD operations without caring for datalayout isn't an insta-win. I think we need solid experimental data to back up this approach.

[aardappel]

@jfbastien It is a theory :) I am making the assumption that companies like Intel haven't spent the last 10 years adding ever wider SIMD just for fun, but you're right, we shouldn't assume that is the right direction just because they went there.

I guess irrespective of performance, I can summarize my point as: if it is very likely we'll want wider SIMD later, we should probably already allow for it in the instruction format, and ideally emulate it until we get there.

[arunetm]

Bytecode encoding for simd is in place. Closing this issue.