概括:
- 无分支甚至可能不是最佳选择。
- 内联 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
不必等待a
和b
准备好。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)
编译器足够聪明,可以使用add
或lea
左移 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 调用约定)。cmp
setb
lea
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/m
、cmp r/m, r
或cmp 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, %rax
withoutsetc
可能会更好,但是如果没有__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
作为输入。