Finalizing the instruction set

It's been a while since we introduced the criteria in #203 for evaluating new proposed instructions. Since then, we have made significant progress on the spec tests, text, and interpreter, to the point where finalizing the instruction set will soon be the main phase 4 blocker.

We should continue evaluating currently proposed instructions using the previous criteria and we should continue to be open to bug fixes and improvements to our existing instructions, but I propose that effective immediately (upon stakeholder agreement) we start labeling all new proposed instructions as post-mvp. Does that sound reasonable to everyone?

I think this is a good idea, but as part of this I think we should also come up with and make public an overall strategy for how incremental extensions will be made to the (fixed-width) instruction set. Having such a strategy will make it easier to draw the line for the MVP.

@lars-t-hansen

@lars-t-hansen, that's a good idea. My assumption was that we would lean heavily on the normal proposal process for follow-on extensions, but the more we sketch out a framework for how we will evaluate and group post-MVP instructions now, the more streamlined that those follow-on proposals will be. Did you have specific thoughts about what our strategy should be?

I think that one of the things that has worked out really well in this proposal has been having clear technical guidelines (e.g. portability, determinism) to focus development and prevent feature creep. Follow-on extensions to this proposal (i.e. not radically different proposals like scalable vectors or machine-specific instructions) will be easier to scope if they each focus on doing one thing well, either by focusing on a particular use case (e.g. neural networks) or a single instruction family (e.g. fma).

@tlively

@tlively, I think grouping instructions thematically is going to be very helpful and I support that. We need to be careful about how we define the groups so that we don't get into another (bulk memory, reference types, threads) quagmire, but maybe that's not too hard with these low-level instructions.

Part of our SIMD strategy will likely have to do with dealing with machine specific corner cases, though. IIRC both arm64 and x64 have support for 8-bit operations but differ in some cases. Also IIRC, the QFMA class of instructions had similar issues. These are desirable instruction (groups) and we should probably be talking about principles for handling cross-architecture incompatibilities (beyond NaN cases) so that we can ship this type of functionality.

These are desirable instruction (groups) and we should probably be talking about principles for handling cross-architecture incompatibilities (beyond NaN cases) so that we can ship this type of functionality.

