¿Por qué este bucle produce "advertencia: la iteración 3u invoca un comportamiento indefinido" y genera más de 4 líneas?

Compilando esto:

#include <iostream>

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

y gccproduce la siguiente advertencia:

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

Entiendo que hay un desbordamiento de entero con signo.

Lo que no puedo entender es ¿por qué el ivalor se rompe por esa operación de desbordamiento?

He leído las respuestas a ¿Por qué el desbordamiento de enteros en x86 con GCC causa un bucle infinito? , pero todavía no tengo claro por qué sucede esto: entiendo que "indefinido" significa "cualquier cosa puede suceder", pero ¿cuál es la causa subyacente de este comportamiento específico ?

En línea: http://ideone.com/dMrRKR

Compilador: gcc (4.8)

El desbordamiento de enteros con signo (como estrictamente hablando, no existe el "desbordamiento de enteros sin signo") significa un comportamiento indefinido . Y esto significa que puede pasar cualquier cosa, y discutir por qué sucede bajo las reglas de C ++ no tiene sentido.

C ++ 11 borrador N3337: §5.4: ¹

Si durante la evaluación de una expresión, el resultado no está definido matemáticamente o no está en el rango de valores representables para su tipo, el comportamiento no está definido. [Nota: la mayoría de las implementaciones existentes de C ++ ignoran los desbordamientos de enteros. El tratamiento de la división por cero, formando un resto usando un divisor de cero, y todas las excepciones de punto flotante varían entre máquinas, y generalmente es ajustable por una función de biblioteca. —Nota final]

Su código compilado con g++ -O3emite advertencia (incluso sin -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)
  ^

La única forma en que podemos analizar lo que está haciendo el programa es leyendo el código de ensamblaje generado.

Aquí está el listado completo de ensamblaje:

    .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

Apenas puedo leer el ensamblaje, pero incluso puedo ver la addl $1000000000, %edilínea. El código resultante se parece más a

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

Este comentario de @TC:

Sospecho que es algo así como: (1) porque cada iteración con icualquier valor mayor que 2 tiene un comportamiento indefinido -> (2) podemos suponer que i <= 2para fines de optimización -> (3) la condición del bucle siempre es verdadera -> (4 ) está optimizado en un bucle infinito.

me dio la idea de comparar el código de ensamblaje del código de OP con el código de ensamblaje del siguiente código, sin comportamiento indefinido.

#include <iostream>

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

Y, de hecho, el código correcto tiene la condición de terminación.

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

Dios mío, eso no es completamente obvio! ¡No es justo! Exijo juicio por fuego!

Enfréntalo, escribiste el código con errores y deberías sentirte mal. Llevar las consecuencias.

... o, como alternativa, hacer un uso adecuado de mejores diagnósticos y mejores herramientas de depuración, para eso están:

• habilitar todas las advertencias

  • -Walles la opción gcc que habilita todas las advertencias útiles sin falsos positivos. Este es un mínimo que siempre debes usar.
  • gcc tiene muchas otras opciones de advertencia , sin embargo, no están habilitadas -Wallya que pueden advertir sobre falsos positivos
  • Desafortunadamente, Visual C ++ se está quedando atrás con la capacidad de dar advertencias útiles. Al menos el IDE habilita algunos por defecto.

• usar banderas de depuración para depurar

  • para el desbordamiento de enteros -ftrapvatrapa el programa en desbordamiento,
  • Compilador de sonido metálico es excelente para esto: -fcatch-undefined-behaviorcoge una gran cantidad de casos de comportamiento indefinido (nota: "a lot of" != "all of them")

¡Tengo un desorden de spaghetti de un programa no escrito por mí que debe enviarse mañana! AYUDA !!!!!! 111oneone

Use gcc's -fwrapv

Esta opción le indica al compilador que asuma que el desbordamiento aritmético con signo de suma, resta y multiplicación se envuelve usando una representación de dos complementos.

¹ - esta regla no se aplica al "desbordamiento de enteros sin signo", como §3.9.1.4 dice que

Los enteros sin signo, declarados sin signo, obedecerán las leyes del módulo aritmético 2 ⁿ donde n es el número de bits en la representación del valor de ese tamaño particular de entero.

y, por ejemplo, el resultado de UINT_MAX + 1está matemáticamente definido - por las reglas del módulo aritmético 2 ⁿ

Respuesta corta, gccespecíficamente ha documentado este problema, podemos ver que en las notas de lanzamiento de gcc 4.8 que dice ( énfasis mío en adelante ):

