Compiler selbstgeschneidert

Teil 4: Erzeugung von Stack-Maschinen-Code

Helmut Richter

Diese als Compiler-Praxis angekündigte Serie befaßt sich jetzt zum ersten Mal mit der Erzeugung von Maschinen code, allerdings noch nicht bis zur letzten Konsequenz. Im ersten Schritt erzeugt der Compiler einen Zwischencode, der nicht von einer real existierenden CPU ausgeführt werden kann. Die Wege von Z80-CP/M-Usern und anderen Compilerbauern brauchen sich noch nicht zu trennen. Der Zwischencode ist für einen nur scheinbar vorhandenen Prozessor gedacht, der in erster Linie mächtige Befehle zur stapelartigen Verwaltung von Daten kennt. Die Codeerzeugung für diese virtuelle Stack-Maschine geschieht praktisch im Parser, der dazu an wohlüberlegten Stellen mit Aufrufen der Prozedur GEN versehen wird.

Erstaunlich ist der Umstand, daß auch in dieser Folge lediglich die Eigenheiten von Turbo-Pascal in die Weiterentwicklung des DOIT-Compilers einfließen, Kenntnisse über die Zielmaschine aber, deren CPU und Befehlssatz, nicht nötig sind. Vom Betriebssystem werden nur die Funktionen 'Lese Zeichen von Tastatur' (read console) sowie 'Schreibe Zeichen auf Bildschirm' (write console) benutzt.

Zunächst aber benötigt man eine erste grobe Idee, wie überhaupt Maschinenprogramm und Daten für einen störungsfreien Programmablauf im Hauptspeicher abzulegen sind.

Wie so oft, gibt es auch hier zwei grundsätzliche Fälle, je nachdem, ob die zu übersetzende Sprache rekursive Unterprogramme zuläßt oder nicht. Kennt die Programmiersprache keine Rekursion, wie etwa BASIC oder Fortran, so besteht die Möglichkeit, die Daten statisch in das laufende Maschinenprogramm einzuflechten, am einfachsten da, wo sie im Programm zum ersten Mal erwähnt werden. Vor jedem Datenblock muß dann natürlich ein Jump jinter den Daten stehen, damit die CPU ihren nächsten Befehl findet.

Ist jedoch Rekursion zugelassen, so müssen bei jedem Unterprogrammaufruf neue lokale Daten dynamisch angelegt werden, sofern das Unterprogramm solche hat. Die lokalen Variablen der höheren Rekursionsstufe dürfen weder überschrieben noch darf auf sie zugegriffen werden.

In diesem Fall bietet es sich an, nicht nur die Rücksprungadresse, sondern auch die Daten auf dem CPU-Stack abzulegen. Bei jedem Unterprogrammaufruf reserviert man sich den benötigten Speicherplatz durch eine Dekrementierung des Stackpointers auf dem Stack. Der DOIT-Compiler arbeitet nach diesem Prinzip, ähnlich wie auch Turbo-Pascal oder Modula-2. Diese Arte der Datenverwaltung prägt den erzeugten Code so stark, daß sich fast alle Operationen auf den Stack beziehen und ein hypothetischer Prozessor für diesen Code Stack-Maschine genannt wird.

[DOIT-Speicherbelegung]
Das DOIT-Programm belegt einen festen Bereich innerhalb des Arbeitsspeichers, während die lokalen Daten bei Unterprogrammaufrufen nach unten wachsen. Wachsen sie in den Programmbereich, stürzt das Programm ab.

Was is'n Stack-Maschin?
Ihre Arbeitsweise ist denkbar einfach: Nehmen wir an, das Statement 'A:=B+1;' soll ausgeführt werden. Dann ist folgendes zu tun:
  1. Lade Variable B von ihrem Speicherplatz auf den Stack.
  2. Lade Konstante 1 auf den Stack.
  3. Addiere die beiden obersten Stack-Elemente, entferne sie vom Stack und schreibe das Resultat wieder auf den Stack.
  4. Sichere oberstes Stack-Element auf den Speicherplatz von A.

