Allocation de registres ----------------------- Situation courante: - une suite d'instructions ou pseudo-instructions du processeur - opérant sur des pseudo-registres en nombre infini - avec le flot de contrôle représenté d'une manière ou d'une autre L'allocation de registres consiste à affecter à chaque pseudo-registre un registre du processeur, ou, si impossible, un emplacement dans la pile (dans le bloc d'activation de la fonction). Exemples d'instructions: load, store arithmétique entière arithmétique flottante comparaisons appel de fonctions (du langage, ou fonctions externes) Exemples de pseudo-instructions: allocation d'un bloc dans le tas branchement à N sorties Certaines instructions ne peuvent pas opérer sur n'importe quels registres. Exemple 1: les conventions d'appels de fonctions. Les arguments et les résultats doivent être passés dans certains registres conventionnels [au moins lorsque l'appelé et l'appelant n'ont pas été compilés ensemble]. Exemple: le processeur Alpha de Digital arguments entiers dans $16 - $21 arguments flottants dans $f16 - $f21 arguments supplémentaires dans la pile résultat entier dans $0, flottant dans $f0 Solution: utiliser des pseudo-registres phi(R) représentant les registres réels R et ajouter des "move" autour de l'instruction d'appel: au lieu de r3 <- call "function_name" (r1, r2) on génère phi($16) <- r1 phi($17) <- r2 phi($0) <- call "function_name"(phi($16), phi($17)) r3 <- phi($0) Exemple 2: la division entière de l'Intel x86: argument dans EAX, résultat dans EAX. Même astuce: au lieu de r3 <- idiv (r1, r2) on génère phi(EAX) <- r1 phi(EAX) <- idiv (phi(EAX), r2) r3 <- phi(EAX) Exemple 3: les instructions deux adresses: résultat et argument 1 doivent être au même endroit au lieu de r3 <- add (r1, r2) on génère r3 <- r1 r3 <- add (r3, r2) (En supposant r3 <> r2. Si r3 = r2, on est déjà en forme "deux adresses".) Notion sémantique d'interférence: --------------------------------- Deux pseudoregistres r1 et r2 interfèrent s'il existe un point A d'une exécution possible de la fonction tel que: 1- r1 et r2 ont déjà été définis 2- r1 et r2 seront utilisés par la suite 3- r1 et r2 ne contiennent pas la même valeur. [Notion hautement indécidable; on en fera des approximations plus tard.] Remarque fondamentale: deux pseudo-registres qui n'interfèrent pas peuvent être mis dans le même registre physique. Plus formellement: une affectation de registres est une fonction F: pseudo-registres --> registres physiques telle que: 1- si r1 et r2 interfèrent, F(r1) <> F(r2) 2- pour tout registre physique R, F(phi(R)) = R Approximations de l'interférence: -------------------------------- On dit qu'un pseudoregistre r est vivant en A le long d'un chemin START -> A -> END si: 1- r est défini avant A r <- op(....) 2- r est utilisé après A ... <- op(... r ...) 3- r n'est pas défini entre A et sa prochaine utilisation Ce sont des notions strictes: r n'est pas vivant si A est une définition de r ou une dernière utilisation de r. On verra plus tard comment calculer efficacement tout ça. Deux pseudoregistres r1 et r2 interfèrent s'il existe un point A du programme tel que 1- r1 est vivant en A 2- r2 est vivant en A 3- r1 et r2 ne sont pas copies l'un de l'autre (c.a.d. les définitions de r1 et r2 qui atteignent le point A ne sont pas toutes de la forme r1 <- r2 ou r2 <- r1) Le graphe d'interférences: -------------------------- C'est un graphe non orienté dont les noeuds sont les pseudo-registres, et contenant un arc r1 <-> r2 ssi r1 et r2 interfèrent. Construction efficace du graphe d'interférences: Pour chaque point A du programme on suppose donné l'ensemble V(A) des pseudoregistres vivants en A. Pour chaque point A: 1) Si A = (r1, ..., rN) <- op(r1', ..., rM') avec op <> move: - ajouter les arcs { ri <-> v | v in V(A), i = 1..N, ri <> r } - si N >= 2 ajouter les arcs { ri <-> rj | i,j = 1..N, ri <> rj } 2) Si A = r <- r' (une instruction move): - ajouter les arcs { r <-> v | v in V(A), v <> r, v <> r' } Preuve de correction: supposons que r1 et r2 interfèrent. On a un point A tel que r1 et r2 sont vivants en A, et de plus r1 n'est pas copie de r2. Quitte à échanger les rôles de r1 et r2, on a donc un chemin de la forme: START ----> def r1 --> def r2 --> A --> utilise r2 et r1 ---> END ^^^ ^^^ pas d'autres defs de r1, r2 (Si un tel chemin n'existait pas, ça veut dire que r1 et r2 seraient définis sur des chemins disjoints menant à A, puis utilisés ensuite: if (cond) { r1 <- ... } else { r2 <- ... } A: utiliser r1 ou r2 C'est impossible dans un langage qui garantit que les variables sont toujours définies avant d'être utilisées.) On montre qu'il existe forcément un arc r1 <-> r2 dans le graphe d'interférence construit par l'algorithme en raisonnant par cas sur l'instruction D2 qui définit r2: - si c'est la même instruction qui définit r1: c'est bon, car on a ajouté des arcs entre tous les registres résultats de D2 deux à deux - sinon, si D2 n'est pas un move: on a ajouté un arc r2 <-> v pour tout v vivant en D2, et r1 est vivant en D2. - si c'est un move r2 <- r3: on a r3 <> r1 car sinon r1 et r2 seraient copie l'un de l'autre. Comme on a ajouté un arc r2 <-> v pour tout v in D2 \ {r3}, on a bien un arc r2 <-> r1. Autres utilisations du graphe d'interférences: ---------------------------------------------- * Pour refléter des contraintes supplémentaires sur l'affectation de registres. Exemple: registres caller-save. Les conventions d'appel spécifient quels registres peuvent être détruits par la fonction appelée [caller-save] quels registres doivent être préservés par la fonction appelée [callee-save] Pour tout appel de fonction A, ajouter des arcs entre V(A) et { phi(R) | R est caller-save } * Pour éliminer les moves inutiles (coalescing): Si A: r <- r' et que r et r' n'interfèrent pas, alors on peut identifier r et r' dans tout le programme et ne pas effectuer l'instruction A. [On met à jour ensuite le graphe d'interférence.] Efficace pour calculer les résultats ``dans les bons registres'' (targeting): phi(R1) <- r phi(R1) <- call "function" (phi(R1)) r' <- phi(R1) Si possible, r et r' vont être fondus avec phi(R1). Coloriage du graphe d'interférences: ------------------------------------ Une affectation de registres F est correcte si: 1- F(r1) <> F(r2) s'il existe un arc r1 <-> r2 dans le graphe d'interférences 2- pour tout registre physique R, F(phi(R)) = R C'est un problème de coloriage de graphe. Beaucoup étudié: 1) k-colorabilité est NP-complet pour k >= 3. (3-colorabilité est équivalent à 3SAT.) Donc, déterminer si un programme peut tourner avec k registres aussi. 2) Des heuristiques en temps linéaire. Heuristique 1 ------------- Tant qu'il existe un noeud N non colorié: - regarder tous ses voisins déjà coloriés - s'ils laissent au moins une couleur libre, l'affecter à N - si toutes les couleurs sont prises, échouer. Pas très fin: A <---> B <---> C est 2-colorable, mais si on affecte 1 à A et 2 à C, on ne peut pas colorier B. Heuristique 2 ------------- - Comme ci-dessus, mais choisir la plus petite couleur libre. Réussit à 2-colorier A <---> B <---> C. Mais: contre-exemple (3-colorabilité). Heuristique 3 ------------- Observation: si tous les noeuds sont de degré < k, le graphe est k-colorable. (condition suffisante mais pas nécessaire). Observation: si G a un noeud N de degré < k et si G \ {N} est k-colorable, alors G est k-colorable. Passe 1: Tant que le graphe contient un noeud de degré < k, l'enlever du graphe et le mettre sur une pile. Passe 2: Colorier les noeuds restants avec une des heuristiques ci-dessus. [peut échouer] Passe 3: Dépiler les noeuds de la pile et leur attribuer une couleur que leurs voisins n'ont pas [n'échoue jamais] Spilling: --------- Que faire avec les pseudoregistres qu'on n'arrive pas à colorier? Les stocker dans la pile (spilling). Quand on rencontre un pseudoregistre non-colorable r : - lui réserver un emplacement dans la pile P(r) - remplacer chaque définition de r (... r ...) <- op(....) par (... r' ...) <- op(....) où r' est un nouveau temporaire store(r', P(r)) - remplacer chaque utilisation de r ... <- op (... r ...) par r' <- load(P(r)) ... <- op (... r' ...) - pour les moves: r <- ... devient store(..., P(r)) ... <- r devient ... <- load(P(r)) Ensuite: recalculer le graphe d'interférence et re-colorier. Exemple: on considère le programme a <- ... b <- ... c <- ... d <- ... x <- a + b x <- x + c x <- x + d Il n'est pas possible d'exécuter ce programme avec seulement trois registres (a, b, c, d interfèrent 2 à 2). Si on essaye de mettre a en pile: a <- ... store(a, P(a)) b <- ... c <- ... d <- ... r <- load(P(a)) x <- r + b x <- x + c x <- x + d Ce n'est pas mieux, car b, c, d, r interfèrent 2 à 2. Mieux: mettre c en pile a <- ... b <- ... c <- ... store(c, P(c)) d <- ... x <- a + b r <- load(P(c)) x <- x + r x <- x + d Critères de choix d'un registre à mettre en pile: ------------------------------------------------- 1- peu d'utilisations (chaque utilisation coûte un "load") 2- degré élevé (beaucoup de voisins dans le graphe d'interférences) 3- longues périodes d'inactivité Splitting: --------- Pour éviter d'accéder à la pile P(r) à chaque définition et à chaque utilisation: "casser" l'utilisation de r en plusieurs pseudo-registres, reliés par des moves. Exemple: a <- ... ... <- ... a ... ... <- ... a ... ... <- ... a ... Après mise en pile de a: a <- ... store(a, P(a)) r <- load(P(a)) ... <- ... r ... r <- load(P(a)) ... <- ... r ... r <- load(P(a)) ... <- ... r ... Mieux: transformer le programme initial en a <- ... a' <- a ... <- ... a' ... ... <- ... a' ... ... <- ... a' ... Après mise en pile de a: a <- ... store(a, P(a)) a' <- load(P(a)) ... <- ... a' ... ... <- ... a' ... ... <- ... a' ... C'est plus efficace si a' peut effectivement être mis en registre.