Wie optimiert GCC eine nicht verwendete Variable, die in einer Schleife inkrementiert wird?

Ich habe dieses einfache C-Programm geschrieben:

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

Ich wollte sehen, wie der gcc-Compiler diese Schleife optimiert (eindeutig hinzufügen 1 2000000000 mal sollte “add 2000000000 einmal”). Also:

gcc test.c und dann time an a.out gibt:

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

$ gcc -O2 test.c und dann time ona.out` ergibt:

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

Dann habe ich beides mit zerlegt gcc -S. Das erste scheint ganz klar:

    .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 addiert, L2 vergleicht -4(%rbp) mit 1999999999 und Schleifen zu L3 if i < 2000000000.

Jetzt das Optimierte:

    .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

Ich kann überhaupt nicht verstehen, was da los ist! Ich habe wenig Ahnung von Montage, aber ich erwartete so etwas wie

addl $2000000000, -8(%rbp)

Ich habe es sogar mit versucht gcc -c -g -Wa,-a,-ad -O2 test.c um den C-Code zusammen mit der Assembly zu sehen, in die er konvertiert wurde, aber das Ergebnis war nicht klarer als das vorherige.

Kann jemand kurz erklären:

1. Das gcc-S-O2 Ausgang.
2. Ist die Schleife so optimiert, wie ich es erwartet habe (eine Summe statt vieler Summen)?

Der Compiler ist sogar noch intelligenter. 🙂

Tatsächlich erkennt es, dass Sie das Ergebnis der Schleife nicht verwenden. Es hat also die gesamte Schleife vollständig entfernt!

Das nennt man Eliminierung toter Codes.

Ein besserer Test ist, das Ergebnis auszudrucken:

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

BEARBEITEN : Ich habe das Erforderliche hinzugefügt #include <stdio.h>; das MSVC-Assembly-Listing entspricht einer Version ohne die #includesollte aber gleich sein.

Ich habe GCC im Moment nicht vor mir, da ich in Windows gebootet habe. Aber hier ist die Demontage der Version mit der printf() auf MSVC:

EDIT: Ich hatte die falsche Assembly-Ausgabe. Hier ist die richtige.

; 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

Also ja, Visual Studio führt diese Optimierung durch. Ich würde davon ausgehen, dass GCC dies wahrscheinlich auch tut.

Und ja, GCC führt eine ähnliche Optimierung durch. Hier ist eine Assembly-Liste für dasselbe Programm mit 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

Compiler haben ein paar Werkzeuge zur Verfügung, um Code effizienter oder “effizienter” zu machen:

1. Wenn das Ergebnis einer Berechnung nie verwendet wird, kann der Code, der die Berechnung durchführt, weggelassen werden (wenn die Berechnung ausgeführt wurde volatile Werte, müssen diese Werte trotzdem gelesen werden, aber die Ergebnisse des Lesens können ignoriert werden). Wenn die Ergebnisse der Berechnungen, die es gespeist haben, nicht verwendet wurden, kann der Code, der diese ausführt, ebenfalls weggelassen werden. Wenn eine solche Weglassung den Code für beide Pfade auf einer bedingten Verzweigung identisch macht, kann die Bedingung als unbenutzt angesehen und weggelassen werden. Dies hat keine Auswirkungen auf das Verhalten (außer der Ausführungszeit) von Programmen, die keine Speicherzugriffe außerhalb der Grenzen vornehmen oder das aufrufen, was Anhang L als “kritisches undefiniertes Verhalten” bezeichnen würde.

2. Wenn der Compiler feststellt, dass der Maschinencode, der einen Wert berechnet, nur Ergebnisse in einem bestimmten Bereich erzeugen kann, kann er alle bedingten Tests auslassen, deren Ergebnis auf dieser Grundlage vorhergesagt werden könnte. Wie oben, wirkt sich dies nicht auf andere Verhaltensweisen als die Ausführungszeit aus, es sei denn, der Code ruft “Critical Undefined Behaviors” auf.

3. Wenn der Compiler feststellt, dass bestimmte Eingaben irgendeine Form von undefiniertem Verhalten mit dem geschriebenen Code hervorrufen würden, würde der Standard dem Compiler erlauben, jeglichen Code wegzulassen, der nur relevant wäre, wenn solche Eingaben empfangen werden, selbst wenn das natürliche Verhalten der Ausführungsplattform Angesichts solcher Eingaben wäre dies harmlos gewesen, und das Umschreiben des Compilers würde es gefährlich machen.

Gute Compiler machen #1 und #2. Aus irgendeinem Grund ist #3 jedoch in Mode gekommen.