Eine Stack-Maschine muß also insgesamt folgendes leisten:

Operationen auf den Daten: Operationen auf dem Stack-Maschinen-Programm: 

+----+---------------+--------------------------------------+
! Nr ! Mnemonik      ! Bedeutung                            !
+----+---------------+--------------------------------------+
!  0 ! LoadIntConst  ! Lade direkte Integerkonstante auf    !
!    !               ! den Stack                            !
!  1 ! LoadCharConst ! wie 0 nur mit Character              !
!  2 ! Operation     ! arithmetische/logische Operation     !
!  3 ! LoadIntVar    ! Integervariable auf den Stack laden  !
!  4 ! LoadCharVar   ! wie 3 nur mit Character              !
!  5 ! SaveIntVar    ! Integervariable vom Stack auf ihren  !
!    !               ! Speicherplatz schreiben              !
!  6 ! SaveCharVar   ! wie 5 nur mit Character              !
!  7 ! Call_Proc     ! Unterprogrammaufruf                  !
!  8 ! DECR_SP       ! Stackpointer (SP) erniedrigen        !
!  9 ! Jump          ! Unbedingter Sprung (im Zwischencode) !
! 10 ! Jump_Cond     ! Bedingter Sprung (IF..THEN..)        !
! 11 ! Call_RTsystem ! Laufzeit-Systemaufruf                !
! 12 ! Return        ! Rückkehr vom Unterprogrammaufruf     !
! 13 ! Save_BP       ! Alten Basepointer auf Stck sichern   !
! 14 ! Init_SP_BP    ! Initialisierung der Stackzeiger      !
+----+---------------+--------------------------------------+
Diese 15 Befehle der Stackmaschine genügen, um alle DOIT-Statements ausführen zu können.
Nun reicht es gewiß nicht aus, benötigte Variablen beim Betreten eines Unterprogramms einfach auf den Stack zu schreiben, im Handumdrehen wäre die Übersicht und damit auch die Information verloren. Eine genaue Stack-Struktur muß her, die neben den Variablen auch Rücksprungadressen von Unterprogrammaufrufen, Operanden und Operationsergebnisse eindeutig verwaltet.

Dazu eine Überlegung. Zu Beginn eines DOIT-Maschinenprogramms muß das Programm zuerst den Stackpointer auf die höchste frei verfügbare Speicheradresse setzen. Dies it bei CP/M die Adresse des BDOS-1. Nun wird der Stackpointer so oft dekrementiert, wie das Hauptprogramm Datenbytes hat.

Da der Quelltext bei der Übersetzung nur einmal durchgelesen wird, ist es zweckmäßig, die Variablen in der Reihenfolhe ihrer Deklarationen auf den Stack zu legen. Der Stackpointer zeigt immer auf den nächsten freien Platz des Stacks.

[DOIT-Speicherbelegung]
Das Hauptprogramm und jeder Unterprogrammaufruf hat seinen eigenen Datenbereich auf dem CPU-Stack. Der Basepointer zeigt hier auf die aktiven, lokalen Daten des letzten Unterprogrammaufrufes.
Haben die Daten eine einheitliche Länge, beispielsweise zwei Byte, so kann man ihre Position im Stack einfach durch die Position ihrer Deklaration erkennen: 
VAR i : INT; (* 1. *)
    j : INT; (* 2. *)
    k : INT; (* 3. *)
Variable k, Nummer drei in der Deklarationsfolge, liegt bei einer Einheitslänge von zwei Byte damit auf BDOS-5 und BDOS-6.

Im Compiler ist die Position eines Datums durch die Variable DatenNr vertreten, für ihren richtigen Wert ist die Prozedur MakeData verantwortlich. Wird sie in der Symboltabelle vermerkt, so kann man bei jedem Auftreten einer Variablen sofort ihren Ablageplatz relativ zum Basiszeiger angeben.

div style="text-align:justify"> Den Basiszeiger auf den Datenbereich des aktivierten (Unter-)Programms nennt man im Compilerbau auch noch Basepointer.

Prozedursegment
Die bisherige Stack-Verwaltung ist noch relativ simpel, funktioniert jedoch nur bei Hauptprogrammen. Ungeklärt ist noch, wie man beom Wechsel von einem Unterprogramm zum anderen die zugehörigen lokalen Daten erreicht. Zudem läßt sich bei rekursiven Prozeduren nicht im vorhinein sage, wie viele Aufrufe stattfinden und wie viele lokale Datensätze zu verwalten sind. Eine dynamische Datenverwaltung muß her.

Dazu geht man völlig analog vor, merkt sich jedoch zusätzlich den Basepointer des voarangehenden Unterprogramms und die eigene Rücksprungadresse. Einen so organisierten Datenbereich nennt man Prozedursegment, activation record oder auch Aktivierungs-Record.

In der skizzierten Situation fällt auf, daß jedes Prozedursegment mit einem Zeiger auf den Beginn des nächst höheren Prozedursegments beginnt. Der Basepointer zeigt auf diese Speicherstelle. Diese Art der Verzeigerung von Prozedursegmenten wird als dynamischer Link (dynamic link) bezeichnet. Er spiegelt die Reihenfolge der tatsächlichen Unterprogrammaufrufe wider und liefert bei Beendigung des aktiven Unterprogramms den richtigen alten Basepointer.

Diese Konstruktion des Stacks hat jetzt nur noch eine Schwachstelle. Die Sprache DOIT erlaubt den Unterprogrammen auf die Daten des Hauptprogramms ohne besondere Ankündigung zuzugreifen. Man muß somit jederzeit das Prozedursegment des Hauptprogramms auffinden können. Wenn dies dann auch noch schnell geht — um so besser. Im Compiler gibt es daher einen zweiten Basepointer, der ständig auf die globalen Daten gerichtet bleibt.

Das Prozedursegment des Hauptprogramms weist eine Besonderheit auf. Es besitzt ebenfalls eine Rücksprungadresse. Der Grund dafür ist reine Bequemlichkeit. Sowohl Haupt- als auch Unterprogramm können so mit exakt denselben Analyse- und Codegenerierungsroutinen baerbeitet werden.

Dazu ist ein Super-Hauptprogramm nötig, das Stack- und Basiszeiger initialisiert, das Hauptprogramm aufruft und nach Ablauf des DOIT-Programms einen CP/M-Warmstart macht. Dann ist die Unterscheidung zwischen Haupt- und Unterprogramm nicht mehr nötig.

Codegenerierung
Der erste Schritt der Codegenerierung besteht darin, die DOIT-Statements in entsprechende Sequenzen von Stack-Maschinen-Befehlen zu übersetzen. Hierbei kommt dem Compiler der Vorteil von LL(1)-Grammatiken und des Parsings durch rekursiven Abstieg zu Hilfe. Ist ein Übersetzungssachverhalt beim Parsen vollständig erfaßt, so wird an Ort und Stelle die Erzeugung des Objektcodes durch Angabe der benötigten Stack-Maschinen-Operation veranlaßt. Die richtige Reihenfolge der erzeugten Befehle wird dabei durch die rekursive Struktur des Parsers sozusagen selbst einbehalten.

Am Beispiel 'i:=i+1' wird der Ablauf der Analyse und die Codegenerierung deutlich. Die Prozedur Statement (in PARS-003.INC) ruft gemäß der Ableitungsregel 'statement ::= identifier := expression' Expression auf. Weiter geht es nach den Regeln 'expression ::= term' und 'term ::= factor' mit den Prozeduren Term und Factor. Und Factor findet wegen 'factor ::= identifier' den Identifier i. Jetzz kann schon Code erzeugt werden:

GEN(3,0,...,'LoadIntVar...'); bzw. GEN(4,0,...,'LoadCharVar...');
je nach dem Typ von i.

Das dem Identifier folgende Plus-Zeichen bewirkt den Rücksprung zu Term und von dort zu Expression.

Die nächste Regel lautet 'expression ::= term + term', und der Parser steigt über Term und Factor zu, zweiten Mal ab und stößt diesmal in Factor auf eine Integer-Konstante. Der nächste Code wird generiert durch die Aufrufe:

GEN(0,0,IWERT,'LoadIntConst...');
bzw.
GEN(1,0,IWERT,'LoadChartConst...');

Das folgende Symbol ist ein Semikolon, und über Term geht es zurück nach Expression. Hier wird die Erzeugung des Codes veranlaßt, der die Addition ausführt:

GEN(2,0,2,'Addition...');

worauf in Statement der Code für die Sicherung des Ergebnisses auf den Speicherplatz von i erzeugt wird:

GEN(5,...,DatenAdresse,'SaveIntVar'...);

Es empfiehlt sich nach wie vor, die Compiler-Prozeduren genau nachzuvollziehen. Die exakten Abläufe können in allen Einzelheiten nur dem Programm-Listing entnommen werden.

In Stack-Maschinen-Befehlen sieht dies alles dann so aus: 
LoadIntVar   0 1 ;
LoadIntConst 0 1 ;
Operation    0 2 ;
SaveIntVar   0 1 ;
Im Compiler besteht jeder Stack-Maschinen-Befehl aus drei Zahlen x, y und z. Die erste ist die Nummer des Befehls, und die zweite gibt die Leveldifferenz beim Zugriff auf Variablen an. In einem Unterprogramm bedeutet y=1 den Zugriff auf Daten des Hauptprogramms und y=0 den Zugriff auf die eigenen lokalen Daten. Die dritte Angabe ist entweder eine direkte oder eine basepoint-relative Adresse oder ein Datum.

Der Stack-Maschinen-Code kann als compiler-interner Zwischencode aufgefaßt werden, der nach außen nicht in Erscheinung tritt. Der Compiler kann ihn aber auf eine Datei schreiben, am Bildschirm zeigen oder sogar ausdrucken, um die Codegenerierung transparent zu machen.

Anders liegen die Dinge zum Beispiel beim UCSD-Pascal-Compiler. Er erzeugt nur Zwischencode, den sogenannten p-Code, der ebenfalls für eine hypothetische Stack-Maschine gedacht ist. Erst zur Laufzeit wird er von einem für die CPU des Rechners geschriebenen Interpreter ausgeführt.

Der Code der Stack-Maschine spielt im DOIT-Compiler also nur die Rolle des Übergabeparameters für die Prozedur GEN. Speichert man ihn zusätzlich in einer Variablen (ZCODE), kann beispielsweise beim Befehl Nr. 3 eine kleine lokale Optimierung durchgeführt werden. War nämlich der vorangehende Befehl ein SaveIntVar auf dieselbe Variable, so befindet sie sich noch als letztes Datum auf dem Stack, und es reicht aus, den Stackpointer zu dekrementieren, anstatt einen umständlichen Ladeprozess auszuführeb.

Backpatching
Ein interessantes Problem für Compilerbauer ist die Erzeugung von Sprüngen im Zwischencode. Dabei muß zwischen Sprüngen nach vorne und Sprüngen nach hinten unterschieden werden. Vorwärtssprünge werden beim EXIT- und beim IF-THEN-Statement nötig, während Rückwärtssprünge nur im Code von DO..OD-Schleifen auftreten.

Kommt ein IF-Statement zur Übersetzung, so muß abhängig von der Auswertung der Bedingung ein Programmblock durchlaufen und ein anderer übersprungen werden. Zur Ausführung kommen darf ja nur einer der beiden Zweige. Leider sind in diesem Stadium der Übersetzung die Ansprungadressen noch nicht verfügbar. Man weiß ja nicht, wie viele DOIT-Statements Then-Zweig und Else-Zweig umfassen und wie viele Zwischencodebefehle zu ihrer Übersetzung benötigt werden.

[DOIT-Sprünge]
Obwohl DOIT kein GOTO kennt, gibt es Vorwärts- und Rückwärtssprünge im übersetzten Code. Ursache sind die bedingte Anweisung, der EXIT-Befehl und die DO..OD-Schleife.
Also merkt der Compiler sich die Adresse des Absprungbefehls in einer Variablen, beispielsweise L0 durch 
L0:=MakeLabel;
und trägt nachträglich beim Auffinden des Ansprungpunktes die momentane Adresse durch 
FixUp(L0);
an der Absprungstelle im übersetzten Code ein. MakeLabel liefert dabei die aktuelle Zwischencodeadresse. Dieses Verfahren, nachträglich Vorwärtssprünge einzutragen, heißt Backpatching.

Um nun eine zu starke Belastung des Laufwerks durch ständiges Hin- und Hersuchen zu vermeiden, speichert der Compiler alle Patch-Informationen in einem Array namens PatchFeld, Typ PatchInfo, und arbeitet dieses Feld am Ende des Parsing-Prozesses auf einmal ab. MakeLabel liefert diesmal keine Adresse, sondern einen Index für ein freies PatchFeld-Record.

Zweimal EXIT
Die EXIT-Sprünge stellen eine weitere Komplikation dar. Sie können sowohl in als auch außerhalb von Schleifen auftreten. Stehen sie in einem DO..OD-Statement, so muß ein Sprung hinter das OD generiert werden, um die Schleife zu verlassen. Kommen sie außerhalb vor, wirken sie wie ein Return, das heißt, es muß ein Sprung auf das (Unter-)Programmende generiert werden. Zur Lösung dieses Problems wendet der Compiler ein besonderes Verfahren an.

Die Verwaltung der EXITs erfolgt mit Hilfe einer linearen Liste, die exakt so organisiert ist wie die Symboltabelle. Trifft der Parser auf ein DO-Symbol, so legt er mit Hilfe von InitExitListe eine lokale Tabelle für eventuelle EXIT-Sprünge an, genau so, wie Block eine neue Symboltabelle für die lokalen Variablen erzeugt.

Alle vorgefundenen EXITs werden nun in diese Liste eingetragen und am Schleifenende mit FixUpExitListe in PatchFeld überführt. Die lokale Liste wird dann verworfen. Ist am (Unter-)Programmende der Zeiger ExitSprung ungleich nil so hat ein EXIT die Wirkung eines Returns. Wider trägt FixUpExitListe die Patch-Informationen in PatchFeld ein.

Rückwärtssprünge treten nur beim DO..OD-Statement auf und stellen den einfacheren Fall dar; zur Compile-Zeit steht die Ansprungadresse ja schon zur Verfügung. Im Zwischencode geschieht das Backpatching folgendermaßen:

Zu Beginn der Schleife reserviert man sich einen Index auf PatchFeld mittels MakeLanbel, speichert ihn in der lokalen Variablen L0 und bearbeitet die Schleifen-Statements. Nach Vorfinden des OD muß ein Sprung auf den Schleifenanfang generiert werden. PatchFeld[L0].Z_Adresse enthält nicht wie beim Vorwärtssprung die Patchadresse sondern den Patchwert, das Sprungziel und muß auf Z_Patch umkopiert werden. Die Patchadresse ist nun die aktuelle ZCode_Adresse. 

MODULE Test;
(* Allgemeines Testmodul für DOIT *)
VAR x       : INT;
    i       : INT;

PROC ReadInt;
BEGIN
  WRITE '?'; READ x;
END (* ReadInt *);

BEGIN (* Hauptprogramm *)
  DO ReadInt;
     IF x < 0 THEN EXIT; FI;
     x := 6 / x;
     WRITE x;
  OD;
END.
Diese DOIT-Beispielprogramm enthält alle wichtigen Funktionen und demonstriert die Codegenerierung. 
Adresse OpCode               Level  Adresse/Wert
------------------------------------------------
    0 : Init_SP_BP            0     57349 ; Stack/Basepointer initialisieren
    1 : Call_Proc             0         3 ; Aufruf des Hauptprogramms
    2 : Jump                  0         0 ; Warmstart
    3 : Save_BP               0         0 ; Basepointer sichern, neuen laden
    4 : Decr_SP               0         2 ; Platz fuer Daten schaffen
    5 : Decr_SP               0         2 ; Platz fuer Daten schaffen
    6 : Jump                  0        13 ; Mgl. Unterprogramme ueberspringen
    7 : Save_BP               0         0 ; Basepointer sichern, neuen laden
    8 : LoadCharConstant      0        63 ; direkte Characterkonstante
    9 : Call_RTsystem         0        13 ; Character schreiben
   10 : Call_RTsystem         0         4 ; Integer einlesen
   11 : SaveIntVar            1         1 ; und sichern
   12 : Return                1         0 ; Return vom Unterprogrammaufruf
   13 : Call_Proc             1     26653 ; Unterprogramm aufrufen
   14 : LoadIntVar            0         1 ; Lade Integervariable X
   15 : LoadInTConst          0         0 ; direkte Integerkonstante
   16 : Operation             0        46 ; Lleiner testen
   17 : Jump                  0        19 ; Sprung auf ELSE-Teil
   18 : Jump_Cond             0        26 ; EXIT-Sprung
   19 : LoadInTConst          0         6 ; direkte Integerkonstante
   20 : LoadIntVar            0         1 ; Lade Integervariable X
   21 : Operation             0        28 ; Division durchfuehren
   22 : SaveIntVar            0         1 ; Save Integer X
   23 : LoadIntVar            0         1 ; Lade Integervariable X
   24 : Call_RTsystem         0        10 ; Integer schreiben
   25 : Jump                  0        13 ; DO..OD: Ruecksprung zum DO
   26 : Return                0         0 ; Return vom Hauptprogrammaufruf
Das Beispielprogramm in Stack-Maschinen-Befehlen.

Unterstützung
Sämtliche Arithmetik-, Logik- und Systemoperationen müsen bei der Simulation der Stack-Maschine vom 'Stack-Maschinen-Prozessor' geliefert werden. Da normale CPUs solche komplexen Operationen nicht als Maschinenbefehle zur Verfügung stellen, müssen sie durch Unterprogramme relisiert werden.

Hier gibt es zwei Möglichkeiten, die notwendigen Unterprogramme mit dem übersetzten Programm zu verbinden:
1. Wie in Turbo-Pascal eird das komplette Laufzeitsystem als Block in den Objektcode angekoppelt.
2. Nur die im übersetzten Programm tatsächlich benötigten Funktionen werden an das Objektmodul angebunden (gelinkt). Dies geschieht zum Beispiel bei Modula-2 und MT+Pascal.

Obwohl der zweite Weg der perfektere ist und beide für die Sprache DOIT recht einfach realisiert werden können, verwendet DOIT die Methode des kopierten Laufzeitblocks. Der Grund ist offensichtlich:

Dieses Konzept ist einfacher zu implementieren. Wird Objektcode bei einer Übersetzung gewünscht, kopiert der Compiler einfach das Laufzeitsystem (Name: DCRTS.LIB) zu der .COM-Datei dazu.

Die Adressen der verschiedenen Unterprogramme aus der Lib sind im Compiler als Konstanten vereinbart und werden bei der Kompilation einfach in den Objektcode eingesetzt. Zudem beginnt das Laufzeitsystem wie bei CP/M auch mit einer Vektorenleiste.

Der nächste und letzte Teil dieser Serie wird sich dem endgültigen Einstieg in die Praxis, nämlich dem Laufzeitsystem und der Erzeugung von Assembler- und Maschinencode widmen.

[Listing]
In diesem Stadium ist der DOIT-Compiler bereits in der Lage, Code für eine virtuelle Stack-Maschine zu erzeugen.
[3. Teil] [Inhalt] [5. Teil]

Edited by Werner Cirsovius
April 2011
© Heise Verlag