Что делает компилятор, который позволяет сравнивать многие значения с несколькими фактическими сравнениями?

Question

Мой вопрос о том, что делает компилятор в этом случае, который оптимизирует код намного больше, чем я думаю, возможно.

При этом перечислении:

enum MyEnum {
    Entry1,
    Entry2,
    ...   // Entry3..27 are the same, omitted for size.
    Entry28,
    Entry29
};

И этой функции:

bool MyFunction(MyEnum e)
{
    if (
    e == MyEnum::Entry1 || 
    e == MyEnum::Entry3 || 
    e == MyEnum::Entry8 || 
    e == MyEnum::Entry14 || 
    e == MyEnum::Entry15 ||
    e == MyEnum::Entry18 ||
    e == MyEnum::Entry21 || 
    e == MyEnum::Entry22 ||
    e == MyEnum::Entry25)
    {
        return true;
    }
    return false;

}

Для функции MSVC генерирует эту сборку при компиляции с флагом оптимизации -Ox ( Godbolt ):

bool MyFunction(MyEnum) PROC                  ; MyFunction
        cmp     ecx, 24
        ja      SHORT $LN5@MyFunction
        mov     eax, 20078725                   ; 01326085H
        bt      eax, ecx
        jae     SHORT $LN5@MyFunction
        mov     al, 1
        ret     0
$LN5@MyFunction:
        xor     al, al
        ret     0

Clang генерирует аналогичную (чуть лучше, на один прыжок меньше) сборку при компиляции с флагом -O3:

MyFunction(MyEnum):                  # @MyFunction(MyEnum)
        cmp     edi, 24
        ja      .LBB0_2
        mov     eax, 20078725
        mov     ecx, edi
        shr     eax, cl
        and     al, 1
        ret
.LBB0_2:
        xor     eax, eax
        ret

Что здесь происходит?Я вижу, что даже если я добавлю больше сравнений перечислений в функцию, генерируемая сборка на самом деле не станет «больше», а изменится только это магическое число (20078725).Это число зависит от того, сколько сравнений перечислений происходит в функции.Я не понимаю, что здесь происходит.

Причина, по которой я смотрю на это, заключается в том, что мне было интересно, хорошо ли написать функцию, как указано выше, или, альтернативно, так, с побитовым сравнением:

bool MyFunction2(MyEnum e)
{
    if (
    e == MyEnum::Entry1 | 
    e == MyEnum::Entry3 |
    e == MyEnum::Entry8 |
    e == MyEnum::Entry14 |
    e == MyEnum::Entry15 |
    e == MyEnum::Entry18 |
    e == MyEnum::Entry21 |
    e == MyEnum::Entry22 |
    e == MyEnum::Entry25)
    {
        return true;
    }
    return false;

}

В результате получается сгенерированная сборка с MSVC:

bool MyFunction2(MyEnum) PROC           ; MyFunction2
        xor     edx, edx
        mov     r9d, 1
        cmp     ecx, 24
        mov     eax, edx
        mov     r8d, edx
        sete    r8b
        cmp     ecx, 21
        sete    al
        or      r8d, eax
        mov     eax, edx
        cmp     ecx, 20
        cmove   r8d, r9d
        cmp     ecx, 17
        sete    al
        or      r8d, eax
        mov     eax, edx
        cmp     ecx, 14
        cmove   r8d, r9d
        cmp     ecx, 13
        sete    al
        or      r8d, eax
        cmp     ecx, 7
        cmove   r8d, r9d
        cmp     ecx, 2
        sete    dl
        or      r8d, edx
        test    ecx, ecx
        cmove   r8d, r9d
        test    r8d, r8d
        setne   al
        ret     0

Поскольку я не понимаю, что происходит в первом случае, я не могу судить, какой из них более эффективен в моем случае.

Answer 1

Довольно умно!Первое сравнение с 24 - это грубая проверка диапазона - если оно больше 24 или меньше 0, оно вылетит;это важно, поскольку следующие инструкции, которые работают с магическим числом, имеют жесткое ограничение на [0, 31] для диапазона операндов.

В остальном, магическое число представляет собой просто битовую маску с битами, соответствующими установленным «хорошим» значениям.

>>> bin(20078725)
'0b1001100100110000010000101'

Легко определить первый и третий биты (считаяот 1 и справа) set, 8th, 14th, 15th, ...

MSVC проверяет его "напрямую", используя инструкцию BT (битовый тест) и переход, clang вместо этого сдвигает его на соответствующую величину (чтобы получить соответствующий бит в позиции самого младшего разряда) и оставить только его И обнулять его (избегая ветвления).

Код C, соответствующий версии clang, будет выглядеть примерно так:

bool MyFunction(MyEnum e) {
    if(unsigned(e) > 24) return false;
    return (20078725 >> e) & 1;
}

Что касается версии MSVC, она больше похожа на

inline bool bit_test(unsigned val, int bit) {
    return val & (1<<bit);
}

bool MyFunction(MyEnum e) {
    if(unsigned(e) > 24) return false;
    return bit_test(20078725, e);
}

(я держал разделенную функцию bit_test, чтобы подчеркнуть, что это на самом деле одна инструкция в сборке, что вещь val & (1<<bit) не соответствуетисходная сборка.

---

Что касается кода на основе if, то он довольно плохой - он использует много CMOV и OR вместе, что является более длинным кодом и, вероятно, сериализуется.выполнение.Я подозреваю, что соответствующий код лязг будет лучше.OTOH, вы написали этот код, используя побитовое ИЛИ (|) вместо более семантически правильного логического ИЛИ (||), и компилятор строго следует вашим указаниям (типично для MSVC).

Другая возможностьпопытка взамен могла бы быть switch - но я не думаю, что можно что-то выиграть по сравнению с кодом, уже сгенерированным для первого фрагмента, который выглядит довольно хорошо для меня.

---

Хорошо, выполняя быстрый тест со всеми версиями для всех компиляторов , мы можем видеть, что:

• перевод C на выходе CLangприведенный выше результат приводит к тому, что во всех компиляторах один и тот же код (= к выходу clang) в значительной степени одинаков;аналогично для перевода MSVC:
• побитовая версия или версия совпадает с логической или версией (= хорошая) как в CLang, так и в gcc;
• в целом, gcc делает по существу то же самое, что иCLang, за исключением случая switch;
• switch результаты варьируются:
  • CLang работает лучше всего, генерируя точно такой же код;
  • генерирует как gcc, так и MSVCкод на основе таблицы переходов, который в этом случае менее хорош;однако:
    • gcc предпочитает генерировать таблицу QWORD, размер торговли для простоты кода настройки;
    • MSVC вместо этого генерирует таблицу байтов, оплачивая ее размером кода установки;Я не мог заставить gcc выдавать похожий код, даже меняя -O3 на -Os (оптимизировать по размеру).

Answer 2

Ах, старый трюк с непосредственным растровым изображением.

GCC делает это тоже, по крайней мере, для коммутатора. x86 asm casetable реализация .К сожалению, в некоторых случаях GCC9 имеет регрессию: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91026#c3;GCC8 и более ранние версии работают лучше.

Еще один пример его использования, на этот раз для code-golf (наименьшее количество байтов кода, в данном случае машинный код x86) для обнаружения определенных букв: Испытание признательности пользователя# 1: Деннис ♦

---

Основная идея состоит в том, чтобы использовать входные данные в качестве индекса в растровом изображении результатов true / false.

FirstВы должны проверить диапазон, потому что растровое изображение имеет фиксированную ширину, а сдвиги x86 оборачивают счетчик сдвигов.Мы не хотим, чтобы высокие значения входили в диапазон, где есть некоторые, которые должны возвращать true.cmp edi, 24 / ja выполняет.

(Если диапазон между самым низким и самым высоким значениями true был, например, от 120 до 140, он мог бы начинаться с sub edi,120 для изменения диапазонавсе до cmp.)

Затем вы используете bitmap & (1<<e) ( bt инструкция ) или (bitmap >> e) & 1 (shr / and) для проверкибит в битовой карте, который сообщает вам, должно ли значение e возвращать значение true или false.

Существует много способов реализовать эту проверку, логически эквивалентные, но с различиями в производительности.

---

Если бы диапазон был шире 32, ему пришлось бы использовать 64-битный размер операнда.Если он шире 64, компилятор может вообще не пытаться выполнить эту оптимизацию.Или все еще может сделать это для некоторых условий, которые находятся в узком диапазоне.

Использование еще большего растрового изображения (в памяти .rodata) было бы возможно, но, вероятно, не то, что большинство компиляторов придумает для вас.Либо с bt [mem],reg (неэффективно), либо вручную индексируем слово и проверяем, что таким же образом этот код проверяет непосредственную битовую карту.Если у вас было много диапазонов с высокой энтропией, возможно, стоит проверить 2x 64-битную непосредственную битовую карту, ветвящуюся или без ветвлений ...

Clang / LLVM предлагает другие приемы для эффективного сравнения снесколько значений (когда не имеет значения, какое из них ударили), например, передать значение в регистр SIMD и использовать упакованное сравнение.Это не зависит от значений, находящихся в плотном диапазоне.( Clang генерирует худший код для 7 сравнений, чем для 8 сравнений )

, который оптимизирует код намного больше, чем я думаю, возможно.

Эти виды оптимизации происходят от умных разработчиков-компиляторов, которые замечают общие шаблоны в исходном коде и думают о разумных способах их реализации.Затем заставьте компиляторы распознавать эти шаблоны и преобразовать их внутреннее представление логики программы, чтобы использовать хитрость.

Оказывается, что операторы switch и switch-like if() являются общими, а агрессивные оптимизации - обычными.

Компиляторы далеки от совершенства, но иногда они действительно приближаются к тому, что люди часто утверждают;Эти компиляторы оптимизируют ваш код для вас, чтобы вы могли писать его понятным для человека способом и при этом выполнять его почти оптимально.Иногда это справедливо для малого масштаба.

---

Поскольку я не понимаю, что происходит в первом случае, я не могу судить, какой из них более эффективен в моем случае.

Непосредственное растровое изображение значительно более эффективно .Нет доступа к памяти данных ни в одном из них, поэтому нет ошибок загрузки кэша.Единственная «дорогая» инструкция - это смещение с переменным счетом (3 моп на основной платформе Intel, из-за надоедливой семантики установки FLAGS в x86; BMI2 shrx - только 1 моп и избегать mov числа до ecx.) https://agner.org/optimize. И другие ссылки на анализ производительности см. В https://stackoverflow.com/tags/x86/info.

* 1.083 * Каждая инструкция в цепочке cmp / cmov не менее 1 моп, и через каждую cmov имеется довольно длинная цепочка зависимостей, потому что MSVC не удосужился разбить ее на 2 или более параллельных цепочек.Но, несмотря на то, что это просто много мопов, гораздо больше, чем у растровой версии, тем хуже для пропускной способности (способность exec-of-order exec перекрывать работу с окружающим кодом), а также задержки.

bt также дешево: 1 моп на современных AMD и Intel.(bts, btr, btc - 2 на AMD, еще 1 на Intel).

Ветвь в версии с непосредственным растровым изображением могла быть setna / and, чтобы сделатьон без ветвей, но специально для этого определения перечисления компилятор ожидал, что он будет в диапазоне.Это могло бы повысить предсказуемость ветвления, потребовав только e <= 31, а не e <= 24.

Так как enum поднимается только до 29, а IIRC его UB имеет значения enum вне диапазона, онможет на самом деле полностью его оптимизировать.

Даже если ветвь e>24 не очень хорошо предсказывает, она все же, вероятно, в целом лучше.Учитывая текущие компиляторы, мы получаем выбор только между цепями cmp / cmov или branch + bitmap.Если не превратить логику asm обратно в C, чтобы ручные компиляторы превратили asm, который мы хотим, тогда мы можем получить без ветвления с помощью AND или CMOV, чтобы сделать его всегда нулевым для вне диапазона e.

Но если нам повезет, оптимизация на основе профиля может позволить некоторым компиляторам выполнять проверку диапазона растровых изображений без ветвей.(В asm поведение shl reg, cl с cl> 31 или 63 четко определено: на x86 он просто маскирует счет. В эквиваленте C вы можете использовать bitmap >> (e&31), который все еще может оптимизироваться до shr; компиляторыЗнайте, что x86 shr маскирует счет, чтобы они могли его оптимизировать. Но не для других ISA, которые насыщают счетчик сдвига ...)

---

Есть много способов реализовать проверку битовых карт, которые довольномного эквивалента.Например, вы могли бы даже использовать выход CF shr, установленный в соответствии с последним сдвинутым битом.По крайней мере, если вы заранее убедитесь, что CF имеет известное состояние для случая cl=0.

Если вы хотите получить целочисленный результат bool, смещение вправо кажется более целесообразным, чем bt /setcc, , но с shr стоимостью 3 моп на Intel, на самом деле может быть лучше использовать bt reg,reg / setc al. Особенно, если вам нужен только bool, и вы можете использовать EAX какваше растровое назначение, поэтому предыдущее значение EAX определенно готово до setcc.(Избегая ложной зависимости от некоторой несвязанной более ранней цепочки деп.)

Кстати, MSVC имеет другие глупости: as Каков наилучший способ установить регистр в ноль в сборке x86: xor, mov или и? объясняет, xor al,al совершенно глупо по сравнению с xor eax,eax, когда вы хотите обнулить AL.Если вам не нужно оставлять старшие байты RAX неизмененными, обнулите полный регистр идиомой обнуления.

И, разумеется, ветвление только для возврата 0 или возврата 1 не имеет особого смысла, если только вы этого не ожидаете.быть очень предсказуемым и хотеть сломать зависимость данных.Я ожидаю, что setc al будет иметь больше смысла, чтобы прочитать результат CF bt