使用进位标志添加多字

Question

GCC具有128位整数.使用这些我可以让编译器使用mul(或imul只有一个操作数)指令.例如

uint64_t x,y;
unsigned __int128 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)) 

(可能不是每个输出都需要一个早期的修改器但是我得到了错误的结果,至少没有最后两个)

这是一个在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;

更新:

我的问题主要是这些问题的重复:

1. 得到-GCC使用的携带的逻辑换任意精度算术-而不列直插组件
2. 高效-128位加成使用进位标志
3. multiword-addition-in-c.

英特尔有一篇很好的文章(新指令支持大整数运算),它讨论了大整数运算和三条新指令MULX,ADCX,ADOX.他们写:

mulx,adcx和adox的内在定义也将集成到编译器中.这是使用内在函数实现的"add with carry"类型指令的第一个示例.内在支持将使用户能够使用更高级别的编程语言(如C/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指令自Haswell的BMI2开始提供.这些ADCX和ADOX说明适用于Broadwell处理器.太糟糕了ADC,自1979年8086以来,没有内在的可用性.这将解决内联装配问题.

编辑:如果定义了BMI2,实际上_addcarry_u64将使用_addcarryx(例如使用setc或 - __int128).

编辑:

我按照LưuVĩnhPhúc的建议尝试了Clang的附加内置装置

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);  
}

但这并没有产生mulx,而且比我预期的要复杂得多.

Answer 1

我使用_addcarry_u64内在的ICC 13.0.01 找到了一个解决方案

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。我不知道如何启用adxICC。也许我需要 ICC 14？

这正是我所期望的 1addq和 3 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

如果不在 Clang 中启用，-madx结果也好不了多少。

编辑： 显然 MSVC 已经有了_addcarry_u64. 我尝试了一下，它和 ICC 一样好（1xadd和 3x adc）。