assembly - 由于从越界内存中跳过 cmov，难以调试 SEGV

Question

我正在尝试编写一些高性能汇编函数作为练习，并且在运行程序时遇到了一个奇怪的段错误，但在 valgrind 或 nemiver 中没有。

基本上不应该运行的 cmov，带有越界地址，即使条件始终为假，也会使我出现段错误

我有一个快速和一个慢速版本。缓慢的一直有效。除非我在 adb 或 nemiver 上运行，否则快速的工作，除非它收到一个非 ascii 字符，否则它会严重崩溃。

ascii_flags 只是一个 128 字节的数组(末尾有一点空间)包含所有 ASCII 字符(字母、数字、可打印等)上的标志。

这有效:

ft_isprint:
    xor EAX, EAX                ; empty EAX
    test EDI, ~127              ; check for non-ascii (>127) input
    jnz .error
    mov EAX, [rel ascii_flags + EDI]    ; load ascii table if input fits
    and EAX, 0b00001000         ; get specific bit
.error:
    ret

但这不是:

ft_isprint:
    xor EAX, EAX                ; empty EAX
    test EDI, ~127              ; check for non-ascii (>127) input
    cmovz EAX, [rel ascii_flags + EDI]  ; load ascii table if input fits
    and EAX, flag_print         ; get specific bit
    ret

Valgrind 实际上确实崩溃了，但除了内存地址之外没有其他信息，因为我没有设法获得更多调试信息。

编辑:

我已经编写了三个版本的函数来考虑这些精彩的答案:

ft_isprint:
    mov RAX, 128                            ; load default index
    test RDI, ~127                          ; check for non-ascii (>127) input
    cmovz RAX, RDI                          ; if none are found, load correct index
    mov AL, byte [ascii_flags + RAX]        ; dereference index into least sig. byte
    and RAX, flag_print                     ; get specific bit (and zeros rest of RAX)
    ret

ft_isprint_branch:
    test RDI, ~127                          ; check for non-ascii (>127) input
    jnz .out_of_bounds                      ; if non-ascii, jump to error handling
    mov AL, byte [ascii_flags + RDI]        ; dereference index into least sig. byte
    and RAX, flag_print                     ; get specific bit (and zeros rest of RAX)
    ret
.out_of_bounds:
    xor RAX, RAX                            ; zeros return value
    ret

ft_isprint_compact:
    xor RAX, RAX                            ; zeros return value preemptively
    test RDI, ~127                          ; check for non-ascii (>127) input
    jnz .out_of_bounds                      ; if non-ascii was found, skip dereferenciation
    mov AL, byte [ascii_flags + RDI]        ; dereference index into least sig. byte
    and RAX, flag_print                     ; get specific bit
.out_of_bounds:
    ret

经过大量测试，对于所有类型的数据，分支函数肯定比 cmov 函数快约 5-15%。正如预期的那样，紧凑型和非紧凑型版本之间的差异很小。 Compact 在可预测数据集上的速度稍快一些，而非 Compact 在不可预测数据上的速度同样稍快。

我尝试了各种不同的方法来跳过“xor EAX，EAX”指令，但找不到任何有效的方法。

编辑:经过更多测试，我将代码更新为三个新版本:

ft_isprint_compact:
    sub EDI, 32                             ; substract 32 from input, to overflow any value < ' '
    xor EAX, EAX                            ; set return value to 0
    cmp EDI, 94                             ; check if input <= '~' - 32
    setbe AL                                ; if so, set return value to 1
    ret

ft_isprint_branch:
    xor EAX, EAX                            ; set return value to 0
    cmp EDI, 127                            ; check for non-ascii (>127) input
    ja .out_of_bounds                       ; if non-ascii was found, skip dereferenciation
    mov AL, byte [rel ascii_flags + EDI]    ; dereference index into least sig. byte
.out_of_bounds:
    ret

ft_isprint:
    mov EAX, 128                            ; load default index
    cmp EDI, EAX                            ; check if ascii
    cmovae EDI, EAX                         ; replace with 128 if outside 0..127
                                            ; cmov also zero-extends EDI into RDI
;   movzx EAX, byte [ascii_flags + RDI]     ; alternative to two following instruction if masking is removed
    mov AL, byte [ascii_flags + RDI]        ; load table entry
    and EAX, flag_print                     ; apply mask to get correct bit and zero rest of EAX
    ret

性能如下，以微秒为单位。 1-2-3 显示执行顺序，以避免缓存优势:

