为什么这个循环会产生“warning: iteration 3u invokes undefined behavior”并输出超过4行？

Question

为什么这个循环会产生“warning: iteration 3u invokes undefined behavior”并输出超过4行？

168

编译这个：

#include <iostream>

int main()
{
    for (int i = 0; i < 4; ++i)
        std::cout << i*1000000000 << std::endl;
}

而 gcc 会产生以下警告：

warning: iteration 3u invokes undefined behavior [-Waggressive-loop-optimizations]
   std::cout << i*1000000000 << std::endl;
                  ^

我知道这是一个有符号整数溢出。

但我不明白为什么这个溢出操作会破坏i的值？

我已经阅读了Why does integer overflow on x86 with GCC cause an infinite loop?的答案，但我仍然不清楚为什么会发生这种情况-我知道"未定义"意味着"任何事情都可能发生"，但是导致这种具体行为的根本原因是什么?

在线链接: http://ideone.com/dMrRKR

编译器: gcc (4.8)

- zerkms

52

有符号整数溢出 -> 未定义的行为 -> 鼻妖。但我必须承认，这个例子相当不错。 - dyp

3

当我读到 Nasal Daemons 时，我发出了“imgur 笑声”，这种笑声是当你看到有趣的东西时微微地从鼻子呼出气来。然后我意识到... 我一定被鼻子恶魔诅咒了！ - corsiKa

1

可能是为什么在x86上使用GCC的整数溢出会导致无限循环？的重复问题。 - Abyx

5

收藏此页以便下次引用，当有人反驳“虽然它在技术上是未定义的，但应该可以做到某事情”时使用。 :) - M.M

1

我在这篇博客文章中提到了这个问题，看起来它正在为这里带来一些流量和投票。 - Shafik Yaghmour

显示剩余24条评论

5个回答

72

简短回答，具体来说是gcc文档化了这个问题，我们可以在gcc 4.8 release notes中看到这一点，其中写道（以下为我的强调）：

GCC现在使用更加激进的分析方法来通过语言标准所施加的约束条件推导出循环迭代次数的上界。这可能会导致不符合标准的程序无法像预期那样工作，例如SPEC CPU 2006 464.h264ref和416.gamess。添加了一个新选项-fno-aggressive-loop-optimizations来禁用这种激进的分析方法。在某些已知迭代次数为常量的循环中，但在达到或在最后一次迭代之前发生了未定义行为的循环中，GCC将警告循环中的未定义行为，而不是推导循环的迭代次数的下界。该警告可以通过-Wno-aggressive-loop-optimizations禁用。

如果我们使用-fno-aggressive-loop-optimizations，无限循环行为应该会停止，在我测试过的所有情况下都是如此。

长答案从了解有符号整数溢出是未定义行为开始，可以查看C++标准草案第5节“表达式”第4段，其中说道：“如果在表达式求值期间，结果在其类型的可表示值范围之外或在数学上没有定义，则行为未定义。”[注：大多数现有的C++实现忽略整数溢出。除以零、使用零除数形成余数以及所有浮点异常的处理方法因机器而异，并且通常可以通过库函数进行调整。-注] 我们知道标准中说的未定义行为是不可预测的，这来自于与定义一起附带的注释。该注释说：

注意：当国际标准省略任何明确的行为定义或程序使用错误构造或错误数据时，可能会出现未定义行为。允许的未定义行为范围从完全忽略情况并产生不可预测的结果，到在翻译或程序执行期间表现出特定于环境的已记录方式（带或不带发出诊断消息），到终止翻译或执行（带有发出诊断消息）。许多错误的程序结构不会引起未定义行为；它们需要被诊断。-注释

但是，gcc优化器到底做了什么，才会将其变成无限循环呢？听起来完全荒谬。但幸运的是，gcc在警告中给了我们一个线索，以便找出其中的奥秘：

warning: iteration 3u invokes undefined behavior [-Waggressive-loop-optimizations]
   std::cout << i*1000000000 << std::endl;
                  ^

