Simd: Shifts amount - should they be masked/modulo?

[ngzhian]

In https://github.com/WebAssembly/simd/blob/master/proposals/simd/SIMD.md#bit-shifts
It is mentioned that "Only the low bits of the shift amount are used", this is not consistent with the behavior of some instructions operating on packed integers.
E.g. for x64's psrlw/psrld [0], if the shift count is > lane bits, the lane is set to all 0s
so (int32) 1 << 32 = 0 according to psrld, but 1 according to the spec.

For arm, the shifts amount is the lower byte of the register, so (int32) 1 << 32 = 0.

Should we clarify the spec to follow this behavior?

[0] https://www.felixcloutier.com/x86/psrlw:psrld:psrlq

[penzn]

Good find! I don't know why this interpretation was chosen to be frank, and search through history and issues does not bring anything useful either. @arunetm, @PeterJensen, @dtig, do you recall why effective shift amount is mod lane size? Does that help with a particular usage pattern?

[tlively]

I assume this was chosen for consistency with the MVP scalar shift instructions: https://webassembly.github.io/spec/core/exec/numerics.html#op-ishl.

[ngzhian]

Could be something to do with the way scalar shifts are defined in https://webassembly.github.io/spec/core/exec/numerics.html#op-ishl
The language used there is "Let k be i2 modulo N"

For scalar operations, modulo N maps down well to scalar shift instructions [0], which masks the count range.

[0] https://www.felixcloutier.com/x86/sal:sar:shl:shr

[dtig]

I think this was just ported over from the main Wasm overview document when it was initially written, we are now running into inconsistencies with tests on the tools and V8, because they both do different things. The tools strictly follow the overview document, whereas V8 uses the hardware instructions that @ngzhian linked, and Sshl, Vshl on ARM. My intuition is that we should closely follow the hardware, but in the case that they do subtly different things, it's not clear what that behavior should be.

[penzn]

The only upside of being consistent with scalar instructions that I can think of is that it would be easier to express shifts in tools (compilers), but as that is not an issue for native shifts it might be not be an issue here as well.

My back of the envelope calculation for the cost of emulating the current semantics is two extra instructions on x86. Haven't done it for Arm, but suspect something similar.

[ngzhian]

Here's some more interesting stuff:
On Arm, the sshl and vshl (register) instructions take the lower byte, thus, if you try to shift by an amount larger than the lane:

[1,1,1,1] << 33 (0x21)
  = [0, 0, 0, 0] (overflows and only takes lower 32bits)

But if you go bigger:

[1,1,1,1] << 256 (0x100)
  = [1,1,1,1] << 0
  = [1,1,1,1]

[dtig]

Two instructions is correct, but it seems wasteful to add them unless applications explicitly rely on these semantics, which seems unlikely to me.

[penzn]

@dtig, I agree.

@ngzhian ouch, that mean that the instruction still would require masking on either of the platforms. I think it would still be two extra instructions for either of the architectures.

[AndrewScheidecker]

FWIW, shifts by a constant amount are very common, and the mask should be trivial to fold with the constant in that case.

[dtig]

For the constant case, the mask even though trivial may not be necessary because the immediate versions of the instructions mask by default on all (most?) platforms.

[penzn]

To my best knowledge shift amount for the instructions in this proposal are variable.

For a shift by immediate, x86 defines immediate as 'imm8', which might take larger values than number of bits in the lane, but at any rate immediate shift can be folded with a mask in code generator.

[dtig]

The shift amount for instructions are variable, but engines can very easily optimize for the case that these are constants, I think that is the case @AndrewScheidecker is referrring to, please correct if I'm mistaken.

On Intel platforms, the immediate is indeed an imm8, but if the value specified by the immediate is larger than S.LaneBits, the destination operand is set to all 0s for the logical shifts, so masking may not be necessary depending on the semantics we decide to keep.

[sunfishcode]

As @ngzhian points out, the ARM behavior is to wrap the count at 256, which is different from other architectures, which means the choices seem to be:

• pick ARM semantics, and emulate it everywhere else
• pick something else, and emulate it on ARM
• nondeterministically let platforms pick

I'd like to make a case against nondeterminism here: even though naive programs are unlikely to notice, SIMD programs are frequently aggressively optimized. People will be looking for ways to squeeze out instructions. The most reliable way to prevent this from leading to programs that don't run on some hardware architectures is to make it deterministic.

Wrapping at the lane width is consistent with the scalar opcodes, and it's fairly cheap to implement on any SIMD instruction set, regardless of what kind of shifts it has, because it's at most just a mask on the shift count. And as @AndrewScheidecker points out, in the very common case of constant shift counts, the masking can be folded away to have no overhead at runtime.

[penzn]

As @ngzhian points out, the ARM behavior is to wrap the count at 256, which is different from other architectures, which means the choices seem to be:

• pick ARM semantics, and emulate it everywhere else
• pick something else, and emulate it on ARM
• nondeterministically let platforms pick

The current semantics (outside of those three) can be a compromise, in my opinion, -- there seem to be the same overhead everywhere, plus it is consistent with the scalar instruction set.

[dtig]

Agree that nondeterministically letting platforms pick is not a good option.

My concern with the current semantics is that they don't match any hardware, so it doesn't seem great to introduce a fixed overhead across the board that can't be optimized away, especially where it may not be necessary. But given that the overhead is an and instruction everywhere, I'm okay with defaulting to wrapping at the lane width. Are there any objections to this?