为什么整数除以 -1(负一)会导致 FPE?

Why does integer division by -1 (negative one) result in FPE?

我的任务是解释 C 代码(运行 在 x86 上)的一些看似 奇怪的行为。我可以很容易地完成其他所有事情,但是这个真的让我很困惑。

Code snippet 1 outputs -2147483648

int a = 0x80000000;
int b = a / -1;
printf("%d\n", b);

Code snippet 2 outputs nothing, and gives a Floating point exception

int a = 0x80000000;
int b = -1;
int c = a / b;
printf("%d\n", c);

我很清楚代码片段 1 (1 + ~INT_MIN == INT_MIN) 结果的原因,但我不太明白整数除以 -1 如何生成 FPE,我也无法在我的 Android phone (AArch64, GCC 7.2.0)。 Code 2 只是输出与 Code 1 相同的结果,没有任何异常。它是 x86 处理器的隐藏 bug 功能吗?

作业没有说明任何其他内容(包括 CPU 架构),但由于整个课程都是基于桌面 Linux 发行版,您可以放心地假设它是现代 x86。


编辑:我联系了我的朋友,他在 Ubuntu 16.04(Intel Kaby Lake,GCC 6.3.0)上测试了代码。结果与指定的任何内容一致(代码 1 输出所述内容,代码 2 因 FPE 而崩溃)。

undefined behavior very bad 事情可能会发生,有时确实会发生。

你的问题在 C 中没有意义(阅读 Lattner on UB)。但是您可以获得汇编代码(例如由 gcc -O -fverbose-asm -S 生成)并关心机器代码行为。

在 x86-64 上,Linux 整数溢出(以及整数除以零,IIRC)给出了 SIGFPE 信号。参见 signal(7)

顺便说一句,传闻在 PowerPC 整数除以零在机器级别给出 -1(但一些 C 编译器生成额外的代码来测试这种情况)。

您问题中的代码是 C 中的未定义行为。生成的汇编代码具有一些已定义的行为(取决于 ISA 和处理器)。

