带有gcc7.3的__atomic_fetch_or的意外x64程序集

我试图使用64位积分作为位图,并原子地获取/释放各个位的所有权.

为此,我编写了以下无锁代码:

#include 
#include 

static constexpr std::uint64_t NO_INDEX = ~std::uint64_t(0);

class AtomicBitMap {
public:
    static constexpr std::uint64_t occupied() noexcept {
        return ~std::uint64_t(0);
    }

    std::uint64_t acquire() noexcept {
        while (true) {
            auto map = mData.load(std::memory_order_relaxed);
            if (map == occupied()) {
                return NO_INDEX;
            }

            std::uint64_t index = __builtin_ctzl(~map);
            auto previous =
                mData.fetch_or(bit(index), std::memory_order_relaxed);
            if ((previous & bit(index)) == 0) {
                return index;
            }
        }
    }

private:
    static constexpr std::uint64_t bit(std::uint64_t index) noexcept {
        return std::uint64_t(1) <

其中,在godbolt,得到以下组件隔离:

main:
  mov QWORD PTR [rsp-8], 0
  jmp .L3
.L10:
  not rax
  rep bsf rax, rax
  mov edx, eax
  mov eax, eax
  lock bts QWORD PTR [rsp-8], rax
  jnc .L9
.L3:
  mov rax, QWORD PTR [rsp-8]
  cmp rax, -1
  jne .L10
  ret
.L9:
  movsx rax, edx
  ret


这正是我的预期1.

@Jester英勇地设法将我的97行复制器缩减为更简单的44行复制器,我进一步减少到35行:

using u64 = unsigned long long;

struct Bucket {
    u64 mLeaves[16] = {};
};

struct BucketMap {
    u64 acquire() noexcept {
        while (true) {
            u64 map = mData;

            u64 index = (map & 1) ? 1 : 0;
            auto mask = u64(1) <

这会生成以下程序集:

BucketMap::acquireBucket():
  mov r8, rdi
  mov rdx, rsi

.L2:
  mov rax, QWORD PTR [rsi]
  xor eax, eax
  lock bts QWORD PTR [rdx], rax
  setc al
  jc .L2
  mov rdi, r8
  mov ecx, 16
  rep stosq
  mov rax, r8
  ret

main:
  sub rsp, 152
  lea rsi, [rsp+8]
  lea rdi, [rsp+16]
  mov QWORD PTR [rsp+8], 1
  call BucketMap::acquireBucket()
  xor eax, eax
  add rsp, 152
  ret


这xor eax,eax意味着这里的程序集总是试图获得索引0 ...导致无限循环.

我只能看到这个集会的两个解释:


我以某种方式触发了未定义的行为.
gcc中存在代码生成错误.


我已经用尽了所有可以触发UB的想法.

任何人都可以解释为什么gcc会产生这个xor eax,eax？

注意:暂时向gcc报告为https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86314.



使用的编译器版本:

$ gcc --version
gcc (GCC) 7.3.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is 
NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR 
PURPOSE.


编译器标志:

-Wall -Wextra -Werror -Wduplicated-cond -Wnon-virtual-dtor -Wvla 
-rdynamic -Wno-deprecated-declarations -Wno-type-limits 
-Wno-unused-parameter -Wno-unused-local-typedefs -Wno-unused-value 
-Wno-aligned-new -Wno-implicit-fallthrough -Wno-deprecated 
-Wno-noexcept-type -Wno-register -ggdb -fno-strict-aliasing 
-std=c++17 -Wl,--no-undefined -Wno-sign-compare 
-g -O3 -mpopcnt




1  实际上,它比我预期的要好,编译器理解fetch_or(bit(index))后面previous & bit(index)的相当于使用bts和检查CF标志是纯金.


1> Matthieu M...：
这是gcc中的窥孔优化错误,请参阅影响版本7.1,7.2,7.3和8.1的#86413.该修复程序已经存在,将分别在7.4和8.2版本中提供.



简短的回答是特定的代码序列(fetch_or+检查结果)生成setcc(设置条件,也就是基于标志的状态),后跟a movzbl(移动和零扩展); 在7.x中优化被引入,其将一个setcc后跟movzbl成xor接着setcc,然而,这优化缺失导致一些检查xor可能重挫其仍然需要的寄存器(在这种情况下,eax).



更长的答案是,fetch_or可以实现cmpxchg为完全通用性,或者,如果仅设置一个位,则为bts(位测试和设置).作为7.x中引入的另一个优化,gcc现在生成一个bts(gcc 6.4仍然生成一个cmpxchg).bts将进位标志(CF)设置为该位的先前值.

也就是说,auto previous = a.fetch_or(bit); auto n = previous & bit;会产生:


lock bts QWORD PTR [
],  设置该位,并捕获其先前的值,

setc l将低8位设置为rx进位标志(CF)的值,
movzx ex, l将零的高位清零rx.


然后将应用窥视孔优化,这会使事情变得混乱.

gcc trunk现在生成正确的程序集:

BucketMap::acquireBucket():
    mov rdx, rdi
    mov rcx, rsi
.L2:
    mov rax, QWORD PTR [rsi]
    and eax, 1
    lock bts QWORD PTR [rcx], rax
    setc al
    movzx eax, al
    jc .L2
    mov rdi, rdx
    mov ecx, 16
    rep stosq
    mov rax, rdx
    ret
main:
    sub rsp, 152
    lea rsi, [rsp+8]
    lea rdi, [rsp+16]
    mov QWORD PTR [rsp+8], 1
    call BucketMap::acquireBucket()
    xor eax, eax
    add rsp, 152
    ret


虽然不幸的是优化不再适用所以我们留下setc+ mov而不是xor+ setc...但至少它是正确的!