长整型的二进制补码

Question

长整型的二进制补码

assemblyx86-64micro-optimizationtwos-complement

9

我想使用Intel I64汇编语言进行长整数运算（128位），并需要创建一个二进制补码。假设我的正值存储在RDX：RAX中。

"翻转位并加1"可以完成2的补码。因此，最朴素的实现方式为（4条指令和14字节的代码）：

  NOT RAX
  NOT RDX
  ADD RAX,1   ; Can't use INC, it doesn't set Carry
  ADC RDX,0

当我使用NEG指令替换NOT指令对RAX进行操作时，它为我执行了“+1”的操作，但进位标志是错误的。NEG RAX会在RAX为零时清除进位标志，但我只需要在此情况下保留进位标志。因此，下一个最好的方法可能是（4条指令和11个字节的代码）：

  NOT RDX
  NEG RAX
  CMC
  ADC RDX,0                  ; fixed, thanks lurker

仍然是4条指令。但是我可以使用减法-1，而由于SBB将进位位添加到被减数中，当进位标志清除时，我将添加+1。因此，我的下一个最佳尝试是这个，只需3条指令和10字节的代码：

   NOT RDX
   NEG RAX
   SBB RDX,-1

从我冗长的文本中可以看出，这并不容易理解。在汇编语言中有更好、更易懂的方法来实现级联2的补码吗？

- Rolf

4

你似乎认为“更好”的意思是“代码更短”，但这并不适用于一个乱序多标量处理器，例如x86-64。我想说，你的第一种实现方式最容易理解，而且如果它们全部执行时间相同，我也不会感到惊讶。 - mcleod_ideafix

顺便问一下：您考虑过使用XMM寄存器吗？它们足够宽，可以容纳128位数字，并且（我没有检查）可能具有处理整数的指令。 - mcleod_ideafix

3

他们没有，所以你仍然需要手动处理进位问题。 - harold

1

谢谢@lurker，我已经修复了它。是的，我考虑过XMM寄存器。它们用于整数向量，其中进位传播不是选项。因此，它们为您提供在未检测到溢出或整数饱和之间进行选择的选择。对于我的目的来说不好。 - Rolf

4

根据Agner Fog的指令表，令人惊讶的是在现代微架构中，“CMC”具有低延迟和高吞吐量，因此第二个版本可能很有竞争力。另一方面，考虑依赖链：1: ADC 通过标志位依赖于 NOT/ADD，依赖于 NOT。2: ADC 依赖于 NOT/CMC 依赖于 NEG。3: SBB 依赖于 NOT/NEG。我认为你已经找到了一个非常聪明的方式来制作最后一个版本。 - EOF

显示剩余4条评论

2个回答

3

顺便提一下，对于EDX：EAX或DX：AX的2个寄存器的数取反，在32位或16位模式下是相同的。使用相同的指令序列。

复制和取反，@phuclv的答案显示了有效的编译器输出。最好的方法是将目标异或零，并使用sub/sbb。

在AMD上，这需要4个前端UOP，在Intel Broadwell及更高版本上也是如此。在Broadwell之前的英特尔处理器上，sbb reg，reg是2个UOP。异或零不在关键路径上（可以在待取反的数据准备好之前完成），因此对于高半部分的总延迟为2或3个周期。当然，低半部分的延迟为1个时钟周期。

Clang的mov/neg对于低半部分可能在Ryzen上更好，因为其具有用于GP整数的mov-elimination，但仍需要用于xor-zeroing的ALU执行单元。但是对于旧CPU，它会在延迟上放置一个mov。但是通常对于可以使用任何ALU端口的指令，后端ALU压力并不像前端瓶颈那样重要。

要就地取反，请使用neg从0中减去

neg   rdx              ; high half first
neg   rax             ; subtract RDX:RAX from 0
sbb   rdx, 0          ; with carry from low to high half

neg 和从0开始的 sub 在设置标志和性能方面是完全等价的。

当使用立即数为0时，ADC/SBB仅在Intel SnB/IvB/Haswell架构中作为单个uop的特殊情况处理。但在 Nehalem 及更早的架构中仍然需要2个uops。不过如果没有mov消除的话，将RAX中的值移动到另一个寄存器中并将其再次通过 SBB 放回 RDX 这一过程会变得更慢。

低半部分（在RAX中）在准备好后的第一个周期中就已经可以使用 neg 了（因此乱序执行后续代码可以开始使用低半部分）。

高半部分的 neg rdx 可以与低半部分并行运行。然后，sbb rdx,0 必须等待来自 neg rdx 和 neg rax 的CF计算出来，所以它要么在低半部分后的1个周期准备好，要么在输入高半部分准备好2个周期后准备好。

与问题中的任何序列相比，上述序列在非常常见的Intel CPU上使用更少的uops。在Broadwell及以后的（单uop SBB，不仅适用于立即数0）。

;; equally good on Broadwell/Skylake, and AMD.  But worse on Intel SnB through HSW
NOT RDX
NEG RAX
SBB RDX,-1     ; can't use the imm=0 special case

任何4条指令序列都明显不是最优的，因为它们总共使用更多uops。其中一些具有更差的ILP / 依赖链 / 延迟，例如低半部分关键路径上的2条指令，或者高半部分的3个周期链。

- Peter Cordes

我有一段时间没有关注这个问题了。非常感谢，你提供了很棒的见解。 - Rolf

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- phuclv · Accepted Answer

指令越短或指令数量越少并不一定意味着执行速度更快，因为每个指令的延迟和吞吐量都是不同的。

例如，过时的指令，如enter, dad, loop等，将非常缓慢，它们只是为了向后兼容而存在。甚至inc比add还要慢。与您在某些μarchs上使用的cmc相同。

因此，一系列低延迟指令可以并行执行，将更快地工作。一些常见的指令组甚至可以融合成一个单独的宏操作。编译器的优化器总是知道这一点，并选择最适合的指令进行发射。

对于此代码片段：

__int128 negate(__int128 x)
{
    return -x;
}

ICC 19.0.1 将生成以下指令

    xor       edx, edx                                      #3.13
    xor       eax, eax                                      #3.13
    sub       rax, rdi                                      #3.13
    sbb       rdx, rsi                                      #3.13

前两个异或指令的成本为零 μop，因为它们在寄存器重命名阶段处理。现在你只有2条指令需要执行

您可以在上面的Godbolt链接中切换编译器，以查看不同编译器包括MSVC（不幸的是它还没有128位类型）的否定方式。以下是GCC和Clang的结果

GCC 8.3：

    mov     rax, rdi
    neg     rax
    mov     rdx, rsi
    adc     rdx, 0
    neg     rdx

Clang：

    mov     rax, rdi
    xor     edx, edx
    neg     rax
    sbb     rdx, rsi

正如你所看到的，Clang也仅使用了3条指令（减去第一条将数据从输入参数移动到必要目标的指令）。但是像xor reg, reg一样，mov也可以是“免费”的。

如果你优化空间（例如在某些高缓存未命中的情况下），情况可能会有所不同，因为某些立即数和指令很长。

它是否更快需要进行微基准测试。但在英特尔CPU上，英特尔编译器（ICC）通常比其他编译器实现更高的性能，因为它更好地理解了体系结构。

请注意，该操作称为否定，而不是二进制补码，后者是一种编码负数的方式。