Dlaczego GCC generuje tak radykalnie różne montaże dla prawie tego samego kodu C?

Question

Dlaczego GCC generuje tak radykalnie różne montaże dla prawie tego samego kodu C?

Podczas pisania zoptymalizowanej funkcji ftol znalazłem bardzo dziwne zachowanie w GCC 4.6.1. Pozwól, że najpierw pokażę Ci kod (dla jasności zaznaczyłem różnice):

Fast_trunc_one, C:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = mantissa << -exponent;                       /* diff */
    } else {
        r = mantissa >> exponent;                        /* diff */
    }

    return (r ^ -sign) + sign;                           /* diff */
}

Fast_trunc_two, C:

int fast_trunc_two(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = (mantissa << -exponent) ^ -sign;             /* diff */
    } else {
        r = (mantissa >> exponent) ^ -sign;              /* diff */
    }

    return r + sign;                                     /* diff */
}

Wydaje się to samo prawda? GCC się nie zgadza. Po skompilowaniu z gcc -O3 -S -Wall -o test.s test.c jest to wyjście asemblera:

Fast_trunc_one, wygenerowano:

_fast_trunc_one:
LFB0:
    .cfi_startproc
    movl    4(%esp), %eax
    movl    $150, %ecx
    movl    %eax, %edx
    andl    $8388607, %edx
    sarl    $23, %eax
    orl $8388608, %edx
    andl    $255, %eax
    subl    %eax, %ecx
    movl    %edx, %eax
    sarl    %cl, %eax
    testl   %ecx, %ecx
    js  L5
    rep
    ret
    .p2align 4,,7
L5:
    negl    %ecx
    movl    %edx, %eax
    sall    %cl, %eax
    ret
    .cfi_endproc

Fast_trunc_two, wygenerowano:

_fast_trunc_two:
LFB1:
    .cfi_startproc
    pushl   %ebx
    .cfi_def_cfa_offset 8
    .cfi_offset 3, -8
    movl    8(%esp), %eax
    movl    $150, %ecx
    movl    %eax, %ebx
    movl    %eax, %edx
    sarl    $23, %ebx
    andl    $8388607, %edx
    andl    $255, %ebx
    orl $8388608, %edx
    andl    $-2147483648, %eax
    subl    %ebx, %ecx
    js  L9
    sarl    %cl, %edx
    movl    %eax, %ecx
    negl    %ecx
    xorl    %ecx, %edx
    addl    %edx, %eax
    popl    %ebx
    .cfi_remember_state
    .cfi_def_cfa_offset 4
    .cfi_restore 3
    ret
    .p2align 4,,7
L9:
    .cfi_restore_state
    negl    %ecx
    sall    %cl, %edx
    movl    %eax, %ecx
    negl    %ecx
    xorl    %ecx, %edx
    addl    %edx, %eax
    popl    %ebx
    .cfi_restore 3
    .cfi_def_cfa_offset 4
    ret
    .cfi_endproc

To jest ekstremalna różnica. To faktycznie pojawia się również na profilu, fast_trunc_one jest o około 30% szybsze niż fast_trunc_two. Teraz moje pytanie: co jest tego przyczyną?

185

c compiler-optimization gcc assembly x86

Author: phuclv, 2012-04-20

Source

3 answers

Taka jest natura kompilatorów. Zakładanie, że pójdą najszybszą lub najlepszą drogą, jest całkiem fałszywe. Każdy, kto sugeruje, że nie musisz nic robić z kodem, aby zoptymalizować, ponieważ "nowoczesne Kompilatory" wypełniają puste pola, wykonują najlepszą pracę, tworzą najszybszy kod itp. Właściwie to widziałem, że gcc jest gorsze od 3.x do 4.przynajmniej x na ramieniu. 4.x mógł złapać do 3.x w tym momencie, ale na początku produkował wolniejszy kod. Z praktyką możesz nauczyć się pisać swój kod tak aby kompilator nie musi pracować tak ciężko i w rezultacie daje bardziej spójne i oczekiwane wyniki.

