Неожиданная сборка x64 для __atomic_fetch_or с gcc 7.3

Ответ 1

Это ошибка оптимизации peephole в gcc, см. # 86413, затрагивающие версии 7.1, 7.2, 7.3 и 8.1. Исправление уже включено и будет доставлено соответственно в версии 7.4 и 8.2.

Короткий ответ заключается в том, что конкретная последовательность кода (результат проверки fetch_or +) генерирует setcc (устанавливается условное, aka на основе состояния флагов), за которым следует 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; auto previous = a.fetch_or(bit); auto n = previous & bit; будет генерировать:

• lock bts QWORD PTR [<address of a>], <bit index> чтобы установить бит и записать его предыдущее значение,
• setc <n>l чтобы установить нижние 8 бит r<n>x в значение флага переноса (CF),
• movzx e<n>x, <n>l для нулевых верхних бит r<n>x.

И тогда будет применена оптимизация глазок, которая все испортит.

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... но по крайней мере это правильно!

Ответ 2

В качестве побочной заметки вы можете найти самый низкий бит 0 бит с прямой манипуляцией бит:

template<class T>
T find_lowest_0_bit_mask(T value) {
    T t = value + 1;
    return (t ^ value) & t;
}

Возвращает битовую маску, а не бит.

Предсказания: T должен быть без знака, value должно содержать не менее 1 бит нуля.

mData.load должен синхронизироваться с mData.fetch_or, поэтому он должен быть

mData.load(std::memory_order_acquire)

а также

mData.fetch_or(..., std::memory_order_release)

И, ИМО, есть что-то в этих бит-атаках, которые заставляют его генерировать неправильную сборку с помощью clang, см. .LBB0_5 который явно ошибочен, потому что он продолжает пытаться установить один и тот же бит, а не перерасчитывать другой бит для установки. Версия, которая генерирует правильную сборку:

#include <cstdint>
#include <atomic>

static constexpr int NO_INDEX = -1;

template<class T>
T find_lowest_0_bit_mask(T value) {
    T t = value + 1;
    return (t ^ value) & t;
}

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

    int acquire() noexcept {
        auto map = mData.load(std::memory_order_acquire);
        while(map != occupied()) {
            std::uint64_t mask = find_lowest_0_bit_mask(map);
            if(mData.compare_exchange_weak(map, map | mask, std::memory_order_release))
                return __builtin_ffsl(mask) - 1;
        }
        return NO_INDEX;
    }

    void release(int i) noexcept {
        mData.fetch_and(~bit(i), std::memory_order_release);
    }

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

    std::atomic_uint64_t mData{ 0 };
};

Ответ 3

xor-zero/set flags/setcc как правило, лучший способ создать 32-разрядное целое число 0/1.

Очевидно, что это безопасно, только если у вас есть запасной регистр на xor -zero, не уничтожая никаких входов в инструкции по установке флага, так что это довольно явно ошибка.

(В противном случае вы можете setcc dl/movzx eax,dl. Предпочтительны отдельные регистры, поэтому movzx может быть нулевой латентностью (mov-elim) на некоторых процессорах, но на критическом пути на других ЦП, так что xor/set-flags/setcc идиома предпочтительнее, поскольку меньшее количество инструкций находится на критическом пути.)

IDK, почему gcc создает целочисленное значение (previous & mask) == 0 в регистре вообще; что, вероятно, часть ошибки.