Hmm je vois. Pour la coloration ça ok c'est un autre problème. A priori j'aurais tendance à tenter une heuristique SLS, faudrait voir ce que ça donne.
Mais concernant le graphe en lui même il faut donc créer un sommet pour toute variable (incluant les constantes au sens registre = constante) et ensuite relier d'un arc celles qui sont modifiées alors qu'une autre peut toujours être utilisée par la suite, c'est ça?
Ensuite si on trouve plus de n couleurs (pour n registres sur la machines) alors il faut commencer à déterminer quels registres peuvent être "lâchés" (dans le cas de constantes on peut les recharger facilement) ou poussés dans la pile (recalculer la valeur contenue prendrait plus de temps qu'empiler / désempiler ou bien aurait des effets de bord). C'est ça?
Après le réordonnancement ça je trouve bizarre de tout tester comme un bourrin, surtout qu'il y a une énormité de combinaisons possibles non?