Zadanie 3

Generacja kodu na procesory ARM

Zadanie polega na napisaniu prostego generatora kodu na procesory ARM. Danymi wejściowymi będzie ciąg prostych operacji arytmetycznych, a zadaniem generatora będzie wygenerowanie realizujących je rozkazów procesora ARM oraz zadbanie o efektywne użycie rejestrów.

Generator będzie generował kod jednej funkcji. Jej jedynym argumentem jest adres tablicy 32-bitowych liczb całkowitych ze znakiem o ustalonym rozmiarze. Wyniki funkcji również będą wpisywane do tej tablicy. Jedynym rozważanym typem danych jest 32-bitowa liczba całkowita ze znakiem. Argumentami operacji są stałe liczbowe lub zmienne. Zmienne mają nazwy ti, gdzie i jest liczbą całkowitą z przedziału od 1 do 512.

Format wejścia

W pierszej linii standardowego wejścia generator otrzyma liczby całkowite n, k i l oddzielone pojedynczym odstępem. Liczba n, mieszcząca się w przedziale od 1 do 1000, oznacza liczbę operacji. Liczby k i l, mieszczące się w przedziale od 1 do 512, są liczbą elementów odpowiednio wejściowych i wyjściowych.

W kolejnych n wierszach znajdują się operacje. W każdym wierszu jest opisana jedna operacja. Opis operacji składa się z nazwy operacji, nazwy zmiennej docelowej oraz dwóch argumentów. Elementy opisu są oddzielone pojedynczym odstępem. Argumentem jest nazwa zmiennej lub stała liczbowa zapisana w postaci dziesiętnej, być może z minusem. Jeśli operacja potrzebuje tylko jednego argumentu, to jako drugi jest podana stała liczbowa 0.

Uzupełnienie: Wśród argumentów operacji arytmetycznych, czyli wszystkich operacji z wyjątkiem operacji przypisania, będzie co najmniej jedna zmienna. Nie będzie zatem wyrażeń, których wartość można obliczyć w trakcie generowania kodu. Argumentem przypisania może być jednak stała.

W tym zadaniu można założyć, że format wejścia jest dokładnie taki, jak opisany powyżej. Generator może zachowywać się dowolnie przy niepoprawnym wejściu.

Lista operacji

+
dodawanie
-
odejmowanie
*
mnożenie
<<
przesunięcie bitowe w lewo
>>
przesunięcie bitowe w prawo (arytmetyczne)
&
iloczyn bitowy (and)
|
suma bitowa (or)
^
rozłączna suma bitowa (xor)
=
przypisanie (tylko jeden argument)

Wymagania dotyczące wygenerowanego kodu

Ciąg operacji podany na wejściu zakłada, że kolejne elementy z tablicy argumentów znajdują się w zmiennych od t1 do tk. Wyniki funkcji są umieszczane w zmiennych od t1 do tl.

Wygenerowany kod otrzyma w rejestrze r0 adres tablicy liczb całkowitych o rozmiarze max(k, l). Przed wywołaniem funkcji początkowe wartości zmiennych od t1 do tk zostaną umieszczone w k początkowych pozycjach tej tablicy. Wygenerowany kod powinien umieścić końcowe wartości zmiennych od t1 do tl w l początkowych pozycjach tej tablicy.

Funkcja powinna zachowywać wartość rejestrów od r4 do r11 i r13. Funkcja może dowolnie wykorzystywać tablicę podaną jako argument, może też przechowywać zmienne lokalne na stosie.

Kod powinien zostać wygenerowany w składni asemblera GNU. Początek funkcji powinien zostać oznaczony symbolem funkcja.

Przykład

Dla wejścia (uwaga: zgodnie ze specyfikacją w ostatnim wierszu jest nieznaczące 0, przez niedopatrzenie wcześniej go zabrakło): 
3 3 1
* t4 t1 t2
+ t5 t4 t3
= t1 t5 0
poprawnym kodem jest na przykład: 
        .text
        .global funkcja
funkcja:
        ldr     r1, [r0]
        ldr     r2, [r0, #4]
        ldr     r3, [r0, #8]
        mul     r2, r1, r2
        add     r2, r2, r3
        str     r2, [r0]
        mov     pc, lr

Punktacja

Na temat generowania efektywnego kodu napisano już wiele i generator, o którym tutaj mowa, można by ulepszać dowolnie długo. Nie oczekuję więc zbyt złożonych rozwiązań. Wymienię tylko kilka cech generatora wraz z przybliżoną ich oceną. Wybrałem te techniki optymalizacji, które są dość proste w implementacji i są bliskie tematyce programowania w asemblerze.

Za prosty generator, który generuje poprawny kod, ale każdej zmiennej przypisuje stałe miejsce w rejestrze, tablicy przekazanej jako argument lub na stosie można otrzymać do 4 punktów.

Za dynamiczną alokację rejestrów (czyli możliwość przypisywania różnych zmiennych do jednego rejestru w różnych fragmentach kodu) można uzyskać do 5 dodatkowych punktów. Nie oczekuję tu zbyt wymyślnych algorytmów. Warto pomyśleć o heurystykach.

Za łączenie operacji, które mogą być wykonane w jednym rozkazie (np. przesunięcie bitowe i dodawanie lub mnożenie i dodawanie) do 4 dodatkowych punktów.

Nie każda stała może być podana jako argument natychmiastowy, niektóre muszą być ładowane z pamięci. Za efektywne korzystanie ze stałych można uzyskać do 2 dodatkowych punktów.

Rozwiązania będę oceniał głównie na podstawie poprawności i szybkości wygenerowanego przez nie kodu dla pewnej liczby przypadków. Przypadki testowe zostaną dobrane tak, by testować wyżej wymienione cechy.

Na potrzeby tego zadania można przyjąć, że rozkazy przesłania do i z pamięci oraz mnożenia zajmują trzy jednostki czasu, a pozostałe jedną.

Nie będę zwracał szczególnej uwagi na techniki, które nie zależą od konkretnego procesora. To znaczy, że można je zaimplementować, ale testy nie będą ich premiowały. Mam na myśli techniki takie jak eliminacja wspólnych podwyrażeń lub przekształcenia arytmetyczne (np. a+a+a+a = 4a).

Uzupełnienie. Poniżej znajduje się bardziej szczegółowy opis technik, których nie będę oceniał.

Powyższe techniki mają mniej wspólnego z programowaniem w asemblerze i mogą być przeprowadzone na takiej reprezentacji programu, jaką otrzymuje generator kodu. Z tego powodu testy przygotuję tak, jakby powyższe przekształcenia zostały już na nich wykonane.

Forma

Generator można zaimplementować w dowolnym języku programowania. Powinien działać pod Linuksem w wydziałowym laboratorium. Powinien wczytywać wejście ze standardowego wejścia oraz wypisywać kod na standardowe wyjście. Proszę o dołączenie do rozwiązania krótkiego opisu zastosowanych technik optymalizacji.

Sposób oddania

Rozwiązania proszę nadsyłać na adres tmal@mimuw.edu.pl do końca sesji wrześniowej.

Aby zaliczyć laboratorium na 5 należy przed rozpoczęciem sesji czerwcowej przesłać rozwiązania zadań warte w sumie co najmniej 22 punkty. Do samego zaliczenia potrzeba 12 punktów.