5

我正在尝试做一些代码优化来消除分支,原来的c代码是

if( a < b ) 
   k = (k<<1) + 1;
else
   k = (k<<1)

我打算用如下的汇编代码替换它

mov a, %rax 
mov b, %rbx
mov k, %rcx
xor %rdx %rdx
shl 1, %rcx
cmp %rax, %rax
setb %rdx
add %rdx,%rcx
mov %rcx, k 

所以我像吹一样写c内联汇编代码,

#define next(a, b, k)\
 __asm__("shl $0x1, %0; \
         xor %%rbx, %%rbx; \
         cmp %1, %2; \
         setb %%rbx; \
         addl  %%rbx,%0;":"+c"(k) :"g"(a),"g"(b))

当我编译下面的代码时出现错误:

operand type mismatch for `add'
operand type mismatch for `setb'

我该如何解决?

4

4 回答 4

10

以下是您的代码中的错误:

  1. 错误:'cmp' 的操作数类型不匹配-- CMP的操作数之一必须是寄存器。您可能正在生成试图比较两个立即数的代码。将第二个操作数的约束从"g"更改为"r"。(参见GCC 手册 - 扩展 Asm - 简单约束
  2. 错误:'setb'的操作数类型不匹配——SETB只接受 8 位操作数,即 setb %bl有效而setb %rbx不能。
  3. C 表达式T = (A < B)应转换为cmp B,A; setb TAT&T x86 汇编器语法。CMP的两个操作数顺序错误。请记住,CMP的工作方式与SUB类似。

一旦你意识到前两个错误消息是由汇编器产生的,那么调试它们的技巧就是查看 gcc 生成的汇编器代码。尝试gcc $CFLAGS -S t.c将有问题的行t.sx86 操作码参考进行比较。关注每条指令允许的操作数代码,您将很快发现问题。

在下面发布的固定源代码中,我假设您的操作数是无符号的,因为您使用的是SETB而不是SETL。我从使用RBX切换到RCX来保存临时值,因为RCX是 ABI 中的一个调用 clobbered 寄存器,并使用"=&c"约束将其标记为earlyclobber操作数,因为RCX在输入之前被清除 a并被b读取:

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

static uint64_t next(uint64_t a, uint64_t b, uint64_t k)
{
    uint64_t tmp;
    __asm__("shl $0x1, %[k];"
        "xor %%rcx, %%rcx;"
        "cmp %[b], %[a];"
        "setb %%cl;"
        "addq %%rcx, %[k];"
        : /* outputs */ [k] "+g" (k), [tmp] "=&c" (tmp)
        : /* inputs  */ [a] "r" (a), [b] "g" (b)
        : /* clobbers */ "cc");
    return k;
}

int main()
{
    uint64_t t, t0, k;
    k = next(1, 2, 0);
    printf("%" PRId64 "\n", k);

    scanf("%" SCNd64 "%" SCNd64, &t, &t0);
    k = next(t, t0, k);
    printf("%" PRId64 "\n", k);

    return 0;
}

main()转换为:

<+0>:   push   %rbx
<+1>:   xor    %ebx,%ebx
<+3>:   mov    $0x4006c0,%edi
<+8>:   mov    $0x1,%bl
<+10>:  xor    %eax,%eax
<+12>:  sub    $0x10,%rsp
<+16>:  shl    %rax
<+19>:  xor    %rcx,%rcx
<+22>:  cmp    $0x2,%rbx
<+26>:  setb   %cl
<+29>:  add    %rcx,%rax
<+32>:  mov    %rax,%rbx
<+35>:  mov    %rax,%rsi
<+38>:  xor    %eax,%eax
<+40>:  callq  0x400470 <printf@plt>
<+45>:  lea    0x8(%rsp),%rdx
<+50>:  mov    %rsp,%rsi
<+53>:  mov    $0x4006c5,%edi
<+58>:  xor    %eax,%eax
<+60>:  callq  0x4004a0 <__isoc99_scanf@plt>
<+65>:  mov    (%rsp),%rax
<+69>:  mov    %rbx,%rsi
<+72>:  mov    $0x4006c0,%edi
<+77>:  shl    %rsi
<+80>:  xor    %rcx,%rcx
<+83>:  cmp    0x8(%rsp),%rax
<+88>:  setb   %cl
<+91>:  add    %rcx,%rsi
<+94>:  xor    %eax,%eax
<+96>:  callq  0x400470 <printf@plt>
<+101>: add    $0x10,%rsp
<+105>: xor    %eax,%eax
<+107>: pop    %rbx
<+108>: retq   

您可以在每次调用之前看到next()移入RSI的结果。printf()

于 2012-12-24T17:37:59.727 回答
9

鉴于 gcc(它看起来像 gcc 内联汇编器)产生:

leal    (%rdx,%rdx), %eax
xorl    %edx, %edx
cmpl    %esi, %edi
setl    %dl
addl    %edx, %eax
ret

int f(int a, int b, int k)
{
  if( a < b ) 
    k = (k<<1) + 1;
  else
    k = (k<<1);

  return k;
}

它会认为编写自己的内联汇编程序完全是浪费时间和精力。

与往常一样,在开始编写内联汇编程序之前,请检查编译器的实际作用。如果您的编译器不生成此代码,那么您可能需要将编译器的版本升级到更新的版本(我向 Jan Hubicka [当时 x86-64 的 gcc 维护者] ca 2001 报告了这种事情,并且我敢肯定它在 gcc 中已经存在了一段时间)。

于 2012-12-24T15:36:38.970 回答
8

你可以这样做,编译器不会生成分支:

k = (k<<1) + (a < b) ;

但是如果你必须,我现在在你的代码中修复了一些东西,它应该可以按预期工作:

__asm__(
        "shl  $0x1, %0; \
        xor  %%eax, %%eax; \
        cmpl %3, %2; \
        setb %%al; \
        addl %%eax, %0;"
        :"=r"(k)        /* output */
        :"0"(k), "r"(a),"r"(b)  /* input */
        :"eax", "cc"   /* clobbered register */ 
);

请注意,setb需要一个reg8ormem8并且您应该将其添加eax到 clobbered 列表中,因为您更改了它,并且cc为了安全起见,至于寄存器约束,我不确定您为什么使用这些,但=r工作r得很好。您需要添加k到输入和输出列表中。GCC-Inline-Assembly-HOWTO中还有更多内容

于 2012-12-24T15:29:38.303 回答
2

概括:

  • 无分支甚至可能不是最佳选择。
  • 内联 asm 打败了其他一些优化,首先尝试其他源代码更改,例如? :经常无分支编译,也使用布尔值作为整数 0/1。
  • 如果您使用 inline-asm,请确保同时优化约束以使编译器生成的代码您的 asm 块之外有效。
  • 整个事情都可以使用cmp %[b], %[a]/ adc %[k],%[k] 您的手写代码比编译器生成的代码更糟糕,但在常量传播/CSE/内联没有使此代码(部分)优化掉的情况下,它们在小范围内是可以击败的。

如果您的编译器生成分支代码,并且分析显示这是错误的选择(该指令中分支未命中的高计数,例如在 Linux perf record -ebranch-misses ./my_program&&上perf report),那么是的,您应该做一些事情来获得无分支代码。

(如果它是可预测的,分支可能是一个优势:分支意味着使用的代码的乱序执行(k<<1) + 1不必等待ab准备好。LLVM 最近合并了一个补丁,默认情况下使 x86 代码生成更加分支,因为现代 x86 CPU 具有如此强大的分支预测器。Clang/LLVM 夜间构建(带有那个补丁)仍然为此 C 源代码选择无分支,至少在循环外的独立函数中)。

如果这是用于二分搜索,那么无分支可能是一个不错的策略,除非您经常看到相同的搜索。(分支+推测执行意味着你有一个关键路径之外的控制依赖,

使用配置文件引导优化进行编译,因此编译器具有关于哪些分支几乎总是单向的运行时信息。它可能仍然不知道一个难以预测的分支与一个整体上采用两条路径但具有简单模式的分支之间的区别。(或者这是基于全局历史可预测的;许多现代分支预测器设计基于分支历史的索引,因此最后几个分支的走向决定了当前分支使用哪个表条目。)

相关:gcc 优化标志 -O3 使代码变慢然后 -O2显示排序数组对循环内的条件进行近乎完美的分支预测的情况,以及gcc -O3数据依赖的无分支代码(没有配置文件引导优化)瓶颈从使用cmov. 但是-O3 -fprofile-use会产生分支代码。(另外,一种不同的编写方式使低延迟无分支代码也能更好地自动向量化。)


如果您不能手持编译器制作您想要的 asm ,内联 asm 应该是您最后的手段,例如(k<<1) + (a<b)按照其他人的建议编写它。

内联汇编破坏了许多优化,最明显的是常量传播(如其他一些答案所示,其中 gcc 将常量移动到内联汇编代码块之外的寄存器中)。 https://gcc.gnu.org/wiki/DontUseInlineAsm

当编译器对某些/所有变量具有常量值时,您可以使用if(__builtin_constant_p(a))等来使用纯 C 版本,但这需要更多的工作。(并且不适用于 Clang,__builtin_constant_p()在函数内联之前对 where 进行评估。)

即使那样(一旦你将事情限制在输入不是编译时常量的情况下),也不可能为编译器提供全部选项,因为你不能根据哪些约束使用不同的 asm 块匹配的(例如a在寄存器和b内存中,反之亦然。)如果您想根据情况使用不同的指令,那您就搞砸了,但在这里我们可以使用多种替代约束来展示大部分灵活性的cmp

让编译器生成接近最优的代码通常比使用内联 asm 更好。Inline-asm 破坏了编译器重用任何临时结果或分散指令以与其他编译器生成的代码混合的能力。(由于良好的乱序执行,指令调度在 x86 上并不是什么大问题,但仍然如此。)


那个asm很垃圾。如果你有很多分支未命中,它比分支实现要好,但更好的无分支实现是可能的。

a<b是一个无符号比较(你正在使用setb,下面的无符号条件)。所以你的比较结果在进位标志中。x86 有一个 add-with-carry 指令。此外,k<<1与 是相同的k+k

所以你想要的 asm(编译器生成或使用内联 asm)是:

# k in %rax,    a in %rdi,  b in %rsi   for this example
cmp     %rsi, %rdi      # CF = (a < b) = the carry-out from edi - esi
adc     %rax, %rax      # eax = (k<<1) + CF  = (k<<1) + (a < b)

编译器足够聪明,可以使用addlea左移 1,有些编译器足够聪明,可以使用adc而不是setb,但它们无法将两者结合起来。

编写带有寄存器参数和返回值的函数通常是了解编译器可能会做什么的好方法,尽管它确实会强制它们在不同的寄存器中产生结果。(另请参阅此问答和 Matt Godbolt 的 CppCon2017 演讲:“我的编译器最近为我做了什么?解开编译器的盖子”</a>)。

// I also tried a version where k is a function return value,
// or where k is a global, so it's in the same register.
unsigned funcarg(unsigned a, unsigned b, unsigned k) {
    if( a < b ) 
       k = (k<<1) + 1;
    else
       k = (k<<1);
    return k;
}

在 Godbolt 编译器资源管理器上,以及其他几个版本。(我unsigned在这个版本中使用过,因为你addl在你的 asm 中使用过。使用unsigned long将除异或归零之外的所有内容都变为 64 位寄存器。(xor %eax,%eax仍然是使 RAX 归零的最佳方法。)

 # gcc7.2 -O3  When it can keep the value in the same reg, uses add instead of lea
    leal    (%rdx,%rdx), %eax       #, <retval>
    cmpl    %esi, %edi      # b, a
    adcl    $0, %eax        #, <retval>
    ret

#clang 6.0 快照 -O3 xorl %eax, %eax cmpl %esi, %edi setb %al leal (%rax,%rdx,2), %eax retq

# ICC18,与 gcc 相同,但无法保存 MOV addl %edx, %edx #14.16 cmpl %esi, %edi #17.12 adcl $0, %edx #17.12 movl %edx, %eax #17.12 ret #17.12

MSVC 是唯一一个不用手动就不会生成无分支代码的编译器。(为我们提供了与上面 clang(k<<1) + ( a < b );完全相同的xor///序列(但使用 Windows x86-64 调用约定)。cmpsetblea

funcarg PROC                         ; x86-64 MSVC CL19 -Ox
    lea      eax, DWORD PTR [r8*2+1]
    cmp      ecx, edx
    jb       SHORT $LN3@funcarg
    lea      eax, DWORD PTR [r8+r8]   ; conditionally jumped over
$LN3@funcarg:
    ret      0

内联汇编

其他答案很好地涵盖了您的实施问题。要调试内联 asm 中的汇编器错误,请使用gcc -O3 -S -fverbose-asm填充 asm 模板来查看编译器向汇编器提供的内容。您会看到addl %rax, %ecx什么的。

这种优化的实现使用多种替代约束,让编译器选择CMP cmp $imm, r/mcmp r/m, rcmp r, r/m形式。我使用了两个替代方法,它们不是通过操作码而是通过哪一侧包含可能的内存操作数来分割事物。 "rme"类似于"g"(rmi) 但仅限于 32 位符号扩展立即数)。

unsigned long inlineasm(unsigned long a, unsigned long b, unsigned long k)
{
    __asm__("cmpq %[b], %[a]   \n\t"
            "adc %[k],%[k]"
        : /* outputs */ [k] "+r,r" (k)
        : /* inputs  */ [a] "r,rm" (a), [b] "rme,re" (b)
        : /* clobbers */ "cc");  // "cc" clobber is implicit for x86, but it doesn't hurt
    return k;
}

我把它放在 Godbolt 上,调用者在不同的上下文中内联它。gcc7.2-O3完成了我们对独立版本的期望(使用寄存器 args)。

inlineasm:
    movq    %rdx, %rax      # k, k
    cmpq %rsi, %rdi         # b, a
    adc %rax,%rax   # k
    ret

我们可以通过内联到其他调用者来查看我们的约束如何工作:

unsigned long call_with_mem(unsigned long *aptr) {
    return inlineasm(*aptr, 5, 4);
}
    # gcc
    movl    $4, %eax        #, k
    cmpq $55555, (%rdi)     #, *aptr_3(D)
    adc %rax,%rax   # k
    ret

使用更大的立即数,我们movabs进入一个寄存器。(但是如果有"i"or"g"约束,gcc 会发出不汇编的代码,或者截断常量,试图为 cmpq 使用一个大的立即常量。)

比较我们从纯 C 中得到的:

unsigned long call_with_mem_nonasm(unsigned long *aptr) {
    return handhold(*aptr, 5, 4);
}
    # gcc -O3
    xorl    %eax, %eax      # tmp93
    cmpq    $4, (%rdi)      #, *aptr_3(D)
    setbe   %al   #, tmp93
    addq    $8, %rax        #, k
    ret

adc $8, %raxwithoutsetc可能会更好,但是如果没有__builtin_constant_p()on ,我们就无法从内联 asm 中得到它k


如果有 mem 替代品,clang 经常会选择它,所以它会这样做:/facepalm。不要使用内联汇编。

inlineasm:   # clang 5.0
    movq    %rsi, -8(%rsp)
    cmpq    -8(%rsp), %rdi
    adcq    %rdx, %rdx
    movq    %rdx, %rax
    retq

顺便说一句,除非您要优化转换为比较加法,否则您可以而且应该要求编译器k<<1作为输入。

于 2017-11-29T23:11:32.090 回答