GCC ahora usa un análisis más agresivo para derivar un límite superior para el número de iteraciones de bucles utilizando restricciones impuestas por los estándares del lenguaje . Esto puede causar que los programas no conformes ya no funcionen como se esperaba, como SPEC CPU 2006 464.h264ref y 416.gamess. Se agregó una nueva opción, optimizaciones de bucle fno agresivo, para deshabilitar este análisis agresivo. En algunos bucles que han conocido un número constante de iteraciones, pero se sabe que ocurre un comportamiento indefinido en el bucle antes de alcanzar o durante la última iteración, GCC advertirá sobre el comportamiento indefinido en el bucle en lugar de derivar el límite superior inferior del número de iteraciones para el bucle La advertencia se puede deshabilitar con las optimizaciones de bucle no agresivo.

y, de hecho, si usamos -fno-aggressive-loop-optimizationsel comportamiento de bucle infinito debería cesar y lo hace en todos los casos que he probado.

La respuesta larga comienza sabiendo que el desbordamiento de enteros con signo es un comportamiento indefinido al mirar el borrador de la sección estándar de C ++ 5 Expresiones, párrafo 4, que dice:

Si durante la evaluación de una expresión, el resultado no está matemáticamente definido o no está en el rango de valores representables para su tipo, el comportamiento es indefinido . [Nota: la mayoría de las implementaciones existentes de C ++ ignoran los desbordamientos de enteros. El tratamiento de la división por cero, formando un resto usando un divisor de cero, y todas las excepciones de coma flotante varían entre máquinas, y generalmente es ajustable por una función de biblioteca. —Nota final

Sabemos que el estándar dice que el comportamiento indefinido es impredecible de la nota que viene con la definición que dice:

[Nota: Se puede esperar un comportamiento indefinido cuando esta Norma Internacional omite cualquier definición explícita de comportamiento o cuando un programa utiliza una construcción errónea o datos erróneos. El comportamiento indefinido permitido varía desde ignorar la situación por completo con resultados impredecibles , hasta comportarse durante la traducción o la ejecución del programa de una manera documentada característica del entorno (con o sin la emisión de un mensaje de diagnóstico), hasta finalizar una traducción o ejecución (con la emisión de un mensaje de diagnóstico). Muchas construcciones de programa erróneas no generan un comportamiento indefinido; están obligados a ser diagnosticados. —Nota final]

Pero, ¿qué puede hacer el gccoptimizador para convertir esto en un bucle infinito? Suena completamente raro. Pero afortunadamente gccnos da una pista para descubrirlo en la advertencia:

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

La pista es Waggressive-loop-optimizations, ¿qué significa eso? Afortunadamente para nosotros, esta no es la primera vez que esta optimización ha roto el código de esta manera y tenemos suerte porque John Regehr ha documentado un caso en el artículo GCC pre-4.8 Breaks Broken SPEC 2006 Benchmarks que muestra el siguiente 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;
}

el artículo dice:

El comportamiento indefinido es acceder a d [16] justo antes de salir del bucle. En C99 es legal crear un puntero a un elemento una posición más allá del final de la matriz, pero ese puntero no debe ser desreferenciado.

y luego dice:

En detalle, esto es lo que está sucediendo. El compilador de AC, al ver d [++ k], puede asumir que el valor incrementado de k está dentro de los límites de la matriz, ya que de lo contrario se produce un comportamiento indefinido. Para el código aquí, GCC puede inferir que k está en el rango 0..15. Un poco más tarde, cuando GCC ve k <16, se dice a sí mismo: "Ajá, esa expresión siempre es verdadera, por lo que tenemos un bucle infinito". La situación aquí, donde el compilador utiliza el supuesto de una buena definición para inferir un hecho útil de flujo de datos,

Entonces, lo que el compilador debe estar haciendo en algunos casos es suponer que dado que el desbordamiento de enteros con signo es un comportamiento indefinido, isiempre debe ser menor 4y, por lo tanto, tenemos un bucle infinito.

Explica que esto es muy similar a la infame eliminación de verificación de puntero nulo del kernel de Linux, donde al ver este código:

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

gccdedujo que dado que sse hizo s->f;referencia en y dado que la desreferenciación de un puntero nulo es un comportamiento indefinido, entonces sno debe ser nulo y, por lo tanto, optimiza la if (!s)comprobación en la siguiente línea.

