C和C++有符号数溢出是一种未定义行为

本文翻译自《Signed Overflow》。

C和C++语言标准规定,有符号数的溢出是未定义的行为。在C99标准的第6.5节。在C++98标准中,它位于第5节[expr]的第5段。这意味着正确的C/C++程序在计算表达式时绝不能生成有符号数溢出。这也意味着编译器可能会假设程序永远不会产生有符号数溢出。

gcc在做优化时很早就利用了这一事实。例如,考虑这个函数:

int f(int x) { return 0x7ffffff0 < x && x + 32 < 0x7fffffff; }

如果有符号算术只是在溢出时回绕,则这等价于0x7ffffff0 < x,因为将32加到这样的值将产生负数。然而,即使是2001年发布的gcc 2.95.3,也会将此函数优化为只返回0的代码。这是有效的,因为编译器可能会假设在正确的程序中不会发生有符号数溢出,并且x + 32得到一个负数的情况只能从有符号数溢出发生。

最近gcc已经开始使用有符号数溢出这一未定义行为来实现更好的边界测试。特别是,考虑这样的代码:

int f()
{
int i;
int j = 0;
for (i = 1; i > 0; i += i)
++j;
return j;
}

这段代码假设如果它不断地将一个正数加倍,它最终会得到一个负数。也就是说,它期望有符号数溢出以某种方式运行。当前主流的gcc会认为在正确的程序中不会发生有符号数的溢出,并将这段代码编译成无限循环。

一些gcc用户对这种优化感到惊讶,并且在2007年初左右提出了强烈抗议。有一段时间有人建议gcc编译应该始终使用-fwrapv选项-fwrapv告诉编译器将有符号数的溢出视为回绕。这是Java定义有符号数溢出的方式。该选项是在2003年为gcc 3.3引入的。

-fwrapv的缺点是它会抑制优化。大多数程序不会产生有符号数溢出,而且正如我们所见,正确的程序都不会产生。当编译器可以假定不会发生有符号数溢出时,它可以生成更好的代码。这尤其出现在循环中。当循环使用有符号整数索引时,编译器可以做得更好,因为它不必考虑索引溢出的可能性。

考虑这个简单的例子:

int f(int i) { int j, k = 0; for (j = i; j < i + 10; ++j) ++k; return k; }

此函数返回什么?当编译器可以假设有符号数溢出是未定义行为时,此函数将编译为只返回10的代码。使用-fwrapv选项,代码就不那么简单了,因为i可能恰好有一个像0x7ffffff8这样的值,它会在循环期间溢出。虽然这是一个简单的例子,但很明显,像这样的循环总是在实际代码中发生。

然而,gcc确实需要回应社区用户的担忧。我在gcc 4.2中引入了两个新选项。第一个是-fno-strict-overflow,告诉编译器,它可能不会假设有符号数溢出是未定义行为。第二个是-Wstrict-overflow,告诉编译器在使用有符号数溢出这个未定义行为来实现优化的情况下发出警告。使用这些选项,可以检测程序中发生有符号数溢出的情况,并且可以禁用依赖有符号数溢出进行的优化,直到程序修复。-Wstrict-overflow甚至发现了一个很小的情况,即gcc本身依赖于有符号数溢出这个未定义行为,在处理常数0x80000000的除法时。

这自然会引出一个问题:-fwrapv-fno-strict-overflow之间有什么区别?在不使用普通二进制补码算法的处理器上有一个明显的区别:-fwrap需要二进制补码溢出,而-fno-strict-overflow则不需要。然而,目前还没有这种处理器被普遍使用。在实践中,我认为这两个选项生成的代码的行为始终相同。然而,它们对优化器的影响不同。例如,此代码:

int f(int x) { return (x + 0x7fffffff) * 2; }

使用-fwrapv-fno-strict-overflow编译出不同汇编代码。之所以出现这种差异,是因为-fwrapv精确地指定了溢出的行为方式,而-fno-strict-overflow只是说编译器不应该优化溢出。对于当前的编译器,使用-fwrapv(和-O2 -fomit-frame-pointer),我可以看到:

movl $1, %eax
subl 4(%esp), %eax
addl %eax, %eax
negl %eax
ret

而使用-fno-strict-overflow选项我看到:

movl 4(%esp), %eax
leal -2(%eax,%eax), %eax
ret

运算结果一样,但是使用了不同的算法。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注