在Compiler Explorer周围测试时,我尝试了以下无溢出函数来计算2个无符号32位整数的平均值:
uint32_t average_1(uint32_t a, uint32_t b)
{
if(a < b){
a ^= b;
b ^= a;
a ^= b;
}
return b + (a - b) / 2;
}
编译为以下内容:(与激活的-O1
、-O2
、-O3
优化相同)
average_1:
cmp edi, esi
jnb .L2
mov eax, edi
mov edi, esi
mov esi, eax
.L2:
sub edi, esi
shr edi
lea eax, [rdi+rsi]
ret
其中代码的交换部分已优化为使用带有1个附加寄存器的mov
指令。
我已经通读了这些问题: Why don't people use xor swaps?,Cost of swapping variables through mov, xor,
并了解到,使用XOR交换更难解释,并且由于需要更多的内存读取,对执行速度没有或负面影响。
但在本例中,看到使用的不是内存,而是eax
、esi
、edi
寄存器,我认为编译后的汇编代码也可以生成为:
average_1:
cmp edi, esi
jnb .L2
xor edi, esi
xor esi, edi
xor edi, esi
...
在没有内存读取和相同数量的指令的情况下,我看不到任何坏的影响,感觉它被更改了。 显然,有些事情我没有想清楚,但到底是什么呢?
编辑:明确地说,这里我的问题不是为什么不使用XOR交换,而是 使用XOR交换时,虽然似乎不会影响执行速度,但为什么仍对其进行优化?
推荐答案
clang做同样的事情。可能是由于编译器构造和CPU架构原因:
将该逻辑分解到一个交换中可能会在某些情况下实现更好的优化;对于编译器来说,提前这样做无疑是有意义的,这样它就可以在交换过程中跟踪值。
异或交换对于交换寄存器来说完全是垃圾,唯一的优点是它不需要临时的。但xchg reg,reg
已经做得更好了。
GCC的优化器识别XOR交换模式并将其分解为遵循原始值,这一点我并不感到惊讶。通常,这使得通过互换实现常量传播和值范围优化成为可能,尤其是在互换不以被交换变量的值为条件的情况下。这种模式识别可能是在将程序逻辑转换为Gimple(SSA)表示后不久发生的,因此在这一点上,它将忘记原始源代码曾经使用过XOR交换,并且不会考虑以这种方式发出ASM。
希望有时这会让它优化到只有一个mov
或两个mov
,这取决于周围代码的寄存器分配(例如,如果一个变量可以移动到新的寄存器,而不是必须回到原始位置)。以及这两个变量是在以后实际使用,还是只使用一个。或者,如果它可以完全解开无条件掉期,可能就没有mov
指令。
但最坏的情况是,需要临时寄存器的三条mov
指令仍然更好,除非它的寄存器快用完了。我猜GCC不够聪明,不会使用xchg reg,reg
而不是溢出其他内容或保存/恢复另一个临时注册表项,因此可能会出现这种优化实际上会带来负面影响的情况。
(显然GCC-Os
确实有优化xchg reg,reg
而不是使用3x mov:PR 92549被修复为GCC10。在RTL->;组装期间,它看起来相当晚。是的,它在这里起作用:将XOR交换转换为xchg:https://godbolt.org/z/zs969xh47)
异或交换延迟较差,无法消除移动
在没有内存读取和相同数量的指令的情况下,我看不到任何坏的影响,感觉它被更改了。显然,有些事情我没有想清楚,但到底是什么呢?
指令计数仅是three things that are relevant for perf analysis之一的粗略代理:前端uop、延迟和后端执行端口。(机器代码大小以字节为单位:x86机器代码指令是可变长度的。)
机器代码字节大小相同,前端uop数量相同但关键路径延迟更差:例如,对于XOR交换,从输入a
到输出a
3个周期,从输入b
到输出a
2个周期。
MOV-SWAP从输入到输出的最坏情况是1周期和2周期延迟,或者使用mov-elimination的延迟更少。(这也可以避免使用后端执行端口,特别是对于前端比整数ALU端口数更宽的IVYbridge和Tiger Lake等CPU。和Ice Lake,除了英特尔已将其上的Mov消除作为错误解决办法;不确定是否为Tiger Lake重新启用了它。)
还相关:
Why is XCHG reg, reg a 3 micro-op instruction on modern Intel architectures?-这3个uop不能从移动消除中受益。但在现代AMDxchg reg,reg
只有2个uop。
如果要进行分支,只需复制平均代码
GCC在这里真正错过的优化(即使使用-O3
)是,尾部复制导致的静态代码大小大致相同,只是多了几个字节,因为它们大多是2字节的指令。最大的优势是,a<b
路径的长度将与另一路径相同,而不是先进行掉期操作,然后再运行相同的3次上行操作来求平均。
更新:GCC将使用-ftracer
(https://godbolt.org/z/es7a3bEPv)为您完成此操作,并优化掉交换。(这是only enabled手动或作为-fprofile-use
的一部分,而不是在-O3
,因此在不使用pgo的情况下一直使用可能会使机器代码在冷函数/代码路径中膨胀并不是一个好主意。)
在源代码中手动完成(Godbolt):
uint32_t average_1_taildup(uint32_t a, uint32_t b)
{
if(a < b){
return a + (b - a) / 2;
}else {
return b + (a - b) / 2;
}
}
# GCC11.2 -O3
average_1_taildup:
cmp edi, esi
jnb .L5
sub esi, edi
shr esi
lea eax, [rsi+rdi]
ret
.L5:
sub edi, esi
shr edi
lea eax, [rdi+rsi]
ret
Clang使用cmov
将版本1和1_taildup
编译成代码(例如cmp/mov/cmovb/cmovb,或者将尾部复制版本搞得一团糟)。
但如果您要使用无分支网络,average_3
会更好:
uint32_t average_3(uint32_t a, uint32_t b)
{
return (a & b) + ((a ^ b) >> 1);
}
# clang 13.0 -O3
average_3:
mov eax, esi
and eax, edi
xor esi, edi
shr esi
add eax, esi
ret
GCC和clang的两个版本都只有5条指令(加上ret),但clang对其进行了安排,使得关键路径延迟从任一输入到输出只有3个周期(3个单微指令),即使没有mov
-消除。(GCC有一条4条指令长的链条,包括一个移动)
有效的无溢出无符号平均值
另请参阅Efficient overflow-immune arithmetic mean in C/C++-扩大到uint64_t可能会更便宜,尤其是在64位计算机上内联时。(正如问题下面的注释中所讨论的,例如https://godbolt.org/z/sz53eEYh9显示了我评论时现有答案中的代码。)另一个很好的选择是这样,但通常不如加宽:
return (a&b) + (a^b)/2;
如果编译器识别出这些习惯用法中的任何一个,他们可以使用ASMadd
/rcr
技巧,这比将unsigned __int128
扩大到uint64_t
求平均值更有效。
相关推荐
最新文章