Por que esse loop produz “aviso: a iteração 3u invoca um comportamento indefinido” e gera mais de 4 linhas?

Compilando isso:

#include <iostream>

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

e gccproduz o seguinte aviso:

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

Eu entendo que há um estouro inteiro assinado.

O que não consigo entender é por que o ivalor é quebrado por essa operação de estouro?

Eu li as respostas para Por que o número inteiro excedente no x86 com o GCC causa um loop infinito? , mas ainda não sei ao certo por que isso acontece. Entendi que "indefinido" significa "tudo pode acontecer", mas qual é a causa subjacente desse comportamento específico ?

Online: http://ideone.com/dMrRKR

Compilador: gcc (4.8)

Estouro de número inteiro assinado (como estritamente falando, não existe "estouro de número inteiro não assinado") significa comportamento indefinido . E isso significa que tudo pode acontecer, e discutir por que isso acontece sob as regras do C ++ não faz sentido.

Rascunho C ++ 11 N3337: §5.4: ¹

Se durante a avaliação de uma expressão, o resultado não é matematicamente definido ou não está no intervalo de valores representáveis ​​para seu tipo, o comportamento é indefinido. [Nota: a maioria das implementações existentes do C ++ ignoram os fluxos de números inteiros. O tratamento da divisão por zero, formando o restante usando um divisor zero, e todas as exceções de ponto flutuante variam entre as máquinas, e geralmente é ajustável por uma função de biblioteca. - end note]

Seu código compilado com g++ -O3aviso de emissão (mesmo sem -Wall)

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)
  ^

A única maneira de analisar o que o programa está fazendo é lendo o código de montagem gerado.

Aqui está a lista completa da montagem:

    .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

Eu mal consigo ler montagem, mas até consigo ver a addl $1000000000, %edilinha. O código resultante se parece mais

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

Este comentário do @TC:

Eu suspeito que é algo como: (1) porque toda iteração com iqualquer valor maior que 2 tem um comportamento indefinido -> (2) podemos assumir que, i <= 2para fins de otimização -> (3) a condição do loop é sempre verdadeira -> (4 ) é otimizado em um loop infinito.

deu-me a idéia de comparar o código de montagem do código do OP com o código de montagem do código a seguir, sem comportamento indefinido.

#include <iostream>

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

E, de fato, o código correto tem condição de término.

    ; ...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...

OMG, isso não é óbvio! Não é justo! Exijo julgamento por fogo!

Lide com isso, você escreveu o código do buggy e deve se sentir mal. Suportar as consequências.

... ou, alternativamente, faça o uso adequado de melhores diagnósticos e melhores ferramentas de depuração - é para isso que servem:

• ativar todos os avisos

  • -Wallé a opção gcc que permite todos os avisos úteis sem falsos positivos. Esse é o mínimo que você deve sempre usar.
  • O gcc tem muitas outras opções de aviso , no entanto, elas não estão ativadas -Wall, pois podem alertar sobre falsos positivos
  • Infelizmente, o Visual C ++ está atrasado com a capacidade de fornecer avisos úteis. Pelo menos o IDE habilita alguns por padrão.

• use sinalizadores de depuração para depuração

  • para excesso de número inteiro -ftrapvintercepta o programa em excesso,
  • O compilador Clang é excelente para isso: -fcatch-undefined-behaviorcaptura muitas instâncias de comportamento indefinido (nota "a lot of" != "all of them":)

Eu tenho uma bagunça de espaguete de um programa não escrito por mim que precisa ser enviado amanhã! AJUDA !!!!!! 111oneone

Use gcc's -fwrapv

Esta opção instrui o compilador a assumir que o excesso aritmético assinado de adição, subtração e multiplicação envolve a representação de dois complementos.

¹ - esta regra não se aplica ao "estouro de número inteiro não assinado", como §3.9.1.4 diz que

Inteiros não assinados, declarados não assinados, devem obedecer às leis do módulo aritmético 2 ^{n em} que n é o número de bits na representação de valor desse tamanho particular de número inteiro.

e, por exemplo, resultado de UINT_MAX + 1é matematicamente definido - pelas regras do módulo aritmético 2 ⁿ

Resposta curta, gccespecificamente documentou esse problema, podemos ver nas notas de versão do gcc 4.8 que diz ( ênfase minha daqui para frente ):

