Есть ли что-то особенное в -1 (0xFFFFFFFF) в отношении АЦП? - PullRequest
Новая
       39

Есть ли что-то особенное в -1 (0xFFFFFFFF) в отношении АЦП?

38 голосов
/ 12 мая 2019

В моем исследовательском проекте я пишу код на C ++. Тем не менее, сгенерированная сборка является одним из ключевых моментов проекта. C ++ не обеспечивает прямой доступ к командам, управляющим флагами, в частности, к ADC, но это не должно быть проблемой, если компилятор достаточно умен, чтобы использовать его. Рассмотрим: 

constexpr unsigned X = 0;

unsigned f1(unsigned a, unsigned b) {
    b += a;
    unsigned c = b < a;
    return c + b + X;
}

Переменная c - это обходной путь, чтобы взять меня в руки флаг переноса и добавить его к b и X. Похоже, мне повезло, и сгенерированный код (g++ -O3, версия 9.1) такой: 

f1(unsigned int, unsigned int):
 add %edi,%esi
 mov %esi,%eax
 adc $0x0,%eax
 retq

Для всех значений X, которые я тестировал, код такой же, как указано выше (за исключением, конечно, непосредственного значения $0x0, которое изменяется соответствующим образом). Однако я обнаружил одно исключение: когда X == -1 (или 0xFFFFFFFFu или ~0u, ... это действительно не имеет значения, как вы пишете его), сгенерированный код: 

f1(unsigned int, unsigned int):
 xor %eax,%eax
 add %edi,%esi
 setb %al
 lea -0x1(%rsi,%rax,1),%eax
 retq

Это кажется менее эффективным, чем исходный код, как было предложено косвенными измерениями (хотя и не очень научными). Я прав? Если это так, это ошибка типа "отсутствующая возможность оптимизации", которая стоит сообщить?

Для чего стоит, clang -O3, версия 8.8.0, всегда использует ADC (как я хотел) и icc -O3, версия 19.0.1 никогда не делает.

Я пытался использовать встроенный _addcarry_u32, но это не помогло. 

unsigned f2(unsigned a, unsigned b) {
    b += a;
    unsigned char c = b < a;
    _addcarry_u32(c, b, X, &b);
    return b;
}

Полагаю, я не правильно использовал _addcarry_u32 (я не смог найти много информации об этом). Какой смысл его использовать, так как я должен предоставить флаг переноса? (Снова вводим c и молимся, чтобы компилятор понял ситуацию.)

Я мог бы, на самом деле, правильно его использовать. Для X == 0 Я счастлив: 

f2(unsigned int, unsigned int):
 add %esi,%edi
 mov %edi,%eax
 adc $0x0,%eax
 retq

