1 /***************************** doc/gen.doc *************************************
3 Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
5 See file COPYRIGHT for information on usage and disclaimer of warranties
7 Enth"alt die Beschreibung der Schnittstelle zwischen dem systemUNabh"angigen
8 und dem systemABh"angigen Teil des Compilers.
10 Authors: Reinhard Grafl EMAIL: cacao@complang.tuwien.ac.at
12 Last Change: 1997/03/05
14 *******************************************************************************/
16 Der gr"osste Teil des Compilers ist maschinenunabh"angig programmiert,
17 aber diejenigen Programmteile, die den tats"achlichen Maschinencode
18 erzeugen, m"ussen f"ur jede Maschine extra implementiert werden.
20 Alle diese abh"angigen Teile habe ich im Verzeichnis 'sysdep' zusammen-
21 gefa"sst (und sysdep selbst ist ein symbolischer Link auf das entsprechende
22 Verzeichnis der tats"achlichen Architektur, so dass nur mehr dieser Link
23 umgesetzt werden muss, damit das Programm auf einem anderen Rechner
24 compiliert werden kann).
26 Im Verzeichnis 'comp' gibt es folgende systemabh"angige Programmteile:
27 (diese Dateien sind als Links in das Verzeichnis 'sysdep' realisiert)
29 reg.c ..... Registerbelegung
30 gen.c ..... generieren von Maschinencode
31 disass.c .. Disassembler (nur f"ur Debug-Zwecke)
34 -------------------------------------------------------------------------------
35 1. Der Registerallokator (reg.c)
36 -------------------------------------------------------------------------------
38 Die Pseudoregister, die vom Compiler bei allen Operationen verwendet werden,
39 m"ussen irgendwann mit tats"achlichen CPU-Registern belegt werden.
41 Die Belegung funktioniert nach folgendem Prinzip:
43 Immer, wenn der Compiler ein CPU-Register f"ur eines seiner
44 Pseudoregister ben"otigt, ruft er eine entsprechende Funktion des
45 Allokators auf. Diese erzeugt eine 'reginfo'-Struktur, die die
46 Information f"ur ein Register enth"alt (Typ INT/FLOAT, Registernummer,
47 Auslagerungsinformation...).
48 Der Inhalt der 'reginfo'-Struktur ist f"ur den systemunabh"angigen
49 Compiler nicht von Bedeutung (wird also sozusagen als opaker Datentyp
51 Wenn irgendwann nicht mehr genug CPU-Register zur Verf"ugung stehen,
52 dann darf der Allokator Register auch in den Speicher (also auf den
53 Stack) auslagern. Er muss dazu einfach eine entsprechende 'reginfo'-
54 Struktur erzeugen, die dann eben den Offset im Stackframe und
55 alle n"otigen Zusatzinformationen enth"alt.
58 Die Funktionen im einzelnen sind:
61 initialisiert den Registerallokator
64 reginfo *reg_allocate(u2 type, bool saved, bool new)
65 erzeugt eine reginfo-Struktur mit den entsprechenden Eintr"agen.
66 (Diese Datenstruktur muss am DUMP-Speicher [siehe Toolbox-Beschreibung]
67 angelegt werden, damit sie irgendwann sp"ater automatisch freigegeben
70 Das so belegte Register muss verschiedene Voraussetzugen erf"ullen:
71 - Es muss ein Datum vom Java-Typ type
72 (= TYPE_INT/TYPE_LONG/TYPE_FLOAT/TYPE_DOUBLE/TYPE_ADDRESS)
74 - Wenn saved=true, dann darf das Register w"ahrend Funktionsaufrufen
75 nicht zerst"ort werden.
76 - Wenn new=true, dann darf das Register noch NIE vorher vergeben
79 Alle so mit 'reg_allocate' belegten Register werden f"ur nachfolgende
80 Aufrufe von 'reg_allocate' gesperrt, sie d"urfen also nicht zweimal
81 hintereinander vergeben werden (eh klar!).
83 Diese Funktion muss IMMER eine g"ultige 'reginfo'-Struktur erzeugen,
84 auch wenn vielleicht keine normalen Register mehr "ubrig sind. In
85 solchen F"allen muss eben ein auf den Speicher ausgelagertes
86 Register erzeugt werden.
89 void *reg_free(reginfo *r)
90 Gibt ein durch reg_allocate angefordertes Register tempor"ar wieder
91 frei. Dabei darf die 'reginfo'-Struktur aber NICHT zerst"ort werden,
92 weil sie vom Compiler sp"ater wieder gebraucht wird.
93 Das solchermassen frei gewordene CPU-Register (nicht diese reginfo-
94 Struktur) darf aber bei einem folgendem Aufruf von reg_allocate
95 wieder vergeben werden.
98 bool reg_reallocate (reginfo *r)
99 versucht ein schon einmal angefordertes (aber in der Zwischenzeit
100 wieder freigegebenens) Register neuerlich anzufordern.
101 Wenn das Register immer noch unbenutzt ist, dann ist alles OK
102 (R"uckgabewert true), sonst wird 'false' zur"uckgeben, und aus der
103 neuerlichen Belegung wird nichts. In diesem Falle wird der Compiler
104 versuchen, mit 'reg_allocate' ein ganz neues Register anzufordern.
107 void reg_display (reginfo *r)
108 dient nur zu Debug-Zwecken, und gibt eine lesbare Darstellung des
109 mit 'reginfo' beschriebenen Registers auf 'stdout' aus.
113 Die nachfolgenden Funktionen sind f"ur die Optimierung der Funktionsaufrufe,
114 bzw. der Registerbenutzung im Zusammenhang mit Funktionsaufrufen bestimmt.
115 Jede dieser Funktionen darf entweder NULL zur"ckliefern (als allererste
116 nichtoptimierte Version), oder aber eine entsprechende 'reginfo'-Struktur.
119 reginfo *reg_parlistresult(u2 type)
120 erzeugt eine 'reginfo'-Struktur (auf dem DUMP), die das CPU-Register
121 beschreibt, mit den normalerweise ein Datum vom Typ type von
122 Funktionen zur"uckgeliefert wird.
123 Diese Funktion wird auch schon vor dem Aufruf von 'reg_init' verwendet,
124 Diese Funktion selbst blockiert noch kein Register, und sie braucht auch
125 keine R"ucksicht auf irgendwelche schon durchgef"uhrten Registerbelegungen
126 nehmen. Die tats"achliche Allokation wird sp"ater mit einem Aufruf
127 von 'reg_reallocate' versucht.
129 reginfo *reg_parlistexception()
130 erzeugt eine 'reginfo'-Struktur (auf dem DUMP), die das CPU-Register
131 beschreibt, mit den normalerweise der Zeiger auf eine Exception von
132 Funktionen zur"uckgeliefert wird.
133 Ansonsten v"ollig analog zu 'reg_parlistresult'
135 reginfo *reg_parlistpar(u2 type)
136 erzeugt eine 'reginfo'-Struktur (auf dem DUMP), die das CPU-Register
137 beschreibt, mit dem normalerweise ein Datum vom Typ type als Parameter
138 an eine Funktion "ubergeben wird.
139 Diese Funktion wird im allgemeinen mehrmals hintereinander aufgerufen,
140 n"amlich f"ur jedes gew"unschte Parameterregister einmal.
141 Jede solche Sequenz wird mit 'reg_parlistinit' eingeleitet.
142 Ansonsten funktioniert diese Funktion wie 'reg_parlistresult'.
143 Achtung: Diese Funktion sollte gegebenenfalls auch maximale Anzahl
144 der Parameter bei Funktionsaufrufen notieren, wenn diese Information
145 sp"ater vom Codegenerator gebraucht wird.
147 void reg_parlistinit ()
148 Setzt den Parameterz"ahler, den die Funktion 'reg_parlistpar' intern
149 ben"otigen wird, auf 0.
152 -------------------------------------------------------------------------------
153 2. Der Codegenerator (gen.c)
154 -------------------------------------------------------------------------------
156 Der Compiler erzeugt im ersten Durchgang eine systemunabh"angige Darstellung
157 einer Methode (Operationen mit Quell- und Ziel(pseudo)registern).
158 Im zweiten Durchgang werden alle Pseudoregister mit tats"achlichen Registern
159 belegt (siehe oben), und
160 im dritten Durchgang wird der tats"achliche Code erzeugt (eben durch
163 Der Codegenerator besteht aus mehreren Teilen:
166 void gen_computestackframe()
167 berechnet das Memory-Layout des Stackframe f"ur die Methode.
168 Dabei m"ussen alle Register, die vom Register-Allokator vergeben
169 worden, sind und die Anzahl der zu sichernden Register und
170 die maximale Anzahl der Parameter ber"ucksichtigt werden.
173 erzeugt den Kopf der Methode (Anlegen des Stackframes, sichern von
174 Registern, holen der Parameter vom Stack oder von Registern, etc..)
176 void gen_pcmd (pcmd *c)
177 erzeugt zu einem Pseudo-Kommando den entsprechenden Maschinencode.
178 Eine Beschreibung der pcmd-Struktur und aller f"ur den Codegenerator
179 relevanten globalen Variablen und Funktionen sind weiter unten beschrieben.
181 void gen_resolvebranch ( void* mcodepiece, u4 sourcepos, u4 targetpos)
182 tr"agt eine tats"achlien Sprungadresse in den vorher erzeuten
183 Maschinencode ein (Backpatching).
184 Parameter: mcodepiece ... Zeiger in den Speicher, wo der entsprechende
186 sourcepos .... relative Adresse des Sprungbefehls in Byte
187 (vom Methodenbeginn an gerechnet)
188 targetpos .... relative Adresse des Sprungziels in Byte
189 (vom Methodenbeginn an gerechnet)
192 Alle Literale, die der Codegenerator erzeugt (konstante Integers,
193 Addressen,...) werden in einem direkt VOR dem Codesegment liegenden
194 Datensegment gespeichert.
195 Dabei w"achst das Datensegment von oben nach unten, und das Codesegment
197 Die Addressierung sowohl des Codes, als auch der Daten kann dann
198 "uber ein einziges Basisregister (auf der ALPHA ist das das Register
200 Der Codegenerator greift auf diese beiden Segmente nur "uber spezielle
201 Funktionen zu, die den Speicher f"ur die Segmente gegebenenfalls
202 vergr"ossern k"onnen.
203 Am Ende der Generierung wird ein dann einziger Speicherblock angelegt,
204 wo beide Segmente passgenau hineingeschrieben werden.
207 3. Der Disassembler (disass.c)
208 -------------------------------------------------------------------------------
210 Der Disassembler dient nur zu Debug-Zwecken und kann durch eine Dummy-Funktion
213 Der Disassembler hat nur eine Funktion:
215 disassemble(u4 *code, u4 len)
216 erzeugt ein lesbares Listing der Maschinenbefehle, die im Speicher
217 an der angegebenen Stelle stehen. Die L"ange des Maschinenprogrammes
218 wird hier in BYTE angegeben.
219 Das Listing wird auf 'stdout' ausgegeben.
223 ------------------------------------------------------------------------------
224 Beschreibung der globalen Variablen und Methoden
225 ------------------------------------------------------------------------------
227 Der Codegenerator braucht f"ur seine Arbeit einige Funktionen und
228 Variablen, die im systemUnabh"angigen Teil bereits zur Verf"ugung stehen.
234 mcode_addu4 (u4 codepiece)
235 f"ugt zum aktuell erzeugten Codesegment ein 32-Byte-Wort hinzu.
236 Damit sollten sich alle Maschinenbefehle (zumindest f"ur RISC)
239 s4 dseg_adds4 (s4 value)
240 s4 dseg_adds8 (s8 value)
241 s4 dseg_addfloat (float value)
242 s4 dseg_adddouble (double value)
243 s4 dseg_addaddress (void *value)
244 diese Funktionen f"ugen das entsprechende Datum zum Datensegment
245 der Methode hinzu. Das Alignment wird auf jeden Fall richtig
248 Alle diese Funktionen liefern als R"uckgabewert den Offset des
249 Datenelements innerhalb des Datensegments zur"uck. Weil das Datensegment
250 direkt vor dem Codesegment liegt, und alle Addressierungen
251 relativ zum Methodenanfang (also zum Anfang des Codes) passieren,
252 sind diese Offsets immer negativ.
254 s4 dseg_addtarget (basicblock *target)
255 funktioniert im Prinzip so wie die obigen Funktionen, allerdings
256 wird in das Datensegment ein Zeiger auf eine Codeposition (deren
257 genaue Adresse aber noch gar nicht feststeht) eingetragen.
258 Die tats"achliche Adresse wird ganz am Ende der Codeerzeugung
259 automatisch an die richtige Stelle geschrieben, so dass beim
260 Programmlauf auf jeden Fall der richtige Wert dort steht.
261 (Diese Funktion wird wahrscheinlich vor allem f"ur Sprungtabellen
265 void mcode_addreference (basicblock *target)
266 Mit dieser Funktion macht der Codegenerator einen Eintrag in die
267 Liste der der sp"ater zu vervollst"andigenden Sprungbefehle.
268 Die Vorgehensweise ist folgende:
269 - Wenn der Codegenerator ein (Vorw"arts-)Sprunganweisung erzeugen will,
270 dann ruft er VORHER mcode_addreference auf (als Parameter
271 die entsprechende basicblock-Struktur)
272 - Dann erzeugt der Codegenerator einen Sprungbefehl (mit mcode_addu4),
273 l"asst dabei aber die Zieladdresse leer (weil sie ja noch nicht
275 - sobald der Code fertig erzeugt worden ist (und alle Sprungziele
276 feststehen) wird f"ur jeden so vorbereiteten Sprungbefehl die
277 Funktion gen_resolvebranch (Dokumentation siehe dort) aufgerufen.
285 zeigt an, dass die Methode eine Leaf-Methode ist, d.h, dass sie keine
286 weiteren Methoden oder Funktionen aufruft
289 die Anzahl der Parameter f"ur die Methode, inklusive dem
290 this-Zeiger (aber um den this-Zeiger braucht sich der Codegenerator
291 sowieso nicht extra k"ummern)
294 ein Zeiger auf ein Array von Integers, die die Java-Grundtypen
295 (TYPE_INT, TYPE_LONG,...) der Parameter angeben
298 gibt den Java-Grundtyp des R"uckgabewertes an (TYPE_INT, TYPE_LONG)
299 oder bei Methoden ohne R"uckgabewert: TYPE_VOID
302 ein Zeiger auf ein Array von Zeigern auf die varinfo-Strukturen.
303 Diese varinfos geben die Pseudoregister an, in die die Parameter
304 der Methode nach dem Aufruf geschrieben werden sollen (der Code
305 f"ur dieses (eventuell n"otige) Umladen der Werte muss von
306 gen_header erzeugt werden).
309 ------------------------------------------------------------------------------
311 ------------------------------------------------------------------------------
313 In den Pseudocommandos (pcmd) stehen als Operanden immer Verweise auf
314 Pseudoregister, denen w"ahrend der Registerbelegungsphase echte
315 Maschinenregister zugewiesen werden.
316 F"ur den nachfolgenden Codegenerator ist dann nur mehr das entsprechende
317 Maschinenregister von Bedeutung.
318 Der Codegenerator darf in der varinfo-Struktur nur auf das Feld
319 'reg' zugreifen, das einen Zeiger auf die entsprechende 'reginfo'-Struktur
320 (wie sie vom Registerallokator erzeugt worden ist -> siehe oben) enth"alt.
321 Der Codegenerator kann sich darauf verlassen, dass jeder varinfo-Struktur,
322 die "uber ein pcmd erreichbar ist, auch ein entsprechendes reginfo zugewiesen
327 ------------------------------------------------------------------------------
329 ------------------------------------------------------------------------------
331 Hier finden sich alle Informationen, die die Funktion 'gen_pcmd'
332 braucht, um damit Maschinencode f"ur ein Pseudokommando zu erzeugen.
333 Die Syntax dieser Struktur (mit Kommentaren) befindet sich unter anderem
334 in der Datei 'defines.c'.
336 F"ur verschiedene Typen von Kommandos muss die Struktur verschiedene
337 Daten enthalten, deshalb ist sie mit Hilfe einer 'union' realisiert,
338 und ein tag-Feld gibt den tats"achlichen Typ der Struktur an (jaja, in
339 C gibt es eben keine abgeleiteten Datentypen ...).
340 Die Werte und Bezeichnung f"ur dieses Tag-Feld steht ebenfalls in der
344 Beschreibung der allgemeinen Felder der 'pcmd'.
346 linkage ... interne Verkettung, f"ur den Codegenerator ohne Bedeutung)
347 tag ....... Kennzeichnung des Typs des Kommandos
349 dest ...... Pseudoregister f"ur eine optionalen Zieloperanden
350 source1 ... Pseudoregister f"ur den 1. optionalen Quelloperanden
354 Alle Kommandos (ausser unbedingten Spr"ungen) haben in irgendeiner Form
355 Operanden-Register. Dabei stehen Register aus denen ein Wert geholt wird
356 in den Feldern source1-source3, und ein Register in das ein Wert geschrieben
357 wird, steht im Feld dest. Alle unbenutzen Felder haben immer den
360 Alle Befehle haben eine genau definierte Anzahl von Operanden, deren
361 Typ ausserdem auf jeden Fall stimmt (die Register wurden zuvor mit
362 'reg_allocate' unter Angabe des richtigen Typs angefordert).
373 Jeder dieser Befehle l"adt einen Wert vom entsprechenden
374 Typ in das Zielregister.
375 Diese konstanten Werte selber stehen in
376 pcmd->i.value, pcmd->l.value ...
379 Kopiert einen Wert vom Quellregister 1 ins Zielregister.
380 Beide Register haben den Typ pcmd->move.type .
383 F"uhrt eine JavaVM-Grundoperation aus.
384 Im Feld pcmd->op.opcode steht der JavaVM-Opcode des gew"unschten
386 Die Anzahl und die Typen der Operanden sind f"ur jede Operation
387 anders. Eine genaue Beschreibung der Semantik findet sich
388 in der JavaVM-Spezifikation. Dabei sind die Quelloperanden
389 in der Reihenfolge wie sie in der Spezifikation am Stack stehen
390 (von links nach rechts), in die Quellregister 1 bis 3 aufgeteilt.
391 Bei Operanden vom Typ LONG oder DOUBLE sind beide 'value-words'
392 in einem Register zusammengefasst.
395 L"adt entweder einen Wert aus dem Speicher, oder schreibt
397 Das Feld pcmd->mem.opcode enth"alt dazu entweder CMD_GETFIELD
399 In pcmd->mem.type steht der Java-Grunddatentyp dieses
400 Feldes, und in pcmd->mem.offset steht der konstante Offset (in Byte),
401 der zum Basisregister (pcmd->source1) addiert werden soll, um die
402 tats"achliche Speicheradresse des Felds zu bekommen.
403 Bei Ladeoperationen steht das Ergebnis nachher im Register
404 pcmd->dest, bei Speicheroperationen steht der zu speichernde
405 Wert im Register pcmd->source2.
408 F"uhrt bedingte oder unbedingte Spr"unge aus. Im Feld
409 pcmd->bra.opcode steht der entsprechende JavaVM-Opcode.
410 Die Operanden (die laut JavaVM-Spec am Stack stehen m"ussen)
411 sind in den Registern pcmd->source1 und pcmd-source2 zu finden
412 (ganz analog zu dene OP-Kommandos).
414 JSR: Hier soll die R"ucksprungadresse ins Register pcmd-dest
416 RET: Obwohl laut JavaVM-Spec dieser Befehl den Stack nicht
417 beeinflusst, hat er dennoch einen Operanden: pcmd->source1
418 enth"alt die R"ucksprungadresse
422 in pcmd->source1 befindet sich der R"uckgabewert
423 (ausgenommen bei RETURN), und
424 in pcmd->source2 ist der Zeiger auf die zu werfende
427 Das Sprungziel (insofern bei dem Befehl eines m"oglich ist) wird
428 als Zeiger auf eine basicblock-Struktur "ubergeben.
429 Zum Aufl"osen der Sprungziele siehe: mcode_addreference.
432 Fu"hrt eine Programmverzweigung "uber eine Sprungtabelle durch.
433 Der einzige Operand (pcmd->source1) ist im Bereich von
434 i = 0 .. pcmd->tablejump.targetcount-1. Der Befehl soll an das
435 dementsprechende Sprungziel pcmd->tablejump.targets[i] verzweigen.
436 Zur Konstruktion einer Sprungtabelle siehe: dseg_addtarget.
440 F"uhrt einen Methoden (bzw. C-Funktions-) -aufruf durch.
441 Die Felder pcmd->method.paramnum und pcmd->method.params[..]
442 geben die Anzahl und die Register an, in denen die Parameter
443 stehen. Unter (g"unstigen) Umst"anden sind einige der Register
444 schon diejenigen, die durch die Aufrufkonventionen die Parameter
445 enthalten sollen (wenn das nicht der Fall ist, dann m"ussen
446 die Werte vor dem Aufruf noch umgeladen werden).
447 Das Feld pcmd->method.exceptionvar enth"alt (wenn es nicht
448 NULL ist) die Variable, in der eine allf"allig aufgetretene
449 Exception zur"uckerwartet wird.
450 Der normale R"uckgabewert der Methode soll ins Register
451 pcmd->dest geschrieben werden.
453 Dieses Pseudokommando wird sowohl f"ur Aufrufe von normalen
454 C-Funktionen (dann steht im Feld pcmd->method->builtin der
455 Zeiger auf diese Funktion) als auch f"ur Aufrufe von Java-Methoden
456 verwendet (dann steht im Feld pcmd->method->builtin der
459 Im zweiten Fall enth"alt das Feld pcmd->method->method einen
460 Zeiger auf die methodinfo-Struktur der gew"unschten Methode.
461 Bei Aufrufen vom Typ INVOKESTATIC und INVOKESPECIAL
462 (der Typ steht in pcmd->method->opcode) braucht dazu nur
463 der Funktionszeiger von dort geladen werden.
464 Bei INVOKEVIRTUAL und INVOKEINTERFACE muss der Funktionszeiger
465 aus der Virtual Function Table der Klasse des tats"achlichen
466 Objektes geholt werden. Der Zeiger auf dieses Objekt ist immer
467 im Register pcmd->method->params[0] zu finden.
468 Eine Beschreibung dieser Tabellen steht in der Datei "global.h".
470 WICHTIG: Dieses System compiliert alle Methoden beim ersten
471 Aufruf, deshalb m"ussen alle Methodenaufrufe immer mit dem
472 Umweg "uber die methodinfo-Struktur passieren, weil nur dort
473 dann der tats"achliche Funktionszeiger eingetragen wird.
474 Wenn die Methode n"amlich noch nicht aufgerufen wurde, dann
475 steht dort ein Zeiger auf den Compiler selbst.
476 Der Compiler ben"otigt f"ur seine Arbeit aber noch zus"atzlich
477 den Zeiger auf die methodinfo-Struktur in einem fixen
478 Register. Auf der DEC-ALPHA verwende ich hier das Register 28.
479 Die Aufrufsequenz auf der DEC-ALPHA f"ur einen normalen
480 INVOKESTATIC-Aufruf w"urde ungef"ahr so aussehen:
482 LDQ (28, 27, position_des_methodinfo_zeigers_im_datensegment)
483 LDQ (27, 28, OFFSET(methodinfo, func) )
485 LDA (27, 26, -position_dieses_befehls_im_code)
490 -------------------------------------------------------------------------------
491 Anhang: Notwendige Opcodes
493 F"ur die Befehle vom Typ OP m"ussen folgende Opcodes unterst"utzt werden:
564 F"ur die Befehle vom Typ MEM m"ussen folgende Opcodes unterst"utzt werden:
569 F"ur die Befehle vom Typ BRA m"ussen folgende Opcodes unterst"utzt werden:
598 F"ur die Befehle vom Typ METHOD m"ussen folgene Opcodes unterst"utzt werden: