Dlaczego kompilatorzy nalegają na użycie rejestru zapisanego przez adresata?

10

Rozważ ten kod C:

void foo(void);

long bar(long x) {
    foo();
    return x;
}

Kiedy kompiluję to na GCC 9.3 z jednym -O3lub -Os, otrzymuję to:

bar:
        push    r12
        mov     r12, rdi
        call    foo
        mov     rax, r12
        pop     r12
        ret

Dane wyjściowe z clang są identyczne, z wyjątkiem wyboru rbxzamiast r12rejestru zapisanego przez użytkownika.

Jednak chcę / oczekuję, że zobaczę zespół, który wygląda mniej więcej tak:

bar:
        push    rdi
        call    foo
        pop     rax
        ret

Po angielsku oto co się dzieje:

  • Wciśnij starą wartość rejestru zapisanego przez odbiorcę na stos
  • Przejdź xdo rejestru zapisanego przez użytkownika
  • Połączenie foo
  • Przejdź xz rejestru zapisanego przez odbiorcę do rejestru wartości zwracanej
  • Pop stos, aby przywrócić starą wartość rejestru zapisanego przez odbiorcę

Po co w ogóle męczyć się z rejestrem zapisanym przez callee? Dlaczego nie zrobić tego zamiast tego? Wydaje się krótszy, prostszy i prawdopodobnie szybszy:

  • Wciśnij xna stos
  • Połączenie foo
  • Wyskakuj xze stosu do rejestru wartości zwracanej

Czy mój zespół się myli? Czy jest to w jakiś sposób mniej wydajne niż bałagan z dodatkowym rejestrem? Jeśli odpowiedź na oba z nich brzmi „nie”, to dlaczego GCC lub brzęk nie robią tego w ten sposób?

Link Godbolt .


Edycja: Oto mniej trywialny przykład, aby pokazać, że tak się dzieje, nawet jeśli zmienna jest użyta w sposób znaczący:

long foo(long);

long bar(long x) {
    return foo(x * x) - x;
}

Rozumiem:

bar:
        push    rbx
        mov     rbx, rdi
        imul    rdi, rdi
        call    foo
        sub     rax, rbx
        pop     rbx
        ret

Wolę to:

bar:
        push    rdi
        imul    rdi, rdi
        call    foo
        pop     rdi
        sub     rax, rdi
        ret

Tym razem jest tylko jedna instrukcja w porównaniu do dwóch, ale podstawowa koncepcja jest taka sama.

Link Godbolt .

Joseph Sible-Reinstate Monica
źródło
4
Ciekawa pominięta optymalizacja.
fuz
1
najprawdopodobniej zostanie przyjęte, że przekazany parametr zostanie wykorzystany, więc chcesz zapisać zmienny rejestr i zachować przekazany parametr w rejestrze nie na stosie, ponieważ kolejne dostępy do tego parametru są szybsze z rejestru. przekaż x foo, a zobaczysz to. więc jest to prawdopodobnie zwykła część konfiguracji ramki stosu.
old_timer
oczywiście widzę, że bez foo nie używa stosu, więc tak jest to pominięta optymalizacja, ale coś, co ktoś musiałby dodać, przeanalizować funkcję i jeśli wartość nie zostanie użyta i nie będzie konfliktu z tym rejestrem (ogólnie jest jest).
old_timer
backend arm robi to również na gcc. więc prawdopodobnie nie backend
old_timer
clang 10 tej samej historii (backend arm).
old_timer

Odpowiedzi:

5

TL: DR:

  • Elementy wewnętrzne kompilatora prawdopodobnie nie są skonfigurowane tak, aby łatwo wyszukiwać tę optymalizację, i prawdopodobnie jest to przydatne tylko w przypadku małych funkcji, a nie w dużych funkcjach między wywołaniami.
  • W większości przypadków lepszym rozwiązaniem jest chęć tworzenia dużych funkcji
  • Może wystąpić opóźnienie w stosunku do kompromisu przepustowości, jeśli foozdarzy się, że nie zapisze / nie przywróci RBX.

Kompilatory to złożone elementy maszyn. Nie są „inteligentni” jak ludzie, a drogie algorytmy pozwalające znaleźć każdą możliwą optymalizację często nie są warte kosztów w dodatkowym czasie kompilacji.