线索是 Waggressive-loop-optimizations，这是什么意思？幸运的是，这种优化方式已经不是第一次破坏代码了，我们很幸运因为 John Regehr 在文章 GCC pre-4.8 Breaks Broken SPEC 2006 Benchmarks 中记录了一个案例，展示了以下代码：

int d[16];

int SATD (void)
{
  int satd = 0, dd, k;
  for (dd=d[k=0]; k<16; dd=d[++k]) {
    satd += (dd < 0 ? -dd : dd);
  }
  return satd;
}

文章说：

未定义行为是在退出循环之前访问d [16]。在C99中，可以合法地创建指向数组末尾一个位置的指针，但是该指针不能被取消引用。

后来又说：

详细地说，这里发生了什么。看到d[++k]时，C编译器可以假设增加后的k值在数组边界内，否则会出现未定义行为。对于此处的代码，GCC可以推断k在0..15范围内。稍后，当GCC看到k < 16时，它会对自己说：“啊哈 - 这个表达式总是成立，所以我们有一个无限循环。”编译器在某些情况下必须执行的操作是假定由于有符号整数溢出是未定义行为，因此i必须始终小于4，因此我们有一个无限循环。

他解释说，这与臭名昭著的Linux内核空指针检查删除非常相似，其中在看到以下代码时：

struct foo *s = ...;
int x = s->f;
if (!s) return ERROR;

"gcc 推断，由于在 s->f; 中解引用了 s，并且解引用空指针是未定义行为，因此 s 不能为 null，因此优化掉了下一行的 if (!s) 检查。"

"这里的教训是，现代优化器非常积极地利用未定义行为，很可能只会变得更加积极。显然，通过只有几个示例，我们就可以看到优化器执行了程序员认为完全不合理的操作，但从优化器的角度来看，这些操作是有意义的。"

- Shafik Yaghmour

7

我知道编译器编写者正在做这件事（我曾经写过编译器甚至优化器），但是有些行为即使是“未定义的”也是“有用的”，而这种对越来越激进的优化的追求只是一种疯狂。你引用的结构是错误的，但优化掉错误检查会让用户感到不友好。 - Julie in Austin

1

@JulieinAustin 我同意这是非常令人惊讶的行为，说开发人员需要避免未定义的行为只是问题的一半。显然，编译器也需要向开发人员提供更好的反馈。在这种情况下，虽然会产生警告，但它并不真正提供足够的信息。 - Shafik Yaghmour

4

我认为这是一件好事，我希望有更好、更快的代码。UB（未定义的行为）永远不应该被使用。 - paulm

1

@paulm 在道德上，UB 显然是不好的，但是提供更好的工具（如 clang 静态分析器）来帮助开发人员在影响生产应用之前捕获 UB 和其他问题是无可厚非的。 - Shafik Yaghmour

1

@ShafikYaghmour 如果你的开发者忽略警告，那他们会关注clang的输出的几率有多大呢？这个问题可以很容易地通过采用“无不合理警告”的严格策略来解决。使用Clang是可取的，但不是必须的。 - deworde

显示剩余5条评论

24

简短概述：该代码生成一个测试，即整数 + 正整数 == 负整数。通常情况下，优化器不会削减这个测试，但在接下来使用了std::endl的特定情况下，编译器会将此测试优化掉。我还没有弄清楚endl的特殊之处。

从-O1及更高级别的汇编代码中可以清楚地看出，gcc对循环进行了重构：

i = 0;
do {
    cout << i << endl;
    i += NUMBER;
} 
while (i != NUMBER * 4)

能够正常工作的最大值是715827882，即 floor(INT_MAX/3)。在-O1优化级别下的汇编片段为：

L4:
movsbl  %al, %eax
movl    %eax, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    %eax, (%esp)
call    __ZNSo5flushEv
addl    $715827882, %esi
cmpl    $-1431655768, %esi
jne L6
    // fallthrough to "return" code

请注意，-1431655768 在二进制补码中等于 4 * 715827882。

使用 -O2 参数进行编译会将其优化为以下形式：

