Создание хорошего дополнения с кодом переноса из Clang

Для этого есть неотъемлемая часть: _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");
}