Comment GCC optimise-t-il une variable inutilisée incrémentée dans une boucle ?

Question

J'ai écrit ce simple programme en C :

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

Je voulais voir comment le compilateur gcc optimise cette boucle (ajouter clairement 1 2000000000 fois devrait être "ajouter 2000000000 une fois"). Donc :

gcc test.c et ensuite time sur a.out donne :

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

$ gcc -O2 test.c et ensuite time on a.out` donne :

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

Puis j'ai démonté les deux avec gcc -S . La première semble assez claire :

    .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 ajoute, L2 compare -4(%rbp) avec 1999999999 et boucle vers L3 si i < 2000000000 .

Maintenant, l'optimisé :

    .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

Je ne comprends pas du tout ce qui se passe là-bas ! J'ai peu de connaissances en assemblage, mais je m'attendais à quelque chose comme

addl $2000000000, -8(%rbp)

J'ai même essayé avec gcc -c -g -Wa,-a,-ad -O2 test.c pour voir le code C ainsi que l'assemblage vers lequel il a été converti, mais le résultat n'était pas plus clair que le précédent.

Quelqu'un peut-il m'expliquer brièvement :

1. Le site gcc -S -O2 sortie.
2. Si la boucle est optimisée comme je le pensais (une seule somme au lieu de plusieurs) ?

Answer 1

Le compilateur est encore plus malin que ça :)

En fait, il se rend compte que vous n'utilisez pas le résultat de la boucle. Donc il a enlevé toute la boucle complètement !

C'est ce qu'on appelle Élimination des codes morts .

Un meilleur test consiste à imprimer le résultat :

#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 : J'ai ajouté les éléments requis #include <stdio.h> ; le listing de l'assemblage MSVC correspond à une version sans l'option #include mais cela devrait être la même chose.

---

Je n'ai pas GCC sous les yeux pour le moment, puisque je suis en train de démarrer sous Windows. Mais voici le désassemblage de la version avec la fonction printf() sur MSVC :

EDIT : J'avais la mauvaise sortie d'assemblage. Voici la bonne.

; 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

Donc oui, Visual Studio fait cette optimisation. Je suppose que GCC le fait probablement aussi.

Et oui, GCC effectue une optimisation similaire. Voici un listing d'assemblage pour le même programme avec gcc -S -O2 test.c (gcc 4.5.2, Ubuntu 11.10, x86) :

        .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

Les compilateurs ont quelques outils à leur disposition pour rendre le code plus efficace ou plus "efficient" :

1. Si le résultat d'un calcul n'est jamais utilisé, le code qui effectue le calcul peut être omis (si le calcul a agi sur volatile ces valeurs doivent toujours être lues mais les résultats de la lecture peuvent être ignorés). Si les résultats des calculs qui l'ont alimenté ne sont pas utilisés, le code qui les effectue peut également être omis. Si cette omission rend le code des deux chemins d'une branche conditionnelle identique, la condition peut être considérée comme inutilisée et omise. Cela n'aura aucun effet sur les comportements (autre que le temps d'exécution) de tout programme qui n'effectue pas d'accès mémoire hors limites ou qui n'invoque pas ce que l'annexe L appellerait des "comportements critiques non définis".

2. Si le compilateur détermine que le code machine qui calcule une valeur ne peut produire des résultats que dans une certaine fourchette, il peut omettre tout test conditionnel dont le résultat pourrait être prédit sur cette base. Comme ci-dessus, cela n'affectera pas les comportements autres que le temps d'exécution, à moins que le code n'invoque des "Comportements indéfinis critiques".

3. Si le compilateur détermine que certaines entrées invoqueraient une forme quelconque de comportement non défini avec le code tel qu'il est écrit, la norme permettrait au compilateur d'omettre tout code qui ne serait pertinent que lorsque ces entrées sont reçues, même si le comportement naturel de la plate-forme d'exécution compte tenu de ces entrées aurait été bénin et que la réécriture du compilateur le rendrait dangereux.

Les bons compilateurs font le n°1 et le n°2. Cependant, pour une raison quelconque, le point 3 est devenu à la mode.