Добавление нескольких слов с использованием флага переноса
GCC имеет 128-битные целые числа. Используя их, я могу заставить компилятор использовать инструкции mul (или imul только с одним операндом). Например
uint64_t x,y;
unsigned __in128 z = (unsigned __int128)x*y;
создает mul. Я использовал это для создания функции 128x128 до 256 (см. Конец этого вопроса перед обновлением для кода, если вам это интересно).
Теперь я хочу сделать 256-битное дополнение, и я не нашел способ заставить компилятор использовать ADC, кроме как с помощью сборки. Я мог бы использовать ассемблер, но я хочу встроенные функции для повышения эффективности. Компилятор уже создает эффективную функцию от 128x128 до 256 (по причине, которую я объяснял в начале этого вопроса), поэтому я не понимаю, почему я должен переписать это в сборке (или любые другие функции, которые компилятор уже реализует эффективно).
Вот встроенная функция сборки, с которой я пришел:
#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))
(вероятно, не каждый выход нуждается в модификаторе раннего clobber но я получаю неправильный результат, по крайней мере, за последние два)
И вот функция, которая делает то же самое в C
void add256(int256 *x, int256 *y) {
uint64_t t1, t2;
t1 = x->x1; x->x1 += y->x1;
t2 = x->x2; x->x2 += y->x2 + ((x->x1) < t1);
t1 = x->x3; x->x3 += y->x3 + ((x->x2) < t2);
x->x4 += y->x4 + ((x->x3) < t1);
}
Зачем нужна сборка? Почему компилятор не компилирует функцию add256 для использования флагов переноса? Есть ли способ заставить компилятор сделать это (например, могу ли я изменить add256, чтобы он это сделал)? Что делать для компилятора, который не поддерживает встроенную сборку (написать все функции в сборке?) Почему для этого не существует?
Вот функция 128x128 до 256
void muldwu128(int256 *w, uint128 u, uint128 v) {
uint128 t;
uint64_t u0, u1, v0, v1, k, w1, w2, w3;
u0 = u >> 64L;
u1 = u;
v0 = v >> 64L;
v1 = v;
t = (uint128)u1*v1;
w3 = t;
k = t >> 64L;
t = (uint128)u0*v1 + k;
w2 = t;
w1 = t >> 64L;
t = (uint128)u1*v0 + w2;
k = t >> 64L;
w->hi = (uint128)u0*v0 + w1 + k;
w->lo = (t << 64L) + w3;
}
Определяет тип:
typedef __int128 int128;
typedef unsigned __int128 uint128;
typedef union {
struct {
uint64_t x1;
uint64_t x2;
int64_t x3;
int64_t x4;
};
struct {
uint128 lo;
int128 hi;
};
} int256;
Update:
Мой вопрос в основном дублирует эти вопросы:
У Intel есть хорошая статья (Новая инструкция по поддержке большой целочисленной арифметики), в которой обсуждается большая целочисленная арифметика и три новые инструкции MULX, ADCX, ADOX, Они пишут:
внутренние определения мульки, adcx и adox также будут интегрированы в компиляторы. Это первый пример инструкции типа "добавить с переносом", реализуемой с помощью. встроенные функции Внутренняя поддержка позволит пользователям реализовать большие целочисленная арифметика с использованием языков программирования более высокого уровня, таких как C/С++.
Внутренние функции
unsigned __int64 umul128(unsigned __int64 a, unsigned __int64 b, unsigned __int64 * hi);
unsigned char _addcarry_u64(unsigned char c_in, unsigned __int64 a, unsigned __int64 b, unsigned __int64 *out);
unsigned char _addcarryx_u64(unsigned char c_in, unsigned __int64 a, unsigned __int64 b, unsigned __int64 *out);
Кстати, MSVC уже имеет _umul128 собственный. Таким образом, хотя MSVC не имеет __int128, встроенный _umul128 может быть использован для генерации mul и, следовательно, умножения на 128 бит.
Инструктаж MULX доступен с BMI2 в Хасуэлле. Для процессоров Broadwell доступны инструкции ADCX и ADOX. Слишком плохо, что для ADC, который был доступен с 8086 в 1979 году, не существует. Это решит проблему встроенной сборки.
Изменить: на самом деле __int128 будет использовать MULX, если BMI2 определен (например, с помощью -mbmi2 или - march=haswell).
Edit:
Я попробовал добавить Clang с несущими носителями, как предложено Lưu Vĩnh Phúc
void add256(int256 *x, int256 *y) {
unsigned long long carryin=0, carryout;
x->x1 = __builtin_addcll(x->x1, y->x1, carryin, &carryout); carryin = carryout;
x->x2 = __builtin_addcll(x->x2, y->x2, carryin, &carryout); carryin = carryout;
x->x3 = __builtin_addcll(x->x3, y->x3, carryin, &carryout); carryin = carryout;
x->x4 = __builtin_addcll(x->x4, y->x4, carryin, &carryout);
}
но это не сгенерировано ADC, и это сложнее, чем я ожидаю.
Ответы
Ответ 1
Я нашел решение с ICC 13.0.01, используя встроенный _addcarry_u64
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);
}
производит
L__routine_start_add256_0:
add256:
xorl %r9d, %r9d #25.9
movq (%rsi), %rax #22.9
addq %rax, (%rdi) #22.9
movq 8(%rsi), %rdx #23.9
adcq %rdx, 8(%rdi) #23.9
movq 16(%rsi), %rcx #24.9
adcq %rcx, 16(%rdi) #24.9
movq 24(%rsi), %r8 #25.9
adcq %r8, 24(%rdi) #25.9
setb %r9b #25.9
ret #26.1
Я скомпилирован с -O3. Я не знаю, как включить adx с ICC. Может быть, мне нужен ICC 14?
Точно 1 addq и три adcq, как я ожидаю.
С помощью Clang результат с использованием -O3 -madx представляет собой беспорядок
add256(uint256*, uint256*): # @add256(uint256*, uint256*)
movq (%rsi), %rax
xorl %ecx, %ecx
xorl %edx, %edx
addb $-1, %dl
adcq %rax, (%rdi)
addb $-1, %cl
movq (%rdi), %rcx
adcxq %rax, %rcx
setb %al
movq 8(%rsi), %rcx
movb %al, %dl
addb $-1, %dl
adcq %rcx, 8(%rdi)
addb $-1, %al
movq 8(%rdi), %rax
adcxq %rcx, %rax
setb %al
movq 16(%rsi), %rcx
movb %al, %dl
addb $-1, %dl
adcq %rcx, 16(%rdi)
addb $-1, %al
movq 16(%rdi), %rax
adcxq %rcx, %rax
setb %al
movq 24(%rsi), %rcx
addb $-1, %al
adcq %rcx, 24(%rdi)
retq
Без включения -madx в Clang результат не намного лучше.
Изменить:
У MSVC уже есть _addcarry_u64. Я попробовал это, и это было так же хорошо, как ICC (1x add и 3x adc).
