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

gcc undefined-behavior

Question

Compilando esto:

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

y gcc produce 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 obtener es por qué el valor 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 ciclo infinito? , pero todavía no tengo claro por qué sucede esto, entiendo que "indefinido" significa que "puede pasar cualquier cosa", pero ¿cuál es la causa subyacente de este comportamiento específico ?

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

Compilador: gcc (4.8)

Answer 1

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

Parece que el desbordamiento de enteros ocurre en la 4ta iteración (para i = 3 ). signed desbordamiento de entero con signo invoca el comportamiento indefinido . En este caso, nada puede predecirse. ¡El ciclo puede iterar solo 4 veces o puede ir al infinito o a cualquier otra cosa!
El resultado puede variar de compilador a compilador o incluso para versiones diferentes 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 usa una construcción errónea o datos erróneos. El comportamiento indefinido permitido va desde ignorar la situación completamente 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 terminar una traducción o ejecución (con la emisión de un mensaje de diagnóstico) . Muchos constructos erróneos del programa no engendran un comportamiento indefinido; se requiere que sean diagnosticados. -finalizar nota]

Answer 2

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

Proyecto C ++ 11 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 sobre-flujos de enteros. El tratamiento de la división por cero, formando un resto utilizando un divisor cero, y todas las excepciones de punto flotante varían entre máquinas, y generalmente es ajustable por una función de biblioteca. -finalizar nota]

Su código compilado con g++ -O3 emite una 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 el programa está haciendo es leyendo el código ensamblador generado.

Aquí está la lista de montaje completo:

 .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 línea addl $1000000000, %edi . 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 i de cualquier valor mayor que 2 tiene un comportamiento indefinido -> (2) podemos suponer que i <= 2 para fines de optimización -> (3) la condición de ciclo es siempre true -> (4) se optimiza en un bucle infinito.

me dio la idea de comparar el código ensamblador del código OP con el código ensamblador del siguiente código, sin un 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 una 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!

Ocúpate de eso, escribiste el código de buggy 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 sirven:

• habilitar todas las advertencias

  • -Wall es 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 con -Wall ya 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 de forma predeterminada.

• usar indicadores de depuración para la depuración

  • para el desbordamiento de enteros -ftrapv atrapa el programa en desbordamiento,
  • El compilador de Clang es excelente para esto: -fcatch-undefined-behavior capta muchos casos de comportamiento indefinido (nota: "a lot of" != "all of them" )

¡Tengo un desastre de spaghetti de un programa que no he escrito y que debe enviarse mañana! AYUDA !!!!!! 111oneone

Use gcc''s -fwrapv

Esta opción indica al compilador que asuma que el desbordamiento aritmético firmado de suma, resta y multiplicación se completa con la representación de complemento a dos.

¹ - esta regla no se aplica al "desbordamiento de enteros sin signo", ya que el §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 del número entero.

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

Answer 3

Otro ejemplo de este error que se informa en gcc es cuando tiene un bucle que se ejecuta para un número constante de iteraciones, pero está usando la variable de contador como un índice en una matriz que tiene menos de esa cantidad 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:

iteración xxu invoca comportamiento indefinido [-Werror = optimizaciones de bucle agresivo]

Answer 4

Respuesta corta, gcc específicamente ha documentado este problema, podemos verlo en las notas de la versión de gcc 4.8 que dice ( énfasis mío en el futuro ):

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 estándares de lenguaje . Esto puede provocar 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 -fno-aggressive-loop-para inhabilitar 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 desactivar con optimizaciones de -Wno-aggressive-loop-optimization.

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

La respuesta larga comienza con saber que el desbordamiento de entero con signo es un comportamiento indefinido mirando 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 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 cero, y todas las excepciones de punto flotante varían entre las 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 a partir 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 usa una construcción errónea o datos erróneos. El comportamiento indefinido permitido va desde ignorar la situación completamente 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 terminar una traducción o ejecución (con la emisión de un mensaje de diagnóstico). Muchos constructos erróneos del programa no engendran un comportamiento indefinido; se requiere que sean diagnosticados. -finalizar nota]

Pero, ¿qué gcc puede hacer el optimizador de gcc para convertir esto en un bucle infinito? Suena completamente loco. Pero afortunadamente, gcc nos da una pista para descubrirlo en la advertencia:

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

La clave son las 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 articulo 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 se debe desreferenciar.

y luego dice:

En detalle, esto es lo que está pasando. El compilador de CA, al ver d [++ k], puede suponer 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: "Aha- esa expresión siempre es verdadera, así que tenemos un ciclo infinito." La situación aquí, donde el compilador usa la asunción de la definición para inferir un hecho útil del flujo de datos,

Entonces, lo que el compilador debe estar haciendo en algunos casos es asumir, dado que el desbordamiento de enteros con signo es un comportamiento indefinido, entonces siempre debo ser menor que 4 y, por lo tanto, tenemos un ciclo infinito.

Él explica que esto es muy similar a la infame eliminación del null puntero del kernel de Linux donde al ver este código:

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

gcc infirió que desde s se hizo referencia en s->f; y dado que eliminar referencias a un puntero nulo es un comportamiento indefinido, entonces s no debe ser nulo y, por lo tanto, optimiza la verificación if (!s) en la siguiente línea.

La lección aquí es que los optimizadores modernos son muy agresivos a la hora de explotar comportamientos indefinidos y lo más probable es que se vuelvan más agresivos. Claramente, con solo algunos 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.

Answer 5

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

Desde el código de ensamblado 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 valor más grande que funciona correctamente es 715827882 , es decir, piso ( INT_MAX/3 ). El fragmento de ensamblaje en -O1 es:

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 el -1431655768 es 4 * 715827882 en complemento a 2.

Al -O2 optimiza 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 el addl se movió más arriba.

Si volvemos a compilar con 715827883 entonces la versión -O1 es idéntica aparte del número cambiado y el valor de prueba. Sin embargo, -O2 luego realiza 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, %esi en -O1 , esa línea se ha eliminado para -O2 . El optimizador debe haber decidido que agregar 715827883 a %esi nunca puede ser igual a -1431655764 .

Esto es bastante desconcertante. Agregar eso a INT_MIN+1 genera el resultado esperado, por lo que el optimizador debe haber decidido que %esi nunca puede ser INT_MIN+1 y no estoy seguro de por qué lo decidirá.

En el ejemplo de trabajo, parece que sería igualmente válido concluir que agregar 715827882 a un número no puede ser igual a INT_MIN + 715827882 - 2 ! (Esto solo es posible si se produce el envolvente), pero no optimiza la 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 se std::endl(std::cout) , la optimización ya no se produce. De hecho, lo reemplazó con std::cout.put(''/n''); std::flush(std::cout); std::cout.put(''/n''); std::flush(std::cout); también hace que la optimización no suceda, aunque std::endl está en línea.

La incorporación de std::endl parece afectar la parte anterior de la estructura de bucle (que no entiendo muy bien qué es lo que está haciendo, pero la 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 mymanual enlining 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

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