Metody realizacji języków programowania/MRJP Wykład 4

Autor: Artur Zaroda (zaroda@mimuw.edu.pl)

Wprowadzenie do maszyn wirtualnych

Rodzaje realizacji języków programowania

Wspólnym elementem realizacji języków programowania jest tzw. przód (ang. front-end), który zajmuje się rozpoznawaniem programu w języku źródłowym. Rezultat jego pracy, np. w formie drzewa struktury uzupełnionego o tablicę symboli, trafia na wejście tzw. tyłu (ang. back-end), którego zadaniem jest umożliwienie wykonania rozpoznanego programu.

Ze względu na sposób pracy tego drugiego etapu, realizacje języków programowania można podzielić na kilka kategorii:

• kompilator - tłumaczy program w języku źródłowym na program w języku docelowym

• translator - jak wyżej, ale tłumaczenie konstrukcji języka źródłowego na konstrukcje języka docelowego odbywa się w dużym stopniu jeden do jednego

• interpreter - wykonuje program posługując się jego reprezentacją

Podział ten nie jest ścisły - wiele realizacji można zaliczyć do kilku kategorii. W szczególności, realizacje języków programowania tradycyjnie nazywane interpreterami składają się zwykle z dwóch części: program źródłowy jest kompilowany do postaci pośredniej, która następnie trafia na wejście interpretera.

Język docelowy kompilatora a maszyny wirtualne

Język docelowy kompilatora zwykle nie pokrywa się z językiem maszyny rzeczywistej, na której programy mają działać.

Po pierwsze, niektórych cech procesora wykonującego program kompilator nie wykorzystuje. W takiej sytuacji można powiedzieć, że maszyna docelowa jest podzbiorem maszyny rzeczywistej wykonującej program.

Po drugie, podczas pracy program musi wykonywać operacje związane np. z zarządzaniem pamięcią czy wejściem-wyjściem, które nie mają swoich odpowiedników na liście instrukcji rozumianych przez procesor. Dlatego też generowany kod jest uzupełniany o tzw. system czasu wykonania (ang. run-time system), który można uznać za rozszerzenie maszyny docelowej.

Autor kompilatora ma więc możliwość odrzucenia pewnych cech maszyny docelowej i uzupełnienia jej o inne. Może też posłużyć się zupełnie nowym modelem maszyny, która nie będzie miała bezpośredniego związku z żadną maszyną rzeczywistą. Konstrukcję taką nazywamy maszyną wirtualną (abstrakcyjną).

Głównym powodem stosowania maszyny wirtualnej realizacji języka programowania jest chęć uproszczenie kompilatora. Znacznie łatwiej napisać generator kodu na zaprojektowaną przez nas maszynę, niż generator kodu maszynowego rzeczywistego procesora. Szczególnie dobrze widać to na przykładzie procesorów x86, których nieregularna lista instrukcji i trybów adresowania połączona z bardzo małą liczbą dostępnych rejestrów sprawia wiele problemów autorom generatorów kodu.

Oprócz względnej łatwości implementacji generatora kodu, zastosowanie maszyny wirtualnej w realizacji języka programowania ma i inne zalety. Między innymi ułatwia przenoszenie kompilatora, a nawet wygenerowanego przez niego kodu, na inne systemy, ułatwia też kontrolowanie programu podczas jego wykonania.

Maszyn wirtualnych zwykle nie stosuje się, gdy ważniejsza od łatwości realizacji języka programowania jest dla nas efektywność kodu wynikowego.

Projektowanie maszyn wirtualnych

Maszynę wirtualną projektujemy tak, by jak najbardziej uprościć generator kodu. Choć nie musi ona mieć żadnego związku z maszyną rzeczywistą, projektując ją powinniśmy też brać pod uwagą łatwość i efektywność jej realizacji.

Zaprojektowanie uniwersalnej maszyny wirtualnej, mimo wielokrotnie podejmowanych prób, jak dotąd się nie udało. Te, które powstają, są przeznaczone dla realizacji określonego języka lub rodziny podobnych języków, np. maszyny wirtualne Javy (tzw. JVM), Smalltalka, Prologu.

W latach 70, na potrzeby realizacji języka Pascal, stworzono maszynę wirtualną nazywaną p-code. Nazwa ta do dziś bywa używana jako synonim języka maszyny wirtualnej. W p-code i maszynach do niej podobnych, większość instrukcji pobiera argumenty ze stosu i tam odkłada wynik. Maszyny takie nazywamy maszynami stosowymi (ang. stack machine). Stosowy model maszyny jest szczególnie przydatny w realizacjach języków proceduralnych. Po uzupełnieniu o niezbędne elementy, można go też stosować w realizacjach języków obiektowych. Przykładem maszyny stosowej jest maszyna wirtualna Javy.

