Registervergabe und Graphenfärbung

Gegeben Programm (das Let innerhalb einer Abstraktion), konstruiere Graph G = (V, E)

• Knoten V: die lokal gebundenen Namen
• Kanten E: falls x und y gleichzeitig benötigt, dann xy∈E.

gesucht ist konfliktfreie Färbung mit geringer Farbzahl:

• Farben C: (virtuelle) Register
• Färbung: Abbildung f : V→C
• konfliktfrei: ∀xy∈E : f (x)≠f (y)