如何在gcc和VS中强制使用cmov

Question

我有这个简单的二进制搜索成员函数,在那里lastIndex,nIter并且xi是类成员:

uint32 scalar(float z) const
{
    uint32 lo = 0;
    uint32 hi = lastIndex;
    uint32 n = nIter;
    while (n--) {
        int mid = (hi + lo) >> 1;
        // defining this if-else assignment as below cause VS2015
        // to generate two cmov instructions instead of a branch
        if( z < xi[mid] ) 
            hi = mid;
        if ( !(z < xi[mid]) )
            lo = mid;
    }
    return lo;
}

gcc和VS 2015都将内循环转换为代码流分支:

000000013F0AA778  movss       xmm0,dword ptr [r9+rax*4]  
000000013F0AA77E  comiss      xmm0,xmm1  
000000013F0AA781  jbe         Tester::run+28h (013F0AA788h) 
000000013F0AA783  mov         r8d,ecx  
000000013F0AA786  jmp         Tester::run+2Ah (013F0AA78Ah)  
000000013F0AA788  mov         edx,ecx  
000000013F0AA78A  mov         ecx,r8d

有没有办法,没有编写汇编内联,说服他们使用正好1 comiss指令和2 cmov指令？

如果没有,有人可以建议如何为此编写gcc汇编程序模板吗？

请注意,我知道二进制搜索算法存在各种变化,编译器很容易生成无分支代码,但这不是问题所在.

谢谢

Answer 1

正如Matteo Italia已经指出的那样,这种避免条件移动指令是GCC版本6的一个怪癖.但他没有注意到的是,它只适用于优化英特尔处理器.

随着GCC 6.3,针对AMD处理器时(即-march=任何的k8,k10,opteron,amdfam10,btver1,bdver1,btver2,btver2,bdver3,bdver4,znver1,可能还有其他人),你得到正是你想要的代码:

    mov     esi, DWORD PTR [rdi]
    mov     ecx, DWORD PTR [rdi+4]
    xor     eax, eax
    jmp     .L2
.L7:
    lea     edx, [rax+rsi]
    mov     r8, QWORD PTR [rdi+8]
    shr     edx
    mov     r9d, edx
    movss   xmm1, DWORD PTR [r8+r9*4]
    ucomiss xmm1, xmm0
    cmovbe  eax, edx
    cmova   esi, edx
.L2:
    dec     ecx
    cmp     ecx, -1
    jne     .L7
    rep ret

在针对任何一代英特尔处理器进行优化时,GCC 6.3避免了条件移动,更喜欢显式分支:

    mov      r9d, DWORD PTR [rdi]
    mov      ecx, DWORD PTR [rdi+4]
    xor      eax, eax
.L2:
    sub      ecx, 1
    cmp      ecx, -1
    je       .L6
.L8:
    lea      edx, [rax+r9]
    mov      rsi, QWORD PTR [rdi+8]
    shr      edx
    mov      r8d, edx
    vmovss   xmm1, DWORD PTR [rsi+r8*4]
    vucomiss xmm1, xmm0
    ja       .L4
    sub      ecx, 1
    mov      eax, edx
    cmp      ecx, -1
    jne      .L8
.L6:
    ret
.L4:
    mov      r9d, edx
    jmp      .L2

这种优化决策的可能理由是,在英特尔处理器上,条件移动效率相当低.CMOV英特尔处理器的延迟时间为2个时钟周期,与AMD的1个周期延迟相比.此外,虽然CMOV指令在英特尔处理器上被解码为多个μops(至少两个,没有机会进行μop融合),因为要求单个μop具有不超过两个输入依赖性(条件移动至少有三个:两个操作数和条件标志),AMD处理器可以CMOV用单个宏操作实现一个,因为它们的设计对单个宏操作的输入依赖性没有这样的限制.因此,GCC优化器替换为条件分支移动仅在AMD处理器,它可能是一个性能WIN- 不是英特尔的处理器,而不是调整为通用86时.

(或者,也许GCC开发人员只是阅读了Linus臭名昭着的咆哮.:-)

但有趣的是,当你告诉GCC调整奔腾4处理器时(由于某些原因你无法为64位版本执行此操作) - GCC告诉你这个架构不支持64位,即使有绝对是实施EMT64的P4处理器,你确实得到了有条件的动作:

    push    edi
    push    esi
    push    ebx
    mov     esi, DWORD PTR [esp+16]
    fld     DWORD PTR [esp+20]
    mov     ebx, DWORD PTR [esi]
    mov     ecx, DWORD PTR [esi+4]
    xor     eax, eax
    jmp     .L2
.L8:
    lea     edx, [eax+ebx]
    shr     edx
    mov     edi, DWORD PTR [esi+8]
    fld     DWORD PTR [edi+edx*4]
    fucomip st, st(1)
    cmovbe  eax, edx
    cmova   ebx, edx