La lección aquí es que los optimizadores modernos son muy agresivos sobre la explotación de comportamientos indefinidos y lo más probable es que solo se vuelvan más agresivos. Claramente, con solo unos pocos ejemplos, podemos ver que el optimizador hace cosas que parecen completamente irracionales para un programador, pero en retrospectiva desde la perspectiva de los optimizadores tiene sentido.

tl; dr El código genera una prueba que entero + entero positivo == entero negativo . Por lo general, el optimizador no optimiza esto, pero en el caso específico de std::endlser utilizado a continuación, el compilador optimiza esta prueba. Todavía no he descubierto qué tiene de especial endl.

Del código de ensamblaje en -O1 y niveles superiores, está claro que gcc refactoriza el ciclo para:

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

El mayor valor que funciona correctamente es 715827882, es decir, floor ( INT_MAX/3). El fragmento de ensamblado en -O1es:

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

Tenga en cuenta que -1431655768está 4 * 715827882en el complemento de 2.

Golpear -O2optimiza eso a lo siguiente:

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

Entonces, la optimización que se ha hecho es simplemente que addlse movió más arriba.

Si, en su 715827883lugar, volvemos a compilar , la versión -O1 es idéntica aparte del número modificado y el valor de prueba. Sin embargo, -O2 hace un cambio:

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

Donde había cmpl $-1431655764, %esien -O1, esa línea se ha eliminado -O2. El optimizador debe haber decidido que agregar 715827883a %esinunca puede ser igual -1431655764.

Esto es bastante desconcertante. Añadiendo que a INT_MIN+1 no generar el resultado esperado, por lo que el optimizador debe haber decidido que %esinunca puede haber INT_MIN+1y no estoy seguro de por qué decidiría eso.

¡En el ejemplo de trabajo parece que sería igualmente válido concluir que sumar 715827882a un número no puede ser igual INT_MIN + 715827882 - 2! (esto solo es posible si realmente ocurre el ajuste), pero no optimiza la salida de línea en ese ejemplo.

El código que estaba usando es:

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

Si std::endl(std::cout)se elimina, la optimización ya no se produce. De hecho, reemplazarlo std::cout.put('\n'); std::flush(std::cout);también hace que la optimización no suceda, aunque std::endlesté en línea.

La alineación de std::endlparece afectar la parte anterior de la estructura del bucle (que no entiendo muy bien lo que está haciendo, pero lo publicaré aquí en caso de que alguien más lo haga):

Con código original y -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

Con la expansión en línea de mymanual 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

Una diferencia entre estos dos es que %esise usa en el original y %ebxen la segunda versión; ¿Hay alguna diferencia en la semántica definida entre %esiy %ebxen general? (No sé mucho sobre el montaje x86).

Otro ejemplo de este error que se informa en gcc es cuando tiene un bucle que se ejecuta durante un número constante de iteraciones, pero está utilizando la variable de contador como un índice en una matriz que tiene menos de ese número de elementos, como:

int a[50], x;

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

El compilador puede determinar que este bucle intentará acceder a la memoria fuera de la matriz 'a'. El compilador se queja de esto con este mensaje bastante críptico:

la iteración xxu invoca un comportamiento indefinido [-Werror =gressive-loop-optimizations]

Lo que no puedo entender es ¿por qué esa operación de desbordamiento rompe el valor?

Parece que el desbordamiento de enteros ocurre en la cuarta iteración (para i = 3). signedel desbordamiento de enteros invoca un comportamiento indefinido . En este caso no se puede predecir nada. ¡El ciclo puede iterar solo 4veces o puede ir al infinito o cualquier otra cosa!
El resultado puede variar de compilador a compilador o incluso para diferentes versiones del mismo compilador.

C11: 1.3.24 comportamiento indefinido:

comportamiento para el cual esta Norma Internacional no impone requisitos
[Nota: Se puede esperar un comportamiento indefinido cuando esta Norma Internacional omite cualquier definición explícita de comportamiento o cuando un programa utiliza una construcción errónea o datos erróneos. El comportamiento indefinido permitido varía desde ignorar la situación por completo con resultados impredecibles, hasta comportarse durante la traducción o la ejecución del programa de una manera documentada característica del entorno (con o sin la emisión de un mensaje de diagnóstico), hasta finalizar una traducción o ejecución (con la emisión de un mensaje de diagnóstico) . Muchas construcciones de programa erróneas no generan un comportamiento indefinido; están obligados a ser diagnosticados. —Nota final]