Wadą stosowego modelu maszyny wirtualnej jest brak możliwości efektywnego wykorzystania rejestrów rzeczywistego procesora wykonującego kod tak, by ograniczyć ilość operacji przesyłania wartości z i do pamięci. Można wprawdzie przyjąć, że wartość z czubka stosu będzie przechowywana w wyróżnionym rejestrze, a nie w pamięci, ale rozszerzenie tego pomysłu na większą liczbę wartości, by wykorzystać kilka czy kilkanaście dostępnych rejestrów, jest w praktyce zbyt trudne. Dlatego też, jako alternatywę lub rozszerzenie modelu stosowego, używa się czasem tzw. maszyn rejestrowych (ang. register machine), w których argumenty operacji przechowywane są w (wirtualnych) rejestrach. Ponieważ nadal mamy tu do czynienia z maszyną wirtualną, nie jesteśmy w tym przypadku ograniczeni liczbą rejestrów rzeczywistego procesora. Możemy np. przyjąć, że nasza maszyna ma 256 rejestrów.

Przykład maszyny wirtualnej

Najprostszym modelem maszyny wirtualnej dla realizacji języków proceduralnych, takich jak Pascal lub C, jest maszyna stosowa. W dalszej części tekstu będziemy się posługiwali maszyną wirtualną, którą nazwiemy Naszą Maszyną Wirtualną (w skrócie NMW). Poniżej przedstawiamy jej definicję.

Pamięć NMW składa się ze słów, z których każde mieści liczbę całkowitą lub adres. Adresy kolejnych słów w pamięci różnią się o 1.

W pamięci znajduje się stos, który rośnie w kierunku malejących adresów. W chwili rozpoczęcia wykonania programu stos jest pusty.

Dwa słowa w pamięci, których adresy będziemy oznaczali symbolicznie SP i FP, mają specjalne znaczenie. W komórce o adresie SP jest zapisany wskaźnik czubka stosu, będący adresem wartości znajdującej się aktualnie na czubku stosu. Zawartość tej komórki jest automatycznie modyfikowana przez instrukcje maszyny. Komórką pamięci o adresie FP będziemy się posługiwali podczas realizacji mechanizmu wywołania i powrotu z funkcji/procedury.

Oto instrukcje rozpoznawane przez NMW:

CONST stała

odkłada na stos wartość stałej przekazanej jako argument

LOAD

odkłada na stos wartość pobraną spod adresu zdjętego z czubka stosu

STORE

zdejmuje ze stosu adres, następnie zdejmuje ze stosu wartość i wkłada ją pod ten adres

ADD

dodawanie, zdejmuje ze stosu najpierw prawy a następnie lewy argument i odkłada na stos ich sumę

SUB

jak wyżej, ale liczy różnicę

MUL

jak wyżej, ale liczy iloczyn

DIV

jak wyżej, ale liczy iloraz

DUP

odkłada na stos wartość znajdującą się na czubku stosu

DROP

usuwa wartość z czubka stosu

SWAP

zamienia kolejność dwóch wartości na czubku stosu

GOTO

zdejmuje ze stosu adres i skacze do instrukcji znajdującej się pod tym adresem

CALL

zdejmuje ze stosu adres i skacze do instrukcji znajdującej się pod tym adresem, na stos odkłada adres następnej instrukcji za instrukcją CALL

EQ

zdejmuje ze stosu dwie wartości i wkłada na stos wartość niezerową, jeśli wartości były równe, a zero, jeśli były różne

NE

jak wyżej, ale sprawdza, czy wartości są różne

LT

jak wyżej, ale sprawdza, czy wartość pod czubkiem stosu jest mniejsza od wartości na czubku stosu

LE

jak wyżej, ale sprawdza, czy mniejsza lub równa

GT

jak wyżej, ale sprawdza, czy większa

GE

jak wyżej, ale spreawdza, czy większa lub równa

IFTRUE

zdejmuje ze stosu adres a następnie wartość i skacze pod ten adres, jeśli wartość była reprezentacją prawdy (wartość niezerowa)

IFFALSE

zdejmuje ze stosu adres a następnie wartość i skacze pod ten adres, jeśli wartość była reprezentacją fałszu (czyli zerem)

READ

wczytuje z wejścia liczbę całkowitą i wkłada jej wartość na stos

WRITE

zdejmuje wartość z czubka stosu i wypisuje ją na wyjście

STOP

zatrzymuje pracę maszyny

W dalszej części tego tekstu, zapisując kod, będziemy pomijali słowo CONST w instrukcji odkładającej na stos stałą. Dzięki temu każda instrukcja będzie zapisywana jako pojedyncze słowo w tekście programu, co ułatwi czytanie kodu

