为什么使用 MOV 指令将异或交换优化为普通交换？

Question

在围绕 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 交换”，而是
"使用异或交换时，虽然似乎不会影响执行速度，但为什么它仍然被优化掉了？"

Answer 1

Clang 做同样的事情。可能出于 compiler-construction 和 CPU 架构原因：

在某些情况下，将逻辑分解成一个交换可能会允许更好的优化；编译器尽早做这件事绝对有意义，这样它就可以通过交换来跟踪值。
Xor-swap 是交换寄存器的总垃圾，唯一的优点是它不需要临时的。但是 xchg reg,reg 已经做得更好了。

我对 GCC 的优化器识别 xor-swap 模式并解开它以遵循原始值并不感到惊讶。通常，这使得 constant-propagation 和 value-range 优化可以通过交换进行，特别是对于交换不以交换的变量值为条件的情况。这个 pattern-recognition 可能在将程序逻辑转换为 GIMPLE (SSA) 表示后不久发生，所以到那时它会忘记原始源曾经使用过异或交换，并且不会考虑以这种方式发出 asm .

希望有时可以让它优化到只有一个 mov 或两个 mov，具体取决于周围代码的寄存器分配（例如，如果其中一个变量可以移动到一个新的寄存器，而不是必须回到原来的位置）。以及两个变量是否在以后实际使用，或者只使用一个。或者如果它可以完全解开无条件交换，也许没有 mov 指令。

但最坏的情况是，三个 mov 指令需要一个临时寄存器仍然更好，除非它运行超出寄存器。我猜 GCC 不够聪明，无法使用 xchg reg,reg 而不是溢出其他东西或 saving/restoring 另一个 tmp reg，所以可能存在这种优化实际上有害的极端情况。

（显然 GCC -Os 确实有一个窥孔优化来使用 xchg reg,reg 而不是 3x mov：~~PR 92549~~ was fixed for GCC10. It looks for that quite late, during RTL -> assembly. And yes, it works here: turning your xor-swap into an xchg: https://godbolt.org/z/zs969xh47 )

xor-swap 延迟更差，击败了 mov-elimination

with no memory reads, and the same number of instructions, I don't see any bad impacts and feels odd that it be changed. Clearly there is something I did not think through though, but what is it?

指令数只是 three things that are relevant for perf analysis 之一的粗略代理：front-end 微指令、延迟和 back-end 执行端口。（并且 machine-code 字节大小：x86 machine-code 指令是 variable-length。）

大小相同 machine-code 字节，front-end 微指令数相同，但 critical-path 延迟更差：3例如，xor-swap 从输入 a 到输出 a 的周期，以及从输入 b 到输出 a 的 2 个周期。

MOV-swap 从输入到输出最多有 1 个周期和 2 个周期的延迟，或者更短。（这也可以避免使用 back-end 执行端口，特别是与 CPU 相关，例如 IvyBridge 和 Tiger Lake，front-end 比整数 ALU 端口的数量更宽。和 Ice Lake，Intel 除外禁用 mov-elimination 作为勘误解决方法；不确定它是否 re-enabled 用于 Tiger Lake。）

还相关：

- 而那 3 个微指令无法从 mov-elimination 中受益。但是在现代 AMD 上 xchg reg,reg 只有 2 微指令。

如果要分支，只需复制平均代码

GCC 在这里真正错过的优化（即使使用 -O3）是 tail-duplication 导致大约相同的静态代码大小，只是多了几个字节，因为这些大多是 2 字节指令。最大的胜利是 a<b 路径然后变成与另一个路径相同的长度，而不是先进行交换的两倍长，然后运行相同的 3 微指令进行平均。

更新：GCC 将使用 -ftracer（https://godbolt.org/z/es7a3bEPv), optimizing away the swap. (That's only enabled 手动或作为 -fprofile-use 的一部分为您完成此操作，而不是 -O3，因此在没有 PGO 的情况下一直使用可能不是一个好主意，可能会使冷函数中的机器代码膨胀 / code-paths.)

在源中手动执行 (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，或者让 tail-duplication 版本有点乱） .

但是如果你打算去无分支那么你的 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 对其进行了安排，因此从任一输入到输出的 critical-path 延迟仅为 3 个周期（3 single-uop 指令），即使没有 mov-消除。（GCC 有一个长 4 条指令的链，包括一个 mov。）

高效non-overflowing无符号均值

另请参阅 - widening to uint64_t can be even cheaper, especially when inlining, on a 64-bit machine. (As discussed in comments under the question, e.g. https://godbolt.org/z/sz53eEYh9 显示我发表评论时现有答案的代码。）

另一个不错的选择是这个，但通常不如加宽：

  return (a&b) + (a^b)/2;

如果编译器识别出这些习语中的任何一个，他们可以使用 asm add/rcr 技巧，不过，这比扩大到 unsigned __int128 更有效地求平均 uint64_t.

为什么使用 MOV 指令将异或交换优化为普通交换？

Why is the XOR swap optimized into a normal swap using the MOV instruction?

c

gcc

optimization

x86-64

swap

xor-swap 延迟更差，击败了 mov-elimination

如果要分支，只需复制平均代码

高效non-overflowing无符号均值