L4:
movsbl  %al, %eax
addl    $715827882, %esi
movl    %eax, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    %eax, (%esp)
call    __ZNSo5flushEv
cmpl    $-1431655768, %esi
jne L6
leal    -8(%ebp), %esp
jne L6 
   // fallthrough to "return" code

因此，已经进行的优化仅仅是将addl移到了更高的位置。

如果我们使用715827883重新编译，则-O1版本除更改的数字和测试值外完全相同。然而，-O2则会进行更改：

L4:
movsbl  %al, %eax
addl    $715827883, %esi
movl    %eax, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    %eax, (%esp)
call    __ZNSo5flushEv
jmp L2

当使用-O1时，代码中出现了cmpl $-1431655764, %esi，但是在-O2中，该行已被删除。优化器必须决定将%esi加上715827883永远不会等于-1431655764。

这相当令人困惑。将715827883添加到INT_MIN+1确实生成了预期结果，因此优化器必须决定%esi永远不可能是INT_MIN+1，但我不确定它为什么会做出这样的决定。

在工作示例中，似乎同样可以得出结论：将715827882添加到一个数字中不能等于INT_MIN + 715827882 - 2！（仅在确实发生wraparound时才可能发生），然而它并没有在那个示例中优化掉该行。

我使用的代码是：

#include <iostream>
#include <cstdio>

int main()
{
    for (int i = 0; i < 4; ++i)
    {
        //volatile int j = i*715827883;
        volatile int j = i*715827882;
        printf("%d\n", j);

        std::endl(std::cout);
    }
}

如果移除 std::endl(std::cout)，则优化将不再发生。事实上，即使使用 std::cout.put('\n'); std::flush(std::cout); 替换它也会导致优化失效，尽管 std::endl 在内联。

std::endl 的内联似乎影响循环结构的较早部分（我不太理解它在做什么，但我会在这里发布它，以防其他人理解）：

使用原始代码和 -O2：

L2:
movl    %esi, 28(%esp)
movl    28(%esp), %eax
movl    $LC0, (%esp)
movl    %eax, 4(%esp)
call    _printf
movl    __ZSt4cout, %eax
movl    -12(%eax), %eax
movl    __ZSt4cout+124(%eax), %ebx
testl   %ebx, %ebx
je  L10
cmpb    $0, 28(%ebx)
je  L3
movzbl  39(%ebx), %eax
L4:
movsbl  %al, %eax
addl    $715827883, %esi
movl    %eax, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    %eax, (%esp)
call    __ZNSo5flushEv
jmp L2                  // no test

通过手动内联 std::endl，-O2：

L3:
movl    %ebx, 28(%esp)
movl    28(%esp), %eax
addl    $715827883, %ebx
movl    $LC0, (%esp)
movl    %eax, 4(%esp)
call    _printf
movl    $10, 4(%esp)
movl    $__ZSt4cout, (%esp)
call    __ZNSo3putEc
movl    $__ZSt4cout, (%esp)
call    __ZNSo5flushEv
cmpl    $-1431655764, %ebx
jne L3
xorl    %eax, %eax

这两者之间的一个区别是，在原始版本中使用%esi，而在第二个版本中使用%ebx。一般情况下，在语义上是否定义了%esi和%ebx之间的差异？（我对x86汇编不太了解）。

- M.M

不过最好弄清楚优化器的逻辑，目前我还不清楚为什么有些情况下测试被优化掉了而有些情况则没有。 - M.M

10

在gcc中报告此错误的另一个例子是当您有一段循环代码，它执行了固定数量的迭代，但是您正在使用计数器变量作为索引来访问一个拥有不到该数量项的数组时，就会发生此错误，例如：

int a[50], x;

for( i=0; i < 1000; i++) x = a[i];

编译器可以确定这个循环将尝试访问数组'a'外的内存。编译器会用这个比较晦涩的信息来进行投诉：

迭代xxu调用未定义行为[-Werror=aggressive-loop-optimizations]

- Ed Tyler

