squalyl (./78) :
d'après ce que j'ai compris on teste des réordonnancements d'instructions pour trouver la config qui améliore l'allocation, en calculant un "score" a chaque essai, en faisant des "mutations" de la config courante, puis on relance le programme et on cherche ce qui améliore le score.

je crois. peut être c'est ça.

Le réordonnancement du code est en soit une autre optimisation. Elle n'est pas indispensable pour faire une allocation de registres ?

Une autre idée, je ne sais pas si elle apporterait un gain sur d'autres optimisations ?
Pour le ré ordonnancement du code on créer cette fois un graphe de dépendance des lignes d'instructions. Connaissant les dépendances entres instructions, on en déduit des blocs ainsi que des optimisations. Sur un processeur avec pipeline c'est indispensable mais sur un processeur comme le 68000 ça permet juste de trouver une instruction ou un ensemble d'instructions capable de remplacer un bloc plus efficacement (moins de cycles). En gros l'idée est d'associer des modèles de code optimisés suivant un automate de succession d'instructions. Le réordonnancement sur 68000 n'apporterai pas grand chose je pense, c'est plutôt les optimisations combinatoires qui donneraient de meilleures résultats.

Je n'ai pas regardé l'algo génétique en détail mais bon une allocation de registres simple devrait déjà largement suffire surtout sur un 68000.