为什么MSVC在执行此位测试之前会发出无用的MOVSX？

Question

在MSVC 2013中编译以下代码,64位版本构建,/O2优化:

while (*s == ' ' || *s == ',' || *s == '\r' || *s == '\n') {
    ++s;
}

我得到了以下代码 - 使用64位寄存器作为带有bt(位测试)指令的查找表,它具有非常酷的优化.

    mov     rcx, 17596481020928             ; 0000100100002400H
    npad    5
$LL82@myFunc:
    movzx   eax, BYTE PTR [rsi]
    cmp     al, 44                          ; 0000002cH
    ja      SHORT $LN81@myFunc
    movsx   rax, al
    bt      rcx, rax
    jae     SHORT $LN81@myFunc
    inc     rsi
    jmp     SHORT $LL82@myFunc
$LN81@myFunc:
    ; code after loop...

但我的问题是:movsx rax, al第一个分支后的目的是什么？

首先,我们从字符串中加载一个字节rax并对其进行零扩展:

movzx eax, BYTE PTR [rsi]

然后cmp/ japair执行和之间的无符号比较,如果更大,则向前分支.al44al

所以现在,我们知道0 <= al <= 44无符号数.因此,al无法设置最高位!

尽管如此,下一条指令是movsx rax, al.这是一个符号扩展的举措.但是由于:

• al 是最低的字节 rax
• 我们已经知道其他7个字节rax是归零的
• 我们刚刚证明了al最高位不可能被设置

这movsx必须是无操作.

为什么MSVC会这样做？我假设它不是用于填充,因为在那种情况下,另一个npad会使意思更清晰.它是否正在刷新数据依赖关系？

(顺便说一下,这个bt优化真的让我开心一些有趣的事实:它在0.6X运行4时cmp/ je你所期望的对,它的方式快于strspn或std::string::find_first_not_of,而且只发生在64位构建即使感兴趣的字符的值低于32.)

Answer 1

您肯定会认识到,此优化是由优化程序中寻找模式的非常具体的代码生成的.只是位掩码的产生就让它消失了.是的,好戏.

这里有两个基本的codegen案例.第一个是更通用的,其中(charmax - charmin <= 64)但是charmax> = 64.优化器需要生成与您所看到的不同的代码,它需要减去charmin.该版本并没有具备MOVSX指令.您可以通过替换看到它*s == ' '的*s == 'A'.

然后是你测试的特殊情况,所有要测试的字符代码都是<64.微软程序员在他的代码中确实处理了这个问题,他确保不会生成一个愚蠢的SUB EAX,0指令.但忽略了生成MOVSX并不是必需的.肯定错过了只检查一般情况下的最佳代码.并且代码中的一般函数调用很容易被忽略,请注意当使用/ J编译时指令如何更改为MOVZX.否则很容易被认为是必要的,没有BT指令将8位寄存器作为第二个操作数,因此AL寄存器负载本身不够.

可能存在假设的优化后优化器,其优化优化器生成的优化代码.并决定保持MOVSX以改善超标量执行.我严重怀疑它存在.

Answer 2

正如Hans Passant已经提到的,您的代码是优化的一个特例.我没有查看编译器/优化器源代码,因此我只能说出我期望发生的事情.但是,这是我对此的解释.

您在C/C++中的代码:

while (*s == ' ' || *s == ',' || *s == '\r' || *s == '\n') {
    ++s;
}

相当于:

while (*s == 32 || *s == 44 || *s == 13 || *s == 12) {
    ++s;
}

要么:

while (*s == 12 || *s == 13 || *s == 32 || *s == 44) {
   ++s;
}

优化器检测到存在具有相同字符的多次(> = 3次)比较的"if".现在,优化器根据需要生成尽可能多的64位模式(8位字符最多4个模式,64*4 =>所有256个可能值).这些位模式中的每一个都具有偏移(=模式中的第一位对应的测试值),其需要从测试中的值中减去.在您的情况下,从12到44的值只需要一个64位模式.因此您的代码将转换为一些通用代码,如下所示:

#define ranged_bittest(pattern, value, min_val, max_val) \
  (val >= min_val) && (val <= max_val) && BT_with_offset(pattern, val, min_val)

while ( !ranged_bittest(<BITPATTERN>, *s, 12, 44) ) {
    ++s;
}

现在进行一些其他优化,ranged_bittest(<BITPATTERN>, *s, 12, 44);因为它检测到具有起始偏移12的位测试以及可以安全地向左移位12位的模式(因为模式的高12位为零). ranged_bittest(<BITPATTERN>, *s, 12, 44)=>ranged_bittest(<BITPATTERN> << 12, *s, 0, 44)

这演变为:

while (!(val >= 0 && val <= 44 && BT_with_offset(<SHIFTEDBITPATTERN>, *s, 0))) {
    ++s;
}

将val >= 0 &&被优化掉(因为它被认为是总是正确的)和"而"被翻译成一些"做"与休息-loop; (在大多数情况下,这对于分支预测更好)导致:

do {
  if (val > 44) break;
  if (BT_with_offset(<SHIFTEDBITPATTERN>, *s, 0)) break;

  ++s;
} while (true);

由于任何原因,优化在此处停止(例如,因为出于性能原因,对进一步优化应用于代码片段的频率存在限制).

现在在组装线

if (BT_with_offset(<SHIFTEDBITPATTERN>, *s, 0)) break;`

被翻译成类似的东西:

MOV <reg64_A>, const_pattern
MOV <reg64_B>, value
SUB <reg64_B>, const_offset
BT <reg64_A>, <reg64_B>

程序集优化器减少:

MOV <reg64_B>, value
SUB <reg64_B>, 0

只是

MOVSX <reg64_B>, value

在你的特殊情况下,这是:

MOVSX rax, al

程序集优化器(不知何故)没有足够的信息来完全消除符号扩展.也许汇编优化器非常"笨"(不能做任何逻辑表达式优化和填充,只是简单的替换)或者尚未激活完整优化级别.

因此它不能删除movsx rax,al,因为它没有关于代码的可能值rax或al在此点的任何元信息.

我不知道,如果这是真的,但这是我对这个案例的最佳猜测......