在测试Compiler Explorer位左右时,我try 了以下无溢出函数,用于计算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;
}

(-O3被激活,-O1被激活)

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个附加寄存器.

我已经通读了这些问题:

得到了使用异或交换更难解释自身,并且由于需要更多的内存读取,对执行速度没有影响或负面影响.

但在本例中,看到的不是内存,而是正在使用的eaxesiedi寄存器,我认为编译后的汇编代码也可以生成为:

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

...

由于没有内存读取和相同数量的指令,我看不到任何不良影响,并且对它的更改感到奇怪.

编辑:要清楚,我的问题不是"为什么不使用XOR交换",而是

推荐答案

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更有效.

C相关问答推荐

为什么 memcpy() 随机不复制正确的值?

为什么启用优化时 GCC 11 编译器会产生奇怪的输出?

Gnuplot 和 C - 绘制不同的符号/ colored颜色

在 C 中使用数组而不是向量

幂函数给出的答案与 C 中的 math.pow 函数不同

确定在嵌入式 C 中运行时使用哪个变量

在编译时构建静态数组

判断由大括号组成的输入字符串是否格式正确

通过默认网关地址的硬件地址而不是以太网多播地址发送多播

为什么 malloc() 被认为是库调用而不是系统调用?

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