Consider adding Horizontal Add

[dtig]

Packed horizontal arithmetic is reasonably performant on SSE3+ and Neon. These would be useful for complex multiplications, and in the absence of the opcodes below, these would need to be a combination of shifts and adds.

f32x4.addHoriz(x: v128, y:v128) -> v128
i32x4.addHoriz(x: v128, y:v128) -> v128
i16x8.addHoriz(x: v128, y:v128) -> v128

Thoughts on whether horizontal add instructions would be useful to include in the current SIMD spec?

[billbudge]

I'm in favor of this. We've implemented it in the V8 prototype.

[stoklund]

The f64x2 version could be included too. ARMv7 would need to do two scalar additions anyway, and ARMv8/SSE3 have the instruction.

MIPS and POWER do not have these instructions.

[gnzlbg]

@billbudge What semantics does the horizontal have w.r.t. floating-point arithmetic ? Is it ordered (if so, how did you implement it) ? Or does it perform a tree reduction ?

[billbudge]

These are pairwise additions, so for a 4 lane vector type, two source operands would form a single destination vector like this:

[ src0[0] + src0[1], src0[2] + src0[3], src1[0] + src1[1], src1[2] + src1[3] ]

The semantics are that of the vpadd instruction on ARM, and the haddps, phaddw, and phaddd on Intel SSE.

[gnzlbg]

I see. I was expecting the intent of these operations to help with full horizontal reductions (e.g. f32x4.addHoriz(x: v128) -> f32), but yes those are useful as well.

[billbudge]

These can be composed to do the full reductions. The advantage of keeping them primitive (pairwise) is that a compiler will have more opportunity to schedule the instructions. If we expose full reduction opcodes, then a WASM compiler has to generate a sequence of multiple pairwise reductions that stall, since WASM compilers don't necessarily do scheduling and other optimization passes. For example, the anyTrue and allTrue boolean vector opcodes have this problem on some platforms (arm).

[gnzlbg]

These can be composed to do the full reductions.

How? The full reductions performs: src[0] + src[1] + src[2] + src[3]. I don't see a way to emulate this with pairwise reductions.

[billbudge]

Starting with a vector:
[x0, x1, x2, x3]

pairwise reduction with itself:
[x0 + x1, x2 + x3, x0 + x1, x2 + x3]
another pairwise reduction with itself:
[x0 + x1 + x2 + x3, x0 + x1 + x2 + x3, x0 + x1 + x2 + x3, x0 + x1 + x2 + x3] // 4 copies of reduction.

If instead you use a zeroed register as the second source, two pairwise reductions give:

[x0 + x1, x2 + x3, 0, 0]
[x0 + x1 + x2 + x3, 0, 0, 0]

Does that make sense?

[gnzlbg]

Does that make sense?

That assumes that floating-point math is associative, but it isn't, that is: (x0 + x1) + (x2 + x3) != x0 + x1 + x2 + x3.

If the intent of the user is to perform an horizontal ordered reduction of the vector elements "as if it were an array" these operations don't help at all.

[gnzlbg]

FWIW I am not saying that these operations are not useful, I was just wondering what their semantics were, because depending on that they allow some operations or others.

[billbudge]

OK, I see what you're saying. You're correct that floating point operations are not associative. The general intent of SIMD is to give performance improvements for vector operations. If you care about exact math, you'd have to shuffle the data or extract lanes and use scalar operations.

[gnzlbg]

FYI Rust's horizontal SIMD reductions currently specify that they perform tree-reductions, and I was trying to see how to map them to WASM. I think LLVM should be able to map them to the horizontal reductions proposed without issues :)

For exact math we might be adding horizontal reductions of the form f32x4.addHoriz(acc: f32, x: v128) -> f32 in the future since some ISAs have instructions for them (e.g. fadda on ARM), but as you mention these will need to fall back to scalar code in other targets.

[lemaitre]

The main problem I see is that floating point arithmetic is not associative.
So the result will depend on the implementation.

We could have the following:

• f32x4.addHorizOrdered(x: v128) -> f32 which computes x0 + (x1 + (x2 + x3))
• f32x4.addHorizTree(x: v128) -> f32 which computes (x0 + x1) + (x2 + x3)
• f32x4.addHorizUnordered(x: v128) -> f32 where the order of the computation is not specified: implementation defined

It would be conceivable to have all 3 instructions that get converted to the right implementation.
To be remembered that VHADDPS instruction in SSE/AVX is actually slower to compute the full reduction than regular adds and shuffles.

But actually, it would also be tempting to not provide those, and let the compiler applying adds and shuffles to get the right result.
Like this, it will always give the correct result as add is fully determined.

I would say it is fine to have instructions that can give slightly different results on different hardware if they are documented as such, and easy alternatives with fully specified results are also provided.

Also, other reductions might be interesting: min, max, bit_and, bit_or, bit_xor...
If you don't provide any instruction for that, it will be implemented with a bunch of shuffles

[gnzlbg]

Whatever the intrinsics added do, they should specify exactly what they do.

The proposed ones are available in most hardware, and it is rare that hardware has intrinsics to do something else. I think the proposed ones are fine for WebAssembly. If users/compilers want to offer other kinds of reduction intrinsics, they should build them on top of these.

For example, Rust offers portable tree reduction operations, and they could be implemented on top of the intrinsics specified here without issues in a reasonably efficient way.

IMO we should only add more intrinsics for these operations if those become widely available in the hardware that webassembly programs runs on.

[lemaitre]

To be fair, I think we should either put all of them (the tree, the ordered and the unspecified), or none.
Those are easy to write without any specific instruction.

I don't know if this could be easily detected by the VM, but it would also be possible to detect the pattern with shuffles and convert it to the best assembly code possible for the hardware.