Nie zakładamy, że każda instrukcja musi się znajdować w odzielnym wierszu kodu źródłowego. Tam, gdzie to poprawi czytelność, możemy w jednym wierszu zapisać kilka instrukcji.

Ponadto, zapisując kod będziemy się posługiwali adresami symbolicznymi (etykietami) instrukcji. Miejsce w kodzie, które chcemy oznaczyć, poprzedzimy identyfikatorem z dwukropkiem. Adres tego miejsca będzie dostępny za pośrednictwem użytego identyfikatora.

Realizacja maszyny wirtulnej

Instrukcje maszyn wirtualnych zazwyczaj nie są bezpośrednio rozumiane przez sprzęt, choć spotyka się też projekty ich sprzętowej realizacji.

Najczęściej, kod generowany na maszynę wirtualną jest zapisywany np. do pliku, a następnie trafia na wejście oddzielnego programu, nazywanego interpreterem maszyny wirtualnej, który go wykonuje. Główną częścią interpretera jest pętla odczytująca kolejne instrukcje do wykonania. Wewnątrz tej pętli znajduje się instrukcja wyboru (case, switch) rozpoznająca i wykonująca instrukcję maszyny wirtualnej. Całość może wyglądać np. tak:

program interpreter_kodu_maszyny_wirtualnej;
... {deklaracje}
var
  pc   : integer; {licznik rozkazów}
  prog : array [0..N] of instrukcja; {interpretowany program}
  aktualna : instrukcja;
begin
  ... {wczytanie programu do tablicy prog}
  pc := 0;
  while true do begin
    aktualna := prog[pc];
    pc := pc + 1;
    case aktualna of
      ADD : ... {wykonanie instrukcji}
      ... {gałęzie case obsługujące pozostałe instrukcje}
    end
  end
end.

Gdyby okazało się, że efektywność tak zbudowanej realizacji nie jest dla nas wystarczająca, możemy sięgnąć po inne rozwiązania. Najprostszym byłoby przesłanie generowanego przez nasz kompilator kodu maszyny wirtualnej na wejście kolejnego kompilatora, który przetłumaczy go na kod maszyny rzeczywistej. Można też bezpośrednio połączyć oba kompilatory tak, by generator kodu kompilatora pierwszego nie tworzył instrukcji maszyny wirtualnej, lecz informował kompilator drugi, co chce wygenerować. Generator kodu kompilatora drugiego, po otrzymaniu takiej informacji, produkowałby kod maszyny rzeczywistej mający taki efekt, jaki powinna mieć aktualna instrukcja maszyny wirtualnej.

Spotyka się też rozwiązania będące hybrydą interpretera i kompilatora - interpreter podczas wykonania programu uruchamia kompilator, by przetłumaczyć fragmenty kodu szczególnie istotne dla jego efektywności. Technika ta nosi nazwę JIT (ang. just-in-time compilation). Przy jej zastosowaniu, generując kod możemy korzystać z informacji, które są dostępne podczas wykonania programu, np. informacji o tym, jak często, gdy wykonujemy daną instrukcję warunkową, warunek jest spełniony. Ta wiedza może nam umożliwić wybór bardziej efektywnego wariantu kodu i tym samym poprawić efektywność całego programu.

Jeśli stwierdzimy, że tłumaczenie pojedynczych instrukcji maszyny wirtualnej na instrukcje maszyny rzeczywistej, nawet z wykorzystaniem informacji dostępnych podczas działania programu, nie daje nam kodu wystarczająco efektywnego, musimy sięgnąć po inny sposób realizacji języka programowania. Klasyczny model kompilacji, w którym generuje się kod pośredni, podlegający następnie optymalizacji, zostanie omówiony później.

Podstawy kompilacji na maszynę wirtualną

Budowa kompilatora generującego kod maszyny wirtualnej, który jest następnie interpretowany, jest często najłatwiejszym i najmniej pracochłonnym sposobem realizacji języka programowania.

Algorytm generatora kodu

Najprostszy algorytm generacji kodu opiera się na schemacie translacji sterowanej składnią. Generator kodu ma postać rekurencyjnej procedury, która rozwiązuje problem tłumaczenia pojedynczej konstrukcji składniowej, zwykle reprezentowanej przez jeden węzeł w drzewie struktury. Jeśli węzeł ten nie jest liściem, jego poddrzewami zajmują się rekurencyjne wywołania generatora kodu.

Realizacja wyrażeń

Maszyna stosowa może wykonywać operacje arytmetyczne wyłącznie na wartościach znajdujących się na stosie. Jedynym sensownym sposobem realizacji wyrażeń arytmetycznych jest więc obliczenie obu argumentów (wyniki będą na stosie) a następnie wykonanie na nich operacji, np. "W1+W2" tłumaczymy jako:

         [W1]
         [W2]
         ADD 

