8

我正在尝试为 GCC 编写内联 x86-64 程序集以有效地使用 MULQ 指令。MULQ 将 64 位寄存器 RAX 与另一个 64 位值相乘。另一个值可以是任何 64 位寄存器（甚至是 RAX）或内存中的值。MULQ 将乘积的高 64 位放入 RDX，将低 64 位放入 RAX。

现在，很容易将正确的 mulq 表达为内联汇编：

#include <stdint.h>
static inline void mulq(uint64_t *high, uint64_t *low, uint64_t x, uint64_t y)
{
    asm ("mulq %[y]" 
          : "=d" (*high), "=a" (*low)
          : "a" (x), [y] "rm" (y)    
        );
}

这段代码是正确的，但不是最优的。MULQ 是可交换的，所以如果y碰巧已经在 RAX 中，那么离开y它所在的位置并进行乘法是正确的。但是 GCC 不知道这一点，所以它会发出额外的指令来将操作数移动到它们预定义的位置。我想告诉 GCC，它可以将任一输入放在任一位置，只要一个以 RAX 结尾并且 MULQ 引用另一个位置。GCC 对此有一个语法，称为“多重替代约束”。请注意逗号（但整个 asm() 已损坏；见下文）：

asm ("mulq %[y]" 
      : "=d,d" (*high), "=a,a" (*low)
      : "a,rm" (x), [y] "rm,a" (y)    
    );

不幸的是，这是错误的。如果 GCC 选择第二个替代约束，它将发出“mulq %rax”。为了清楚起见，考虑这个函数：

uint64_t f()
{
    uint64_t high, low;
    uint64_t rax;
    asm("or %0,%0": "=a" (rax));
    mulq(&high, &low, 7, rax);
    return high;
}

用 编译gcc -O3 -c -fkeep-inline-functions mulq.c，GCC 发出这个程序集：

0000000000000010 <f>:
  10:   or     %rax,%rax
  13:   mov    $0x7,%edx
  18:   mul    %rax
  1b:   mov    %rdx,%rax
  1e:   retq

“mul %rax”应该是“mul %rdx”。

如何重写这个内联汇编，以便在每种情况下都生成正确的输出？

4

5 回答 5

6

这个 2012 年的问题在 2019 年仍然非常重要。虽然 gcc 发生了变化，并且生成的一些代码在 2012 年并不是最优的，但现在，反过来也成立。

受Whitlock分析的启发，我mulq在 9 种不同的情况下进行了测试，其中每个x和y都是常数 ( 5, 6) 或内存中的值 ( , bar)或 ( , zar) 中的值：raxf1()f2()

uint64_t h1() { uint64_t h, l; mulq(&h, &l,    5,    6); return h + l; }
uint64_t h2() { uint64_t h, l; mulq(&h, &l,    5,  bar); return h + l; }
uint64_t h3() { uint64_t h, l; mulq(&h, &l,    5, f1()); return h + l; }
uint64_t h4() { uint64_t h, l; mulq(&h, &l,  bar,    5); return h + l; }
uint64_t h5() { uint64_t h, l; mulq(&h, &l,  bar,  zar); return h + l; }
uint64_t h6() { uint64_t h, l; mulq(&h, &l,  bar, f1()); return h + l; }
uint64_t h7() { uint64_t h, l; mulq(&h, &l, f1(),    5); return h + l; }
uint64_t h8() { uint64_t h, l; mulq(&h, &l, f1(),  bar); return h + l; }
uint64_t h9() { uint64_t h, l; mulq(&h, &l, f1(), f2()); return h + l; }

我已经测试了 5 个实现：Staufk、Whitlock、Hale、Burdo和我自己的：

inline void mulq(uint64_t *high, uint64_t *low, uint64_t x, uint64_t y) {
    asm("mulq %[y]" : [a]"=a,a"(*low), "=d,d"(*high) : "%a,rm"(x), [y]"rm,a"(y) : "cc");
}

所有实现仍然无法在所有情况下产生最佳代码。虽然其他人无法为h3, h4and生成最佳代码h6，但 Whitlock 和我的仅在以下情况下失败h3：

