为什么使用MOV指令将XOR交换优化为普通交换？ [英] Why is the XOR swap optimized into a normal swap using the MOV instruction?
问题描述
在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到输出a3个周期，从输入b到输出a2个周期。
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不能从移动消除中受益。但在现代AMD
xchg 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
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求平均值更有效。
这篇关于为什么使用MOV指令将XOR交换优化为普通交换？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
