Я пытаюсь создать код (в настоящее время использующий 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-битный), вы скоро получите беспорядок or
s и другие инструкции, касающиеся цепочки, вместо простой цепочки add
, adc
, adc
… adc
,
Примитивы с множественной точностью, кажется, делают ужасную работу именно в том смысле, для чего они предназначены.
Итак, я ищу код, который я мог бы обобщить на любую длину (нет необходимости делать это, просто достаточно, чтобы я мог понять, как это сделать), и этот clang создает дополнения таким же эффективным образом, как и то, что он делает с он построен на 128-битном типе (который, к сожалению, я не могу легко обобщить). Я полагаю, что это просто цепочка adc
s, но я приветствую аргументы и код, что это должно быть что-то еще.
Для этого есть неотъемлемая часть: _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 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
…
На 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