Tekst źródłowy strony 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 wykonywania.

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

=== 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. 

Mimo wielokrotnie podejmowanych prób, jak dotąd nie udało się zaprojektować uniwersalnej maszyny wirtualnej. 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 siedemdziesiątych 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 przyjąć, że wartość znajdująca się na wierzchołku stosu będzie przechowywana w wyróżnionym rejestrze a nie w pamięci. Rozszerzenie tego pomysłu na większą liczbę wartości, by wykorzystać kilka czy kilkanaście dostępnych rejestrów, jest jednak 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 stosu, który jest adresem wartości znajdującej się aktualnie na wierzchołku 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 ze 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 wierzchołku stosu

; '''DROP''' : usuwa wartość z wierzchołka stosu

; '''SWAP''' : zamienia kolejność dwóch wartości na wierzchołku 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 po instrukcji '''CALL'''

; '''EQ''' : zdejmuje ze stosu dwie wartości i wkłada na stos wartość niezerową, jeśli wartości były równe, lub 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 wierzchołkiem stosu jest mniejsza od wartości na wierzchołku 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 sprawdza, czy większa lub równa

; '''IFTRUE''' : zdejmuje ze stosu adres a potem wartość i skacze pod ten adres, jeśli wartość była reprezentacją prawdy (wartość niezerowa)

; '''IFFALSE''' : zdejmuje ze stosu adres a potem 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ść ze 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.

=== Pamięć maszyny wirtualnej ===

Podczas wykonania programu w pamięci znajduje się jego kod. Ze względów bezpieczeństwa można go umieścić w obszarze chronionym przed zapisem.

Dane programu dzielimy na:

; automatyczne
: Ich czas życia jest wyznaczony przez czas działania procedury/funkcji. Dane te umieszczane są zwykle na stosie. Więcej na ten temat napiszemy w następnym wykładzie.

; kontrolowane
: Mogą powstawać i ginąć, na żądanie programisty, w dowolnym momencie wykonania programu. Dane te umieszczane są na stercie (ang. heap), której obsługa jest tematem oddzielnego wykładu.

; statyczne
: Istnieją przez cały czas wykonania programu (np. stałe).

Na dane należące do każdej z tych kategorii przeznaczamy zwykle oddzielny obszar pamięci. Sposób reprezentacji danych zależy tylko od ich typu, nie od miejsca, w którym się znajdują. Liczba całkowita w pamięci będzie wyglądała tak samo na stosie jak i na stercie.

Wpływ na reprezentację danych mają również cechy realizowanego języka programowania.
Języki z typami dynamicznymi wymagają, by dane w pamięci zawierały informację o typie. W przypadku języków z typami statycznymi, których realizację będziemy omawiali w dalszej części tego wykładu, informacja o typie znajduje się tylko w kodzie źródłowym.  

=== Realizacja maszyny wirtualnej ===

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 kodu maszyny wirtualnej generowanego przez nasz kompilator 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, który ma taki efekt, jaki powinna mieć aktualna instrukcja maszyny wirtualnej.

Na przykład instrukcję

 ADD

Naszej Maszyny Wirtualnej moglibyśmy przetłumaczyć na dwie instrukcje procesora Pentium (zapisane w składni AT&T):

 popl %eax
 addl %eax, (%esp)

W niektórych przypadkach na instrukcje maszyny docelowej można tłumaczyć nie pojedyncze instrukcje maszyny wirtualnej, lecz ich ciągi. Np. ciąg instrukcji:

 FP LOAD 2 ADD LOAD

można, przy założeniu, że rolę rejestru FP maszyny wirtualnej będzie pełnił rejestr %ebp procesora, przetłumaczyć na:

 pushl 8(%ebp)

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ń ===

==== Operacje arytmetyczne i relacyjne ====

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 

Tłumaczeniem

 x/(y-5)

będzie więc:

          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.

==== Operacje logiczne ====

Wyrażenia logiczne można liczyć tak jak arytmetyczne. Ponieważ często występują w instrukcjach warunkowych lub w pętlach, gdzie kierują przepływem sterowania, możliwa jest też inna realizacja, w której obliczenie wyrażenia zawsze kończy się skokiem w jeden z dwóch punktów w programie w zależności od tego, czy warunek był prawdziwy czy nie.

Jeśli założymy skrócone obliczanie wyrażeń (przerywamy, gdy znamy wynik), może w nich być wiele instrukcji skoku wykonujących się gdy wyrażenie jest prawdziwe lub nie. Nazwiemy je skokami dla prawdy i dla fałszu.

W tłumaczeniu instrukcji:

 '''if''' E1 '''and''' E2 '''then''' I1 '''else''' I2

skoki dla prawdy z E1 powinny prowadzić do E2 a z E2 do I1. Skoki dla fałszu z E1 oraz E2 kierujemy do I2.

W tłumaczeniu instrukcji:

 '''if''' E1 '''or''' E2 '''then''' I1 '''else''' I2

skoki dla prawdy z E1 oraz E2 kierujemy do I1, skoki dla fałszu z E1 do E2 a z E2 do I2.

W tłumaczeniu:

 '''if''' '''not''' E '''then''' I1 '''else''' I2

z E dla fałszu skaczemy do I1 a dla prawdy do I2.

Np. tłumaczeniem:

 '''if''' (a '''or''' b) '''and''' '''not''' c '''then''' I1 '''else''' I2

będzie:

         adres_a LOAD
         L1 IFFALSE
         L2 GOTO
 L1:     adres_b LOAD
         L4 IFFALSE
         L2 GOTO
 L2:     adres_c LOAD
         L3 IFFALSE
         L4 GOTO
 L3:     [I1]            ; tu znajdzie się tłumaczenie I1
         L5 GOTO
 L4:     [I2]            ; tu znajdzie się tłumaczenie I2
 L5:

Jakość tego kodu można poprawić, zmieniając niektóre skoki warunkowe z IFFALSE na IFTRUE i usuwając instrukcje skoku, które prowadzą do następnej instrukcji. Po dokonaniu tych uproszczeń otrzymamy:
 
         adres_a LOAD
         L2 IFTRUE
         adres_b LOAD
         L4 IFFALSE
 L2:     adres_c LOAD
         L4 IFTRUE
         [I1]            ; tu znajdzie się tłumaczenie I1
         L5 GOTO
 L4:     [I2]            ; tu znajdzie się tłumaczenie I2
 L5:

=== 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 "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

którą tłumaczymy na:

 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: