编译器优化可能会导致整数溢出。可以吗？

Question

我有一个int x。为简单起见，假设ints 占据范围 -2^31 到 2^31-1。我想计算2*x-1. 我允许x为任何值 0 <= x<= 2^30。如果我计算 2*(2^30)，我会得到 2^31，这是整数溢出。

一种解决方案是计算2*(x-1)+1. 比我想要的多了一项减法，但这不应该溢出。但是，编译器会将其优化为2*x-1. 这是源代码的问题吗？这是可执行文件的问题吗？

这是 Godbolt 的输出2*x-1：

func(int):                               # @func(int)
        lea     eax, [rdi + rdi]
        dec     eax
        ret

这是 Godbolt 的输出2*(x-1)+1：

func(int):                               # @func(int)
        lea     eax, [rdi + rdi]
        dec     eax
        ret

Answer 1

正如Miles暗示的那样：C++ 代码文本受 C++ 语言规则的约束（整数溢出=坏），但编译器仅受 cpu 规则的约束（溢出=ok）。允许进行代码不允许的优化。

但不要以此作为偷懒的借口。如果您编写未定义的行为，编译器会将其视为提示并执行其他优化，从而导致您的程序执行错误的操作。

Answer 2

仅仅因为有符号整数溢出在 C++ 语言级别没有明确定义，并不意味着在汇编级别也是如此。由编译器发出在您的目标 CPU 架构上明确定义的汇编代码。

我很确定本世纪制造的每个 CPU 都使用了二进制补码有符号整数，并且溢出对于它们来说是完美定义的。2*x这意味着简单地计算，让结果溢出，然后减去 1，让结果下溢回来是没有问题的。

许多这样的 C++ 语言级规则的存在是为了掩盖不同的 CPU 架构。在这种情况下，有符号整数溢出是未定义的，因此针对使用例如带符号整数的补码或符号/数值表示形式的CPU的编译器不会被迫添加额外的指令来符合二进制补码的溢出行为。

但是，不要假设您可以使用在目标 CPU 上明确定义但在 C++ 中未定义的构造并获得您期望的答案。C++ 编译器假设执行优化时不会发生未定义的行为，因此，如果您的代码不是定义良好的 C++，它们可以并且将会生成与您期望的代码不同的代码。

Answer 3

ISO C++ 规则适用于您的源代码（始终适用，无论目标计算机如何）。不适用于编译器选择制作的汇编，特别是对于有符号整数包装正常工作的目标。

“好像”规则要求函数的 asm 实现对于抽象机不会遇到有符号整数溢出（或其他未定义行为）的每个输入值产生与 C++ 抽象机相同的结果。 asm 如何产生这些结果并不重要，这就是 as-if 规则的全部要点。 在某些情况下，就像您的情况一样，最有效的实现会包装和解开抽象机不会的某些值。（或者一般来说，不要在抽象机为unsigned或 gcc所做的地方换行-fwrapv。）

C++ 抽象机中的 UB 有符号整数溢出的一个影响是，它允许编译器将int循环计数器优化为指针宽度，而不是每次通过循环或类似的事情都重新进行符号扩展。此外，编译器可以推断值范围限制。但这与他们将逻辑实现到某些目标机器的汇编中的方式完全不同。UB 并不意味着“必须失败”，事实上恰恰相反，除非您使用-fsanitize=undefined. gcc -fwrapv如果您使用比 ISO C++ 实际提供的更多保证来解释源代码（加上实现超出此范围的任何保证，就像您使用.），那么优化器可以更自由地制作与源代码不匹配的 asm。

对于像 之类的表达式x/2，每种可能int x都有明确定义的行为。对于2*x，编译器可以假设x >= INT_MIN/2和x <= INT_MAX/2，因为较大的量级将涉及 UB。

2*(x-1)+1x意味着from(INT_MIN+1)/2到的合法值范围(INT_MAX+1)/2。例如，在 32 位 2 的补码目标上，-1073741823(0xc0000001) 到1073741824(0x40000000)。从积极的一面来看，2*0x3fffffff不会溢出，不会因增量而换行，因为2*x是偶数。

