clang: _mm512_reduce_add_ps lowers to LLVM IR that does not reflect correct reduce order

[RalfJung]

This

#include <immintrin.h>
float foo(__m512 x) {
    return _mm512_reduce_add_ps(x);
}

produces

define dso_local noundef float @foo(float vector[16])(<16 x float> noundef %x) local_unnamed_addr #0 {
entry:
  %0 = tail call reassoc noundef float @llvm.vector.reduce.fadd.v16f32(float -0.000000e+00, <16 x float> %x)
  ret float %0
}

According to the LangRef, the reassoc here means that the addition may happen in any order, which is not what Intel documents -- they specify a particular, "tree-like" order.

Even worse, we can chain two of these operations:

#include <immintrin.h>
float foo(__m512 x) {
    float xr = _mm512_reduce_add_ps(x);
    __m512 y = _mm512_set_ps(
        xr, 1.8, 9.3, 0.0, 2.5, 0.0, 6.7, 9.0,
        0.0, 1.8, 9.3, 0.0, 2.5, 0.0, 6.7, 9.0
    );
    return _mm512_reduce_add_ps(y);
}

Now the second addition may be arbitrarily re-associated with the first one. As far as I understand, there's nothing about reassoc that constrains the re-association to only happen "inside" a single operation (and indeed, as a fast-math flag it is explicitly intended to apply when multiple subsequent operations are all reassoc).

_mm512_reduce_add_ps should probably either use a vendor-specific intrinsic, or LLVM IR needs a version of vector.reduce.fadd that explicitly specifies the "tree-like" reduction order documented by Intel.

[llvmbot]

@llvm/issue-subscribers-backend-x86

Author: Ralf Jung (RalfJung)

This ```C #include <immintrin.h> float foo(__m512 x) { return _mm512_reduce_add_ps(x); } ``` [produces](https://godbolt.org/z/qera4378s) ``` define dso_local noundef float @foo(float vector[16])(<16 x float> noundef %x) local_unnamed_addr #0 { entry: %0 = tail call reassoc noundef float @llvm.vector.reduce.fadd.v16f32(float -0.000000e+00, <16 x float> %x) ret float %0 } ``` According to the [LangRef](https://llvm.org/docs/LangRef.html#fast-math-flags), the `reassoc` here means that the addition may happen in *any* order, which is not what [Intel documents](https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=_mm512_reduce_add_ps&expand=133&ig_expand=5303) -- they specify a particular, "tree-like" order.

Even worse, we can chain two of these operations:

#include <immintrin.h>
float foo(__m512 x) {
    float xr = _mm512_reduce_add_ps(x);
    __m512 y = _mm512_set_ps(
        xr, 1.8, 9.3, 0.0, 2.5, 0.0, 6.7, 9.0,
        0.0, 1.8, 9.3, 0.0, 2.5, 0.0, 6.7, 9.0
    );
    return _mm512_reduce_add_ps(y);
}

Now the second addition may be arbitrarily re-associated with the first one. As far as I understand, there's nothing about reassoc that constrains the re-association to only happen "inside" a single operation (and indeed, as a fast-math flag it is explicitly intended to apply when multiple subsequent operations are all reassoc).

_mm512_reduce_add_ps should probably either use a vendor-specific intrinsic, or LLVM IR needs a version of vector.reduce.fadd that explicitly specifies the "tree-like" reduction order documented by Intel.

[anematode]

Presumably this applies to mul as well, and all masked variants thereof.

How about IR intrinsics reduce_tree.(fadd|fmul).v[n]f(16|32|64)? I could see this behavior being useful for other arches in the future, since this is the lowest-latency method of reducing floats. Also, under appropriate fast math flags, reduce_tree could become a plain reduce with reassoc.

Oh, there's also reduce_min and reduce_max intrinsics that I suppose aren't commutative either due to NaN inputs. So that would be 4 new IR intrinsics.

[phoebewang]

Do you get unexpected result against the document? We lower this intrinsic in "tree-like" order in the backend when reassoc is set. So we intended to alwasy generate this flag for _mm512_reduce_add_ps.

[RalfJung]

Do you get unexpected result against the document?

I haven't checked. It doesn't matter. LLVM IR is an abstraction in its own right with its own semantics, and a lot of non-trivial infrastructure relying on those semantics. The clang frontend generates LLVM IR that does not properly capture its intent. It may happen to be the case that the backend currently does the right thing and no optimization pass disturbs these simple examples, but that's a fragile situation to rely on. It's akin to generating LLVM IR with UB and arguing "yeah but current optimizations don't exploit this UB so it's fine".

For instance, an LLVM IR pass could just remove reassoc. That would be an entirely correct transformation according to the LangRef. Just because currently no pass does this, doesn't mean no pass will do it in the future.

[phoebewang]

Do you get unexpected result against the document?

I haven't checked. It doesn't matter. LLVM IR is an abstraction in its own right with its own semantics, and a lot of non-trivial infrastructure relying on those semantics. The clang frontend generates LLVM IR that does not properly capture its intent. It may happen to be the case that the backend currently does the right thing and no optimization pass disturbs these simple examples, but that's a fragile situation to rely on. It's akin to generating LLVM IR with UB and arguing "yeah but current optimizations don't exploit this UB so it's fine".

For instance, an LLVM IR pass could just remove reassoc. That would be an entirely correct transformation according to the LangRef. Just because currently no pass does this, doesn't mean no pass will do it in the future.

The reassoc has special meaning to reduce intrinsics. IIRC, it is intended to indicate backend to choose the best performed lowering. Because different targets have different associative method. A tree-like association performs better on X86 but may not on other targets.

In a word, allowing targets to choose their most efficient lowering with reassoc is one of the design goals of reduce intrinsics. And it is impossible a pass to remove reassoc if we believe passes will never do negative optimization, though we can solve the problem by turning the reassoc flag into a bool parameter of reduce intrinsics if necessary.

[RalfJung]

In a word, allowing targets to choose their most efficient lowering with reassoc is one of the design goals of reduce intrinsics.

We don't want the "most efficient" lowering, we want the exact lowering Intel documents. Maybe that's the same today but who knows what happens in the future. And reassoc doesn't document that it will definitely do any particular lowering.

Your argument also this relies on fast-math passes never using reassoc to actually re-associate multiple of these "reduce" operations, which they would totally be allowed to do.

So, overall it sounds like you are suggesting to overload reassoc to give it a second meaning, quite distinct from the meaning documented in LangRef. Why is that preferable over having a dedicated flag that avoids any confusion due to overloading?

[RKSimon]

Looking back at #46850 when this was last discussed, the Intel docs then described the reduction as a scalar expansion:

float _mm512_reduce_add_ps (__m512 a)

dst[31:0] := 0.0
FOR j := 0 to 15
i := j*32
dst[31:0] := dst[31:0] + a[i+31:i]
ENDFOR

but it now describes it as this which matches the llvm expansion:

DEFINE REDUCE_ADD(src, len) {
	IF len == 2
		RETURN src[31:0] + src[63:32]
	FI
	len := len / 2
	FOR j:= 0 to (len-1)
		i := j*32
		src[i+31:i] := src[i+31:i] + src[i+32*len+31:i+32*len]
	ENDFOR
	RETURN REDUCE_ADD(src[32*len-1:0], len)
}
dst[31:0] := REDUCE_ADD(a, 16)

[RalfJung]

Wait, Intel changed their spec? oO

[RKSimon]

I'm not sure (it was 3 years ago!), I'm going off my comments in the previous issue.