更加神秘的是，只有在启用优化时消息才会发出。微软 VB 的 "数组越界" 消息是给新手的吗？ - Ravi Ganesh

6

我无法理解为什么这个溢出操作会破坏我的i值？

似乎在第四次迭代（当i = 3时）发生了整数溢出。有符号整数溢出会引起未定义行为。在这种情况下，无法预测任何结果。循环可能只迭代4次，也可能无限迭代或其他任何情况！不同编译器版本甚至可能产生不同的结果。

C11:1.3.24未定义行为：

这个国际标准没有强制要求的行为 [注意：当这个国际标准省略了任何明确的行为定义或程序使用错误的结构或错误的数据时，可以期望出现未定义的行为。允许的未定义行为范围从完全忽略情况到具有特定环境特征的文档化方式进行翻译或程序执行（带或不带诊断消息），直到终止翻译或执行（带诊断消息）。许多错误的程序结构不会产生未定义的行为，它们需要被诊断。 - end note]

- haccks

@bits_international; 是的。 - haccks

4

没错，解释一下为什么我要点踩是公平的。这个答案中提供的信息是正确的，但它缺乏教育性，并完全忽略了一个问题：溢出似乎发生在不同的位置（停止条件）而不是引起溢出的操作。具体情况下，事物是如何破裂的机制并没有得到解释，尽管这是这个问题的核心。这是一个典型的糟糕的老师情况，老师的答案不仅没有解决问题的核心，还阻碍了进一步的问题。它几乎听起来像... - Szabolcs

5

我认为这是未定义行为，从此处开始我不再关心它是如何或为什么会出错。标准允许它出错。没有进一步的问题。可能你并不是这个意思，但是它看起来是这样。我希望在stackoverflow上能看到更少（不幸常见）的这种态度。这对实际使用没有任何帮助。如果你获取用户输入，检查每个有符号整数操作之后是否溢出是不合理的，即使标准说程序的任何其他部分可能因此崩溃。了解如何出错可以帮助在实践中避免这类问题。 - Szabolcs

3

@Szabolcs：最好把C语言看作是两种语言，其中一种旨在让简单的编译器在程序员利用构造函数可靠地实现其目标平台但不适用于其他平台的情况下实现合理高效的可执行代码，并因此被标准委员会忽略，而第二种语言则排除所有这些不受标准支持的构造函数，以便让编译器应用额外的优化，这可能会或可能不会超过程序员必须放弃的优化。 - supercat

@Szabolcs：由于嵌入式或系统编程通常不可能在所有系统上都执行相同的概念，因此标准忽略了这些概念，后者对于系统编程完全无用。不幸的是，gcc的作者似乎对使优化与适合嵌入式或系统编程的语言版本兼容表现出很少的兴趣。 - supercat

1

@Szabolcs “如果你获取用户输入，检查每个有符号整数操作后是否溢出是不合理的” - 这是正确的，因为此时为时已晚。您必须在每个有符号整数操作之前检查溢出。 - melpomene

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- milleniumbug · Accepted Answer

有符号整数溢出（严格来说，“无符号整数溢出”并不存在）意味着未定义行为。这意味着任何事情都可能发生，在C++规则下讨论它为什么会发生是没有意义的。

C ++ 11草案N3337：§5.4: ¹

如果在表达式的评估过程中，结果在其类型的表示范围内不能被数学上定义或表示，则其行为是未定义的。[注意：大多数现有的C ++实现忽略整数溢出。除以零，使用零除数形成余数以及所有浮点异常的处理因机器而异，并且通常可以通过库函数进行调整。—end note]

即使没有-Wall选项，您的代码使用g++ -O3编译时也会发出警告。

a.cpp: In function 'int main()':
a.cpp:11:18: warning: iteration 3u invokes undefined behavior [-Waggressive-loop-optimizations]
   std::cout << i*1000000000 << std::endl;
                  ^
a.cpp:9:2: note: containing loop
  for (int i = 0; i < 4; ++i)
  ^

唯一的分析程序正在做什么的方法是通过阅读生成的汇编代码。

