397 lines
22 KiB
TeX
397 lines
22 KiB
TeX
% !TeX spellcheck = de_DE
|
|
\documentclass[11pt,a4paper,toc]{scrartcl}
|
|
\usepackage[a4paper,left=2.5cm,right=2.5cm,top=2.5cm,bottom=2.5cm]{geometry}
|
|
\usepackage[ngerman]{babel}
|
|
\usepackage{amssymb}
|
|
\usepackage{scrextend}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage{amsmath}
|
|
\usepackage{enumitem}
|
|
\usepackage{mathtools}
|
|
\usepackage[load=named]{siunitx}
|
|
\usepackage{csquotes}
|
|
\usepackage[hidelinks]{hyperref}
|
|
%\usepackage{listings}
|
|
\usepackage{algorithmicx}
|
|
\usepackage{algpseudocode}
|
|
%\usepackage{pgfplots}
|
|
\usepackage{tikz}
|
|
%\usetikzlibrary{positioning}
|
|
%\usetikzlibrary{arrows.meta}
|
|
%\usetikzlibrary{quotes}
|
|
%\usetikzlibrary{angles}
|
|
%\usetikzlibrary{babel}
|
|
%\usetikzlibrary{fit}
|
|
%\usepackage{datetime}
|
|
%\usepackage{xcolor}
|
|
|
|
%\pdfminorversion=7 % Import-Unterstützung für PDFs bis Version 1.7
|
|
%\pgfplotsset{compat=1.16} % verhindern, dass pgfplots im Rückwärtskompatibilitätsmodus arbeitet
|
|
|
|
|
|
\setlist[enumerate,1]{label={\arabic*.}}
|
|
\setlist[enumerate,2]{label={\alph*)}}
|
|
|
|
\title{Grundlagen des Übersetzerbaus: Verfahren}
|
|
\author{Marco Ammon (my04mivo)}
|
|
\date{\today}
|
|
|
|
\makeatletter
|
|
\g@addto@macro\bfseries{\boldmath}
|
|
\makeatother
|
|
|
|
\begin{document}
|
|
\maketitle
|
|
|
|
\tableofcontents
|
|
\clearpage
|
|
\section{AST-Transformationen}
|
|
|
|
\subsection{Innere Klassen}
|
|
\begin{description}
|
|
\item[innere Klasse:] in \texttt{Outer} enthaltene, nicht statische Klasse \texttt{Inner}
|
|
\end{description}
|
|
|
|
\begin{enumerate}
|
|
\item flache Hierarchie durch Verschieben der inneren Klasse außerhalb der umgebenden Klasse(n): \texttt{Outer.Inner} $\rightarrow$ \texttt{Outer\$Inner}
|
|
\item Konstruktor der inneren Klasse um Parameter ggf. erzeugen und um Parameter \texttt{Outer this\$i} ergänzen (mit $i$ als Schachtelungstiefe von \texttt{Outer}), zusätzlich gleichnamige Instanzvariable einfügen
|
|
\item Zugriffen auf Instanzvariablen von \texttt{Outer} ein \texttt{this\$i.} voranstellen
|
|
\item Hilfsmethoden für Zugriff auf private Instanzvariablen von \texttt{Outer} in \texttt{Outer} einfügen (mit aktueller Java-Version durch spezielles Attribut in Klassendatei nicht mehr notwendig)
|
|
\item Alle Auftreten von \texttt{Inner} durch \texttt{Outer\$Inner} ersetzen
|
|
\item Bei von \texttt{Inner} erbenden Klassen \texttt{(new Outer()).super();} im Konstruktor ergänzen, damit \text{Outer}-Instanz erzeugt wird
|
|
\item Bei in Blöcken deklarierten inneren Klassen wird der Zugriff auf finale (oder \enquote{effectively-final}) Variablen durch Ergänzen des Konstruktors um diese Variablen ermöglicht
|
|
\end{enumerate}
|
|
|
|
\subsection{Generics}
|
|
\begin{enumerate}
|
|
\item \enquote{Ausradieren} der Typen (\enquote{type erasure}):\begin{itemize}
|
|
\item \texttt{GenericClass<TypeParameter>} $\rightarrow$ \texttt{GenericClass}
|
|
\item Typ \texttt{TypeParameter} bleibt gleich
|
|
\item Typparameter \texttt{TypeParameter} $\rightarrow$ \texttt{Object}
|
|
\end{itemize}
|
|
\item Brückenmethoden einfügen, die \texttt{Object} zu \texttt{A} casten und dann eigentliche Implementierung aufrufen
|
|
\item Wenn Typparameter \texttt{A} einer Methode nicht aus den Argumenten ableitbar ist, Verwendung des abgeleiteten Typs \texttt{*}, der Untertyp aller Typen ist
|
|
\end{enumerate}
|
|
|
|
\section{Transformation zu Zwischensprache}
|
|
\begin{itemize}
|
|
\item mehrdimensionale Arrays meistens zu eindimensionalen Array linearisiert
|
|
\item Operatorenabbildung in \enquote{Post-Order}-Reihenfolge
|
|
\item Kurzschlusssemantik: \begin{itemize}
|
|
\item code(\texttt{a \&\& b}, $\texttt{L}_\texttt{true}$, $\texttt{L}_\texttt{false}$) $\rightarrow$ code(\texttt{a}, $\texttt{L1}$, $\texttt{L}_\texttt{false}$); \texttt{L1:} code(\texttt{b}, $\texttt{L}_\texttt{true}$, $\texttt{L}_\texttt{false}$)
|
|
\item code(\texttt{a || b}, $\texttt{L}_\texttt{true}$, $\texttt{L}_\texttt{false}$) $\rightarrow$ code(\texttt{a}, $\texttt{L}_\texttt{true}$, $\texttt{L1}$); \texttt{L1:} code(\texttt{b}, $\texttt{L}_\texttt{true}$, $\texttt{L}_\texttt{false}$)
|
|
\item code(\texttt{!a}, $\texttt{L}_\texttt{true}$, $\texttt{L}_\texttt{false}$) $\rightarrow$ code(\texttt{a}, $\texttt{L}_\texttt{false}$, $\texttt{L}_\texttt{true}$
|
|
\end{itemize}
|
|
\item code(\texttt{while e do st od}) $\rightarrow$ $\texttt{jmp L}_\texttt{cond}$; $\texttt{L}_\texttt{true}$: code(\texttt{st}); $\texttt{L}_\texttt{cond}$: code(\texttt{e}, $\texttt{L}_\texttt{true}$, $\texttt{L}_\texttt{false}$); $\texttt{L}_\texttt{false}$:
|
|
\item \texttt{switch-case}: \begin{itemize}
|
|
\item \texttt{if}-Kaskade
|
|
\item \texttt{lookupswitch}: Tabelle aus $(c_i, \texttt{L}_i)$-Tupel von Konstante $c_i$ und Sprungziel $\texttt{L}_i$ wird durchsucht
|
|
\item \texttt{tableswitch}: Konstante wird als Index in Tabelle mit Sprungzielen (\enquote{jump table}) gewählt
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\section{Funktionsaufrufe}
|
|
\begin{enumerate}
|
|
\item Vorbereitung: \begin{enumerate}
|
|
\item Argumentauswertung gemäß Übergabemechanismus
|
|
\item Sichern von Caller-Save-Registern auf dem Stack
|
|
\item Argumente in Registern/auf dem Stack ablegen
|
|
\item Funktionsaufruf
|
|
\end{enumerate}
|
|
\item Prolog: \begin{enumerate}
|
|
\item Sichern des alten FP und Allokation des Stackframes
|
|
\item Sichern von Callee-Save-Registern im Stackframe
|
|
\end{enumerate}
|
|
\item Funktionsrumpf
|
|
\item Epilog: \begin{enumerate}
|
|
\item Ablage des Rückgabewerts in Register/auf dem Stack
|
|
\item Restauration von Callee-Save-Registern
|
|
\item Freigabe des Stackframes und Restauration des FP
|
|
\item Rückkehr
|
|
\end{enumerate}
|
|
\item Nachbereitung: \begin{enumerate}
|
|
\item Abspeichern des Ergebnis an vorgesehener Stelle
|
|
\item Entfernen der Argumente vom Stack
|
|
\item Restauration der Caller-Save-Register
|
|
\end{enumerate}
|
|
\end{enumerate}
|
|
|
|
\section{Geschachtelte Funktionen}
|
|
\begin{itemize}
|
|
\item ohne Display: \begin{itemize}
|
|
\item Aufruf der geschachtelte Funktion mit Zeiger auf Aktivierungsrahmen der umschließenden Funktion (sog. statischer Vorgängerverweis SV)
|
|
\item bei Aufruf aus tieferer Schachtelungstiefe SV des Aufrufers ggf. bis zum relevanten Aktivierungsrahmen verfolgen
|
|
\end{itemize}
|
|
\item mit Display (gesondertes, globales Array) zur Speicherung der SV: \begin{itemize}
|
|
\item Bei Betreten von Funktion der Schachtelungstiefe $t$, ihren FP an Index $t$ im Display speichern und ggf. bereits bestehenden Wert einer Schwesterfunktion im eigenen Aktivierungsrahmen sichern
|
|
\item Durch statisch bekannte Schachtelungstiefe Größe des Displays zur Übersetzungszeit bekannt und Zugriff auf lokale Variablen aus umschließenden Kontext durch Dereferenzieren des SV aus statisch bekannter Position im Display
|
|
\end{itemize}
|
|
\item Funktionszeiger: auch Argumentwerte müssen mit Zeiger gespeichert werden
|
|
\end{itemize}
|
|
|
|
\section{Objekt-orientierte Sprachen}
|
|
|
|
\subsection{Methodenauswahl in Java}
|
|
\begin{enumerate}
|
|
\item Bestimmung der Klasse (des Interfaces), in der nach Methode zu suchen ist
|
|
\item Bestimmung der zu Argumenttypen passenden, anwendbaren/zugreifbaren Methoden \begin{enumerate}
|
|
\item Auswahl der Methodendeklarationen, deren Parameter in Anzahl und Typ zu den statischen Argumenttypen passen
|
|
\item Verwerfen der in Sichtbarkeit eingeschränkte Methoden
|
|
\item Auswahl der spezifischsten Methode
|
|
\end{enumerate}
|
|
\item Kontextüberprüfung (z.B. statische Funktionen, \texttt{void} Rückgabetyp, etc.)
|
|
\end{enumerate}
|
|
|
|
\subsection{Einfachvererbung}
|
|
\begin{itemize}
|
|
\item Attribute aus Oberklasse \texttt{O} liegen auch in Unterklasse \texttt{U} am selben statischen Offset zum Objektanfang $\rightarrow$ einfacher, statischer Zugriff
|
|
\item Objekt enthält Zeiger auf Klassendeskriptor
|
|
\item Klassendeskriptor enthält:\begin{itemize}
|
|
\item V-Table mit Adressen der Funktionen(Indizes in Tabelle wie Attribute)
|
|
\item Verweis auf Klassendeskriptor der Elternklasse
|
|
\end{itemize}
|
|
\item Dynamischer Methodenaufruf: \begin{enumerate}
|
|
\item Verfolgung des Zeigers zum Klassendeskriptor
|
|
\item Index in V-Table im Klassendeskriptor ist für auszuführende Methode bereits vom Compiler bekannt
|
|
\item Indirekter Sprung
|
|
\end{enumerate}
|
|
\item Casts: \begin{itemize}
|
|
\item Upcasts können vom Übersetzer verifiziert werden
|
|
\item Downcasts müssen zur Laufzeit überprüft werden:\begin{itemize}
|
|
\item ohne Display: \begin{enumerate}
|
|
\item Verfolgung des Zeigers zum Klassendeskriptor
|
|
\item Vergleich des Klassendeskriptors des Objekts mit Klassendeskriptor der Zielklasse
|
|
\item Solange keine Übereinstimmung, Vergleich mit Klassendeskriptor der Elternklasse
|
|
\item Beim Erreichen von gesuchtem Klassendeskriptor ist Casts erlaubt, ansonsten Laufzeitfehler
|
|
\end{enumerate}
|
|
\item mit Display: \begin{enumerate}
|
|
\item (maximale) Vererbungstiefe statisch feststellbar $\rightarrow$ pro Klasse kann Array aus Oberklassen angelegt werden
|
|
\item Zur Überprüfung in Array vergleichen, ob an (statisch aus der Schachtelungstiefe bekannter) Position der Zielklasse wirklich Zielklasse eingetragen ist
|
|
\end{enumerate}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\subsection{Vererbung mit Interfaces}
|
|
\begin{itemize}
|
|
\item Statische Bestimmung der V-Table-Indizes nicht mehr möglich
|
|
\item Pro Kombination aus Klasse \texttt{A} und Interface \texttt{I} wird eine Interface-V-Table \texttt{A:I} angelegt, in der Interface-Funktionen an statisch bekannten Indizes liegen:\begin{itemize}
|
|
\item Interface-V-Table enthält Verweis auf Klassendeskriptor von \texttt{A}
|
|
\item Da von Klasse implementierte Funktionen erwarten, dass \texttt{this} auf Objektbeginn zeigt, müssen Hilfsmethoden, die \texttt{this} korrigieren, erstellt und in die Interface-V-Table eingetragen werden
|
|
\end{itemize}
|
|
\item Objekt enthält \enquote{hinter} Attributen noch Verweise auf alle assoziierten Interface-V-Tables
|
|
\item Klassendeskriptor enthält Anzahl der von einer Klasse implementierten Interfaces sowie Verweis auf Interface-Tabelle der Klasse
|
|
\item Interface-Tabelle enthält Tripel aus (Offset, Verweis auf Interface-Deskriptor, Verweis auf Interface-V-Table) für alle von Klasse implementierten Interfaces: \begin{itemize}
|
|
\item Offset gibt Offset von Verweis auf jeweilige Interface-V-Table zum Anfang des Objekts an
|
|
\end{itemize}
|
|
\item Dynamischer Methodenaufruf falls statischer Typ Interface ist (sonst wie bei Einfachvererbung):\begin{enumerate}
|
|
\item Hilfsmethode mit statisch bekanntem Offset in der Interface-V-Table nachschlagen
|
|
\item Hilfsmethode verschiebt \texttt{this}-Zeiger um statisch bekannten Offset auf Objektanfang und ruft statisch bekannte, in \texttt{A} implementierte Methode auf
|
|
\end{enumerate}
|
|
\item Casts:\begin{itemize}
|
|
\item Klasse $\rightarrow$ Interface:\begin{enumerate}
|
|
\item Objektzeiger zu Klassendeskriptor zu Interface-Tabelle verfolgen
|
|
\item In Interface-Tabelle nach Eintrag für Interface suchen (ggf. komplettes Durchlaufen)
|
|
\item Im Erfolgsfall ist Cast gültig, sonst Laufzeitfehler
|
|
\item Referenz für neue Variable aus Objektanfang + zu Interface gehörigem Offset aus Interface-Tabelle bestimmen
|
|
\end{enumerate}
|
|
\item Interface $\rightarrow$ Klasse:\begin{enumerate}
|
|
\item Objektzeiger zu Interface-V-Table zu Klassendeskriptor verfolgen
|
|
\item Falls Klassendeskriptor nicht Zielklasse entspricht, Verfolgung zu Oberklasse(n)
|
|
\item Im Erfolgsfall ist Cast gültig, sonst Laufzeitfehler
|
|
\item Zeiger von Klassendeskriptor zu Interface-Tabelle verfolgen
|
|
\item In Interface-Tabelle Eintrag für Interface nachschlagen (garantiert vorhanden)
|
|
\item Referenz für neue Variable aus aktuellem Zeiger - zu Interface gehörigem Offset aus Interface-Tabelle bestimmen
|
|
\end{enumerate}
|
|
\end{itemize}
|
|
\item Interface mit Standardimplementierung:\begin{itemize}
|
|
\item Wird Standardimplementierung verwendet, muss der Objektzeiger beim Aufruf mit Interface als statischem Typ nicht korrigiert werden; allerdings ist Hilfsmethode anzulegen und in Klassen-V-Table einzutragen
|
|
\end{itemize}
|
|
\item Interface mit veränderlichem Zustand:\begin{itemize}
|
|
\item Implementierende Klassen erhalten Instanzvariablen des Interfaces als eigene Instanzvariablen
|
|
\item Interface hat implizite Getter-/Setter-Methoden, die von Klasse implementiert werden
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\subsection{Mehrfachvererbung}
|
|
\begin{itemize}
|
|
\item Objekt enthält V-Table pro Elternklasse und eine V-Table für eigene Methoden:\begin{itemize}
|
|
\item Wenn Elternmethoden nicht überschrieben werden, Verhalten wie bei Interfaces mit Standardimplementierung
|
|
\item Sonst Hilfsmethoden in V-Tables für Anteil der jeweiligen Elternklasse eintragen
|
|
\end{itemize}
|
|
\item Diamantenproblem: Mehrere Elternklassen erben von selber Klasse \texttt{A} $\rightarrow$ Attribute von \texttt{A} mehrfach vorhanden
|
|
\item Virtual Inheritance als Lösung für Diamentenproblem (nur ein Feld für doppeltes Attribut \texttt{a}):\begin{itemize}
|
|
\item \texttt{A}-Anteil des Objekts nicht mehr an festem Offset, sondern zusätzliches Offset-Feld in jedem \enquote{Anteil} des Objekts
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\section{Code-Selektion}
|
|
|
|
\subsection{Mit Registerzuteilung}
|
|
|
|
\subsubsection{Naiver Code-Generator}
|
|
\begin{itemize}
|
|
\item arbeitet auf minimalem Grundblöcken (einzelner Zwischencode-Befehl)
|
|
\item pro Befehl:
|
|
\begin{enumerate}
|
|
\item Da alle Variablen im Speicher liegen, Laden der Operanden in Register
|
|
\item Durchführung der Operation auf Registern
|
|
\item Rückschreiben des Ergebnisses in Speicher
|
|
\end{enumerate}
|
|
\item Optimierung: feste Zuteilung von Argumenten, Variablen und Zwischenergebnissen einer Funktion in Register (wenige Register müssen aber für Operationen frei bleiben)
|
|
\end{itemize}
|
|
|
|
\subsubsection{Einfacher Code-Generator mit \texttt{getreg}}
|
|
\begin{itemize}
|
|
\item arbeitet auf maximalen Grundblöcken
|
|
\item alle Variablen vor und nach maximalem Grundblock im Speicher
|
|
\item Durchlaufen aller Zwischencode-Befehle und Mitführen von Register- und Adressdeskriptoren
|
|
\item \begin{equation*}
|
|
\texttt{getreg (}x \leftarrow y\, \texttt{op}\, z \texttt{)}= \begin{cases*}
|
|
R & falls $y$ alleine in $R$ steht und $y$ nicht mehr benötigt wird\\
|
|
U & falls es unbenutztes Register $U$ gibt\\
|
|
R & \parbox[t]{.65\textwidth}{falls $x$ in einem Register stehen muss/soll, schreibe Inhalt von $R$ in Speicherplätze aller darin enthaltenen Variablen}\\
|
|
M_x & sonst
|
|
\end{cases*}
|
|
\end{equation*},\\
|
|
dazu zusätzlich Deskriptoren anpassen
|
|
\item Für jeden Befehl $x \leftarrow y\, \texttt{op}\, z$:\begin{enumerate}
|
|
\item $L_x = \texttt{getreg (}x \leftarrow y\, \texttt{op}\, z \texttt{)}$
|
|
\item Wähle $L_y$ aus Adressdeskriptor von $y$ (möglichst Register)
|
|
\item Falls $y$ noch nicht in $L_x$, generiere $L_x = L_y$
|
|
\item Wähle Platz $L_z$ aus Adressdeskriptor von $z$ (möglichst Register)
|
|
\item Generiere $L_x = L_x\, \texttt{op}\, L_z$
|
|
\item Deskriptoren aktualisieren:\begin{enumerate}
|
|
\item $L_x$ in Adressdeskriptor von $x$ eintragen
|
|
\item Falls $L_x$ Register, zugehörigen Registerdeskriptor aktualisieren
|
|
\end{enumerate}
|
|
\item Falls keine weitere Verwendung von $y$, $z$ im Grundblock und in Register,\begin{enumerate}
|
|
\item ggf. Werte in Speicher zurückschreiben
|
|
\item Register von $y$ bzw. $z$ freigeben
|
|
\item Deskriptoren aktualisieren
|
|
\end{enumerate}
|
|
\end{enumerate}
|
|
\end{itemize}
|
|
|
|
\subsubsection{Sethi-Ullman-Algorithmus}
|
|
\begin{enumerate}
|
|
\item Baue DAG-Repräsentation von Befehlen, Variablen und Zwischenergebnissen auf
|
|
\item Wandle DAG durch Herausschneiden gemeinsamer Teilausdrücke in Wald um
|
|
\item Bestimme Ershov-Zahl $r$ (Anzahl der für Auswertung benötigten Register) rekursiv für jeden Teilbaum (vertausche Operanden bei kommutativen Operationen so dass möglichst viele Variablen direkt aus Speicher gelesen werden können):\\
|
|
\begin{align*}
|
|
r(t_1\, \texttt{op}\, t_2) &= \begin{cases*}
|
|
r(t_1) + 1 & falls $r(t_1) = r(t_2)$\\
|
|
\max(r(t_1), r(t_2)) & sonst
|
|
\end{cases*}\\
|
|
r(v) &= \begin{cases*}
|
|
1 & falls linker Operand\\
|
|
0 & falls rechter Operand
|
|
\end{cases*}
|
|
\end{align*}
|
|
\item Code-Erzeugung und Mitführung eines Stapels unbenutzter Register:\begin{enumerate}
|
|
\item Rekursives Traversieren des Ausdrucksbaums
|
|
\item Besuchen der Kinder nach absteigendem Registerbedarf
|
|
\item Generierung des Befehls für aktuellen Ausdruck
|
|
\end{enumerate}
|
|
\item Auftrennung des Baumes, wenn Teilbäume mehr Register als verfügbar benötigen $\rightarrow$ Teilbaum vor Auswertung des übrigen Baums im Speicher auswerten
|
|
\end{enumerate}
|
|
|
|
\subsubsection{Dynamische Programmierung}
|
|
\begin{enumerate}
|
|
\item Rekursives Berechnen eines Kostenfelds $C[i]$ für jeden Knoten des Baums und $0 \leq i \leq \vert R\vert$ ($R$ Register der Zielarchitektur):\begin{itemize}
|
|
\item $C[i]$: Kosten der Auswertung des Teilbaums in ein Register, sofern $i$ Register zur Verfügung stehen:\begin{enumerate}
|
|
\item Für alle möglichen Maschinenbefehle $x$ alle möglichen Auswertungsreihenfolgen $y$ der Registeroperanden als $C[x, y, i]$ berechnen: erster Operand hat $i$ Register, zweiter $i-1$ Register, etc. zur Verfügung
|
|
\item $C[x, y, i] = $ Summe der Kindkosten bei Auswertungsreihenfolge $y$ $+$ Kosten des Befehls $x$
|
|
\item $C[i] = \min C[x, y, i]$, dann mit $x$ und $y$ des Minimums annotieren
|
|
\end{enumerate}
|
|
\item $C[0]$: Kosten der Auswertung des Teilbaums, wenn alle Register zur Verfügung stehen, aber Ergebnis am Ende in Speicher geschrieben wird (ergo $C[j] + 1 $)
|
|
\end{itemize}
|
|
\item Rekursives Auftrennen des Baums, wenn Ergebnis in Speicher abgelegt wird (aus annotiertem Befehl ersichtlich)
|
|
\item Ablegen der Teilbäume in Schlange (\enquote{untere Bäume zuerst})
|
|
\item Code-Generierung durch Abarbeitung der Schlange und Code-Generierung der jeweiligen Teilbäume
|
|
\end{enumerate}
|
|
|
|
\subsection{Ohne Registerzuteilung}
|
|
|
|
\subsubsection{Baumtransformationen}
|
|
\begin{enumerate}
|
|
\item Top-Down-Überdeckung des Baums mit passenden Mustern, Auswahl nach Kostenmaß (etwa meiste überdeckte Knoten)
|
|
\item Bottom-Up-Transformation gibt Instruktion bei Anwendung des Musters aus
|
|
\end{enumerate}
|
|
|
|
\subsubsection{Verfahren von Graham/Glanville}
|
|
\begin{enumerate}
|
|
\item Instruktionsbäume in Präfixform (\enquote{polnische Notation}) kodieren
|
|
\item Definition einer Maschinengrammatik, die für jeden verfügbaren Maschinenbefehl eine Produktion enthält:\begin{itemize}
|
|
\item linke Seite: Betriebsmittel, das das Ergebnis des Befehls enthält (Speicher, Register)
|
|
\item rechte Seite: Befehl mit Operanden
|
|
\end{itemize}
|
|
\item Parsen des Baumtexts mit Maschinengrammatik emittiert den Maschinencode (dabei Mehrdeutigkeit nach Heuristik auflösen)
|
|
\end{enumerate}
|
|
|
|
\section{Registerzuteilung}
|
|
\begin{itemize}
|
|
\item Lebendigkeit der Definition eines symbolischen Registers (einer Variable), wenn Pfad von Eintrittsknoten über Definition und Definition nach Verwendung noch gebraucht wird
|
|
\item Lebensspanne einer Definition umfasst alle Punkte, an denen Definition lebendig ist
|
|
\item Lebensspannen zweier Definitionen des selben symbolischen Registers verschmelzen, sofern sich beide überschneiden
|
|
\item Generelles Vorgehen: \begin{enumerate}
|
|
\item Konstruktion des Kollisionsgraphs:\begin{enumerate}
|
|
\item Knoten für jede Lebensspanne von symbolischen Registern
|
|
\item Kanten zwischen kollidierenden (sich überschneidende) Lebensspannen
|
|
\end{enumerate}
|
|
\item Konstruktion des Interferenzgraphs:\begin{enumerate}
|
|
\item Erweiterung des Kollisionsgraphs um einen Knoten pro realem Register
|
|
\item Einfügen von Kanten zwischen allen realen Registern (\enquote{Clique})
|
|
\item Einfügen von Kanten zwischen sich (aufgrund von Limitationen der Befehle) ausschließenden realen und symbolischen Registern
|
|
\end{enumerate}
|
|
\item Färben des Interferenzgraphs mit $R$ (Anzahl der realen Register) Farben entspricht Registerzuteilung
|
|
\item Bei Nichtfärbbarkeit des Graphs ggf. symbolisches Register durchgängig im Speicher halten
|
|
\end{enumerate}
|
|
\end{itemize}
|
|
|
|
\subsection{Grad-$<R$-Regel}
|
|
\begin{enumerate}
|
|
\item Sofern Graph Knoten mit Grad $< R$ enthält, ist Graph färbbar $\rightarrow$ Knoten aus Graph (und inzidente Kanten) entfernen
|
|
\item Rekursive Anwendung auf verbleibenden Graph
|
|
\item Wird leerer Graph erreicht, ist ursprünglicher Graph färbbar $\rightarrow$ Knoten in umgekehrter Reihenfolge Farbe zuweisen, die nicht mit Nachbarn in Konflikt steht
|
|
\item Optimistische Erweiterung: Wenn kein Knoten mit Grad $< R$ verbleibt, einen Knoten als aussortiert markieren, dann bei Farbvergabe aber trotzdem versuchen, passende Farbe zu finden
|
|
\item Lebensspannenaufspaltung durch zusätzlich eingefügte Kopieroperationen
|
|
\item Vermeidung von Kopieroperationen durch Registerverschmelzung (\enquote{Coalescing}):\begin{itemize}
|
|
\item Kopieroperation $s_i \leftarrow s_j$ kann gespart werden, wenn jeweilige Lebensspannen nicht kollidieren
|
|
\item $R$-Färbbarkeit des entstehenden Interferenzgraphs bleibt erhalten wenn eine der folgenden Bedingungen zutrifft:\begin{itemize}
|
|
\item Grad des verschmolzenen Knoten $< R$
|
|
\item verschmolzener Knoten hat weniger als $R$ Nachbarn vom Grad $\geq R$
|
|
\item alle Nachbarn beider Knoten entweder schon mit dem anderen Knoten interferieren oder einen Grad $< R$ haben
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{enumerate}
|
|
|
|
\section{Instruktionsanordnung}
|
|
\begin{itemize}
|
|
\item Abhänigkeits-DAG:\begin{itemize}
|
|
\item Betrachtung pro Grundblock
|
|
\item Knoten: Instruktion
|
|
\item Kante: Datenabhängigkeit zwischen zwei Instruktionen:\begin{itemize}
|
|
\item Flussabhängigkeit (\enquote{read after write})
|
|
\item Ausgabeabhängigkeit (\enquote{write after write})
|
|
\item Antiabhängigkeit (\enquote{write after read})
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item Ausführungszeit (\enquote{ExecTime}) einer Instruktion: Zeit bis Instruktion durch alle Stufen der Pipeline gewandert ist
|
|
\item Latenz (\enquote{Latency}) einer Instruktion: Zeit, die Instruktion bis zur Ausführung warten muss
|
|
\item Verzögerung (\enquote{Delay}) einer Instruktion: Zeit bis alle davon abhängigen Instruktionen ausgeführt wurden:
|
|
\begin{equation*}
|
|
\mathrm{Delay}(n) = \begin{cases*}
|
|
\mathrm{ExecTime}(n) & falls $n$ Blattknoten\\
|
|
\max_{m\in \mathrm{Succ}(n)} \left( \mathrm{Latency}(n, m) + \mathrm{Delay}(m)\right) & sonst
|
|
\end{cases*}
|
|
\end{equation*}
|
|
\item List-Scheduling: solange DAG Knoten enthält\begin{enumerate}
|
|
\item Wurzelknoten $w$ mit größtem Delay wählen
|
|
\item $w$ an Ausgabeliste anhängen
|
|
\item $w$ aus DAG entfernen
|
|
\end{enumerate}
|
|
\end{itemize}
|
|
%\printbibliography
|
|
\end{document}
|