% Studienarbeit von Marc Weikard
%
% Universitaet Hamburg
% Fachbereich Informatik
% Arbeitsbereich DBIS
%
% Kapitel: Maschinencode


\chapter{Die Maschinencodegenerierung}
\label{Kap. Maschinencode}

Effizienz, Portabilit"at und einfache Skalierbarkeit sind wesentliche Grundpfeiler der Tycoon-Philosophie. Diese Aspekte spiegeln sich auch im Tycoon-Laufzeitsystem wieder.

TVM-Bytecode ist eine kompakte Programmrepr"asentation, die durch ihre Plattform\-unabh"angigkeit innovative Konzepte, wie z.B. migrierende, persistente Threads, erst erm"oglicht. Seine geringe Komplexit"at und f"ur Erweiterungen offene Struktur garantiert die einfache Implementierung geeigneter Interpreter bzw. Codegeneratoren. Bytecode, als Instruktionssatz einer virtuellen Maschine und der daraus resultiernden interpretierenden Ausf"uhrung, bedingt jedoch im Vergleich zu Maschinencode eine geringere Performanz, da die Ausf"uhrung einer Byteinstruktion durch eine Sequenz von 10 -- 50 Maschineninstruktionen emuliert werden mu"s. 

Die direkte "Ubersetzung von TL-Funktionen in Maschinencode scheidet aufgrund schwerwiegender Nachteile aus, obwohl sie zu einer h"ohere Ablaufgeschwindigkeit f"uhren w"urde:           
\begin{itemize}
\item Mangelnde Portabilit"at. \\
Die fehlende Bin"arkompatibilit"at zwischen verschiedenen Prozessorfamilien erfordert f"ur jede Systemplattform eigene Codegeneratoren und beschr"ankt die gemeinsame Nutzung von Daten und Programmen auf homogene Rechnerumgebungen.
\item Hohe Komplexit"at. \\
Moderne Prozessoren weisen eine erheblich komplexere Architektur und einen umfangreicheren Befehlssatz als die virtuelle Maschine auf. F"ur Codegeneratoren besteht ein erh"ohter Implementierungsaufwand.  
\item Gro"ser Speicherbedarf.\\
Die Funktionalit"at einer Byteinstruktion (8 Bit) mu"s durch eine Sequenz von Maschineninstruktionen (auf RISC-Prozessoren 32, teilweise 64 Bit) realisiert werden.
\end{itemize}
Die dynamische Maschinencodeerzeugung unter Verwendung bestehender Compilertechnologie stellt ad"aquate Methoden bereit, die hohe Performanz des Maschinencodes ohne die oben genannten Nachteile zu nutzen.  

Dieses Kapitel beschreibt die Implementierung eines dynamischen Maschinencodegenerators f"ur das Tycoon-Laufzeitsystem unter besonderer Beachtung der Erfordernisse, die von Seiten eines persistenten Systems gestellt werden, u.a. Unterst"utzung der Freispeicherverwaltung und der Laufzeiteinbindung (Abschnitt~\ref{Abs. Implementierungsprobleme}). Zus"atzlich werden M"oglichkeiten der Programmoptimierung diskutiert (Abschnitt~\ref{Abs. Optimierung}).


\section{Integration in die Tycoon-Architektur}
\label{Abs. Integration}

Bei der Entwicklung des dynamischen Codegenerators f"ur das Tycoon-System standen zwei Ziele im Vordergrund:
\begin{enumerate}
\item Der erzeugte Code soll auch weiterhin alle innovativen Konzepte, u. a. die Migration von Threads, unterst"utzen.      
\item Die L"osung soll m"oglichst geringe Eingriffe und "Anderungen am System erfordern.
\end{enumerate}
Aus diesen Vorgaben heraus mu"s der Bytecode als plattformunabh"angige Programmrepr"asentation erhalten bleiben und als Ausgangsbasis f"ur den Maschinencode dienen. Der Codegenerator selbst wird als \e{just in time} Compiler in das Laufzeitsystem integriert (siehe Abbildung~\ref{NeueArchitektur}). Im Gegensatz zu einer statischen Maschinencodeerzeugung im Anschlu"s an die "Ubersetzung von TL in Bytecode, die gr"o"sere "Anderungen an Compiler-Backend und Laufzeitsystem erfordern w"urde, ist diese Art der Codeerzeugung einerseits auch auf im Netz migrierende Threads anwendbar, zum anderen mu"s nur zur Ausf"uhrung kommender Bytecode in Maschinencode "ubersetzt werden.

\begin{figure}[b]
\begin{center}
\leavevmode
\epsfxsize=12cm
\epsffile{Bilder/NeueArchitektur.eps}
\caption{Tycoon-Schichtarchitektur mit integriertem Maschinencodegenerator}
\label{NeueArchitektur}
\end{center}
\end{figure}

Interpreter und generierter Maschinencode existieren in der modifizierten Architektur der TVM gleichberechtigt nebeneinander. Zugriff und Ablaufkontrolle werden von einer "ubergeordneten Instanz wahrgenommen, die dar"uber hinaus den dynamischen Codegenerator steuert. Die Entscheidung, wann eine Funktion interpretiert bzw. in Maschinencode "uberf"uhrt wird, kann von verschiedenen Kriterien abh"angig gemacht werden. In der aktuellen Implementierung werden alle Funktionen des TL-"Ubersetzers von der dynamischen Codeerzeugung ausgeschlossen, d.h. der "Ubersetzer selbst wird interpretiert und nur f"ur "ubersetzte Funktionen Maschinencode generiert. Dieses Verhalten sorgt f"ur eine optimale Geschwindigkeit der interaktiven Entwicklungsumgebung, da so lange Wartezeiten beim Systemstart vermieden werden. Es sind jedoch auch andere Mechanismen denkbar, z.B. nur besonders h"aufig genutzte Funktionen zu "ubersetzen oder die Codeerzeugung benutzergesteuert an- und auszuschalten.

Der Maschinencode folgt exakt dem TVM-Stapelmodell und f"uhrt insbesondere einen kompletten Registersatz, bestehend aus Bytecodebefehlsz"ahler, Stapel-, Rahmen- und Ausnahmezeiger, analog zum Interpreter. Die Ausf"uhrungsgrundlage ist f"ur alle innovativen Konzepte des Tycoon Systems, die auf der plattformunabh"angigkeit des Bytecodes basieren, vollkommen transparent. Auch der Wechsel zwischen bzw. der gegenseitige Aufruf von Interpreter und Maschinencode ist problemlos zu realisieren.   

Maschinencode wird nicht auf direktem Weg erzeugt, der dynamische Codegenerator bedient sich stattdessen der Programmiersprache C und eines externen C-"Ubersetzers. Die Vorteile, die sich aus der Verwendung von C als portable Zwischensprache ergeben, werden ausf"uhrlich in Abschnitt~\ref{Abs. C} diskutiert. Die Codeerzeugung umfa"st die Schritte:
\begin{itemize}
\item Bytecode reassemblieren \\
Der Bytecode wird in eine f"ur die Optimierung bzw. Codegenerierung besser geeignete Form transformiert. Opcodes und Operanden werden auf ihre volle Gr"o"se erweitert und die entsprechenden \s{PFIX}, \s{NFIX} und \s{OPR} Byteoperationen entfernt. F"ur Sprungbefehle mit relativer Adressierung werden absolute Zieladressen ermittelt. Alle Stellen, an denen die Abgabe des Kontrollflusses m"oglich ist, werden markiert (siehe hierzu auch Abschnitt~\ref{Abs. Sicherungspunkte}).
\item Optimierung \\
Diese Phase ist optional und im aktuellen System nicht realisiert. In Abschnitt~\ref{Abs. Optimierung} wird jedoch ein m"ogliches Beispiel zur Programmoptimierung vorgestellt.   
\item C-Quellcode erzeugen \\
Die in den Schritten 1 bzw. 2 gewonnene Programmdarstellung wird in C-Quelltext transformiert und auf einem externen Massenspeicher als tempor"are Datei abgelegt.   
\item Maschinencode generieren \\
Der C-"Ubersetzer erzeugt aus der Quelldatei Maschinencode und legt diesen als Datei auf dem Massenspeicher ab.
\item Maschinencode einbinden  \\
Die Mechanismen, die der Einbindung des Maschinencodes dienen, werden in Abschnitt~\ref{Abs. Einbindung} erl"autert.
\end{itemize}

\section{Die Wahl von C als portable Zwischensprache}
\label{Abs. C}

Zwei Alternativen bieten sich f"ur die Generierung von Maschinencode aus Bytecode an:
\begin{enumerate}
\item Entwicklung eigener Codegeneratoren \\
Sie geben dem Entwickler als gr"o"sten Vorteil die Kontrolle "uber die Anbindung an das Laufzeitsystem und alle prozessorinternen Besonderheiten, z.B. die Verwendung von Registervariablen, Zeigerarithmetik und Zugriffe auf Datenstrukturen. Dem entgegen stehen die hohen Entwicklungskosten, da jede Rechnerarchitektur spezifische Codegeneratoren erfordert.
\item Nutzung existierender, plattform"ubergreifender Werkzeuge \\
Sie erm"oglichen die Wiederverwendung bereits erprobter Technologie, die von architekturspezifischen Grenzen abstrahiert. Bestehende Codegeneratoren gewinnen vor allem durch die Verf"ugbarkeit leistungsf"ahiger Optimierer. Selbst auf niedrigem Niveau operierende Werkzeuge wie Assembler sind in der Lage, einfache Optimierungen vorzunehmen, z.B. l"angere Befehlssequenzen durch wenige bzw. einzelne "aquivalente Instruktionen zu ersetzen (\e{peephole optimizer}). Andere auf h"oherem Niveau operierende Werkzeuge, z.B. Compiler, implementieren wesentlich effizientere Optimierungsmechanismen \cite{ASU}.
\end{enumerate}
Der im Vergleich zu einem spezifischen Codegenerator geringe Entwicklungsaufwand und die hohe Portabilit"at waren die ausschlaggebenden Kriterien, ein bestehendes Werkzeug einzusetzen.    

Die Mehrzweckprogrammiersprache C bietet sich aufgrund besonderer Vorteile f"ur die Nutzung als Zwischensprache bei der dynamischen Codeerzeugung an:
\begin{itemize}
\item C-Quellcode ist einfach zu generieren.
\item C orientiert sich an der heutigen Prozessoren zugrundeliegenden 'von Neumann'-Architektur. Diese starke Hardwaren"ahe f"uhrt zur Erzeugung sehr schnellen Maschinencodes.
\item Durch Beschr"ankung auf die vom American National Standards Institute (ANSI) vorgegebenen Standards k"onnen plattformunabh"angige Programme geschrieben werden.  
\item Es existieren leistungsf"ahige Optimierer. 
\end{itemize}
C ist zudem nicht zuletzt Dank der Free Software Foundation und ihres auf allen g"angigen Systemplattformen frei verf"ugbaren GNU C-Compilers eine der am weitesten verbreiteten Programmiersprachen.