以下是完整的汇编清单：

    .file   "a.cpp"
    .section    .text$_ZNKSt5ctypeIcE8do_widenEc,"x"
    .linkonce discard
    .align 2
LCOLDB0:
LHOTB0:
    .align 2
    .p2align 4,,15
    .globl  __ZNKSt5ctypeIcE8do_widenEc
    .def    __ZNKSt5ctypeIcE8do_widenEc;    .scl    2;  .type   32; .endef
__ZNKSt5ctypeIcE8do_widenEc:
LFB860:
    .cfi_startproc
    movzbl  4(%esp), %eax
    ret $4
    .cfi_endproc
LFE860:
LCOLDE0:
LHOTE0:
    .section    .text.unlikely,"x"
LCOLDB1:
    .text
LHOTB1:
    .p2align 4,,15
    .def    ___tcf_0;   .scl    3;  .type   32; .endef
___tcf_0:
LFB1091:
    .cfi_startproc
    movl    $__ZStL8__ioinit, %ecx
    jmp __ZNSt8ios_base4InitD1Ev
    .cfi_endproc
LFE1091:
    .section    .text.unlikely,"x"
LCOLDE1:
    .text
LHOTE1:
    .def    ___main;    .scl    2;  .type   32; .endef
    .section    .text.unlikely,"x"
LCOLDB2:
    .section    .text.startup,"x"
LHOTB2:
    .p2align 4,,15
    .globl  _main
    .def    _main;  .scl    2;  .type   32; .endef
_main:
LFB1084:
    .cfi_startproc
    leal    4(%esp), %ecx
    .cfi_def_cfa 1, 0
    andl    $-16, %esp
    pushl   -4(%ecx)
    pushl   %ebp
    .cfi_escape 0x10,0x5,0x2,0x75,0
    movl    %esp, %ebp
    pushl   %edi
    pushl   %esi
    pushl   %ebx
    pushl   %ecx
    .cfi_escape 0xf,0x3,0x75,0x70,0x6
    .cfi_escape 0x10,0x7,0x2,0x75,0x7c
    .cfi_escape 0x10,0x6,0x2,0x75,0x78
    .cfi_escape 0x10,0x3,0x2,0x75,0x74
    xorl    %edi, %edi
    subl    $24, %esp
    call    ___main
L4:
    movl    %edi, (%esp)
    movl    $__ZSt4cout, %ecx
    call    __ZNSolsEi
    movl    %eax, %esi
    movl    (%eax), %eax
    subl    $4, %esp
    movl    -12(%eax), %eax
    movl    124(%esi,%eax), %ebx
    testl   %ebx, %ebx
    je  L15
    cmpb    $0, 28(%ebx)
    je  L5
    movsbl  39(%ebx), %eax
L6:
    movl    %esi, %ecx
    movl    %eax, (%esp)
    addl    $1000000000, %edi
    call    __ZNSo3putEc
    subl    $4, %esp
    movl    %eax, %ecx
    call    __ZNSo5flushEv
    jmp L4
    .p2align 4,,10
L5:
    movl    %ebx, %ecx
    call    __ZNKSt5ctypeIcE13_M_widen_initEv
    movl    (%ebx), %eax
    movl    24(%eax), %edx
    movl    $10, %eax
    cmpl    $__ZNKSt5ctypeIcE8do_widenEc, %edx
    je  L6
    movl    $10, (%esp)
    movl    %ebx, %ecx
    call    *%edx
    movsbl  %al, %eax
    pushl   %edx
    jmp L6
L15:
    call    __ZSt16__throw_bad_castv
    .cfi_endproc
LFE1084:
    .section    .text.unlikely,"x"
LCOLDE2:
    .section    .text.startup,"x"
LHOTE2:
    .section    .text.unlikely,"x"
LCOLDB3:
    .section    .text.startup,"x"
LHOTB3:
    .p2align 4,,15
    .def    __GLOBAL__sub_I_main;   .scl    3;  .type   32; .endef