2*x - 1x意味着fromINT_MIN/2 + 1到的合法值范围INT_MAX/2。例如，在 32 位 2 的补码目标上，-1073741823(0xc0000001) 到1073741823(0x3fffffff)。因此表达式可以产生的最大值是2^n - 3，因为 INT_MAX 将为奇数。

在这种情况下，较复杂表达式的合法值范围是较简单表达式的超集，但通常情况并非总是如此。

x他们为每个明确定义的输入产生相同的结果。x86 asm（其中包装是明确定义的）可以像其中一个或另一个一样工作，可以实现其中任何一个，为所有非 UB 情况生成正确的结果。因此，如果编译器不能为两者提供相同的高效汇编，那么编译器就会做得很糟糕。

一般来说，2 的补码和无符号二进制整数数学是可交换和结合的（对于数学上正确的运算，如+和*），编译器可以而且应该充分利用。例如，重新排列a+b+c+d以(a+b)+(c+d)缩短依赖链。（请参阅Why does GCC optimization a*a*a*a*a*a to (a*a*a)*(a*a*a)? 的答案，了解 GCC 使用整数执行此操作的示例，但是不是FP。）

不幸的是，GCC 有时不愿意进行像这样的有符号整数优化，因为它的内部将有符号整数数学视为非关联，这可能是因为错误地应用了 C++ UB 规则来优化目标机器的 asm。这是 GCC 错过的优化；Clang没有这个问题。

进一步阅读：

• 是否有一些有意义的统计数据可以证明保持有符号整数算术溢出未定义是合理的？回复：它允许一些有用的循环优化。
• http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
• 未定义的行为是否适用于 asm 代码？（不）
• 内联 x86 汇编中是否未定义整数溢出？

整个情况基本上是一团糟，C 的设计者没有预料到当前优化编译器的复杂程度。像 Rust 这样的语言更适合它：如果你想要包装，你可以（并且必须）在每个操作的基础上告诉编译器，对于有符号和无符号类型。喜欢x.wrapping_add(1)。

2*x回复：为什么 clang 将 the和 the-1与lea/分开dec

Clang 在 Ice Lake 之前就针对 Intel CPU 上的延迟进行了优化，以额外的 uop 吞吐量成本为代价节省了一个周期的延迟。（编译器通常倾向于延迟，因为现代 CPU 通常足够宽，可以承受吞吐量成本，尽管它确实占用了乱序执行窗口中的空间来隐藏缓存未命中延迟。）

lea eax, [rdi + rdi - 1]Skylake 上有 3 个周期延迟，而其使用的 LEA 上有 1 个周期延迟。（有关详细信息，请参阅为什么用于测试 Collat​​z 猜想的 C++ 代码比手写汇编运行得更快？ ）。在 AMD Zen 系列上，它在延迟方面实现了收支平衡（复杂的 LEA 仅具有 2c 延迟），同时仍会花费额外的 uop。在 Ice Lake 和后来的 Intel 上，即使是 3 组件 LEA 也只有 1 个周期，因此这纯粹是一个缺点。请参阅https://uops.info/LEA_B_I_D8 (R32) ， （Base、Index、8 位位移，比例因子 = 1）的条目。

此调整决策与整数溢出无关。

Answer 4

有符号整数上溢/下溢是未定义的行为，因此编译器可以进行此类优化。因为允许编译器在上溢/下溢的情况下执行任何操作，所以它可以执行此操作，或者执行任何其他对于需要关心的用例来说更优化的操作。

\n

如果有符号溢出的行为被指定为 \xe2\x80\x9cDEC PDP-8 在 1973 年所做的事情，\xe2\x80\x9d 其他目标的编译器将需要插入指令来检查溢出，如果发生溢出，产生该结果，而不是 CPU 本身执行的任何操作。

\n