O GCC agora usa uma análise mais agressiva para derivar um limite superior para o número de iterações de loops usando restrições impostas pelos padrões de linguagem . Isso pode fazer com que programas não conformes deixem de funcionar conforme o esperado, como SPEC CPU 2006 464.h264ref e 416.gamess. Uma nova opção, -fno-aggressive-loop-optimizations, foi adicionada para desativar essa análise agressiva. Em alguns loops que possuem número constante de iterações, mas sabe-se que um comportamento indefinido ocorre no loop antes de atingir ou durante a última iteração, o GCC avisa sobre o comportamento indefinido no loop em vez de derivar o limite superior inferior do número de iterações para o loop. O aviso pode ser desativado com -Wno-aggressive-loop-optimizations.

e, de fato, se usarmos -fno-aggressive-loop-optimizationso comportamento do loop infinito cessará e ocorre em todos os casos que testei.

A resposta longa começa com o conhecimento de que o excesso de número inteiro assinado é um comportamento indefinido, observando o rascunho da seção padrão C ++, 5 Expressões, parágrafo 4, que diz:

Se durante a avaliação de uma expressão, o resultado não for matematicamente definido ou não estiver no intervalo de valores representáveis ​​para seu tipo, o comportamento será indefinido . [Nota: a maioria das implementações existentes do C ++ ignora estouros de número inteiro. O tratamento da divisão por zero, formando o restante usando um divisor zero, e todas as exceções de ponto flutuante variam entre as máquinas, e geralmente é ajustável por uma função de biblioteca. - end note

Sabemos que o padrão diz que o comportamento indefinido é imprevisível a partir da observação que acompanha a definição que diz:

[Nota: Comportamento indefinido pode ser esperado quando esta Norma Internacional omite qualquer definição explícita de comportamento ou quando um programa usa uma construção incorreta ou dados errados. O comportamento indefinido permitido varia de ignorar completamente a situação com resultados imprevisíveis , comportar-se durante a tradução ou a execução do programa de maneira documentada, característica do ambiente (com ou sem a emissão de uma mensagem de diagnóstico), até o término de uma tradução ou execução (com a emissão de uma mensagem de diagnóstico). Muitas construções de programas erradas não geram comportamento indefinido; eles precisam ser diagnosticados. - end note]

Mas o que o gccotimizador pode fazer no mundo para transformar isso em um loop infinito? Parece completamente maluco. Mas, felizmente, gccnos dá uma pista para descobrir isso no aviso:

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

A pista é: o Waggressive-loop-optimizationsque isso significa? Felizmente para nós, não é a primeira vez que essa otimização quebra o código dessa maneira e temos sorte porque John Regehr documentou um caso no artigo GCC pré-4.8 Breaks Broken SPEC 2006 Benchmarks, que mostra o seguinte código:

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;
}

o artigo diz:

O comportamento indefinido está acessando d [16] pouco antes de sair do loop. Em C99, é legal criar um ponteiro para um elemento uma posição após o final da matriz, mas esse ponteiro não deve ser desreferenciado.

e depois diz:

Em detalhes, aqui está o que está acontecendo. O compilador CA, ao ver d [++ k], pode assumir que o valor incrementado de k está dentro dos limites da matriz, pois ocorre um comportamento indefinido. Para o código aqui, o GCC pode inferir que k está no intervalo de 0 a 15. Um pouco mais tarde, quando o GCC vê k <16, ele diz para si mesmo: "Ah - essa expressão é sempre verdadeira, então temos um loop infinito". A situação aqui, em que o compilador usa a suposição de boa definição para inferir um fato útil do fluxo de dados,

Então, o que o compilador deve estar fazendo em alguns casos está assumindo, já que o excesso de número inteiro assinado é um comportamento indefinido, isempre deve ser menor que 4e, portanto, temos um loop infinito.

Ele explica que isso é muito semelhante à infame remoção de verificação de ponteiro nulo do kernel do Linux, onde ao ver este código:

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

gccinferiu que, uma vez que sfoi diferido s->f;e desreferenciar um ponteiro nulo é um comportamento indefinido, ele snão deve ser nulo e, portanto, otimiza a if (!s)verificação na próxima linha.

