Szukam sposobu alokacji zmiennych lokalnych do rejestrów. Jestem świadomy kilku poważnych metod, aby to zrobić (mianowicie tych wymienionychna Wikipedii), ale utknąłem na tym, jak „rozlewa się”. Również odpowiednia literatura jest dość onieśmielająca. Mam nadzieję, że jest coś prostszego, które spełni moje priorytety:

Poprawność - algorytm, który wygeneruje poprawny kod niezależnie od liczby zmiennych lokalnych.Prostota - coś, co mogę zrozumieć bez konieczności czytania zbyt dużej ilości literatury.Wydajność - musi być lepsza niż obecna metoda, czyli:

Przetłumacz operacjęx = y # z do:

movl y, %eax
movl z, %ebx
op %ebx, %eax
movl %eax, x

Ponieważ atakuję Intel 386, niektóre istotne ograniczenia to:

Operacje binarne przyjmują dwa argumenty, z których jeden jest źródłem i miejscem docelowym. Operacje unarne przyjmują pojedynczy argument.Operacje mogą uzyskać dostęp tylko do jednej lokalizacji pamięci; dlatego operacje binarne wymagają co najmniej jednego argumentu w rejestrze.Dostępnych jest maksymalnie sześć rejestrów:%eax %ebx %ecx %edx %esi %edi. (%ebp może również zostać uwzględniony w ostateczności.)Istnieją specjalne przypadki, takie jak dzielenie liczb całkowitych i rejestry powrotne, ale na razie mogę je zignorować.

W tym momencie kompilator wykonuje trzy kroki:

i386ification: wszystkie operacje są konwertowane na formularza = a # b (luba = #a dla operacji jednostkowych).Analiza żywotności: określane są zestawy zmiennych na żywo przed i po każdej operacji.Przydział rejestru: wykres interferencji jest zbudowany i kolorowy.

A potem kompilator wyrzuca kredki w powietrze i nie wie, co robić dalej.

Przykład

public int mf(int cr, int ci) {
    int i = 0;
    int zr = 0;
    int zi = 0;

    while (i < 100 && zr*zr + zi*zi < 4) {
        int t = zr * zr - zi * zi + cr;
        zi = 2 * zr * zi + ci;
        zr = t;

        i = i + 1;
    }
    return i;
}

Oto dość ładny wykres zakłóceń dla funkcji i CFG z informacją o żywotności. Obraz CFG wymaga niestety przewijania w pionie.

Wykres interferencji dla funkcji dla 14 zmiennychWykres przepływu sterowania dla funkcji z informacjami o żywotności

Wykorzystano siedem kolorów. Chciałbym rozlać jeden z nich (lub zestaw zmiennych przypisanych temu kolorowi). Metoda wyboru, która nie jest zbyt ważna. Podstępne jest to, jak poradzić sobie z rozlanymi zmiennymi.

Powiedzmy, że rozlewam „różowy”, który jest zbiorem zmiennycht, $t4, $t7. Oznacza to, że te operacje odnoszące się do jednej z tych zmiennych będą miały do ​​niego dostęp z jego pozycji na ramce stosu, a nie poprzez rejestr. To powinno działać w tym przykładzie.

Ale co, jeśli program był:

...
a = a + b
...

i obojea ib trzeba było się rozlać? Nie mogę wyemitować instrukcjiaddl b, a z dwoma adresami pamięci. Potrzebowałbym kolejnego zapasowego rejestru, aby tymczasowo zatrzymać jeden z operandów, a to oznacza rozlanie innego koloru. Sugeruje to ogólną metodę:

Jeśli wszystkie zmienne można pokolorowaćr kolory, świetnie!W przeciwnym razie rozlewaj niektóre kolory i związane z nimi zmienne.Jeśli istnieje operacja, która uzyskuje dostęp do dwóch rozlanych zmiennych, wylej inny kolor i użyj zapasowego rejestru do tymczasowego przechowywania wszystkich takich operacji.

W tym momencie podejrzewam, że rozlewa się znacznie więcej rzeczy niż jest to konieczne i zastanawiam się, czy jest jakiś sprytniejszy sposób na rozlanie rzeczy, taki jak rozlanie części życia zmiennej, a nie cała sama zmienna. Czy są jakieś proste techniki, których mogę tutaj użyć? Ponownie nie celuję szczególnie wysoko - na pewno nie na tyle wysoko, by wymagać czytania zbyt głębokiego. ;-)

Specyficzne problemy

Główny specyficzny problem to: kiedy zmienna jest rozlana, jak wpływa to na generowane instrukcje? Czy wszystkie instrukcje używające tej zmiennej muszą mieć do niej bezpośredni dostęp (z pozycji stosu)? Jak to zadziała, jeśli operacja wykorzystuje dwie rozlane zmienne? (Architektura nie pozwala na dostęp do dwóch różnych lokalizacji pamięci).

Dodatkowe problemy to:

Jak określić, gdzie wstawić instrukcje ładowania / przechowywania, dla poprawności (a co ważniejsze, wydajności)?Czy mogę rozlać zmienną tylko przez tę część swojego życia, gdy nie jest ona w użyciu natychmiastowym, a następnie rozpakować ją później? Aby wszystkie instrukcje działały na niewypełnionych rejestrach. Zmienna może żyć w różnych rejestrach w różnym czasie.Czy mogę być bardziej wydajny w szczególnych przypadkach. Na przykład,%eax jest używana do zwracanej wartości, więc byłoby miło, gdyby zwracana zmienna została przydzielona do tego rejestru do czasu napotkania zwrotu. Podobnie, niektóre rejestry są „callee-save”, więc jeśli w czasie wywołania funkcji wystąpiło mniej zmiennych, przypisanie ich do rejestrów niezapisanych oznaczałoby, że mogę uniknąć przechowywania tych rejestrów.Czy formularz SSA pomoże dużo (jeśli w ogóle)? Możliwość wyeliminowania typowych podwyrażeń i oceny stałych może zmniejszyć (?) Ciśnienie rejestru, ale w przeciwnym razie miałoby to jakiś wpływ?

Aspekty, którymi się nie przejmuję (w tej chwili) to:

Alokacja i optymalizacja stosu: jest już implementowana naiwnie i może być w razie potrzeby zoptymalizowana za pomocą wykresu interferencji.Wydajność podczas kompilacji, tak długo, jak się kończy. (NP-kompletność nie oznacza, że ​​danego algorytmu należy unikać).Aktualizacja

Przepraszam za przestój - zastanawiałem się nad udzielonymi odpowiedziami i próbowałem znaleźć łatwe podejście, aby rozpocząć wdrażanie niektórych pomysłów. Szczerze mówiąc, zwlekałem ...: -

Znalazłem bardzo fajną prezentację (niestety PPT):

http://www.cs.princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt

Który odpowiada na pytanie, jak radzić sobie z konkretnymi potrzebami operacyjnymi (np. Korzystanie z tego samego rejestru dla źródła i miejsca docelowego lub wymaganie określonego rejestru dla niektórych operacji). Nie jestem pewien, czy cykl Liveness-Coloring-Allocation kończy się.

Spróbuję wkrótce wykonać pewną pracę i mam nadzieję, że zamknę to pytanie.