Projekt kompilatora - generowanie kodu

Generację kodu można uznać za ostatnią fazę kompilacji. Dzięki generowaniu kodu pocztowego proces optymalizacji można zastosować w kodzie, ale można to postrzegać jako część samej fazy generowania kodu. Kod wygenerowany przez kompilator jest kodem obiektowym jakiegoś języka programowania niższego poziomu, na przykład asemblera. Widzieliśmy, że kod źródłowy napisany w języku wyższego poziomu jest przekształcany w język niższego poziomu, co daje w wyniku kod obiektowy niższego poziomu, który powinien mieć następujące minimalne właściwości:

Powinien zawierać dokładne znaczenie kodu źródłowego.
Powinien być wydajny pod względem wykorzystania procesora i zarządzania pamięcią.

Zobaczymy teraz, jak kod pośredni jest przekształcany w docelowy kod obiektowy (w tym przypadku kod asemblera).

Skierowany graf acykliczny

Directed Acyclic Graph (DAG) to narzędzie, które przedstawia strukturę podstawowych bloków, pomaga zobaczyć przepływ wartości przepływających między podstawowymi blokami, a także oferuje optymalizację. DAG zapewnia łatwą transformację podstawowych bloków. DAG można zrozumieć tutaj:

Węzły liści reprezentują identyfikatory, nazwy lub stałe.
Węzły wewnętrzne reprezentują operatorów.
Węzły wewnętrzne reprezentują również wyniki wyrażeń lub identyfikatory / nazwy, w których mają być przechowywane lub przypisywane wartości.

Example:

t₀ = a + b
t₁ = t₀ + c
d = t₀ + t₁

[t ₀ = a + b]	[t ₁ = t ₀ + c]	[d = t ₀ + t ₁ ]

Optymalizacja wizjera

Ta technika optymalizacji działa lokalnie na kodzie źródłowym, aby przekształcić go w zoptymalizowany kod. Mówiąc lokalnie, mamy na myśli niewielką część dostępnego bloku kodu. Metody te można stosować zarówno do kodów pośrednich, jak i docelowych. Zestaw instrukcji jest analizowany i sprawdzany pod kątem następującej możliwej optymalizacji:

Eliminacja zbędnych instrukcji

Na poziomie kodu źródłowego użytkownik może wykonać następujące czynności:

int add_ten(int x)
   {
   int y, z;
   y = 10;
   z = x + y;
   return z;
   }

int add_ten(int x)
   {
   int y;
   y = 10;
   y = x + y;
   return y;
   }

int add_ten(int x)
   {
   int y = 10;
   return x + y;
   }

int add_ten(int x)
   {
   return x + 10;
   }

Na poziomie kompilacji kompilator wyszukuje instrukcje, które są z natury zbędne. Wielokrotne ładowanie i przechowywanie instrukcji może mieć to samo znaczenie, nawet jeśli niektóre z nich zostaną usunięte. Na przykład:

MOV x, R0
MOV R0, R1

Możemy usunąć pierwszą instrukcję i przepisać zdanie jako:

MOV x, R1

Nieosiągalny kod

Kod nieosiągalny to część kodu programu, do której nigdy nie uzyskuje się dostępu z powodu konstrukcji programistycznych. Programiści mogli przypadkowo napisać fragment kodu, do którego nigdy nie można dotrzeć.

Example:

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is %d”, x);
}

W tym segmencie kodu printf Instrukcja nigdy nie zostanie wykonana, ponieważ element sterujący programu wraca, zanim będzie mógł wykonać printf może być usunięty.

Przepływ optymalizacji sterowania

Istnieją przypadki w kodzie, w których sterowanie programem przeskakuje tam iz powrotem bez wykonywania żadnego znaczącego zadania. Te skoki można usunąć. Rozważmy następujący fragment kodu:

...		
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1

W tym kodzie etykieta L1 może zostać usunięta, gdy przekazuje sterowanie do L2. Więc zamiast przeskakiwać do L1, a następnie do L2, sterowanie może bezpośrednio dotrzeć do L2, jak pokazano poniżej:

...		
MOV R1, R2
GOTO L2
...
L2 :   INC R1

Uproszczenie wyrażeń algebraicznych

Są sytuacje, w których wyrażenia algebraiczne można uprościć. Na przykład wyrażeniea = a + 0 można zastąpić a i wyrażenie a = a + 1 można po prostu zastąpić przez INC a.

Redukcja siły

Istnieją operacje, które pochłaniają więcej czasu i miejsca. Ich „siłę” można zmniejszyć, zastępując je innymi operacjami, które zajmują mniej czasu i miejsca, ale dają ten sam efekt.

Na przykład, x * 2 można zastąpić x << 1, która obejmuje tylko jedną zmianę w lewo. Chociaż wyjście a * a i a ² jest takie samo, implementacja a ² jest znacznie wydajniejsza.

Dostęp do instrukcji maszyny

Maszyna docelowa może wdrażać bardziej wyrafinowane instrukcje, które mogą znacznie wydajniej wykonywać określone operacje. Jeśli kod docelowy może bezpośrednio uwzględnić te instrukcje, nie tylko poprawi to jakość kodu, ale także zapewni bardziej wydajne wyniki.

Generator kodów

