In einer Funktion ist die Zahl gleichzeitig lebendiger Werte an der ungünstigsten Stelle 5. Wie viele Register werden mindestens benötigt, um alle Werte ohne Spill in Registern zu halten, wenn der Interferenzgraph in einem einfachen Fall keine weiteren Einschränkungen außer diesen 5 erzeugt?

Antwort: A. 5

Die fünf gleichzeitig lebendigen Werte interferieren alle miteinander, sodass im Interferenzgraphen die fünf Knoten durch Kanten vollständig verbunden sind (vollständiger Graph) und zum Färben mindestens fünf Farben nötig sind. In einfachen Fällen wie linearem Code, in dem sich Lebensdauern als Intervalle darstellen lassen, kann mit so vielen Farben gefärbt werden, wie es höchstens gleichzeitig lebendige Werte gibt, sodass fünf Register genügen. Mit vier wäre irgendwo ein Spill, also das Auslagern eines Werts in den Speicher, nötig. Zehn wäre mehr als nötig.