.L2:
    sub     ecx, 1
    cmp     ecx, -1
    jne     .L8
    fstp    st(0)
    pop     ebx
    pop     esi
    pop     edi
    ret

我怀疑这是因为奔腾4上的分支错误预测是如此昂贵,因为它的管道非常长,单个错误预测分支的可能性超过了你可能通过打破循环携带的依赖关系和微小的增加的延迟来获得的任何微小的收益.CMOV.另一种方式:错误预测的分支在P4上变慢了很多,但是延迟CMOV并没有改变,所以这偏向于有条件的移动.

调整后来的架构,从Nocona到Haswell,GCC 6.3又回到了它更倾向于采用分支而不是条件移动的策略.

所以,虽然这看起来像是一个严格的内环循环中的主要悲观(并且它看起来也是这样),如果没有基准来支持你的假设,就不要那么快就解雇它.有时,优化器并不像它看起来那么愚蠢.请记住,有条件移动的优点是它避免了分支错误预测的惩罚; 条件移动的缺点是它增加了依赖链的长度并且可能需要额外的开销,因为在x86上,只允许寄存器→寄存器或存储器→寄存器条件移动(无常数→寄存器).在这种情况下,所有内容都已经注册,但仍需要考虑依赖链的长度.Agner Fog在他的汇编语言优化子程序中给出了以下经验法则:

如果代码是依赖链的一部分并且预测率优于75%,则可以说条件跳转比条件移动更快.如果我们可以避免冗长的计算......当选择另一个操作数时,条件跳转也是首选.

第二部分不适用于此,但第一部分不适用.这里肯定存在一个循环携带的依赖链,除非你进入一个破坏分支预测(通常精度> 90%)的真正病态的情况,分支实际上可能更快.事实上,Agner Fog继续说道:

循环携带的依赖链对条件移动的缺点特别敏感.例如,[此代码]

// Example 12.16a. Calculate pow(x,n) where n is a positive integer
double x, xp, power;
unsigned int n, i;
xp=x; power=1.0;
for (i = n; i != 0; i >>= 1) {
    if (i & 1) power *= xp;
    xp *= xp;
}

使用循环内的分支比使用条件移动更有效,即使分支预测不佳.这是因为浮点条件移动会增加循环传递的依赖关系链,并且因为具有条件移动的实现必须计算所有power*xp值,即使它们未被使用也是如此.

循环携带的依赖链的另一个例子是排序列表中的二进制搜索.如果要搜索的项目随机分布在整个列表中,则分支预测率将接近50%,并且使用条件移动将更快.但是如果项目通常彼此接近以使预测率更好,则使用条件跳转比条件移动更有效,因为每次进行正确的分支预测时依赖链都会被破坏.

如果列表中的项目实际上是随机的或接近随机的,那么您将成为重复分支预测失败的受害者,并且条件移动将更快.否则,在更常见的情况下,分支预测将在75%的时间内成功,这样您将从分支中获得性能获胜,而不是扩展依赖链的条件移动.

理论上很难对此进行推理,而且更难以正确猜测,因此您需要将其与实际数字进行实际比较.

如果您的基准测试确认条件移动确实会更快,那么您有几个选择:

1. 升级到更高版本的GCC,如7.1,即使针对英特尔处理器,也会在64位版本中生成条件移动.
2. 告诉GCC 6.3优化AMD处理器的代码.(甚至可能只是优化一个特定的代码模块,以便最大限度地减少全局影响.)

3. 获得真正的创造性(丑陋且可能不可移植),在C中编写一些比特错误的代码,无分支地执行比较和设置操作.这可能会让编译器发出一个条件移动指令,或者它可能让编译器发出一系列bit-twiddling指令.您必须检查输出以确定,但如果您的目标只是为了避免分支错误预测处罚,那么任何一个都可以.

   例如,像这样:

   inline uint32 ConditionalSelect(bool condition, uint32 value1, uint32 value2)
   {
      const uint32 mask = condition ? static_cast<uint32>(-1) : 0;
      uint32 result = (value1 ^ value2);   // get bits that differ between the two values
      result &= mask;                      // select based on condition
      result ^= value2;                    // condition ? value1 : value2
      return result;
   }
   

   然后你会在内部循环中调用它,如下所示:

   hi = ConditionalSelect(z < xi[mid], mid, hi);
   lo = ConditionalSelect(z < xi[mid], lo, mid);
   

   GCC 6.3在针对x86-64时为此生成以下代码:

       mov     rdx, QWORD PTR [rdi+8]
       mov     esi, DWORD PTR [rdi]
       test    edx, edx
       mov     eax, edx
       lea     r8d, [rdx-1]
       je      .L1
       mov     r9, QWORD PTR [rdi+16]
       xor     eax, eax
   .L3:
       lea     edx, [rax+rsi]
       shr     edx
       mov     ecx, edx
       mov     edi, edx
       movss   xmm1, DWORD PTR [r9+rcx*4]
       xor     ecx, ecx
       ucomiss xmm1, xmm0
       seta    cl               // <-- begin our bit-twiddling code
       xor     edi, esi
       xor     eax, edx
       neg     ecx
       sub     r8d, 1           // this one's not part of our bit-twiddling code!
       and     edi, ecx
       and     eax, ecx
       xor     esi, edi
       xor     eax, edx         // <-- end our bit-twiddling code
       cmp     r8d, -1
       jne     .L3
   .L1:
       rep ret
   

   请注意,内部循环完全是无分支的,这正是您想要的.它可能不如两条CMOV指令那么有效,但它会比长期错误预测的分支更快.(毋庸置疑,GCC和任何其他编译器都足够聪明,可以内联ConditionalSelect函数,这样我们就可以出于可读性的目的将其写成外联.)

