Why/how gcc 是否编译了此签名溢出测试中的未定义行为,因此它可以在 x86 上运行但不能在 ARM64 上运行?

Why/how does gcc compile the undefined behaviour in this signed-overflow test so it works on x86 but not ARM64?

我正在自学 CSAPP,并且在 运行 断言测试期间 运行 遇到 st运行ge 问题时得到了 st运行ge 结果.

我不知道从什么开始这个问题,所以让我先得到代码(文件名在评论中可见):

// File: 2.30.c
// Author: iBug

int tadd_ok(int x, int y) {
    if ((x ^ y) >> 31)
        return 1;  // A positive number and a negative integer always add without problem
    if (x < 0)
        return (x + y) < y;
    if (x > 0)
        return (x + y) > y;
    // x == 0
    return 1;
}
// File: 2.30-test.c
// Author: iBug

#include <assert.h>

int tadd_ok(int x, int y);

int main() {
    assert(sizeof(int) == 4);

    assert(tadd_ok(0x7FFFFFFF, 0x80000000) == 1);
    assert(tadd_ok(0x7FFFFFFF, 0x7FFFFFFF) == 0);
    assert(tadd_ok(0x80000000, 0x80000000) == 0);
    return 0;
}

和命令:

gcc -o test -O0 -g3 -Wall -std=c11 2.30.c 2.30-test.c
./test

(旁注:命令行中没有任何 -O 选项,但由于它默认为级别 0,显式添加 -O0 应该不会有太大变化。)

以上两个命令 运行 在我的 Ubuntu VM(amd64,GCC 7.3.0)上运行得很好,但是其中一个断言在我的 [=45= 上失败了] phone(AArch64 或 armv8-a,GCC 8.2.0).

2.30-test.c:13: main: assertion "tadd_ok(0x7FFFFFFF, 0x7FFFFFFF) == 0" failed

请注意,第一个断言已通过,因此 int 在平台上保证 运行 为 4 个字节。

所以我在 phone 上启动 gdb 试图获得一些见解:

