Я пытаюсь создать код (в настоящее время использующий 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 multi-precision, как показано ниже:
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
на lo-словах, тогда adc
на hi-словах, это просто add
hi-слова, тогда add
lo-слова, то делает adc
на привет-слово снова с аргументом нуля.
Это может показаться не слишком плохим, но если вы попробуете это с более крупными словами (скажем, 192 бит, 256 бит), вы скоро получите беспорядок or
и другие инструкции, связанные с переносом цепи, вместо простой цепи add
, adc
, adc
,... adc
.
Многоточечные примитивы, похоже, делают ужасную работу именно в том, что они намерены делать.
Итак, я ищу код, который я мог бы обобщить до какой-либо длины (не нужно делать это, достаточно, чтобы я мог разобраться, как это сделать), который clang производит дополнения с таким же эффектом, как и то, что он делает с ним встроенный 128-битный тип (который, к сожалению, я не могу легко обобщить). Я предполагаю, что это должна быть целая цепочка adc
s, но я могу аргументировать и код, что это должно быть что-то еще.