Dans une fonction, le nombre maximal de valeurs vivantes simultanément est de 5. Dans le cas simple où le graphe d'interférence ne crée pas d'autre contrainte que ces 5 valeurs, combien de registres faut-il au minimum pour placer toutes les valeurs en registre sans déversement ?

Réponse : A. 5

Les 5 valeurs vivantes simultanément interfèrent toutes entre elles ; elles forment dans le graphe d'interférence 5 nœuds tous reliés (graphe complet), dont la coloration exige au moins 5 couleurs. Dans le cas simple où les intervalles de vie se représentent comme des intervalles, comme dans un code linéaire, le graphe se colore avec un nombre de couleurs égal au maximum de valeurs vivantes simultanément ; 5 registres suffisent donc. Avec 4, il faudrait quelque part déverser une valeur en mémoire. 10 est plus que nécessaire.