为什么使用 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

其中代码的交换部分经过优化，可以使用mov具有 1 个附加寄存器的指令。

我已经阅读了这些问题：

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

并得到：

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

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

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

...

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

---

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

Answer 1

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

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

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

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

希望有时这可以让它优化到只有一个mov或两个movs，具体取决于周围代码的寄存器分配（例如，如果其中一个变量可以移动到新的寄存器，而不必最终返回到原始位置） ）。以及这两个变量是否在稍后实际使用，或者仅使用一个。或者，如果它可以完全解开无条件互换，也许不会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到输出需要 2 个周期。a

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

还相关：

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

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

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

更新：GCC 将为您执行此操作-ftracer（https://godbolt.org/z/es7a3bEPv），优化交换。 （这只能手动启用或作为 的一部分启用-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使用（例如 cmp / mov / cmovb / cmovb，或者使尾部重复版本有点混乱）将版本 1 和1_taildup编译成代码。cmov

但如果你打算无分支机构，那么你的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 条指令，包括一个 mov。）

高效非溢出无符号均值

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

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

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

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