917 lines
50 KiB
TeX
917 lines
50 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
|
|
|
|
% TODO: MathOperators verwenden
|
|
% TODO: Code in \texttt{} setzen
|
|
|
|
\setlist[enumerate,1]{label={\arabic*.}}
|
|
\setlist[enumerate,2]{label={\alph*)}}
|
|
|
|
\title{Optimierungen in Übersetzern: Verfahren}
|
|
\author{Marco Ammon (my04mivo)}
|
|
\date{\today}
|
|
|
|
\makeatletter
|
|
\g@addto@macro\bfseries{\boldmath}
|
|
\makeatother
|
|
|
|
\begin{document}
|
|
\maketitle
|
|
|
|
\tableofcontents
|
|
\clearpage
|
|
\section{Kontrollflussanalyse}
|
|
\subsection{Kontrollflussgraph}
|
|
\begin{itemize}
|
|
\item Gerichteter Graph
|
|
\item Knoten: Grundblöcke (meist maximal)
|
|
\item Kante zwischen zwei Blöcken $A$ und $B$ wenn $B$ direkt nach $A$ ausgeführt werden kann (etwa [un-]bedingter Sprung oder Fallthrough)
|
|
\item Synthetische Ergänzung um Entry- und Exit-Knoten, die mit Kante verbunden sind
|
|
\item Kontrollflussabhängigkeit: Bei Verzweigungsknoten $v$ mit direkten Nachfolgern $a$ und $b$: $y$ kontrollflussabhängig von $v$ $\Leftrightarrow$ mindestens ein Pad von $a$ zum Exit-Knoten ohne $y$ und jeder Pfad von $b$ zum Exit-Knoten über $y$
|
|
\end{itemize}
|
|
\subsection{Dominanz}
|
|
\begin{itemize}
|
|
\item Knoten $x$ dominiert $y$ ($x \geq \geq y$), wenn jeder Pfad von Wurzel zu $y$ durch $x$ laufen muss
|
|
\item Strikte Dominanz $x >> y$, falls zusätzlich $x \neq y$ gilt
|
|
\item $\mathrm{ImmDom[}y\mathrm{]}$ ist strikter Dominator von $y$, der $y$ am Nächsten ist
|
|
\item Dominatorbaum enthält jeden Knoten als Kind seines ImmDomms $\rightarrow$ Pfad zwischen $x$ und $z$ in Dominatorbaum $\Leftrightarrow$ $x >> z$
|
|
\end{itemize}
|
|
|
|
\subsubsection{Berechnung der Dominatoren $D(n)$ eines Knoten $n$}
|
|
|
|
\paragraph{Iterativer Fixpunkt-Algorithmus}
|
|
\begin{itemize}
|
|
\item mit $\mathcal{O}(\vert E\vert \vert N\vert ^2)$
|
|
\item Zunächst Überapproximation der Dominatorenmenge
|
|
\item Initialisierung aller $D(n) \in N$ mit $N$ außer Startknoten $S$ mit $D(S) = S$
|
|
\item Bis Fixpunkt erreicht ist: alle $D(n)$ zu $D'(n) = \lbrace n\rbrace \cup \bigcap_{(p, n) \in E} D(p)$
|
|
\item $n$ am besten in Tiefensuchereihenfolge durchlaufen
|
|
\end{itemize}
|
|
|
|
\paragraph{Lengauer-Tarjan-Algorithmus mit Spannendem Tiefenbaum $T$}
|
|
\begin{itemize}
|
|
\item Besuch des KFG in Tiefensuchreihenfolge mit zugehöriger Nummerierung: \begin{itemize}
|
|
\item \enquote{Spannende} Kanten gehen zu frisch nummerierten Knoten
|
|
\item Rückschreitende Kanten gehen zu Vorgänger (kleinere DFS-Nummer) in $T$
|
|
\item Fortschreitende Kanten gehen zu Nachfolger (größere DFS-Nummer) in $T$
|
|
\item Kreuzkanten führen in früher besuchten Ast in $T$
|
|
\end{itemize}
|
|
\item Dominatoren $D(n)$ liegen auf jeden Fall \enquote{über} $n$ in $T$
|
|
\item Berechnung der Semidominatoren $\mathrm{SemDom}\lbrack w\rbrack$ in Reihenfolge fallender DFS-Nummern: \begin{itemize}
|
|
\item Direkte Vorgänger auf $T$ sind Kandidaten (T-/fortschreitende Kanten)
|
|
\item $\min_{u\in \mathrm{Pred}(w), u > w} \mathrm{SemDom}\lbrack u\rbrack$ ist Kandidat (Kreuz-/rückschreitende Kanten)
|
|
\item Minimum der Kandidaten ist $\mathrm{SemDom}\lbrack w\rbrack$
|
|
\end{itemize}
|
|
\item Berechnung von $\mathrm{ImmDom}\lbrack w\rbrack$ durch Durchlaufen in Tiefenordnung von $\mathrm{SemDom}\lbrack w\rbrack$ nach $w$ (ohne $\mathrm{SemDom}\lbrack w\rbrack$):\begin{itemize}
|
|
\item Jeweils alle Vorgänger $u$ untersuchen und $u$ mit kleinstem $\mathrm{SemDom}\lbrack u\rbrack$ finden
|
|
\item \begin{equation*}
|
|
\mathrm{ImmDom}\lbrack w\rbrack = \begin{cases}
|
|
\mathrm{SemDom}\lbrack u\rbrack & \mathrm{falls}\, \mathrm{SemDom}\lbrack w\rbrack = \mathrm{SemDom}\lbrack u \rbrack\\
|
|
\mathrm{ImmDom}\lbrack u\rbrack & \mathrm{sonst}
|
|
\end{cases}
|
|
\end{equation*}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\subsubsection{Dominanzgrenze}
|
|
\begin{itemize}
|
|
\item Dominanzgrenze $DG[x]$ enthält Knoten $y$, die einen von $x$ dominierten Vorgänger besitzen, aber nicht von $x$ streng dominiert werden
|
|
\item Berechnung der $DG[x]$: \begin{align*}
|
|
DG[x] &= DG_\text{local}[x] \cup \bigcup_{z \in N, \mathrm{ImmDom}[z] = x} DG_\text{up}[x, z] \\
|
|
DG_\text{local}[x] &= \lbrace y \in \mathrm{Succ}(x) \mid \mathrm{ImmDom}[y] \neq x\rbrace\\
|
|
DG_\text{up}[x, z] &= \lbrace y \in DG[z] \mid \mathrm{ImmDom}[y] \neq x\rbrace
|
|
\end{align*}
|
|
\item Invertierung der Dominanzgrenzen liefert Kontrollflussabhängigkeiten
|
|
\end{itemize}
|
|
|
|
\subsection{Schleifenerkennung}
|
|
\begin{itemize}
|
|
\item Region: \begin{itemize}
|
|
\item Untergraph mit einem \enquote{Header} $d$, der (potentiell mehrere) Eingangskante von außerhalb besitzt
|
|
\item Wichtige Region: maximale Region mit $d$ dominiert alle Knoten der Region
|
|
\item Hierarchischer Flussbaum: Baum der Regionen
|
|
\end{itemize}
|
|
\item Rückwärtskante: Kante $(n,d)$ mit $d \geq \geq n$
|
|
\item Natürliche Schleife: \begin{itemize}
|
|
\item Rückwärtskante $(n, d)$ sowie alle Knoten $k$ mit $d \ge \ge k$ und es gibt einen Pfad von $k$ nach $n$ ohne $d$
|
|
\item Bestimmung mit Worklist-Algorithmus, der bei $n$ beginnt und rekursiv die Vorgänger bis $d$ durchläuft und in Menge aufnimmt
|
|
\end{itemize}
|
|
\item Suche nach Rückwärtskanten und natürlichen Schleifen in wichtigen Regionen ausreichend
|
|
\item \enquote{Unsaubere} Regionen: \begin{itemize}
|
|
\item ein Knoten dominiert nachgeordneten Zyklus
|
|
\item Erkennung durch Prüfung der Reduzierbarkeit des Graphs: \begin{itemize}
|
|
\item Entfernung der Rückwärtskanten aus KFG $\rightarrow$ azyklischer Graph, in dem jeder Knoten von der Wurzel erreicht werden kann $\Leftrightarrow$ KFG frei von unnatürlichen Schleifen
|
|
\item Alternative mit Transformationen: Am Ende Graph aus einem einzigen Knoten $\Leftrightarrow$ KFG reduzierbar (ohne Zyklen) \begin{description}
|
|
\item[T1-Transformation] Selbstschleifen aus Graph löschen
|
|
\item[T2-Transformation] Knoten mit eindeutigem Vorgänger mit diesem zusammenfassen
|
|
\end{description}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\section{Datenflussanalyse}
|
|
\begin{itemize}
|
|
\item Datenabhängigkeiten verhindern Umordnen: \begin{itemize}
|
|
\item Schreiben vor Lesen: Flussabhängigkeit $\delta^\mathrm{f}$
|
|
\item Schreiben vor Schreiben: Ausgabeabhängigkeit $\delta^\mathrm{o}$
|
|
\item Lesen vor Schreiben: Antiabhängigkeit $\delta^\mathrm{a}$
|
|
\end{itemize}
|
|
\item Starke Variablendefinition: sichere Zuweisung zu einer Variablen
|
|
\item Schwache Variablendefinition: mögliche Zuweisung zu einer Variablen (etwa über Zeiger oder Referenz, die möglicherweise auf Variable zeigen)
|
|
\end{itemize}
|
|
|
|
\subsection{Berechnung von Datenflusswissen}
|
|
\begin{itemize}
|
|
\item Funktion pro Grundblock: \begin{itemize}
|
|
\item Eingabe: bei Vorwärtsproblem (Rückwärtsproblem) Datenflusswissen der Vorgängerknoten (Nachfolgerknoten)
|
|
\item Vorverarbeitung: logische Operationen oder Mengenoperationen \begin{itemize}
|
|
\item sicher (must): Eigenschaft muss auf allen Eingangskanten erfüllt sein
|
|
\item möglich (may): Eigenschaft muss auf mindestens einer Eingangskante erfüllt sein
|
|
\end{itemize}
|
|
\item Ausgabe: auf Eingabe und in Grundblock enthaltenen Befehlen basierendes, aktualisiertes Datenflusswissen
|
|
\end{itemize}
|
|
\item Iterativer Fixpunkt-Algorithmus für Vorwärtsproblem: optimal Besuch in Reihenfolge des spannenden Tiefenbaums \begin{algorithmic}[]
|
|
\State $\mathrm{in}(\mathrm{Entry}) \gets \mathrm{Init}$
|
|
\ForAll{$n \in N \setminus \lbrace \mathrm{Entry}\rbrace$}
|
|
\State $\mathrm{in}(n) \gets \bot$
|
|
\EndFor
|
|
\State $\mathrm{WL} \gets N\setminus \lbrace \mathrm{Entry}\rbrace$
|
|
\While{$\mathrm{WL} \neq \emptyset$}
|
|
\State $B \gets \mathrm{pop}(\mathrm{WL})$
|
|
\State $\mathrm{out} \gets f_B(\mathrm{in}(B))$
|
|
\ForAll{$B' \in \mathrm{Succ}(B)$}
|
|
\State $\mathrm{in}(B') \gets \mathrm{in}(B') \sqcup \mathrm{out}$
|
|
\If{$\mathrm{out} \neq \mathrm{out}(B)$}
|
|
\State $\mathrm{WL} \gets \mathrm{WL} \cup \lbrace B'\rbrace$
|
|
\State $\mathrm{out}(B) \gets \mathrm{out}$
|
|
\EndIf
|
|
\EndFor
|
|
\EndWhile
|
|
\end{algorithmic}
|
|
\item Probleme bei Verwendung von Bitvektoren:\begin{itemize}
|
|
\item Transformation erfordert komplettes Neuberechnen
|
|
\item Bitvektoren oft zu groß für jeweilige Nutzungsstelle
|
|
\end{itemize}
|
|
\item Alternative Datenstrukturen: \begin{itemize}
|
|
\item Definitions-Nutzungs-Graph für erreichbare Nutzungen
|
|
\item Nutzungs-Definitions-Graph für erreichenden Definitionen
|
|
\item Variablen-Netz als Vereinigung aller sich schneidenden DU-Graphen
|
|
\item Single Static-Assignment (SSA)
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\subsection{Typische Datenflussprobleme}
|
|
\begin{itemize}
|
|
\item Erreichende Definitionen: \begin{itemize}
|
|
\item mindestens ein Pfad, auf dem Variable nicht erneut schwach definiert wird
|
|
\item Optimierungen: \begin{itemize}
|
|
\item Keine erreichende Definition $\rightarrow$ Variable nicht initialisiert
|
|
\item Genau eine oder gleiche Definition $\rightarrow$ Konstantenweitergabe oder Kopienfortschreibung möglich
|
|
\item Alle Variablen nur außerhalb einer Schleife definiert $\rightarrow$ Ausdruck schleifeninvariant
|
|
\end{itemize}
|
|
\item Umsetzung: \begin{itemize}
|
|
\item Eine Bitposition pro Variablendefinition
|
|
\item Setzen bei Definition der Variable
|
|
\item Zurücksetzen bei mindestens schwacher Definition
|
|
\item Anfangsbelegung: false
|
|
\item Vorverarbeitung: oder
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item Konstantenweitergabe: \begin{itemize}
|
|
\item Eine Bitposition plus Wert pro Variable
|
|
\item Setzen von Bit und Wert bei konstanter Definition
|
|
\item Zurücksetzen von Bit bei mindestens schwacher oder nicht konstanter Definition
|
|
\item Anfangsbelegung: false, ?
|
|
\item Vorverarbeitung: und sowie Wertgleichheit
|
|
\end{itemize}
|
|
\item Kopienfortschreibung: \begin{itemize}
|
|
\item Eine Bitposition pro aus Kopieren entstandener Wertgleichtheitsbeziehung
|
|
\item Setzen bei Kopieroperation
|
|
\item Zurücksetzen wenn Original oder Kopie mindestens schwach definiert wird
|
|
\item Anfangsbelegung: false
|
|
\item Vorverarbeitung: und
|
|
\end{itemize}
|
|
\item Verfügbare Ausdrücke: \begin{itemize}
|
|
\item auf allen Pfaden von Entry-Knoten aus wird Ausdruck bestimmt und verwendete Variablen anschließend nicht mehr schwach definiert
|
|
\item Optimierungen: \begin{itemize}
|
|
\item Elimination gleicher Teilausdrücke
|
|
\item Wiederverwendung statt Neuberechnung
|
|
\end{itemize}
|
|
\item Umsetzung: \begin{itemize}
|
|
\item Eine Bitposition pro wertnummeriertem (Teil-)Ausdruck
|
|
\item Setzen wenn Ausdruck ausgewertet wird
|
|
\item Zurücksetzen wenn vorkommende Variable mindestens schwach definiert wird
|
|
\item Anfangsbelegung: false
|
|
\item Vorverarbeitung: und sowie Ausdruck muss auf allen Pfaden verfügbar sein
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item Lebendige Variablen: \begin{itemize}
|
|
\item lebendig in Knoten $D$, wenn es einen Pfad von $D$ zum Exit-Knoten gibt, auf der die Variable ohne vorherige Redefinition schwach benutzt wird; sonst tot
|
|
\item Optimierungen: \begin{itemize}
|
|
\item Tote Variablen müssen nicht ausgerechnet werden
|
|
\item Weniger Registerdruck
|
|
\item Elimination redudanter Schleifenlaufvariablen nach der Schleife
|
|
\end{itemize}
|
|
\item Umsetzung: \begin{itemize}
|
|
\item Eine Bitposition pro Variable
|
|
\item Setzen bei Verwendung der Variable
|
|
\item Zurücksetzen bei starker Redefinition
|
|
\item Anfangsbelegung: false
|
|
\item Vorverarbeitung: oder
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item Erreichbare Nutzungen: \begin{itemize}
|
|
\item Alle Nutzungen einer Variable durch Bestimmen der Pfade, auf denen Variable ohne vorherige Redefinition verwendet wird
|
|
\item Zweck: Hilfreich für Lebendigkeitsspannen und Registerallokation
|
|
\end{itemize}
|
|
\item Vorhersehbare Ausdrücke: \begin{itemize}
|
|
\item auf allen Pfaden zum Exit-Knoten wird Ausdruck bestimmt und verwendete Variablen werden nicht vorher schwach redefiniert
|
|
\item Optimierungen: \begin{itemize}
|
|
\item Vorziehen der Ausdrucksberechnung zur Verkleinerung der Code-Größe
|
|
\item Geringerer Registerdruck in folgenden Zweigen
|
|
\end{itemize}
|
|
\item Umsetzung: \begin{itemize}
|
|
\item Eine Bitposition pro (Teil-)Ausdruck
|
|
\item Setzen bei Auswertung des Audrucks
|
|
\item Zurücksetzen bei mindestens schwacher Redefinition einer der verwendeten Variablen
|
|
\item Anfangsbelegung: false
|
|
\item Vorverarbeitung: und
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\section{Wertnummerierung in Grundblock}
|
|
\begin{itemize}
|
|
\item Post-Order-Traversierung des Ausdrucksbaums
|
|
\item Jede referenzierte Variable bekommt eindeutige Id
|
|
\item Kombination aus Operator und beiden Argumenten bekommt entweder frische Id oder bei Duplikat (auch kommutativ) bereits verwendete
|
|
\item Gleiche Ids $\Leftrightarrow$ gleicher Ausdruck
|
|
\end{itemize}
|
|
|
|
\section{Static Single Assignment (SSA)}
|
|
\begin{itemize}
|
|
\item Jede Variable hat exakt eine starke und keine schwache Definition
|
|
\item erfordert Verwendung von $\phi$-Funktionen, die verschiedene Variablen zusammenführt
|
|
\end{itemize}
|
|
|
|
\subsection{Konstruktion der SSA-Form}
|
|
\begin{itemize}
|
|
\item In isoliertem Grundblock trivial: Erzeugung einer neuen Variable $x_i$ bei jeder Definition
|
|
\item $\phi$-Funktionen sollten möglichst sparsam nur wenn notwendig eingefügt werden
|
|
\end{itemize}
|
|
|
|
\subsubsection{Iteratives Dominanzgrenzenverfahren nach Cytron ($\mathcal{O}(N^2)$)}
|
|
\begin{itemize}
|
|
\item Dominanzgrenzenkriterium: Aus Definition von $v$ in Grundblock $X$ folgt eine $\phi$-Funktion für $v$ in jedem Grundblock der Dominanzgrenze von $X$
|
|
\item Eingefügte $\phi$-Funktionen werden Variablen zugewiesen, für die das Dominanzgrenzenkriterium erneut angewendet werden muss
|
|
\end{itemize}
|
|
|
|
\subsubsection{Wertnummerierungsverfahren nach Click}
|
|
\begin{itemize}
|
|
\item Wertnummerierung für jeden Grundblock $Z$ durchführen: \begin{itemize}
|
|
\item $\mathrm{wn}_Z(\mathrm{const}) = \mathrm{const}$
|
|
\item Wenn $Z$ Entry-Knoten, alle Wertnummern der Tupel in $Z$ auf ungültig setzen
|
|
\item Bei zwei Vorgängern $X, Y$ von $Z$, welche beide bereits besucht sind:\begin{itemize}
|
|
\item Wenn $\mathrm{wn}_X(t) \neq \mathrm{wn}_Y(t)$, dann neue Wertnummer $x$ für $\mathrm{wn}_Z(t)$ einführen und $\mathrm{wn}_Z(t) = \phi(\mathrm{wn}_X(t), \mathrm{wn}_Y(t))$ generieren
|
|
\item Ansonsten: $\mathrm{wn}_Z(t) = \mathrm{wn}_X(t)$
|
|
\end{itemize}
|
|
\item Bei einem Vorgänger $X$ mit undefiniertem $\mathrm{wn}_X(t)$ diesen rekursiv initialisieren
|
|
\item Bei zwei Vorgängern $X, Y$ von $Z$, wobei nur $X$ noch unbesucht ist:\begin{itemize}
|
|
\item Neue Wertnummer für $\mathrm{wn}_Z(t)$ einführen
|
|
\item Neue besondere Wertnummer für $\mathrm{wn}_X(t)$ einführen
|
|
\item Vorläufige $\phi'$-Funktion $\mathrm{wn}_Z(t) = \phi'(\mathrm{wn}_X(t), \mathrm{wn}_Y(t))$ generieren
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item Wertnummerierung für alle Tupel $t$ in $Z$ durchführen
|
|
\item Nach Durchführung für alle Blöcke, $\phi'$-Funktionen korrigieren: \begin{itemize}
|
|
\item Besondere Wertnummern in $X$ durch letzte in $X$ gültige Wertnummer ersetzen
|
|
\item Offene $\phi'$-Funktionen durch abgeschlossene $\phi$-Funktion mit ersetzten Werten ersetzen
|
|
\item Falls $t$ in unbesuchten Blöcken nicht geändert wurde, $\mathrm{wn}_Z(t) = \phi'(\mathrm{wn}_X(t),\mathrm{wn}_Y(t))$ löschen und alle Verwendungen von $\mathrm{wn}_Z(t)$ durch $\mathrm{wn}_X(t)$ ersetzen
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\newpage
|
|
\subsubsection{Wertnummerierungsverfahren nach Click/Braun (aus Übung)}
|
|
\begin{algorithmic}
|
|
\Function{Visit}{Basisblock $b$}
|
|
\State Wertnummerierung mit ReadVar/WriteVar durchführen
|
|
\ForAll{KFG-Nachfolger $s$ von $b$}
|
|
\If{$b$ ist letzter Vorgänger (höchste Tiefensuchnummer) von $s$}
|
|
\State \Call{Seal}{$s$}
|
|
\EndIf
|
|
\If{$s$ noch nicht besucht}
|
|
\State \Call{Visit}{$s$}
|
|
\EndIf
|
|
\EndFor
|
|
\EndFunction
|
|
\Statex
|
|
\Function{Seal}{Basisblock $b$}
|
|
\ForAll{vorläufige $\phi$-Funktion für Variable $v$ in $b$}
|
|
\ForAll{KFG-Vorgänger $p$ von $b$}
|
|
\State \Call{ReadVar}{$v$, $p$} als Operand zu $\phi$-Funktion hinzufügen
|
|
\EndFor
|
|
\EndFor
|
|
\EndFunction
|
|
\Statex
|
|
\Function{WriteVar}{Variable $v$, Basisblock $b$}
|
|
\State \Return nächste frische Wertnummer für $v$
|
|
\EndFunction
|
|
\Statex
|
|
\Function{ReadVar}{Variable $v$, Basisblock $b$}
|
|
\If{$b$ enthält bereits Wertnummer für $v$}
|
|
\State \Return Wertnummer für $v$ in $b$
|
|
\EndIf
|
|
\If{$b$ ist noch nicht versiegelt}
|
|
\State vorläufige $\phi$-Funktion mit nächster Wertnummer für $v$ in $b$ einfügen
|
|
\State \Return Wertnummer der $\phi$-Funktion
|
|
\ElsIf{$b$ hat nur einen Vorgänger $p$}
|
|
\State \Return \Call{ReadVar}{$v$, $p$}
|
|
\Else
|
|
\State $phi$-Funktion mit nächster Wertnummer für $v$ in $b$ in einfügen
|
|
\ForAll{KFG-Vorgänger $p$ von $b$}
|
|
\State \Call{ReadVar}{$v$, $p$} als Operand zu $\phi$-Funktion hinzufügen
|
|
\EndFor
|
|
\State \Return Wertnummer der $\phi$-Funktion
|
|
\EndIf
|
|
\EndFunction
|
|
\end{algorithmic}
|
|
|
|
\subsection{Optimierungen auf SSA-Form}
|
|
\begin{itemize}
|
|
\item Konstantenweitergabe: \begin{itemize}
|
|
\item Aus $v_i = c$ können alle Verwendungen von $v_i$ durch die Konstante $c$ ersetzt werden
|
|
\item Aus $v_i = \phi(c_1, c_2, \textellipsis)$ kann $v_i$ durch $c_1$ ersetzt werden, wenn alle $c_i$ gleich sind
|
|
\item Datenflussanalyse muss nach Ersetzung nicht wiederholt werden, Worklist-Algorithmus reicht aus
|
|
\end{itemize}
|
|
\item Kopienfortschreibung: Aus $v_i = y_j$ kann jede Verwendung von $v_i$ durch $y_j$ ersetzt werden
|
|
\item Lebendigkeit einer Variable lässt sich direkt aus weiterem lesenden Zugriff erkennen
|
|
\item Gemeinsame Teilausdrücke, verfügbare Ausdrücke und vorhersehbare Ausdrücke lassen sich durch Wertnummerierung in gesamter Prozedur leicht erkennen
|
|
\item Elimination toten Codes:\begin{itemize}
|
|
\item alles, was nicht als lebendig markiert ist, ist tot
|
|
\item Markierung von Anweisungen als lebendig, falls sie \begin{itemize}
|
|
\item Seiteneffekte wie I/O, Funktionsaufrufe oder die Rückgabe von Werten hat
|
|
\item eine später von einer lebendigen Anweisung benutzte Variable schreibt
|
|
\item eine Verzweigung ist, von der eine lebendige Anweisung kontrollflussabhängig ist
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\subsection{Rücktransformation aus SSA-Form}
|
|
\begin{itemize}
|
|
\item $\phi$-Funktion nicht in Hardware abbildbar, Umwandlung notwendig
|
|
\item Aus $v_3 = \phi(v_1, v_2)$ wird \begin{itemize}
|
|
\item $v_3 = v_i$ in Vorgängerblock $i$ falls sich Lebensspannen der $v_i$ nicht paarweise überlappen (konventionelle SSA-Form)
|
|
\item $v_3 = t$ ($t$ frische Temporärvariable) in Block mit $\phi$-Funktion sowie $t = v_i$ in Vorgängerblock $i$
|
|
\end{itemize}
|
|
\item Sequentialisierung paralleler Kopieroperationen (TODO VL-06)
|
|
\item Variablen können auch nur schwach definiert sein, etwa durch Zeiger auf Variablen oder Seiteneffekte von Prozeduren auf globale Variablen $\rightarrow$ Hilfsfunktion $\mathrm{isAlias}(p, v)$\begin{itemize}
|
|
\item \begin{equation*}
|
|
\mathrm{isAlias}(p, v) = \begin{cases}
|
|
*p & \text{falls}\, p = \&v\\
|
|
v & \text{sonst}
|
|
\end{cases}
|
|
\end{equation*}
|
|
\item Für jede Zuweisung $*p = $ für jede Variable $v_i$, auf die $p$ zeigen könnte, neue Zuweisung $v_{i+1} = \mathrm{isAlias}(p, v_i)$ einfügen
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\section{Alias-Analyse}
|
|
\begin{itemize}
|
|
\item Aliase: Verschiedene Möglichkeiten auf gleiche Speicherstelle zuzugreifen
|
|
\item Sprachabhängige Quellen von Aliasen: \begin{itemize}
|
|
\item dynamisch allokierte Datenstrukturen
|
|
\item Zeiger
|
|
\item überlappende Speicherbereiche
|
|
\item Referenzen auf Arrays, -Abschnitte, -Dimensionen und -Elemente
|
|
\item Prozedurparameter
|
|
\item Zeigerarithmetik
|
|
\end{itemize}
|
|
\item Sprachunabhängige Quellen wie Transitivität ($a$ zeigt auf $b$ und $b$ zeigt auf $c$ $\rightarrow$ $c$ ist von $a$ erreichbar)
|
|
\item TODO: Aliase in Fortran, Pascal, C und Java (VL-07)
|
|
\item mögliche Aliase (may) müssen nur in einem Pfad Aliase sein
|
|
\item sichere Aliase (must) müssen in allen Pfaden Aliase sein
|
|
\item Fluss-ignorierende Analyse bestimmt, ob Namen irgendwo im KFG Aliase sein können: \begin{itemize}
|
|
\item vergleichsweise einfach berechenbar
|
|
\item oft für interprozedurale Analyse eingesetzt
|
|
\item Relation $\mathrm{Alias}(a, b)$ gibt an, dass $a$ und $b$ für ganze Prozedur Aliase sind, ist reflexiv, symmetrisch und bei must-Analyse auch transitiv
|
|
\end{itemize}
|
|
\item Fluss-sensitive Analyse bestimmt, ob Namen in einem Basisblock Aliase sein können: \begin{itemize}
|
|
\item aufwändige Berechnung
|
|
\item oft für intraprozedurale Analyse eingesetzt
|
|
\item Funktion $\mathrm{Alias}(P, v) = S$ gibt an, dass $v$ an Programmpunkt $P$ auf Speicherstelle $S$ zeigen kann
|
|
\item Bei may-Analyse: \begin{itemize}
|
|
\item $\mathrm{Alias}(P, v_1) \cap \mathrm{Alias}(P, v_2) \neq \emptyset \Leftrightarrow$ $v_1, v_2$ sind in $P$ Aliase
|
|
\item nicht transitiv
|
|
\end{itemize}
|
|
\item Bei must-Analyse: \begin{itemize}
|
|
\item $\vert \mathrm{Alias}(P, v)\vert = 1$, Aliase wenn Speicherstelle gleich
|
|
\item transitiv
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item intraprozedurale Analyse: \begin{itemize}
|
|
\item Betrachtung einer einzelnen Prozedur
|
|
\item Worst-Case-Annahmen bei Aufruf anderer Prozedur
|
|
\item häufig auf Datenflussproblem zurückgeführt
|
|
\end{itemize}
|
|
\item interprozedurale Analyse: \begin{itemize}
|
|
\item Standard-Verfahren
|
|
\item Andersens Algorithmus
|
|
\item Steensgards Algorithmus
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\subsection{DFA-Ansatz zur intraprozeduralen, fluss-sensitiven may-Analyse nach Muchnick}
|
|
\begin{itemize}
|
|
\item Vorwärtsproblem mit minimalen Grundblöcken
|
|
\item Sprachabhängige lokale Flussfunktionen für unmittelbare Auswirkungen pro Instruktion (Sammler/Gatherer), hier für C: \begin{itemize}
|
|
\item Programmpunkt $P$: Kante in KFG der minimalen Grundblöcke
|
|
\item $\mathit{stmt}(P)$: Instruktion an Quelle der $P$-Kante
|
|
\item o.B.d.A. Annahme, dass jeder Programmpunkt $P$ nur einen Vorgänger $P'$ besitzt (synthetisch für Vorverarbeitung erzeugen)
|
|
\item Speicherstelle des Datums $x$ an Punkt $P$ $\mathit{mem}_P(x)$ initialisieren auf \begin{itemize}
|
|
\item $\mathit{star}(o)$: Für $o$ statisch allozierter Speicherbereich
|
|
\item $\mathit{anon}$: Dynamisch allozierter Speicherbereich
|
|
\end{itemize}
|
|
\item $\mathit{any}$ als Menge aller Speicherbereiche
|
|
\item Notation für Funktionen des Aliaswissens:\begin{itemize}
|
|
\item $\mathit{ptr}_P(x)$: Menge der Speicherstellen, auf die $x$ an $P$ zeigen kann
|
|
\item $\mathit{ref}_P(x)$: Menge der Speicherstellen, die an $P$ von $x$ über beliebig viele Derefenzierungen erreicht werden können
|
|
\item $\mathit{ovr}_P(x)$: Menge der Speicherstellen, die $x$ an $P$ überdecken kann
|
|
\end{itemize}
|
|
\item Flussfunktionen:\begin{itemize}
|
|
\item \texttt{x = \&a}: $\mathit{ptr}_P(x) = \lbrace\mathit{mem}_P(a)\rbrace = \lbrace\mathit{mem}_{P'}(a)\rbrace$
|
|
\item \texttt{x = y}: \begin{equation*}
|
|
\mathit{ptr}_P(x) = \mathit{ptr}_P(y) = \begin{cases*}
|
|
\lbrace \mathit{mem}_0(*y)\rbrace & falls $P' = 0$\\
|
|
\mathit{ptr}_{P'}(y) & sonst
|
|
\end{cases*}
|
|
\end{equation*}
|
|
\item \texttt{*x = a}: $\mathit{ptr}_P(x) = \mathit{ptr}_{P'}(x)$, zusätzlich wenn \texttt{*x} Zeiger $\mathit{ptr}_P(*x) = \mathit{ptr}_{P'}(*x) \cup \mathit{ptr}_{P'}(a)$
|
|
\item \texttt{f(...)}: \begin{itemize}
|
|
\item $G$: Menge der global sichtbaren Zeiger
|
|
\item $L$: Menge der lokalen Variablen im Aufrufer, deren Adresse berechnet wurde
|
|
\item $\forall x \in G \cup L:\, \mathit{ptr}_P(x) = \left(\cup_{g \in (G \cup \mathit{mem}(G))} \mathit{ref}_{P'}(g)\right) \cup \left(\cup_{l\in L} \mathit{ref}_{P'}(l)\right)$
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item Sprachunabhängiger Fixpunktpunktalgorithmus (Verbreiter/Propagator): \begin{itemize}
|
|
\item Initialisierung aller Zeigervariablen $x$ mit \begin{equation*}
|
|
\mathit{Ptr}(P, x) = \begin{cases*}
|
|
\emptyset & falls $P = 0$ und $x$ ist lokale Variable\\
|
|
\mathit{any} & falls $P = 0$ und $x$ ist globale Variable\\
|
|
\lbrace \mathit{mem}_0(*x)\rbrace & falls $P = 0$ und $x$ ist Parameter\\
|
|
\emptyset & sonst
|
|
\end{cases*}
|
|
\end{equation*}
|
|
\item Berechnung des Aliaswissens:\begin{equation*}
|
|
\mathit{Ptr}(P, x) = \begin{cases*}
|
|
\mathit{ptr}_P(x) & falls $\mathit{stmt}(P)$ Zeiger $x$ beeinflusst\\
|
|
\mathit{Ptr}(P',x) & sonst
|
|
\end{cases*}
|
|
\end{equation*}
|
|
\item Bei Flussfunktion $\mathit{ptr}_P(*c)$ für alle $k \in \mathit{Ptr}(P, c)$ Wissen $\mathit{Ptr}(P, k)$ berechnen
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\subsection{Standard-Verfahren zur interprozeduralen, fluss-insensitiven may-Analyse}
|
|
\begin{itemize}
|
|
\item Laufzeit: $\mathcal{O}(n^2 + n \cdot e)$
|
|
\item Alias-Quellen in Sprachen ohne \&-Operator: \begin{itemize}
|
|
\item Übergabe globaler Variable an Funktion
|
|
\item Übergabe der gleichen Variable an mehrere formale Parameter einer Funktion
|
|
\item Zugriff auf umgebende Variablen/formale Parameter bei geschachtelten Prozeduren (vgl. globale Variablen)
|
|
\end{itemize}
|
|
\item Prozeduraufrufgraph (PCG): \begin{itemize}
|
|
\item Knoten: Prozeduren des Programms
|
|
\item Gerichtete Kante von $p$ nach $q$ wenn $p$ $q$ aufrufen kann
|
|
\end{itemize}
|
|
\item Variablenbindungsgraph: \begin{itemize}
|
|
\item Knoten: formale Parameter
|
|
\item Gerichtete Kante von $x$ nach $y$ wenn $(p, q)$ in PCG, $x$ formaler Parameter von $p$ und $x$ Argument für formalen Parameter $y$ von $q$
|
|
\item transitiver Abschluss liefert Alias-Menge der formalen Parameter (aber globale Variablen sind nicht berücksichtigt)
|
|
\end{itemize}
|
|
\item Paarbindungsgraph: \begin{itemize}
|
|
\item Knoten: alle Paare formaler Parameter
|
|
\item Gerichtete Kante von $(x, y)$ nach $(X, Y)$, wenn \begin{itemize}
|
|
\item $(x,y)$ bei einem Anruf an $(X,Y)$ gebunden werden oder
|
|
\item $(x,y)$ bei einem Aufruf im Inneren einer geschachtelten Prozedur an $(X, Y)$ gebunden werden, wobei ggf. Aliase von $x$ oder $y$ verwendet werden
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}\begin{enumerate}
|
|
\item Aliase globaler Variablen: \begin{enumerate}
|
|
\item Bindungen von globalen Variablen an formalen Parametern entdecken
|
|
\item Aus Pfaden in Variablenbindungsgraph zusätzliche formale Parameter, an die globale Variable weitergegeben werden können, bestimmen (in topologischer Reihenfolge durchlaufen; bei Zyklen bis Fixpunkt erreicht)
|
|
\item Aliase der globalen Variablen ablesen
|
|
\end{enumerate}
|
|
\item Parameterpaare als Aliase: Zwei formale Parameter sind Aliase, wenn \begin{itemize}
|
|
\item die gleiche Variable an beide übergeben wird
|
|
\item eine globale Variable und einer ihrer Aliase übergeben wird
|
|
\end{itemize}\begin{enumerate}
|
|
\item Betrachtung aller Paare formaler Parameter
|
|
\item Markierung der Paare, die beim Aufruf zu Alias-Paaren werden können
|
|
\item Propagation von Alias-Informationen durch den PCG
|
|
\item Ablesen der Aliase formaler Parameter
|
|
\end{enumerate}
|
|
\end{enumerate}
|
|
|
|
\subsection{Steensgards Algorithmus zur interprozeduralen, fluss-insensitiven may-Analyse}
|
|
\begin{itemize}
|
|
\item kontext-insensitiv: vermischt Aliaswissen mehrerer Aufrufe der gleichen Funktion
|
|
\item Speichergraph: \begin{itemize}
|
|
\item Knoten: eine oder mehrere Speicherstellen
|
|
\item gerichtete Kante: \enquote{zeigt (möglicherweise) auf}-Beziehung, damit Alias: (*start, ziel)
|
|
\end{itemize}
|
|
\item approximiert Speichergraph: \begin{itemize}
|
|
\item Maximal eine abgehende Kante pro Knoten
|
|
\item Zusammenfassung mehrerer Speicherstellen, auf die Variable zeigen kann, zu einer Speicherstelle
|
|
\end{itemize}
|
|
\end{itemize}\begin{enumerate}
|
|
\item Einführung eines Knotens im Speichergraph pro Variable, wobei Kanten Zeiger repräsentieren
|
|
\item Fluss-ignorierendes, lineares Abarbeiten aller Anweisungen: \begin{itemize}
|
|
\item $a = \&b$: Kante zwischen $a$ und $b$ einfügen; sofern bereits Kante zwischen $a$ und $x$ existiert, rekursives Verschmelzen von $x$ und $b$
|
|
\item $a = b$:\begin{itemize}
|
|
\item $b$ ist Zeiger: Verschmelzen der Ziele von $a$ und $b$, anschließend zeigen beide auf diesen Knoten
|
|
\item $b$ ist kein Zeiger bzw. noch nicht erkannt: Annotiere $b$ mit $\lbrace a = b\rbrace$ (Falls später Zeigerziel $y$ von $b$ entdeckt wird, muss Kante von $a$ nach $y$ ergänzt werden)
|
|
\end{itemize}
|
|
\item $a = *b$: \begin{itemize}
|
|
\item $b$, $*b$ haben bereits ausgehende Kanten: Kante zwischen $a$ und $**b$ ergänzen
|
|
\item sonst: analog zu $a = b$ mit adäquaten Annotationen
|
|
\end{itemize}
|
|
\item $*a = b$: \begin{itemize}
|
|
\item $a$, $*a$ mit ausgehenden Kanten: rekursives Verschmelzen von $*b$ und $**a$
|
|
\item $a$ noch ohne ausgehende Kante: Annotation von $a$ mit $\lbrace *a = b\rbrace$
|
|
\end{itemize}
|
|
\item $a = b \oplus c$ mit $\oplus$ binärer Operation: \begin{itemize}
|
|
\item $a$, $b$, $c$ nicht als Zeiger erkannt: Annotation von $b$ und $c$ mit $\lbrace a= b\rbrace$ bzw. $\lbrace a= c\rbrace$
|
|
\item $b$ oder $c$ Zeiger: Kante von $a$ nach $*b$ hinzufügen, $c$ mit $\lbrace a = b\rbrace$ annotieren
|
|
\end{itemize}
|
|
\item $x = p(y_1, \textellipsis, y_n)$ mit Funktion $p(z_1, \textellipsis, z_n)$ \begin{enumerate}
|
|
\item Zuweisungsregeln $z_i = y_i$ verwenden
|
|
\item ggf. Speichergraph für Anweisungen von $p$ berechnen
|
|
\item Zuweisungsregeln für $x$ verwenden
|
|
\end{enumerate}
|
|
\item Funktionszeiger: Bei Verschmelzen auf Typen achten
|
|
\end{itemize}
|
|
\end{enumerate}
|
|
|
|
\section{Schleifen}
|
|
\subsection{Schleifeninvariante Anweisungen}
|
|
\begin{itemize}
|
|
\item schleifeninvariante Instruktion: alle Operanden $v$ sind \begin{itemize}
|
|
\item konstant oder
|
|
\item nur außerhalb der Schleife berechnet oder
|
|
\item innerhalb der Schleife in \emph{einer} schleifeninvarianten Instruktion berechnet
|
|
\end{itemize}
|
|
\item Auffinden schleifeninvarianter Instruktionen: \begin{enumerate}
|
|
\item Identifikation natürlicher Schleifen
|
|
\item Berechnung der erreichenden Definitionen
|
|
\item Konstantenfaltung
|
|
\item Markierung aller konstanten Ausdrücke und Variablen, sowie alle Markierung, deren erreichende Definitionen außerhalb der Schleife liegen, als schleifeninvariant
|
|
\item Solange neue Markierungen auftreten: alle Instruktionen/Variablen als schleifeninvariant markieren, wenn \begin{itemize}
|
|
\item sie konstant sind oder
|
|
\item wenn alle erreichenden Definitionen außerhalb der Schleife liegen oder
|
|
\item wenn genau eine erreichende Definition existiert und diese als schleifeninvariant markiert ist
|
|
\end{itemize}
|
|
\end{enumerate}
|
|
\item Herausziehen von schleifeninvarianten (Teil-)Ausdrücken vor den Schleifenkopf unter Beachtung von Seiteneffekten/Fehlern immer möglich
|
|
\item Auswahl von herausziehbaren Zuweisungen: \begin{enumerate}
|
|
\item Berechnung der Dominanz, erreichenden Definitionen und Anwendung von Konstantenfaltung
|
|
\item Berechnung der invarianten Instruktionen
|
|
\item Bestimmung der Schleifenausgänge, also Knoten, die KFG-Nachfolger außerhalb der natürlichen Schleife besitzen
|
|
\item Alle Anforderungen an Zuweisungen müssen für Herausziehbarkeit gelten:\begin{itemize}
|
|
\item schleifeninvariant
|
|
\item in Grundblock, der alle Schleifenausgänge, nach denen die Variable lebendig ist, dominiert und alle die Variable nutzenden Blöcke strikt dominiert (oder in definierendem Block nach Definition auftritt)
|
|
\item einzige Zuweisung zu Variable in der ganzen Schleife
|
|
\end{itemize}
|
|
\item Herausziehen vor den Schleifenkopf in Breitensuchreihenfolge zur Bewahrung der Datenabhängigkeiten zwischen herausgezogenen Zuweisungen
|
|
\end{enumerate}
|
|
\item Sonderfall while-Schleife: Schleifenausgang wird von keinem anderen Grundblock in der Schleife dominiert, also keine herausziehbaren Zuweisungen in der Schleife $\rightarrow$ erst Umbau zu do-while-Schleife
|
|
\item Optimierung bei invariantem Test: Generierung einer eigenen Schleife für jeden Fall
|
|
\end{itemize}
|
|
|
|
\subsection{Induktionsvariablen}
|
|
\begin{itemize}
|
|
\item Induktionsvariable: Variable, die bei jeder Schleifeniteration um konstanten Wert inkrementiert oder dekrementiert wird
|
|
\item Einfache Induktionsvariable: Variable $x$, die nur durch $x = x \pm c$ mit schleifeninvariantem $c$ verändert wird
|
|
\item Abhängige Induktionsvariable: Variable $y$, die in der Schleife durch $y = a \cdot x \pm b$ mit schleifeninvarianten $a$ und $b$ als lineare Funktion aus Induktionsvariable $x$ berechnet wird
|
|
\item Berechnung der Familie einer einfachen Induktionsvariable $x$: Menge der Induktionsvariablen $y$, die mit linearer Funktion $y = c_1 \cdot x \pm c_2$ von $x$ mit schleifeninvarianten $c_1$ und $c_2$ abhängen: \begin{itemize}
|
|
\item Zuweisung der Form $y = c_1 \cdot x \pm c_2$
|
|
\item Zuweisung der Form $y = c_1 \cdot z \pm c_2$, wobei $z \in \mathrm{Familie}(x)$ und \begin{itemize}
|
|
\item keine Veränderung von $x$ zwischen Zuweisung zu $z$ und Zuweisung zu $y$
|
|
\item keine von außerhalb der Schleife erreichende Definition von $z$ erreicht Zuweisung zu $y$
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item Berechnungen der Tripel $(x, c_1, c_2)$ für alle Induktionsvariablen $y$ einer Schleife:\begin{enumerate}
|
|
\item Berechnung von Schleifeninvarianz und erreichenden Definitionen
|
|
\item Bestimmung aller einfachen Induktionsvariablen durch Code-Inspektion (\enquote{Pattern Matching})
|
|
\item Bestimmung aller Variablen $y$ mit einziger (oder identischen) Zuweisung der Form $y = x \pm c$ oder $y = c \cdot x$ mit $x$ Induktionsvariable und $c$ schleifeninvariant:\begin{itemize}
|
|
\item $x$ ist einfache Induktionsvariable:
|
|
\begin{equation*}
|
|
\mathrm{Tripel}(y) = \begin{cases*}
|
|
(x, 1, c) & falls $y = x + c$ oder $y = c + x$\\
|
|
(x, 1, -c)& falls $y = x - c$\\
|
|
(x, c, 0)& sonst ($y = x \cdot c$ oder $y = c \cdot x$)
|
|
\end{cases*}
|
|
\end{equation*}
|
|
\item $x$ ist abhängige Induktionsvariable mit Tupel $(u, d_1, d_2)$:
|
|
\begin{equation*}
|
|
\mathrm{Tripel}(y) = \begin{cases*}
|
|
(u, d_1, d_2 + c) & falls $y = x + c$ oder $y = c + x$\\
|
|
(u, d_1, d_2 - c) & falls $y = x - c$\\
|
|
(u, d_1 \cdot c, d_2 \cdot c_2) & sonst ($y = c \cdot x$ oder $y = x \cdot c$)
|
|
\end{cases*}
|
|
\end{equation*}
|
|
\end{itemize}
|
|
\end{enumerate}
|
|
\item Vereinfachung der Berechnungsvorschrift von Schleifenlaufvariablen pro Iteration (Reduktion der Ausdrucksstärke, \enquote{Strength Reduction}) für jede einfache Induktionsvariable $x$: \begin{enumerate}
|
|
\item Für jede von $x$ abhängige Induktionsvariable $y$ mit Tripel $(x, a, b)$:\begin{enumerate}
|
|
\item Einführung neuer Variable $y'$
|
|
\item Ersetzung der Zuweisung zu $y$ durch $y = y'$
|
|
\item Einfügen der Zuweisung $y' = y' \pm (a \cdot c)$ nach jeder Zuweisung $x = x \pm c$
|
|
\item Einfügen der Zuweisung $y' = x\cdot a + b$ vor dem Schleifenkopf
|
|
\end{enumerate}
|
|
\end{enumerate}
|
|
\item Modifikation von bedingten Sprüngen ggf. möglich
|
|
\item Verringerung der Anzahl von Array-Bereichstests ggf. möglich
|
|
\end{itemize}
|
|
|
|
\subsection{Datenabhängigkeiten in Schleifen und Arrays}
|
|
\begin{itemize}
|
|
\item Schleifenunabhängige Datenabhängigkeiten: existieren auch ohne Schleife (etwa wenn im Rumpf)
|
|
\item Schleifengetragene Datenabhängigkeiten: resultieren ausschließlich aus Schleife (etwa zwischen verschiedenen Iterationen)
|
|
\item Iterationsvektor $i = (i_1, i_2, \textellipsis, i_d)$ für $d$ geschachtelte Schleifen\begin{itemize}
|
|
\item eindeutig für jede Iteration
|
|
\item lexikographische Ordnung auf Iterationsvektoren
|
|
\item $i \angle j$ $\Leftrightarrow$ Iteration $i$ zur Laufzeit vor Iteration $j$
|
|
\end{itemize}
|
|
\item Iterationsraum: Menge aller möglichen Iterationsvektoren
|
|
\item Abhängigkeitsdistanz (bei geschachtelten Schleifen Vektor) $d$: Bei Datenabhängigkeit zwischen Iteration $i_\mathrm{source}$ und $j_\mathrm{target}$ und $i_\mathrm{source} \angle j_\mathrm{target}$, dann $i_\mathrm{source} + d = j_\mathrm{target}$
|
|
\item Abhängigkeitsrichtung: Vergröberung der Abhängigkeitsdistanz mit folgenden Ersetzungen an jeder Position des Vektors: \begin{equation*}
|
|
r_i = \begin{cases*}
|
|
= & falls $0 = d_i$\\
|
|
< & falls $0 < d_i$\\
|
|
> & falls $0 > d_i$
|
|
\end{cases*}
|
|
\end{equation*}
|
|
\item Richtungsvektor: Zusammenfassung aller Abhängigkeitsrichtungen einer Schleife:\begin{itemize}
|
|
\item \enquote{übliche} Zusammenfassungen (z.B. $=$ und $<$ zu $\leq$)
|
|
\item keine Aussage $*$ bei $<$ und $>$
|
|
\end{itemize}
|
|
\item Die Abhängigkeit tragende Schleife $p$ folgt aus der Struktur der Abhängigkeitsdistanzen bei Inkrementschleifen:
|
|
\begin{equation*}
|
|
(\underbrace{d_1, d_2, \textellipsis}_{0}, \underbrace{d_p}_{>0}, \underbrace{\textellipsis, d_n}_{\mathrm{beliebig}})
|
|
\end{equation*}
|
|
\item Parallele Ausführbarkeit aller Iterationen einer Schleife $p$ gegeben, wenn \begin{itemize}
|
|
\item diese keine Abhängigkeit trägt (alle Abhängigkeitsdistanzen haben $d_p = 0$) oder
|
|
\item jede schleifengetragene Abhängigkeit von einer $p$ umgebenden Schleife getragen wird (für jede Abhängigkeitsdistanz $\exists q < p: d_q > 0$)
|
|
\end{itemize}
|
|
\item Parallele Ausführung nicht immer gewinnbringend, da auf Cache-Ebene Abhängigkeiten auftreten können (\enquote{False Sharing})
|
|
\item Optimierungsmöglichkeiten:\begin{itemize}
|
|
\item Skalare Ersetzung von Array-Ausdrücken (\enquote{register pipelining}), wenn: \begin{itemize}
|
|
\item Abhängigkeit wird von innerster Schleife getragen
|
|
\item Konstante Abhängigkeitsdistanz $d$
|
|
\item $d+1$ freie Register
|
|
\end{itemize}\begin{enumerate}
|
|
\item Vor Schleife Initialisierung der Register und \enquote{Abschälen} der ersten $d$ Iterationen
|
|
\item In Schleife Benutzung der Register bei Lesezugriff und Speicherung der Registerinhalte bei Speicherzugriff, sowie am Anfang des Rumpfs \enquote{Aufrücken} der Register
|
|
\end{enumerate}
|
|
\item Skalar-Vervielfachung: Einführung eines Arrays zur Elimination von unnötigen Abhängigkeiten einer Temporärvariable
|
|
\item Verbesserung der zeitlichen Lokalität durch optimierte Registerverwendung
|
|
\item Verbesserung der räumlichen Lokalität durch optimierte Cache-Verwendung
|
|
\item Parallelisierung/Vektorisierung von Schleifen
|
|
\item Daten-/Prozessplatzierung zur Kommunikationsoptimierung
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\subsection{Indexanalyse}
|
|
\begin{itemize}
|
|
\item Bestimmung, ob 2 Array-Zugriffe selbe bzw. unterschiedliche Elemente ansprechen: Grundannahme pessimistisch (gleiches Element)
|
|
\item Für 2 Array-Zugriffe $S1$ $A[f_1(i_1, \textellipsis, i_d), \textellipsis, f_m(i_1, \textellipsis, i_d)]$ und\\
|
|
$S2$ $A[g_1(i_1, \textellipsis, i_d), \textellipsis, g_m(i_1, \textellipsis, i_d)]$ gilt $S1 \delta S2$ $\Leftrightarrow$:\begin{itemize}
|
|
\item mindestens ein Schreibzugriff
|
|
\item $\exists I, J: I=(i_1, \textellipsis, i_d) \angle J =(j_1, \textellipsis, j_d)$ mit $I, J$ innerhalb der Schleifengrenzen (Ungleichunssystem mit Nebenbedingungen)
|
|
\item $\forall p: f_p(I) = g_p(J)$ (Gleichungssystem mit Schleifenlaufvariablen als Variablen und Konstanten aus linearem Index-Ausdruck als Koeffizienten)
|
|
\end{itemize}
|
|
\item Aus Laufzeitgründen lediglich Tests, sonst pessimistische Grundannahme: \begin{itemize}
|
|
\item GGT-Test:\begin{enumerate}
|
|
\item Gleichsetzen der beiden Array-Ausdrücke
|
|
\item Konstante auf eine Seite umformen
|
|
\item Abhängigkeit nur dann möglich, wenn der größte gemeinsame Teiler der Koeffizienten die Konstante teilt
|
|
\item Für verschiedene Arten der Abhängigkeit in obige Kriterien einsetzen
|
|
\end{enumerate}
|
|
\item Ungleichungstest:\begin{enumerate}
|
|
\item Ungleichungen für im Code verwendete Variablen $i$ mit $i_\mathrm{w}$, $i_\mathrm{r}$ für Schreib- und Lesezugriff aufstellen:\begin{enumerate}
|
|
\item Ungleichungen für Schleifengrenzen
|
|
\item Ungleichungen für relative Beziehung von $i_\mathrm{w}$ und $i_\mathrm{r}$
|
|
\end{enumerate}
|
|
\item Gleichung für Zugriff aufstellen und so umstellen, dass 0 auf einer Seite steht
|
|
\item In Gleichung jeweils untere und obere Grenzwerte einsetzen und damit ein Intervall bestimmen
|
|
\item Sofern Intervall nicht 0 enthält, keine Abhängigkeit
|
|
\end{enumerate}
|
|
\item Fourier-Motzkin-Test: \begin{itemize}
|
|
\item Ungleichungssystem in kanonische Form ($\le c$, $c$ Konstante) überführen \begin{itemize}
|
|
\item $\beta < b \cdot z$ untere Schranke für $z$ mit $\beta > 0$
|
|
\item $a \cdot z < \alpha$ obere Schranke für $z$ mit $\alpha > 0$
|
|
\end{itemize}
|
|
\item Mit Fourier-Motzkin-Elimination Variable $z$ eliminieren:
|
|
\begin{equation*}
|
|
a\cdot \beta \leq a \cdot z \cdot b \leq b\cdot \alpha \rightarrow a\cdot \beta \leq b\cdot \alpha
|
|
\end{equation*}
|
|
\item Algorithmus aus Übung: \begin{algorithmic}
|
|
\Repeat
|
|
\State Unbekannte $x_j$ auswählen
|
|
\State $L \gets \lbrace i \mid a_{ij} < 0 \rbrace$
|
|
\State $U \gets \lbrace i \mid a_{ij} > 0 \rbrace$
|
|
\ForAll{$i \in L \cup U$}
|
|
\State Reihe $i$ mit $\vert a_{ij}\vert$ normalisieren
|
|
\EndFor
|
|
\ForAll{$i \in L$}
|
|
\ForAll{$k \in U$}
|
|
\State Füge Ungleichung $A_{[i]} + A {[k]} \leq b_i + b_k$ hinzu
|
|
\EndFor
|
|
\EndFor
|
|
\State Ignoriere/Lösche alle Reihen aus $L \cup U$
|
|
\Until{System aus trivialen Ungleichungen}
|
|
\end{algorithmic}
|
|
\item Kleineres Problem $a\cdot \beta \leq b\cdot \alpha$ rekursiv lösen:\begin{itemize}
|
|
\item keine Lösung $\rightarrow$ unabhängig
|
|
\item Lösung existiert $\rightarrow$ Prüfung, ob auch ganzzahlige Lösung für $a\cdot z\cdot b$ existiert
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
|
|
\subsection{Entfernung von schleifengetragenen Datenabhängigkeiten}
|
|
\begin{itemize}
|
|
\item Legalität: Für jede Datenabhängigkeit muss die relative Reihenfolge auch nach Anwendung der Transformation bzw. Restrukturierung erhalten bleiben, d.h. die entstehenden Abhängigkeits\-distanz\-vektoren dürfen nicht lexikographisch negativ sein und müssen ihre Datenabhängigkeitsart behalten
|
|
\end{itemize}
|
|
|
|
\subsubsection{Schleifentransformationen}
|
|
\begin{itemize}
|
|
\item Erhalten Durchlaufreihenfolge
|
|
\item Neuausrichtung:\begin{itemize}
|
|
\item Verschiebung der Ausführung einer Anweisung um $d$ Iterationen (wobei $d$ konstante Abhängigkeitsdistanz ist)
|
|
\item Bedingte Anweisungen für die ersten und letzten $d$ Anweisungen zur Erhaltung der Semantik
|
|
\end{itemize}
|
|
\item Ausrollen um Faktor $f$: \begin{itemize}
|
|
\item Pro Iteration der neuen Schleife gleich $f$ Iterationen der alten Schleife ausführen
|
|
\item Reduktion des Schleifenoverheads
|
|
\item Vergrößerung des Codes
|
|
\end{itemize}
|
|
\item Bereichtsteilen: \begin{itemize}
|
|
\item Iterationsbereich wird auf zwei Schleifen mit jeweils gleichem Rumpf aufgeteilt
|
|
\item ermöglicht weitere Optimierungen (etwa mit DFA oder Vektorisierung)
|
|
\item Vergrößerung des Codes
|
|
\end{itemize}
|
|
\item Schälen (Spezialfall des Bereichsteilens):\begin{itemize}
|
|
\item erste (oder letzte) Iteration der Schleife werden herausgezogen um spezielle Datenabhängigkeiten zu eliminieren
|
|
\item ermöglicht oft Parallelisierung der Restschleife
|
|
\item ergänzt Neuausrichtung
|
|
\end{itemize}
|
|
\item Produktschleifenbildung:\begin{itemize}
|
|
\item Kombination geschachtelter Schleifen zu einer Schleife durch Multiplikation der Bereiche
|
|
\item Produktgröße oft besser geeignet für Parallelisierung/Vektorisierung
|
|
\item fügt ggf. abhängige Induktionsvariablen ein
|
|
\item verhindert möglicherweise andere Optimierungen
|
|
\end{itemize}
|
|
\item Streifenschneiden:\begin{itemize}
|
|
\item Aufteilen des Schleifenbereichs in mehrere Bereiche (Blöcke, Streifen) bestimmter Größe
|
|
\item verbessert Parallelisierung/Vektorisierung der Schleife
|
|
\item oft nach Produktschleifenbildung
|
|
\item erhöht Schleifenoverhead durch zusätzliche Abhängigkeitsdimension
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\subsubsection{Schleifenrestrukturierungen}
|
|
\begin{itemize}
|
|
\item Ändern Durchlaufreihenfolge
|
|
\item Verschmelzung:\begin{itemize}
|
|
\item Zusammenfassen der Rümpfe mehrerer Schleifen
|
|
\item Voraussetzungen:\begin{itemize}
|
|
\item beide Schleifen haben gleichen Indexbereich
|
|
\item Namensgleichheit beider Laufvariablen kann durch Umbenennung erreicht werden
|
|
\item Bei keiner Skalarnutzung in zweiter Schleife darf es erreichende Definition aus anderer Schleife geben
|
|
\end{itemize}
|
|
\item Legalität: Es darf keine Abhängigkeit zwischen einer Instruktion aus der zweiten Schleife mit einer aus der ersten in einer späteren Iteration entstehen
|
|
\item Reduktion des Schleifenoverheads
|
|
\item größere Grundblöcke erlauben effizientere lokale Optimierungen
|
|
\item ggf. verbesserte zeitliche Lokalität
|
|
\end{itemize}
|
|
\item Rumpfteilen:\begin{itemize}
|
|
\item Aufteilen des Rumpfs einer Schleife auf mehrere Schleifen
|
|
\item Gegenteil der Verschmelzung
|
|
\item Legalität: \begin{itemize}
|
|
\item Anweisungen, die in starken Zusammenhangskomponenten des Abhängigkeitsgraphs der zu teilenden Schleife liegen, dürfen nicht auf verschiedene Schleifen verteilt werden
|
|
\item Reihenfolge der Schleifen muss Abhängigkeiten vor dem Teilen widerspiegeln
|
|
\end{itemize}
|
|
\item kleinere Grundblöcke verringern ggf. Registerdruck
|
|
\item kleinere Rümpfe passen besser in den Instruktionscache
|
|
\item ggf. kann eine der Schleifen parallelisiert/vektorisiert werden
|
|
\end{itemize}
|
|
\item Kachelschneiden: \begin{itemize}
|
|
\item Aufteilen mehrerer geschachtelter Schleifen in Kacheln bestimmter Größe
|
|
\item Legalität: Wenn Schleifenvertauschungen legal sind
|
|
\item Verbesserung der Lokalität
|
|
\item Erlaubt Registerverwendung
|
|
\item Höherer Schleifenoverhead
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\paragraph{Lineare Schleifenrestrukturierungen}
|
|
\begin{itemize}
|
|
\item Schleifenvertauschung:\begin{itemize}
|
|
\item Innere Schleife wird zur äußeren
|
|
\item Erhalt der schleifenunabhängigen Datenabhängigkeiten
|
|
\item Tausch der Einträge der entsprechenden Dimensionen in Richtungsvektoren und Abhängigkeitsdistanzen der schleifengetragenen Datenabhängigkeiten
|
|
\item Legalität: Alle Abhängigkeitsdistanzen (vorher per Definition lexikographisch positiv) müssen auch danach positiv sein
|
|
\item Nach außen Ziehen der abhängigkeitstragenden Schleifen ermöglicht ggf. im Inneren parallelisierbare Schleife mit großer Breite
|
|
\item ggf. Verbesserung der räumlichen oder zeitlichen Lokalität
|
|
\item Korrektur der Indexbereiche bei nicht-rechteckigen Iterationsräumen (ggf. durch Fourier-Motzkin-Elimination)
|
|
\end{itemize}
|
|
\item Richtungsumkehr:\begin{itemize}
|
|
\item Inkrement- in Dekrementschleife umwandeln (oder vice versa)
|
|
\item Voraussetzung: alle Abhängigkeiten müssen von umgebender Schleife getragen werden
|
|
\item ggf. Ermöglichung weiterer Optimierungen wie Verschmelzung
|
|
\end{itemize}
|
|
\item Neigen:\begin{itemize}
|
|
\item Verschiebung des Array-Indexbereichs der inneren Schleife um $f \cdot i$ mit $f$ Neigungsfaktor und $i$ Iterationsvariable der äußeren Schleife
|
|
\item Abzug von $f \cdot i$ bei Verwendungen der inneren Iterationsvariable
|
|
\item Abhängigkeit $(d_1, d_2)$ wird zu $(d_1, d_2 + f \cdot d_1)$ $\rightarrow$ Ermöglichung weiterer Restrukturierungen
|
|
\end{itemize}
|
|
\item Allgemeiner Fall:\begin{itemize}
|
|
\item Transformation der Indexvektoren mit Matrix $U$ mit Eigenschaften (unimodular):\begin{itemize}
|
|
\item $U \in \mathbb{Z}^{n\times n}$
|
|
\item $\exists\, U^{-1} \in \mathbb{Z}^{n\times n}:\, U U^{-1} = I$
|
|
\item Hinreichende Bedingung: $\vert\mathrm{det}(U)\vert = 1$
|
|
\end{itemize}
|
|
\item Legalität: Für alle Abhängigkeitsdistanzen $d$ muss gelten $0 \angle d U$
|
|
\item Vertauschungsmatrix für Dimensionen 2 und 3: \begin{equation*}
|
|
U = \begin{psmallmatrix}
|
|
1 & & & \\
|
|
& 0 & 1 & \\
|
|
& 1 & 0 & \\
|
|
& & & 1
|
|
\end{psmallmatrix}
|
|
\end{equation*}
|
|
\item Richtungsumkehrungsmatrix für Dimension 2: \begin{equation*}
|
|
U = \begin{psmallmatrix}
|
|
1 & 0\\
|
|
0 & -1
|
|
\end{psmallmatrix}
|
|
\end{equation*}
|
|
\item Neigungsmatrix für Faktor $f$ in Dimension 2:\begin{equation*}
|
|
U = \begin{psmallmatrix}
|
|
1 & f\\
|
|
0 & 1
|
|
\end{psmallmatrix}
|
|
\end{equation*}
|
|
\end{itemize}
|
|
\item Gezielte Konstruktion von Transformationsmatrix $U$ zur Ermöglichung bestimmter Optimierungen:\begin{itemize}
|
|
\item Matrix $D$ aus Abhängigkeitsdistanzvektoren
|
|
\item Gesucht: $U^{\mathrm{T}}$ mit $U^{\mathrm{T}} D^{\mathrm{T}} = D^{\mathrm{T}\prime}$, sodass $D^{\mathrm{T}\prime}$ Optimierungsanforderungen erfüllt
|
|
\end{itemize}\begin{enumerate}
|
|
\item Lineares Gleichungssystem $\left( I^{\mathrm{T}} \mid D^{\mathrm{T}} \right)$ zu $\left( U^{\mathrm{T}} \mid D^{\mathrm{T}\prime} \right)$ mit gewünschtem $D^{\mathrm{T}\prime}$ umformen
|
|
\item $U^{-1}$ aus $U$ bestimmen
|
|
\item Transformation der Verwendung der Iterationsvariablen $i, j, \textellipsis$ im Schleifenrumpf wie folgt:
|
|
\begin{equation*}
|
|
\begin{psmallmatrix}
|
|
i\\
|
|
j\\
|
|
\vdots
|
|
\end{psmallmatrix} = U^{-1} \begin{psmallmatrix}
|
|
i'\\
|
|
j'\\
|
|
\vdots
|
|
\end{psmallmatrix}
|
|
\end{equation*}
|
|
\item Anpassung der Schleifengrenzen für $i', j', \textellipsis$ mit Fourier-Motzkin, bei innerster Schleife beginnend
|
|
\end{enumerate}
|
|
\end{itemize}
|
|
\end{document}
|