使用clang的携带代码生成良好的添加

Question

我正在尝试生成代码(目前使用clang ++ - 3.8),它添加了两个由多个机器字组成的数字.为了简化目前我只添加128位数字,但我希望能够概括这一点.

首先是一些typedef:

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在LO-的话,那么adc在喜字,它只是addS中的喜字,那么addS中的LO-的话,那么做一个adc为零的参数再次喜字.

这可能看起来还不错,但是当你尝试这个具有较大的话(说为192bit,256bit的),你很快就会一团糟orS和对付携带了链中的其他指令,而不是一个简单链add,adc,adc,... .adc.

多精度原语似乎在他们打算做的事情上做得非常糟糕.

所以,我正在寻找的是代码,我可以推广到任意长度(无需这样做,刚好够这样我就可以工作,如何),这铛产生增加在方式与作为它用干高效它内置128位类型(遗憾的是我不能轻易推广).我认为这应该只是一个adcs 链,但我欢迎参数和代码,它应该是别的东西.

Answer 1

有一个固有的做法:_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内在.英特尔针对这些内在函数的文档曾经与编译器生成的程序集不同,但现在看来他们的文档是正确的.但是,Visual Studio中仍只出现生产adcx用_addcarryx_u64而ICC同时生产adcx和adox使用这种内在.但即使ICC产生两个指令,它也不会产生最佳代码(ICC 15),因此仍然需要内联汇编.

就个人而言,我认为C/C++的非标准功能(如内联汇编或内在函数)需要这样做,这是C/C++的一个弱点,但其他人可能不同意.该adc指令自1979年以来一直在x86指令集中.我不会屏住C/C++编译器能够最佳地找出你想要的时间adc.当然它们可以有内置类型,__int128但是当你想要一个不是内置的更大类型时,你必须使用一些非标准的C/C++特性,如内联汇编或内在函数.

就内联汇编代码而言,我已经使用进位标志在多字加法中为寄存器中的8个64位整数发布了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)) 

如果要显式加载内存中的值,可以执行以下操作

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

国际刑事法院大会

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