Zgłosiłem to jako błąd GCC 69986 - możliwy mniejszy kod z -Os poprzez użycie push / pop do rozlewania / przeładowywania z powrotem w 2016 roku ; nie było żadnej aktywności ani odpowiedzi od twórców GCC. : /

Nieznacznie powiązane: błąd GCC 70408 - ponowne użycie tego samego rejestru zachowanego wywołania dałoby w niektórych przypadkach mniejszy kod - twórcy kompilatora powiedzieli mi, że zajmie to dużo pracy, aby GCC mógł wykonać tę optymalizację, ponieważ wymaga to kolejności sortowania oceny dwóch foo(int)wywołań w oparciu o to, co uprościłoby cel asm.


Jeśli foo się nie zapisuje / nie przywraca rbx, istnieje kompromis między przepływnością (liczbą instrukcji) a dodatkowym opóźnieniem przechowywania / przeładowania w xłańcuchu zależności -> retval.

Kompilatory zwykle preferują opóźnienie nad przepustowością, np. Używając 2x LEA zamiast imul reg, reg, 10(3-cyklowe opóźnienie, 1 / przepustowość zegara), ponieważ większość kodu średnio znacznie mniej niż 4 uops / zegar na typowych 4-szerokich potokach, takich jak Skylake. (Więcej instrukcji / uopsów zajmuje więcej miejsca w ROB, zmniejszając jednak to, jak daleko może zobaczyć to samo okno poza kolejnością, a wykonanie jest w rzeczywistości pęknięte, a przeciągnięcia prawdopodobnie odpowiadają za mniej niż 4 uops / średnia zegara).

Jeśli foopush / pop RBX, to niewiele można zyskać na opóźnieniu. Przywracanie odbywa się tuż przed, a retnie zaraz po nim, chyba nie ma to znaczenia, chyba że wystąpi błąd w retprzepowiedni lub błąd I-cache, który opóźnia pobranie kodu z adresu zwrotnego.

Większość nietrywialnych funkcji zapisuje / przywraca RBX, więc często nie jest dobrym założeniem, że pozostawienie zmiennej w RBX w rzeczywistości oznacza, że ​​naprawdę pozostała w rejestrze przez połączenie. (Chociaż losowe wybieranie funkcji rejestrów z zachowaniem połączeń może być czasem dobrym rozwiązaniem).


Więc tak push rdi/ pop raxbyłby bardziej wydajny w tym przypadku, i prawdopodobnie jest to pominięta optymalizacja dla drobnych funkcji nie-liściowych, w zależności od tego, co foorobi i równowagi między dodatkowym opóźnieniem przechowywania / przeładowania w xporównaniu do większej liczby instrukcji zapisywania / przywracania dzwoniącego rbx.