h3():
 callq 4004d0 <f1()>
 mov %rax,%r8
 mov $0x5,%eax
 mul %r8
 add %rdx,%rax
 retq

在其他条件相同的情况下，可以看出我的比 Whitlock 的简单。使用额外级别的间接并使用 gcc 的内置函数（在 clang 中也可用，但我尚未测试），可以h3通过调用此函数而不是mulq：

inline void mulq_fixed(uint64_t* high, uint64_t* low, uint64_t x, uint64_t y) {
    if (__builtin_constant_p(x))
        mulq(high, low, y, x);
    else
        mulq(high, low, x, y);
}

产量：

h3():
 callq 4004d0 <f1()>
 mov $0x5,%edx
 mul %rdx
 add %rdx,%rax
 retq

使用的想法__builtin_constant_p实际上取自gcc的文档：

模板中无法确定选择了哪个替代方案。但是，您可以使用内置函数（例如 __builtin_constant_p）来包装您的 asm 语句，以获得所需的结果。

在Compiler Explorer中亲自查看。

注意：Whitlock 的实现还有另一个更小的和意想不到的缺点。您需要在Compiler Explorer中检查选项11010 ，否则输出会产生误导，并且 functions , ...,似乎使用了两次指令。这是因为 Compiler Explorer 的解析器没有正确处理汇编器指令//而只是将它们删除，同时显示了两个可能的路径（'s 和's）。或者，您可以取消选中选项.text。h1h9mulq.ifnc.else.endif .if.else

于 2019-07-03T23:30:08.120 回答
4 
__asm__ ("mulq %3" : "=a,a" (*low), "=d,d" (*high) : "%0,0" (x), "r,m" (y))

这类似于您可以在longlong.h各种 GNU 软件包中找到的内容。"r,m"而不是"rm"真的为了clang的利益。如此处所讨论的，多重约束语法对于 clang 似乎仍然很重要。真可惜，但我仍然发现 clang 在约束匹配方面（尤其是在 x86[-86] 上）比 gcc 做得更差。对于 gcc：

__asm__ ("mulq %3" : "=a" (*low), "=d" (*high) : "%0" (x), "rm" (y))

就足够了，并且有利于保留(y)在登记册中，除非登记册压力太大；但在许多情况下，clang似乎总是溢出。我的测试表明它将选择"r"多约束语法中的第一个选项。

"%3"作为指令中的被乘数，允许寄存器（首选）或内存位置，如第三个操作数的别名，相对于零，即(y). "0"别名'第零'操作数：(*low)，它是明确"a"的，即%rax对于64位。中的前导%字符"%0"是交换运算符：也就是说，如果有助于寄存器分配，(x) 可以与 (y) 交换。显然，mulq可交换为：x * y == y * x。

我们实际上在这里受到了很大的限制。mulq将 64 位操作数乘以%3in 的值%rax以产生 128 位乘积：%rdx:%rax. 这"0" (x)意味着(x)必须加载到%rax，并且(y)必须加载到 64 位寄存器或内存地址。但是，%0意味着(x)，并且以下输入(y)可能会通勤。

我还会参考我发现的最实用的内联汇编教程。虽然gcc引用是“权威的”，但它们的教程很差。

感谢Chris发现我原来的约束排序中的错误。

于 2013-04-07T17:05:06.237 回答
3

与关于内联 asm 语法的一般问题不同：

对于 64x64 => 128-bit multiply ，您实际上并不需要内联汇编。
GCC/clang/ICC 知道如何优化a * (unsigned __int128)b到一条mul指令。__int128如果您可以让编译器自己发出漂亮的 asm，那么 在两个 GNU C 扩展（内联 asm 与 https://gcc.gnu.org/wiki/DontUseInlineAsm

unsigned __int128 foo(unsigned long a, unsigned long b) {
    return a * (unsigned __int128)b;
}

在 Godbolt 编译器资源管理器上编译 gcc/clang/ICC 到这个

# gcc9.1 -O3  x86-64 SysV calling convention
foo(unsigned long, unsigned long):
        movq    %rdi, %rax
        mulq    %rsi
        ret                         # with the return value in RDX:RAX

或者返回高半部分

