(für einen basic block)
Knoten: die symbolischen Register r1, r2,...
Kanten: ri rk, falls ri und rk gleichzeitig lebendig sind.
(lebendig: wurde initialisiert, und wird noch gebraucht)
finde Knotenfärbung (d. i. Zuordnung c: symbolisches Register Maschinenregister) mit möglichst wenig Farben (Maschinenregistern), für die
(x, y) E(G) : c(x) c(y).
Ist algorithmisch lösbares, aber schweres Problem (NP-vollständig)