但是,我绝对不会建议您使用内联汇编重写循环的任何部分.所有标准原因都适用于避免内联汇编,但在这种情况下,即使是提高性能的愿望也不是使用它的令人信服的理由.如果你试图将内联汇编放到该循环的中间,那么你更有可能混淆编译器的优化器,如果你只是把编译器留给它自己的设备那么会导致低于你原来的代码差. .您可能必须在内联汇编中编写整个函数才能获得良好的结果,即使这样,当GCC的优化器尝试内联函数时,也可能存在溢出效应.

MSVC怎么样？好吧,不同的编译器有不同的优化器,因此有不同的代码生成策略.如果您已经开始哄骗所有目标编译器发出特定的汇编代码序列,事情就会变得非常难以实现.

在MSVC 19(VS 2015)上,当以32位为目标时,您可以按照获取条件移动指令的方式编写代码.但是,在构建64位二进制文​​件时,这不起作用:您可以使用分支机构,就像GCC 6.3针对英特尔一样.

但是,有一个很好的解决方案,它运行良好:使用条件运算符.换句话说,如果您编写如下代码:

hi = (z < xi[mid]) ? mid : hi;
lo = (z < xi[mid]) ? lo  : mid;

然后VS 2013和2015将始终发出CMOV指令,无论您是构建32位还是64位二进制文​​件,无论是针对size(/O1)还是speed(/O2)进行优化,/favor:Intel64还是针对Intel()或AMD (/favor:AMD64).

这确实无法CMOV在VS 2010上返回指令,但仅限于构建64位二进制文​​件时.如果您需要确保此方案也生成无分支代码,则可以使用上述ConditionalSelect功能.

Answer 2

正如评论中所述，没有简单的方法来强制执行您所要求的内容，尽管 gcc 的最新版本（>4.4）似乎已经像您所说的那样对其进行了优化。编辑：有趣的是，gcc 6 系列似乎使用一个分支，而不像gcc 5和gcc 7系列使用两个cmov.

通常__builtin_expect可能无法推动 gcc 使用cmov，因为cmov当难以预测比较结果时通常很方便，同时告诉__builtin_expect编译器可能的结果是什么 - 所以你只会将其推向错误的方向。

尽管如此，如果您发现这种优化极其重要，您的编译器版本通常会出错，并且由于某种原因您无法使用 PGO 帮助它，相关的 gcc 汇编模板应该类似于：

    __asm__ (
        "comiss %[xi_mid],%[z]\n"
        "cmovb %[mid],%[hi]\n"
        "cmovae %[mid],%[lo]\n"
        : [hi] "+r"(hi), [lo] "+r"(lo)
        : [mid] "rm"(mid), [xi_mid] "xm"(xi[mid]), [z] "x"(z)
        : "cc"
    );

使用的约束是：

• hi和lo进入“写入”变量列表，约束+r为cmov只能使用寄存器作为目标操作数，并且我们有条件地仅覆盖其中之一（我们不能使用=，因为它意味着该值总是被覆盖，因此编译器会可以自由地为我们提供一个与当前目标寄存器不同的目标寄存器，并在我们的块之后使用它来引用该变量asm）；
• mid位于“读取”列表中，rm可以cmov将寄存器或内存操作数作为输入值；
• xi[mid]并且z在“已读”列表中；
  • z具有特殊x约束，表示“任何 SSE 寄存器”（第一个操作数需要ucomiss）；
  • xi[mid]有xm，因为第二个ucomiss操作数允许内存运算符；z考虑到和之间的选择xi[mid]，我选择最后一个作为直接从内存中获取的更好候选者，因为它z已经在寄存器中（由于 System V 调用约定 - 并且无论如何都会在迭代之间缓存）并且xi[mid]是仅用于本次比较；
• cc（FLAGS 寄存器）位于“破坏”列表中 - 我们只破坏标志，仅此而已。