__GLOBAL__sub_I_main:
LFB1092:
    .cfi_startproc
    subl    $28, %esp
    .cfi_def_cfa_offset 32
    movl    $__ZStL8__ioinit, %ecx
    call    __ZNSt8ios_base4InitC1Ev
    movl    $___tcf_0, (%esp)
    call    _atexit
    addl    $28, %esp
    .cfi_def_cfa_offset 4
    ret
    .cfi_endproc
LFE1092:
    .section    .text.unlikely,"x"
LCOLDE3:
    .section    .text.startup,"x"
LHOTE3:
    .section    .ctors,"w"
    .align 4
    .long   __GLOBAL__sub_I_main
.lcomm __ZStL8__ioinit,1,1
    .ident  "GCC: (i686-posix-dwarf-rev1, Built by MinGW-W64 project) 4.9.0"
    .def    __ZNSt8ios_base4InitD1Ev;   .scl    2;  .type   32; .endef
    .def    __ZNSolsEi; .scl    2;  .type   32; .endef
    .def    __ZNSo3putEc;   .scl    2;  .type   32; .endef
    .def    __ZNSo5flushEv; .scl    2;  .type   32; .endef
    .def    __ZNKSt5ctypeIcE13_M_widen_initEv;  .scl    2;  .type   32; .endef
    .def    __ZSt16__throw_bad_castv;   .scl    2;  .type   32; .endef
    .def    __ZNSt8ios_base4InitC1Ev;   .scl    2;  .type   32; .endef
    .def    _atexit;    .scl    2;  .type   32; .endef

我几乎看不懂汇编语言，但我也能看到addl $1000000000, %edi这一行。生成的代码看起来更像是

for(int i = 0; /* nothing, that is - infinite loop */; i += 1000000000)
    std::cout << i << std::endl;

@T.C.的这条评论:

我怀疑原因是：(1) 因为任何值大于2的i的每次迭代都有未定义的行为 -> (2) 我们可以假设i <= 2以进行优化 -> (3) 循环条件始终为真 -> (4) 它被优化成无限循环。

这启发我将OP代码的汇编代码与以下没有未定义行为的代码的汇编代码进行比较。

#include <iostream>

int main()
{
    // changed the termination condition
    for (int i = 0; i < 3; ++i)
        std::cout << i*1000000000 << std::endl;
}

实际上，正确的代码已经有了终止条件。

    ; ...snip...
L6:
    mov ecx, edi
    mov DWORD PTR [esp], eax
    add esi, 1000000000
    call    __ZNSo3putEc
    sub esp, 4
    mov ecx, eax
    call    __ZNSo5flushEv
    cmp esi, -1294967296 // here it is
    jne L7
    lea esp, [ebp-16]
    xor eax, eax
    pop ecx
    ; ...snip...

很遗憾，这是编写有漏洞代码的后果。

幸运的是，您可以利用更好的诊断和调试工具-这就是它们存在的目的：

启用所有警告
-Wall 是gcc选项，可启用所有有用的警告，没有误报。这是你应该始终使用的最低限度。
gcc还有许多其他警告选项，但它们不会随-Wall启用，因为它们可能会产生误报。
不幸的是，Visual C ++ 在提供有用警告方面落后。至少IDE默认启用一些。
使用调试标志进行调试
- 对于整数溢出，-ftrapv 在溢出时使程序陷入困境，
- Clang编译器非常适合此操作：-fcatch-undefined-behavior 捕捉了许多未定义行为的实例（注意："许多"！=“全部”）

我有一个混乱的程序需要明天发货！救命！！！！111oneone

使用gcc的-fwrapv

此选项指示编译器假定有符号算术加法、减法和乘法溢出使用二进制补码表示进行循环。

¹ - 该规则不适用于“无符号整数溢出”，因为§3.9.1.4说：

无符号整数，声明为unsigned，应遵守对该特定大小的整数值表示中的比特数取模的算术法则。

例如 UINT_MAX + 1 的结果是按照算术模2ⁿ的规则进行定义的。