\section{L"osung spezieller Implementierungsprobleme}
\label{Abs. Implementierungsprobleme}

Persistente Programmiersprachen stellen besondere Anforderungen bei der Generierung von Maschinencode, vor allem die Unterst"utzung einer Freispeicherverwaltung, Ausnahmebehandlung, paralleler Threads und der Einbindung externen Programmcodes in ein laufendes System. Dieser Abschnitt zeigt L"osungsm"oglichkeiten f"ur die erw"ahnten Probleme auf.


\subsection{Einbindung externen Programmcodes zur Laufzeit}
\label{Abs. Einbindung}

Die Nutzung eines externen C-"Ubersetzers bedingt die Notwendigkeit, den generierten Maschinencode zur Laufzeit in das Tycoon-System einzubinden. Die unter \pn{Solaris} erfolgte Implementierung verwendet hierzu die vom Betriebssystem bereitgestellte M"oglichkeit, dynamisch ladbare Bibliotheken (\e{shared libraries}) zu verwenden. Dynamische Bibliotheken wurden urspr"unglich f"ur den Einsatz in Mehrbenutzerbetriebssystemen konzipiert, da sie in nur einer Laufzeitinstanz ihre Funktionalit"at mehrenen Programmen zur Verf"ugung stellen k"onnen und so zu erheblichen Speicherplatzeinsparungen f"uhren.

Die Erzeugung einer dynamischen Bibliothek erfordert zwei Schritte: die Generierung einer Objektdatei aus dem C-Quelltext durch den C-Compiler und deren anschlie"sende Transformation in eine dynamische Bibliothek durch den Linker. Die Betriebssystemfunktionen \s{dlopen} und \s{dlsym} erm"oglichen das Laden einer dynamischen Bibliothek zur Laufzeit bzw. die Ermittlung der Speicheradressen exportierter Funktionen und Datenstrukturen.

Jedem Funktionsobjekt entspricht eine dynamische Bibliothek. Nachdem diese geladen wurde, kann der Funktionszeiger auf den Maschinencode mittels \s{dlsym} ermittelt, derefenziert und so die Funktion aufgerufen werden.  
 
Da dynamische Bibliotheken auch die Verwendung globaler Variablen gestatten, ergibt sich die einfache Anbindung an die unterst"utzenden Funktionen des Laufzeitsystems und die Objektspeicherschnittstelle.

F"ur Systeme, die nicht "uber den Mechanismus des dynamischen Bindens verf"ugen, bietet sich die in \cite{BDBV94} vorgestellte Methode an, selbstextrahierenden Code zu verwenden. Der Codegenerator erzeugt hierzu aus jeder Funktion ein Programm, welches sofort ausgef"uhrt wird und seinen Maschinencode in einer tempor"aren Datei ablegt. Diese Datei kann nun vom Laufzeitsystem gelesen und die darin enthaltene Funktion aufgerufen werden. Dieser Ansatz erfordert jedoch zwingend die Generierung vollkommen im Speicher relokatiblen Programmcodes und erlaubt nicht den direkten Zugriff auf globale Objekte, so da"s diese z.B. als Funktionsargumente "ubergeben werden m"ussen.  


\subsection{Caching von Funktionen}
\label{Abs. Caching}

Die Effizienz des Funktionsaufrufes spielt in einer "uberwiegend funktionalen Sprache wie TL f"ur die Systemperformanz eine entscheidende Rolle. Allein die Laufzeit des externen C-"Ubersetzers, \cite{EHK95} geht beim GNU C-Compiler von 30000 n"otigen Zyklen f"ur die Generierung einer Maschineninstruktion aus, "ubertrifft die Ausf"uhrungszeiten der erzeugten Funktionen in der Regel bei weitem und w"urde so, bei mit jedem Funktionsaufruf neu zu generierenden Code, jeglichen durch den Maschinencode erreichten Geschwindigkeitsvorteil zunichte machten. Aus diesem Grund ist es zwingend notwendig, einmal eingebundenen Maschinencode m"oglichst "uber die gesamte Laufzeit hinweg im System zu halten und einen Mechanismus zur Verf"ugung zu stellen, der ein schnelles Auffinden der aufgerufenen Funktionen erlaubt.

Das Laufzeitsystem stellt zu diesem Zweck eine Indextabelle mit $2^{16}$ Eintr"agen bereit, in die f"ur jede dynamisch eingebundene Funktion die OID des Literalvektors und die Speicheradresse des geladenen Maschinencodes eingetragen werden. Leere Tabelleneintr"age werden als frei markiert. Der Zugriff auf die einzelnen Tabelleneintr"age erfolgt "uber einen 16 Bit gro"sen Index, der aus der ver"anderlichen OID (siehe auch Abschnitt~\ref{Abs. Freispeicherverwaltung}) des Literalvektors errechnet wird. Dieses in der Literatur als \e{hashing} bekannte Verfahren \cite{ALGO} verbindet den schnellen Zugriff auf einzelne Elemente mit geringem Speicherplatzverbrauch.

Die effiziente Implementierung des Hashing-Mechanismus ist von der richtigen Wahl des Zugriffsschl"ussels abh"angig. Die Berechnung eines 16 Bit gro"sen Index aus den Literalvektor-OIDs der gesuchten Funktionen ist sehr schnell -- sie erfordert auf Maschinenebene nur eine Registerschiebeoperation mit anschlie"sender Maskierung der relevanten Bits -- und liefert nur in Ausnahmef"allen f"ur zwei verschiedene Funktionen den gleichen Wert.

Die Speicheradresse des Maschinencodes kann nach erfolgter Indexberechnung und der notwendigen "Uberpr"ufung, ob der ermittelte Tabelleneintrag auch von der gesuchten Funktion belegt wird, aus der Tabelle ausgelesen werden. Sollte der entsprechende Eintrag noch frei sein, so wird der dynamische Codegenerator f"ur die aufzurufende Funktion Maschinencode erzeugen, einbinden und die Hash-Tabelle aktualisieren. Im Falle von Konflikten kommt der in \cite{ALGO} diskutierte Aufl"osungsmechanismus des \e{linear probing} zum Einsatz.   

Dynamisch generierter C-Quellcode und der TVM-Interpreter benutzen f"ur Funktionsaufrufe denselben Mechanismus:
{\xr \begin{tabbing}
XX\= XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX \= X \kill  
  \> literalOID = *FramePointer;                   \> /* OID Literalvektor laden */ \\
  \> functionPointer = lookup(literalOID); \> /* Funktionszeiger laden */ \\
  \> (*functionPointer)(0);                        \> /* Funktion aufrufen */
\end{tabbing}}
Die in der "ubergeordneten Kontrollinstanz (Abschnitt~\ref{Abs. Integration}) lokalisierte Funktion \s{functionLookup} liefert einen Zeiger auf die aufzurufende Funktion. Bei diesem Zeiger kann es sich sowohl um die Speicheradresse dynamisch gebundenen Maschinencodes als auch um einen Funktionszeiger auf den Interpreter handeln. Der Wechsel zwischen beiden Ausf"uhrungsvarianten wird von der Kontrollinstanz gesteuert und ist auf der Codeebene voll transparent.  


\subsection{Freispeicherverwaltung}
\label{Abs. Freispeicherverwaltung}

Wie in Abschnitt~\ref{Abs. TSP} beschrieben, unterst"utzt der Objektspeicher eine Freispeicherverwaltung, die f"ur die automatische Deallokation nicht mehr erreichbarer Daten- und Funktionsobjekte zust"andig ist. Sie ist ein interner Mechanismus des Objektspeichers und auf Ebene des Bytecodes bzw. des generierten Maschinencodes nicht sichtbar. Dies erfordert auf der einen Seite keinerlei Unterst"utzung durch das Laufzeitsystem und erm"oglicht die Implementierung verschiedener Speicherverwaltungsstrategien, hat aber andererseits erheblichen Einflu"s sowohl auf den Interpreter als auch den Maschinencode, da sich Objektreferenzen zur Laufzeit "andern k"onnen.

Die Speicherfreigabe und damit verbundene Neuvergabe der OIDs kann prinzipiell mit jeder Allokation eines persistenten Objektes ausgel"ost werden. Daher d"urfen Datenwerte, die innerhalb einer Funktion mehrmals ben"otigt werden, nicht in (Register)Variablen zwischengespeichert werden, sondern m"ussen bei jedem Zugriff erneut aus dem Stapel- bzw. Objektspeicher ausgelesen werden. Betroffen von diesem Umstand ist vor allem die erreichbare G"ute des generierten Maschinencodes, da die Reduzierung von Speicherzugriffen durch das Laden von Datenworten in Prozessorregister, eine f"ur C-"Ubersetzer g"angige und effiziente Optimierungstechnik, nicht genutzt werden kann. Hieraus ergeben sich auch f"ur den Interpreter und den erzeugten C-Quelltext Restriktionen im Einsatz von lokalen und globalen Variablen.        

Die Freispeicherverwaltung beeinflu"st auch die in Abschnitt~\ref{Abs. Caching} beschriebene Indextabelle der dynamisch eingebundenen Maschinencodefunktionen. Mit Aufruf der Speicherfreigabe "andern sich die OIDs der Funktionsobjekte und ihrer einzelnen Komponenten und erfordern so eine Aktualisierung der Tabelle. Die Aufz"ahlungsfunktion stellt nicht nur einen Weg bereit Objekte der Kontrolle der Freispeicherverwaltung zu unterstellen, sie liefert au"serdem f"ur bereits bekannte Objekte die neue Referenz in den Objektspeicher zur"uck. So kann die neue OID f"ur jeden eingetragenen Literalvektor ermittelt und eine neue Indextabelle aufgebaut werden.


\subsection{Persistente Sicherungspunkte}
\label{Abs. Sicherungspunkte}

Die orthogonale Persistenz des Tycoon Systems erstreckt sich auf Daten, Funktionen und Threads. F"ur Threads ergeben sich aufgrund ihrer dynamischen Struktur besondere Restriktionen, die die dynamische Codegenerierung beeinflussen.

Die Ausf"uhrungskontexte jeder innerhalb eines Threads aktivierten Funktion m"ussen zu bestimmten Zeitpunkten, z.B. dem Ausl"osen der Freispeicherverwaltung, dem Setzen von Sicherungspunkten oder dem Herunterfahren des Systems, eingefroren und sp"ater wieder aktiviert werden. Ohne genaue Kenntnis der zugrundeliegenden Systemarchitektur und Unterst"utzung durch das Betriebssystem ist dieses Ziel bei Maschinencode nicht zu erreichen, da der Ausf"uhrungszustand durch folgende Parameter bestimmt wird: den Prozessorregistern, dem Stapelspeicher und der Speicheraufteilung. Diese Parameter sind f"ur jede Plattform spezifisch und nicht "ubertragbar.

Der virtuelle Maschine schafft dagegen eine von der Rechnerarchitektur unabh"angige Basis f"ur die einheitliche Darstellung des Systemzustandes. Aus diesem Grund f"uhrt der generierte Maschinencode den kompletten TVM-Ausf"uhrungskontext analog zum Interpreter weiter. 

An allen Punkten, an denen der Kontrollflu"s eine Funktion verl"a"st, werden die TVM-Register explizit aktualisiert und Wiedereinstiegspunkte generiert. Dies betrifft:
\begin{itemize}
\item Funktionsaufrufe,
\item Aufrufe externer C-Funktionen,
\item TSP-Operationen, die neue Objekte anlegen, sowie
\item Ausnahmen.
\end{itemize}
Alle entsprechenden Byteinstruktionen werden in der Reassemblierungsphase entsprechend markiert und w"ahrend der Codeerzeugung von zus"atzlichem C-Quellcode umgeben. Dies wird am Beispiel der Byteinstruktion \s{ARRAY} gezeigt (Beispiel~\ref{Array}), die von dem C-Makro \s{saveTVMRegisters(8)} eingeleitet wird, welches die TVM-Register sichert und den Befehlsz"ahler auf die n"achste auszuf"uhrende Instruktion (im Beispiel 8) setzt. Eine am Ende generierte Sprungmarke (\s{cont8}) definiert den Wiedereinstiegspunkt und erlaubt das Wiederaufsetzen bei der folgenden Instruktion.

\begin{Beispiel}
\begin{center}
\begin{minipage}{0cm}
{\xr \begin{tabbing}
XX \= XX \= XX \= XXXXXXXXXXXXXXXXXXXXXX \= X \kill
   \> ... \\
   \> {\xb saveTVMRegisters(8);}   \> \> \> {\xb /* TVM Register sichern, */} \\
   \> \{                           \> \> \> {\xb /* Befehlsz"ahler = 8 */} \\
   \>    \> Word i; \\
   \>    \> Word nElements = Operand; \\
   \>    \> tsp\_OID oid; \\
   \>    \> oid = tsp\_newArray(store, tsp\_Format\_TAGGED, nElements); \rule{0mm}{6mm} \\
   \>    \> for(i = 0; i < nElements; i++) \rule{0mm}{6mm} \\
   \>    \>    \> tsp\_SET\_WORD(store, oid, i, *(StackPointer - i)); \\
   \>    \> StackPointer -= nElements; \\
   \>    \> *(++StackPointer) = oid; \\
   \> \} \\
{\xb cont8:}                    \> \> \> \> {\xb /* Wiedereinstiegspunkt */} \\
   \> ...
\end{tabbing}}
\end{minipage}
\caption{C-Quellcode der Byteinstruktion \s{ARRAY}}
\label{Array}
\end{center}
\end{Beispiel}

Die generierten Sprungziele markieren alle Programmpunkte, an denen ein Wiederaufsetzen bzw. Neustart der Funktion erfolgen kann. Da diese Stellen nicht direkt aufgerufen werden k"onnen, wird jeder Funktion der Wiedereinstiegspunkt als Argument in Form des TVM-Befehlsz"ahlers "ubergeben, welcher in einem die Funktion einleitenden Prolog ausgewertet wird (Beispiel~\ref{Prolog}).

\begin{Beispiel}[t]
\begin{center}
\begin{minipage}{0cm}
{\xr \begin{tabbing}
XX \= XX \= XXXXXXXX \= XXXXXXXXXXXXXXXXXXXX \= X \kill
Word generated\_X4574(Word contIP) \\
\{ \\
   \> ... \\
   \> {\xb if(contIP == 0) \{}                       \> \> \> {\xb //} \\
   \>    \> {\xb ...}                                   \> \> {\xb //} \\
   \>    \> {\xb CHECK\_STACK\_OVERFLOW(14)}            \> \> {\xb //} \\
   \>    \> {\xb goto start;}                           \> \> {\xb //} \\
   \> {\xb \}}                                       \> \> \> {\xb // Prolog} \\
   \> {\xb switch(contIP) \{}                        \> \> \> {\xb //} \\
   \>    \> {\xb case 4:}   \> {\xb goto cont4;}           \> {\xb //} \\
   \>    \> {\xb case 16:}  \> {\xb goto cont16;}          \> {\xb //} \\
   \>    \> {\xb default:}  \> {\xb return ILLEGAL\_CONT;} \> {\xb //} \\
   \> {\xb \}} \\
{\xb start:}                                      \> \> \> \> // Wiedereinstiegspunkt \\
   \> ... \\
   \> {\xb saveTVMRegisters(4);} \\
   \> {\xs call    '=='}                             \> \> \> // Funktionsaufruf \\
{\xb cont4:}                                      \> \> \> \> // Wiedereinstiegspunkt \\
   \> ... \\
   \> {\xb saveTVMRegisters(16);} \\
   \> {\xs call    '+'}                              \> \> \> // Funktionsaufruf \\
{\xb cont16:}                                     \> \> \> \> // Wiedereinstiegspunkt \\
   \> ... \\
   \> {\xs ret} \\
\}
\end{tabbing}}
\end{minipage}
\caption{Funktionsprolog}
\label{Prolog}
\end{center}
\end{Beispiel}

Beim Funktionsaufruf, d.h. bei der "Ubergabe einer 0 als Argument, wird "uberpr"uft, ob der Stapelspeicher noch gen"ugend freie Eintr"age f"ur die Ausf"uhrung der Funktion bereith"alt. Sollte dies nicht der Fall sein, wird er automatisch vergr"o"sert. Der von jeder Funktion auf dem Stapel ben"otigte Platz wird bereits statisch w"ahrend der Generierung des Bytecodes im Compiler-Backend ermittelt und im Literalvektor abgelegt. 

Der ohnehin sehr aufwendige Funktionsaufruf wird durch den Prolog weiter verteuert (zu den Auswirkungen siehe Abschnitt~\ref{Abs. Performanz}). Die Verwendung der schnelleren Adressarithmetik des GNU C-"Ubersetzers, wie sie in \cite{BDBV94} demonstriert wird, kann nicht zum Einsatz kommen, da sie nicht plattformunabh"angig ist. Sie w"urde zudem, als spezielle Syntaxerweiterung, die Nutzung beliebiger C-"Ubersetzer verhindern.

\newpage

\subsection{Parallele Threads}
\label{Abs. parallele Threads}

Die Abarbeitung paralleler Threads, ist eng mit der Implementierung der persistenten Sicherungspunkte gekoppelt, da die Ausf"uhrung von Funktionen an definierter Stelle unterbrochen und zu einem sp"ateren Zeitpunkt fortgesetzt werden mu"s. Der Kontexttransfer erfolgt durch den in Abschnitt~\ref{Abs. parallele Prozesse} beschriebenen Mechanismus des Laufzeitsystems. Der Codegenerator erzeugt an ausgew"ahlten Programmpunkten C-Quellcode, der mit Ablauf des festgelegten Zeitintervalls den Ausf"uhrungskontext wechselt. Diese Kontextwechselpunkte sind:
\begin{itemize}
\item Funktionseintritt
\item Sprungbefehle mit R"uckw"artsreferenz
\end{itemize}
Funktionsaufrufe treten w"ahrend der Ausf"uhrung aufgrund des funktionalen Charakters von TL in regelm"a"sigen, kurzen Abst"anden auf und eignen sich daher gut f"ur die Ausl"osung von Kontextwechseln. Um die Blockierung des Prozessmanagers durch Endlosschleifen zu verhindern, werden weitere Kontextwechselpunkte bei Sprungbefehlen mit r"uckw"arts gerichteten Zieladressen eingef"ugt. 

Threads sind im Tycoon System keine isolierten Objekte. Es herrscht ein gewisses Ma"s an Interaktion, ein Thread kann andere Threads erzeugen, suspendieren, beenden oder an einen anderen Rechner verschicken. Aus diesem Grund ist an den Kontextwechselpunkten das Speichern des TVM-Kontextes und die Generierung von Wiedereinstiegspunkten erforderlich, um die Abarbeitung suspendierter Funktionen wieder aufzunehmen. Kontextwechselpunkte stellen somit nur eine besondere Form der persistenten Sicherungspunkte dar (Beispiel~\ref{Kontextwechsel}).

\begin{Beispiel}[p]
\begin{center}
\begin{minipage}{0cm}
{\xr \begin{tabbing}
XX \= XX \= XX \= XXXXX \= XXXXXXXXXXXXXX \= X \kill
Word generated\_X174432(Word contIP) \\
\{ \\
   \> ... \\
   \> if(contIP == 0) \{ \\
   \>    \> {\xb if(timer) \{}             \> \> \> {\xb /* Ablauf Zeitscheibe testen */} \\
   \>    \>    \> {\xb saveTVMRegisters(0);}  \> \> {\xb /* TVM Register sichern */} \\
   \>    \>    \> {\xb schedule();}           \> \> {\xb /* Kontextwechsel einleiten */} \\
   \>    \> {\xb \}} \\
   \>    \> CHECK\_STACK\_OVERFLOW(9); \\
   \>    \> goto start; \\
   \> \} \\
   \> switch(contIP) \{ \\
   \>    \> case 7:  \> \> goto cont7; \\
   \>    \> default: \> \> return ILLEGAL\_CONT; \\
   \> \} \\
start: \\
   \> ... \\
{\xb cont7:} \\
   \> ... \\
   \> if(condition) goto jump21;        \> \> \> \> // Byteinstruktion CJ (cond. jump) \\
   \> ... \\
   \> {\xb if(timer) \{}                \> \> \> \> {\xb /* Ablauf Zeitscheibe testen */} \\
   \>    \> {\xb saveTVMRegisters(7);}     \> \> \> {\xb /* TVM Register sichern */} \\
   \>    \> {\xb schedule();}              \> \> \> {\xb /* Kontextwechsel einleiten */} \\
   \> {\xb \}} \\
   \> {\xb goto cont7;}                 \> \> \> \> // Byteinstruktion J (jump) \\
jump21: \\
   \> ... \\
   \> {\xs ret} \\
\}
\end{tabbing}}
\end{minipage}
\caption{Unterst"utzung von Kontextwechseln}
\label{Kontextwechsel}
\end{center}
\end{Beispiel}


\subsection{Ausnahmebehandlung}
\label{Abs. Ausnahmen}

Der dynamisch generierte Maschinencode arbeitet auf dem TVM-Stapelspeicher. Er belegt aber im Gegensatz zum Bytecode auch Speicherplatz auf dem vom Laufzeitsystem benutzten C-Stapelspeicher, auf dem z.B. R"ucksprungadressen und Prozessorregister gerettet werden. Durch dieses Verhalten tritt insbesondere bei der Behandlung von TL-Ausnahmen ein Problem auf, da diese den aktuellen Programmflu"s unterbrechen und an einer anderen, in den Ausnahmepaketen des TVM-Stapelspeichers spezifizierten Stelle, die nicht innerhalb der selben Funktion liegen mu"s, fortsetzen. Vom Maschinencode abgelegte Speicherworte k"onnen auf dem C-Stapel zur"uckbleiben und im weiteren Programmablauf zum Absturz des Systems f"uhren. Vor der Bearbeitung einer TL-Ausnahme m"ussen daher "uberz"ahlige Speicherworte entfernt und auf dem C-Stapelspeicher ein konsistenter Zustand hergestellt werden.

\newpage

Zur Verwirklichung dieser Aufgabe wird die in \cite{Math92} vorgestellte Ausnahmebehandlung auf C-Ebene verwendet. Sie bedient sich der Betriebssystemfunktionen \s{setjmp} und \s{longjmp}.
\begin{itemize}
\item \s{setjmp} sichert den Ausf"uhrungskontext eines Programms, d.h. die Prozessorregister und die Umgebung des Stapelspeichers, in eine Datenstruktur.
\item \s{longjmp} restauriert den von \s{setjmp} gesicherten Kontext und f"ahrt mit der Programmausf"uhrung so fort, als ob der Aufruf des vorangegangenen \s{setjmp} gerade erfolgt w"are. Ein Argument, das an \s{longjmp} "ubergeben und als Funktionsergebnis des \s{setjmp}-Aufrufs durchgereicht wird, erm"oglicht die Unterscheidung, ob ein Kontext gesichert oder wiederhergestellt wurde.
\end{itemize}
Mit diesen beiden Funktionen l"a"st sich eine vollwertige Ausnahmebehandlung realisieren, von welcher die in der Kontrollinstanz lokalisierte Steuerungsschleife (siehe Abschnitt~\ref{Abs. Integration}) gekapselt wird (Beispiel~\ref{Steuerschleife}).

\begin{Beispiel}[p]
\begin{center}
\begin{minipage}{0cm}
{\xr \begin{tabbing}
XX \= XX \= XX \= XX \= XXXXXXXXXXXXXXXXXXXXXXXXXXX \= X \kill
tsp\_Tagged globalControl(void) \\
\{ \\
   \> tsp\_OID oidCode; \\
   \> Word ipCode, rValue; \\
   \> cfun pFunction; \\
   \> ... \\
   \> loadTVMRegisters();                         \> \> \> \> /* Register aus Objekt- */ \\
   \> ...                                         \> \> \> \> /* speicher laden */ \\
   \> {\xb except\_TRY} \\
   \>    \> while(TRUE) \{ \\
   \>    \>    \> ... \\
   \>    \>    \> oidCode = activeFunction();           \> \> /* aktive Funktion laden */ \\
   \>    \>    \> ipCode = IP;                          \> \> /* Befehlsz"ahler laden */ \\
   \>    \>    \> ... \\
again: \\
   \>    \>    \> pFunction = lookup(oidCode);          \> \> /* Funktionszeiger laden */ \\
   \>    \>    \> rValue = (*pFunction)(ipCode);        \> \> /* Funktion aufrufen */ \\
   \>    \>    \> if(rValue == ILLEGAL\_CONT) \\
   \>    \>    \>    \> abort(); \\
   \>    \>    \> ... \\
   \>    \> \} \\
   \> {\xb except\_WHEN(exception\_TL) \{} \\
   \>    \> ... \\
   \>    \> SP = *(EP++);                            \> \> \> // Programmfortsetzung aus \\
   \>    \> FP = *(EP++);                            \> \> \> // dem Ausnahmepaket \\
   \>    \> IP = *(EP++);                            \> \> \> // ermitteln \\
   \>    \> ... \\
   \>    \> oidCode = activeFunction();              \> \> \> /* aktive Funktion laden */ \\
   \>    \> ipCode = IP;                             \> \> \> /* Befehlsz"ahler laden */ \\
   \>    \> goto again; \\
   \> {\xb \}} \\
   \> {\xb except\_WHEN(exception\_ESCAPE) \{} \\
   \>    \> oidCode = activeFunction(); \\
   \>    \> ipCode = IP = 0;  \\
   \>    \> goto again; \\
   \> {\xb \}} \\
   \> {\xb except\_END} \\
   \> ... \\
\}
\end{tabbing}}
\end{minipage}
\caption{Steuerschleife des dynamischen Codegenerators}
\label{Steuerschleife}
\end{center}
\end{Beispiel}

Die Steuerschleife \s{globalControl} wird f"ur jeden Thread einmal aufgerufen. Sie "uberwacht den TVM-Stapelspeicher und st"o"st, solange dieser nicht leer ist, die Ausf"uhrung der an den obersten Funktionsrahmen gebundenen Funktion an. Sie wird von den C-Makros \s{except\_TRY} und \s{except\_END} umschlossen. Das \s{TRY} Konstrukt sichert den aktuellen Ausf"uhrungskontext mittels \s{setjmp} und ist der Punkt, an dem die Programmausf"uhrung nach Ausl"osung einer Ausnahme wieder aufgenommen wird. Unterschiedliche Ausnahmen werden in den \s{except\_WHEN} Zweigen gezielt behandelt.

Der dynamische Codegenerator erzeugt aus der Byteinstruktion \s{RAISE}, die eine TL-Ausnahme einleitet, das Makro \s{except\_RAISE(exception\_TL)}, welches das System durch \s{longjmp} auf den gesicherten Kontext zur"ucksetzt. Die weitere Behandlung "ubernimmt der entsprechende \s{except\_WHEN} Zweig der Steuerschleife. Hier werden das oberste Paket vom Ausnahmestapel genommen, die TVM-Register neu initialisiert und anschlie"send zur"uck in die Schleife gesprungen.

Der Ausnahmemechanismus bietet zudem die M"oglichkeit, "uber das Laufzeitsystem in den Programmablauf einzugreifen. Es existieren Hilfsfunktionen, die Ausf"uhrungsrahmen auf dem TVM-Stapel anlegen, die TVM-Register manipulieren und die entsprechenden Funktionen durch Ausl"osung einer Ausnahme \s{exception\_ESCAPE} starten. Genutzt wird diese Funktionalit"at im TL-"Ubersetzer, der auf dem Tycoon-Toplevel eingegebene Ausdr"ucke direkt nach ihrer "Ubersetzung in Bytecode ausf"uhrt.


\section{M"ogliche Optimierungen des Codegenerators}
\label{Abs. Optimierung}

Die TVM ist eine virtuelle Maschine, deren Instruktionen "uber einem Stapelspeicher operieren. Diese Arbeitsweise orientiert sich nicht an der tats"achlich zugrundeliegenden Prozessorarchitektur und bietet daher Raum f"ur Optimierungen. Eine einfache Optimierungsm"oglichkeit ist die Eliminierung unn"otiger Stapelzugriffe. Sie wird in diesem Abschnitt an einem kleinen Beispiel schematisch dargestellt.

Die folgenden Zeilen zeigen die TVM-Assemblerdarstellung der TL Anweisung $\{x + 3\} * 2$.
{\xr \begin{tabbing}
XX\= XXXXXXXXXXXX \= X \kill  
  \> ldg x      \> // globale Konstante x auf den Stapel laden \\
  \> ldc 3      \> // Ganzzahl 3 auf den Stapel laden \\
  \> add        \> // Werte addieren und Ergebnis ablegen \\
  \> ldc 2      \> // Ganzzahl 2 auf den Stapel laden \\
  \> mul        \> // multipizieren
\end{tabbing}}
Die einfachste M"oglichkeit der Transformation in C-Quelltext ist die Erzeugung zu den Byteinstruktionen "aquivalenter C-Makros.  
{\xr \begin{tabbing}
XX\= XXXXXXXXXXXXXXXXXXXXXXXXX \= X \kill  
  \> push(tsp\_get(x));     \> // push(value)  Wert auf Stapel legen \\
  \> push(3);               \> // pop()        Wert von Stapel laden \\
  \> push(pop()+pop());     \> // tsp\_get(OID) Objekt aus Store laden \\
  \> push(2); \\
  \> push(pop()*pop());
\end{tabbing}}
Diese erste Variante ben"otigt zwar im Gegensatz zum Interpreter keine Befehlsdekodierung, enth"alt jedoch noch einige "uberfl"ussige und, da auf den Hauptspeicher zugreifend, kostentr"achtige Stapelzugriffe. Die Entfernung unn"otiger Speicherzugriffe und Zeigerarithmetik f"uhrt zu folgendem Code:  
{\xr \begin{tabbing}
XX\= X \kill
  \> push(tsp\_get(x)+3); \\
  \> push(pop()*2);
\end{tabbing}}
In einem letzten Schritt k"onnen die primitiven Operationen '\raisebox{1pt}{\small +}' und '\raisebox{-2.5pt}{*}' zusammengefa"st werden.
{\xr \begin{tabbing}
XX\= X \kill
  \> push((tsp\_get(x)+3)*2);
\end{tabbing}}
Dieses mit einem geringen Aufwand zu implementierende Verfahren ist nicht nur in der Lage, die Performanz zu erh"ohen, es reduziert auch die Gr"o"se des generierten Maschinencodes. 

Voraussetzung f"ur den erfolgreichen Einsatz dieser Optimierungsstrategie ist eine vorher im Compiler-Backend erfolgte Optimierung des Bytecodes. Arithmetische und logische Operationen werden vom TL-"Ubersetzer nicht direkt in die entsprechenden Byteinstruktionen "ubersetzt sondern "uber Basisfunktionen, welche die Instruktionen kapseln, angesprochen. Diese Funktionsaufrufe stellen eine Barriere f"ur die Optimierung dar und m"ussen durch die Funktionsexpansion (\e{inlining}) des dynamischen TML-Optimierers entfernt werden.

Weitergehende Optimierungen, wie in \cite{LL95,KEH91} beschrieben, die den sp"aten "Ubersetzungszeitpunkt und die damit verbundenen zus"atzlich verf"ugbaren Informationen, z.B. Funktionsargumente, ausnutzen, k"onnen nur eingeschr"ankt erfolgen. W"ahrend des "Ubersetzungsprozesses von TL "uber TML hin zu Bytecode gehen zu viele semantische Informationen, vor allem die dringend erforderlichen Typinformationen,  verloren.
