¿Cómo optimiza GCC una variable no utilizada que se incrementa dentro de un ciclo?

Question

escribí este sencillo programa C:

int main() { 
    int i; 
    int count = 0; 
    for(i = 0; i < 2000000000; i++){ 
     count = count + 1; 
    } 
} 

quería ver cómo el compilador gcc optimiza este bucle (añadir claridad 1 2000000000 tiempos deben ser "agregan una vez"). Por lo tanto:

gcc test.c y luego en timea.out da:

real 0m7.717s 
user 0m7.710s 
sys 0m0.000s 

$ gcc -O2 test.c y luego time on a.out` da:

real 0m0.003s 
user 0m0.000s 
sys 0m0.000s 

Luego desarmé ambos con gcc -S. El primero parece bastante claro:

.file "test.c" 
    .text 
.globl main 
    .type main, @function 
main: 
.LFB0: 
    .cfi_startproc 
    pushq %rbp 
    .cfi_def_cfa_offset 16 
    movq %rsp, %rbp 
    .cfi_offset 6, -16 
    .cfi_def_cfa_register 6 
    movl $0, -8(%rbp) 
    movl $0, -4(%rbp) 
    jmp .L2 
.L3: 
    addl $1, -8(%rbp) 
    addl $1, -4(%rbp) 
.L2: 
    cmpl $1999999999, -4(%rbp) 
    jle .L3 
    leave 
    .cfi_def_cfa 7, 8 
    ret 
    .cfi_endproc 
.LFE0: 
    .size main, .-main 
    .ident "GCC: (Ubuntu/Linaro 4.5.2-8ubuntu4) 4.5.2" 
    .section .note.GNU-stack,"",@progbits 

L3 añade, L2 comparar con -4(%rbp)1999999999 y loops a L3 si i < 2000000000.

Ahora el uno optimizado:

.file "test.c" 
    .text 
    .p2align 4,,15 
.globl main 
    .type main, @function 
main: 
.LFB0: 
    .cfi_startproc 
    rep 
    ret 
    .cfi_endproc 
.LFE0: 
    .size main, .-main 
    .ident "GCC: (Ubuntu/Linaro 4.5.2-8ubuntu4) 4.5.2" 
    .section .note.GNU-stack,"",@progbits 

No puedo entender en absoluto lo que está pasando allí! Tengo poco conocimiento de montaje, pero me esperaba algo así como

addl $2000000000, -8(%rbp) 

Incluso probé con gcc -c -g -Wa, -a, -ad -O2 test.c para ver el código C junto con el conjunto al que se convirtió, pero el resultado no fue más claro que el anterior.

Puede alguien explicar brevemente:

1. El gcc -S salida O2.
2. Si el bucle está optimizado como esperaba (¿una suma en lugar de muchas sumas)?

Answer 1

El compilador es aún más inteligente que eso. :)

De hecho, se da cuenta de que no está utilizando el resultado del ciclo. ¡Así que sacó todo el ciclo por completo!

Esto se llama Dead Code Elimination.

Una prueba mejor es imprimir el resultado:

#include <stdio.h> 
int main(void) { 
    int i; int count = 0; 
    for(i = 0; i < 2000000000; i++){ 
     count = count + 1; 
    } 

    // Print result to prevent Dead Code Elimination 
    printf("%d\n", count); 
} 

EDIT: He añadido la requerida #include <stdio.h>; el listado del ensamblado de MSVC corresponde a una versión sin el #include, pero debería ser el mismo.

---

No tengo GCC en frente de mí en este momento, ya que estoy en Windows. Pero aquí está el desmontaje de la versión con el printf() en MSVC:

EDITAR: tuve una salida de ensamblaje incorrecta. Esta es la correcta.

; 57 : int main(){ 

$LN8: 
    sub rsp, 40     ; 00000028H 

; 58 : 
; 59 : 
; 60 :  int i; int count = 0; 
; 61 :  for(i = 0; i < 2000000000; i++){ 
; 62 :   count = count + 1; 
; 63 :  } 
; 64 : 
; 65 :  // Print result to prevent Dead Code Elimination 
; 66 :  printf("%d\n",count); 

    lea rcx, OFFSET FLAT:??_C@_03PMGGPEJJ@?$CFd?6?$AA@ 
    mov edx, 2000000000    ; 77359400H 
    call QWORD PTR __imp_printf 

; 67 : 
; 68 : 
; 69 : 
; 70 : 
; 71 :  return 0; 

    xor eax, eax 

; 72 : } 

    add rsp, 40     ; 00000028H 
    ret 0 

Así que sí, Visual Studio hace esta optimización. Supongo que GCC probablemente también lo haga.

Y sí, GCC realiza una optimización similar. He aquí una lista de ensamblaje para el mismo programa con gcc -S -O2 test.c (gcc 4.5.2, Ubuntu 11.10, 86):

 .file "test.c" 
     .section  .rodata.str1.1,"aMS",@progbits,1 
.LC0: 
     .string "%d\n" 
     .text 
     .p2align 4,,15 
.globl main 
     .type main, @function 
main: 
     pushl %ebp 
     movl %esp, %ebp 
     andl $-16, %esp 
     subl $16, %esp 
     movl $2000000000, 8(%esp) 
     movl $.LC0, 4(%esp) 
     movl $1, (%esp) 
     call __printf_chk 
     leave 
     ret 
     .size main, .-main 
     .ident "GCC: (Ubuntu/Linaro 4.5.2-8ubuntu4) 4.5.2" 
     .section  .note.GNU-stack,"",@progbits 

Answer 2

compiladores tienen algunas herramientas a su disposición para hacer el código más eficiente o más "eficiente":

1. Si no se usa nunca el resultado de un cálculo, el código que realiza el cálculo se puede omitir (si el cálculo actúa sobre volatile valores, esos valores deben todavía ser leídos, pero los resultados de la lectura pueden ser ignorados). Si los resultados de los cálculos que lo alimentaron no se usaron, también se puede omitir el código que los realiza. Si tal omisión hace que el código para ambas rutas en una rama condicional sea idéntico, la condición puede considerarse como no utilizada y omitida. Esto no tendrá ningún efecto sobre los comportamientos (que no sean el tiempo de ejecución) de ningún programa que no haga accesos de memoria fuera de límites ni invoque lo que el Anexo L llamaría "Comportamientos no definidos críticos".

2. Si el compilador determina que el código máquina que calcula un valor solo puede producir resultados en un cierto rango, puede omitir cualquier prueba condicional cuyo resultado pueda predecirse sobre esa base. Como se indicó anteriormente, esto no afectará los comportamientos que no sean el tiempo de ejecución a menos que el código invoque "Comportamientos no definidos críticos".

3. Si el compilador determina que ciertas entradas invocarían cualquier forma de Comportamiento Indefinido con el código tal como está escrito, el Estándar permitiría al compilador omitir cualquier código que solo sería relevante cuando tales entradas se reciban, incluso si el el comportamiento de la plataforma de ejecución dado que tales entradas hubieran sido benignas y la reescritura del compilador lo harían peligroso.

Buenos compiladores do # 1 and # 2. Por alguna razón, sin embargo, # 3 se ha puesto de moda.