unsigned long umulhi64(unsigned long a, unsigned long b) {
    unsigned __int128 res = a * (unsigned __int128)b;
    return res >> 64;
}

        movq    %rdi, %rax
        mulq    %rsi
        movq    %rdx, %rax
        ret

GCC 完全理解这里发生的事情，这*是可交换的，因此如果它只有一个在寄存器中，而没有另一个，它可以将任一输入用作内存操作数。

不幸的是，根据来自寄存器或内存的某些输入，AFAIK 通常不可能使用不同的 asm 模板。所以完全使用不同的策略（例如直接加载到 SIMD 寄存器而不是做一些整数）是不可能的。

多替代约束的东西非常有限，主要只适用于诸如 之类的指令的内存源版本与内存目标版本add，或类似的东西。

于 2019-07-04T00:52:54.300 回答
2

Brett Hale 的回答在某些情况下会产生次优代码（至少在 GCC 5.4.0 上）。

鉴于：

static inline void mulq(uint64_t *high, uint64_t *low, uint64_t x, uint64_t y) {
    __asm__ ("mulq %3" : "=a" (*low), "=d" (*high) : "%0" (x), "rm" (y) : "cc");
}

uint64_t foo();

然后mulq(&high, &low, foo(), 42)编译为：

    call    foo
    movl    $42, %edx
    mulq    %rdx

…这是最佳的。

但现在颠倒操作数的顺序：

    mulq(&high, &low, 42, foo());

……看看编译后的代码会发生什么：

    call    foo
    movq    %rax, %rdx
    movl    $42, %eax
    mulq    %rdx

哎呀！发生了什么？编译器坚持将 42 放入rax，因此它必须将返回值从foo()中移出rax。显然%（交换）操作数约束是有缺陷的。

有没有办法优化这个？事实证明是有的，虽然有点乱。

static inline void mulq(uint64_t *high, uint64_t *low, uint64_t x, uint64_t y) {
    __asm__ (
        ".ifnc %2,%%rax\n\t"
        "mulq %2\n\t"
        ".else\n\t"
        "mulq %3\n\t"
        ".endif"
        : "=a,a" (*low), "=d,d" (*high)
        : "a,rm" (x), "rm,a" (y)
        : "cc");
}

现在mulq(&high, &low, foo(), 42)编译为：

    call    foo
    movl    $42, %edx
    .ifnc   %rax,%rax
    mulq    %rax
    .else
    mulq    %rdx
    .endif

并mulq(&high, &low, 42, foo())编译为：

    call    foo
    movl    $42, %edx
    .ifnc   %rdx,%rax
    mulq    %rdx
    .else
    mulq    %rax
    .endif

此代码使用汇编程序技巧来解决 GCC 不允许我们根据它选择的约束替代项发出不同的汇编代码的限制。在每种情况下，汇编器将只发出两条可能mulq指令中的一条，具体取决于编译器是否选择了 putx或yin rax。

可悲的是，如果我们将返回值乘以foo()内存位置的值，这个技巧就不是最理想的了：

extern uint64_t bar;

现在mulq(&high, &low, bar, foo())编译为：

    call    foo
    .ifnc bar(%rip),%rax
    mulq bar(%rip)
    .else
    mulq %rax
    .endif

…这是最佳的，但mulq(&high, &low, foo(), bar)编译为：

    movq    bar(%rip), %rbx
    call    foo
    .ifnc   %rax,%rax
    mulq    %rax
    .else
    mulq    %rbx
    .endif

…不必要地复制bar到rbx.

不幸的是，我无法找到一种方法让 GCC 在所有情况下都输出最佳代码。为了调查，强制乘法器成为内存操作数只会导致 GCC 加载bar(%rip)到寄存器中，然后将该寄存器存储到临时堆栈位置，然后将其传递到mulq.

于 2017-01-22T23:14:53.627 回答
0

使用这样的技巧：

void multiply(unsigned& rhi, unsigned& rlo, unsigned a, unsigned b)
{
__asm__(
"    mull  %[b]\n"
:"=d"(rhi),"=a"(rlo)
:"1"(a),[b]"rm"(b));
}

注意"1"输入操作数的参数规范a。这意味着“将'a'放入参数＃1所在的相同位置”。

于 2013-10-05T00:05:22.830 回答