(gdb) l 2.30.c:1
1       // File: 2.30.c
2       // Author: iBug
3
4       int tadd_ok(int x, int y) {
5           if ((x ^ y) >> 31)
6               return 1;  // A positive number and a negative integer always add without problem
7           if (x < 0)
8               return (x + y) < y;
9           if (x > 0)
10              return (x + y) > y;
(gdb) b 2.30.c:10
Breakpoint 1 at 0x728: file 2.30.c, line 10.
(gdb) r
Starting program: /data/data/com.termux/files/home/CSAPP-2019/ch2/test
warning: Unable to determine the number of hardware watchpoints available.
warning: Unable to determine the number of hardware breakpoints available.

Breakpoint 1, tadd_ok (x=2147483647, y=2147483647)
    at 2.30.c:10
10              return (x + y) > y;
(gdb) p x
 = 2147483647
(gdb) p y
 = 2147483647
(gdb) p (x + y) > y
 = 0
(gdb) c
Continuing.
2.30-test.c:13: main: assertion "tadd_ok(0x7FFFFFFF, 0x7FFFFFFF) == 0" failed

Program received signal SIGABRT, Aborted.
0x0000007fb7ca5928 in abort ()
   from /system/lib64/libc.so
(gdb) d 1
(gdb) p tadd_ok(0x7FFFFFFF, 0x7FFFFFFF)
 = 1
(gdb)

正如您在 GDB 输出中看到的,结果非常不一致,因为达到了 2.30.c:10 上的 return 语句,而 return 值应该是 0,但是函数仍然 returns 1,使断言失败。

请指出我在这里出错的地方。


请尊重我所呈现的。只说它是 UB 而没有关联平台,尤其是 GDB 输出,不会有任何帮助。

有符号整数溢出调用 undefined behavior。您不能通过添加两个数字并检查它们是否以某种方式环绕来检查溢出情况。虽然您 可能 在 x86/x64 系统上摆脱这个问题,但不能保证其他人也会有同样的行为。

然而,您 可以 做的是一些算术运算以及 INT_MAXINT_MIN 来进行检查。

int tadd_ok(int x, int y) {
    if ((x ^ y) >> 31)
        return 1;  // A positive number and a negative integer always add without problem
    if (x < 0)
        return INT_MIN - x < y;
    if (x > 0)
        return INT_MAX - x > y;
    // x == 0
    return 1;
}

表达式 INT_MAX - x > y 在算术上等同于 INT_MAX > x + y 但防止发生溢出。类似地,INT_MIN - x < y 在算术上等同于 INT_MIN < x + y 但防止溢出。

编辑:

如果要强制定义有符号整数溢出,可以使用 gcc 的 -fwrapv 选项。但是,您最好完全避免溢出。

根据 C 标准,有符号整数溢出是未定义的行为,这与保证环绕的无符号溢出不同。

尝试使用最新的 GCC x86-64 和 -O3 将您的代码放在 Godbolt 上。它被优化为:

mov eax, 1
ret 

这是可以接受的。我想为 ARM64 发出了等效的指令序列,但我不知道该体系结构,仅通过查看无法确定。

如前所述,您正在调用未定义的行为。 C 中没有为有符号整数定义溢出。编译器理解,第二个和第三个 if 语句未根据有符号整数定义,因此编译器决定,无论采用什么分支,都不会在定义良好的程序中发生。因此整个函数 tadd_ok 折叠成一个 return 1.

是否禁用优化并不重要:这些 if 语句调用未定义的行为早在优化器开始工作之前就已确定。

启用调试信息的生成也无关紧要,因为这不会改变它生成代码的方式(它只是为解释二进制转储和进程状态的工具添加注释)。

最后但同样重要的是,当您让 GDB 打印语句 (x+y)>y 的结果时,它会在 C 编译范围之外执行此操作,但根据 "running on the metal" 指令。 After C 不是唯一编译为二进制的语言。虽然有符号整数下溢在 C 中是未定义的,但它可能在某些不同的语言中有完美的定义;并且您可能也希望能够在此类程序上使用 GDB。当将 p (x+y)>y 的输出与 C 语句 (x+y)>yxysigned int 的输出进行比较时,您是在将橙子与苹果进行比较;它们是非常不同的东西。

符号溢出是 ISO C 中的未定义行为。您不能可靠地导致它,然后然后检查它是否发生。

在表达式 (x + y) > y; 中,允许编译器假定 x+y 不会溢出(因为那将是 UB)。因此,它优化到检查 x > 0.(是的,真的,gcc 即使在 -O0 也会这样做)。

这个优化是 gcc8 中的新功能。在 x86 和 AArch64 上是一样的;你一定在 AArch64 和 x86 上使用了不同的 GCC 版本。 (即使在 -O3、gcc7.x 和更早的时候(故意?)错过了这个优化。clang7.0 也没有这样做。他们实际上做了 32 位加法和比较。他们也错过了优化 tadd_okreturn 1,或 add 并检查溢出标志(ARM 上的 V,x86 上的 OF)。Clang 的优化 asm 是 >>31、OR 和一个 XOR 运算,但 -fwrapv 实际上更改了该 asm,因此它可能没有进行完整的溢出检查。)

您可以说 gcc8 "breaks" 是您的代码,但就合法/可移植 ISO C 而言,它实际上已经被破坏。gcc8 刚刚揭示了这一事实。


为了看得更清楚,让我们将该表达式分离到一个函数中。 gcc -O0 无论如何都会单独编译每个语句,因此仅在 x<0 时运行的信息不会影响 tadd_ok 函数中此语句的 -O0 代码生成。

// compiles to add and checking the carry flag, or equivalent
int unsigned_overflow_test(unsigned x, unsigned y) {
    return (x+y) >= y;    // unsigned overflow is well-defined as wrapping.
}

// doesn't work because of UB.
int signed_overflow_expression(int x, int y) {
    return (x+y) > y;
}

On the Godbolt compiler explorer with AArch64 GCC8.2 -O0 -fverbose-asm:

signed_overflow_expression:
    sub     sp, sp, #16       //,,      // make a stack fram
    str     w0, [sp, 12]      // x, x   // spill the args
    str     w1, [sp, 8]       // y, y
   // end of prologue

   // instructions that implement return (x+y) > y; as return  x > 0
    ldr     w0, [sp, 12]      // tmp94, x
    cmp     w0, 0     // tmp94,
    cset    w0, gt  // tmp95,                  // w0 = (x>0) ? 1 : 0
    and     w0, w0, 255       // _1, tmp93     // redundant

  // epilogue
    add     sp, sp, 16        //,,
    ret     

GCC -ftree-dump-original-optimized 甚至会在完成此优化后将其 GIMPLE 变回类 C 代码(来自 Godbolt link):

;; Function signed_overflow_expression (null)
;; enabled by -tree-original

{
  return x > 0;
}

不幸的是,即使使用 -Wall -Wextra -Wpedantic,也没有 warning 进行比较。这不是 平凡 正确的;它仍然取决于 x.

优化后的 asm 不出所料 cmp w0, 0 / cset w0, gt / ret0xff 的 AND 是多余的。 cset is an alias of csinc,使用零寄存器作为两个来源。所以它会产生 0 / 1。对于其他寄存器,csinc 的一般情况是有条件的 select 和任何 2 个寄存器的增量。

无论如何,cset 是 AArch64 等同于 x86 setcc,用于将标志条件转换为寄存器中的 bool


如果您希望您的代码按照编写的方式工作,您需要 compile with -fwrapv 使其在 C 变体中具有明确定义的行为 -fwrapv 使 GCC 工具。默认为 -fstrict-overflow,如 ISO C 标准。

如果你想在现代 C 中检查有符号溢出,你需要编写检测溢出的检查而不实际导致溢出。这更难,更烦人,并且是编译器编写者和(某些)开发人员之间争论的焦点。他们争辩说,围绕未定义行为的语言规则并不意味着在为目标机器编译时将其用作 "gratuitously break" 代码的借口,这在 asm 中是有意义的。但是现代编译器大多只实现 ISO C(具有一些扩展和额外定义的行为),即使在为 x86 和 ARM 等目标体系结构编译时也是如此,在这些体系结构中,有符号整数没有填充(因此可以很好地包装),并且不会陷入溢出。

所以你可以在 war 中说 "shots fired",将 gcc8.x 更改为实际上 "breaking" 这样的不安全代码。 :P

Detecting signed overflow in C/C++ and How to check for signed integer overflow in C without undefined behaviour?


因为有符号加法和无符号加法在 2 的补码中是相同的二元运算,您可以也许只是转换为 unsigned 来进行加法,然后返回进行有符号比较。这将使您的函数版本在 "normal" 实现上是安全的:2 的补码,并且在 unsignedint 之间进行转换只是对相同位的重新解释。

这不能有 UB,它不会给出补码或 sign/magnitude C 实现的正确答案。

return  (int)((unsigned)x + (unsigned)y) > y;

这编译(使用 gcc8.2 -O3 for AArch64)到

    add     w0, w0, w1            // x+y
    cmp     w0, w1                // x+y  cmp  y
    cset    w0, gt
    ret

如果您将 int sum = x+y 编写为独立于 return sum < y 的 C 语句,则在禁用优化的情况下,此 UB 对于 gcc 将不可见。 但是作为同一表达式的一部分,即使 gcc 和默认 -O0 也可以看到它。

编译时可见的 UB 各种糟糕。在这种情况下,只有特定范围的输入会产生 UB,因此编译器假定它不会发生。如果在执行路径上看到无条件 UB,则优化编译器可以假定该路径永远不会发生。 (在没有分支的函数中,它可以假定函数从未被调用,并将其编译为一条非法指令。)有关编译时可见 UB 的更多信息,请参阅

(-O0 并不意味着 "no optimization",它意味着除了已经需要通过 gcc 的内部表示进行转换之外,没有 额外的 优化适用于任何目标平台的 asm。@Basile Starynkevitch 在中解释 Disable all optimization options in GCC)

一些其他编译器可能会 "turn their brains off" 禁用优化,并做一些更接近于将 C 音译成 asm 的事情,但 gcc 不是 那样。例如,gcc 仍然使用乘法逆来除以 -O0 处的常数。 (Why does GCC use multiplication by a strange number in implementing integer division?) 所有其他 3 个主要的 x86 编译器 (clang/ICC/MSVC) 使用 div.

我知道您要求的是 UB 以外的其他东西,但恐怕这是导致您的问题的原因,即使您使用的是 -O0。让我们看看生成的程序集。

我已将您的功能简化为此以隔离 UB:

int tadd_ok(int x, int y) {
    if (x > 0)
        return (x + y) > y;

    return 1;
}

为 AArch64 (-O0 -x c -march=armv8-a) 生成的输出:

tadd_ok:
        sub     sp, sp, #16
        str     w0, [sp, 12]
        str     w1, [sp, 8]
        ldr     w0, [sp, 12]
        cmp     w0, 0
        ble     .L2           ; if (x <= 0) goto return stmt
        ldr     w0, [sp, 12]  ; here we are runnig (x + y) > y branch
        cmp     w0, 0         ; x is compared to zero
        cset    w0, gt        ; return value is set to (x > 0)
        and     w0, w0, 255
        b       .L3
.L2:
        mov     w0, 1
.L3:
        add     sp, sp, 16
        ret

请记住,由于不允许有符号整数溢出,因此表达式 (x + y) 始终大于 y,除非 x <= 0。 GCC 在 优化器启动之前知道这个 ,所以它将 (x + y) > y 替换为 x > 0.

尽管它只是进行了相同的检查,但它似乎忘记了这一点 - 没有启用优化的副作用。

您可以将上面的 C 代码替换为:

int tadd_ok(int x, int y) {
    if (x > 0)
        return x > 0;

    return 1;
}

并且输出不变:

tadd_ok:
        sub     sp, sp, #16
        str     w0, [sp, 12]
        str     w1, [sp, 8]
        ldr     w0, [sp, 12]
        cmp     w0, 0
        ble     .L2
        ldr     w0, [sp, 12]
        cmp     w0, 0
        cset    w0, gt
        and     w0, w0, 255
        b       .L3
.L2:
        mov     w0, 1
.L3:
        add     sp, sp, 16
        ret

有了上面的代码,优化器会做什么就很清楚了:

tadd_ok:
        mov     w0, 1
        ret

您使用的其他选项不会改变任何东西,平台无关紧要,因为没有生成附加指令。

至于 GDB:它通过使用编译器生成的相同代码在被调试进程中执行复杂表达式来运行复杂表达式,因此输出不会有任何不同。因此评估 tadd_ok(0x7FFFFFFF, 0x7FFFFFFF) 运行相同的代码。

我想补充一点,在 GCC 中有一个简单的方法来处理带溢出的有符号加法并定义它。您可以使用 https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html 中记录的内置函数来执行定义为回绕的签名操作(add、sub、mul),它会告诉您操作是否溢出。

bool __builtin_add_overflow(type1 a, type2 b, type3 *res)

例如,您可以像这样重写您的函数:

int tadd_ok(int x, int y) {
    int result;
    return !__builtin_add_overflow(x, y, &result);
    // result now contains (int)((unsigned int)x + (unsigned int)y)
}