Inefficient x64 codegen for bitselect

[abrown]

bitselect is a 3-instruction lowering in cranelift and a 4-instruction lowering in v8.

[jan-wassenberg]

I guess the bit-select semantics were chosen because ARM does it that way?
Sure would be nice if this mapped to a single blendv instruction on x86. Have we considered the following semantics which would allow using both VBSL on ARM and blendv on x86?

The input to bitselect should be a "mask" with all bits either zero or 1. That's typically true anyway (result of comparison instruction), and anyone who has a high-bit-only mask (0x8..0) can right-shift to get the all-bits mask.

Given that requirement, x86 blendv does the right thing - checking the upper bit is sufficient. The operation can lower to a single instruction.

[tlively]

@jan-wassenberg If I understand correctly, the proposed semantics is the same as the current bitselect semantics except that it requires that all mask bits for a particular lane have the same value. Is that correct? If so, would a malformed mask result in a trap? I expect having to validate the mask would lead to similarly suboptimal codegen.

[jan-wassenberg]

@tlively Right. I agree validating inside bitselect would be expensive. Is undefined behavior generally unacceptable? If so, we could define a Mask type guaranteed by the compiler to have that property. Comparisons would return that type, and we could provide mask<=>simd128 conversions that do validation.

[abrown]

Let's see if I understand:

• if the mask is static (e.g. from i32x4.const or a special mask instruction?), then a JIT compiler could validate that it is correct before emitting a single blendv
• if the mask is dynamic,
  • it is as the output of a comparison (e.g. i32x4.eq), in which case the JIT compiler could guarantee the mask is well-formed and emit a single blendv
  • or it is coming from some other runtime value in which case the user would need to convert it to a mask using some new instruction (i32x4.to_mask) with an added cost of ? instructions to validate it (what exactly is an invalid instruction? a combination of 0s and 1s in a lane for ARM?)

[tlively]

Yes, WebAssembly cannot have undefined or implementation-defined behavior. Introducing a new mask type could solve the problem, but it would be a large amount of complexity to add to the current proposal. I propose that we keep the current bitselect instruction and defer discussion of a more complex version to a post-MVP SIMD proposal.

[jan-wassenberg]

@abrown Yes, that's what I was thinking. Valid could mean all_true((mask == 0) | mask).

@tlively I totally understand that this would be a large change with relatively low ROI. It's still worth keeping in mind that masks would ideally be a separate type, if long vectors should ever be extended to AVX-512. (There, masks are single-bit, and it would be inefficient to expand them to vectors after every comparison.)

[tlively]

I totally agree that having a separate mask type would make sense in a follow up SIMD proposal 👍

[abrown]

I understand the complexity argument but I think this would be far easier to do now than later. Once the current semantics for bitselect are baked in, we would have to create a new instruction for the semantics @jan-wassenberg described--right? And the accompanying confusion from users of this instruction won't help: "we have two instructions doing almost the same thing but one is more efficient?" I don't see how the masked bitselect can be backwards-compatible in any way that doesn't involve a lot more work than we would have to do now. Why not just do this now, even if it does involve some work?

[tlively]

Because it would be a lot of work and we are trying to get SIMD into the hands of our users soon. Creating a new bitselect instruction in the future will be fine. A precedent for that kind of addition is the nontrapping float-to-int instructions, which were added post-MVP when we realized the MVP trapping float-to-int instructions were not as useful. To be clear, I like this idea and would be happy to do it in the future, but I don't think we should delay shipping MVP SIMD to make this change.

[dtig]

@abrown Having different semantics here that can map to one instruction for bitselect either mean introducing a new separate mask type, or validating the mask. The code sequence here for x64 is fairly straightforward, and in both cases uses 1-cycle instructions (we could optimize V8 codegen here to get rid of the mov), vs. the blend* instructions on many processes take 2-cycles. A non 1-1 mapping on Intel architectures doesn't always mean suboptimal performance. I'm going to agree with @tlively here that I don't think a change is warranted here for the ROI. But if you think that it would be, please follow up with a concrete proposal of what the operation semantics would be, and preferably performance data to warrant the additional work for the change of semantics.

[zeux]

Very often the mask in bitselect comes from a comparison instruction. In this case x64 code generator can elide the extra instructions and just use blendv directly. On SKX blendv is 1 uop and has throughput of 1, vs and/andnot/or sequence that is 3 uops, but each insn has throughput of 3/clock so it's unclear to me which one is faster. Could be worth an experiment on the engine side though, or is it too much work to trace the "origin" of the value that feeds into bitselect? This is loosely equivalent to a separate mask type, but doesn't require spec changes.

[nfrechette]

Even if the instructions dispatch in the same cycle with and/andnot/or, they will not retire in the same cycle due to the dependencies. Depending on the surrounding code, it's possible that they will reorder and the extra latency will not be measurable but they do end up using more registers as well and they do make the function longer. Both of these factors can impact whether a function will be inlined or not.

And/andnot/or often can execute on more pipes than blendv although that isn't always the case. For example, on Ryzen logical operations can use pipe 0, 1, 2, or 3 while blendv can use pipe 0 or 1.

I think any benchmark we can cook up to measure this will be synthetic in nature and might not reflect the real world., There might not be an always optimal choice. IMO either way is fine but if I had to pick one, I would opt for blendv. It's what I use my math lib as well.

[dtig]

@zeux In V8, we could trace the origin, but most Wasm engines by design are more simplistic than that, i.e. the operations are expected to map directly to code generation without the need for more optimizations. Though we could argue that we pattern match for shuffles so we could justify adding more optimizations there. I'm just not sure that this particular case warrants that optimization.

@nfrechette Synthetic benchmarks don't represent real world data, but what I was proposing more is that if there is a need to change the semantics, I think a concrete proposal to prototype/ benchmark is required. I do agree that this particular case performance either way is very application dependent, and either way doesn't necessarily outweigh the other significantly, so I'm unwilling to put in too much effort into this particular operation.

[zeux]

@dtig I guess my point was that I don't think we need to change the wasm spec here since the opportunity for better codegen is left open. If an engine does any sort of stack->SSA conversion then this tracking is probably simple; if an engine doesn't do that it's going to miss out on a lot of other opportunities such as shifts.

[dtig]

@zeux I agree that we don't need a spec change here, but not necessarily for the same reasons. My earlier comment was trying to clarify that there were some speculative spec changes discussed earlier with different performance tradeoffs, and none of those seemed significantly better than the other. It was more of a suggestion for @abrown to have a concrete proposal so we can discuss actual tradeoffs or prototype if necessary.

Re. tracking, I think that we could do it in the future as an additional optimization, but wanted to point out that for wasm in general it's been explicit design choice not to do so, and most engines make the same choice.