Zusammenfassung verschiedener Verfahren aus "Grundlagen des Übersetzerbaus"
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
UE1-Verfahren/verfahren.tex

396 lines
22 KiB

% !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}