Создание хорошего дополнения с кодом переноса из Clang
Я пытаюсь создать код (в настоящее время использующий clang++-3.8), который добавляет два числа, состоящие из нескольких машинных слов. Для упрощения на данный момент я добавляю только 128-битные числа, но я бы хотел обобщить это.
Сначала несколько typedefs:
typedef unsigned long long unsigned_word;
typedef __uint128_t unsigned_128;
И тип "результат":
struct Result
{
unsigned_word lo;
unsigned_word hi;
};
Первая функция, f, берет две пары слов без знака и возвращает результат, в качестве промежуточного шага, помещая оба этих 64-битных слова в 128-битное слово перед их добавлением, вот так:
Result f (unsigned_word lo1, unsigned_word hi1, unsigned_word lo2, unsigned_word hi2)
{
Result x;
unsigned_128 n1 = lo1 + (static_cast<unsigned_128>(hi1) << 64);
unsigned_128 n2 = lo2 + (static_cast<unsigned_128>(hi2) << 64);
unsigned_128 r1 = n1 + n2;
x.lo = r1 & ((static_cast<unsigned_128>(1) << 64) - 1);
x.hi = r1 >> 64;
return x;
}
Это на самом деле очень удобно, например:
movq 8(%rsp), %rsi
movq (%rsp), %rbx
addq 24(%rsp), %rsi
adcq 16(%rsp), %rbx
Теперь вместо этого я написал более простую функцию с использованием примитивов clang с множественной точностью, как показано ниже:
static Result g (unsigned_word lo1, unsigned_word hi1, unsigned_word lo2, unsigned_word hi2)
{
Result x;
unsigned_word carryout;
x.lo = __builtin_addcll(lo1, lo2, 0, &carryout);
x.hi = __builtin_addcll(hi1, hi2, carryout, &x.carry);
return x;
}
Это производит следующую сборку:
movq 24(%rsp), %rsi
movq (%rsp), %rbx
addq 16(%rsp), %rbx
addq 8(%rsp), %rsi
adcq $0, %rbx
В этом случае есть дополнительное дополнение. Вместо того, чтобы делать обычные add на словах, то adc на словах, это просто addПривет, тогда addС логи слова, то делает adc на привет слово снова с аргументом нуля.
Это может показаться не слишком плохим, но когда вы попробуете это с большими словами (скажем, 192-битный, 256-битный), вы скоро получите беспорядок ors и другие инструкции, касающиеся цепочки, вместо простой цепочки add, adc, adc... adc,
Примитивы с множественной точностью, кажется, делают ужасную работу именно в том смысле, для чего они предназначены.
Итак, я ищу код, который я мог бы обобщить на любую длину (нет необходимости делать это, просто достаточно, чтобы я мог понять, как это сделать), и этот clang производит дополнения таким же образом, как и то, что он делает с он построен на 128-битном типе (который, к сожалению, я не могу легко обобщить). Я полагаю, что это просто цепочка adcs, но я приветствую аргументы и код, что это должно быть что-то еще.
4 ответа
Для этого есть встроенная функция: _addcarry_u64. Однако только Visual Studio и ICC (по крайней мере VS 2013 и 2015 и ICC 13 и ICC 15) делают это эффективно. Clang 3.7 и GCC 5.2 до сих пор не производят эффективный код с этим свойством.
Кроме того, в Clang есть встроенный модуль, __builtin_addcll, но он также не производит эффективного кода.
Причина, по которой Visual Studio делает это, заключается в том, что она не допускает встроенную сборку в 64-битном режиме, поэтому компилятор должен предоставить способ сделать это встроенным (хотя Microsoft не торопилась с реализацией этого).
Поэтому с использованием Visual Studio _addcarry_u64, С использованием ICC _addcarry_u64 или встроенная сборка. С Clang и GCC используйте встроенную сборку.
Обратите внимание, что после микроархитектуры Broadwell появились две новые инструкции: adcx а также adox который вы можете получить с помощью встроенного _addcarryx_u64. Документация Intel для этих встроенных компонентов раньше отличалась от сборки, созданной компилятором, но, похоже, их документация сейчас верна. Тем не менее, Visual Studio все еще только производит adcx с _addcarryx_u64 в то время как ICC производит оба adcx а также adox с этим присущим. Но даже несмотря на то, что ICC выдает обе инструкции, он не выдает наиболее оптимальный код (ICC 15), поэтому встроенная сборка все еще необходима.
Лично я считаю, что тот факт, что для этого требуется нестандартная функция C/C++, такая как встроенная сборка или встроенные функции, является слабостью C/C++, но другие могут не согласиться. adc инструкция находится в наборе команд x86 с 1979 года. Я бы не стал останавливаться на том, что компиляторы C / C++ способны оптимально вычислять, когда вы хотите adc, Конечно, они могут иметь встроенные типы, такие как __int128 но в тот момент, когда вам нужен не встроенный больший тип, вам придется использовать некоторые нестандартные функции C/C++, такие как встроенная сборка или встроенные функции.
С точки зрения встроенного кода ассемблера, чтобы сделать это, я уже опубликовал решение для 256-битного сложения для восьми 64-битных целых чисел в регистре при сложении нескольких слов с использованием флага переноса.
Вот этот код сохранил.
#define ADD256(X1, X2, X3, X4, Y1, Y2, Y3, Y4) \
__asm__ __volatile__ ( \
"addq %[v1], %[u1] \n" \
"adcq %[v2], %[u2] \n" \
"adcq %[v3], %[u3] \n" \
"adcq %[v4], %[u4] \n" \
: [u1] "+&r" (X1), [u2] "+&r" (X2), [u3] "+&r" (X3), [u4] "+&r" (X4) \
: [v1] "r" (Y1), [v2] "r" (Y2), [v3] "r" (Y3), [v4] "r" (Y4))
Если вы хотите явно загрузить значения из памяти, вы можете сделать что-то вроде этого
//uint64_t dst[4] = {1,1,1,1};
//uint64_t src[4] = {1,2,3,4};
asm (
"movq (%[in]), %%rax\n"
"addq %%rax, %[out]\n"
"movq 8(%[in]), %%rax\n"
"adcq %%rax, 8%[out]\n"
"movq 16(%[in]), %%rax\n"
"adcq %%rax, 16%[out]\n"
"movq 24(%[in]), %%rax\n"
"adcq %%rax, 24%[out]\n"
: [out] "=m" (dst)
: [in]"r" (src)
: "%rax"
);
Это дает почти идентичную сборку из следующей функции в ICC
void add256(uint256 *x, uint256 *y) {
unsigned char c = 0;
c = _addcarry_u64(c, x->x1, y->x1, &x->x1);
c = _addcarry_u64(c, x->x2, y->x2, &x->x2);
c = _addcarry_u64(c, x->x3, y->x3, &x->x3);
_addcarry_u64(c, x->x4, y->x4, &x->x4);
}
У меня ограниченный опыт работы со встроенной сборкой GCC (или встроенной сборкой в целом - я обычно использую ассемблер, такой как NASM), так что, возможно, есть лучшие решения для встроенной сборки.
Так что я ищу код, который я мог бы обобщить на любую длину
Чтобы ответить на этот вопрос, вот еще одно решение с использованием шаблонного метапрограммирования. Я использовал этот же трюк для раскручивания петли. Это дает оптимальный код с ICC. Если Clang или GCC когда-либо внедрить _addcarry_u64 эффективно это было бы хорошим общим решением.
#include <x86intrin.h>
#include <inttypes.h>
#define LEN 4 // N = N*64-bit add e.g. 4=256-bit add, 3=192-bit add, ...
static unsigned char c = 0;
template<int START, int N>
struct Repeat {
static void add (uint64_t *x, uint64_t *y) {
c = _addcarry_u64(c, x[START], y[START], &x[START]);
Repeat<START+1, N>::add(x,y);
}
};
template<int N>
struct Repeat<LEN, N> {
static void add (uint64_t *x, uint64_t *y) {}
};
void sum_unroll(uint64_t *x, uint64_t *y) {
Repeat<0,LEN>::add(x,y);
}
Ассамблея от ICC
xorl %r10d, %r10d #12.13
movzbl c(%rip), %eax #12.13
cmpl %eax, %r10d #12.13
movq (%rsi), %rdx #12.13
adcq %rdx, (%rdi) #12.13
movq 8(%rsi), %rcx #12.13
adcq %rcx, 8(%rdi) #12.13
movq 16(%rsi), %r8 #12.13
adcq %r8, 16(%rdi) #12.13
movq 24(%rsi), %r9 #12.13
adcq %r9, 24(%rdi) #12.13
setb %r10b
Мета-программирование - это базовая особенность ассемблеров, поэтому очень плохо, что C и C++ (кроме как через мета-программирование на основе шаблонов) также не имеют решения для этого (язык D делает это).
Встроенная сборка, которую я использовал выше, которая ссылалась на память, вызывала некоторые проблемы в функции. Вот новая версия, которая, кажется, работает лучше
void foo(uint64_t *dst, uint64_t *src)
{
__asm (
"movq (%[in]), %%rax\n"
"addq %%rax, (%[out])\n"
"movq 8(%[in]), %%rax\n"
"adcq %%rax, 8(%[out])\n"
"movq 16(%[in]), %%rax\n"
"addq %%rax, 16(%[out])\n"
"movq 24(%[in]), %%rax\n"
"adcq %%rax, 24(%[out])\n"
:
: [in] "r" (src), [out] "r" (dst)
: "%rax"
);
}
На Clang 6 оба __builtin_addcl а также __builtin_add_overflow произвести такую же, оптимальную разборку.
Result g(unsigned_word lo1, unsigned_word hi1, unsigned_word lo2, unsigned_word hi2)
{
Result x;
unsigned_word carryout;
x.lo = __builtin_addcll(lo1, lo2, 0, &carryout);
x.hi = __builtin_addcll(hi1, hi2, carryout, &carryout);
return x;
}
Result h(unsigned_word lo1, unsigned_word hi1, unsigned_word lo2, unsigned_word hi2)
{
Result x;
unsigned_word carryout;
carryout = __builtin_add_overflow(lo1, lo2, &x.lo);
carryout = __builtin_add_overflow(hi1, carryout, &hi1);
__builtin_add_overflow(hi1, hi2, &x.hi);
return x;
}
Сборка для обоих:
add rdi, rdx
adc rsi, rcx
mov rax, rdi
mov rdx, rsi
ret
Начиная с clang 5.0 можно получить хорошие результаты, используя __uint128_t-добавление и получение переноса путем сдвига:
inline uint64_t add_with_carry(uint64_t &a, const uint64_t &b, const uint64_t &c)
{
__uint128_t s = __uint128_t(a) + b + c;
a = s;
return s >> 64;
}
Во многих ситуациях clang по-прежнему выполняет странные операции (я полагаю, из-за возможного алиасинга?), Но обычно копирует одну переменную во временную подсказку.
Примеры использования с
template<int size> struct LongInt
{
uint64_t data[size];
};
Ручное использование:
void test(LongInt<3> &a, const LongInt<3> &b_)
{
const LongInt<3> b = b_; // need to copy b_ into local temporary
uint64_t c0 = add_with_carry(a.data[0], b.data[0], 0);
uint64_t c1 = add_with_carry(a.data[1], b.data[1], c0);
uint64_t c2 = add_with_carry(a.data[2], b.data[2], c1);
}
Общее решение:
template<int size>
void addTo(LongInt<size> &a, const LongInt<size> b)
{
__uint128_t c = __uint128_t(a.data[0]) + b.data[0];
for(int i=1; i<size; ++i)
{
c = __uint128_t(a.data[i]) + b.data[i] + (c >> 64);
a.data[i] = c;
}
}
Godbolt Link: все приведенные выше примеры собраны только для mov, add а также adc инструкции (начиная с clang 5.0 и, по крайней мере, -O2).
Примеры не дают хорошего кода с gcc (до 8.1, который на данный момент является самой высокой версией на Годболте). И мне пока не удалось получить ничего полезного с __builtin_addcll...
Код, использующий__builtin_addcllполностью оптимизирован Clang, начиная с версии 10, для цепочек не менее 3 (для которых требуется переменный перенос, который также производит перенос). Godbolt показывает, как clang 9 испортил setc/movzx для этого случая.
Clang 6 и более поздние версии хорошо справляются с этим для гораздо более простого случая цепочек из 2, как показано в ответе @zneak, где перенос из an не требуется.
Идиоматический код без встроенных функций тоже хорош. Более того, он работает во всех компиляторах, а также полностью оптимизирован GCC 5+ для цепочек из 2 (add/, без использования выноса изadc). Сложно написать правильный C, который генерирует перенос, когда есть перенос, поэтому его нелегко расширить.
Result h (unsigned_word lo1, unsigned_word hi1, unsigned_word lo2, unsigned_word hi2)
{
unsigned_word lo = lo1 + lo2;
bool carry = lo < lo1;
unsigned_word hi = hi1 + hi2 + carry;
return Result{lo, hi};
}