Clang也做了同样的事情.可能是由于编译器构造和CPU体系 struct 的原因:
在某些情况下,将这种逻辑分解为一种交换可以实现更好的优化;对于编译器来说,尽早执行某些操作是有意义的,这样它就可以在交换过程中跟踪值.
异或交换对于交换寄存器来说完全是垃圾,唯一的优点是它不需要临时的.但xchg reg,reg
已经做得更好了.
GCC的优化器识别xor交换模式并将其分解以遵循原始值,我并不感到惊讶.一般来说,这使得通过交换不断传播和值范围优化成为可能,尤其是在交换不以被交换的变量的值为条件的情况下.这种模式识别可能是在将程序逻辑转换为GIMPLE(SSA)表示后不久发生的,因此在这一点上,它会忘记原始源代码曾经使用过异或交换,而不会考虑以这种方式发出asm.
希望有时这能让它优化到只有一个mov
或两个mov
,这取决于周围代码的寄存器分配(例如,如果其中一个变量可以移动到新寄存器,而不必返回原始位置).以及这两个变量是以后实际使用,还是只使用一个.或者,如果它能完全解开无条件交换的谜团,也许就没有mov
条指令了.
但最糟糕的情况是,需要临时寄存器的3mov
条指令仍然更好,除非寄存器用完了.我猜GCC不够聪明,无法使用xchg reg,reg
来代替溢出其他内容或保存/恢复另一个tmp注册,因此可能会出现这种优化实际带来伤害的情况.
(显然GCC -Os
does有一个窥视孔优化,使用xchg reg,reg
而不是3x mov:PR 92549是为GCC10修复的.它看起来很晚了,在RTL->;组装期间.是的,它在这里工作:将xor交换转换为xchg:https://godbolt.org/z/zs969xh47)
xor交换延迟更差,无法消除mov
由于没有内存读取和相同数量的指令,我看不到任何不良影响,并且对它的更改感到奇怪.很明显,有些事情我没有想清楚,但那是什么呢?
指令计数只是three things that are relevant for perf analysis个端口之一的粗略代理:前端UOP、延迟和后端执行端口.(机器代码大小以字节为单位:x86机器代码指令长度可变.)
机器代码字节的大小相同,前端UOP的数量也相同,例如,对于异或交换,从输入a
到输出a
的周期为but the critical-path latency is worse:3,从输入b
到输出a
的周期为2.
MOV交换从输入到输出的延迟最差为1周期和2周期,或小于mov-elimination.(这也可以避免使用后端执行端口,特别是与IvyBridge和Tiger Lake等前端宽度大于整数ALU端口数的CPU有关.Ice Lake,但作为一种勘误解决方案,Intel禁用了对其进行mov消除;不确定是否为Tiger Lake启用了它.)
同样相关的还有:
如果要分支,只需复制平均代码即可
GCC在这里真正遗漏的优化(即使是-O3
)是尾部重复会导致几乎相同的静态代码大小,只是多了几个字节,因为这些大部分是2字节指令.最大的好处是,a<b
路径与另一条路径的长度相同,而不是两倍于先进行交换,然后运行相同的3个UOP进行平均.
update: GCC will do this for you with 102 (100), optimizing away the swap.(这是only enabled手动或作为-fprofile-use
的一部分,而不是-O3
,所以在没有PGO的情况下一直使用可能不是一个好主意,这可能会导致冷函数/代码路径中的机器代码inflating .)
在源代码中手动执行(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,或者为尾部复制版本制造一些混乱).
But if you're going to go branchless then your 100 is superior:
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条单uop指令),即使没有mov
个消除.(GCC有一个4条指令长的链,包括一个mov.)
有效非溢出无符号均值
另请参见https://godbolt.org/z/sz53eEYh99078/efficient-overflow-immune-arithmetic-mean-in-c-c">Efficient overflow-immune arithmetic mean in C/C++-扩展到uint64_t可能更便宜,尤其是在64位机器上进行内联时.(正如在问题下的 comments 中所讨论的,例如https://godbolt.org/z/sz53eEYh9显示了我发表 comments 时现有答案的代码.)
另一个不错的 Select 是这样,但通常不如加宽:
return (a&b) + (a^b)/2;
不过,如果编译器识别出这些习语中的任何一种,他们可以使用asm add
/rcr
技巧,这比将平均值uint64_t
扩大到unsigned __int128
更有效.