Register-Interferenz-Graph

(für einen basic block)

Knoten: die symbolischen Register r1, r2,...

Kanten: ri $ \leftrightarrow$ rk, falls ri und rk gleichzeitig lebendig sind.

(lebendig: wurde initialisiert, und wird noch gebraucht)

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)



Johannes Waldmann 2005-01-28