\psuSectionStart{{{{property(ITEM)}}}}{{{{n(block)}}}}\psuSectionStop{{{{property(ITEM)}}}}{{{{n(block,-)}}}}- Endgültiges Lowering auf Maschinencode
- Call-Frame und Call-Sequenzen
- Instruktionen als Snippets auswählen
- Spilling und Registerauswahl
- [Graphfärben]?
- Tooling
- Assembler
- ELF
- Dynamische Libraries
Effektive Programmierer: Effiziente Programmierer:
\subtitle{{{{subtitle()}}}}
\maketitleframe
\begin{frame}{Einordnung in die Vorlesung: Maschinencodeerzeugung}
\begin{center}
\includegraphics[page=8,width=0.9\linewidth]{fig/01-overview-small}
\end{center}
\bi
\ii Zwischencode der virtuellen Maschine auf eine \structure{reale Maschine} abbilden{%
\bi
\ii Verbleibende \alert{semantische Lücken}: Funktionsaufrufe, lokale Variablen, Befehle
\ii Application Binary Interface (ABI), Registervergabe, Binärformat (ELF)
\ei
}
\ei
\end{frame}
\begin{frame}[fragile,t]{Wo stehen wir? Wo wollen wir hin?}
\vspace{-1em}
\begin{columns}[t]
\begin{column}{0.49\textwidth}
\columntitle{Zwischencode-Maschine}
\vspace{-1em}
\btAnimation[width=0.7\textwidth]{center,raisebox,1:<1->}{fig/10-motivation}
\bii
\ii Speicherabstraktion\tikzmark{left-memory}{
\bi
\ii unendlich viele Parameter
\ii unendlich viele Variablen
\ei
}
\ii Befehle \tikzmark{left-befehle}{
\bi
\ii Meist 3-Adress-Befehle
\ii \ircmd{Call}: Beliebige Argumentanzahl
\ei
}
\ii Speicherung des Programms\tikzmark{left-program} {
\bi
\ii Objekte im Übersetzerzustand
\ii Basisblöcke sind ungeordnet
\ei
}
\eii
\end{column}\hfill
\begin{column}{0.49\textwidth}
\columntitle{Reale Maschine (z.B. IA-32)}
{\ttfamily\footnotesize
\def\OPB{\bfseries\let\OP\OPA}
\def\OPA{\mdseries\let\OP\OPB}
\let\OP\OPA
\renewcommand{\baselinestretch}{0.8}
\newcommand{\B}{{\let\kern\hskip\,}}
\begin{minipage}{1.0\linewidth}
\hspace{-1ex}\textbf{foo:}\\
\OP c8\B 0c\B 00\B 00\B%
\OP 8b\B 45\B 08\B%
\OP bb\B 03\B 00\B 00\B00\B%
\OP 01\B c3\B%
\OP 89\B 5d\B fc\B%
\OP b8\B 04\B 00\B 00\B 00\B%
\OP 0f\B af\B d8\B%
\OP 89\B 5d\B f8\B%
\OP b8\B 13\B 00\B 00\B 00\B%
\OP 50\B%
\OP 53\B%
\OP 8b\B 4d\B 08\B%
\OP 51\B%
\OP e8\B bb\B ff\B ff\B ff\B%
\OP 83\B c4\B 0c\B%
\OP 89\B 45\B f4\B%
\OP c9\B%
\OP c3\B%
\end{minipage}
}{\\[1ex]\scriptsize (Keine Sorge, wir gehen nur bis Assembler)}
\medskip
\bii
\ii \tikzmark{right-memory}Speicherabstraktion {
\bi
\ii 6 Ganzzahl-Register (32-Bit)
\ii Endlicher Speicher (ausreichend)
\ei
}\medskip
\ii \tikzmark{right-befehle}Befehle {
\bi
\ii 2 Operanden, zeitgleich Quelle+Ziel
\ii \ircmd{call} transportiert keine Argumente
\ii Verschiedene Adressierungsmodi
\ii Komplexe Befehle (CISC)
\ei
}\medskip
\ii \tikzmark{right-program}Speicherung des Programms {
\bi
\ii Binärformat des Betriebssystems
\ii Lineare Sequenz von Befehlen
\ei
}
\eii
\end{column}
\end{columns}
\only<handout:2-|2->{\AtBeginShipoutNext{%
\AtBeginShipoutUpperLeftForeground{%
\begin{tikzpicture}[remember picture, overlay]%
\draw[ultra thick,srared,->] ($(pic cs:left-befehle)+(up:3pt)$) -- ($(pic cs:right-befehle)+(-1pt,3pt)$);
\draw[ultra thick,srared,->] ($(pic cs:left-memory)+(up:3pt)$) --node[fill=white,draw,align=center,anchor=south east,pos=0.8,yshift=-2ex]{Wir verwenden IA-32\\als Beispiel} ($(pic cs:right-memory)+(-1pt,3pt)$);
\draw[ultra thick,srared,->] ($(pic cs:left-program)+(up:3pt)$) -- ($(pic cs:right-program)+(-1pt,3pt)$);
\end{tikzpicture}
}
}
}
\end{frame}In dem Teil der Veranstaltung “Programmiersprachen und Übersetzer”, der sich mit der technischen Seite, dem Übersetzerbau, beschäftigt, haben wir zunehmend darauf hingearbeitet, die semantische Lücke zwischen dem Text der Quellcodeebene und dem Programm der Maschinenebene zu schließen.
Schrittweise haben wir uns von Zeichen zu Tokens (Scanner), von Tokens zu Bäumen (Parsing), von Bäumen zu semantisch korrekten Bäumen (Semantische Analyse), und von abstrakten Syntaxbäumen zum Zwischencode (Codeerzeugung) bewegt.
Aber es fehlt noch ein letzter Schritt:
Wir müssen von der Ebene des Zwischencodes zur Ebene der real existierenden Maschine kommen.
Und da gibt es noch einige Unterschiede:
Wo die IR-Maschine beliebig viele Register hat, hat der Prozessor nur eine endliche Anzahl derer.
Wo die IR-Maschine Funktionsaufrufe mit Parameterübergabe beherrscht, gibt es auf dem physikalisch existierenden Prozessor nur einen call-Befehl, der mehr ein Sprung auf Steroiden ist.
Wo die IR-Maschine unspezifiziert ist, wie das Programm startet, müssen wir für die Ausführungsplattform ein passendes Binärformat erzeugen.
All diese verbleibenden Aspekte werden wir in die Vorlesung thematisieren.
Damit vollenden wir unsere Reise zur Schließung der semantischen Lücke, einer Reise, die man als 10.000 Abstraktionsebenen unter der Entwicklungsumgebung bezeichnen könnte.
Als Zielplattform, anhand derer wir die Maschinencodeerzeugung diskutieren werden, habe ich die IA-32 (32-Bit Intel Architektur) gewählt. Nicht, weil diese besonders hübsch oder zugänglich ist, sondern weil sie ein seit 40 Jahren stabiles Prozessorinterface bietet. Außerdem unterstützen alle Intel CPUs bis heute diesen 32-Bit Modus, auch wenn wir diese normalerweise im 64-Bit AMD64 Modus betreiben. Daher können Sie die Programme, die aus dem Übungsübersetzer fallen, wirklich ausführen und schrittweise im Debugger durchgehen. Dabei ist die Konzentration auf IA-32 kein Hindernis für die Verallgemeinerbarkeit der vorgestellten Techniken. Jede Abbildung des Zwischencodes auf eine reale Prozessorarchitektur muss die selben Probleme lösen, wie wir dies für IA-32 tun müssen. Oft fallen dabei Designentscheidungen anders aus, aber die Probleme bleiben die gleichen.
Das erste Problem, dessen wir uns annehmen müssen, ist, wie wir die Speicherabstraktion der IR-Maschine auf den Prozessor abbilden.
Unsere IR-Maschine ist mit einer sehr mächtigen Speicherabstraktion ausgestattet, weil wir dort zum einen symbolisch benannte Variablen (Register) haben, von denen wir unendlich viele besitzen können.
Außerdem gibt es die Befehle StackAlloc und HeapAlloc, die es uns erlauben, zusätzlichen Speicherplatz für Objekte anzufordern; es gibt also eine sehr rudimentäre Unterstützung für Objekte.
Reale Prozessoren sind deutlich eingeschränkter: Kein realer Prozessor hat unendlich viele Registern, sondern ihre Anzahl ist beschränkt. Der Speicher ist auch nicht so hübsch in Variablen und allozierte Objekte strukturiert, sondern wir arbeiten nur mit einer endlichen Anzahl an Speicherzellen, die wir über einen numerischen Index (== Zeiger) ansprechen können.
Zwischen beiden Welten bedarf es also einer Abbildungsfunktion.
Das zweite Problem sind die Befehle der IR-Maschine:
Wir haben uns den Zwischencode so definiert, dass die meisten Befehle 3 Operanden haben (Quadrupelschreibweise), wobei Quell- und Zieloperanden getrennt voneinander gewählt werden können.
Auf IA-32 haben wir diesen Luxus nicht, dort haben Befehle in der Regel 2 Operanden, wovon ein Operand eine doppelte Rolle hat und sowohl Quell- als auch Zieloperand ist.
Außerdem haben wir auf der IR-Ebene den Call-Befehl, der nicht nur eine Funktion aufruft, sondern auch, nebenbei, eine beliebige Anzahl an Argumenten als Parameter an die neue Funktionsinstanz übergeben kann, wo sie dann wie lokale Variablen verwendet werden können.
Das ist sehr schick, aber es wird von keiner realen Maschine unterstützt.
Das Attribut, bei dem Sie stutzig werden müssen, ist “beliebige Anzahl”, denn nichts auf einer realen Maschine hat eine beliebige Anzahl; immer gibt es irgendeine Art von oberer Schranke[fn::Am Ende besteht die Maschine eben doch aus einer endlichen Anzahl von Atomen, die nur eine endliche Anzahl von Taktzyklen betrieben werden kann, bevor Elektromigration alle Gates und Leitungen aufgefressen hat.
Oh Memento Mori!].
Auch hier brauchen wir für jeden IR-Befehl eine Abbildung auf einen IA-32-Befehl.
Das dritte Problem ist die Speicherung des Programms. Darüber haben wir uns bei der IR-Maschine überhaupt keine Gedanken gemacht. Die Befehle kamen einfach irgendwo her und wurden entlang des Kontrollflussgraphen abgearbeitet. IA-32 kennt aber Kontrollflussgraphen nicht als Dateiformat, sondern nur einen linearen Instruktionsstrom. Wir müssen unser übersetztes Programm so in eine Datei speichern, dass es vom Betriebssystem, als ein Prozess, in den Speicher geladen wird, wo es dann als Instruktionsstrom abgearbeitet werden kann. Wir schauen uns dazu an, wie das ELF-Binärformat für Linux aufgebaut ist und wie der erzeugte Assemblercode im Anschluss an die Übersetzung für die Ausführung vorbereitet wird.
Alles in allem: Machen Sie sich bereit, die letzte semantische Lücke zu schließen. Am Ende haben wir ein ausführbares Binärprogramm.
\dividerframe{Speicherabstraktion:\\Call-Frames}
\begin{frame}{Funktionsaufrufe auf Maschinenebene}
\btAnimation[width=0.8\textwidth]{center,1:<1->}{fig/10-call-terms}
\bi
\ii \structure{Funktionsaufruf}: Argumente werden als Parameter übertragen {
\bi
\ii IR-Ebene: Beliebig viele Parameter kommen \enquote{magisch} beim Callee an
\ii \textbf{Erinnerung}: Aufrufe erzeugen \alert{Funktionsinstanz mit eigenem Call-Frame}
\ii Call-Frame enthält Parameter, Rücksprungadresse und lokale Variablen
\ei
}\medskip
\ii<2-> Für die reale Maschine müssen wir einige \textbf{Entscheidungen} treffen:{%
\bi
\ii \structure{Datenlayout}: Welches Datum liegt an welcher Stelle?
\ii \structure{Verantwortung}: Wer legt den Call-Frame an und füllt ihn mit Daten?
\ii \structure{Invarianten}: \btSetTab Welche Teile des Maschinenzustandes bleiben über einen\\
\btUseTab Funktionsaufruf hinweg erhalten?\\[1ex]
\ii[$\Rightarrow$] Die Antworten hierauf ergeben die \structure{Aufrufkonvention}.
\ei
}
\ei
\end{frame}
\begin{frame}[fragile]{Aufrufkonventionen}
\begin{btBlock}{Definition: Die Aufruf\textbf{konvention} bestimmt,\ldots}
\ldots wie \structure{Argumente} an Funktionen übergeben werden und\\
\ldots welche Teile des \structure{Maschinenzustands} der Callee erhalten muss und\\
\ldots wo der Caller den \structure{Rückgabewert} auslesen kann.
\end{btBlock}
\bi
\ii Das Betriebssystem und Übersetzer bestimmen die Aufrufkonvention {
\bi
\ii Funktionen können unabhängig voneinander übersetzt werden.
\ii Interoperabilität zwischen verschiedenen Übersetzern und Sprachen
\ei
}\medskip
\ii<2-> Beispiel: Sys-V Calling Convention für C auf IA-32/GNU Linux{
\bi
\ii Callee legt Call-Frame auf dem Stack an und räumt ihn wieder weg
\ii Argumente werden von \textbf{rechts-nach-links} auf den Stack gelegt
\ii Rückgabewerte: \btSetTab \texttt{\%eax} für \lstinline[style=C]{int}, \texttt{\%st0} für \lstinline[style=C]{double}\\
\btUseTab Größere Argumente/Rückgabewerte wie in Vorlesung 8
\ii \structure{Callee-saved Register}: \texttt{\%esp, \%ebp, \%ebx, \%esi, \%edi}
\ei
}
\ei
\medskip
\uncover<3->{Andere Konvention (auf IA-32): \btSetTab syscall, optlink, pascal, stdcall, fastcall,\\
\btUseTab vectorcall, safecall, thiscall, \ldots}
\end{frame}Der erste Schritt, über den wir uns bei der Transformation von IR-Code zu Maschinencode Gedanken machen werden, sind Funktionsaufrufe.
Anhand dieser Funktionsaufrufe lernen wir nicht nur, wie Argumente transportiert werden, sondern auch, wie lokale Variablen im Call-Frame abgelegt werden.
Dazu wollen wir uns aber zunächst in Erinnerung rufen, was der IR-Befehl Call genau getan hat.
Der erste Operand von Call war der Name der Funktion, die der Aufrufer (Caller) aktivieren will (Callee).
Die restlichen (beliebig viele) Operanden sind die Argumente, die vom Caller zum Callee übertragen werden (Datenfluss A).
Für jeden Funktionsaufruf entsteht eine neue Funktionsinstanz, die wir mit eigenen lokalen Variablen ausstatten, die im Call-Frame gespeichert werden.
Zusätzlich wird im Call-Frame auch noch eine Rücksprungadresse gespeichert, die angibt, an welche Codestelle im Caller wir beim Return-Befehl zurückkehren.
Mit der Rückkehr kann, über den Rückgabewert, ein zweiter Datenfluss (R) stattfinden.
Zentral bei der Abbildung auf die Maschine ist der Call-Frame. Für diesen stellt sich die Frage nach dem Datenlayout. Ähnlich wie bei Record-Typen müssen wir uns auf ein konkretes Abbild im Speicher festlegen. Nur so können wir die Verwendung von symbolischen Namen effizient auf die zeigerbasierte Adressierung der Maschine abbilden. Darüber hinaus müssen wir die Entscheidung über den Besitzer{{{see(06-ownership,Besitz von Objekten)}}} des Call-Frames treffen: Wer erzeugt den Call-Frame und wer löscht ihn wieder? Caller oder Callee? Außerdem müssen wir uns darauf festlegen, was der Callee am Maschinenzustand überhaupt verändern darf. Darf der Callee den gesamten Speicher mit Nullen überschreiben (eher nicht nützlich), oder darf der Caller annehmen, dass einige Teile des Maschinenzustands unverändert bleiben.
Wie Sie bereits sehen, ich spreche hier häufig davon, dass wir uns festlegen müssen. Diese Entscheidungen, die wir bei der Abbildung von Funktionsaufrufen und dem Call-Frame machen, sind nicht zwingend, sondern es sind Designentscheidungen. Es sind Konventionen, an die sich sowohl Caller als auch Callee halten, um miteinander arbeiten zu können. Daher heißen diese Designentscheidungen auch Aufrufkonventionen.
Eine Aufrufkonvention regelt, im Kern, drei Dinge: Zum einen wird geregelt, wie Operanden von Caller zum Callee kommen. Dabei legt der Caller die Operanden an fest definierte Orte in der Maschine (z.B. auf den Stack oder ins Register) und der Callee verlässt sich darauf, an genau diesen Stellen die Argumente zu finden. In der Rückrichtung verhält es sich mit dem Rückgabewert: Der Callee legt sein Berechnungsergebnis an eine vordefinierte Stelle in der Maschine, wo sie der Caller wieder auslesen kann.
Das Dritte, was eine Aufrufkonvention regelt, ist der Maschinenzustand, der über einen Funktionsaufruf hinaus unberührt bleibt.
Wir haben schon häufiger davon gesprochen, dass wir Funktionsaufrufe als Komplexoperationen ansehen können, mit denen der Befehlssatz erweitert wird.
Die Aufrufkonvention beschreibt dann, welche Seiteneffekte eine solche Call-Komplexoperation auf den Maschinenzustand hat.
Eine mögliche Regel könnte zum Beispiel sein: Der Callee darf nur das Register eax, seinen eigenen Call-Frame, und alle über Zeiger erreichbare Speicherzellen verändern.
Aufrufkonventionen dienen dazu Kompatibilität zu schaffen. Zum einen kann ein Übersetzer so Funktionen unabhängig voneinander zu Maschinencode übersetzen, da die Regeln für Funktionsaufrufe überall gleich sind. Dies funktioniert sogar, wenn wir den Übersetzer auf mehreren Quelldateien ausführen, um eine separate Übersetzung durchzuführen (dazu später mehr). Aber eine Aufrufkonvention fördert auch die Kompatibilität zwischen verschiedenen Übersetzern, und sogar zwischen unterschiedlichen Programmiersprachen. So ist die Aufrufkonvention für C-Funktionen auf den meisten Plattformen die Lingua Franca, um Funktionen aus anderen Programmiersprachen aufzurufen.
Als Beispiel werden wir uns im Folgenden der System-V Aufrufkonvention für C auf der IA-32 Plattform beschäftigen.
Diese können Sie genauer im Spezifikationsdokument ab Seite 35 nachlesen.
Keine Angst, die Spezifikation ist sehr klar und, wenn Sie mit dieser Vorlesungseinheit durch sind, gut zu verstehen.
Bei dieser Konvention werden die Argumente von rechts nach links auf den Stack gelegt, was dazu führt, dass das erste Argument zu oberst auf dem Stack liegt. Wir werden gleich sehen, welchen Vorteil diese Entscheidung bei Funktionen mit einer variablen Anzahl an Argumenten hat (z.B. printf()).
Außerdem regelt die Aufrufkonvention, dass Rückgabewerte vom Typ int in %eax und Fließkommazahlen in %st0 gespeichert werden.
Bezüglich des unveränderten Maschinenzustands regelt die System-V Aufrufkonvention, dass fünf Register (%esp, %ebp, %ebx, %esi, %edi) nach einem Funktionsaufruf den gleichen Zustand haben müssen, wie vor dem Funktionsaufruf. Die Callee-saved Register werden vom Callee gespeichert und am Ende wiederhergestellt.
Da Konventionen nur Konventionen sind, gibt es natürlich verschiedene Aufrufkonventionen[fn::siehe xkcd: Competing Standard]. So verwendet Windows im selben Programm für normale Funktionsaufrufe die fastcall-Konvention und die Pascal-Konvention für Systemaufrufe.
\begin{frame}{Call-Frame auf IA-32/Linux}
\begin{columns}
\begin{column}{0.4\textwidth}
\btAnimation[width=\textwidth]{range=1-7:<1->}{fig/10-stack}%
\btAnimation[width=\textwidth]{5:<8>,4:<9>,1:<10>}{fig/10-stack}
\end{column}\hfill
\begin{column}{0.6\textwidth}
\bii
\ii Auf der IA-32 Plattform wächst der Stack von den hohen zu den niedrigen Adressen
\ii Der \structure{Stackpointer} ist in \texttt{\%esp}
\eii
\medskip
\columntitle{Aufrufsequenz}
\bi\ii[]\be
\ii<handout:2-|2-> Argumente von \textbf{rechts nach links} ermöglicht Funktionen mit variabler Argumentanzahl {
\bi
\ii \texttt{\texttt{push arg2}; \only<3->{\texttt{push arg1}; }\only<4->{\texttt{push arg0};}}
\ei
}
\ii<handout:5-|5-> CPU legt Rücksprungadresse auf den Stack{
\bi
\ii \texttt{call bar}
\ei
}
\ii<handout:7-|7-> Konstante Offsets durch Basiszeiger{
\bi
\ii \texttt{push \%ebp; mov \%esp, \%ebp;}
\ei
}
\ii<handout:6-|6-> Callee kann Raum für lokale Daten anlegen{
\bi
\ii sub x, \%esp
\ei
}
\ii<handout:8-|8-> Return in umgekehrter Reihenfolge
\ee\ei
\end{column}
\end{columns}
\end{frame}Betrachten wir die Situation eines Funktionsaufrufs und die Erzeugung des Call-Frames auf IA-32 noch einmal genauer.
Basis für diese Betrachtung ist, dass der Stack auf IA-32 von den hohen zu den niedrigen Adressen wächst, was sich in Maschinenbefehlen wie push und pop niederschlägt.
Außerdem wird im Register %esp der Stackzeiger gespeichert, der als impliziter Quell- und Zieloperand für push/pop dient.
Wir starten unsere Betrachtung im Caller, der eine Funktion mit 3 Parametern aufrufen wird.
Um diesen Aufruf zu tätigen, führt der Caller die sogenannte Aufrufsequenz durch.
Die Aufrufsequenz sind jene Maschinenbefehle, die auf Seiten des Callers den Funktionsaufruf vorbereiten und durchführen.
Der erste Schritt der Aufrufsequenz ist das Speichern der Argumente auf den Stack.
Dabei legen wir die Argumente von rechts nach links auf den Stack.
Achten Sie bei der Animation auf den linken und den rechten Rand des Stacks.
Auf der linken Seite sehen wir, wie der Stackzeiger mit jedem Argument nach unten wandert, da er immer auf das oberste Element des Stacks zeigt.
Auf der rechten Seite habe ich notiert, wie wir zu jedem Zeitpunkt auf das jeweilige Argument relativ zum Stackzeiger zugreifen könnten.
Nachdem alle drei Argumente auf dem Stack liegen, können wir auf den Wert von arg2 mit einem relativen Offset von 8 (8(%esp) == %esp + 8) zugreifen.
Dieser relative Zugriff ist von großer Bedeutung, weil der Stackzeiger (und später der Basiszeiger) der Anker ist, an dem wir den Call-Frame festhalten können. Über die relativen und konstanten (!) Offsets können wir dann auf die einzelnen Felder des Call-Frames zugreifen. Dieses Vorgehen ist dem Vorgehen für Records sehr ähnlich: Auch dort gab es einen Zeiger, an dem wir das Objekt festgehalten haben und relative Offsets, die wir mit dem Datenlayout festgelegt haben. Genauso verhält es sich bei Call-Frames.
In den relativen Offsets liegt auch der Grund, wieso die Argumente von rechts nach links auf den Stack gelegt werden:
Stellen Sie sich vor, dass unsere Funktion nicht nur 3 Parameter hat, sondern noch viel mehr, im schlimmsten Fall sogar eine variable Anzahl.
Diese würden unter arg2 liegen und sie hätten keinen Einfluss auf die relativen Offsets für die ersten 3 Argumente.
Der Callee kann also auf die ersten Argumente zugreifen, ohne zu wissen, wie viele Argumente noch kommen.
Überlegen Sie sich dazu, mit welchem Offset das erste Argument von ~printf()~[fn::int printf(const char *format, …)]
relativ zum Stackzeiger gespeichert ist.
Da mit diesem ersten Argument format gespeichert ist, wie viele Argumente noch zu erwarten sind, kann die Implementierung die restlichen Offsets dynamisch berechnen.
Wenn sie diesen Mechanismus noch genauer verstehen möchten, schauen Sie sich die Manpage va_arg(3) an.
Nachdem die Argumente auf dem Stack liegen, wird der Maschinenbefehl call ausgeführt, der die Rücksprungadresse auf den Stack legt und den Kontrollfluss zum Callee umleitet.
Durch die Rücksprungadresse können wir später den Kontrollfluss des Callers wieder aufnehmen.
Da die Kontrolle über die Maschine nun beim Callee liegt, kann dieser den Rest des Call-Frames anlegen, indem der Stackpointer noch weiter nach unten verschoben wird.
In diesem Zwischenbereich (gelb) werden dann die lokalen Variablen abgelegt.
Wie Sie sehen, habe ich in der Animation keine feste Größe für diesen Bereich angegeben, sondern erst mal die Zahl x.
Solange eine Funktion nur lokale Variablen hat, aber niemals eine dynamische Stackallokation (StackAlloc) durchführt, ist der gelbe Bereich von bekannter Größe und die Zahl x eine Konstante. In diesem Fall können wir weiterhin über einen konstanten Stackzeiger-Offset auf die Argumente zugreifen. Hätte unsere Funktion beispielsweise 3 lokale Variablen à 4 Byte, würden wir mit 24(%esp) an arg2 kommen.
Problematisch wird es, wenn der gelbe Bereich von unbekannter Größe ist.
In diesem Fall brauchen wir einen zweiten Zeiger, der in die Mitte des Call-Frames zeigt, sodass die Parameter weiterhin über konstante Offsets erreicht werden können.
Dieser Zeiger heißt Basiszeiger und wird auf IA-32 in %ebp gespeichert.
Es heißt deswegen Basiszeiger, weil er eigentlich an die Basis des Call-Frames zeigt, die viele Autoren am Beginn des gelben Bereichs verorten.
Für diese Autoren beginnt der Call-Frame erst mit den lokalen Variablen und die Argumente gehören noch zum Call-Frame des Aufrufers.
Da ich es aber unlogisch finde, dass Parameter und lokale Variablen einer Funktionsinstanz in unterschiedlichen Call-Frames liegen, definieren wir den Call-Frame in dieser Veranstaltung so, dass er sowohl Parameter und lokale Variablen überdeckt.
Verwendet man einen Basiszeiger, so muss der ursprüngliche Wert dieses Registers gesichert (und am Ende wiederhergestellt) werden. Schließlich gehört %ebp zu den Callee-Save Registern.
Am Ende der Funktion baut der Callee seinen Anteil des Call-Frames wieder ab und gibt die Kontrolle mit dem ret-Maschinenbefehl an den Caller zurück.
Dieser entfernt dann wieder die Parameter vom Stack und fährt mit seinem Kontrollfluss, nun um den Rückgabewert reicher, fort.
\begin{frame}{Unterschiede der Aufrufkonventionen}
\bi
\ii Übergabe von \structure{Argumenten in Registern} {
\bi
\ii Die ersten N Argumente können in Registern übergeben werden
\ii Spart Speicherzugriffe beim Funktionsaufruf
\ei
}\bigskip
\ii<2-> \textbf{Trade-Off} zwischen Caller-save/Callee-save Registermengen {
\bi
\ii Wenige Caller-save Register: wenig unnötige Registersicherungen
\ii Wenige Callee-save Register: Blattfunktionen können in Registern arbeiten
\ei
}\bigskip
\ii<3-> Zusätzliche Parameter liefern Aufrufkontext {
\bi
\ii \textbf{thiscall}: In C++ wird der this-Zeiger in \texttt{\%ecx} übergeben
\ii Zieladresse für Rückgabeobjekte im 0. Parameter
\ei
}
\ei
\end{frame}Ich möchte noch ganz kurz darauf eingehen, in welchen Aspekten sich Aufrufkonventionen unterscheiden können. Da auf aktuellen Plattformen Speicherzugriffe langsamer sind als Registerzugriffe, werden bei neueren Aufrufkonventionen die ersten Argumente nicht über den Speicher, sondern über die Register übergeben. Dies ist eine Optimierung, die insbesondere bei Funktionen mit weniger Argumenten, was die meisten Funktionen sind, die Anzahl der Speicheroperationen erheblich einschränkt.
Eine andere Designentscheidung für Aufrufkonventionen ist die Anzahl der Callee-Save Register. Umso mehr Register als Callee-Save angenommen werden, desto mehr Sicherungsoperationen können wir uns auf Seiten des Aufrufers sparen, da diese beim Callee gesichert werden. Andersherum, bei weniger Callee-save Registern haben Funktionen, insbesondere Blattfunktionen, mehr Register zur Verfügung, die ohne Sicherung verwendet werden können. Das grundlegende Problem ist, dass der Caller nicht weiß, welche Register der Callee tatsächlich verwenden wird, und der Callee nicht weiß, welche Register sein Caller in der Zukunft noch verwenden will. Deshalb suchen Aufrufkonventionen nach einem Trade-Off zwischen keine Callee-save Register und ausschließlich Callee-save Registern, der dieses gegenseitige Nicht-Kennen ausgleicht. Meist kümmert sich sowohl Caller als auch Callee um etwa die Sicherung des halben Registersatzes.
Der dritte Aspekt, der ebenfalls in Aufrufkonventionen geregelt ist, sind zusätzliche, nicht sichtbare Register.
So wird beim thiscall (C++) der Zeiger auf das Objekt, auf dem eine Methode ausgeführt werden soll, im Register %ecx übergeben. Über solche zusätzlichen Argumente haben wir allerdings schon im Kapitel zur Codeerzeugung ausführlich geredet{{{see(08-codegen-records, Codeerzeugung für Records)}}}.
\begin{frame}[fragile]{Lokale Variablen}
\begin{btBlock}{Die Welt am Beginn einer Funktion\hfill Parameter: \checkmark}\small
\begin{columns}
\begin{column}{0.7\textwidth}
Nach der Sicherung des \alert{alten Basiszeigers}, sind die Parameter mit einem \structure{konstanten, positiven Offset} zum \advantage{neuen Basiszeiger} adressierbar. \end{column}\hfill \hspace{-3ex}\begin{column}{0.3\textwidth}\ttfamily bar:\\ \ \alert{push \%ebp}\\ \ \advantage{mov \%esp, \%ebp}\\ \ mov \structure{8(\%ebp)}, \%eax \end{column} \end{columns} \end{btBlock}
\bi
\ii<2-> Unendlicher virtueller Registersatz (IR) vs. endlicher realer Registersatz{
\bi
\ii IR-Variablen müssen auf Speicherstellen im Call-Frame abgebildet werden
\ii Einfachste Variante: Jede Variable $\rightarrow$ ein \structure{Slot} im Call-Frame{\\[1ex]
\begin{columns}
\hfill\begin{column}{0.7\textwidth}
\begin{code}[tag=Python]
\begin{py}
for idx, var in enumerate(function.variables):
var.slot = idx
var.ebp_offset = -4 + (-4 * idx)
\end{py}
\end{code}
\end{column}\hfill
\end{columns}\mbox{}\\[1ex]
}
\ii Variablenslots werden relativ zum Basiszeiger adressiert
\ei
}\medskip
\ii<3-> Komplexer: Colocation von Variablen in Slots + kluge \structure{Registerallokation}
\ei
\end{frame}
Die Aufrufkonvention legt fest, welche Argumente über den Speicher im Call-Frame und welche in Registern übergeben werden. Daher wissen wir nun, wie der Maschinenzustand aussieht, bevor die erste Instruktion unserer Funktion ausgeführt wird. Nachdem wir dort den alten Basiszeiger gesichert und einen neuen etabliert haben, können wir mit konstanten Offsets auf die Parameter zugreifen. Aber es fehlt noch etwas essentielles: Wie bilden wir die lokalen Variablen auf den Speicher ab? Diesen (gelben) Teil habe ich bisher absichtlich ausgelassen, um jetzt genauer darauf einzugehen.
Das Problem ist, dass es (meist) mehr lokale Variablen in einer IR-Funktion gibt als der Registersatz der Maschine Plätze vorsieht. So bleiben bei IA-32 noch 6 “General-Purpose Register” über, in denen wir Werte speichern können, nachdem wir Stackzeiger und Basiszeiger abgezogen haben. Für alle Funktionen, die nur 6 IR-Variablen haben, können wir also eine 1:1 Abbildung vornehmen und brauchen keinen Stackspeicher vorsehen. Aber wie oft trifft das schon ein, nur 6 Variablen?
Daher müssen wir den Call-Frame als zusätzlichen Zustandsspeicher für die Funktionsinstanz auffassen. Dazu legen wir am Beginn der Funktion eine gewisse Anzahl an Speicherslots an, in denen wir Variablenwerte zwischenspeichern können, wenn sie gerade nicht in Register liegen. Wir können dann Werte zwischen Registern und Speicherslots hin und her verschieben.
Bei der einfachsten Variante diese Abbildung von IR-Variablen durchzuführen, legen wir für jede Variable einen festen Slot an, der fix mit dieser IR-Variable verbunden ist. Durch diese fixe Zuordnung zwischen IR-Variable und Stack-Slot können wir für jede Variable einen konstanten Basiszeiger-Offset angeben, mit dem wir den zugehörigen Slot adressieren können.
Ich möchte hier noch einmal ganz deutlich machen, dass es einen kategorischen Unterschied zwischen Variable und Stack-Slot gibt:
Variablen sind ein Konzept der IR-Ebene und so auf der Maschinenebene so nicht vorhanden.
Slots dagegen sind auf der Maschinenebene vorhanden, da wir auf eine konkrete Speicherzelle zeigen können und sagen:
“Das ist der Stack-Slot 3 im Call-Frame zu einer Funktionsinstanz von bar()”.
Wie ist aber das Verhältnis von Variable zu Slot (in unserer fixen Zuordnung)?
Man kann es sich bildlich so vorstellen, dass die Variable ein Geist ist, der entweder gerade in einem Register oder in einem Stack-Slot lebt.
Zu jedem Zeitpunkt kann dieser Geist nur in einem dieser beiden Orte leben, denn entweder enthält ein Register den aktuellen Wert der Variable oder ein Stack-Slot.
Im Fall eines etwas komplexeren Übersetzers ist die Zuordnung von Variable an Stack-Slots nicht so fix wie in unserer einfachen Variante. In diesen Fällen kann eine Variable an unterschiedlichen Punkten in einer Funktion in verschiedenen Slots leben und mehrere Variablen können sich einen Slot teilen. Auf diese Weise kann ein Übersetzer den Speicherverbrauch minimieren, was, durch weniger Druck auf den Cache, auch zu einer schnelleren Ausführung führt.
\dividerframe{Befehlsauswahl\\und\\Registerallokation}
\begin{frame}{Übersetzung des IR-Programms}
\vspace{-2em}
\begin{columns}[t]
\begin{column}{0.49\textwidth}
\begin{btBlock}{\hfill Befehlsauswahl\tikzmark{A}\hfill\mbox{}}
Wähle für jeden IR-Befehl eine einzelne oder eine Sequenz aus Maschinenbefehlen aus.
\end{btBlock}
\bii
\ii<2-> Abbildung meist nicht eindeutig {\\[1ex]
\enquote{AMD64 kennt 36 \texttt{mov}-Varianten}\\[1ex]
\bi
\ii Unterschiedliche Programmgröße
\ii Unterschiedliche Laufzeit
\ii Unterschiedlicher Energieverbrauch
\ei
}\medskip
\ii<2-> Betrachtung mehrerer IR-Befehle verbessert die Befehlsauswahl
\eii
\end{column}\hfill
\begin{column}{0.49\textwidth}
\begin{btBlock}{\hfill\tikzmark{B}Registerallokation\hfill\mbox{}}
Bestimme, in welchen Abschnitten eine IR-Variable in ihrem Slot oder in einem CPU-Register lebt.
\end{btBlock}
\bii
\ii<3-> Problem bei \#Variablen$>$\#Register
\ii<3-> Konsistent für alle Kontrollflüsse
\ii<3-> Massive Performance-Auswirkung {
\bi
\ii CPU-Register: \hspace{1em}\btSetTab 1 Zyklus
\ii L1-Cache (Hit): \btUseTab 4 Zyklen
\ii L2-Cache (Hit): \btUseTab 10 Zyklen
\ii Speicher: \btUseTab 60-100 Zyklen
\ei
}
\eii
\end{column}
\end{columns}
\begin{columns}
\begin{column}<2->{0.49\textwidth}
\bii
\ii[$\Rightarrow$] Für sich: \ALERT{NP-vollständig}
\eii
\end{column}\hfill
\begin{column}<3->{0.49\textwidth}
\bii
\ii[$\Rightarrow$] Für sich: \ALERT{NP-vollständig}
\eii
\end{column}
\end{columns}
\bigskip
\uncover<4->{\hspace{-1em}\ALERT{Alles noch schlimmer}: Befehlsauswahl und Registerallokation beeinflussen sich gegenseitig und sind Abhängig von der CPU-Mikroarchitektur.}
\only<4>{\AtBeginShipoutNext{%
\AtBeginShipoutUpperLeftForeground{%
\begin{tikzpicture}[remember picture, overlay]%
\draw[ultra thick,srared,<->] ($(pic cs:A)+(up:3pt)$) -- node[above]{Interaktion}($(pic cs:B)+(-1pt,3pt)$);
\end{tikzpicture}
}
}
}
\end{frame}Nachdem durch die Aufrufkonvention und die Abbildung von IR-Variablen auf Stack-Slots klar ist, wie das Datenlayout für einen Call-Frame aussieht, geht es nun darum, die IR-Befehle als Maschinenbefehle zu codieren. Dazu müssen zwei Entscheidungen getroffen werden: Bei der Befehlsauswahl wird für einen IR-Befehl ein einzelner oder eine Sequenz von Maschinenbefehlen ausgewählt. Bei der Registerallokation entscheiden wir, zu welchem Zeitpunkt eine Variable in ihrem Slot lebt und wann sie in einem CPU-Register zu finden ist. Haben wir beide Probleme gelöst, können wir die Maschinenbefehle zusammen mit den passenden Registeroperanden als Assembler rausschreiben und sind fertig mit der Übersetzung. Also eigentlich ganz einfach, wären da nicht zwei NP-vollständige Probleme.
Zum einen ist die Befehlsauswahl nicht so einfach:
Viele Prozessoren, insbesondere CISC-Architekturen, haben viele Varianten eines einzelnen Befehls, die sich alle, mehr oder weniger stark, in ihrer Semantik und in ihren nicht-funktionalen Eigenschaften unterscheiden.
So kennt die AMD64-Architektur 36 verschiedene Varianten von mov, die im Assembler alle mit dem mov-Opcode notiert werden.
Außerdem ist nicht für jeden IR-Befehl eine 1:1 Abbildung möglich, sondern es wird eine 1:N Abbildung auf Maschinenbefehle benötigt, um die geforderte Funktionalität umzusetzen.
Das ganze wird noch schlimmer, weil die Betrachtung mehrerer IR-Befehle in einer M:N Weise zu besseren Übersetzungsergebnissen führt.
Alles in allem hat sich herausgestellt, dass eine optimale Befehlsauswahl ein NP-vollständiges Problem ist.
Zum anderen ist auch die Registerallokation ein Problem: Die Entscheidung, welche Variable zu welchem Zeitpunkt in welchem Register lebt, hat zum einen massive Auswirkungen auf die Performance des Programms. Dies rührt daher, dass Zugriffe auf den Speicher viel, viel langsamer sind als auf Register[fn::siehe: Your computer is already a distributed system. Why isn’t your OS?][fn::Zugriffszeiten von Stackoverflow.]. Daher kostet jeder Transfer zwischen Stack-Slot und Register richtig viel Zeit und wir möchten während der Laufzeit möglichst wenige Slot-Register-Transfers haben. Aber Registerallokation ist auch ein kompliziertes Problem, wenn man Variablen über Basisblockgrenzen hinweg im Register halten möchte. Erwartet der Code eines Basisblocks zum Beispiel eine Variable in einem bestimmten Register, so müssen alle Vorgängerblöcke dafür sorgen, dass die Variable auch tatsächlich in diesem Register geladen ist. Da der CFG im Allgemeinen aber weder linear noch azyklisch ist, haben wir es hier mit einer zyklischen Rückkopplung solcher Bedingungen zu tun. Alles in allem hat sich herausgestellt, dass eine optimale Registerallokation ein NP-vollständiges Problem ist.
Aber das ganze wird noch schlimmer, da Befehlsauswahl und Registerallokation miteinander interagieren: Nicht jede Befehlssequenz, die die Befehlsauswahl in Betracht zieht, braucht gleich Register. Und nicht jeder Maschinenbefehl kann mit jedem Register aufgerufen werden. Außerdem gibt es auch noch Befehle, die als Seiteneffekt den Inhalt von Registern verändern. Alles in allem: Die Kombination aus Registerallokation und Befehlsauswahl ist ein richtig richtig dickes Brett.
\begin{frame}{Minimale Maschinencodeerzeugung}
\vspace{-1em}
\begin{btBlock}{}
Wenn alles zu kompliziert ist, überlegt man sich den einfachsten Basisfall.
\end{btBlock}
\medskip
\begin{columns}
\begin{column}{0.6\textwidth}
\bi
\ii \structure{Befehlsauswahl}: Makroexpansion {
\bi
\ii<handout:2-|2-> Jeder IR-Befehl wird zu einer festen Assembler-Sequenz
\ii<handout:2-|2-> Platzhalter für Registeroperanden
\ii<handout:3-|3-> Zusätzliche Anweisungen wo und wie die Operanden vorliegen müssen
\ii<handout:4-|4-> Muster für jede Instruktion instantiieren
\ei
}\medskip
\ii \structure{Registerallokation}: Spilling {
\bi
\ii<handout:5-|5-> \structure{Spilling}: Variablenwert aus einem Register in den Speicher schreiben.\\[1ex]
\ii<handout:5-|5-> Variablen immer neuladen
\ii<handout:5-|5-> Ergebnisse direkt spillen
\ii<handout:6-|6-> Jede Variable hat einen Speicherslot
\ei
}
\ei
\end{column}\hfill
\begin{column}{0.4\textwidth}
{ \btAnimation[width=0.6\textwidth]{center,padding,1:<1->}{fig/10-operation-selection}
\Large $\Downarrow$
\medskip
}
\uncover<handout:2-|2->{\btAnimation[width=0.8\textwidth]{center,padding,2:<1>,range=2-6:<2->}{fig/10-operation-selection}}
\end{column}
\end{columns}
\end{frame}
\tikzset{solution/.style={
inner xsep=2em,fill=white,
fill opacity=0.8,
label={[draw=safegreen, thick, minimum width=8cm,fill=white]center:{\Large\advantage{\textbf{#1}}}}
}
}
\begin{frame}[fragile]{Probleme der Minimallösung}
\textbf{3 Probleme}: \ALERT{\uncover<2->{Ineffizient}\uncover<3->{, Ineffizient}\uncover<4->{, Ineffizient.}}
\bigskip
\begin{tikznodeenv}[name=A]\begin{minipage}{\textwidth}
\bi
\ii<4-> Ständig werden Register, völlig ohne Not, \alert{gesichert und geladen}{
\begin{columns}
\begin{column}{0.75\textwidth}
\btUseExtraItemSep[-\smallskipamount]\vspace{-1em}%
\bi
\ii In Registern vorgeladene Variablen werden verworfen
\ii Hauptteil des Programms macht nur noch Spilling
\ii Speicherzugriffe sind, trotz Cache, langsamer
\ei
\end{column}\hfill
\begin{column}{0.25\textwidth}
\begin{code}[]
\begin{asm}[style=smaller]
...
mov %ebx, -8(%ebp)
\end{asm}
\vspace{1pt}\hrule\vspace{1pt}
\begin{asm}[style=smaller]
mov -8(%ebp), %eax
...
\end{asm}
\end{code}
\end{column}
\end{columns}
}
\ei
\end{minipage}\end{tikznodeenv}
\begin{tikznodeenv}[name=B]\begin{minipage}{\textwidth}
\bi
\ii<5-> Starre Ersetzungsmuster nutzen \alert{komplexe CPU Befehle} nicht{
\begin{columns}
\begin{column}{0.7\textwidth}
\btUseExtraItemSep[-\smallskipamount]\vspace{-1em}%
\bi
\ii Besonders bei CISC sind Befehle oft sehr mächtig
\ii IR-Ops sind absichtlich einfach und HW-unabhängig
\ii Ein Befehl überdeckt mehrere IR-Befehle
\ei
\end{column}\hfill
\begin{column}{0.30\textwidth}
\begin{code}[]
\begin{asm}[style=smaller]
imul %ebx, 8
add %eax, %ebx
mov (%ebx), %eax
\end{asm}
\end{code}%
\vspace{2pt}%
\begin{code}
\begin{asm}[style=smaller]
mov (%eax,%ebx,8), %eax
\end{asm}
\end{code}
\end{column}
\end{columns}
}
\ei
\end{minipage}\end{tikznodeenv}
\begin{tikznodeenv}[name=C]\begin{minipage}{\textwidth}
\bi
\ii<6-> Starre Befehlsreihenfolgen \alert{ignorieren moderne Mikroarchitekturen}{
\bi
\ii Moderne Prozessoren arbeiten Pipelined, Out-of-Order und Superskalar
\ii Befehle können im \enquote{Windschatten} anderer Befehle ausgeführt werden
\ii Reihenfolge der Befehle hat massiven Einfluss auf die Ausführungszeit
\ei
}
\ei
\end{minipage} \end{tikznodeenv}
\only<|handout:2-|7->{\AtBeginShipoutNext{%
\AtBeginShipoutUpperLeftForeground{%
\begin{tikzpicture}[remember picture, overlay]
%
\node[fit=(A),solution={Globale(re) Registerallokation}]{};
\node[fit=(B),solution={Peephole-Optimizer}]{};
\node[fit=(C),solution={Instruktions-Scheduling}]{};
\end{tikzpicture}
}
}
}
\end{frame}Und immer wenn der Informatiker nicht weiter weiß, besinnt man sich auf die einfachste Methode, das Problem zu lösen und überlegt sich danach, an welchen Stellen man die Methode verbessern kann[fn::Wichtig bei einem solchen Vorgehen inkrementeller Verbesserungen ist aber, dass man sich leicht in ein lokales Optimum manövrieren kann. Um dies zu vermeiden lohnt es sich eine optimale Lösung zu formulieren, egal wie aufwendig diese ist.]. Dieser einfachste Basisfall für die Maschinencodeerzeugung wird uns dabei helfen, das Problem genauer zu verstehen, bevor wir einen Vorschlag diskutieren, wie wir diese Minimallösung verbessern können. Die Minimallösung besteht daraus, dass wir eine Makroexpansion für jeden IR-Befehl durchführen und alle Variablen vor der Sequenz aus dem Slot lesen und direkt danach wieder in zurückschreiben.
Für die Makroexpansion hinterlegen wir für jeden unserer 16 IR-Befehle ein festes Makro, welches wir expandieren, wenn ein solcher Befehl im IR-Programm vorkommt. Dieses Makro besteht aus einer Maschinenbefehlsequenz, die einen oder mehrere Instruktionen umfasst. An den Stellen, an denen Register in den Operationen verwendet werden würden, enthält das Makro allerdings Platzhalter (R1, R2), die von der Registerallokation gefüllt werden. Zusätzlich gibt es noch eine Reihe von Anweisungen, welcher IR-Operand in welchen Platzhalter geladen werden soll, und in welchem Platzhalter-Register das Ergebnis zu finden sein wird.
Für jedes Auftreten des IR-Befehls im IR-Programm instantiieren wir das Makro und verbinden die Anweisungen an den Ein- und Ausgängen mit den konkreten Operanden. Die Instantiierung des Makros übergeben wir dann an die Registerallokation, die dafür sorgen muss, dass für jeden Platzhalter ein Register ausgewählt wird, die aktuellen Variablen-Werte in den Register landen, und das Ergebnis im Zieloperanden landet.
Die einfachste Variante einer Registerallokation ist ein Spilling-Registerallokator. Bei dieser Art der Registerallokation betrachten wir immer nur einen einzigen Befehl: Vor dem Befehl laden wir alle Variablen frisch aus ihrem fix zugeordneten Stack-Slot in ein Register. Nachdem die Befehlssequenz abgearbeitet ist, wird das Ergebnis sofort wieder in einen Slot zurückgeschrieben. Dieses direkte Zurückschreiben führt dazu, dass eine Variable nur für die Dauer einer einzige Instruktion in einem Register lebt. Es gibt keinerlei Probleme, dass es über Kontrollflüsse hinweg zu irgendwelchen Inkonsistenzen kommen kann oder wir vergessen, irgendeinen Wert zurückzuschreiben. Schick. Schick, aber ineffizient.
Ineffizienz ist genau das Problem dieser minimalen Maschinencodeerzeugung.
An (mindestens) drei Stellen wird das Potential der Maschine nicht voll ausgenützt:
Zum einen transferieren wir ständig Variablen-Werte zwischen Speicher und Register hin und her, egal ob diese vielleicht schon in einem Register vorgeladen sind.
Allein am Add-Beispiel, bei dem 3 von 4 Befehlen nur Transfers waren, wird deutlich, dass ein Hauptteil unseres Programms sich damit beschäftigt, den Speicher zu beschäftigen.
Viel klüger wäre es, nur das aus dem Speicher zu laden, was nicht schon in einem Register geladen ist. Wenn wir den Preis für das Laden aus dem Speicher bezahlt haben, dann wollten wir, solange es irgendwie geht, auch etwas davon haben.
Das zweite Problem ist, dass die starren Makros komplexere Fähigkeiten der CPU nicht ausnützen können.
Insbesondere bei CISC Maschinen kann ein einzelner Befehl eine sehr komplexe Semantik haben.
Auf den Folien sehen Sie eine Adressberechnung für ein Array, das einmal naiv aus drei Makros zusammengesetzt wurde, und einmal den passenden IA-32 Befehl, der in einem Rutsch %eax+8*%ebx rechnet und dereferenziert.
Die Besonderheiten der Prozessorarchitektur werden also nicht vollständig ausgenützt.
In eine ähnliche Richtung, aber unterschiedlich davon, ist das dritte Problem der Minimallösung: Die Makroexpansion ignoriert, dass moderne CPUs Befehle nicht stumpf hintereinander ausführen, sondern dass diese mit einer Pipeline arbeiten, Instruktionen in unterschiedlicher Reihenfolge als angegeben ausführen können (Out-of-Order) und überdies noch mehrere funktionale Einheiten haben (Superskalar). Dies führt dazu, dass Befehle quasi im Windschatten anderer Befehle “umsonst” ausgeführt werden können. So können in einer Out-of-Order-CPU Befehle auf der ALU ausgeführt werden, während ein früherer Befehl noch auf den Speicher wartet. Dieses Problem kann man so zusammenfassen, dass die Besonderheiten der Prozessor-*Mikroarchitektur* nicht ausgenützt werden.
Für all diese Teilaspekte gibt es Methoden die Maschinencodeerzeugung zu verbessern: Zum einen kann man bei der Registerallokation mehr als nur einen Befehl auf einmal betrachten und so eine globalere Registerallokation durchführen. Durch dieses größere Wissen wird die Allokation zwar aufwendiger, das Ergebnis aber um Größenordnungen besser. Um die Prozessorarchitektur auszunützen, haben moderne Übersetzer einen Peephole-Optimizer, der immer eine fixe Anzahl an Assemblerinstruktionen (z.B. 3 aufeinanderfolgende Befehle) mit einer Muster-Datenbank vergleicht und durch effizientere Schnipsel ersetzt. Um die mikroarchitekturellen Besonderheiten auszunützen, kann die Instruktion-Selektion Assemblerbefehle so umordnen, dass immer noch die gleiche Berechnung durchgeführt wird, aber möglichst viele Instruktionen im Windschatten anderer verdeckt werden.
Im Folgenden greifen wir uns den Aspekt der Registervergabe heraus und diskutieren einen Registerallokator, der nicht so sehr unter Amnesie leidet und sich, über den Verlauf eines einzelnen Basisblocks hinweg, merkt, welche Variablen bereits in den Registersatz transferiert wurden.
\begin{frame}[fragile]{Ein Registerallokator mit Gedächtnis}
\OrangeBox{Die Minimallösung vergisst nach jeder Instruktion alles.}
\medskip
\bi
\ii \textbf{Idee}: Der Registersatz ist \structure{Cache} für die Speicher-Variablenslots{
\bi
\ii Bereits in Register geladene Variablen sollen wiederverwendet werden
\ii Veränderte Variablen werden erst verzögert zurückgeschrieben
\ii Variablen \structure{leben} in ihrem Slot \textbf{oder} in einem Register
\ei
}\medskip
\ii<2-> Registerallokation auf Granularität eines Basisblocks {
\bi
\ii Verschränkung von Registerallokation (RA) und Makroexpansion (ME)
\ii ME weist RA an Variablen zu laden bzw. Register zurückzuschreiben
\ii RA führt währenddessen Buch über den Zustand des Registersatzes\\[1ex]{
\begin{code}[]
\begin{py}
def emit_Add(self, instr): # Makroexpansion für dst := Add lhs, rhs
reg_lhs = self.RA.load(instr.lhs)
reg_rhs = self.RA.load(instr.rhs, modify=True)
self.emit_instr("add", reg_lhs, reg_rhs)
self.RA.write(reg_rhs, instr.dst)
\end{py}
\end{code}
}
\ii LLVM bietet mit \texttt{RegAllocFast.cpp} eine ähnliche Heuristik
\ei
}
\ei
\end{frame}
\begin{frame}[fragile]{Interface des Allokators}
\bi
\ii Synchronisation zwischen Allokator und Expansion mittels \structure{Hooks} {
\bi
\ii \codeinline[style=py]{def before_Function(func)} -- Variablenslots festlegen
\ii \codeinline[style=py]{def before_BasisBlock(bb)} -- Zurücksetzen des Allokatorzustandes
\ii \codeinline[style=py]{def before_Instruction(instr)} -- Sonderbehandlung von \ircmd{Call}, \ircmd{Goto}...
\ei
}\medskip
\ii Allokieren eines leeren Registers: \codeinline[style=py]{def alloc_register(reg=None)}{
\bi
\ii Wenn kein Register vorgegeben wird, wählt der Allokator eines aus
\ii Noch ungesicherte Ergebnisse werden ggf. in den Variablenslot gespeichert
\ei
}\medskip
\ii Lade Variable nach Register: \codeinline[style=py]{def load(src, dst_reg=None, modify=False)}{%
\bi
\ii Sorgt dafür, dass \texttt{src} in einem Register vorliegt
\ii Mit \texttt{dst\_reg} können wir ein spezifisches Register verlangen
\ii Mit \texttt{modify} zeigen wir an, ob wir das Register verändern werden
\ei
}\medskip
\ii Schreibe Register nach Variable: \codeinline[style=py]{def write(src_reg, dst_var)}{%
\bi
\ii \texttt{dst\_var} wird zukünftig den Wert \texttt{src\_reg} haben
\ii Das Schreiben in den Speicher kann verzögert erfolgen
\ei
}
\ei
\end{frame}Zuerst müssen wir die Weltsicht dieses Allokators grundlegend erklären: Dieser Allokator mit Gedächtnis sieht den Registersatz als eine Art schnellen Zwischenspeicher (Cache) für die Slots der Variablen im Speicher. Der Allokator geht einen Basisblock Instruktion für Instruktion, von oben nach unten, durch und merkt sich währenddessen, welche Werte bereits im Cache liegen und welche in den Registersatz geladen werden müssen. Für letztere werden dann Load-Befehle emittiert, um den Cache zu füllen. Außerdem schreibt der Allokator die Werte aus den Registern nicht sofort zurück, wie das bei der Minimallösung der Fall war, sondern erst verzögert (lazy spilling). In den Worten der Veranstaltung “Grundlagen der Rechnerarchitektur” verwendet dieser Allokator den Registersatz als einen vollassoziativen Cache mit Write-Back Strategie. Wenn Ihnen dieser Satz Probleme bereitet, gehen Sie noch einmal zu Ihren GRA Unterlagen zurück und lesen Sie dort nach, was damit gemeint ist.
Verwendet werden kann der Allokator direkt aus der Makroexpansion heraus.
Auf den Folien sehen Sie, wie die Makroexpansion für den Add-IR-Befehl aussieht.
Dabei hat die Expansion über self.RA Zugriff auf den verwendeten Registerallokator.
Dieser verwaltet nicht nur, wie der Name andeutet, die vollen und freien Register, sondern auch die Zuordnung von Register zu Variablen.
Daher ordnet die Makroexpansion an, dass die linke (instr.lhs) und die rechte (instr.rhs) in Register geladen sein müssen.
Dabei gibt das Makro zusätzlich die Information an die Registerallokation, dass Sie gedenkt, das Register in dem die rechte Seite geladen (reg_rhs) ist, zu modifizieren.
Die eigentliche Makro-Sequenz besteht nur aus der Instruktion "add", welche in den Assembler ausgegeben bzw.
emittiert wird.
Am Ende kommuniziert die Makrosequenz, dass die Zielvariable (instr.dst) in reg_rhs zu finden ist.
Um die Integration von Makroexpansion und Registerallokator vollends zu verstehen, schauen wir uns die API des Registerallokators an. In einer funktionalen Hierarchie ist der Registerallokator vollständig abhängig von der Makroexpansion. Dies bedeutet, dass die Registerallokation niemals von alleine tätig wird, sondern an neuralgischen Stellen aufgerufen wird, um Variablen zu laden bzw. ihr die Chance gibt, sich mit der Maschinencodeerzeugung zu synchronisieren.
Durch drei Hooks, die jeweils vor der Maschinencodeerzeugung für eine Funktion, einen Basisblock oder eine einzelne Instruktion ausgeführt werden, erhält der Allokator die Möglichkeit, seine interne Buchführung entsprechend anzupassen. An diesen Stellen findet kein Informationsfluss vom Allokator zur Makroexpansion statt.
Anders Verhält es sich bei den Funktionen alloc_register(), load() und write().
Hier bekommt der Allokator einen konkreten Arbeitsauftrag von der Makroexpansion ein Register freizuräumen, eine Variable in ein Register zu transferieren, bzw. ein Ergebnis-Register mit einer IR-Variable zu verknüpfen.
Dabei muss die Makroexpansion anfordern können, dass ein konkretes Register allokiert werden soll (reg, dst_reg), da manche Maschinenbefehle ihre Operanden in bestimmten Registern erwarten.
Ohne diese Nebenbedingung darf der Allokator sich das Register frei aussuchen.
\begin{frame}{Zustand des Allokators}
\btAnimation[width=0.6\textwidth]{center, padding, range=1-2:<1->}{fig/10-allocator}
\bi
\ii Während seiner Arbeit trackt der Allokator den Registerzustand{
\bi
\ii \texttt{free}: Wurde das Register für die aktuelle Instruktion schon benutzt?
\ii \texttt{value}: Welche Variable lebt aktuell in diesem Register?
\ii \texttt{dirty}: Muss der Wert noch in den Slot zurückgeschrieben werden?
\ei
}\medskip
\ii<handout:2-|2-> \textbf{Beispielbelegung} {
\bi
\ii[\structure{eax}] Nicht Herausgegeben; \btSetTab Nichts geladen
\ii[\structure{ebx}] Herausgegeben; \btUseTab Variable a geladen; Synchronisiert mit Speicher
\ii[\structure{ecx}] Nicht Herausgegeben; \btUseTab Variable b geladen; Rückschreiben erforderlich
\ii[\structure{edx}] Herausgegeben; \btUseTab Variable c geladen; Synchronisiert mit Speicher
\ei
}
\ei
\end{frame}Bevor wir zur Funktionalität des Allokators kommen, schauen wir uns an auf welcher Datenbasis der Allokator arbeitet[fn::Grundprinzip, um informatische Lösungen zu verstehen: Fragen Sie danach, was der Zustand (Daten) ist und mit nach welchen Regeln dieser verarbeitet wird.]. Der Zustand unseres verbesserten Allokators besteht aus drei Feldern pro Prozessor-Register, die während der Maschinencodeerzeugung kontinuierlich geupdatet werden.
Das free-Feld zeigt an, ob dieses Register für die aktuelle Instruktion bereits allokiert wurde.
Da wir sicherstellen müssen, dass die beiden load() Befehle im Add-Makro unterschiedliche Register bekommen, brauchen wir dieses Boolesche Flag, um doppelte Herausgabe zu verhindern.
Diese Felder werden vor jeder Instruktion im before_Instruction()-Hook zurück auf free=true gesetzt.
Das value-Feld zeigt an, ob gerade eine Variable in diesem Register “lebt”, und wenn ja, welche. Zu Beginn eines Basisblocks wissen wir von keinem Register, dass es den aktuellen Wert einer Variable beinhaltet, weswegen diese Felder als leer initialisiert werden.
Das dirty-Feld zeigt an, dass der Stack-Slot der Variable und der Register-Inhalt gerade nicht synchronisiert sind und im Stack-Slot nur ein veralteter Wert zu finden ist. Dies bedeutet auch, dass der Wert im Register irgendwann in den Speicher zurückgeschrieben werden muss. Der Wert des Booleschen dirty-Flags ist nur dann von Relevanz, wenn dem Register eine IR-Variable in value zugeordnet ist.
Gehen wir nun die drei wichtigen API-Befehle (alloc_register(), load() und write()) durch:
\begin{handoutframeselect}
\begin{frame}{\texttt{alloc\_register()}}
\btAnimation[width=0.6\textwidth]{center, padding, 2:<1>, 3:<2-3>, range=4-7:<4->}{fig/10-allocator}
\bi
\ii \textbf{Vorbereitung}: Vor jeder Instruktion setzen wir \texttt{free} zurück{
\bi
\ii Jedes Register kann in jeder Instruktion verwendet werden
\ii Herausgabe eines Registers erzeugt \structure{Kosten} für Spilling und Neuladen
\ei
}\medskip
\ii<3-> \structure{Priorisierte Allokation} von Registern für die Befehlsauswahl {
\bi
\ii<4-> Leere Register erzeugen keine Folgekosten \hfill (Kosten: 0 \texttt{mov})
\ii<5-> Wert-Neuladen für saubere, aber belegte Register \hfill (Kosten: 1 \texttt{mov})\\
Wissen über aktuellen Wert wird gelöscht \\[1ex]
\ii<7-> Spilling und Wert-Neuladen für dreckige Register \hfill (Kosten: 2 \texttt{mov})\\
Der Allokator emittiert direkt einen Spill-Befehl für das Register
\ei
}
\ei
\end{frame}
\end{handoutframeselect}Als erstes schauen wir uns alloc_register() an, mit dem die Makroexpansion ein leeres Register anfordern kann.
Dies ist beispielsweise notwendig, wenn ein Wert aus dem “Nichts” erschaffen wird, wie dies, zum Beispiel, bei Reference der Fall ist.
Das Ziel der Vergabe ist es, ein Register so zu wählen, dass im weiteren Verlauf so wenig Folgekosten wie möglich entstehen. Zwar kann unser Allokator nicht in die Zukunft schauen, aber wir können zumindest eine oberere Schranke angeben, welche maximalen Folgekosten im weiteren Verlauf des Basisblocks entstehen können.
Der Allokator errechnet für jedes CPU-Register einen Score und gibt jenes Register mit dem günstigsten Score heraus; er nimmt eine priorisierte Allokation vor.
Für jeden Aufruf von alloc_register() kommen natürlich nur jene Register in Frage, die noch nicht vergeben sind (free=yes).
Die niedrigsten Kosten fallen an, wenn wir ein leeres Register herausgeben. Da kein Wert aus dem Registersatz verdrängt wird, können in der Zukunft auch keine Kosten für ein Neu-Laden des Wertes auftauchen. Leere Register werden also mit der höchsten Priorität vergeben.
Als nächstes geben wir Register heraus, die zwar einen Wert beinhalten, dieser aber mit dem Stack-Slot synchronisiert sind.
Für diese Register können im weiteren Verlauf nur kosten für das Neu-Laden des Wertes anfallen, wenn dieser von einem anderen Befehl noch einmal benötigt werden sollte; es fällt maximal ein Speicher-Register-Transfer an.
Wenn dieses Register herausgegeben wird, wird die Bindung zwischen Register und IR-Variable aufgehoben (value=None).
Der teuerste Fall tritt ein, wenn wir ein Register herausgeben, das einen noch nicht synchronisierten Wert beinhaltet (dirty=yes). In dieser Situation kommen auf jeden Fall Kosten für die Spill-Operation zusammen und es kann zusätzlich in der Zukunft dazu kommen, dass wir den Wert neu laden müssen. Im schlimmsten Fall zieht die Vergabe dieses Registers also zwei Register-Speicher-Transfers hinter sich her. Wir sollten diese Register also nur dann Herausgeben, wenn kein anderes Register mehr frei ist, oder die Makroexpansion ganz explizit nach diesem Register gefragt hat (alloc_register(reg="ecx")).
\begin{handoutframeselect}[2-]
\begin{frame}<\slideselection>[fragile]{\texttt{write(src\_reg, dst)}}
\uncover<2->{\btAnimation[width=0.6\textwidth]{center, padding, 8:<1-2>, 9:<3>, 10:<4-5>,11:<6->}{fig/10-allocator}}
\bi
\ii Befehlsauswahl hat Befehle emittiert, die \texttt{src\_reg} beschrieben haben{
\bi
\ii Registerinhalt soll in Zukunft als \texttt{dst}-Variable verfügbar sein
\ii Verzögertes Herausschreiben der Variable in ihren Speicherslot
\ei
}\medskip
\ii<2-> \textbf{Beispiel}: Zuweisung zwischen zwei Variablen \hfill \texttt{b := \ircmd{Assign} a}\\{
\begin{columns}
\begin{column}{0.49\textwidth}
\begin{code}[]
\begin{py}[style=highlighting]
def emit_Assign(instr):
@3src = self.RA.load(instr.src)@
@4dst = self.RA.alloc_register()@
@5self.emit_instr("mov", src, dst)@
@6self.RA.write(src, instr.dst)@
\end{py}
\end{code}
\end{column}\hfill
\begin{column}{0.49\textwidth}
\begin{code}[]\ttfamily
\uncover<3->{mov -8(\%ebp), \%eax}\\
\uncover<5->{mov \%eax, \%ebx}
\end{code}
\vspace{-1em}%
\bi
\ii<6-> \texttt{write()} setzt nur \texttt{value} und \texttt{dirty}\\[-1ex]
\ii<6-> \codeinline[style=asm,style=smaller]{mov %ebx, -12(%ebx)} geschieht später
\ei
\end{column}
\end{columns}
}
\ei
\end{frame}
\end{handoutframeselect}Am Ende eines Makroexpansion wird häufig angewiesen, dass das Ergebnis, was nun in einem der allokierten Register vorliegt, in eine IR-Variable geschrieben werden soll. Dabei geht unser Allokator den Weg, dass wir den Wert nicht sofort in den Stack-Slot schreiben, sondern nur ab sofort alle Zugriffe auf die IR-Variable aus dem angegebenen Register bedienen. Dazu setzen wir das value-Feld auf die entsprechende Zielvariable und vermerken, dass Registerinhalt und Stack-Slot gerade nicht übereinstimmen. Das Zurückschreiben geschieht dann zu einem späteren Zeitpunkt.
\begin{handoutframeselect}
\begin{frame}{\texttt{load(src)}}
\btAnimation[width=0.6\textwidth]{center, padding, range=12-16:<1->, 16:<6->}{fig/10-allocator}
\bi
\ii Laden einer Variable in ein beliebiges Register {
\bi
\ii<2-> \structure{Basisfall}: Variable ist nicht geladen $\rightarrow$ \texttt{alloc\_register()} + Ladebefehl
\ii<3-> Bereits geladen und sauber $\rightarrow$ Register allokiert markieren und herausgeben
\ii<4-> Variable bereits geladen, aber dreckig{
\bi
\ii Der Aufrufer will die Variable nicht verändern \btSetTab $\rightarrow$ wie geladen und sauber
\ii<5-> \texttt{load(src, modify=True)} \btUseTab $\rightarrow$ Register vorher spillen
\ei
}
\ei
}\medskip
\ii<6-> Laden einer Variable in ein spezifisches Register{
\bi
\ii Manchmal brauchen wir etwas in einem spezifischen Register \hfill\texttt{ret/\%eax}
\ii Bereits geladenen Wert mit \texttt{xchg} austauschen
\ei
}
\ei
\end{frame}
\end{handoutframeselect}Der load()-Befehl unseres Allokators ist der spannendste Teil der verfügbaren API.
Hier verwenden wir die Buchhaltung, die wir über die Registerinhalte führen, um Ladebefehle zu sparen, wenn Werte bereits im Register-“Cache” verfügbar sind.
Dabei weist uns die Makroexpansion an, eine gewisse IR-Variable (src) in ein Register zu laden. Hierbei unterscheiden wir zwischen mehreren Fällen, abhängig davon, wie der aktuelle Allokatorzustand aussieht:
Findet sich die zu ladende Variable in keinem Register (load(z)), so allokieren wir mittels alloc_register() ein neues Register und emittieren einen Ladebefehl, der die Variable aus ihrem Stack-Slot in das Register transferiert.
Spannend wird es, wenn die Variable bereits in einem Register lebt.[fn::Dieser ist einer der Knackpunkte des Registerallokators mit Gedächtnis.]
Wenn die Variable bereits geladen ist und das Register mit dem Stack-Slot synchronisiert ist, geben wir das Register (ebx) einfach heraus.
Erst wenn Register als dreckig markiert sind, müssen wir unterscheiden, was die Makroexpansion mit dem Register vorhat:
Will die Expansion das Register mit dem Variablenwert nur lesen, so können wir dreckige Register einfach herausgeben.
Will die Makroexpansion nicht nur den Wert einer Variable haben, sondern darüber hinaus das Register auch zum rechnen bzw. für das Ergebnis verwenden, so müssen wir dreckige Register zuerst durch einen Spill-Befehl mit dem entsprechenden Stack-Slot synchronisieren.
Würden wir das dreckige Register nicht vorher in den Variablen-Slot zurückschreiben, würden der aktuellste Wert der Variable verloren gehen.
Neben diesen vier Fällen gibt es noch einige Sonderfälle, wenn der Aufrufer von load() ein konkretes Register angefordert hat. In diesem Fall kann es sich lohnen, wenn ein Wert bereits in einem anderen Register geladen ist, den Inhalt beider Register zu tauschen (xchg) Befehl. Falls Sie weitergehendes Interesse an diesen Sonderfällen haben, können Sie diese im Übungsübersetzer anschauen.
\begin{frame}{Besondere Situationen für den Allokator}
\bi
\ii \structure{Datenflüsse}, die die Grenzen der Basisblöcke überschreiten{
\bi
\ii Basisblock-Übergreifende Registervergabe ist \alert{viel schwieriger}
\ii Werte müssten in allen Vorgängern in den selben Registern sein\\[1ex]
\ii[$\Rightarrow$] Wir starten jeden Basisblock mit einem leeren Zustand
\ei
}\medskip
\ii<2-> \structure{Funktionsaufrufe} und \structure{Sprünge}{
\bi
\ii Funktionen/andere Basisblöcke könnten die Variablen aus dem Speicher lesen
\ii Funktionen können Speicher verändern\\[1ex]
\ii[$\Rightarrow$] Alle Register sichern und Zustand zurücksetzen
\ei
}\medskip
\ii<3-> \structure{Speicheroperationen} haben wieder ein \textbf{Alias-Problem}{
\bi
\ii Wir wissen nicht, ob der gelesene/geschriebene Zeiger auf eine Variable zeigt
\ii \ircmd{Store} könnte Registerwerte invalidieren, \ircmd{Load} könnte alte Werte lesen\\[1ex]
\ii[$\Rightarrow$] Wir sichern/invalidieren Register, die jemals referenzierte Variablen enthalten\\
\hfill \texttt{ptr := \ircmd{Reference} var}
\ei
}
\ei
\end{frame}
\begin{frame}<4>{Benchmark}
\btAnimation{center,range=1-4:<1->}{fig/10-eval}
\bi
\ii Evaluation der beiden Allokatoren und Gegenüberstellung mit GCC{
\bi
\ii Benchmark: Iterativer Fibonacci, \texttt{fib\_iter(100000000)}
\ii Evaluationssystem: i7 6600 @ 2.60 Ghz, 32-Bit Modus
\ii Test-Setup: \texttt{perf stat -r 10 ./a.out}
\ei
}
\ii[$\Rightarrow$]<3-> PSÜ-Übersetzer mit Optimierungen ist Vergleichbar mit \texttt{gcc -O0}
\ii[$\Rightarrow$]<4-> GCC kann natürlich noch viel besseren Code erzeugen
\ei
\end{frame}Zuletzt müssen wir noch einige Situationen behandeln, die besonderer Behandlung durch den Allokator bedürfen. Informiert wird der Allokator über diese Situationen durch die bereits erwähnten Hooks.
Zum einen ist eine Registervergabe, die Basisblockgrenzen überschreitet, viel schwieriger als eine blocklokale Vergabe. Wieder haben wir hier das Problem, dass nur die Registerbelegungen, die in allen Vorgängerknoten konsistent sind, über Blockgrenzen hinweg Gültigkeit haben. Anders ausgedrückt: Eine Variable muss am Ende aller Vorgängerknoten im gleichen Register geladen sein, um bereits vor der ersten Instruktion eines Blocks als geladen zu gelten. Wir machen es uns hier einfach und werfen vor jedem Block einfach den gesamten Allokatorzustand weg.
Ein anderes Problem sind Funktionsaufrufe.
Da eine Funktion nur die Calle-saved Register über einen Funktionsaufruf bewahrt, müssen wir bei einem Call-Befehl alle Register, deren Inhalt potentiell vernichtet wird, invalidieren.
Dazu gehört, dass dreckige Register vorher rausgeschrieben und die Kopplung zwischen Register und IR-Variable aufgehoben werden muss. Um auf Nummer sicher zu gehen, werfen wir an dieser Stelle ebenfalls den gesamten Allokator-Zustand weg und tun so, als würde nach dem Call ein neuer Basisblock beginnen.
Ebenfalls kommen wir an dieser Stelle wieder mit dem Alias-Problem in Berührung:
Eine Referenz auf eine lokale IR-Variable wird auf der Maschinencodeebene zu einem Zeiger auf den entsprechenden Stack-Slot.
Daher kann Store-Befehl dazu führen, dass der Stack-Slot einer Variable plötzlich einen aktuelleren Wert enthält als das Register.
Unser Cache wurde also “hintenrum” invalidiert.
Um dieses Problem zu behandeln, werfen wir bei jedem Store alle Variablen aus unserer Buchhaltung, für die irgendwo in der Funktion eine Referenz erzeugt worden ist. Auf diese Weise verhindern wir, dass wir aus einem Register einen veralteten Wert für gültig halten.
Trotz aller dieser konservativen Annahmen und das häufige Wegwerfen des Allokator-Zustandes, hat unser verbesserter Allokator bereits einen erheblichen Einfluss auf die Performance von Programmen.
Um Ihnen dies zu verdeutlichen, habe ich einen iterativen Fibonacci einmal mit der Minimallösung und einmal mit der verbesserten Registervergabe übersetzt.
Dabei kommt bereits ein gewaltige Verbesserung von 36 Prozent heraus und unser Übungsübersetzer kommt in die Region von gcc, wenn dieser ohne Optimierungen gestartet wird.
Allerdings sehen Sie auch, dass GCC noch einiges aus einem solchen iterativen Fibonacci herausholt.
Diese Verbesserungen stammen sogar hauptsächlich aus der Registervergabe, da die innere Schleife der Fibonacci-Berechnung gänzlich in Registern stattfinden kann und ohne Speicheroperationen auskommt.
\dividerframe{Programme und Prozesse}
\begin{frame}{Übersicht des restlichen Übersetzungsvorgang}
\begin{btBlock}{}\small
In den letzten 10 Vorlesungen haben wir gelernt, aus Quellcode Assembler zu machen.
Daraus muss noch ein \structure{Programm} erzeugt werden, das als \structure{Prozess} gestartet und ausgeführt werden kann.
\end{btBlock}
\btAnimation[width=\textwidth]{range=1-4:<1->}{fig/10-linking-overview}
\bi
\ii<2-> Aber da ist noch mehr\ldots {
\bi
\ii \structure{Seperate Übersetzung} ermöglicht inkrementelles Neuübersetzen
\ii<handout:3-|3-> Der \structure{Loader} bringt die Binärdatei in den Prozessspeicher
\ii<handout:4-|4-> \structure{Gemeinsame Bibliotheken} erlauben es, Binärcode zu teilen
\ei
}
\ei
\end{frame}
\begin{frame}{Das Executable and Linkable Format (ELF)}
\bi
\ii ELF ist \textbf{das} \structure{Dateiformat} für übersetzten Programmcode unter Linux{
\bi
\ii Objektdateien, Bibliotheken und Binärprogramme werden als ELF gespeichert
\ii Andere Plattformen haben ähnliche Formate: Mach-O (Mac), PE (Windows)
\ii Es gibt viele \advantage{Tools}, um ELF-Dateien zu inspizieren und zu verarbeiten
\ei
}\medskip
\ii ELFs speichern Code/Daten zusammen mit anderen Metadaten{
\bi
\ii \texttt{readelf -a ELF} liefert eine Übersicht über die Metadaten
\ii Metadaten werden im Link-Prozess ergänzt und festgelegt
\ei
}
\ii Ein ELF beinhaltet zwei Sichten auf Programmdaten {
\begin{columns}[t]
\begin{column}{0.49\textwidth}
\columntitle{Link View}
\bii
\ii Informationen für den Linker
\ii Welche Funktionen werden definiert?
\ii Welche Funktionen werden aufgerufen?
\ii Nebenbedingungen für das Arrangieren von Code/Daten
\eii
\end{column}\hfill
\begin{column}{0.49\textwidth}
\columntitle{Load View}
\bii
\ii Informationen für den Loader
\ii Welcher Dateiabschnitt gehört an welche virtuelle Speicheradresse?
\ii Was wird ausführbar/schreibbar/lesbar?
\ii Müssen Bibliotheken geladen werden?
\eii
\end{column}
\end{columns}
}\ei
\end{frame}Mit Makroexpansion und Registervergabe haben wir jetzt alle Bausteine zusammen, um einen Übersetzer zu bauen, der aus dem Quellcode ein Stück Assembler-Programm für einen konkreten Prozessor erstellt[fn::Er herrscht große Freude allerorten!]. Aber damit sind wir eigentlich noch lange nicht fertig, denn Prozessoren führen, wie wir in der ersten Vorlesung gelernt haben, keinen Assembler aus, sondern binär-codierte Maschinenbefehle aus dem Speicher. Daher müssen wir noch kurz besprechen, was nach dem Übersetzer kommt, um ein vollständiges Bild zu bekommen.
Diskutieren werden wir diesen weiteren Lebenslauf unseres Programms anhand es ELF-Dateiformats, welches unter Linux verwendet wird, um bereits übersetzte Programme und Programmfragmente zu speichern, und welche auch die Basis für die Ausführung eines Programms im Rahmen eines Prozesses darstellt[fn::Sollte Ihnen der Unterschied zwischen Programm und Prozess nicht klar sein, schauen Sie sich noch einmal die zugehörigen Folien in der Veranstaltung “Grundlagen der Betriebssysteme” an.]. ELF ist also der zentrale Angelpunkt, um binär-codierten Maschinencode zu speichern und zur Ausführung zu bringen.
ELF ist auch eng verbunden mit der separaten Übersetzung von Quellcodedateien. Dabei wird der Übersetzer für mehrere Quelldateien separat aufgerufen und mit dem Zwischenschritt über den Assembler eine Objekt-Datei erstellt. Diese Objektdateien, die bereits Binärdaten enthalten und dem ELF-Format entsprechen, werden dann vom Linker zu einer großen ELF-Datei zusammengebunden. Dabei werden symbolische Referenzen zwischen den Objektdateien aufgelöst, sodass es möglich ist, eine Funktion, die in einer anderen Objekt-Datei definiert ist, aufzurufen.
Ebenfalls spielt das ELF-Format eine zentrale Rolle für die gemeinsame Verwendung von Bibliotheken. Durch diese “Shared Libraries” kann Binärcode in mehreren Programmen und Prozessen verwenden werden, ohne ihn mehrfach auf Platte bzw. im RAM zu halten. Die Verbindung zu ELF ist, dass auch diese geteilten Bibliotheken im ELF-Format gespeichert sind.
Aber was ist dieses ELF? ELF ist ein Dateiformat, das nicht nur Binärcode beinhaltet, sondern auch noch zusätzliche Metadaten speichert. Zum Beispiel geben Symbole in einem ELF einem Byte einen “symbolischen Namen”, welcher an anderer Stelle im ELF, oder in einem anderen ELF referenziert werden kann. Ein sehr hübscher graphischer Überblick über das ELF Dateiformat wurde von Ange Albertini angefertigt. Wichtig an ELF ist, dass die Metadaten zwei Sichten auf die enthaltenen Binärdaten beinhalten: den Link- und den Load View. Beide schauen wir uns nun an.
\begin{handoutframeselect}
\begin{frame}{ELF: Link View}
\vspace{-1em}
\begin{columns}
\begin{column}{0.35\textwidth}
\btAnimation[width=\textwidth]{1:<1>,2:<2->}{fig/10-elf-link-view}
\end{column}\hfill
\begin{column}{0.65\textwidth}
\bii
\ii Assembler erzeugt Objektdatei im ELF-Format{
\bi
\ii Assembler-Befehle werden zu Maschinencode
\ii Pseudo-Instruktionen steuern die Codeerzeugung
\ii Definition und Verwendung symbolischer Namen
\ei
}\medskip
\ii<2-> \structure{Sektionen} enthalten Daten, Code und Metadaten{%
\bi
\ii Flags: Allokiert(A), Ausführbar(X), Schreibbar(W)
\ii Relative Sprünge (\ircmd{Goto}) bereits aufgelöst
\ii Lücken für noch unbekannte Werte
\ii Tool: \fbox{\texttt{objdump -D ELF}}
\ei
}\medskip
\ii<2-> \structure{Symbole} geben einzelnen Bytes einen Namen{
\bi
\ii Symbole in diesem ELF definiert sein (z.B. \texttt{main})
\ii Undefinierte Symbole werden noch aufgelößt
\ii Tool: \fbox{\texttt{nm ELF}}
\ei
}\medskip
\ii<2-> \structure{Relokationen} sind Modifikationsregeln {
\bi
\ii Wo muss der Linker den Code modifizieren?
\ii Bsp.: \texttt{\&fib} wird als PC-relative Adresse eingefügt
\ii Tool: \fbox{\texttt{objdump -r ELF}}
\ei
}
\eii
\end{column}
\end{columns}
\end{frame}
\end{handoutframeselect}
\begin{frame}{ELF: Was geschieht beim Linken?}
\btAnimation[height=0.86\textheight]{center,3:<1>,4:<2->}{fig/10-elf-link-view}
\end{frame}Zuerst betrachten wir den Link View der, wie der Name es andeutet, beim Linken von mehreren Objektdateien zu einem ausführbaren Programm verwendet wird. Erzeugt werden die Objektdateien vom Assembler, der aus den *Mnemonics*[fn::Das Wort lässt sich in etwa mit Merkspruch übersetzen und es ist selbst das genaue Gegenteil von dem, was es bedeutet. Ich finde es überhaupt nicht einfach zu merken.] Binärcode erstellt. Neben den als Maschinenbefehle kodierten Assemblerzeilen gibt es auch noch Pseudo-Instruktionen, die die Erzeugung der ELF-Datei steuern. So gibt der Pseudobefehl .text an, dass ab nun Code kommt, während .data angibt, dass nun Daten folgen. Außerdem beinhaltet Assembler symbolische Namen (main, foo), die der Prozessor nicht unterstützt, und die daher in des ELFs landen müssen.
Der Link-View besteht hauptsächlich aus drei wichtigen Elementen: Sektionen, Symbole und Relokationen.
Sektionen beinhalten die eigentlichen Binärdaten, die im Fall der Text-Sektion Maschinenbefehle sind, und im Falle der Daten-Sektion vorinitialisierte globale Variablen. Sektionen haben also, in der ELF-Datei, einen Anfang, eine Länge und einen Namen. Außerdem hat jede Sektion noch Flags, die angeben, ob der Inhalt der Sektion einmal in den Prozess geladen werden soll (A), dort ausführbar ist (X) oder geschrieben werden soll (W). Da der Assembler noch nicht alle symbolischen Referenzen auflösen kann (z.B. zu Funktionen aus anderen Objekt-Dateien), lässt er an entsprechender Stelle Platzhalter, die vom Linker aufgefüllt werden. Sie sollten einmal hergehen und eine Objektdatei mittels readelf -a (Metadaten) objdump -D (Disassembly) dekodieren, um ein Gefühl für den Inhalt dieser Sektionen zu bekommen.
Neben der eigentlichen Nutzlast, die in Sektionen gespeichert ist, gibt es noch die Symboltabelle[fn::Technisch gesehen ist die Symboltabelle auch eine Sektion, die allerdings nicht in den Prozess geladen wird.
Aber zum Erklären ist es einfacher hier einen strikten Unterschied zu postulieren.].
In dieser sind symbolische Namen deklariert.
Wenn diese in der ELF-Datei definiert sind, so referenziert ein Symbol ein bestimmtes Byte in einer der Sektionen.
So zeigt das Symbol main in die Text-Sektion (T) auf das Byte mit dem Wert 0x55, was dem IA-32 Befehl push %ebp entspricht und den Beginn der Funktion markiert.
Aber ein Symbol kann auch noch undefiniert (U) sein, wie das bei fib der Fall ist.
Eine solche Situation zeigt an, dass das Symbol in einer anderen Objektdatei definiert sein muss.
Die Auflösung der undefinierten Symbole übernimmt der Linker.
Um die Symbole einer ELF-Datei zu betrachten, rufen Sie einmal das Tool nm auf einer Objektdatei auf.
Außerdem gibt es noch die Liste der Relokationen. Diese Relokationen sind Anweisungen wie der Binärcode beim Linken bzw. beim Laden verändert werden muss. So enthält eine Objekt-Datei für jede Verwendung eines undefinierten Symbols eine Relokation, die das undefinierte Symbol mit der Verwendungsstelle verbindet. Steht irgendwann die Adresse eines Symbols fest, so wird die referenzierte Lücke entsprechend umgebogen. Da manche Platzhalter eine relative (Funktionsaufrufe auf IA-32 sind Funktionsrelativ) und manche eine absolute Adressierung (Referenzerzeugung einer Variable) verlangen, hat jede Relokation noch einen Typ, der angibt, wie die Adresse des Symbols in die Binärdaten hineingepatcht werden soll.
Relokationen spielen sowohl beim Linken als auch beim Laden eine Rolle. Wenn ein Programm es erlauben soll, an unterschiedliche Stellen in den RAM geladen zu werden, so müssen alle Codestellen, die eine absolute Adressierung verlangen, entsprechend angepasst werden. Insbesondere bei geteilten Bibliotheken spielen diese Run-Time Relocations eine große Rolle.
Was geschieht nun also beim Linken mehrerer Objektdateien?
Wir rufen den Linker mit mehreren Objektdateien (main.o, foo.o) auf.
Dieser sammelt Sektionen gleichen Namens ein und hängt diese im Ergebnis-ELF hintereinander.
Wichtig zu verstehen ist, dass nicht einzelne Funktionen die Granularität des Linkers ist, sondern ganze Sektionen.
Nachdem die Sektionen gesammelt und verbunden sind, wird auch die Symboltabelle vereinigt. Dabei werden undefinierte Symbole, soweit möglich, durch definierte Symbole aus anderen Objekt-Dateien (oder aus Bibliotheken) aufgelöst. Soll am Ende eine ausführbare Datei entstehen, darf kein Symbol unaufgelöst bleiben. Ist dies doch der Fall, kommt es zu einem Linker-Fehler.
Zusätzlich werden beim Linken alle Relokationen aufgelöst, die auf nun definierte Symbole zeigen.
Dazu modifiziert der Linker die Platzhalter in den Sektionen entsprechend des Relokationstyps und des Symbolwertes.
Betrachten Sie sich hierzu die beiden Relokationen:
Beides sind PC-relative Relokationen (R_386_PC32), die das Symbol fib referenzieren[fn::~e8 xx xx xx xx~ ist ein call-Befehl].
Die obere Lücke ist in main() und führt daher einen Sprung nach vorne (um 5 Bytes aus), während die zweite Lücke ein PC-relativ nach hinten springt (der Rekursionsschritt).
Kann eine Relokation bereits vollständig beim Linken durchgeführt werden, so müssen wir sie nicht in die ausführbare Datei übernehmen.
\begin{frame}{ELF: Load View}
\bi
\ii Linker und Loader haben unterschiedliche Sichten auf die Binärdatei{
\bi
\ii Der Loader arbeitet mit Segmenten und Bibliotheksreferenzen
\ii Der Ladeprozess soll möglichst schnell und einfach sein
\ii Sektionen (und Symbole) werden für den Load View nicht benötigt \hfill \texttt{strip}
\ei
}\medskip
\ii Das Laden geschieht auf Granularität von \structure{Segmenten}{
\bi
\ii Im ELF:\hspace{1cm}\btSetTab Dateioffset und Länge des Segments
\ii Im Prozess: \btUseTab Ziel-Adresse, Länge der Allokation und Zugriffsrechte
\ei
}\medskip
\ii \structure{Shared Libraries} sind ebenfalls ELF-Dateien {
\bi
\ii Symbole können für andere ELF-Dateien exportiert werden
\ii ELF-Dateien können Bibliotheken und exportiere Symbole anfordern
\ii Angeforderte Bibliotheken werden mitgeladen und die Importe aufgelöst
\ei
}
\ei
\end{frame}
\begin{handoutframeselect}
\begin{frame}[fragile,t]{Was geschieht beim Laden?}
\btAnimation[width=\textwidth]{range=1-7:<1->}{fig/10-elf-load-view}
\begin{code}[tag=Pseudo Code]
\begin{py}[style=highlighting]
@2elf = ELF("main")@ # Ein minimaler Loader (ohne Libraries)
@3AS = AddressSpace()@
for seg in elf.program_headers:
va_start = seg.VirtAddr or 0xf0000
@4AS[va_start...seg.MemSize ] = 0@
@5AS[va_start...seg.FileSize] = ELF[seg.Offset...seg.FileSize]@
@6AS[va_start...seg.MemSize ].setFlags(seg.Flg)@
@7os.StartProzess(as=AS, eip = ELF.EntryPoint, esp=0xf0fff)@
\end{py}
\end{code}
\end{frame}
\end{handoutframeselect}Die zweite Sicht auf eine ELF-Datei ist die Load-View.
Diese wird beim Laden eines Programms in den Adressraum eines Prozesses verwendet.
Dabei werden völlig andere Metadaten verwendet als beim Linken, was es auch erlaubt, die Metadaten über Sektionen und Symbole aus der ELF-Datei zu entfernen.
Dieses “strippen” von Binärdateien wird verwendet, um kleinere Programme zu erzeugen, aber auch, um Informationen über die Programmstruktur vor einem Reverse-Engineer zu verheimlichen.
Daher wird Ihnen nm /bin/bash nur nm:
/bin/bash no symbols ausgeben.
Aber zurück zum Ladeprozess: Dieser basiert auf Segmenten, die eine Abbildung von einem Abschnitt der ELF-Datei und einem Speicherbereich im Adressraum vornehmen. Jedes Segment, welches als “zu laden” markiert ist, wird beim Ladeprozess aus der ELF-Datei in den Speicher eines Prozesses geladen. Dabei trägt ein Segment wiederum Metadaten: So kann ein Segment angeben, an eine fixe Adresse geladen zu werden oder besondere Zugriffsrechte zu bekommen. So muss der Zielbereich eines Segments, welches ausführbaren Code enthält, nach dem Laden beim Betriebssystem als ausführbar markiert werden, da es ansonsten zu einem Segmentation Fault kommt.
Auf der Seite des ELFs besteht ein Segment aus einem Offset, das relativ zum Beginn der ELF-Datei berechnet wird, und der Länge in der Datei (FileSiz).
Auf der Abbildungsseite kann ein Segment eine virtuelle Adresse (VirtAddr) vorgeben, an die es geladen werden will, eine Abbildungslänge (MemSiz) und besagte Segment-Metadaten (Flg)
Ist die Abbildungslänge länger als die Dateilänge, wird beim Laden mit Nullen aufgefüllt.
Auf diese Weise ist auch das BSS Segment implementiert:
Beim Segment, das die Daten-Sektion enthält, gilt FileSiz < MemSize.
Der Loader iteriert über die Segmente und fordert entsprechende Bereiche im Adressraum an. In diese Bereiche werden dann die Daten aus der ELF Datei, entsprechend der Segmente, kopiert und beim Betriebssystem entsprechend als ausführbar oder schreibbar markiert. Nach dem Ladeprozess springt der Loader an den Einstiegspunkt, der ebenfalls in den ELF-Metadaten gespeichert wird.
Alles in allem ist ein ELF-Loader ein relativ einfaches Stück Code, das in einigen Zeilen und mit einigen Kopieroperationen bereits eine Datei zur Ausführung bringen kann. Komplizierter wird es erst, wenn die Binärdatei an unterschiedlichen Stellen geladen werden kann oder es geteilte Bibliotheken gibt.
\begin{frame}{ELF: Shared Libraries}
\begin{center}
\includegraphics[width=0.7\textwidth]{fig/10-libraries}
\end{center}
\bi
\ii<2-> \advantage{Vorteile} von Shared Libraries {
\bi
\ii Code kann zwischen Programmen geteilt werden \hfill $\Rightarrow$ Weniger Festplatte
\ii Code kann zwischen Prozessen geteilt werden \hfill $\Rightarrow$ Weniger RAM
\ii Update einer Bibliothek erfordert keine Neuübersetzung aller Programme
\ei
}\medskip
\ii<3-> \alert{Besonderheiten} von Shared Libraries beim Ladeprozess {
\bi
\ii Das Auflösen der importierten Symbole (Linken) geschieht zur Ladezeit
\ii Bibliothek kann in jedem Prozess woanders geladen sein
\ii[$\Rightarrow$] Bibliothekscode muss verschiebbar sein
\ei
}
\ei
\end{frame}Wie bereits angedeutet, geteilte Bibliotheken sind ein gutes Mittel, um Platz, sowohl auf der Platte als auch im RAM, zu sparen. Dies funktioniert indem Shared Libraries Code enthalten, der von mehreren Programmen referenziert werden kann. Beim Laden wird dann nicht nur das ausführbare Hauptprogramm geladen, sondern auch noch alle referenzierten Bibliotheken. Der Loader löst dann alle Querverbindungen zwischen Bibliothek und Hauptprogramm auf, sodass es so wirkt, als hätten wir den Inhalt der Bibliothek im Linkprozess mit in das Binärprogramm kopiert.
Ein weiterer Vorteil von geteilten Bibliotheken ist, dass wir bei einem Update nur die Bibliothek updaten müssen, um eine ganze Reihe von Programmen mit dem Update zu versorgen. Dieser Vorteil, ist allerdings auch ein Nachteil, wenn ein System Programme enthält, welche die selbe Bibliothek in unterschiedlichen Versionen erwarten.
Wie sich mit geteilten Bibliotheken Platz auf der Platte sparen lässt, ist einigermaßen naheliegend: Der Code der Bibliothek liegt nur einmal auf Platte und nicht zig mal für jedes Binärprogramm, was ihn verwendet. Aber wie lässt sich durch geteilte Bibliotheken Platz im RAM sparen, wo die Bibliothek doch in unterschiedlichen Adressräumen zugreifbar ist. Die Antwort liegt darin zuzugeben, dass Segmente beim Laden nicht wirklich in den Speicher kopiert werden, sondern der Abschnitt im ELF nur mittels Speichervirtualisierung eingeblendet wird. Die gleiche physikalische Seite, wie sie im RAM-Riegel liegt, wird also in mehreren Prozessen, teilweise an unterschiedlichen virtuellen Adressen, sichtbar. Daher muss der Code in geteilten Bibliotheken auch Unabhängig von seiner Ladeadresse sein, was mit diversen technischen Tricks erreicht werden kann.
Auf Ebene der ELF-Datei funktionieren Bibliotheken so, dass das Hauptprogramm und jede Bibliothek eine Liste der benötigten Bibliotheken enthält. Außerdem sind in den ELF-Dateien auch noch alle importierten und exportierten dynamischen Symbolen vermerkt, die als Referenzen vom Loader aufgelöst werden. Eine Übersicht über die benötigten Bibliotheken einer Binärdatei erhalten Sie mit dem Werkzeug ldd:
$ ldd /bin/bash linux-vdso.so.1 (0x00007ffde376d000) libtinfo.so.6 => /lib/x86_64-linux-gnu/libtinfo.so.6 (0x00007ff34a6c6000) libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007ff34a6c1000) libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007ff34a501000) /lib64/ld-linux-x86-64.so.2 (0x00007ff34a85e000)
Hier sehen wir, dass fünf Shared Libraries bei Start einer Bash-Shell geladen werden.
Dabei gibt es in dieser Ausgabe zwei besondere Bibliotheken:
Die linux-vdso.so ist eine Bibliothek, die vom Betriebssystemkern stammt und schnellen sehr ausgewählte Kerndatenstrukturen zulässt{{{wikipedia_en(VDSO)}}}.
Die andere ist die ld-linux.so (letzte Zeile).
Diese ist das Ladeprogramm selbst und hat bei der GNU C Bibliothek die Besonderheit, sowohl eine geteilte Bibliothek als auch eine ausführbare Datei zu sein.
Überzeugen Sie sich selbst davon: Finden Sie den Pfad Ihrer ld-linux.so heraus und führen Sie den Loader einmal von Hand aus.
Ohne Argumente wird es Sie nur über seine Fähigkeiten in einer Hilfemeldung in Kenntnis setzen.
\begin{frame}{Zusammenfassung}
\bi
\ii Maschinencodeerzeugung schließt die verbleibende \structure{semantische Lücke} {
\bi
\ii Abbildung der IR-Maschine $\Rightarrow$ reale Maschine mit \alert{endlichen Ressourcen}
\ii Komplexe Befehlssätze und keine Abstraktion vom Speicher
\ei
}\medskip
\ii \structure{Call-Frame} enthält Argumente, Rücksprungadresse und Variablenslots{
\bi
\ii Jede Funktionsinstanz hat ihren eigenen Call-Frame
\ii Caller und Callee halten sich an die \structure{Aufrufkonvention}
\ii Basiszeiger erlaubt Adressierung mit konstanten Offsets
\ei
}\medskip
\ii \structure{Befehlsauswahl} und \structure{Registerallokation} sind NP-vollständige Probleme {
\bi
\ii Die Minimallösung besteht aus Makroexpansion und \alert{ständigem Spilling}
\ii Verbesserte Registerallokation sieht Registersatz als Cache für Variablenslots
\ei
}\medskip
\ii ELF: Dateiformat für Objektdateien, Programme und Bibliotheken {
\bi
\ii \structure{Link View}: Sektionen, Symbole und Relokationen
\ii \structure{Load View}: Segmente, importierte und exportierte Symbole
\ii \structure{Bibliotheken} erlauben Code-Sharing zwischen Programmen
\ei
}
\ei
\end{frame}