(完成作业是为了让您阅读更多关于 UB 的信息,特别是 Lattner 's blog,您应该 绝对 阅读)

有符号 int 二进制补码除法未定义,如果:

  1. 除数为零,或
  2. 被除数是 INT_MIN(==0x80000000 如果 intint32_t),除数是 -1(二进制补码, -INT_MIN > INT_MAX,这会导致整数溢出,这是C中未定义的行为)

https://www.securecoding.cert.org 建议在检查此类边缘情况的函数中包装整数运算)

由于您是通过违反规则 2 调用未定义的行为,所以任何事情都有可能发生,并且当它发生时,您平台上的这个特定的任何事情恰好是由您的处理器生成的 FPE 信号。

在 x86 上,如果你 divide 通过 实际使用 idiv 操作(这对于常量参数来说并不是必需的,不是即使对于已知为常数的变量,但无论如何它还是发生了),INT_MIN / -1 是导致 #DE(divide 错误)的情况之一。这确实是商超出范围的特殊情况,通常这是可能的,因为 idiv divides 一个额外的 wide dividend by the divisor,如此多的组合会导致溢出 - 但 INT_MIN / -1 是唯一不是您通常可以从中访问的 div-by-0 的情况高级语言,因为它们通常不公开额外的 wide-dividend 功能。

Linux 烦人地将#DE 映射到 SIGFPE,这可能让第一次处理它的每个人都感到困惑。

这里发生了四件事:

  • gcc -O0 行为解释了两个版本之间的差异:idivneg。 (虽然 clang -O0 碰巧用 idiv 编译了它们)。以及为什么即使使用编译时常量操作数也会得到这个。

  • x86 idiv 错误行为与 ARM 上除法指令的行为

  • 如果整数运算导致信号被传递,POSIX 要求它是 SIGFPE:On which platforms does integer divide by zero trigger a floating point exception? 但是 POSIX 不需要 需要对任何特定的整数运算进行补漏白。 (这就是允许 x86 和 ARM 不同的原因)。

    单一 Unix 规范 defines SIGFPE as "Erroneous arithmetic operation". It's confusingly named after floating point, but in a normal system with the FPU in its default state, only integer math will raise it. On x86, only integer division. On MIPS, a compiler could use add instead of addu for signed math, so you could get traps on signed add overflow. (gcc uses addu even for signed,但未定义行为检测器可能会使用 add。)

  • C 未定义行为规则(有符号溢出,特别是除法)让 gcc 发出可以在这种情况下陷入陷阱的代码。


没有选项的 gcc 与 gcc -O0.

相同

-O0 Reduce compilation time and make debugging produce the expected results. This is the default.

这解释了你的两个版本之间的区别:

gcc -O0不仅不尝试优化,它还主动反优化使asm独立实现函数内的每个C语句。这允许 gdb's jump command to work safely, letting you jump to a different line within the function and act like you're really jumping around in the C source. Why does clang produce inefficient asm with -O0 (for this simple floating point sum)? 解释更多关于 -O0 如何以及为什么编译它的方式。

它也不能对语句之间的变量值进行任何假设,因为您可以使用 set b = 4 更改变量。这显然对性能有灾难性的影响,这就是为什么 -O0 代码 运行 比正常代码慢几倍,以及为什么 . It also makes -O0 asm output ,因为所有 storing/reloading,并且缺少即使是最明显的优化。

int a = 0x80000000;
int b = -1;
  // debugger can stop here on a breakpoint and modify b.
int c = a / b;        // a and b have to be treated as runtime variables, not constants.
printf("%d\n", c);

我把你的代码放在 Godbolt 函数中 compiler explorer 以获得这些语句的 asm。

要评估 a/bgcc -O0 必须发出代码以从内存中重新加载 ab,而不对它们的值做出任何假设。

但是 with int c = a / -1;,你不能用调试器 -1 改变 ,所以 gcc 可以而且确实以同样的方式实现了那个语句将使用 x86 neg eax 或 AArch64 neg w0, w0 指令实现 int c = -a;,并由加载(a)/存储(c)包围。在 ARM32 上,它是 rsb r3, r3, #0(反向减法:r3 = 0 - r3)。

然而,clang5.0 -O0 没有做那个优化。它仍然使用 idiv 作为 a / -1,因此这两个版本在 x86 上都会出现 clang 故障。为什么 gcc 完全“优化”?参见 Disable all optimization options in GCC。 gcc 总是通过内部表示进行转换,而 -O0 只是生成二进制文件所需的最少工作量。它没有试图使 asm 尽可能像源代码的“愚蠢和文字”模式。


x86 idiv 与 AArch64 sdiv:

x86-64:

    # int c = a / b  from x86_fault()
    mov     eax, DWORD PTR [rbp-4]
    cdq                                 # dividend sign-extended into edx:eax
    idiv    DWORD PTR [rbp-8]           # divisor from memory
    mov     DWORD PTR [rbp-12], eax     # store quotient

imul r32,r32 不同,没有没有被除数上半部分输入的 2 操作数 idiv。无论如何,这并不重要; gcc 仅将它与 edx = eax 中符号位的副本一起使用,因此它实际上是在执行 32b / 32b => 32b 商 + 余数。 As documented in Intel's manualidiv 引发#DE:

  • 除数 = 0
  • 签名的结果(商)对于目标来说太大了。

如果使用全范围的除数,很容易发生溢出,例如对于 int result = long long / int 具有单个 64b / 32b => 32b 划分。但是 gcc 不能做那种优化,因为它不允许编写会出错的代码,而不是遵循 C 整数提升规则并进行 64 位除法和 then t运行迎合 int。它还

进行 32b / 32b 除法时(使用 cdq),唯一可以溢出的输入是 INT_MIN / -1。 “正确的”商是一个 33 位有符号整数,即带有前导零符号位的正 0x80000000 使其成为正 2 的补码有符号整数。由于这不适合 eaxidiv 引发了 #DE 异常。然后内核传递 SIGFPE.

AArch64:

    # int c = a / b  from x86_fault()  (which doesn't fault on AArch64)
    ldr     w1, [sp, 12]
    ldr     w0, [sp, 8]          # 32-bit loads into 32-bit registers
    sdiv    w0, w1, w0           # 32 / 32 => 32 bit signed division
    str     w0, [sp, 4]

ARM 硬件除法指令不会引发被零除或 INT_MIN/-1 溢出的异常。 Nate Eldredge 评论道:

The full ARM architecture reference manual states that UDIV or SDIV, when dividing by zero, simply return zero as the result, "without any indication that the division by zero occurred" (C3.4.8 in the Armv8-A version). No exceptions and no flags - if you want to catch divide by zero, you have to write an explicit test. Likewise, signed divide of INT_MIN by -1 returns INT_MIN with no indication of the overflow.

AArch64 sdiv documentation 没有提到任何例外情况。

但是,整数除法的软件实现可能会引发:http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.faqs/ka4061.html。 (默认情况下,gcc 在 ARM32 上使用库调用除法,除非您设置具有硬件除法的 -mcpu。)


C 未定义的行为。

因为INT_MIN / -1在C中是未定义的行为,就像所有有符号整数溢出一样。 这允许编译器在 x86 等机器上使用硬件除法指令而不检查特殊情况。如果它必须不是错误,未知输入将需要运行-time compare-and branch checks,没有人希望 C 要求这样做。


更多关于 UB 的后果:

启用优化后,编译器可以假设aba/b[=213=时仍然有它们的设置值]s。然后它可以看到程序有未定义的行为,因此可以做任何它想做的事。 gcc 选择像 -INT_MIN.

那样生成 INT_MIN

在 2 的补码系统中,最负数是它自己的负数。对于 2 的补码,这是一个令人讨厌的极端情况,因为它意味着 abs(x) 仍然可以为负数。 https://en.wikipedia.org/wiki/Two%27s_complement#Most_negative_number

int x86_fault() {
    int a = 0x80000000;
    int b = -1;
    int c = a / b;
    return c;
}

为 x86-64

使用 gcc6.3 -O3 编译
x86_fault:
    mov     eax, -2147483648
    ret

clang5.0 -O3 编译为(即使使用 -Wall -Wextra` 也没有警告):

x86_fault:
    ret

未定义行为确实是完全未定义的。编译器可以随心所欲,包括在函数入口处返回 eax 中的任何垃圾,或加载 NULL 指针和非法指令。例如对于 x86-64 使用 gcc6.3 -O3:

int *local_address(int a) {
    return &a;
}

local_address:
    xor     eax, eax     # return 0
    ret

void foo() {
    int *p = local_address(4);
    *p = 2;
}

 foo:
   mov     DWORD PTR ds:0, 0     # store immediate 0 into absolute address 0
   ud2                           # illegal instruction

你的 -O0 案例没有让编译器在编译时看到 UB,所以你得到了“预期的”asm 输出。

另请参阅 What Every C Programmer Should Know About Undefined Behavior(Basile 链接的同一个 LLVM 博客 post)。

这两种情况都很奇怪,因为第一种情况是 -2147483648 除以 -1,应该得到 2147483648,而不是您收到的结果。除以 -1(作为乘法)应将被除数的符号更改为正数。但是 int 中没有这样的正数(这就是引发 U.B 的原因)

0x80000000 不是 32 位体系结构(如标准中所述)中的有效 int 数字,它表示二进制补码中的数字。如果你计算它的负值,你会再次得到它,因为它在零附近没有相反的数字。 当你用带符号的整数进行算术运算时,它适用于整数加法和减法(总是小心,因为当你将最大值添加到某个 int 时你很容易溢出)但是你不能安全地使用它来乘法或除法。所以在这种情况下,您正在调用 未定义的行为。您总是在溢出时使用带符号的整数调用未定义的行为(或实现定义的行为,相似但不相同),因为实现在实现方面差异很大。

我将尝试解释可能发生的情况(没有信任),因为编译器可以自由地做任何事情,也可以什么都不做。

具体来说,0x80000000用二进制补码表示就是

1000_0000_0000_0000_0000_0000_0000

如果我们补这个数,我们得到(先补所有位,然后加一)

0111_1111_1111_1111_1111_1111_1111 + 1 =>
1000_0000_0000_0000_0000_0000_0000  !!!  the same original number.

令人惊讶的是相同的数字....你有一个溢出(这个数字没有对应的正值,因为我们在改变符号时溢出)然后你取出符号位,用

屏蔽
1000_0000_0000_0000_0000_0000_0000 &
0111_1111_1111_1111_1111_1111_1111 =>
0000_0000_0000_0000_0000_0000_0000

这是你用作股息的数字。

但正如我之前所说,这就是您的系统上可能发生的情况,但不确定,正如标准所说,这是 未定义的行为,因此,您可以从你的 computer/compiler.

得到任何不同的行为

您得到的不同结果可能是第一个操作由编译器完成,而第二个操作由程序本身完成的结果。在第一种情况下,您将 0x8000_0000 分配给变量,而在第二种情况下,您 正在计算程序中的值 。这两种情况都是未定义的行为,您会看到它发生在您的眼前。

#注意 1

就编译器而言,标准没有说明必须实现的 int 的有效范围(标准通常不包括 0x8000...000 二进制补码架构) 0x800...000 在二进制补码体系结构中的正确行为应该是,因为它具有该类型整数的最大绝对值,所以在将数字除以它时给出 0 的结果。但是硬件实现通常不允许除以这样的数字(因为他们中的许多人甚至没有实现有符号整数除法,而是从无符号除法中模拟它,所以很多人只是简单地提取符号并进行无符号除法)这需要在除法之前检查,正如标准所说 未定义的行为 ,允许实现自由地避免这种检查,并且不允许除以该数字。他们只是 select 从 0x8000...0010xffff...fff 的整数范围,然后从 0x000..00000x7fff...ffff,不允许值 0x8000...0000 无效.