Right, I think we need to start talking again about conditional compilation for these sorts of features -- either as a generic feature (https://github.com/webassembly/conditional-sections) or as something specific to SIMD.

I think we need to set a date for finalizing the instruction set, but this date should be in the future, not imminent. Right now the SIMD specification is missing whole classes of instructions (e.g. #348), and finalizing this early would make it unusable for a set of use-cases.

IMO a good criterion for finalizing the ISA would be to check that all instructions from ARM NEON and x86 SSE4.1 either:

Have a close equivalent in WAsm SIMD, or
Can't be specified in a portable and efficient way across architectures

IMO a good criterion for finalizing the ISA would be to check that all instructions from ARM NEON and x86 SSE4.1

Adding equivalents of "missing" hardware instructions does not guarantee users would be able to leverage them. In particular, I'd like to avoid the situation when we are going to add some amount of instructions which all map to existing hardware ops, but overall the speedup vs scalar is around 1x. Also, there are other desired properties aside from mapping of hardware instructions - code size is probably the most important criteria.

If we are serious about evaluating whether or not we can add any more instructions we need to have a set of actual, not micro, benchmarks linked from this repo, which we can test for both speed and size of generated binaries. If we can't come up with something like this, I'd rather freeze the set against adding new operations (fixing already added ops is OK).

@Maratyszcza

Getting full coverage of portable native instructions is an explicit non-goal of this proposal. That's why we've always had criteria demanding demonstrated speedups in real-world use cases. @Maratyszcza, how far in the future would you want the cutoff date to be?

IMO, we need to hold until at least end of the year, to make sure SIMD specification works for multiple classes of applications.

I'm concerned that SIMD specification might be too tied to the small number of applications ported so far, and missing important instructions needed for other applications. Checking instructions present in SSE4.1 and NEON is a good exercise in looking for missing instructions, as the designers of native SIMD instructions sets already had to make similar decisions on which instructions to include.

IMO, we need to hold until at least end of the year, to make sure SIMD specification works for multiple classes of applications.

Are there specific teams that we're waiting for? I'm curious why an additional 3 months is necessary now, since SIMD has been available experimentally for a year+ now.

Checking instructions present in SSE4.1 and NEON is a good exercise in looking for missing instructions, as the designers of native SIMD instructions sets already had to make similar decisions on which instructions to include.

Agreed, but there's no requirement that these instructions go into the SIMD MVP. We already know that there are instructions that will never be included in the SIMD MVP (e.g. anything with non-determinism), so I think it's reasonable to hold off on other instructions too, knowing that they can be bucketed into the next round of instructions.

Are there specific teams that we're waiting for? I'm curious why an additional 3 months is necessary now, since SIMD has been available experimentally for a year+ now.

Origin Trial is active since July 14, 2020 release of Chrome 84, just over two months. AFAICT, many teams were reluctant to port code to WebAssembly SIMD before OT as there wasn't any path to production. Some types of applications we haven't seen yet are:

Scientific computing applications, in particular using double-precision and mixed-precision (missing whole sets of instructions, see Double-precision SIMD conversions #348)
Hashing and cryptography (e.g. missing carry-less multiplication, unclear how well WAsm SIMD works for bitslicing algorithms)
Algorithms using Hamming weight (unclear if existing dynamic shuffle instruction is sufficient, or we need dedicated Population Count instructions)

Besides, I have several instruction proposals in review (#124, #127, #237, #247, #290, #350, #352), and I'd like to see them accepted/rejected based on performance evaluation. I think three months would be enough to finish it.

Agreed, but there's no requirement that these instructions go into the SIMD MVP. We already know that there are instructions that will never be included in the SIMD MVP (e.g. anything with non-determinism), so I think it's reasonable to hold off on other instructions too, knowing that they can be bucketed into the next round of instructions.

WebAssembly doesn't have any mechanism for runtime feature detection, and thus software must threat different WAsm extensions as separate architectures (e.g. TensorFlow.js has to recompile 3 times for WAsm MVP, WAsm SIMD, WAsm SIMD+Threads). Supporting both WAsm SIMD and WAsm SIMD2 is not like supporting SSE2 and SSE4, it is like supporting both x86 and ARM. Because of the resulting deployment pains, I want WAsm SIMD MVP to be sufficiently feature-complete that most applications could target it.

@lars-t-hansen

Some types of applications we haven't seen yet are ...

Thanks, this is helpful. I'm curious if we know whether anyone is actively working on porting for these applications, however. I wouldn't want to wait 3 months and be in the same place we are now.

Besides, I have several instruction proposals in review (#124, #127, #237, #247, #290, #350, #352), and I'd like to see them accepted/rejected based on performance evaluation. I think three months would be enough to finish it.

Some of these are older proposals, and I agree they should be resolved. Some of them are much newer, however. I'm a little concerned that we will keep finding another few instructions to add and not be able to move forward with the MVP.

WebAssembly doesn't have any mechanism for runtime feature detection, and thus software must threat different WAsm extensions as separate architectures

Agreed, this is an issue @lars-t-hansen brought up above. I think we should seriously consider adding an explicit runtime SIMD feature detection instruction for this purpose, so we don't have to increase the size of the support matrix you mention.

I think we should seriously consider adding an explicit runtime SIMD feature detection instruction for this purpose, so we don't have to increase the size of the support matrix you mention.

See #356!

Good that Marat mentions crypto - AES would probably be helpful, it's very widely used.

PPC and x86 have straightforward instructions but unfortunately ARM splits the operation differently: instead of ShiftRows, SubBytes, MixColumns, XOR (x86 AESENC), they have ShiftRows+SubBytes+XOR(AESE) and MixColumns (AESMC), and the AESE and AESMC should be consecutive to enable fusing. Anyone interested in defining a way to bridge that gap?

Cryptographic primitives are already exposed through Web Cryptography API, so I see little value in having AES instructions in the spec: they would be nice for parallel RNG, but given that multithreaded WAsm applications are uncommon, it wouldn’t have much usage. I was more thinking about carryless multiplication, which has use-cases in hashing beyond cryptography.

CLMUL is indeed interesting, +1 for that. AES is useful beyond standard crypto, though - RNG as you say (I wrote one), and some other hashes also use it (Meow hash).

@ngzhian

Yeah, sorry. And I can't seem to create the issue or assign the tags you're suggesting. I'll leave this for @ngzhian .

I doubt this is V8 bug, zeroing of the lanes requires extra manipulations. See #93.

@tlively

@tlively LLVM is re-generating the mask on each iteration of the loop instead of keeping it as a constant.

@omnisip

@omnisip Can you open a new issue on this repo with an example that demonstrates that problem in C/C++?

@omnisip

@omnisip V8 doesn't support constant loads from memory, so we regenerate the mask every time (tracking bug https://crbug.com/v8/10980).

As explained, vpaddusb is necessary due to how pshufb works, we need to set top bit of the shuffle mask to zero the destination lane. In general we have to do this all the time, but I think it makes you cry because you clearly used a constant mask, and yet V8 doesn't seem to know that. I think there can be some wins we get from pattern matching on swizzle(v128, v128.const) to get better codegen. (Filed https://crbug.com/v8/10992)

Can you share a simple benchmark for this, and do you think that this poor codegen will be a bottleneck? (note that if you are hand writing intrinsics, there are ways around this, like storing the mask into a v128 local, you will eliminate the ceremony around moving values into reg, moving into xmm, then shuffling just to create mask.)

@ngzhian

@ngzhian Thanks for the informed response. The insult to injury is that it's recreating the mask in the loop -- which is being caused outside of V8 by the LLVM code generation. After getting a better understanding of vpaddusb, I can actually appreciate how this works with pshufb.

Does this [mask regeneration] happen the same way with the shuffle operation or just with swizzle? I'd like to add a zshuffle such that zshuffle v128_a, v128_b, Imm[] becomes completely interchangeable with swizzle when the first two parameters are the same. The logic for adding zeroing looks pretty straightforward on both ARM, and X86. I'd also like to add a runtime variant of zshuffle that supports swizzling across two vectors. With both, we can have a functionally complete version of shuffle and swizzle that covers masked (runtime) and unmasked (compile time) cases.

With respect to the benchmark, I'm happy to do so. The challenge with this particular situation is that I have to keep adding operations to solve my unsigned 8bit to 32bit conversion, and I'm constantly shuffling (or swizzling) already because there's no horizontal add or horizontal multiply and add. [This particular use case gets a lot of benefit from pmaddubsw but I haven't finished the research yet to see how portable this functionality is]. So anything I can do to cut the number of ops is helpful.

One thing I'm interested in, but don't know how practical it is, is to update the standard for our shuffle to match the Intel pshufb implementation rather than worrying about adding and saturating. The reason I suggest this is because it's actually a really flexible implementation. Once you get to understand what they were doing by looking at the bottom four bits, you can easily scale the same logic to look at the bottom 5 bits for 32byte/256bit vectors, bottom 6 bits for 64byte/512bit vectors, and bottom 7bits for 128byte/1024bit vectors. That's a decent amount of room to grow going forward. If the ARM chipset doesn't require any extra emulation instructions to see that a value is out of range or it works in a way compatible with pshufb, we'll have a very flexible solution going forward. The only thing that would need to change is how the user is informed of what happens if the value doesn't have the top bit set, instead of correcting it for them, we just explain it takes the bottom bits and mask it out. We could put together a best practice of telling them to put 0xff in that field instead of 33 or 17 or whatever it may be.

Edits: Minor clarifications and antecedents.

(note that if you are hand writing intrinsics, there are ways around this, like storing the mask into a v128 local, you will eliminate the ceremony around moving values into reg, moving into xmm, then shuffling just to create mask.)

This is super intriguing. What do you mean by this? In my particular case, I'm actually pre-generating the shuffle masks once, but LLVM seems to be inlining them (and not consistently). If I could trick LLVM or V8 into thinking the thing was a string or such that I could load off of the stack, I'd be open to that too, but it seems like that's something related to constant generation.

@tlively

which is being caused outside of V8 by the LLVM code generation.

I think filing a bug to @tlively would be useful to track this. Maybe somewhere in Emscripten? (this repository has more to do with the specification rather than the implementat/toolchain).

Does this [mask regeneration] happen the same way with the shuffle operation or just with swizzle?

This mask regeneration you're seeing is specific to swizzle, and is specifically used to set up a mask (0x7070707070707070) to do saturating addition to deal with pshufb behavior. (We can probably reduce this down to 2 instructions rather than 3).

For shuffle, in general, we have no such mask setup, instead we copy the shuffle immediates into a register, then call pshufb. (https://source.chromium.org/chromium/chromium/src/+/master:v8/src/compiler/backend/x64/code-generator-x64.cc;l=3706;drc=1d85b5f7bd02e59acf890afdf6255fed92b2a701).

We have a special check for shuffle(x, x, imms), where the inputs are the same (https://source.chromium.org/chromium/chromium/src/+/master:v8/src/wasm/simd-shuffle.h;l=22?q=f:simd-shuffle&ss=chromium%2Fchromium%2Fsrc:v8%2F), and can make use of this to generate better code.

because there's no horizontal add or horizontal multiply and add

I think there is interest in such an instruction, raising a separate issue for this to gauge interest will be good. (I think this was brought up before, but did not get standardized, perhaps I'm misremembering.)

This is super intriguing. What do you mean by this? In my particular case, I'm actually pre-generating the shuffle masks once

Maybe I don't understand your example correctly, say you are using the mask in a hot loop, you can do something like

v128.const 0x00 0xff 0xff 0xff 0x01 0xff 0xff 0xff 0x02 0xff 0xff 0xff 0x03 0xff 0xff 0xff
local.set $mask
loop:
  local.get $input
  local.get $mask
  i8x16.swizzle $input $mask
  do other stuff

which should reduce this generated code to just once, rather than every loop:

0x94a9e81d4e0    c0  48b800ffffff01ffffff REX.W movq rax,0xffffff01ffffff00
0x94a9e81d4ea    ca  c4e1f96ec8     vmovq xmm1,rax
0x94a9e81d4ef    cf  c5fb12c9       vmovddup xmm1,xmm1
0x94a9e81d4f3    d3  48b802ffffff03ffffff REX.W movq rax,0xffffff03ffffff02
0x94a9e81d4fd    dd  c4e3f122c801   vpinsrq xmm1,xmm1,rax,0x1

One thing I'm interested in, but don't know how practical it is, is to update the standard for our shuffle to match the Intel pshufb implementation rather than worrying about adding and saturating.

Interesting idea. We use Tbl for ARM implementation, the logic there is that any index out of range would result in 0. If we opt for pshufb style of top bit set to zero a lane, ARM implementation wouldn't have to change, since top bit set = out of range for an unsigned index. Note that this would be for swizzle only. For shuffle, the lane indices are immediates, which are validated to be in range, so the implementation shouldn't need to do any unnecessary check. (Which is something maybe V8 is doing, I will have to double check this, so thanks for bringing this up.)

@tlively

which is being caused outside of V8 by the LLVM code generation.

I think filing a bug to @tlively would be useful to track this. Maybe somewhere in Emscripten? (this repository has more to do with the specification rather than the implementat/toolchain).

Yeah. That's already been filed, and when it's resolved, it would be equivalent to your v128.local solution you proposed in your second comment -- making this a bit more moot.

Does this [mask regeneration] happen the same way with the shuffle operation or just with swizzle?

This mask regeneration you're seeing is specific to swizzle, and is specifically used to set up a mask (0x7070707070707070) to do saturating addition to deal with pshufb behavior. (We can probably reduce this down to 2 instructions rather than 3).

For shuffle, in general, we have no such mask setup, instead we copy the shuffle immediates into a register, then call pshufb. (https://source.chromium.org/chromium/chromium/src/+/master:v8/src/compiler/backend/x64/code-generator-x64.cc;l=3706;drc=1d85b5f7bd02e59acf890afdf6255fed92b2a701).

We have a special check for shuffle(x, x, imms), where the inputs are the same (https://source.chromium.org/chromium/chromium/src/+/master:v8/src/wasm/simd-shuffle.h;l=22?q=f:simd-shuffle&ss=chromium%2Fchromium%2Fsrc:v8%2F), and can make use of this to generate better code.

Really, this is what I want. If I could use your shuffle with the same vector and get it to zero the lanes, I would be happy. For grins, is it possible for me to get 0xff all the way through to V8 through WASM, or will it get filtered out and check before then?

because there's no horizontal add or horizontal multiply and add

I think there is interest in such an instruction, raising a separate issue for this to gauge interest will be good. (I think this was brought up before, but did not get standardized, perhaps I'm misremembering.)

Yes. I'm following the other ticket #20 and will put together a PR for this when I have a spare moment.

Really, this is what I want. If I could use your shuffle with the same vector and get it to zero the lanes, I would be happy.

No promises here unfortunately, we try to optimize, but get it wrong sometimes, since LLVM does some matching, and V8 does some matching. There have been discussions at length (e.g. #196) about such problems. I am not sure what the current state of that is. Possible thing you can do is:

have a repro
see where the masks get messed up...
a. if the the masks in .wasm is different from the source mask you use, file a bug on Emscripten
b. if the mask you use in the source stays the same as the masks in .wasm, and things run slower than you expected, file a bug on v8.

One thing I'm interested in, but don't know how practical it is, is to update the standard for our shuffle to match the Intel pshufb implementation rather than worrying about adding and saturating.

Interesting idea. We use Tbl for ARM implementation, the logic there is that any index out of range would result in 0. If we opt for pshufb style of top bit set to zero a lane, ARM implementation wouldn't have to change, since top bit set = out of range for an unsigned index. Note that this would be for swizzle only. For shuffle, the lane indices are immediates, which are validated to be in range, so the implementation shouldn't need to do any unnecessary check. (Which is something maybe V8 is doing, I will have to double check this, so thanks for bringing this up.)

You're welcome. If this is viable and acceptable, it would be great.

Since we made an initial decision on this, I will close this issue we can discuss further steps on #389.

Navigation Menu

Repository navigation

Finalizing the instruction set #343

13 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Finalizing the instruction set #343

Description

Activity

lars-t-hansen commented on Sep 11, 2020

tlively commented on Sep 11, 2020

lars-t-hansen commented on Sep 14, 2020

binji commented on Sep 14, 2020

Maratyszcza commented on Sep 18, 2020

penzn commented on Sep 18, 2020

tlively commented on Sep 19, 2020

Maratyszcza commented on Sep 21, 2020

binji commented on Sep 21, 2020

Maratyszcza commented on Sep 21, 2020

binji commented on Sep 21, 2020

tlively commented on Sep 22, 2020

jan-wassenberg commented on Sep 24, 2020

Maratyszcza commented on Oct 3, 2020

jan-wassenberg commented on Oct 4, 2020

13 remaining items

omnisip commented on Oct 5, 2020

penzn commented on Oct 5, 2020

omnisip commented on Oct 5, 2020

tlively commented on Oct 5, 2020

ngzhian commented on Oct 6, 2020

omnisip commented on Oct 6, 2020

omnisip commented on Oct 6, 2020

ngzhian commented on Oct 6, 2020

ngzhian commented on Oct 6, 2020

ngzhian commented on Oct 6, 2020

omnisip commented on Oct 6, 2020

ngzhian commented on Oct 6, 2020

omnisip commented on Oct 6, 2020

tlively commented on Oct 30, 2020

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions