%% -*- mode: latex; TeX-master: "compilerbau.tex"; -*-

\begin{slide}{Registervergabe}

\kopf{$ $Id: reg.tex,v 1.1 2011-10-16 14:06:16 waldmann Exp $ $}

benötigen Speicher für 
\begin{itemize}\itemsep 0pt
\item lokale Variablen und
\item Werte von Teilausdrücken (wg. Linearisierung)
\end{itemize}
am liebsten in Registern (ist schneller als Hauptspeicher)

es gibt aber nur begrenzt viele Register.

\bigskip

Zwischencode-Generierung für ``unendlich'' viele symbolische Register,
dann Abbildung auf Maschinenregister und (bei Bedarf) Hauptspeicher
(register spilling).

\end{slide}

\begin{slide}{Register-Interferenz-Graph}

(für einen basic block)
\begin{itemize}
\item
Knoten: die symbolischen Register $r_1, r_2, \ldots$
\item
Kanten: $r_i \leftrightarrow r_k$, 
falls  $r_i$ und $r_k$ gleichzeitig lebendig sind.

(lebendig: wurde initialisiert und wird noch gebraucht)
\end{itemize}
finde Knotenfärbung 
(d. i. Zuordnung $c$: symbolisches Register $\to$ Maschinenregister)
mit möglichst wenig Farben (Maschinenregistern), für die

$\forall (x,y) \in E(G): c(x) \neq c(y)$.

Ist algorithmisch lösbares, aber schweres Problem (NP-vollständig)

\end{slide}

\begin{slide}{Register-Graphen-Färbung (Heuristik)}

Heuristik für Färbung von $G$:
\begin{itemize}\itemsep 3pt
\item wenn $|G|=1$, dann nimm erste Farbe
\item wenn $|G|>1$, dann 
  \begin{itemize}
  \item wähle $x = $ irgendein Knoten mit minimalem Grad,
  \item färbe $G\setminus\{x\}$
  \item gib $x$ die kleinste Farbe, die nicht in Nachbarn $G(x)$ vorkommt.
  \end{itemize}
\end{itemize}

Aufgabe: finde Graphen $G$ und zulässige Reihenfolge der Knoten,
für die man so keine optimale Färbung erhält.

Falls dabei mehr Farben als Maschinenregister,
dann lege die seltensten Registerfarben in Hauptspeicher.

(Es gibt bessere, aber kompliziertere Methoden.)

\end{slide}
