Как GCC оптимизирует неиспользуемую переменную, увеличивающуюся внутри цикла?

Я написал эту простую программу на C:

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

Я хотел посмотреть, как gcc-компилятор оптимизирует этот цикл (явно добавьте 1 2000000000 раз, должно быть "добавить 2000000000 один раз" ). Итак:

gcc test.c, а затем time на a.out дает:

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

$gcc -O2 test.c, а затем time on a.out` дает:

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

Затем я разобрал оба с gcc -S. Первое кажется совершенно ясным:

    .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 добавляет, L2 сравнивает -4(%rbp) с 1999999999 и переходит в L3, если i < 2000000000.

Теперь оптимизированный:

    .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

Я не могу понять, что там происходит! У меня мало знаний об сборке, но я ожидал чего-то вроде

addl $2000000000, -8(%rbp)

Я даже попытался использовать gcc -c -g -Wa, -a, -ad -O2 test.c, чтобы увидеть код C вместе со сборкой, в которую он был преобразован, но результат был не более ясно, что предыдущий.

Может кто-нибудь коротко объяснить:

Вывод gcc -S -O2.
Если цикл оптимизирован, как я ожидал (одна сумма вместо многих сумм)?

Ответ 1

Компилятор даже умнее.:)

Фактически, он понимает, что вы не используете результат цикла. Таким образом, он полностью захватил весь цикл!

Это называется Dead Code Elimination.

Лучшим тестом является печать результата:

#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: Я добавил требуемый #include <stdio.h>; список сборки MSVC соответствует версии без #include, но она должна быть одинаковой.

У меня нет GCC передо мной на данный момент, так как я загружен в Windows. Но вот разборка версии с printf() на MSVC:

EDIT: у меня был неправильный сбор. Здесь правильный.

; 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:[email protected][email protected][email protected]
    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

Итак, Visual Studio делает эту оптимизацию. Я бы предположил, что GCC, вероятно, тоже делает.

И да, GCC выполняет аналогичную оптимизацию. Здесь список сборок для той же программы с 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

Ответ 2

У компиляторов есть несколько инструментов в их распоряжении, чтобы сделать код более эффективным или более "эффективным":

Если результат вычисления никогда не используется, код, который выполняет вычисление, может быть опущен (если вычисление действовало на значения volatile, эти значения все равно должны быть прочитаны, но результаты чтения могут быть игнорируются). Если результаты вычислений, которые его подавали, не использовались, код, который их выполняет, также может быть опущен. Если такое упущение делает код для обоих путей на условной ветки одинаковым, условие может считаться неиспользованным и опущенным. Это не повлияет на поведение (отличное от времени выполнения) любой программы, которая не делает образы доступа к границам или вызывает то, что приложение L будет называть "Критические Undefined Поведения".
Если компилятор определяет, что машинный код, который вычисляет значение, может давать только результаты в определенном диапазоне, он может опустить любые условные тесты, результаты которых можно было бы предсказать на этой основе. Как и выше, это не повлияет на поведение, отличное от времени выполнения, если код не вызывает "Критические Undefined Поведения".
Если компилятор определяет, что определенные входы будут вызывать любую форму Undefined Behavior с кодом, написанным, стандарт позволит компилятору опустить любой код, который будет иметь значение только тогда, когда такие входы будут получены, даже если естественное поведение платформы исполнения, учитывая такие входы, было бы доброкачественным, и переписывание компилятора сделало бы его опасным.

Хорошие компиляторы делают # 1 и # 2. По какой-то причине, однако, номер 3 стал модным.