geogeo (./76) :
Oui mais le calcul reste toujours NP-complet ?

Il y a des heuristiques approximatives, comme d'habitude.

Mais il y a aussi d'autres algorithmes heuristiques pour l'allocation de registres qui ne passent pas par de la coloration de graphes (ni des algorithmes génétiques d'ailleurs, ça, c'est une technique très générale qui peut être utilisée pour pratiquement tout ce qui touche à l'optimisation (au sens mathématique, ce qui est aussi bien plus vaste comme domaine que l'optimisation de code!), donc forcément aussi ici, mais ce n'est pas la seule).