为什么 mod 2^n 对有符号数使用 CLTD 指令

Question

所以我知道当你对无符号操作执行 x mod 2^n 时，编译器会简单地将该操作转换为 x & (2^n - 1)。

但是当我查看使用带符号数的编译器实现时，例如

int signed_rem8(int x) { return x %8; }

我得到这样的结果 (https://godbolt.org/z/xY3Ef6WEc):

 movl    -4(%rbp), %eax
 cltd
 shrl    , %edx
 addl    %edx, %eax
 andl    , %eax
 subl    %edx, %eax

这背后的逻辑是什么？

Answer 1

这是由于带有负数的 modulo 运算符的行为。

此运算符的行为是 a/b 向零四舍五入，a%b returns 一个数字 (a/b)*a + a%b 等于 a （参见 ISO/IEC 9899:2011 §6.5.5 ¶6）。由于“向零舍入”意味着对负结果向上舍入，对正结果向下舍入，这实际上意味着余数取分子的符号。

为了正确实现此行为，编译器使用 cltd 指令（sign-extending eax 到 edx:eax），如下所示：

movl    -4(%rbp), %eax  # load numerator x
cltd                    # edx = x >= 0 ? 0 : -1
shrl    , %edx       # edx = x >= 0 ? 0 :  7
addl    %edx, %eax      # eax = x >= 0 ? x : x + 7
andl    , %eax        # eax = x >= 0 ? x&7 : x-1 & 7
subl    %edx, %eax      # eax = x >= 0 ? x&7 : (x-1 & 7) - 7

因此，如果是正数，我们得到 0 到 7 范围内的正余数，而如果是负数，我们得到 −7 到 0 范围内的负余数。

在这两种情况下，余数在数值上都是正确的，因为余数应该代表余数 class x mod 8，并且正余数和负余数都是那个。

您可能会看到其他编译器使用略有不同的代码来解决这个问题，但总体思路是相似的。

为什么 mod 2^n 对有符号数使用 CLTD 指令

Why does mod 2^n use CLTD instruction for signed numbers

c

assembly

optimization

x86

compiler-optimization