Typiquement, dans un premier temps le code est généré en utilisant des "variables temporaires" au lieu des registres de la machine (ie on suppose qu'on a en fait une infinité de registres).

Ensuite, il y a une analyse de durée de vie des temporaires qui permet de construire le graphe d'interférences.
La construction de ce graphe est assez simple:
- chaque instruction lit un ensemble de temporaires et écrit un ensemble de temporaires
- un temporaire est vivant s'il existe une instruction suivante dans le flot de controle qui le lit, sinon il est mort -> définition des intervalles de durée de vie
- le graphe a pour sommets les temporaires. une arete relie deux temporaires si leur intervalle de durée de vie se chevauche

Et après la coloration intervient.

Ca, c'est le schéma classique de génération de code tel qu'on l'enseigne à l'école (cf par exemple le Dragon book)
Mais évidemment, il y a surement d'autres approches.

Je crois me souvenir qu'il y a des cas où l'allocation se fait bien (ça parlait en vrac de chordal graphs, de SSA form, ...)