A lição aqui é que os otimizadores modernos são muito agressivos sobre a exploração de comportamentos indefinidos e provavelmente só serão mais agressivos. Claramente, com apenas alguns exemplos, podemos ver que o otimizador faz coisas que parecem completamente irracionais para um programador, mas em retrospecto da perspectiva dos otimizadores, faz sentido.

tl; dr O código gera um teste que inteiro + número inteiro positivo == número inteiro negativo . Normalmente, o otimizador não otimiza isso, mas no caso específico de std::endlser usado a seguir, o compilador otimiza esse teste. Ainda não descobri o que há de especial endl.

No código do assembly nos níveis -O1 e superiores, é claro que o gcc refatora o loop para:

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

O maior valor que funciona corretamente é 715827882, ou seja, floor ( INT_MAX/3). O snippet de montagem em -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

Observe que o complemento -1431655768está 4 * 715827882no 2's.

Bater -O2otimiza isso para o seguinte:

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

Portanto, a otimização que foi feita é apenas que a addlsubida foi mais alta.

Se recompilarmos em 715827883vez disso, a versão -O1 será idêntica à parte do número alterado e do valor do teste. No entanto, -O2 faz uma alteração:

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

Onde havia cmpl $-1431655764, %esia -O1, essa linha foi removido porque -O2. O otimizador deve ter decidido que adicionar 715827883a %esinunca pode ser igual -1431655764.

Isso é bastante intrigante. Acrescentando que, para INT_MIN+1 não gerar o resultado esperado, para que o otimizador deve ter decidido que %esinunca pode ser INT_MIN+1e eu não sei por que ele iria decidir isso.

No exemplo de trabalho, parece igualmente válido concluir que adicionar 715827882a um número não pode ser igual INT_MIN + 715827882 - 2! (isso só é possível se a envolvência realmente ocorrer), mas não otimiza a linha nesse exemplo.

O código que eu estava usando é:

#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);
    }
}

Se o std::endl(std::cout)for removido, a otimização não ocorrerá mais. De fato, substituí-lo por std::cout.put('\n'); std::flush(std::cout);também faz com que a otimização não aconteça, mesmo que std::endlesteja embutida.

O inlining de std::endlparece afetar a parte anterior da estrutura do loop (que eu não entendo direito o que está fazendo, mas vou publicá-la aqui, caso alguém o faça):

Com código original e -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

Com inlining mymanual de 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

Uma diferença entre esses dois é que %esié usado no original e %ebxna segunda versão; existe alguma diferença na semântica definida entre %esie %ebxem geral? (Eu não sei muito sobre montagem x86).

Outro exemplo desse erro relatado no gcc é quando você tem um loop que é executado para um número constante de iterações, mas você está usando a variável counter como um índice em uma matriz que possui menos que esse número de itens, como:

int a[50], x;

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

O compilador pode determinar que esse loop tentará acessar a memória fora da matriz 'a'. O compilador reclama disso com esta mensagem bastante enigmática:

A iteração xxu invoca um comportamento indefinido [-Werror = otimizações de loop agressivo]

O que não consigo entender é por que o valor é quebrado por essa operação de estouro?

Parece que o excesso de número inteiro ocorre na 4ª iteração (para i = 3). signedestouro inteiro invoca um comportamento indefinido . Nesse caso, nada pode ser previsto. O loop pode iterar apenas algumas 4vezes ou pode ir para o infinito ou qualquer outra coisa!
O resultado pode variar de compilador para compilador ou mesmo para versões diferentes do mesmo compilador.

C11: 1.3.24 comportamento indefinido:

comportamento para o qual este Padrão Internacional não impõe requisitos
[Nota: Um comportamento indefinido pode ser esperado quando este Padrão Internacional omite qualquer definição explícita de comportamento ou quando um programa usa uma construção ou dados errados. O comportamento indefinido permitido varia de ignorar completamente a situação com resultados imprevisíveis, comportar-se durante a tradução ou a execução do programa de maneira documentada, característica do ambiente (com ou sem a emissão de uma mensagem de diagnóstico), até o término de uma tradução ou execução (com a emissão de uma mensagem de diagnóstico) . Muitas construções de programas erradas não geram comportamento indefinido; eles precisam ser diagnosticados. - end note]