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

Question

Я написал эту простую программу на 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 on 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 вместе со сборкой, в которую он был преобразован, но результата не было Более понятно, что предыдущий.

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

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

Answer 1

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

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

Это называется Устранение мертвого кода .

Лучший тест - распечатать результат:

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

РЕДАКТИРОВАТЬ: Я добавил необходимые #include <stdio.h>; листинг сборки MSVC соответствует версии без #include, но он должен быть таким же.

---

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

РЕДАКТИРОВАТЬ: у меня был неправильный вывод сборки. Вот правильный.

; 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

Так что да, 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

Answer 2

Компиляторы имеют в своем распоряжении несколько инструментов, чтобы сделать код более эффективным или более «эффективным»:

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

2. Если компилятор определяет, что машинный код, который вычисляет значение, может давать результаты только в определенном диапазоне, он может пропустить любые условные тесты, результат которых может быть предсказан на этой основе. Как указано выше, это не повлияет на поведение, отличное от времени выполнения, если код не вызывает «Критическое неопределенное поведение».

3. Если компилятор определит, что определенные входные данные будут вызывать любую форму неопределенного поведения с кодом, как написано, Стандарт позволит компилятору пропустить любой код, который будет иметь значение только при получении таких входных данных, даже если естественное поведение платформы выполнения, учитывая такие входные данные, было бы доброкачественным, и переписывание компилятора сделало бы его опасным.

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