Błąd tutaj jest Twoje oczekiwania co do tego, co zostanie wyprodukowane, a nie co zostało faktycznie wyprodukowane. Jeśli chcesz, aby kompilator generował to samo wyjście, podaj mu to samo wejście. Matematycznie nie takie same, nie takie same, ale właściwie takie same, bez różnych ścieżek, bez współdzielenia lub dystrybucji operacji z jednej wersji do drugiej. Jest to dobre ćwiczenie w zrozumieniu, jak napisać swój kod i sprawdzanie, co z nim robią Kompilatory. Nie popełnij błędu i nie zakładaj, że ponieważ jedna wersja gcc dla jednego procesora docelowego pewnego dnia dała pewien wynik, że jest to reguła dla wszystkich kompilatorów i całego kodu. Musisz użyć wielu kompilatorów i wielu celów, aby poczuć, co się dzieje.

Gcc jest dość paskudny, zapraszam do zajrzenia za kurtynę, spojrzenia na wnętrzności gcc, spróbowania dodać cel lub zmodyfikować coś samodzielnie. Jest ledwo trzymany razem przez taśmę klejącą i drut. Dodatkowa linia kodu dodana lub usunięta w krytycznych miejscach i rozpada się. Fakt, że w ogóle wyprodukował użyteczny kod, jest czymś, z czego można się cieszyć, zamiast martwić się o to, dlaczego nie spełnił innych oczekiwań.

Czy przyjrzałeś się jakie wersje GCC produkują? 3.x i 4.x w szczególności 4.5 vs 4.6 vs 4.7, itp? i dla różnych procesorów docelowych, x86, arm, mips itp. lub różnych smaków x86, jeśli jest to natywny kompilator, którego używasz, 32 bit vs 64 bit, itp? A potem llvm (clang) dla różnych celów?

Mystic wykonał świetną robotę w procesie myślowym wymaganym do pracy nad problemem analizy / optymalizacji kodu, oczekując, że kompilator wymyśli cokolwiek z tego, cóż, nie oczekuje się od żadnego "nowoczesnego kompilatora".

Bez wchodzenia w właściwości matematyczne, Kod tej postaci

if (exponent < 0) {
  r = mantissa << -exponent;                       /* diff */
} else {
  r = mantissa >> exponent;                        /* diff */
}
return (r ^ -sign) + sign;                           /* diff */

Doprowadzi kompilator do A: zaimplementuj go w tej formie, wykonaj if-then-else then converge na wspólnym kodzie, aby zakończyć i powrócić. lub B: Zapisz gałąź, ponieważ jest to koniec funkcji. Również nie kłopocz się używaniem lub zapisywaniem r.

if (exponent < 0) {
  return((mantissa << -exponent)^-sign)+sign;
} else {
  return((mantissa << -exponent)^-sign)+sign;
}

Następnie można dostać się do jak mistyczne wskazał zmienna znak znika wszystkie razem dla kodu, jak napisano. Nie spodziewałbym się, że kompilator zobaczy zmienną sign, więc powinieneś zrobić to sam i nie zmuszać kompilatora, aby próbował to rozgryźć.

To doskonała okazja, by zagłębić się w gcc kod źródłowy. Wygląda na to, że znalazłeś przypadek, w którym optymalizator widział jedną rzecz w jednym przypadku, a drugą w innym przypadku. Następnie wykonaj następny krok i sprawdź, czy gcc nie może zobaczyć tej sprawy. Każda optymalizacja jest tam, ponieważ jakaś osoba lub grupa rozpoznała optymalizację i celowo ją tam umieściła. Aby ta optymalizacja była tam i działała za każdym razem, gdy ktoś musi ją tam umieścić (a następnie przetestować, a następnie utrzymać ją w przyszłości).

Zdecydowanie nie Załóżmy, że mniej kodu jest szybsze, a więcej kodu jest wolniejsze, bardzo łatwo jest stworzyć i znaleźć przykłady, które nie są prawdziwe. Częściej może być tak, że mniej kodu jest szybsze niż więcej kodu. Jak pokazałem od początku, można jednak utworzyć więcej kodu, aby zapisać rozgałęzianie w tym przypadku lub zapętlenie, itp., a wynik netto będzie szybszy kod.

