\chapter{Codegenerierung f"ur eine virtuelle Registermaschine}
\label{CodeGen}

Eine Voraussetzung f"ur die innovativen M"oglichkeiten des
Tycoon-Systems wie die Programmierung mit persistenten Threads \cite{MatSchm94}
 oder mobilen Agenten in heterogenen Netzen  \cite{Mathiske95}
ist eine maschinenunabh"angige und effektive Ausf"uhrungsrepr"asentation.
 Der Einsatz einer virtuellen Maschine
ist eine M"oglichkeit, Portabilit"at zu gew"ahrleisten; dieser Ansatz
wird f"ur eine Vielzahl von Sprachen mit Erfolg genutzt, z.B. Smalltalk \cite{GoRo83},
Java \cite{JAVA}, PC-Scheme \cite{BartleyJensen86} , TL \cite{MatSchm92}
und TooL \cite{GawMat96b}.

Die in diesen Systemen eingesetzten virtuellen Maschinen interpretieren einen ver\-einfachten
Maschinencode, der eine gezielte Unterst"utzung der Semantik der Hochsprache anbietet
und  Hardwaredetails verbirgt.
Durch  Portierung des Interpreters und des
Laufzeitsystems kann eine neue Hardwareplattform auf relativ einfache
Weise erschlossen werden. Ferner besteht die M"oglichkeit, Schnittstellen
f"ur externe Systeme in der Architektur der virtuellen \mbox{Maschine} vorzusehen und
dadurch die flexible Integration bestehender und zuk"unftiger \mbox{Dienste} zu erm"oglichen.


Einen gravierenden Nachteil stellt jedoch die Performanz von abstrakten Maschinen dar:
die Ausf"uhrungsgeschwindigkeit von virtuellem Maschinencode ist um eine bis zwei Gr"o\3enordnungen
schlechter als die von echtem Maschinencode. Die Ausf"uhrungszeiten
sind im wesentlichen  durch folgende Faktoren bestimmt:
\begin{itemize}
\item
Der Overhead einer Interpretationsschleife  liegt zwischen 10 bis 50
Zyklen pro Befehl der virtuellen Maschine\footnote{Diese Zahlen ergeben sich aus dem SPARC-Assembler-Text des Interpreters f"ur die
Tycoon-Registermaschine, und sind nur als grobe Sch"atzung anzusehen.}.
\item
Reale Maschinenregister k"onnen nicht f"ur Operanden verwendet werden.
\end{itemize}


Der interpretierte Kellermaschinencode der TVM bietet wenig
M"oglichkeiten f"ur
Ver\-besserungen durch Codegenerierungsma\3nahmen.
Statt eines neuen Entwurfs einer \mbox{ver"anderten} Kellermaschine
wird im Rahmen dieser Arbeit die bestehende Kellermaschine
TVM des Tycoon-Systems durch
eine Registermaschine  ersetzt, um einen Vergleich zwischen
den \mbox{beiden} Rechnerarchitekturen vor dem Hintergrund des Einsatzes
als virtuelle \mbox{Maschine} zu bieten.
Die Motivation f"ur diesen Schritt ist folgenderma\3en:
Registermaschinencode kann durch Register\-allokation in der
Codegenerierungsphase optimiert
werden, weil "uber eine gr"o\3ere Menge an
frei zug"angigen  lebendigen Operanden ({\em working set}) in den
simulierten Registern
verf"ugt wird, und damit  explizite Operandenbewegungen vermieden
werden. Techniken der Codegenerierung f"ur Registermaschinen
und der Registerallokation
sind erprobt und k"onnen direkt umgesetzt werden.



Der n"achste Schritt zur Effizienzsteigerung ist die Erzeugung von echtem
Maschinencode bedarfsweise zur Laufzeit; Ans"atze hierzu sind unter anderem in
\cite{LeeLeone96} und \cite{Engler94} beschrieben. F"ur das Tycoon System werden 
folgende Alternativen in Betracht gezogen:
\begin{enumerate}
\item
Erzeugung von C-Code aus dem Bytecode und anschlie\3ende "Ubersetzung
zur Laufzeit.
\item
Direkte Erzeugung von Maschinencode aus dem Bytecode.
\end{enumerate}

F"ur ein derartiges Vorhaben kann eine virtuelle Registerarchitektur
eher geeignet sein als eine Kellermaschine, da
explizit angegebene Operanden in echte Maschinenregister gelegt werden
k"onnen. Da aber eine Maschinencodegenerierung zun"achst experimentellen
Charakter bes"a\3e, ist nach wie vor die Leistung der interpretierenden
Maschine von Vorrang, wie auch die Robustheit und Einfachheit der
Codegenerierung. In den folgenden Abschnitten werden die Mechanismen
der Erzeugung von Registermaschinencode beschrieben. Ein
Leistungsvergleich zwischen interpretierenden Keller- und
Registerarchitekturen findet sich im Kapitel \ref{Benchmarks}.


\section{Die Architektur der Tycoon Registermaschine}

\begin{figure}[tbh]
\begin{center}
\leavevmode
\epsfxsize=12cm
\epsffile{closure.eps}
\end{center}
\caption{Format eines Funktionsabschlusses}
\label{ClosureFormat}
\end {figure}


 
Ausf"uhrungsgrundlage der Registerarchitektur,
deren Entwurf von Andreas Gawecki stammt, ist das sogenannte {\em flat closure}-Format (siehe Abbildung 
\ref{ClosureFormat}) f"ur Funktionsabschl"usse, auf das
einige der Instruktionen der Registermaschine zugeschnitten sind.
Ein Funktions\-abschlu\3 besteht in dem Tycoon-System aus 
zwei Vektoren:
dem Vektor der freien (globalen) Bindungen einer Funktion  und einem Codeobjekt
bestehend aus Bytecode und einem Vektor
der Literale (Zeichenketten, gro\3e Zahlen usw.). Dieser Aufbau
stellt eine M"oglichkeit dar, die lexikalischen Sichtbarkeitsregeln der Hochsprache
zu unterst"utzen. 
Der Vorteil dieser Struktur gegen"uber anderen Mechanismen wie verkettete
Umgebungen (z.B. beschrieben in \cite{Connor90})
liegt in dem schnellen Zugriff auf die freien Bindungen einer Funktion.
Bei "uber\-setzten TooL-Methoden, die noch nicht optimiert wurden, entfallen die globalen Bindungen, da Werte
von Exemplarvariablen "uber Botschaften referenziert werden.
Ein Funktionsabschlu\3 ist die Ausf"uhrungsrepr"asentation f"ur
eine Abstraktion.


\begin {figure}[tbh]
\centering

\begin{tabular}{|| l | l | l ||} \hline
{\em Opcode (Hex)}    &  {\em Befehl}  &  {\em Bedeutung} \\ \hline
0i              &  {\tt push}            &  Register i im Keller ablegen\\
1i              &  {\tt drop}            &   i Kellerfelder entfernen \\
2i              &  {\tt jump}            &  Endrekursiver Sprung an das Codeobjekt in r0 \\
3i              &  {\tt call}            &  Aufruf des Codeobjekts in r0 \\
4i              &  {\tt return}          &  Return, i Kellerfelder entfernen  \\
5d ii           &  {\tt ld\_sp}           &  rd \(\leftarrow\) Kellerfeld ii \\
6d ii           &  {\tt ld\_lit}          &  rd \(\leftarrow\) Literal ii \\
7i ds           &  {\tt seti}            &  rd[i] \(\leftarrow\) rs \\
80 ds           &  {\tt get}             &  rd \(\leftarrow\) rd[rs] \\
8x ds           &  {\tt alu}             &  rd \(\leftarrow\) rd $\otimes $ rs, \\
                &                        &  $\otimes \in
		                           \{+,-,\times,\div,mod,\wedge,\vee,xor,shl,shr,=,>,\ge,<,\le\} $\\
90 ds           &  {\tt geti}             &  rd \(\leftarrow\) rd[i] \\
9x di           &  {\tt alui}            &  rd \(\leftarrow\) rd \(\otimes \) i, \\
                &                        &  $\otimes \in
		                           \{+,-,\times,\div,mod,\wedge,\vee,xor,shl,shr,=,>,\ge,<,\le\} $\\
ad ii           &  {\tt closure}         &  rd \(\leftarrow\) neues Feld der Gr"o\3e ii \\
bi jj           &  {\tt send}            &  send r0 Selektor: jj, Argumente in r1 $\ldots $r15 \\
ci ii jj        &  {\tt sendLong}        &  send r0 Selektor: iijj,Argumente in r1 $\ldots $r15 \\
$\ldots$        &                        & \\
d1 d-           &  {\tt ld\_ok}           &  rd $\leftarrow$ ok (TSP-Wert f"ur nil) \\
d2 d-           &  {\tt ld\_false}        &  rd $\leftarrow$ false \\
d3 d-           &  {\tt ld\_true}         &  rd $\leftarrow$ true \\
e0 di           &  {\tt ld\_int}          & rd \(\leftarrow\) i \\
e1 ds           &  {\tt mov}             & rd \(\leftarrow\) rs \\
$\ldots$        &                        & \\
f1 ii           &  {\tt branch}              & Sprung um ii Bytes \\
f2 ii           &  {\tt branch\_cf}           & Bedingter Sprung um ii Bytes \\ \hline
\end{tabular}

\caption{Ausschnitt aus dem Instruktionssatz der Registermaschine}
\label{TRMOpCodes}
\end {figure}
 
Ein Teil des Instruktionssatzes der Registermaschine TRM\footnote{Tycoon Register Machine} ist in Abbildung \ref{TRMOpCodes}
wieder\-gegeben. Die Maschine ist eine Zwei-Adre\3-Maschine mit 16 Registern,
einem Keller und einem kompakten Befehlssatz (Bytecode) und bietet eine "ahnliche hochsprachliche 
Unter\-st"utzung wie die TVM ({\tt closure}, {\tt send}, {\tt class\_new} usw.).
Funktionsparameter werden in den Registern R1 bis R15 "ubergeben, wobei
der aufgerufene
Funktionsabschlu\3 bzw. der Empf"anger einer TooL-Botschaft in R0 abgelegt
wird. Mehr Parameter d"urfen nicht "uber\-geben werden.
Da der aufgerufene Funktionsabschlu\3 in R0 "ubergeben wird,
bleiben die globalen Bindungen w"ahrend der Ausf"uhrung einer
Funktion erreichbar.
Per Konvention liegen Funktionsergebnisse nach einem Aufruf in R0 vor.

Auffallend an dieser Architektur sind Abweichungen von "ublichen RISC-Architekturen,
 die aus der engen Verbindung zwischen Compiler-Technologie  
und Rechnerarchitektur ent\-standen. Diese Verbindung "au\3ert sich in Merkmalen wie
dem {\em load/store}-Modus, der die Analyse der Wert"ubertragungsbeziehungen
vereinfacht, Drei-Adre\3-Befehle passend zur Compiler-Zwischensprache
des Drei-Adre\3-Codes  und einer gro\3en Zahl
von allgemein verwendbaren
Registern (meistens 32). Programme in imperativen Sprachen mit relativ gro\3en
 Sequenzen 
von Anweisungen ohne Prozeduraufrufe k"onnen in sehr effizienten Maschinencode
f"ur RISCs "ubersetzt werden.
Eine ausf"uhrliche Erl"auterung dieser Zusammenh"ange
findet sich in \cite{HenPat90}. 

F"ur primitive Operationen ist die Zwischensprache TML isomorph zu
Drei-Adre\3-Code, aber gr"o\3ere Sequenzen von primitiven Anweisungen kommen seltener 
vor und werden vielfach von Prozeduraufrufen unterbrochen. Dadurch verringert sich die
Zahl der Variablen, die "uber l"angere Zeit in Registern gehalten werden k"onnen, und
der Vorteil von Drei-Adre\3-Befehlen, durch die zus"atzliche
 Register-Lade-Operationen vermieden werden k"onnen,
reduziert sich erheblich. Daher ist die Entscheidung f"ur ein Zwei-Adre\3-Format
mit weniger Register sinnvoll. Eine  kompakte Bytecodierung 
der Befehle ist m"oglich,  wenn in der Architektur maximal 16 Register
vorgesehen sind, da nur vier Bits f"ur die Codierung der Operanden
ben"otigt werden.

\section{Codegenerierung f"ur die Registermaschine}

Der CPS-Dialekt TML wird ohne weitere Transformationen\footnote{Im R"uckblick hat sich diese Tatsache als nachteilig erwiesen, worauf in
Abschnitt \ref{abstractions} noch eingegangen wird.}
in Maschinencode "ubersetzt.
Wie schon in Abschnitt \ref{TMLSection} erw"ahnt, kann TML als Lambdakalk"ul-Dialekt in
zwei syntaktische Kategorien  (Applikationen und Abstraktionen) aufgeteilt werden,
die bei der Codeerzeugung unterschiedlich behandelt werden.


\subsection{Applikationen}

Die applikative Natur von TML als strikter CPS-Dialekt bestimmt den Ablauf der 
Codegenerierung: Erst werden die Argumente einer Funktion (oder primitiven Operation)
ausgewertet und in Zielregistern abgelegt und anschlie\3end wird die Funktion
(oder primitive Operation) auf die Argumente angewandt.
In TML treten vier Formen von Applikationen auf:
\begin{enumerate}
\item
Lambda-Applikationen
\item
Funktionsapplikationen
\item 
Anwendung primitiver Operationen
\item
Fortsetzungsapplikationen
\end{enumerate} 
Der folgende TML-Ausschnitt enth"alt alle vier Applikationsarten: {\sf a} wird
durch eine Lambda-Applikation an 3 gebunden, die Addition ist ein TML-Primitiv,
und das Ergebnis der Addition wird durch eine Fortsetzungsapplikation weitergereicht
an die Funktionsapplikation {\small\sf (f 2 t\_1 $\ldots$)}.

\begin{xple}
\begin{tabbing}
(\k{lambda}(a)  \\
  $.$  (+ a 5 \k{cont}(t\_1)  \\
  $.$     (f 2 t\_1 cc))\\
  $.$ 3)\\
\end{tabbing}
\end{xple}

Die Auswertung der Argumente und die Code-Emission erfolgen je nach 
Applikationsart unterschiedlich:
\begin{enumerate}
\item 
Lambda-Applikationen dienen dazu, lokale Variablen zu binden, wobei die 
Argumente in beliebige Register abgelegt werden. F"ur die Lambda-Applikation
im obigen Beispiel 
k"onnte zum Beispiel durch die Emission von \sfrontq {\tt ld\_int R1 3}\sbackq der Wert
3 an {\sf a} gebunden werden\footnote{Die Strategie zur Auswahl der
Register wird in Abschnitt \ref{TargetingStrategy} erl"autert; die Wahl
{\tt R1} hat an dieser Stelle keine besondere Bedeutung.}.
\item
Bei Funktionsapplikationen m"ussen die Parameter\-"ubergabe\-konventionen der TRM
eingehalten werden, d.h. die Argumente werden in den Registern R0$\ldots$R15 abgelegt.
\item
Die Anwendung primitiver Operationen erfordert keine vorgeschriebenen Register
und bietet eine M"oglichkeit, die Qualit"at des Codes durch Registerallokation 
zu verbessern.
\item
Fortsetzungen erhalten ihr Argument aus der vorherigen Applikation, und erweitern
die lokalen Bindungen um ihren Parameter. Wenn die vorherige Applikation
ein Prozeduraufruf war, liegt das Argument in R0 vor (bedingt durch die 
Aufrufkonventionen der TRM), sonst in einem beliebigen Register.
Fortsetzungsaufrufe werden auf drei Arten "ubersetzt:
\begin{enumerate}
\item
Aufrufe an ungebundene Lambda-Fortsetzungen  von Applikationen erfordern
keinen Code.
\item
Gebundene Fortsetzungen werden in einen Sprung "ubersetzt.
\item
F"ur den Aufruf der R"ucksprungfortsetzung wird ein {\tt
return}-Bytecode emittiert.
\end{enumerate}

\end{enumerate}

Unter der Annahme, da\3 die Funktion {\sf f} aus dem Beispiel an der ersten Stelle 
im aktuellen Umgebungsvektor zu finden ist, und dieser in R15 liegt, ist
eine geeignete Codesequenz f"ur das Beispiel:

\begin{xple}
\begin{tabular}{lllll}
{\tt ld\_int}&{\tt r1}&{\tt 3}  &; {\rm Binden von 3 an {\sf a}} & (\k{lambda}(a) $\ldots$) 3 \\
{\tt addi}&{\tt r1}&{\tt 5}   &; {\rm Primitive Operation}     & (+ a 5 $\ldots$ \\
{\tt mov}&{\tt r2 }&{\tt r1}  &; {\rm Erweitern der Bindungen} & \k{cont}(t\_1) \\
{\tt mov}&{\tt r0 }&{\tt r15} &; {\rm Umgebung nach r0}        & (f 2 t\_1 $\ldots$)$_{1}$  \\
{\tt geti}&{\tt r0 }&{\tt 1}   &; {\rm {\sf f}  nach r0}        & (f 2 t\_1 $\ldots$)$_{2}$ \\
{\tt ld\_int}&{\tt r1}&{\tt 2}  &; {\rm 2 nach r1}               & (f 2 t\_1 $\ldots$)$_{3}$ \\
{\tt call}         &&   &; {\rm Funktionsaufruf}         & (f 2 t\_1 $\ldots$)$_{4}$   \\
{\tt return}&{\tt 0} &      &; {\rm R"ucksprungfortsetzung}  & cc \\
\end{tabular}
\end{xple}



\subsection{Abstraktionen} \label{abstractions}

Abstraktionen als gleichberechtigte Werte in TML erfordern eine besondere Behandlung
bei der Codegenerierung, um die Semantik der lexikalischen Sichtbarkeitsregeln und
die Eigenschaft von Funktionen als gleichberechtigte Werte
zu realisieren.
Ein Funktionsabschlu\3 mu\3 einen Teil der Erzeugungsumgebung, n"amlich die Menge  der freien
Bindungen, beinhalten, damit unabh"angig von der aktuellen
Ausf"uhrungsumgebung alle referenzierten Werte erreichbar bleiben (selbst
wenn die Erzeugungsumgebung nicht mehr existiert). In dem Tycoon-System
m"ussen Funktionsabschl"usse zus"atzlich speicherbar sein. 

Die folgenden Schritte aus dem TVM-Codegenerator zur "Ubersetzung von Funktionsabschl"ussen ({\em closure conversion})
  werden  auf TRM-Mechanismen abgebildet:

\begin{enumerate}
\item
Der Rumpf einer Abstraktion wird in Bytecode "ubersetzt, wobei die freien
Variablen der Abstraktion in einer Liste eingesammelt werden. Die Lage einer
Variable in dieser Liste entspricht dem Index, an dem diese Bindung im 
Umgebungsvektor liegen wird. Dieser Index ist daher schon w"ahrend der
Code-Emission des Rumpfs bekannt.
\item 
Der "ubersetzte Bytecode wird mit den Literalen des Rumpfes w"ahrend der "Ubersetzung
in einen Literalvektor zusammengefa\3t, der wiederum
zu den Literalen des um\-gebenden Kontextes hinzugef"ugt wird
und somit im umgebenden Kontext referenzierbar ist. Eine verkettete
Struktur (siehe Abbildung \ref{litvecChain}) von Literalvektoren entsteht, die im Literalvektor
der obersten Funktion eingetragen wird. 
\item
F"ur den umgebenden Ausf"uhrungskontext der Abstraktion wird Code generiert, der den Umgebungsvektor
anlegt und die freien Bindungen eintr"agt.
Dieser Code enth"alt  au\3erdem Befehle, die den Literalvektor des
Rumpfes (erreichbar "uber die Literale des umgebenden Kontextes) im Umgebungsvektor
des Funktionsabschlusses eingetragen.
\end{enumerate}


\begin{figure}[tbh]
\begin{center}
\leavevmode
\epsfxsize=10cm
\epsffile{litvecs.eps}
\end{center}
\caption{Verkettung von Literalvektoren}
\label{litvecChain}
\end {figure}


Das Vorgehen soll an folgender Beispielabstraktion erl"autert werden:
\begin{xple}
\begin{tabular}{l}
\k{proc}(cc) \\
  (cc a)
\end{tabular}
\end{xple}
Diese
Abstraktion besitzt nur eine freie Variable {\sf a}, daher wird {\sf a} an der Position
mit dem Index 1 im Umgebungsvektor\footnote{Der Umgebungsvektor
liegt per Konvention bei einem Funktionsaufruf in R0.}
liegen, woraus sich der Index des 
{\tt geti}-Befehls im Bytecode des Rumpfes ergibt:
\begin{xple}
\begin{tabular}{ll}
{\tt geti r0 1}  &; {\rm erste globale Variable im Umgebungsvektor: {\sf a}} \\
{\tt return  0}  &; {\rm R"uckgabe "uber r0}\\
\end{tabular}
\end{xple}
Der Code zum Anlegen des Funktionsabschlusses
wird im umgebenden Kontext der Abstraktion ausgef"uhrt. Unter der Annahme, 
da\3 im umgebenden Kontext {\sf a} lokal in R3 vorliegt und der Literalvektor
der Abstraktion  {\small\sf \k{proc}(cc)$\,$(cc a)} 
sich an dem Index 2 im aktuellen Literalvektor befindet, sieht der
Bytecode zum Anlegen des Funktionsabschlusses wie folgt aus:
\begin{xple}
\begin{tabular}{ll}
{\tt closure r0 2} &; {\rm Allokation von 2 Worten f"ur {\sf a} und den Literalvektor} \\
{\tt seti  1 r0 r3} &; {\rm Eintragen von {\sf a}}\\
{\tt ld\_lit  r15 2}  &; {\rm Literalvektor des Rumpfes nach r15} \\
{\tt seti 0  r0 r15}  &; {\rm Eintragen des Literalvektors}\\ 
\end{tabular}
\end{xple}

Abbildung \ref{abstractionCode} deutet an, wie diese Codefragmente
in Literalvektoren verkettet werden und  auf welche Weise
der Bytecode eines
anzulegenden
Funktionsabschlusses zur Laufzeit im aktuellen Literalvektor erreichbar ist.


\begin{figure}[tbh]
\begin{center}
\leavevmode
\epsfxsize=10cm
\epsffile{abscode.eps}
\end{center}
\caption{Literalvektoren f"ur die Abstraktion {\sf {\bf proc}(cc)$\,$(cc a) }}
\label{abstractionCode}
\end {figure}



Eine Erkenntnis aus der Entwicklung des  Codegenerators betrifft die "Ubersetzung
von Abstraktionen: in TML als Sprache h"oherer Ordnung  sind Abstraktionen Objekte
erster Klasse wie in TL oder TooL. Wie an dem vorherigen Beispiel erkennbar ist, hat
die Erzeugung von Funktionsabschl"ussen in Maschinencodeschritten keine
Entsprechung im TML-Code. In dem in dieser Arbeit verwendeten
Registerallokationsverfahren (siehe Abschnitt \ref{regAlloc}) wirkt sich
\mbox{diese} Tatsache
nachteilig aus, da die Registerallokation auf der TML-Repr"asentation arbeitet, und
die Erzeugung von Funktionsabschl"ussen zu nicht explizit erkennbaren Register\-anforderungen
f"uhrt. Eine L"osung ist, "ahnlich wie in dem ML-"Ubersetzer von Appel
\cite{Appel89} oder dem CPS-Backend von Kelsey und Hudak \cite{Kelsey89a}
obige Schritte als zus"atzliche TML-Transformationsphase
durchzuf"uhren, und  damit alle Variablenbenutzungen und Registeranforderungen
offenzulegen. 

\subsubsection{Wechselseitig rekursive Abstraktionen}


Bei wechselseitig rekursiven Abstraktionen tritt das Problem auf, da\3
einige der freien \mbox{Variablen} einer Abstraktion zum Zeitpunkt des Anlegens
des Funktionsabschlusses noch nicht gebunden sind, und zwar die
jeweils wechselseitig rekursiven Bezeichner. Der folgende TML-Ausschnitt
verdeutlicht diesen Sachverhalt:

\begin{xple}
\begin{tabular}{ll}
  (Y \k{proc}(c\_1 g f)&\\
  (c\_1 &\\
    \k{cont}()&\\
      (c g)&\\
    \k{proc}(c\_2)       &; {\rm Abstraktion {\sf g}}\\
      (c\_2 f)        &; {\rm besitzt {\sf f} als freie Variable}\\
    \k{proc}(c\_3)       &; {\rm Abstraktion {\sf f}}\\
      (c\_3 g)))      &; {\rm besitzt {\sf g} als freie Variable}\\
\end{tabular}
\end{xple}


Wenn der Funktionsabschlu\3 von {\sf g} angelegt wird, ist die freie Variable {\sf f}
im Umgebungs\-kontext noch nicht gebunden. Sie wird erst nach Anlegen des
Funktionsabschlusses von {\sf f}, also nach der "Ubersetzung der Abstraktion {\sf f}
gebunden. Daher werden die Eintr"age der un\-gebundenen freien Variablen 
in den Globalvektoren erst nach der "Ubersetzung aller wechsel\-seitig rekursiven
Abstraktionen vorgenommen.
F"ur obigen TML-Code sieht der emittierte Maschinen\-code folgenderma\3en aus:
\begin{xple}
\begin{tabular}{ll}
{\tt closure   r15     2} &; {\rm Anlegen des Funktionsabschlusses {\sf g}}\\
{\tt ld\_lit    r14     1} &; {\rm Literalvektor von {\sf g} an Index 1 im aktuellen Kontext}\\
{\tt seti  0   r15     r14}&; {\rm Eintrag des Literalvektors} \\
&\\
{\tt closure   r14     2} &; {\rm Anlegen des Funktionsabschlusses {\sf f}}\\
{\tt seti  1   r14     r15} &; {\rm {\sf g} ist schon gebunden}\\
{\tt ld\_lit    r13     2} &; {\rm Literalvektor von {\sf f} an Index 2 im aktuellen Kontext} \\
{\tt seti  0   r14     r13} &; {\rm Eintrag des Literalvektors} \\
&\\
{\tt seti  1   r15     r14} &; {\rm Nachtrag: {\sf f} in {\sf g} eintragen}
\end{tabular}
\end{xple}




\section{Registerallokation} \label{regAlloc}

Ein wesentlicher Aspekt bei der Codegenerierung f"ur Registerarchitekturen ist
eine Registerallokation. Eine geschickte Verwaltung der knappen Ressource
\glqq Register\backq
f"uhrt zu effizientem und elegantem Maschinencode, und auf realen Maschinen
werden Variablenzugriffe entscheidend beschleunigt.
Das verbreitete Verfahren, die Allokation als F"arbungsproblem aus der
Graphentheorie zu modellieren \cite{Chaitin81} \cite{ChowHen90}, l"a\3t
sehr \mbox{effiziente} Registerbelegungen zu, wird aber nicht f"ur CPS-basierte
"Ubersetzer eingesetzt.
Durch die hohe Dichte an Prozeduraufrufen sind  Grundbl"ocke k"urzer
als in imperativen Sprachen,
so da\3 die Menge der lebendigen Variablen in der Regel klein ist.
Ferner diktieren die Parameter\-"ubergabe\-konventionen einen Gro\3teil der
Registerbelegungen, so da\3 die Allokations\-freiheit zus"atzlich eingeschr"ankt
ist.
Anstelle einer umfassenden Allokation wird in dem TRM-Codegenerator eine
Registerzuordnung ({\em register targeting})
nach \cite{Wulf73} vor\-genommen, eine Methode, die auch in 
ML-"Ubersetzern \cite{Appel89} und 
Lisp-"Ubersetzern \cite{HARE} \cite{ORBIT}  zum Einsatz kommt.
Die Registerzuordnung besteht aus zwei getrennten Phasen:
 einer Lebendigkeitsanalyse und einem Zuordnungslauf.

\subsection{Lebendigkeitsanalyse}

In \cite{Wulf73} wird ein  N"aherungsverfahren f"ur die Berechnung von Lebendigkeits\-bereichen
von Bezeichnern
beschrieben, das auch in dem TRM-Codegenerator eingesetzt wird.
Jeder Knoten eines Programms
erh"alt eine Ordnungsnummer, welche die Position des Knotens als
Tupel von zwei Zahlen angibt: der Linearordnungszahl und der Verzweigungsordnungszahl. 
Die Linearordnungszahl entspricht etwa einer \glqq Zeilennummer\backq, die sich aus einer
Linearisierung des Programms erg"abe (verschiedene Bl"ocke eines Konditionals
werden  in Maschinen\-anweisungen "ubersetzt, die hintereinander im Speicher
liegen). Die Linearordnungszahl wird von einem Knoten zum n"achsten inkrementiert.
Die Verzweigungsordnungszahl ist f"ur verschiedene Arme einer Verzweigung gleich
und wird entlang eines Arms ebenfalls inkrementiert.
Die Verzweigungsordnung erm"oglicht einen einfachen Test, ob
verschiedene Variablen in den gleichen Zweigen lebendig sind.

Die Berechnung der 
Ordnungstupel erfolgt in einem einfachen Durchlauf
des TML-Baums.
Abbildung \ref{lonFon} zeigt die
Tupel $<$Linearordnung,Verzweigungsordnung$>$ f"ur einen TML-Ausschnitt.



\begin{figure}[tbh]
\begin{center}
\leavevmode
\epsfxsize=8cm
\epsffile{lonfon.eps}
\end{center}
\caption{Linearordnung und Verzweigungsordnung eines TML-Baums}
\label{lonFon}
\end {figure}

Die Zuordnung der Ordnungszahlen auf das Bespiel in Abbildung
\ref{lonFon} ist folgenderma\3en:

\begin{xple}
\begin{tabular}{ll}
(\k{lambda}(join)  &$<1,1>$ \\
 . (== x true false &$<2,2>$ \\
 .  \k{cont}()     &$<3,3>$ \\
 .     (join 6502) &$<4,4>$ \\
 .  \k{cont}()     &$<5,3>$ \\
 .     (join x)) &$<6,4>$ \\
  \k{cont}(t)          &$<7,5>$ \\
    (cc t))        &$<8,6>$ \\
\end{tabular}
\end{xple}



Der Lebendigkeitsbereich eines Bezeichners ist durch die Ordnungsposition
seiner ersten Definition und die Position seiner letzten Nutzung gegeben. Globale Bezeichner
erhalten die Position des Funktionskopfes als Definitionsposition. In
dem Beispiel besitzt {\sf x} den Lebendigkeitsbereich $<$1,1$>$-$<$6,4$>$
und {\sf t} den Lebendigkeitsbereich $<$7,5$>$-$<$8,6$>$.
Derartig definierte Lebendigkeitsbereiche lassen sich als Rechtecke
auffassen (siehe Abbildung \ref{lonluFonlu}),
deren linker unterer Eckpunkt die Definitionsposition ist und deren rechter
oberer Eckpunkt durch die Position der letzten Nutzung gebildet wird.
Ein Lebendigkeitskonflikt zweier Bezeichner ist an der "Uberschneidung
der jeweiligen Rechtecke erkennbar.

Die Berechnung der Lebendigkeitsbereiche erfolgt in einem zweiten Baumdurchlauf,
in dem die Definitionspunkte
und letzten Nutzungspunkte f"ur
alle Bezeichner in eine Tabelle eingetragen werden.

\begin{figure}[tbh]
\begin{center}
\leavevmode
\epsfxsize=10cm
\epsffile{lonlufonlu.eps}
\end{center}
\caption{Lebendigkeitsbereiche als Rechtecke}
\label{lonluFonlu}
\end {figure}

\subsection{Registerzuordnung}
\label{TargetingStrategy}

In dem  Registerzuordnungsverfahren  k"onnen Registerpr"aferenzen f"ur lokale
Variablen ermittelt werden. Allerdings werden im Gegensatz zu
dem in \cite{Wulf73} beschriebenen Verfahren im Tycoon-Codegenerator
"ahnlich wie bei \cite{Appel89}
Zielregister ({\em targets}) bei
einem Baumaufstieg und nicht bei dem Abstieg abgeleitet. 
Dabei lassen sich aus vorgeschriebenen 
Registerbelegungen, die aus den Prozeduraufrufkonventionen und den
Beschr"ankungen einiger Befehle folgen, geeignete Register f"ur
fr"uhere Vorkommen einer Variable finden, so da\3 unn"otige
Lade-Befehle vermieden werden k"onnen.
Das einfache Beispiel in Abbildung \ref{targetExample} veranschaulicht diesen 
Zusammenhang.

\begin {figure}[tbh]
\setlength{\unitlength}{1mm}
\begin{xple}
\begin{tabular}{ll}

$\ldots$ &\\
 \k{cont}(a)               &; {\rm 3. Definition von{\sf a}: ideal ist{\tt R2}}   \\
  (+ a 1 \k{cont}(b)        &; {\rm 2. Definition von{\sf b}: ideal ist {\tt R1}}
\begin{picture}(0,0)
\put(10,-5){\vector(0,1){13}}
\put(15,0){\rm Ableitungsrichtung}
\end{picture}
  \\
    (f b a cc))         &; {\rm 1. Funktionsaufruf:{\sf b} in{\tt R1},{\sf a} in{\tt R2}}\\

\end{tabular}
\end{xple}

\caption{Zuordnungsbeispiel}
\label{targetExample}
\end {figure}

Der im TRM-Codegenerator eingesetzte Zuordnungsalgorithmus nutzt sowohl den 
Baumabstieg als auch den Aufstieg:

\begin{itemize}
\item
Der Aufstieg dient der Ableitung geeigneter
Definitionsregister und Nutzungsregister f"ur Operanden primitiver Operationen.
Trifft man beim Aufstieg auf eine vorgeschriebene Nutzung eines Registers, so
wird diese weiter nach oben propagiert. In dem \mbox{Beispiel \ref{targetExample}}
erfordert der Aufruf von {\sf f}, da\3 {\sf b} in R1 und {\sf a} in R2 vorliegt. Bei der
Anwendung der primitiven Operation {\sf \sfrontq +\sbackq} weiter oben im Baum ist f"ur {\sf a} also R2 ein 
g"unstiges 
Nutzungsregister, und die Definition von {\sf a} sollte geeigneterweise auch R2
verwenden.
\item
Der Abstieg wird dazu genutzt, Kandidaten f"ur eine Keller-Allokation zu ermitteln.
Im  Keller m"ussen alle Variablen alloziert werden, deren Lebendigkeitsbereich
mehrere Grundbl"ocke "uberspannt. Das Ende eines Grundblocks ist
 durch TML-Konstrukte mit mehr als einer Fortsetzung
(z.B. Konditionale), Funktionsaufrufe und den Fixpunkt-Kombinator Y gekennzeichnet. 

Das Verfahren beim Abstieg
ist folgenderma\3en:
Alle Definitionen von lokalen \mbox{Variablen} werden akkumulierend weitergereicht,
bis der Abstieg auf einen der begrenzenden Knotentypen st"o\3t. Alle akkumulierten Variablen,
die mit ihrem Lebendigkeitsbereich diesen Knoten "uberspannen, werden zur Allokation in
den Keller vermerkt.
\end{itemize}

\subsection{Zuteilung der Register}

Die endg"ultige Zuteilung der Register erfolgt w"ahrend der
Codegenerierung.
Hierzu werden in Anlehnung an \cite{Dragonbook} zwei Tabellen gef"uhrt:
eine f"ur den aktuellen Inhalt der Registerbank und eine Tabelle f"ur die 
Aufenthaltsorte aller Variablen.
Die Registervergabe erfolgt durch eine zentrale Funktion {\sl resolveLocation},
die ein Datum (Variable, Literal, oder Abstraktion) und ein Zielregister als Parameter
 erh"alt, und je nach Inhalt der Tabellen und Lebendigkeitsinformation
wie folgt agiert:
\begin{enumerate}
\item
Liegt das Datum schon in dem gew"unschten Register, ist keine Codeemission
erforderlich.
\item
Liegt das Datum in einem anderen Register {\tt Rx}, so lautet die n"otige TRM-Anweisung:\\
{\small\tt mov Rziel Rx}
\item
Variablen, die sich im Keller befinden, werden von dem Keller in das Zielregister
bef"ordert: \\
{\small\tt ld\_sp Rziel offset}
\item
Globale Variablen m"ussen "uber den Globalvektor geholt werden (der vorher durch eine
rekursive Anwendung der Funktion {\sl resolveLocation} in ein weiteres Register gebracht
werden mu\3): \\
{\small\tt mov Rziel Rglobalvektor} \\
{\small\tt geti Rziel offset}
\item 
Literale werden aus dem Literalvektor gelesen: \\
{\small\tt ld\_lit Rziel offset}
\item
Sollten Konflikte bei der Zuteilung auftreten, weil das Zielregister ein
lebendiges Datum enth"alt, wird der Inhalt des Zielregisters im Keller ausgelagert. 
\item 
Falls das Zielregister nicht spezifiziert ist, wird das n"achste freie
Register ohne lebendigen Inhalt vergeben.
\item
Alle "Anderungen der Aufenthaltsorte werden in den Tabellen vermerkt.
\end{enumerate}


Die Wirksamkeit dieses Registerallokationsverfahrens soll an dem
Beispiel der Fakult"atfunktion demonstriert werden. Von dem folgenden
TML-Code,
der wie der TRM-Code von der Ausgabe des "Ubersetzers
"ubernommen wurde, sind aus Gr"unden der "Ubersichtlichkeit
einige Teile (wie die Ausnahmebehandlung) weggelassen; an
den Ergebnissen der Registerzuteilung f"ur den TRM-Code "andert dieses
nichts:

\begin{xple}
\k{proc}(n c\_1)
  (== n 1
      \k{cont}()
        (c\_1 1)
      \k{cont}()
        (- n 1 \k{cont}(t\_1)
        (f t\_1 \k{cont}(t\_2)
        (* n t\_2  c\_1))))
\end{xple}

Der dazugeh"orige TRM-Code ist:

\begin{xple}
\begin{tabular}{lllll}
{\tt  push}          &{\tt r0}&              &; f &(1) \\
{\tt  push}          &{\tt r1} &             &; n &(2)\\
{\tt  eqi}           &{\tt r1} &{\tt  1}     &;& \\
{\tt  branch\_cf}     &    &{\tt l0} &; &\\
{\tt  branch}        &    &{\tt l1}&;&\\
{\tt l0:}&&&& \\
{\tt  ld\_int}       &{\tt r0} &{\tt  1}      &; &\\
{\tt  return}         &{\tt  2}  &            &;  &(3)\\
{\tt l1:}&&&&\\
{\tt  ld\_sp}         &{\tt r1} &{\tt  0}      &; n&\\
{\tt  subi}           &{\tt r1}  &{\tt  1}      &;   &(4)\\
{\tt  ld\_sp}         &{\tt r0} &{\tt  1}      &; f&\\
{\tt  call}           &{\tt  1}  &            &; f&\\
{\tt  move}           &{\tt r2}  &{\tt r0}      &; t&\\
{\tt  ld\_sp}         &{\tt r0}  &{\tt  0}      &; n&\\
{\tt  mul}            &{\tt r0}   &{\tt r2}      &;   &(5) \\
{\tt  return}         &{\tt  2}  &           &; \\
\end{tabular}
\end{xple}

Zu einigen Punkten des TRM-Codes l"a\3t sich folgendes anmerken:
\begin{enumerate}
\item
Die Funktion {\sf f} mu\3 als rekursive Funktion im Keller abgelegt
werden.
\item
Der Lebendigkeitsbereich des Parameters {\sf n} "uberspannt unter
anderem den Funktionsaufruf {\sf (f t\_1 $\ldots$)}  und mu\3 daher auch im Keller liegen.
\item
Die beiden Kellereintr"age m"ussen vor dem R"ucksprung aus
dem Keller gel"oscht werden.

\item
Da das Ergebnis von {\sf(- n 1 $\ldots$) } als erster Parameter des
rekursiven Aufrufs von
{\sf f} in dem Register R1 erwartet wird, schl"agt der
Zuordnungsalgorithmus das Register R1 f"ur die Definition von {\sf
t\_1} vor.

\item
Das Register R0 wird als Ergebnisregister des letzten Schritts {\sf (* n t\_2 $\ldots$)}
gew"ahlt, da Funktionen ihre Ergebnisse in R0 ablegen.



\end{enumerate}




Anhand der gemessenen Laufzeiten f"ur einige Benchmarks  erfolgt in dem
n"achsten \mbox{Kapitel} ein quantitativer Vergleich mit der Kellermaschine.
Vorab l"a\3t sich feststellen, da\3 das Code\-generierungs\-verfahren f"ur
die TRM erheblich aufwendiger  als die
Codegenerierung f"ur die TVM ist, und da\3 der Performanzgewinn
zu gering ist, um die Registermaschine als Ausf"uhrungsplattform
zu rechtfertigen.
