Compiler selbstgeschneidert
Teil 5: Erzeugung von Maschinencode
Helmut Richter
Nach dem Bau des Scanners, des Parsers und der Generierung von Stack-Maschinen-Befehlen sind alle Vorbereitungen für die Erzeugung von CPU-abhängigen Maschineninstruktionen getroffen.
Die Entscheidung fiel aus naheliegenden Gründen auf Z80-Code.
Die Code-Generierung des DOIT-Compilers ist aber in keiner Weise auf einen bestimmten CPU-Typ festgelegt.
Genausogut läßt er sich als Cross-Compiler auslegen, der als Turbo-Pascal-Programm unter CP/M-80 oder MS-DOS läuft und 6502-Code erzeugt.
Prinzipiell geht es lediglich darum, mit dem Befehlssatz einer real existierenden CPU die Operationen der virtuellen Stack-Maschine zu simulieren.
Praktisch alle für die Coderzeugung nötigen Ergänzungen betreffen die Prozedur GEN, von der hier eine komplette Version gezeigt wird.
Sie ersetzt das provisorische Include-File DC-002.INC aus der letzten Folge.
In DC-003.INC sind noch die Prozeduren PatchASMFile und PatchCOMFile nachzutragen.
Arithmetische und logische Funktionen, Ein- und Ausgaberoutinen und die Konvertierung von Zahlen müssen von einem Laufzeitsystem geleistet werden, das hier in beispielhafter Form als Assemblerlisting vorgestellt wird.
Nach diesen Änderungen ist der Compiler in der Lage, simultan Zwischen-, Assembler- und Maschinencode zu erzeugen, vorausgesetzt, die logischen Variablen ZWC_Gen, ASM_Gen, COM_Gen stehen auf TRUE.
Ein echter Mehr-Pass-Compiler würde Assembler- und Maschinencode erst in einem zweiten Durchgang (Pass) aus dem Stack-Maschinen-Programm erzeugen.
Wegen der unterschiedlichen Startadressen der DOIT-Unterprogramme in den drei Codearten bedeutet das allerdings etlichen Mehraufwand.
Die unterschiedlichen Startadressen sind auch für eine Ungereimtheit bei der Generierung des Zwischencodes verantwortlich.
Die alte Version von GEN erzeugt bei 'Call_Proc' eine viel zu hohe Aufrufadresse.
Im
Beispielprogramm von Teil 4 (Befehl 13) war dies 26653, obwohl das Unterprogramm auf Zwischencodeadresse 7 stand.
Diese hohe Zahl ist keine Startadresse, sondern die Adresse des Symboltabellenelementes der gerufenen Prozedur.
Sie erlaubt dem neuen GEN den Zugriff auf die verschiedenen Startadressen der Prozedur im Zwischen-, Assembler- und Maschinencode, ist also wichtig für Erzeugung der drei Codearten.
In den Prozeduren aus Teil 4 sind noch zwei Korrekturen nötig.
Um zwischen dem Aufruf des Hauptprogramms und dem eines Unterprogramms zu unterscheiden, muß in der Prozedur
Parse (S. 105) der Aufruf
GEN(7,0,ZCode_Adresse+2,...
zu
GEN(7,1,ZCode_Adresse+2,...
geändert werden.
In der Prozedur
NewObj (S. 103) muß beim Anlegen einer neuen Character-Variablen (CharVar) MakeData statt
MakeData(DatenAdresse,1)
durch
MakeData(DatenAdresse,2)
aufgerufen werden.
Andernfalls gibt es ein Durcheinander im Prozedursegment.
In der Beschränkung...
Ein Assembler-Freak wird den vom Compiler erzeugten Code nicht als sonderlich effektiv bezeichnen.
Er ist zugegebenermaßen mager, denn er verwendet nur 34 vreschiedene Befehle des Z80.
Zusammen mit den vom Laufzeitsystem zur Verfügung gestellten Funktionen reicht er aber aus, um die 15 Stack-Maschinen-Befehle zu simulieren.
Und mehr ist mit dieser Serie auch gar nicht beabsichtigt.
Ein Compiler, der für eine CPU maßgeschneiderten Code erzeugt, also alle Befehle und Register optimal ausnutzt, läßt sich nicht in wenigen Monaten programmieren und eignet sich schon gar nicht zur Demonstration von Prinzipien.
Auch die Register der Z80 werden nicht so universell benutzt, wie der Befehlssatz es zulassen würde.
Eine wichtige Spezialaufgabe übernehmen die Indexregister.
Das IX-Register ist der Basepointer des gerade aktiven Prozedursegments, während das IY-Register ausschließlich für die Adressierung der globalen Daten zuständig ist.
Doch nun zur Codegenerierung.
Vom Zwischen- und Assemblercode gelangt man durch einen einfachen Trick, nämlich durch 'Makroexpansion'.
Die Stack-Maschinen-Befehle werden als Assemblermakros angesehen und einfach gegen entsprechende Assemblerbefehls-Sequenzen ausgetauscht.
+----------+--------+----------------------------+
! Register ! Länge ! Zweck/Einsatz !
+----------+--------+----------------------------+
! HL ! 16 Bit ! 16 Bit-Integerarithmetik !
! ! ! (Addition/Subtraktion) !
! ! ! RETURN-Sprung (JP (HL)) !
! DE ! 16 Bit ! 16 Bit-Integerarithmetik !
! ! ! (Addition/Subtraktion) !
! BC ! 16 Bit ! Arithmetik/Zähler !
! IY ! 16 Bit ! Basepointer für Aktivie- !
! ! ! rungsrecord globaler Daten !
! IX ! 16 Bit ! Basepointer für Aktivie- !
! ! ! rungsrecord lokaler Daten !
! SP ! 16 Bit ! aktueller Stackpointer !
! A ! 8 Bit ! logische Vergleiche und !
! ! ! 8-Bit Arithmetik !
+----------+--------+----------------------------+
|
|
Im kompilierten Code hat jedes Z80-Register eine festgelegte Aufgabe.
|
So wird aus GEN(11,0,4), das ist 'CALL_RTsystem 0 4', der Aufruf
CALL 259D (=100H+3)
aus GEN(5,0,1), das ist 'SaveIntVar 0 1', die Sequenz
POP HL
LD (IX-dd),H
LD (IX-(dd+1)),L
Die beiden Zwischencodebefehle zusammen lesen eine Integer durch Aufruf der Lese-Integer-Routine des Laufzeitsystems ein und legen sie auf den Speicherplatz der ersten Variablen im Prozedursegment ab.
Dabei gibt dd den Offset der Variablen relativ zum Basepointer an, muß also in diesem Fall zwei sein, weil alle Variablen zwei Bytes lang sind.
Die Anweisung 'LoadIntVar 1 1' wurd nach gleicher Methode zu
LD H,(IY-dd) ; (dd = 1x2)
LD L,(IX-(dd+1))
PUSH HL
und scon ist die globale Variable Nummer 1 auf dem Stack.
Diese Ergänzung geschieht im großen CASE-Statement der neuen GEN-Prozedur mit der Stack-Maschinen-Befehls-Nummer x als Schaltervariablen.
Jetzt ist ein kleines Manko sichtbar, das man sich durch Verwendung der IX- und IY-Register als Basepointer einhandelt.
Da sie nur 128 Byte nach unten greifen können, lassen sich nur 64 Integers adressieren.
DOIT erlaubt deshalb nur eine beschränkte Zahl von Variablen-Deklarationen pro Prozedur.
Ändern läßt sich das durch eine aufwendigere Assemblersequenz für die entsprechenden Stack-Maschinen-Befehle.
Eine weitere Beschwernis bringen die verschiedenen Längen der drei Codearten mit sich.
Es ist deshlab notwendig, drei verschiedene laufende Adressen bereitzuhalten:
ZCode_Adresse für den Zwischencode, ASMCode_Adresse für das Assemblerprogramm und MCode_Adresse für den Objektcode.
Zudem dürfen alle drei Codesorten verschiedene Anfangsadressen haben, die in ZCode_Offset, ASMCode_Offset und MCode_Offset festgelegt werden müssen.
...liegt DOITs Größe
Aus Assemblercode Maschineninstruktionen zu machen, ist jetzt nicht mehr schwer.
Der Compiler erledigt dies in einem Aufwasch, indem er WriteCode die gewünschten Maschinenbefehle als hexadezimale Zahlen und deren Länge als Integer übergibt.
Der Aufruf
WriteCode('E1',0,1);
schreibt den Maschinenbefehl 'E1' (POP HL) ohne weitere Daten oder Adressen (daher die Null) mit einem Byte Länge auf ProgrammName.COM und je nach Belegung von ASM_Gen den Assemblertext auf ProgrammName.ASM.
Am Ende des einen Analyselaufs über das des einen Analyselaufs über das Quellprogramm ist so der Objektcode auf die COM-Datei geschrieben.
Das Backpatching von ASM- und COM-Datei erledigen die Prozeduren PatchASMFile und PatchCOMFile.
Leider ist das Eintragen der richtigen Sprungadresse im Objektcode nicht so einfach wie bei Zwischen- und Assemblercode.
Hier liegt ja keine Record-Struktur vor.
PatchCOMFile berechnet sie Patch-Adresse durch
j:=M_Adresse-TPA_Angfang
und dann den zugehörigen Dateisektor mit
Sektor:=j DIV 128;
Die sektorrelative Adresse ergibt sich aus
pos:=j MOD 128;
Nun kann man auf den Sektor positionieren:
SEEK(CMD,Sektor)
und ihn lesen:
BLOCKREAD(CMD,Sektorpuffer,1)
Der Patch wird durch
Sektorpuffer [pos] := BYTE
(LO(M_Patch));
Sektorpuffer [pos+1] := BYTE
(HI(M_Patch));
eingetragen und anschließend zurückgeschrieben.
Der Aufruf von PatchASMFile ind PatchCOMFile ist in Back-Patch schon vorgesehen, und wird bei entsprechender Belegung von ASM_Gen und COM_Gen automatisch durchgeführt, genau wie bei ZWC_Gen.
Wie der Zwischencode läßt sich auch der Assemblercode nicht einfach 'austypen', da er eine Record-Datei ist.
Wer sich den Assemblercode ansehen möchte, kann die Prozedur ZeigeZwischenCode kopieren und zu ZeigeASMCode umbauen.
Stackoperationen: (5)
PUSH HL
POP HL
POP DE
PUSH IX
POP IX
Ladeoperationen: (15)
LD SP,(0006) (Hier liegt die BDOS-Adresse)
LD IX,(0006)
LD IY,(0006)
LD HL,nnnn
LD H,'$'
LD L,nn
LD A,H
LD H,(IX+dd)
LD L,(IX+dd)
LD (IX+dd),H
LD (IX+dd),L
LD H,(IY+dd)
LD L,(IY+dd)
LD (IY+dd),H
LD (IY+dd),L
|
Erniedrigung um 1: (4)
DEC SP
DEC IX
DEC IY
DEC A
Absolute und relative Sprünge: (5)
JP nnnn
JP Z,nnnn
JR nnnn
JR Z,nnnn
JR NZ,nnnn
Unterprogrammaufruf und Rücksprung zum
Hauptprogramm: (2)
CALL nnnn
RET
Logische Operationen und Tests: (3)
XOR A entspricht LD A,0
OR A
BIT 0,L
|
Der Code-Generator ist bewußt einfach gehalten und benutzt nur diese 34 Z80-Befehle.
|
Optimierung
Der große Nachteil dieses Ein-Pass-Verfahrens sind die mangelhaften Optimierungsmöglichkeiten des generierten Codes.
So können invariante Ausdrücke in Schleifen, die bei jedem Durchlauf auf dieselben Operationen führen, wie
DO
i:= 1;
... i bleibt unverändert...
OD;
nicht erkannt und vor die Schleife gezogen werden.
Gemeinsame Teilausdrücke wie
i:= j + 6;
... j bleibt unverändert...
i:= j + 6;
Befehlsfolgen wie
SaveIntVar 0 n
LoadIntVar 0 n
kann der Compiler jedoch zu
Decr_SP 0 2
PUSH L
POP HL
auf.
Diese Sequenz kann zwar wegen der Adreßrechnung nicht einfach entfallen, könnte aber durch zwei NOPs ersetzt werden.
Laufzeitsystem
Wie schon im letzten Teil beschrieben, enthält der DOIT-Objektcode ein kleines Laufzeitsystem.
Es ist in Z80-Assembler geschrieben und beginnt mit einer Vektorenleiste, genau wie das CP/M-BDOS auch.
Das Ende ist mit dem Label ENDLIB markiert.
Das Laufzeitsystem umfaßt in der gezeigten Form 602 ($25A) Bytes.
Dieser oder ein größerer Wert muß im Compiler bei der Deklaration des Puffer-Arrays PF (Prozedur InitParser) gegen die dort zu knapp bemessenen 256 Bytes ausgetauscht werden.
Ebenfalls muß die Konstante MCode_Offset angepaßt werden (alt: $200, neu $35B).
|
|
|
Zum Abtippen:
Der Hexdump des provisorischen Laufzeitsystems mit Prüfsummen.
|
Die Unterprogramm des RTS sind in Funktionsblöcken angeordnet.
Auf die Systemfunktionen wie ReadInt und WriteChar folgen die arithmetischen Operationen, beispielsweise ADDOP und SUBOP und schließlich die logischen Operationen wie EQLOP, GTROP.
Am Schluß liegen die Texte und Ziffernpuffer.
Aus Platzgründen ist das System nicht vollständig.
Nicht alle Funktionen sind implementiert, jedoch ohn System-Crash aufrufbar.
Sie liefern dann den Wert Null oder ein anderes konstantes Ergebnis zurück.
Die ReadInt-Routine ist bewußt einfach programmiert, sie verlangt immer die Eingabe von fünf Ziffern.
Das Modul kann Integers und Characters einlesen und ausschreiben.
Bei der Arithmetik sind Addition, Subtraktion und eine Multiplikation für positive Zahlen vorhanden, an logischen Operationen stehen OD, EQuaL und NotEQual zur Verfügung.
Die restlichen Funktionen lassen sich leicht ergänzen.
Als Einstieg bieten sich die fehlenden logischen Funktionen an, die analog zu den vorhandenen programmiert werden können.
Bei der Erweiterung des Laufzeitsystems ist in der Sprungleiste am Anfang des RTS ein Vektor auf die neue Funktion einzufügen und die Konstantendeklarationen im Compiler (ReadInt, ReadChar, ...) anzupassen.
Außerdem muß unbedingt beachtet werden, daß der Code eine Stack-Maschine simuliert, das heißt, das Funktionsergebnis musß als oberstes Stacj-Element zurückgegeben werden.
Ist dann MCode_Offset = ENDLIB und das Puffer-Array PF genügend groß, braucht sie neue Funktion nur in den Prozeduren Expression oder Condition eingebaut zu werden.
Ein Assemblertestprogramm, direkt +ber das Laufzeitsystem gelegt, ist beim Testen der Funktionen von großem Nutzen.
Ein guter Debugger mit Single-Step-Mode auch.
Es gibt viele Stellen, an denen sich weiterschneidern läßt.
Auf Sprachebene können neue Standardtypen eingebaut werden (Pointer, Arrays, Records, Reals, Strings).
Auf Codegenerierungsebene können beispielsweise Daten nichtrekursiver Prozeduren im Adreßraum des Moduls statt auf dem Stack abgelegt werden.
Eine höhere Auslastung der Register kann man durch bessere Belegungsstrategien und Registerbelegungspläne erreichen und last and best, DOIT kann zum Mehrpasscompiler umgestrickt werden, um dann höhere Optimierungen durchführen zu können.
Ausführliche Methoden sind (leider nur in Englisch) in [2] beschrieben.
Auch die Qualität des Laufzeitsystems ist verbesserungsfähig:
String-Ausgabe bei WRITE-Anweisungen, Typenkonversionen, mathematische Funktionen wie Potenzen, ABS, SIN,...
Nachwort
Interessierten Lesern ist natürlich nicht entgangen, daß die vom Compiler tolerierte Syntax von der Sprachdefinition aus dem ersten Teil abweicht oder daß der Scanner bei der Folge '(* *)' seine Schwierigkeiten hat.
Dieser Bug läßt sich übrigens beheben, indem man in der Prozedur Kommentar das zweite 'GetChar' durch 'while ch='*' do GetChar' ersetzt.
Um wirklich einen Einblick in das Handwerk des Compilerbaus zu geben, ist nun mal ein bestimmter Aufwand notwendig gewesen.
Und bei dem Umfang, den der Compiler inzwischen angenommen hat, läßt sich beim besten Willen nicht ausschließen, daß er unter bestimmten Bedingungen Unsinn produziert.
Wenn Sie also einen Fehler finden und denken:
'Mensch, wie konnte der das übersehen?', seien Sie nachsichtig mit dem geplagten Autor.
Entfernen Sie den Bug, und weiter zur nächsten Überraschung, getreu nach Murphy's Gesetz 'Kein Programm ohne Fehler.
Murphy war ein Optimist.
Disketten mit dem Programmtext des DOIT-Compilers sind über den Verlag beim Autor erhältlich.
Literatur
| [1] | Wirth, N:
'Compilerbau' Teubner Verlag, Stuttgart 1984. |
| [2] | Ullman, J. D., Aho, A. V.:
'Prinziples of Compiler Design' Addison-Wesley Verlag, New York 1977. (ca. 100 DM) |
| [3] | Wirth, N:
'Algorithmen und Datenstrukturen' Teubner Verlag, Stuttgart 1982 |
| [4] | Zima, H.:
'Compilerbau I', 'Compilerbau I', B.I. Wissenschaftsverlag, Zürich 1982 |
| [5] | Davie, A. J. T.:
'Recursive Descent Compiling' Verlag Ellis Horwood Limited, Chichester, West Sussex, England 1981 |
|
|
|
|
| [Listing des Codegenerators] |
[Listing der Run-Time Library] |
|
Der DOIT-Compiler ist schon ein kleines Programmsystem geworden.
Er leistet ja auch mehr, als nur Maschinencode zu erzeugen...
|
Bearbeitet von
Werner Cirsovius
April 2011
© Heise Verlag
![[4. Teil]](../../gif/arrow_left.gif){kind=icon}
![[Inhalt]](../../gif/arrow_up.gif){kind=icon}