我正在试着生成代码(目前使用clang++-3.8),将两个由多个机器字组成的数字相加。为了简化起见,我现在只添加128位数字,但我希望能够概括这一点。
首先是一些类型定义:
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
和其他处理进位的指令,而不是一个简单的add
,adc
,adc
,... adc
的链。
多精度基元似乎做了一个可怕的工作,正是他们打算做的。
所以我要找的是我可以归纳为任意长度的代码(不需要这样做,只是足够让我能想出如何),哪个clang产生加法的方式是一样有效的,因为它是在128位类型内置(不幸的是,我不能很容易地概括)。我假设这应该只是一个adc
的链,但我欢迎参数和代码,它应该是其他的东西。
4条答案
按热度按时间c90pui9n1#
There is an intrinsic to do this: _addcarry_u64. However, only Visual Studio and ICC (at least VS 2013 and 2015 and ICC 13 and ICC 15) do this efficiently. Clang 3.7 and GCC 5.2 still don't produce efficient code with this intrinsic.
Clang in addition has a built-in which one would think does this,
__builtin_addcll
, but it does not produce efficient code either.The reason Visual Studio does this is that it does not allow inline assembly in 64-bit mode so the compiler should provide a way to do this with an intrinsic (though Microsoft took their time implementing this).
Therefore, with Visual Studio use
_addcarry_u64
. With ICC use_addcarry_u64
or inline assembly. With Clang and GCC use inline assembly.Note that since the Broadwell microarchitecture there are two new instructions:
adcx
andadox
which you can access with the _addcarryx_u64 intrinsic . Intel's documentation for these intrinsics used to be different then the assembly produced by the compiler but it appears their documentation is correct now. However, Visual Studio still only appears to produceadcx
with_addcarryx_u64
whereas ICC produces bothadcx
andadox
with this intrinsic. But even though ICC produces both instructions it does not produce the most optimal code (ICC 15) and so inline assembly is still necessary.Personally, I think the fact that a non-standard feature of C/C++, such as inline assembly or intrinsics, is required to do this is a weakness of C/C++ but others might disagree. The
adc
instruction has been in the x86 instruction set since 1979. I would not hold my breath on C/C++ compilers being able to optimally figure out when you wantadc
. Sure they can have built-in types such as__int128
but the moment you want a larger type that's not built-in you have to use some non-standard C/C++ feature such as inline assembly or intrinsics.In terms of inline assembly code to do this I already posted a solution for 256-bit addition for eight 64-bit integers in register at multi-word addition using the carry flag .
Here is that code reposted.
If you want to explicitly load the values from memory you can do something like this
That produces nearlly identical assembly as from the following function in ICC
I have limited experience with GCC inline assembly (or inline assembly in general - I usually use an assembler such as NASM) so maybe there are better inline assembly solutions.
So what I'm looking for is code that I could generalize to any length
To answer this question here is another solution using template meta programming. I used this same trick for loop unrolling. This produces optimal code with ICC. If Clang or GCC ever implement
_addcarry_u64
efficiently this would be a good general solution.Assembly from ICC
Meta programming is a basic feature of assemblers so it's too bad C and C++ (except through template meta programming hacks) have no solution for this either (the D language does).
The inline assembly I used above which referenced memory was causing some problems in a function. Here is a new version which seems to work better
cld4siwp2#
在叮当6,两个
__builtin_addcl
和__builtin_add_overflow
produce the same, optimal disassembly。两者的装配:
pdtvr36n3#
从clang 5.0开始,可以使用
__uint128_t
-加法并通过移位获得进位位来获得良好的结果:在许多情况下,clang仍然会执行奇怪的操作(我假设是因为可能的别名?),但通常将一个变量复制到临时变量中会有所帮助。
使用示例
手动使用:
通用解决方案:
Godbolt Link:上面的所有示例都只编译为
mov
、add
和adc
指令(从clang 5.0开始,且至少为-O2)。这些例子不能用gcc(最高8.1,目前是godbolt的最高版本)生成好的代码,而且我还没有设法得到任何可用的
__builtin_addcll
......rbpvctlc4#
使用
__builtin_addcll
的代码在Clang 10版本中进行了全面优化,适用于至少3个链(这要求adc
具有可变的进位输入,也会产生进位输出)。Godbolt展示了Clang 9在这种情况下将setc/movzx弄得一团糟。Clang 6和之后的代码可以很好地处理2个链的情况,如@zneak的答案所示,其中不需要从
adc
进行进位。没有内建的惯用代码也很好。而且,它在每个编译器中都能工作,并且也被GCC 5+完全优化为2的链(
add
/adc
,没有使用adc
的进位输出)。编写正确的C来在有进位输入时生成进位输出是很棘手的,所以这不容易扩展。https://godbolt.org/z/ThxGj1WGK