Od generatora kodu oczekuje się zrozumienia środowiska wykonawczego maszyny docelowej i zestawu instrukcji. Generator kodu powinien wziąć pod uwagę następujące rzeczy, aby wygenerować kod:

Target language: Generator kodu musi być świadomy charakteru języka docelowego, dla którego kod ma zostać przekształcony. Ten język może ułatwić niektóre instrukcje specyficzne dla maszyny, aby pomóc kompilatorowi wygenerować kod w wygodniejszy sposób. Maszyna docelowa może mieć architekturę procesora CISC lub RISC.
IR Type: Reprezentacja pośrednia ma różne formy. Może mieć strukturę abstrakcyjnego drzewa składniowego (AST), odwrotną notację polską lub kod 3-adresowy.
Selection of instruction: Generator kodu przyjmuje reprezentację pośrednią jako dane wejściowe i konwertuje (odwzorowuje) ją na zestaw instrukcji maszyny docelowej. Jedna reprezentacja może mieć wiele sposobów (instrukcji), aby ją przekonwertować, więc odpowiedzialność za mądry wybór odpowiednich instrukcji spoczywa na generatorze kodu.
Register allocation: Program ma kilka wartości, które mają być zachowane podczas wykonywania. Architektura maszyny docelowej może nie pozwalać na przechowywanie wszystkich wartości w pamięci procesora lub rejestrach. Generator kodu decyduje, jakie wartości zachować w rejestrach. Decyduje również o rejestrach, które mają być używane do przechowywania tych wartości.
Ordering of instructions: W końcu generator kodu decyduje o kolejności, w jakiej instrukcja zostanie wykonana. Tworzy harmonogramy instrukcji ich wykonania.

Deskryptory

Generator kodu musi śledzić zarówno rejestry (dostępność), jak i adresy (lokalizację wartości) podczas generowania kodu. Dla obu z nich używane są następujące dwa deskryptory:

Register descriptor: Deskryptor rejestru służy do informowania generatora kodu o dostępności rejestrów. Deskryptor rejestru śledzi wartości przechowywane w każdym rejestrze. Zawsze, gdy podczas generowania kodu wymagany jest nowy rejestr, należy sprawdzić dostępność rejestru przy użyciu tego deskryptora.
Address descriptor: Wartości nazw (identyfikatorów) używanych w programie mogą być przechowywane w różnych lokalizacjach podczas wykonywania. Deskryptory adresów służą do śledzenia lokalizacji pamięci, w których przechowywane są wartości identyfikatorów. Te lokalizacje mogą obejmować rejestry procesora, sterty, stosy, pamięć lub kombinację wspomnianych lokalizacji.

Generator kodu aktualizuje oba deskryptory w czasie rzeczywistym. Dla instrukcji load, LD R1, x, generator kodu:

aktualizuje deskryptor rejestru R1, który ma wartość x i
aktualizuje deskryptor adresu (x), aby pokazać, że jedno wystąpienie x znajduje się w R1.

Generowanie kodu

Bloki podstawowe składają się z sekwencji rozkazów trójadresowych. Generator kodu przyjmuje tę sekwencję instrukcji jako dane wejściowe.

Note: Jeśli wartość nazwy zostanie znaleziona w więcej niż jednym miejscu (rejestr, pamięć podręczna lub pamięć), wartość rejestru będzie miała pierwszeństwo przed pamięcią podręczną i pamięcią główną. Podobnie wartość pamięci podręcznej będzie preferowana w stosunku do pamięci głównej. Pamięć główna nie jest preferowana.

getReg: Generator kodu używa funkcji getReg do określenia statusu dostępnych rejestrów i lokalizacji wartości nazw. getReg działa w następujący sposób:

Jeśli zmienna Y jest już w rejestrze R, używa tego rejestru.
W przeciwnym razie, jeśli jakiś rejestr R jest dostępny, używa tego rejestru.
W przeciwnym razie, jeśli obie powyższe opcje nie są możliwe, wybiera rejestr, który wymaga minimalnej liczby instrukcji ładowania i przechowywania.

Dla instrukcji x = y OP z generator kodu może wykonać następujące czynności. Załóżmy, że L to lokalizacja (najlepiej rejestr), w której ma zostać zapisane wyjście y OP z:

Wywołaj funkcję getReg, aby zdecydować o lokalizacji L.
Określ bieżącą lokalizację (rejestr lub pamięć) y konsultując się z deskryptorem adresu y. Jeśliy nie jest obecnie zarejestrowany L, a następnie wygeneruj następującą instrukcję, aby skopiować wartość y do L:

MOV y ', L

gdzie y’ reprezentuje skopiowaną wartość y.
Określ bieżącą lokalizację z używając tej samej metody, co w kroku 2 dla y i wygeneruj następującą instrukcję:

OP z ', L.

gdzie z’ reprezentuje skopiowaną wartość z.
Teraz L zawiera wartość y OP z, do której ma zostać przypisana x. Tak więc, jeśli L jest rejestrem, zaktualizuj jego deskryptor, aby wskazać, że zawiera on wartośćx. Zaktualizuj deskryptorx aby wskazać, że jest przechowywany w miejscu L.
Jeśli yiz nie mają już zastosowania, można je zwrócić systemowi.

Inne konstrukcje kodu, takie jak pętle i instrukcje warunkowe, są przekształcane w język asemblera w sposób generalny.