Najważniejsze jest to, że podałeś kompilator z innego źródła i spodziewałeś się tych samych wyników. Problemem nie jest kompilator wyjście, ale oczekiwania użytkownika. Dość łatwo jest zademonstrować dla konkretnego kompilatora i procesora dodanie jednej linii kodu, która sprawia, że cała funkcja jest znacznie wolniejsza. Na przykład dlaczego zmiana a = b+ 2; Na A = b + c + 2; powoduje, że _fill_in_the_blank_compiler_name_ generuje radykalnie inny i wolniejszy kod? Odpowiedź oczywiście była taka, że kompilator był zasilany innym kodem na wejściu, więc jest to całkowicie poprawne, aby kompilator generował inne wyjście. (jeszcze lepiej jest, gdy zamienisz dwa niepowiązane linie kodu i spowodujesz radykalną zmianę wyjścia) nie ma oczekiwanej zależności między złożonością i rozmiarem wejścia a złożonością i rozmiarem wyjścia. Wrzuć coś takiego do clang:

for(ra=0;ra<20;ra++) dummy(ra);

Wyprodukował około 60-100 linii asemblera. Rozwinął pętlę. Nie liczyłem linii, jeśli się nad tym zastanowić, to trzeba dodać, skopiować wynik na wejście do wywołania funkcji, zrobić funkcję połączenie, minimum trzy operacje. więc w zależności od celu, który jest prawdopodobnie 60 instrukcji co najmniej, 80 jeśli cztery na pętlę, 100 jeśli pięć na pętlę, itp.

63

Author: old_timer,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2019-10-02 07:34:50

Mysticial już dał świetne Wyjaśnienie, ale pomyślałem, że dodam, FWIW, że naprawdę nie ma nic fundamentalnego o tym, dlaczego kompilator miałby dokonać optymalizacji dla jednego, a nie drugiego.

Kompilator clang LLVM daje na przykład ten sam kod dla obu funkcji (z wyjątkiem nazwy funkcji), dając:

_fast_trunc_two:                        ## @fast_trunc_one
        movl    %edi, %edx
        andl    $-2147483648, %edx      ## imm = 0xFFFFFFFF80000000
        movl    %edi, %esi
        andl    $8388607, %esi          ## imm = 0x7FFFFF
        orl     $8388608, %esi          ## imm = 0x800000
        shrl    $23, %edi
        movzbl  %dil, %eax
        movl    $150, %ecx
        subl    %eax, %ecx
        js      LBB0_1
        shrl    %cl, %esi
        jmp     LBB0_3
LBB0_1:                                 ## %if.then
        negl    %ecx
        shll    %cl, %esi
LBB0_3:                                 ## %if.end
        movl    %edx, %eax
        negl    %eax
        xorl    %esi, %eax
        addl    %edx, %eax
        ret

Ten kod nie jest tak krótki jak pierwsza wersja gcc z OP, ale nie tak długi jak druga.

Kod z innego kompilatora (którego nie będę nazwa), kompilując dla x86_64, tworzy to dla obu funkcji:

fast_trunc_one:
        movl      %edi, %ecx        
        shrl      $23, %ecx         
        movl      %edi, %eax        
        movzbl    %cl, %edx         
        andl      $8388607, %eax    
        negl      %edx              
        orl       $8388608, %eax    
        addl      $150, %edx        
        movl      %eax, %esi        
        movl      %edx, %ecx        
        andl      $-2147483648, %edi
        negl      %ecx              
        movl      %edi, %r8d        
        shll      %cl, %esi         
        negl      %r8d              
        movl      %edx, %ecx        
        shrl      %cl, %eax         
        testl     %edx, %edx        
        cmovl     %esi, %eax        
        xorl      %r8d, %eax        
        addl      %edi, %eax        
        ret

Co jest fascynujące, ponieważ oblicza obie strony if, a następnie używa warunkowego ruchu na końcu, aby wybrać właściwy.

Kompilator Open64 tworzy:

fast_trunc_one: 
    movl %edi,%r9d                  
    sarl $23,%r9d                   
    movzbl %r9b,%r9d                
    addl $-150,%r9d                 
    movl %edi,%eax                  
    movl %r9d,%r8d                  
    andl $8388607,%eax              
    negl %r8d                       
    orl $8388608,%eax               
    testl %r8d,%r8d                 
    jl .LBB2_fast_trunc_one         
    movl %r8d,%ecx                  
    movl %eax,%edx                  
    sarl %cl,%edx                   
.Lt_0_1538:
    andl $-2147483648,%edi          
    movl %edi,%eax                  
    negl %eax                       
    xorl %edx,%eax                  
    addl %edi,%eax                  
    ret                             
    .p2align 5,,31
.LBB2_fast_trunc_one:
    movl %r9d,%ecx                  
    movl %eax,%edx                  
    shll %cl,%edx                   
    jmp .Lt_0_1538

I podobny, ale nie identyczny, kod dla fast_trunc_two.

W każdym razie, jeśli chodzi o optymalizację, to loteria - jest jaka jest... Nie zawsze jest łatwo wiedzieć, dlaczego kod jest kompilowany sposób.

23

Author: Charphacy,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-04-30 05:40:17

score 256 · Accepted Answer

Aktualizacja do synchronizacji z edycją OP

Majstrując przy kodzie, udało mi się zobaczyć, jak GCC optymalizuje pierwszą sprawę.

Zanim zrozumiemy, dlaczego są tak różne, najpierw musimy zrozumieć, jak GCC optymalizuje fast_trunc_one().

Wierz lub nie, fast_trunc_one() jest zoptymalizowany do tego:

int fast_trunc_one(int i) {
    int mantissa, exponent;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);

    if (exponent < 0) {
        return (mantissa << -exponent);             /* diff */
    } else {
        return (mantissa >> exponent);              /* diff */
    }
}

To tworzy dokładnie ten sam zespół co oryginalny fast_trunc_one() - nazwy rejestrów i wszystko.

Zauważ, że nie ma xor s w Zgromadzenie dla fast_trunc_one(). To mnie zdradziło.

Jak to?

Krok 1: sign = -sign

Najpierw przyjrzyjmy się zmiennej sign. Od sign = i & 0x80000000; istnieją tylko dwie możliwe wartości, które sign mogą przyjmować:

sign = 0
sign = 0x80000000

Teraz rozpoznaj to w obu przypadkach, sign == -sign. Dlatego, gdy zmienię oryginalny kod na ten:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = mantissa << -exponent;
    } else {
        r = mantissa >> exponent;
    }

    return (r ^ sign) + sign;
}

Produkuje dokładnie taki sam montaż jak oryginalny fast_trunc_one(). Oszczędzę Ci zgromadzenia, ale jest identyczne-rejestry i w ogóle.

Krok 2: redukcja matematyczna: x + (y ^ x) = y

sign może przyjmować tylko jedną z dwóch wartości, 0 lub 0x80000000.

gdy x = 0, to x + (y ^ x) = y wtedy trywialne
dodawanie i xoring przez 0x80000000 jest takie samo. Odwraca znak. Dlatego x + (y ^ x) = y posiada również x = 0x80000000.

Dlatego x + (y ^ x) zmniejsza się do y. A kod upraszcza do to:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = (mantissa << -exponent);
    } else {
        r = (mantissa >> exponent);
    }

    return r;
}

Ponownie, to kompiluje się do dokładnie tego samego zestawu-nazw rejestrów i wszystkich.

Powyższa wersja ostatecznie redukuje się do tego:

int fast_trunc_one(int i) {
    int mantissa, exponent;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);

    if (exponent < 0) {
        return (mantissa << -exponent);             /* diff */
    } else {
        return (mantissa >> exponent);              /* diff */
    }
}

Czyli prawie dokładnie to, co GCC generuje w złożeniu.

Więc dlaczego kompilator nie optymalizuje fast_trunc_two() do tego samego?

Kluczową częścią fast_trunc_one() jest optymalizacja x + (y ^ x) = y. W fast_trunc_two() wyrażenie x + (y ^ x) jest dzielone na gałęzie.

Podejrzewam, że to wystarczy aby pomylić GCC, aby nie dokonać tej optymalizacji. (Musiałby podnieść ^ -sign z gałęzi i połączyć go z r + sign na końcu.)

Na przykład, to tworzy ten sam zespół co fast_trunc_one():

int fast_trunc_two(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = ((mantissa << -exponent) ^ -sign) + sign;             /* diff */
    } else {
        r = ((mantissa >> exponent) ^ -sign) + sign;              /* diff */
    }

    return r;                                     /* diff */
}