Есть ли что-то особенное в -1 (0xFFFFFFFF) в отношении АЦП? - программирование
Подтвердить что ты не робот

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

В моем исследовательском проекте я пишу код 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) g++ -O3:

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

Для всех значений X которые я тестировал, код такой же, как указано выше (за исключением, конечно, непосредственного значения $0x0 которое изменяется соответственно). Однако я обнаружил одно исключение: когда X == -1 (или 0xFFFFFFFFu или ~0u ,... на самом деле не имеет значения, как вы его ~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 там делает? Две инструкции, чтобы прочитать флаг переноса и восстановить его? В самом деле? Я надеюсь, что я очень плохо!)

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

Тот факт, что clang компилирует его с помощью adc доказывает, что он допустим, т.е. Требуемый asm соответствует источнику 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 правильно.

Смысл его существования заключается в том, чтобы позволить вам выражать добавление с переносом, а также выполнением, что сложно в чистом 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, к сожалению, отстой в расширенной точности /biginteger, написанном на чистом C. Clang иногда работает немного лучше, но большинство компиляторов плохо в этом разбираются. Вот почему функции самого низкого уровня gmplib написаны от руки в asm для большинства архитектур.

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

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

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

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

https://agner.org/optimize/