Możliwe jest, że metadane rozwijania stosu reprezentują tutaj zmiany w RSP, tak jak gdyby używał sub rsp, 8do przelania / przeładowania xdo slotu stosu. (Ale kompilatory też nie znają tej optymalizacji wykorzystania pushrezerwy miejsca i inicjalizacji zmiennej. Jaki kompilator C / C ++ może używać instrukcji push pop do tworzenia zmiennych lokalnych, zamiast tylko zwiększać esp raz? I robić to więcej niż jeden lokalny var doprowadziłby do zwiększenia .eh_framemetadanych związanych z odwijaniem stosu, ponieważ przesuwasz wskaźnik stosu oddzielnie z każdym wypchnięciem. Nie powstrzymuje to jednak kompilatorów przed użyciem push / pop do zapisywania / przywracania zachowanych połączeń.


IDK, gdyby warto uczyć kompilatory, jak szukać tej optymalizacji

Może to dobry pomysł na całą funkcję, a nie na jedno wywołanie wewnątrz funkcji. I jak powiedziałem, opiera się na pesymistycznym założeniu, że i footak uratuje / przywróci RBX. (Lub optymalizacja pod kątem przepustowości, jeśli wiesz, że opóźnienie od x do wartości zwracanej nie jest ważne. Ale kompilatory nie wiedzą o tym i zwykle optymalizują pod kątem opóźnienia).

Jeśli zaczniesz przyjmować to pesymistyczne założenie w wielu kodach (jak w przypadku pojedynczych wywołań funkcji w funkcjach), zaczniesz otrzymywać więcej przypadków, w których RBX nie zostanie zapisany / przywrócony i mógłbyś skorzystać.

Nie chcesz także tego dodatkowego zapisu / przywracania push / pop w pętli, po prostu zapisz / przywróć RBX poza pętlą i użyj rejestrów zachowanych w pętli, które wykonują wywołania funkcji. Nawet bez pętli, w ogólnym przypadku większość funkcji wykonuje wiele wywołań funkcji. Ten pomysł optymalizacji może być zastosowany, jeśli naprawdę nie używasz xżadnego z wywołań, tuż przed pierwszym i po ostatnim, w przeciwnym razie masz problem z utrzymaniem wyrównania stosu 16 bajtów dla każdego, calljeśli wykonujesz jeden pop po zadzwoń, przed kolejnym połączeniem.

Kompilatory nie są świetne w drobnych funkcjach. Ale nie jest to również świetne dla procesorów. Wywołania funkcji innych niż wbudowane mają najlepszy wpływ na optymalizację, chyba że kompilatory widzą elementy wewnętrzne odbiorcy i przyjmują więcej założeń niż zwykle. Nieliniowe wywołanie funkcji jest niejawną barierą pamięci: osoba dzwoniąca musi założyć, że funkcja może odczytać lub zapisać dane globalnie dostępne, więc wszystkie takie zmienne muszą być zsynchronizowane z maszyną abstrakcyjną C. (Analiza ucieczki pozwala przechowywać mieszkańców w rejestrach między połączeniami, jeśli ich adres nie uniknął funkcji). Ponadto kompilator musi założyć, że wszystkie rejestry z zablokowanymi wywołaniami są zablokowane. To zasysa zmiennoprzecinkowe w systemie V 86-64, który nie ma rejestrów XMM z zachowaniem wywołania.

Małe funkcje, takie jak, bar()lepiej wpasowują się w swoich rozmówców. Skompiluj, -fltoaby w większości przypadków mogło się to zdarzyć nawet ponad granicami plików. (Wskaźniki funkcji i granice biblioteki współużytkowanej mogą to pokonać).


Myślę, że jednym z powodów, dla których kompilatory nie zadały sobie trudu przeprowadzenia tych optymalizacji, jest to, że wymagałoby to całej gamy różnych kodów we wnętrzu kompilatora , innych niż normalny stos vs. kod alokacji rejestru, który wie, jak zapisać zachowane wywołanie rejestruje i używa ich.

tj. byłoby dużo pracy do wdrożenia i dużo kodu do utrzymania, a jeśli zrobi się to zbyt entuzjastycznie, może to pogorszyć kod.

A także, że (miejmy nadzieję) nie ma to znaczenia; jeśli ma to znaczenie, powinieneś być wbudowany barw jego rozmówcę lub foow bar. Jest to w porządku, chyba że istnieje wiele różnych barfunkcji i foojest duże, a z jakiegoś powodu nie mogą włączyć się do swoich rozmówców.

Peter Cordes
źródło
nie jestem pewien, czy warto pytać, dlaczego jakiś kompilator tłumaczy kod w ten sposób, kiedy lepiej użyć ..., jeśli nie błąd w tłumaczeniu. na przykład możliwe pytanie, dlaczego clang tak dziwny (niezoptymalizowany) przetłumaczył pętlę, porównaj z gcc, icc, a nawet msvc
RbMm
1
@RbMm: Nie rozumiem twojego zdania. To wygląda na zupełnie oddzielną pominiętą optymalizację clang, niezwiązaną z tym, o co chodzi w tym pytaniu. Błędy pominiętej optymalizacji istnieją, aw większości przypadków powinny zostać naprawione. Śmiało i zgłoś to na stronie bugs.llvm.org
Peter Cordes,
tak, mój przykład kodu absolutnie niezwiązany z pierwotnym pytaniem. po prostu kolejny przykład dziwnego (jak na mój wygląd) tłumaczenia (i tylko jednego kompilatora clang). ale wynik kodu asm i tak jest poprawny. tylko nie najlepszy i eveen nie natywny porównaj gcc / icc / msvc
RbMm