-O3 a.out
1 cond 153185, 2 branch 238341 3 no_table 145436
1 cond 148928, 3 branch 248954 2 no_table 116629
2 cond 149599, 1 branch 226222 3 no_table 117428
2 cond 117258, 3 branch 241118 1 no_table 147053
3 cond 117635, 1 branch 228209 2 no_table 147263
3 cond 146212, 2 branch 220900 1 no_table 147377
-O3 main.c
1 cond 132964, 2 branch 157963 3 no_table 131826
1 cond 133697, 3 branch 159629 2 no_table 105961
2 cond 133825, 1 branch 139360 3 no_table 108185
2 cond 113039, 3 branch 162261 1 no_table 142454
3 cond 106407, 1 branch 133979 2 no_table 137602
3 cond 134306, 2 branch 148205 1 no_table 141934
-O0 a.out
1 cond 255904, 2 branch 320505 3 no_table 257241
1 cond 262288, 3 branch 325310 2 no_table 249576
2 cond 247948, 1 branch 340220 3 no_table 250163
2 cond 256020, 3 branch 415632 1 no_table 256492
3 cond 250690, 1 branch 316983 2 no_table 257726
3 cond 249331, 2 branch 325226 1 no_table 250227
-O0 main.c
1 cond 225019, 2 branch 224297 3 no_table 229554
1 cond 235607, 3 branch 199806 2 no_table 226286
2 cond 226739, 1 branch 210179 3 no_table 238690
2 cond 237532, 3 branch 223877 1 no_table 234103
3 cond 225485, 1 branch 201246 2 no_table 230591
3 cond 228824, 2 branch 202015 1 no_table 226788

无表版本与 cmov 一样快，但不允许容易实现的局部变量。除非在零优化中的可预测数据上，否则分支算法更糟？我在那里没有任何解释。

我将保留 cmov 版本，它是最优雅且易于更新的版本。感谢所有的帮助。

Answer 1

cmov是一个 ALU 选择操作，它总是在检查条件之前读取两个源 .使用内存源不会改变这一点。如果条件为假，它不像一个 ARM 谓词指令，它就像一个 NOP。 cmovz eax, [mem]也无条件地写入 EAX，无论条件如何，都将零扩展到 RAX。
就大部分 CPU 而言(乱序调度器等)，cmovcc reg, [mem]处理方式与 adc reg, [mem] 完全一样: 3 输入 1 输出 ALU 指令 . ( adc 写入标志，与 cmov 不同，但不要紧。)微融合内存源操作数是一个单独的 uop，恰好是同一 x86 指令的一部分。这也是 ISA 规则的运作方式。
真的，这是 cmovz 更合适的助记符作为 selectz
x86 的唯一条件加载 (不会在错误地址上出错，只是可能运行缓慢)是:

受条件分支保护的正常负载 .分支错误预测或其他导致运行错误负载的错误推测得到了相当有效的处理(可能开始页面遍历，但一旦识别出错误推测，正确的指令流的执行就不必等待任何内存操作由推测执行启动)。
如果在您无法读取的页面上有 TLB 命中，那么在错误加载达到退休之前不会发生更多事情(已知是非推测性的，因此实际上会发生 #PF 页面错误异常，这不可避免地会发生)慢)。在某些 CPU 上，这种快速处理会导致 Meltdown 攻击。 >.< 见 http://blog.stuffedcow.net/2018/05/meltdown-microarchitecture/ .

rep lodsd RCX=0 或 1。(不快也不高效，但微码分支是特殊的，不能从英特尔 CPU 上的分支预测中受益。参见 What setup does REP do?。Andy Glew 提到了微码分支错误预测，但我认为这些与正常分支未命中，因为似乎有固定成本。)

AVX2 vpmaskmovd/q /AVX1 vmaskmovps/pd .对于掩码为 0 的元素，错误会被抑制。即使来自合法地址的全 0 掩码的掩码加载也需要~200 周期的微码辅助和基址+索引寻址模式。)见 section 12.9 CONDITIONAL SIMD PACKED LOADS AND STORES和英特尔优化手册中的表 C-8。 (在 Skylake 上，使用全零掩码存储到非法地址也需要帮助。)
较早的 MMX/SSE2 maskmovdqu 仅存储(并具有 NT 提示)。只有具有 dword/qword(而不是字节)元素的类似 AVX 指令具有加载形式。

AVX512 屏蔽负载

AVX2 收集一些/所有掩码元素。

......也许还有其他我忘记了。 TSX/RTM 事务中的正常负载:故障中止事务而不是引发 #PF。但是您不能指望错误的索引错误，而不仅仅是从附近的某个地方读取虚假数据，因此这并不是真正的条件加载。它也不是 super 快。

另一种可能是 cmov您无条件使用的地址，选择从哪个地址加载。例如如果你有 0从其他地方加载，那会起作用。但是你必须在寄存器中计算表索引，而不是使用寻址模式，所以你可以 cmov最后的地址。
或者只是 CMOV 索引并在表的末尾填充一些零字节，以便您可以从 table + 128 加载.
或者使用分支，它可能会很好地预测很多情况。但对于像法语这样的语言，您会在公共(public)文本中找到低 128 和更高的 Unicode 代码点的混合，但可能不是这样。

