为什么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/ja指令对al和44进行无符号比较，若al大于44则跳转。

因此我们知道al在无符号数中满足0 <= al <= 44。 因此，al的最高位肯定不会被设置！

尽管如此，下一条指令是movsx rax, al，这是一个符号扩展的移动指令。但由于：

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

所以这个movsx必须是无操作的。

MSVC为什么要这样做？我认为这不是为了填充空间，因为在这种情况下另一个npad会使含义更清晰。 是为了刷新数据依赖关系或其他原因吗？

（顺便说一句，这个bt优化真的让我很高兴。一些有趣的事实：它的运行时间是你可能期望的4个cmp/je指令对的0.6倍，比strspn或std::string::find_first_not_of快得多，并且只会在64位构建中发生，即使感兴趣的字符值小于32。）

- japreiss

---

我已经有一段时间没有深入研究汇编语言了（实际上太久了），但是“我们已经知道其他7个字节都被清零了”-你是怎么知道的？如果在movsx之前它们不是零，那么在该指令之后它们肯定是零。在movzx eax之前的指令只能将其零扩展到32位，而movsx rax指令则将其符号扩展到64位（即剩余的4个字节）吗？如果这不正确，请提前谅解；正如我所说，我已经有一段时间没有深入研究了。 - WhozCraig

我95%确信，在64位代码中，所有带32位目标寄存器的指令都会隐式地将高32位清零。现在正在寻找权威来源。 - japreiss

看起来这似乎与下限为0有关。将 *s == ' ' 更改为 *s == 'A'，指令就会消失 :) - Hans Passant

你是否对两个版本进行了基准测试？显然存在一些微妙的CPU错误会导致错误依赖，有时候额外的语句可以消除这种依赖关系，导致较长的代码运行更快 - 额外的指令运行时间为负数！ - MSalters

我不是100%确定，但我认为后端正在插入指令以进行部分寄存器停顿。这极大地依赖于体系结构，并且编译器启发式算法可能认为这是避免它的最佳方法。 - Marco A.

Answer 1

你一定意识到这个优化是由优化器中非常特定的代码产生的，它在查找模式时使用了特定的位掩码生成技巧。只要看一下位掩码生成的过程就可以看出来。是的，这是个不错的技巧。

这里有两种基本的代码生成情况。第一种是更通用的情况，其中 (charmax - charmin <= 64)，但 charmax >= 64。优化器需要生成与您所看到的不同的代码，它需要减去 charmin。那个版本没有 MOVSX 指令。您可以通过将 *s == ' ' 替换为 *s == 'A' 来查看它。

然后是您测试的特殊情况，所有要测试的字符代码都小于 64。微软程序员确实在他的代码中处理了这个问题，他确保不会生成愚蠢的 SUB EAX,0 指令。但是忽略了生成 MOVSX 指令并不是必要的事实。他只检查了一般情况下的最优代码，很容易漏掉这种细节。而且代码中有一个一般函数调用，所以很容易忽略，注意当您使用 /J 编译时指令如何变成 MOVZX。否则，很容易认为是必要的，因为没有以 8 位寄存器作为第二个操作数的 BT 指令，所以单独的 AL 寄存器加载是不够的。

可能有一个假设的后优化器，可以对优化器生成的优化代码进行优化。并决定保留 MOVSX 指令以提高超标量执行效率。但我非常怀疑它是否存在。

- Hans Passant

---

+1 是为“后优化优化器”而加的，它可以优化由优化器生成的已经被优化过的代码。 - user703016

优化器是一个非常被滥用的词。 - 500 - Internal Server Error

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;
}

优化器检测到有一个“if”语句，其中同一字符进行了多次（>=3次）比较。现在，优化器将生成所需的64位模式（对于8位字符最多4个模式，64*4=>所有256种可能的值）。每个比特模式都有一个偏移量（=与模式中第一个比特对应的测试值），需要从测试值中减去。 在您的情况下，仅需要一个64位模式，用于值范围从12到44。因此，您的代码将转换为类似于以下通用代码：

#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开始的bittest和一个可以安全左移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 &&会被优化掉（因为它被认为始终为真），而"while"将被转换为一些带有break的"do"-循环；（在大多数情况下，这对分支预测更好）因此得到：

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，因为它没有关于rax或al可能值的元信息。

我不知道这是否正确，但这是我对这种情况的最佳猜测...

- SDwarfs

Answer 3

当我第一次看到这段代码时，最让我印象深刻的是它的优化程度实际上很差。
虽然使用64位寄存器进行查找表是个不错的技巧，但为什么还要使用"INC"而不是更好的"ADD，1"呢？
为什么在知道BT指令使用其源操作数MOD 64（因此有58位无需考虑）时，还要使用"CMP ..." "JA ..." "MOVSX ..."？
为什么不利用条件分支被预测为向后走的事实？
为什么不减少分支的数量？
我认为真正的汇编程序员会写成下面这样：

  mov     rcx, 0FFFFEFFEFFFFDBFFh  ;~0000100100002400h
  sub     rsi, 1
  npad    1
$LL82@myFunc:
  add     rsi, 1
  movzx   eax, BYTE PTR [rsi]   ;mov al,[rsi]
  test    al, 11000000b
  setz    bl
  test    bl, bl
  bt      rcx, rax
  ja      SHORT $LL82@myFunc

ja会在(CF或ZF) = 0时跳转

• 对于AL=[64,255]，ZF=1并且CF不影响结果
• 对于AL=[0,63]，ZF=0并且对于AL={10,13,32,44}，CF=0

当ASCII码在范围[64,255]内时，test al, 11000000b指令将产生一个非零结果(ZF=0)。由于使用了组合setz bl test bl, bl来翻转ZF为1，所以ja指令无法继续循环。
相反，当ASCII码在范围[0,63]内时，ZF最终将变为0，从而允许ja完全解释从bt rcx, rax指令得到的CF。

_{也许我们对优化编译器期望过高了？}

- Sep Roland

---

“CMP / JA” 不能被移除。例如，如果 c == 'J' == 0x4A，那么 c 的低6位是 0xA == '\n'，因此我们会得到错误的答案。 - japreiss

PPS: 但是 MOV rbx, rax AND rbx, 192 BT rcx, rax JA @loop 可能与一个否定的模式（除了位12、13、32、44之外，所有位都为1）结合使用。因为 MOV rbx, rax AND rbx, 192 设置 ZF=0（零标志），如果值<=63。BT只改变CF标志。而 JA @loop 跳转如果 (CF==0 and ZF==0)。这将是两个更多的指令，但它们都不是分支指令。仍然比原问题中编译器的解决方案更快。 - SDwarfs

“add 1”比“inc”更好的前提在现今几乎是错误的。 “gcc在这里做得非常好。它可以通过使用inc edx而不是add edx，1来节省一个代码字节，因为没有人关心P4及其部分标志修改指令的错误依赖性。” - phuclv

“INC”更短，因此在缓存未命中时可能会产生不同的影响。一些现代编译器（包括clang-3.8和英特尔的ICC 13）在优化速度（-O3）时确实使用inc，而不仅仅是为了大小，当它们不需要之后检查进位标志时。这可以节省1个字节（64位模式）或2个字节（32位模式中的inc r32短格式），从而在总代码大小上产生小百分比差异。”（https://dev59.com/y1oV5IYBdhLWcg3wPctv#36510865） - phuclv

@PeterCordes 我（终于）修复了这个答案中的代码。我使用了SDwarfs的建议，但发现ZF恰恰相反，与所需相反。 - Sep Roland