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

Question

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

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

Я хотел увидеть, как GCC компилятор оптимизирует этот цикл (очевидно, добавить 2000000000 раз должны быть «добавить один раз»). Итак:

НКУ test.c, а затем time на a.out дает:

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

$ НКУ -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

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

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

Это называется 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:??_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 стала модной.