代码审查
请注意 [rel]仅在寻址模式中不涉及寄存器(RIP 除外)时才有效。 RIP 相对寻址替换了 2 种冗余方式之一(以 32 位代码)来编码 [disp32] .它使用较短的非 SIB 编码，而 ModRM+SIB 仍然可以编码绝对 [disp32]没有寄存器。 (对于像 [fs: 16] 这样的地址很有用，用于相对于带有段基的线程本地存储的小偏移量。)
如果您只想尽可能使用 RIP 相对寻址，请使用 default rel在您的文件顶部 . [symbol]将是 RIP 相对的，但 [symbol + rax]惯于。不幸的是，NASM 和 YASM 默认为 default abs . [reg + disp32]是一种在与位置相关的代码中索引静态数据的非常有效的方法，只是不要自欺欺人地认为它可以与 RIP 相关。见 32-bit absolute addresses no longer allowed in x86-64 Linux? . [rel ascii_flags + EDI]也很奇怪，因为 您在 x86-64 代码中以寻址模式使用 32 位寄存器 .通常没有理由花费地址大小前缀来将地址截断为 32 位。
但是，在这种情况下，如果您的表位于虚拟地址空间的低 32 位，而您的函数 arg 仅指定为 32 位(因此允许调用者在 RDI 的高 32 位留下垃圾)，实际上是使用胜利 [disp32 + edi]而不是 mov esi,edi或零扩展的东西。如果您是故意这样做的，请务必说明您使用 32 位寻址模式的原因。
但在这种情况下，使用 cmov在索引上将为您零扩展到 64 位。
使用字节表中的 DWORD 加载也很奇怪。您偶尔会跨越缓存线边界并遭受额外的延迟。

@fuz 在索引上展示了一个使用 RIP 相对 LEA 和 CMOV 的版本。
在 32 位绝对地址可以的位置相关代码中，务必使用它来保存指令 . [disp32]寻址模式比 RIP-relative 差(长 1 个字节)，但 [reg + disp32]当位置相关代码和 32 位绝对地址没问题时，寻址模式非常好。 (例如 x86-64 Linux，但不是 OS X，其中可执行文件总是映射到低 32 位之外。)请注意它不是 rel .

; position-dependent version taking advantage of 32-bit absolute [reg + disp32] addressing
; not usable in shared libraries, only non-PIE executables.
ft_isprint:
    mov     eax, 128               ; offset of dummy entry for "not ASCII"
    cmp     edi, eax               ; check if ascii
    cmovae  edi, eax               ; replace with 128 if outside 0..127
              ; cmov also zero-extends EDI into RDI
    movzx   eax, byte [ascii_flags + rdi] ; load table entry
    and     al, flag_print         ; mask the desired flag
      ; if the caller is only going to read / test AL anyway, might as well save bytes here
    ret

如果您的表中的任何现有条目具有与您想要的高输入相同的标志 ，例如也许条目 0你永远不会在隐式长度的字符串中看到，你仍然可以异或零 EAX 并将你的表保持在 128 个字节，而不是 129 个字节。
test r32, imm32占用的代码字节比您需要的多 . ~127 = 0xFFFFFF80将适合符号扩展字节，但不是 TEST r/m32, sign-extended-imm8 编码。 cmp有这样的编码，不过，基本上就像所有其他立即指令一样。
您可以使用 cmp edi, 127 检查 127 以上的未签名/ cmovbe eax, edi或 cmova edi, eax .这节省了 3 个字节的代码大小。或者我们可以使用 cmp reg,reg 节省 4 个字节使用 128我们用于表索引。
对于大多数人来说，数组索引之前的范围检查也比检查高位更直观。 and al, imm8仅为 2 个字节，而 and r/m32, sign-extended-imm8 为 3 个字节.只要调用者只读取 AL，它在任何 CPU 上都不会变慢。在 Sandybridge 之前的 Intel CPU 上，在 AND 到 AL 之后读取 EAX 可能会导致部分寄存器停顿/减速。如果我没记错的话，Sandybridge 不会为读-修改-写操作重命名部分寄存器，而且 IvB 和更高版本根本不会重命名 low8 部分寄存器。
您也可以使用 mov al, [table]而不是 movzx保存另一个代码字节。较早的 mov eax, 128已经打破了对 EAX 旧值的任何错误依赖，因此它不应该有性能下降。但是 movzx不是一个坏主意。
当所有其他条件相同时，较小的代码大小几乎总是更好(对于指令缓存占用空间，有时用于打包到 uop 缓存中)。但是，如果它花费了任何额外的 uops 或引入了任何错误的依赖项，那么在优化速度时就不值得了。