Для X == -1 Я несчастен: - (

f2(unsigned int, unsigned int):
 add %esi,%edi
 mov $0xffffffff,%eax
 setb %dl
 add $0xff,%dl
 adc %edi,%eax
 retq

Я действительно получаю ADC, но это явно не самый эффективный код. (Что там делает dl? Две инструкции прочитать флаг переноса и восстановить его? Правда? Надеюсь, я очень ошибаюсь!)

1 Ответ

33 голосов
/ 12 мая 2019

mov + adc $-1, %eax более эффективен, чем xor-нулевой + setc + 3-компонентный lea как для задержки, так и для счетчика uop на большинстве процессоров, и не хуже для любых соответствующие процессоры. 1

Это похоже на gcc пропущенную оптимизацию : он, вероятно, видит особый случай и фиксируется на нем, стреляя себе в ногу и предотвращая распознавание паттерна adc.

Я не знаю, что именно он увидел / искал, так что да, вы должны сообщить об этом как об ошибке с пропущенной оптимизацией. Или, если вы хотите копать глубже, вы можете посмотреть результаты GIMPLE или RTL после прохождения оптимизации и посмотреть, что произойдет. Если вы знаете что-нибудь о внутренних представительствах GCC. У Godbolt есть окно дампа дерева GIMPLE, которое вы можете добавить из того же выпадающего меню, что и "клон компилятора".

Тот факт, что clang компилирует его с adc, доказывает, что это законно, т. Е. Требуемый асм соответствует исходному коду C ++, и вы не пропустили какой-то особый случай, мешающий компилятору выполнить эту оптимизацию. (Предполагая, что clang не содержит ошибок, как здесь).

Эта проблема, безусловно, может возникнуть, если вы не будете осторожны, например, Попытка написать функцию общего вида adc, которая принимает перенос и обеспечивает перенос из сложения с 3 входами, трудна в C, потому что любое из двух дополнений может выполнять, поэтому вы не можете просто использовать sum < a+b идиома после добавления переноса к одному из входов. Я не уверен, что можно заставить gcc или clang испускать add/adc/adc, где середина adc должна взять перенос и произвести вынос.

например. 0xff...ff + 1 оборачивается до 0, поэтому sum = a+b+carry_in / carry_out = sum < a не может оптимизироваться до adc, поскольку ему необходимо игнорировать перенос в специальном случае, где a = -1 и carry_in = 1.

Итак, другое предположение, что, возможно, gcc подумал о том, чтобы сделать + X ранее, и выстрелил себе в ногу из-за этого особого случая. Это не имеет большого смысла, хотя.

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

Вы используете _addcarry_u32 правильно.

Смысл его существования в том, чтобы позволить вам выразить добавление с помощью переноса в , а также переноса out , что сложно в чистом C. GCC и clang не оптимизируют это хорошо, часто не просто сохраняя результат переноса в CF.

Если вы хотите только вынос, вы можете предоставить 0 в качестве переноса, и он будет оптимизирован до add вместо adc, но все равно даст вам выноску как переменную C.

например. чтобы добавить два 128-битных целых числа в 32-битные порции, вы можете сделать это 

// bad on x86-64 because it doesn't optimize the same as 2x _addcary_u64
// even though __restrict guarantees non-overlap.
void adc_128bit(unsigned *__restrict dst, const unsigned *__restrict src)
{
    unsigned char carry;
    carry = _addcarry_u32(0, dst[0], src[0], &dst[0]);
    carry = _addcarry_u32(carry, dst[1], src[1], &dst[1]);
    carry = _addcarry_u32(carry, dst[2], src[2], &dst[2]);
    carry = _addcarry_u32(carry, dst[3], src[3], &dst[3]);
}

( На Годболте с GCC / clang / ICC )

Это очень неэффективно по сравнению с unsigned __int128, где компиляторы просто использовали бы 64-битный add / adc, но заставляют clang и ICC выдавать цепочку add / adc / adc / adc. GCC делает беспорядок, используя setcc для хранения CF в целое число для некоторых шагов, затем add dl, -1, чтобы вернуть его в CF для adc.

GCC, к сожалению, отстой в расширенной точности / большойинтеграции, написанной на чистом C. Clang иногда работает немного лучше, но большинство компиляторов в этом плохи Вот почему функции самого низкого уровня gmplib написаны от руки в asm для большинства архитектур.

Сноска 1 : или для количества мопов: равно Intel Haswell и более ранним, где adc равно 2 моп, за исключением немедленного нуля, когда особый случай декодеров семейства Sandybridge равен 1 моп.

Но 3-компонентный LEA с base + index + disp делает его инструкцией с 3-тактным временем ожидания для процессоров Intel, так что это определенно хуже.

В Intel Broadwell и более поздних версиях adc - это команда с 1 моп, даже с ненулевым моментом, использующая поддержку мопов с 3 входами, представленную в Haswell для FMA.

Таким образом, равное общее количество мопов, но худшая задержка означает, что adc все равно будет лучшим выбором.

https://agner.org/optimize/

...