Np. tłumaczeniem "x/(y-5)" będzie:

         adres_x
         LOAD
         adres_y
         LOAD
         5
         SUB
         DIV

Kosztem, jaki płacimy za łatwość generacji kodu dla wyrażeń na maszynę stosową jest nieefektywność kodu. Maszyny rzeczywiste mają zwykle możliwość operowania na wartościach w rejestrach lub pod wskazanymi adresami w pamięci. Na maszynie stosowej z tego nie korzystamy.

Realizacja instrukcji

Przypisanie

Kod dla przypisania, gdy po lewej stronie jest zwykła zmienna, składa się z instrukcji liczących wartość wyrażenia z prawej strony i z instrukcji STORE zdejmującej wynik na zmienną. Przypisanie postaci "zmienna := E" tłumaczymy więc na:

         [E]
         adres_zmiennej
         STORE

gdzie adres_zmiennej reprezentuje adres, pod którym w pamięci znajduje się wartość zmiennej, na którą przypisujemy.

Np. tłumaczeniem "x:=y*z" będzie:

         adres_y
         LOAD
         adres_z
         LOAD
         MUL
         adres_x
         STORE

Podobnie realizujemy przypisania, po których lewej stronie występuje nie zmienna prosta, lecz złożone wyrażenie, reprezentujące np. odwołanie do elementu tablicy, pola rekordu itp. W wyniku obliczenia wyrażenia po lewej stronie przypisania otrzymamy nie jego wartość, jak to jest z wypadku wyrażenia po prawej stronie, lecz adres komórki pamięci, do której mamy wpisać wartość. Tłumaczenie instrukcji przypisania "E := F" będzie więc miało postać:

         [F]
         [E]
         STORE

Pętla typu "repeat ... until ..."

Teraz przejdziemy do omówienia sposobu realizacji konstrukcji, które wymagają bardziej złożonego schematu przepływu sterowania. Skupimy się na realizacji instrukcji warunkowych i pętli.

Spośród wszystkich rodzajów pętli, najłatwiej będzie nam zrealizować pętlę "repeat L until E":

tresc:
         [L]
         [E]
         tresc
         IFFALSE

Np. tłumaczeniem "repeat x:=x+2 until x>10" będzie:

tresc:
         adres_x
         LOAD
         2
         ADD
         adres_x
         STORE
         adres_x
         LOAD
         10
         GT
         tresc
         IFFALSE

Instrukcja warunkowa "if ... then ..."

Najprostszą formą instrukcji warunkowej jest "if E then I", którą możemy tłumaczyć na:

         [E]
         koniec
         IFFALSE
         [I]
koniec:

Np. tłumaczeniem "if x<0 then x:=0-x" będzie:

         adres_x
         LOAD
         0
         LT
         koniec
         IFFALSE
         0
         adres_x
         LOAD
         SUB
         adres_x
         STORE
koniec:

Instrukcja warunkowa "if ... then ... else ..."

Dla instrukcji warunkowej "if E then I1 else I2" naturalnym tłumaczeniem jest:

         [E]
         po_else
         IFFALSE
         [I1]
         koniec
         GOTO
po_else:
         [I2]
koniec:

Np. tłumaczeniem "if x<y then z:=y else z:=x" będzie:

         adres_x
         LOAD
         adres_y
         LOAD
         LT
         po_else
         IFFALSE
         adres_y
         LOAD
         adres_z
         STORE
         koniec
         GOTO
po_else:
         adres_x
         LOAD
         adres_z
         STORE
koniec:

Pętla "while ... do ..."

Dla pętli "while ... do ..." można podać trzy różne sposoby realizacji, z których każdy jest sensowny:

warunek:
         [E]
         koniec
         IFFALSE
         [I]
         warunek
         GOTO
koniec:

         warunek
         GOTO
tresc:
         [I]
warunek:
         [E]
         tresc
         IFTRUE

         [E]
         koniec
         IFFALSE
tresc:
         [I]
         [E]
         tresc
         IFTRUE
koniec:

Pierwszy wariant jest efektywny, jeśli często warunek pętli jest od razu fałszywy a wariant drugi, jeśli do treści pętli zwykle wchodzi się przynajmniej raz. Wariant trzeci łączy oba rozwiązania, ale daje dłuższy kod (wyrażenie występuje dwa razy), co może spowodować, że będzie działał wolniej.

Np. tłumaczeniem "while x>0 do x:=x-10" zgodnie z pierwszym z tych schematów będzie:

warunek:
         adres_x
         LOAD
         0
         GT
         koniec
         IFFALSE
         adres_x
         LOAD
         10
         SUB
         adres_x
         STORE
         warunek
         GOTO
koniec: