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

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 指令。

我已经阅读了这些问题：

为什么人们不使用异或交换？
通过 mov、xor 交换变量的成本

并得到：

• 使用XOR 交换本身更难以解释，并且
• mov 指令方法需要更多内存，因此不会对执行速度产生负面影响 读。

但在这种情况下，看到的不是内存，而是仅使用了 eax、esi、edi 寄存器，我认为编译后的汇编代码也可以生成为：

average_1:
        cmp     edi, esi
        jnb     .L2
        xor     edi, esi
        xor     esi, edi
        xor     edi, esi

...

没有内存读取，并且指令数量相同，我没有看到任何不良影响，并且对它的更改感到奇怪。 显然，有些事情我没有想到，但它是什么？

---

编辑：要明确的是，这里我的问题不是“为什么不使用异或交换”，而是
“当使用 XOR 交换时，虽然它在这种特殊情况下似乎不会影响执行速度，但为什么它仍然被优化了？ ”

Answer 1

Clang 也做同样的事情。可能是出于编译器构造和 CPU 架构的原因：

• 将逻辑分解为交换可能在某些情况下可以实现更好的优化；对于编译器来说，尽早执行这件事绝对是有意义的，这样它就可以通过交换来跟踪值。

• 异或交换对于交换寄存器来说完全是垃圾，唯一的优点是它不需要临时。但是 xchg reg,reg 已经做得更好了。

---

我对 GCC 的优化器识别异或交换模式并将其解开以遵循原始值并不感到惊讶。一般来说，这使得通过交换实现常量传播和值范围优化成为可能，特别是在交换不以被交换的变量值为条件的情况下。这种模式识别可能会在将程序逻辑转换为 GIMPLE (SSA) 表示形式后不久发生，因此那时它会忘记原始源曾经使用过异或交换，并且不会考虑以这种方式发出 asm。

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

但最坏的情况是，三个需要临时寄存器的 mov 指令仍然更好，除非寄存器用完。我猜 GCC 不够聪明，无法使用 xchg reg,reg 来代替溢出其他内容或保存/恢复另一个 tmp reg，因此可能存在这种优化实际上会造成伤害的极端情况。

（显然 GCC -Os 确实有一个窥视孔优化，可以使用 xchg reg,reg 而不是 3x mov：PR 92549 已修复GCC10。它在 RTL 期间查找这一点 -> 是的，它在这里起作用：将你的 xor-swap 转换为 xchg：https://godbolt.org/z/zs969xh47)

xor-swap 具有更差的延迟并击败了 mov-elimination

没有内存读取，并且指令数量相同，我没有看到任何不良影响，并且对它的更改感到奇怪。显然有些事情我没有想到，但它是什么？

指令计数只是 之一的粗略代理与性能分析相关的三件事：前端微指令、延迟和后端执行端口。 （机器代码大小以字节为单位：x86 机器代码指令是可变长度的。）

机器代码字节大小相同，前端微指令数量相同，但关键路径延迟更差：对于异或交换，从输入 a 到输出 a 需要 3 个周期，从输入 b 到输出 a 需要 2 个周期，例如。

MOV-swap 从输入到输出的最坏情况为 1 周期和 2 周期延迟，或者使用 mov-消除。 （这也可以避免使用后端执行端口，特别是与 IvyBridge 和 Tiger Lake 等前端比整数 ALU 端口数量宽的 CPU 相关。还有 Ice Lake，除了 Intel 禁用了 mov-elimination 作为勘误表解决方法；不确定是否为 Tiger Lake 重新启用。）

还相关：

• 为什么是 XCHG reg, reg现代英特尔架构上的 3 个微操作指令？ - 而这 3 个微操作不能从 mov-elimination 中受益。但在现代 AMD xchg reg,reg 上只有 2 uops。

---

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

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

更新：GCC 将使用 -ftracer 为您执行此操作 (https://godbolt .org/z/es7a3bEPv），优化掉交换。（即仅启用手动或作为-fprofile-use，而不是在 -O3 处，因此在没有 PGO 的情况下一直使用可能不是一个好主意，可能会在冷函数/代码路径中使机器代码膨胀。）

在源代码中手动执行此操作（<一个href="https://godbolt.org/z/78cEEsTTW" rel="noreferrer">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 编译为代码/code> （例如 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 对其进行了安排，因此关键即使没有 mov 消除，从输入到输出的路径延迟也仅为 3 个周期（3 个单微指令指令）。 （GCC 有一条链，长度为 4 个指令，包括一个 mov。）

高效非溢出无符号均值

另请参阅 C/C++ 中高效的防溢出算术平均值 - 扩展到 uint64_t 甚至可以更便宜，尤其是在内联时，在64 位机器。 （正如问题下的评论中所讨论的，例如 https://godbolt.org/z/sz53eEYh9 显示代码来自我发表评论时的现有答案。）

另一个不错的选择是这样，但通常不如扩大：

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

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