在线IDE上程序表现异常

Question

我找到了以下C++程序(源代码):

#include <iostream>
int main()
{
    for (int i = 0; i < 300; i++)
        std::cout << i << " " << i * 12345678 << std::endl;
}

这似乎是一个简单的程序，在我的本地机器上输出正确，例如：

0 0
1 12345678
2 24691356
...
297 -628300930
298 -615955252
299 -603609574

然而，在像CodeChef这样的在线IDE上，它会输出以下内容：

0 0
1 12345678
2 24691356
...
4167 -95167326
4168 -82821648
4169 -7047597

为什么 for 循环不在 300 处终止？而且这个程序总是在 4169 终止。为什么是 4169 而不是其他值？

- arpanmangal

---

可能是因为有符号整数溢出具有未定义的行为。 - eerorika

我知道有符号数溢出是未定义行为，但这个情况实在是一个惊人的失败... - Galik

不要假定UB受到限制，这是一个很好的教训。 - M.M

你为什么认为第一个输出是“正确的输出”，我很好奇。 - Lightness Races in Orbit

@LightnessRacesinOrbit - 嗯，那个提醒确实很有价值！ - davidbak

Answer 1

我会假设在线编译器使用GCC或兼容的编译器。当然，任何其他编译器也可以执行相同的优化，但是GCC文档很好地解释了它所做的事情：-faggressive-loop-optimizations。此选项告诉循环优化器使用语言约束来推导循环迭代次数的边界。这假定循环代码不会通过例如导致有符号整数溢出或越界数组访问的方式调用未定义的行为。循环迭代次数的边界用于指导循环展开和剥离以及循环退出测试优化。此选项默认启用。此选项仅允许基于已被证明存在UB的情况进行假设。要利用这些假设，可能需要启用其他优化，例如常量折叠。

---

有符号整数溢出具有未定义的行为。优化器能够证明，任何大于173的i值都会导致UB，并且因为它可以假设没有UB，所以它还可以假设i永远不会大于173。然后，它可以进一步证明i < 300始终为真，因此循环条件可以被优化掉。为什么是4169而不是其他值？这些网站可能限制它们显示的输出行数（或字符数或字节数），并且碰巧共享相同的限制。

- eerorika

---

如果编译器可以证明对于任何大于173的i值都会存在未定义行为，那么为什么它不发出警告而是执行无意义的优化？ - Jabberwocky

@MichaelWalz 它确实会发出一个。 - HolyBlackCat

去除多余的布尔测试并非毫无意义的优化，而是一项非常有用的优化。但如果要添加额外的代码来禁用/撤销在存在错误源代码时的优化，则这种做法（大部分）是无意义的。 - user1084944

@MichaelWalz: 就像你所建议的那样，编译器无法可靠地检测 UB（未定义行为）（尽管它有时可以警告可能发生的情况，就像它实际上在这里做的那样）。相反，它可以在“假设不会出现 UB”的最佳意图下继续进行。这两个东西或许微妙但实际上是非常不同的。编译器不会像“啊哈！UB！现在我可以启用某种优化”一样去操作 - 优化一直都在那里。它一直在做类似于这样的事情。但只要程序编写正确，您不会看到任何对其语义的影响。 - Lightness Races in Orbit

比喻来说，你家前门的制造商可能决定在门中间战略性地放置一块金属，这样门就更加坚固了。除非你打洞或者错误使用门，否则你永远也不会注意到这一点。 - Lightness Races in Orbit

Answer 2

"未定义行为是未定义的。" (c)

Codechef使用的编译器似乎遵循以下逻辑：

1. 未定义行为不可能发生。
2. i * 12345678 溢出，如果 i > 173 （假设使用32位 int），会导致未定义行为。
3. 因此，i 永远不会超过 173。
4. 因此，i < 300 是多余的，可以被替换为 true。

循环本身似乎是无限的。显然，Codechef只在特定时间后停止程序或截断输出。

- HolyBlackCat

---

我刚刚数了一下输出中的字符数量，似乎是“2^16”。显然，这是一个巧合，两者都将输出截断为“2^16”个字符。 - HolyBlackCat

@ArpanMangal说，像4169这样的鼻妖现在正在Ideone和Codechef上开派对。UB未定义，它可以是任何东西，包括鼻妖。认真分析UB是浪费时间，应该利用这个时间来找出如何避免发生UB。 - jmoreno

@jmoreno，如果你对编译器设计感兴趣，那么这并不是浪费时间。 - user253751

尽管如此，这一次我们成功地对其进行了分析。了解 UB 如何破坏程序有助于得出在哪些情况下 UB 是可以被接受的结论，如果有的话。 - HolyBlackCat

宇宙所做的一切都是正确的（根据定义），那么学习天文学有什么意义呢？ - user253751

Answer 3

在你的 for 循环内，由于最大值 int 可能是 2147483647，而 174 * 123456789 表达式得出的结果是 2148147972，这可能导致在第174次迭代时会触发 未定义行为，因为没有符号整数溢出。所以你正在观察 UB 的影响，尤其是在使用 GCC 编译器进行优化标记设置的情况下。很可能编译器已经通过发出以下警告来提醒你：

warning: iteration 174 invokes undefined behavior [-Waggressive-loop-optimizations]

移除 (-O2) 优化标志以观察不同的结果。

- Ron

---

值得注意的是，未定义行为可以产生“溯源”效应——因为未定义行为会发生在第174次迭代中，标准甚至不要求循环的前173次迭代应该按预期进行！ - user1084944

@Hurkyl 的确如此。UB 导致整个程序，包括之前的语句都表现出 UB，这有点自相矛盾。 - Ron

@Ron：这并不矛盾。程序要么有明确定义的语义，要么没有。请记住，C++代码不是一系列要执行的指令；它是对程序的描述。 - Lightness Races in Orbit

@LightnessRacesinOrbit：一个程序的语义部分未指定但不完全未定义是可能的。C标准试图将这个概念应用于它所谓的“有界UB”，尽管它使用的语言有点含糊。允许编译器在处理诸如整数溢出之类的事情时具有广泛但不无限制的自由，不会干扰许多其他有用的优化，但会使语言更适合处理从不可信来源接收到的数据。 - supercat

@supercat：确实，未指定的行为与未定义的行为不同。我们正在讨论后者。 - Lightness Races in Orbit

虽然我不知道C++标准是否具有这样的功能，但C标准定义了一类实现，将__STDC_ANALYZABLE__定义为非零值。对于这样的实现，标准区分“有界UB”和“关键UB”，并尝试限制前者的影响。 - supercat

Answer 4

编译器可以假设不会发生未定义行为，因为有符号溢出是UB，可以假设从未出现过i * 12345678 > INT_MAX，因此也可以推断出i <= INT_MAX / 12345678 < 300，从而删除检查i < 300。

- yassin