[Bug libstdc++/115454] New: std::experimental::find_last_set is buggy on x86-64-v4

[Bug libstdc++/115454] New: std::experimental::find_last_set is buggy on x86-64-v4

[lee.imple at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115454

            Bug ID: 115454
           Summary: std::experimental::find_last_set is buggy on x86-64-v4
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: lee.imple at gmail dot com
  Target Milestone: ---

We are using a simd with 4 uint64_t elements (with `deduce_t`) on x86-64-v4.
We are trying to find the last element with the value -1 (i.e. all 1s).

The code is as following (available at https://godbolt.org/z/3f1nszf8E ),
compiled with the options `-O3 -march=x86-64-v4 -std=c++20`.

```c++
#include <experimental/simd>
#include <cstdint>

using deduce_t_element = std::experimental::simd<
    std::uint64_t,
    std::experimental::simd_abi::deduce_t<std::uint64_t, 4>
>;
using fixed_size_element = std::experimental::simd<
    std::uint64_t,
    std::experimental::simd_abi::fixed_size<4>
>;

int f_deduce(deduce_t_element e) {
    return find_last_set(e != -1);
}

int f_fixed_size(fixed_size_element e) {
    return find_last_set(e != -1);
}
```

G++ trunk gives the following assembly (I add the comments).

```asm
f_deduce(std::experimental::parallelism_v2::simd<unsigned long,
std::experimental::parallelism_v2::simd_abi::_VecBltnBtmsk<32> >):
  vpcmpeqd %ymm1, %ymm1, %ymm1
  movl $-1, %eax
  vpcmpq $4, %ymm1, %ymm0, %k0
  kmovb %k0, %edx
  orb $-16, %dl                # %dl |= 0xf0
  je .L1
  movzbl %dl, %edx             
  movl $31, %eax
  lzcntl %edx, %edx            # leading zeros is 24 
                               # because the next byte is always 0b1111
  subl %edx, %eax              # so we get the result is 31 - 24 = 7
.L1:
  ret
f_fixed_size(std::experimental::parallelism_v2::simd<unsigned long,
std::experimental::parallelism_v2::simd_abi::_Fixed<4> >):
  vpcmpeqd %ymm0, %ymm0, %ymm0
  movl $63, %edx
  vpcmpq $4, (%rdi), %ymm0, %k0
  kmovb %k0, %eax
  andl $15, %eax
  lzcntq %rax, %rax
  subl %eax, %edx
  movl %edx, %eax
  vzeroupper
  ret
```

In fact, the first function always gives the result 7 whatever argument it
gets, which is more obvious from clang++'s result.

```asm
f_deduce(std::experimental::parallelism_v2::simd<unsigned long,
std::experimental::parallelism_v2::simd_abi::_VecBltnBtmsk<32>>): #
@f_deduce(std::experimental::parallelism_v2::simd<unsigned long,
std::experimental::parallelism_v2::simd_abi::_VecBltnBtmsk<32>>)
  movl $7, %eax
  retq
f_fixed_size(std::experimental::parallelism_v2::simd<unsigned long,
std::experimental::parallelism_v2::simd_abi::_Fixed<4>>): #
@f_fixed_size(std::experimental::parallelism_v2::simd<unsigned long,
std::experimental::parallelism_v2::simd_abi::_Fixed<4>>)
  vpcmpeqd %ymm0, %ymm0, %ymm0
  vpcmpeqq (%rdi), %ymm0, %k0
  kmovd %k0, %eax
  xorb $15, %al
  movzbl %al, %eax
  lzcntq %rax, %rcx
  movl $63, %eax
  subl %ecx, %eax
  vzeroupper
  retq
```

I don't know why, but compiled result of `fixed_size_simd` seems to be
different.

[Bug libstdc++/115454] std::experimental::find_last_set is buggy on x86-64-v4

[mkretz at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115454

Matthias Kretz (Vir) <mkretz at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2024-06-13
           Assignee|unassigned at gcc dot gnu.org      |mkretz at gcc dot gnu.org

--- Comment #1 from Matthias Kretz (Vir) <mkretz at gcc dot gnu.org> ---
Confirmed. The != compare returns an 8-bit mask (internally) for a 4-element
simd_mask in
https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/experimental/bits/simd_x86.h;h=4ab933b573c614654902d6f5747d53e39f4b100f;hb=HEAD#l2350.
The high 4 bits are incorrectly set because of the ~ operator on the resulting
mask. Those bits are not cleared before calling std::bit_width - 1, which is
why the result is unconditionally 7.

You can work around the bug by replacing 'e != -1' with '!(e == -1)' for the
time being.

[Bug libstdc++/115454] std::experimental::find_last_set is buggy on x86-64-v4

[mkretz at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115454

--- Comment #2 from Matthias Kretz (Vir) <mkretz at gcc dot gnu.org> ---
Actually, find_last_set needs to clear padding bits as well. This fixes the
issue. Regression tests are running now.


commit b85ff52c1fb059f75bcedf103a15fce9db8bc92b
Author: Matthias Kretz <m.kretz@gsi.de>
Date:   Fri Jun 14 15:11:25 2024 +0200

    libstdc++: Fix find_last_set(simd_mask) to ignore padding bits

    With the change to the AVX512 find_last_set implementation, the change
    to AVX512 operator!= is unnecessary. However, the latter was not
    producing optimal code and unnecessarily set the padding bits. In
    theory, the compiler could determine that with the new !=
    implementation, the bit operation for clearing the padding bits is a
    no-op and can be elided.

    Signed-off-by: Matthias Kretz <m.kretz@gsi.de>

    libstdc++-v3/ChangeLog:

            PR libstdc++/115454
            * include/experimental/bits/simd_x86.h (_S_not_equal_to): Use
            neq comparison instead of bitwise negation after eq.
            (_S_find_last_set): Clear unused high bits before computing
            bit_width.
            * testsuite/experimental/simd/pr115454_find_last_set.cc: New
            test.

diff --git a/libstdc++-v3/include/experimental/bits/simd_x86.h
b/libstdc++-v3/include/experimental/bits/simd_x86.h
index 517c4b4a5be..8a23aa2082b 100644
--- a/libstdc++-v3/include/experimental/bits/simd_x86.h
+++ b/libstdc++-v3/include/experimental/bits/simd_x86.h
@@ -2339,29 +2339,29 @@ _S_not_equal_to(_SimdWrapper<_Tp, _Np> __x,
_SimdWrapper<_Tp, _Np> __y)
                  __assert_unreachable<_Tp>();
              }
            else if constexpr (sizeof(__xi) == 64 && sizeof(_Tp) == 8)
-             return ~_mm512_mask_cmpeq_epi64_mask(__k1, __xi, __yi);
+             return _mm512_mask_cmpneq_epi64_mask(__k1, __xi, __yi);
            else if constexpr (sizeof(__xi) == 64 && sizeof(_Tp) == 4)
-             return ~_mm512_mask_cmpeq_epi32_mask(__k1, __xi, __yi);
+             return _mm512_mask_cmpneq_epi32_mask(__k1, __xi, __yi);
            else if constexpr (sizeof(__xi) == 64 && sizeof(_Tp) == 2)
-             return ~_mm512_mask_cmpeq_epi16_mask(__k1, __xi, __yi);
+             return _mm512_mask_cmpneq_epi16_mask(__k1, __xi, __yi);
            else if constexpr (sizeof(__xi) == 64 && sizeof(_Tp) == 1)
-             return ~_mm512_mask_cmpeq_epi8_mask(__k1, __xi, __yi);
+             return _mm512_mask_cmpneq_epi8_mask(__k1, __xi, __yi);
            else if constexpr (sizeof(__xi) == 32 && sizeof(_Tp) == 8)
-             return ~_mm256_mask_cmpeq_epi64_mask(__k1, __xi, __yi);
+             return _mm256_mask_cmpneq_epi64_mask(__k1, __xi, __yi);
            else if constexpr (sizeof(__xi) == 32 && sizeof(_Tp) == 4)
-             return ~_mm256_mask_cmpeq_epi32_mask(__k1, __xi, __yi);
+             return _mm256_mask_cmpneq_epi32_mask(__k1, __xi, __yi);
            else if constexpr (sizeof(__xi) == 32 && sizeof(_Tp) == 2)
-             return ~_mm256_mask_cmpeq_epi16_mask(__k1, __xi, __yi);
+             return _mm256_mask_cmpneq_epi16_mask(__k1, __xi, __yi);
            else if constexpr (sizeof(__xi) == 32 && sizeof(_Tp) == 1)
-             return ~_mm256_mask_cmpeq_epi8_mask(__k1, __xi, __yi);
+             return _mm256_mask_cmpneq_epi8_mask(__k1, __xi, __yi);
            else if constexpr (sizeof(__xi) == 16 && sizeof(_Tp) == 8)
-             return ~_mm_mask_cmpeq_epi64_mask(__k1, __xi, __yi);
+             return _mm_mask_cmpneq_epi64_mask(__k1, __xi, __yi);
            else if constexpr (sizeof(__xi) == 16 && sizeof(_Tp) == 4)
-             return ~_mm_mask_cmpeq_epi32_mask(__k1, __xi, __yi);
+             return _mm_mask_cmpneq_epi32_mask(__k1, __xi, __yi);
            else if constexpr (sizeof(__xi) == 16 && sizeof(_Tp) == 2)
-             return ~_mm_mask_cmpeq_epi16_mask(__k1, __xi, __yi);
+             return _mm_mask_cmpneq_epi16_mask(__k1, __xi, __yi);
            else if constexpr (sizeof(__xi) == 16 && sizeof(_Tp) == 1)
-             return ~_mm_mask_cmpeq_epi8_mask(__k1, __xi, __yi);
+             return _mm_mask_cmpneq_epi8_mask(__k1, __xi, __yi);
            else
              __assert_unreachable<_Tp>();
          }                                                   // }}}
@@ -5292,7 +5292,7 @@ _S_find_first_set(simd_mask<_Tp, _Abi> __k)
       _S_find_last_set(simd_mask<_Tp, _Abi> __k)
       {
        if constexpr (__is_avx512_abi<_Abi>())
-         return std::__bit_width(__k._M_data._M_data) - 1;
+         return std::__bit_width(_Abi::_S_masked(__k._M_data)._M_data) - 1;
        else
          return _Base::_S_find_last_set(__k);
       }
diff --git a/libstdc++-v3/testsuite/experimental/simd/pr115454_find_last_set.cc
b/libstdc++-v3/testsuite/experimental/simd/pr115454_find_last_set.cc
new file mode 100644
index 00000000000..b47f19d3067
--- /dev/null
+++ b/libstdc++-v3/testsuite/experimental/simd/pr115454_find_last_set.cc
@@ -0,0 +1,49 @@
+// { dg-options "-std=gnu++17" }
+// { dg-do run { target *-*-* } }
+// { dg-require-effective-target c++17 }
+// { dg-additional-options "-march=x86-64-v4" { target avx512f } }
+// { dg-require-cmath "" }
+
+#include <experimental/simd>
+
+namespace stdx = std::experimental;
+
+using T = std::uint64_t;
+
+template <typename U, int N>
+using V = stdx::simd<U, stdx::simd_abi::deduce_t<U, N>>;
+
+[[gnu::noinline, gnu::noipa]]
+int reduce(V<T, 4> x)
+{
+  static_assert(stdx::find_last_set(V<T, 4>([](unsigned i) { return i; }) !=
V<T, 4>(0)) == 3);
+  return stdx::find_last_set(x != -1);
+}
+
+[[gnu::noinline, gnu::noipa]]
+int reduce2()
+{
+  using M8 = typename V<short, 8>::mask_type;
+  using M4 = typename V<int, 4>::mask_type;
+  if constexpr (sizeof(M8) == sizeof(M4))
+    {
+      M4 k;
+      __builtin_memcpy(&__data(k), &__data(M8(true)), sizeof(M4));
+      return stdx::find_last_set(k);
+    }
+  return 3;
+}
+
+
+int main()
+{
+  const V<T, 4> x {};
+
+  const int r = reduce(x);
+  if (r != 3)
+      __builtin_abort();
+
+  const int r2 = reduce2();
+  if (r2 != 3)
+      __builtin_abort();
+}

[Bug libstdc++/115454] std::experimental::find_last_set is buggy on x86-64-v4

[mkretz at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115454

Matthias Kretz (Vir) <mkretz at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.5

[Bug libstdc++/115454] std::experimental::find_last_set is buggy on x86-64-v4

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115454

--- Comment #3 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Matthias Kretz <mkretz@gcc.gnu.org>:

https://gcc.gnu.org/g:1340ddea0158de3f49aeb75b4013e5fc313ff6f4

commit r15-1500-g1340ddea0158de3f49aeb75b4013e5fc313ff6f4
Author: Matthias Kretz <m.kretz@gsi.de>
Date:   Fri Jun 14 15:11:25 2024 +0200

    libstdc++: Fix find_last_set(simd_mask) to ignore padding bits

    With the change to the AVX512 find_last_set implementation, the change
    to AVX512 operator!= is unnecessary. However, the latter was not
    producing optimal code and unnecessarily set the padding bits. In
    theory, the compiler could determine that with the new !=
    implementation, the bit operation for clearing the padding bits is a
    no-op and can be elided.

    Signed-off-by: Matthias Kretz <m.kretz@gsi.de>

    libstdc++-v3/ChangeLog:

            PR libstdc++/115454
            * include/experimental/bits/simd_x86.h (_S_not_equal_to): Use
            neq comparison instead of bitwise negation after eq.
            (_S_find_last_set): Clear unused high bits before computing
            bit_width.
            * testsuite/experimental/simd/pr115454_find_last_set.cc: New
            test.

[Bug libstdc++/115454] std::experimental::find_last_set is buggy on x86-64-v4

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115454

--- Comment #4 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-14 branch has been updated by Matthias Kretz
<mkretz@gcc.gnu.org>:

https://gcc.gnu.org/g:e77f314ccd422ffa05c6c06837e2cb94c25f2bba

commit r14-10331-ge77f314ccd422ffa05c6c06837e2cb94c25f2bba
Author: Matthias Kretz <m.kretz@gsi.de>
Date:   Fri Jun 14 15:11:25 2024 +0200

    libstdc++: Fix find_last_set(simd_mask) to ignore padding bits

    With the change to the AVX512 find_last_set implementation, the change
    to AVX512 operator!= is unnecessary. However, the latter was not
    producing optimal code and unnecessarily set the padding bits. In
    theory, the compiler could determine that with the new !=
    implementation, the bit operation for clearing the padding bits is a
    no-op and can be elided.

    Signed-off-by: Matthias Kretz <m.kretz@gsi.de>

    libstdc++-v3/ChangeLog:

            PR libstdc++/115454
            * include/experimental/bits/simd_x86.h (_S_not_equal_to): Use
            neq comparison instead of bitwise negation after eq.
            (_S_find_last_set): Clear unused high bits before computing
            bit_width.
            * testsuite/experimental/simd/pr115454_find_last_set.cc: New
            test.

    (cherry picked from commit 1340ddea0158de3f49aeb75b4013e5fc313ff6f4)

[Bug libstdc++/115454] std::experimental::find_last_set is buggy on x86-64-v4

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115454

--- Comment #5 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Matthias Kretz
<mkretz@gcc.gnu.org>:

https://gcc.gnu.org/g:a0b92a530ad61389c0cdeb8d8ece4677e019c28e

commit r11-11517-ga0b92a530ad61389c0cdeb8d8ece4677e019c28e
Author: Matthias Kretz <m.kretz@gsi.de>
Date:   Fri Jun 14 15:11:25 2024 +0200

    libstdc++: Fix find_last_set(simd_mask) to ignore padding bits

    With the change to the AVX512 find_last_set implementation, the change
    to AVX512 operator!= is unnecessary. However, the latter was not
    producing optimal code and unnecessarily set the padding bits. In
    theory, the compiler could determine that with the new !=
    implementation, the bit operation for clearing the padding bits is a
    no-op and can be elided.

    Signed-off-by: Matthias Kretz <m.kretz@gsi.de>

    libstdc++-v3/ChangeLog:

            PR libstdc++/115454
            * include/experimental/bits/simd_x86.h (_S_not_equal_to): Use
            neq comparison instead of bitwise negation after eq.
            (_S_find_last_set): Clear unused high bits before computing
            bit_width.
            * testsuite/experimental/simd/pr115454_find_last_set.cc: New
            test.

    (cherry picked from commit 4787960dcaf0de3f46464960f5246de9b3c69a06)

[Bug libstdc++/115454] std::experimental::find_last_set is buggy on x86-64-v4

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115454

--- Comment #6 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Matthias Kretz
<mkretz@gcc.gnu.org>:

https://gcc.gnu.org/g:fbd088a069b172cae4e268abe2d38e567ef97990

commit r13-8861-gfbd088a069b172cae4e268abe2d38e567ef97990
Author: Matthias Kretz <m.kretz@gsi.de>
Date:   Fri Jun 14 15:11:25 2024 +0200

    libstdc++: Fix find_last_set(simd_mask) to ignore padding bits

    With the change to the AVX512 find_last_set implementation, the change
    to AVX512 operator!= is unnecessary. However, the latter was not
    producing optimal code and unnecessarily set the padding bits. In
    theory, the compiler could determine that with the new !=
    implementation, the bit operation for clearing the padding bits is a
    no-op and can be elided.

    Signed-off-by: Matthias Kretz <m.kretz@gsi.de>

    libstdc++-v3/ChangeLog:

            PR libstdc++/115454
            * include/experimental/bits/simd_x86.h (_S_not_equal_to): Use
            neq comparison instead of bitwise negation after eq.
            (_S_find_last_set): Clear unused high bits before computing
            bit_width.
            * testsuite/experimental/simd/pr115454_find_last_set.cc: New
            test.

    (cherry picked from commit 1340ddea0158de3f49aeb75b4013e5fc313ff6f4)

[Bug libstdc++/115454] std::experimental::find_last_set is buggy on x86-64-v4

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115454

--- Comment #7 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by Matthias Kretz
<mkretz@gcc.gnu.org>:

https://gcc.gnu.org/g:8b5bdeb8aa2c2f6dbd448a8f7d500d9eaece48e1

commit r12-10574-g8b5bdeb8aa2c2f6dbd448a8f7d500d9eaece48e1
Author: Matthias Kretz <m.kretz@gsi.de>
Date:   Fri Jun 14 15:11:25 2024 +0200

    libstdc++: Fix find_last_set(simd_mask) to ignore padding bits

    With the change to the AVX512 find_last_set implementation, the change
    to AVX512 operator!= is unnecessary. However, the latter was not
    producing optimal code and unnecessarily set the padding bits. In
    theory, the compiler could determine that with the new !=
    implementation, the bit operation for clearing the padding bits is a
    no-op and can be elided.

    Signed-off-by: Matthias Kretz <m.kretz@gsi.de>

    libstdc++-v3/ChangeLog:

            PR libstdc++/115454
            * include/experimental/bits/simd_x86.h (_S_not_equal_to): Use
            neq comparison instead of bitwise negation after eq.
            (_S_find_last_set): Clear unused high bits before computing
            bit_width.
            * testsuite/experimental/simd/pr115454_find_last_set.cc: New
            test.

    (cherry picked from commit 1340ddea0158de3f49aeb75b4013e5fc313ff6f4)