c++ - 使用来自 clang 的进位代码产生良好的添加

Question

我正在尝试生成添加两个由多个机器字组成的数字的代码(当前使用 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，它只是 adds 高字，然后 adds 低字，然后再次对高字执行 adc，参数为零。

这看起来可能还不错，但是当您尝试使用较大的单词(例如 192 位、256 位)时，您很快就会得到一堆 or 和其他处理链上进位的指令，而不是 add、adc、adc、... adc 的简单链。

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

所以我正在寻找的是可以概括为任何长度的代码(无需这样做，就足以让我弄清楚如何去做)，clang 以一种与它内置 128 位类型(不幸的是我不能轻易概括)。我认为这应该只是一个 adc 链，但我欢迎参数和代码，它应该是别的东西。

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 内在函数访问它们。英特尔对这些内在函数的文档曾经是 different then the assembly produced by the compiler，但现在看来他们的文档是正确的。但是，Visual Studio 似乎仍然只使用 _addcarryx_u64 生成 adcx 而 ICC 使用此内在函数生成 adcx 和 adox .但即使 ICC 生成了两条指令，它也不会生成最佳代码 (ICC 15)，因此仍然需要内联汇编。

就个人而言，我认为需要 C/C++ 的非标准特性(例如内联汇编或内在函数)来执行此操作是 C/C++ 的一个弱点，但其他人可能不同意。 adc 指令自 1979 年以来一直在 x86 指令集中。我不会屏住呼吸 C/C++ 编译器能够以最佳方式找出您需要 adc 的时间。当然，它们可以具有内置类型，例如 __int128，但是当您想要一个非内置的更大类型时，您必须使用一些非标准的 C/C++ 功能，例如内联汇编或内在函数。

---

就执行此操作的内联汇编代码而言，我已经在 multi-word addition using the carry flag 的寄存器中发布了 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 之类的汇编程序)方面的经验有限，所以也许有更好的内联汇编解决方案。

---

So what I'm looking for is code that I could generalize to any length

在这里回答这个问题是使用模板元编程的另一种解决方案。 I used this same trick for loop unrolling 。这会产生具有 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);
}

从 ICC 组装

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