Sélection d'instructions ------------------------ Langage source (après élimination du pattern-matching, introduction des fermetures, et explicitation du tagging et du boxing): Programmes: let rec f (x1, ..., xn) = e and g (y1, ..., ym) = e' and ... in e Expressions: e ::= x variables | 0 | 1 | 2 | false | true | "hello" | ... constantes | f adresses de fonctions | e(e1, ..., eN) appel de fonction | primop(e1, ..., eN) opération primitive | let x = e1 in e2 liaison locale | if e1 then e2 else e3 conditionnelle | case e of cst1 -> e1 | ... | cstN -> eN conditionnelle multiple | loop e end boucle infinie | catch e1 with e2 exceptions statiques | exit ("goto" propre) | try e1 with x -> e2 exceptions dynamiques primop ::= +i | -i | *i | /i | ... arithmétique entière | +f | -f | *f | /f | ... arithmétique flottante | =i | <>i | f | catch loop if e1 then e2 else exit end with () - pour le partage de code dans les "and" et "or" séquentiels if e1 && e2 then e3 else e4 --> (naif) if e1 then if e2 then e3 else e4 else e4 (duplique e4) (meilleur) catch if not e1 then exit; if not e2 then exit; e3 with e4 Jeux d'instructions: -------------------- * Machines à pile: une pile (de taille non bornée) toutes les opérations s'effectuent sur les mots au sommet de la pile Ex: addition: dépiler x dépiler y empiler x+y Ex: appel de fonction e(e1, ..., eN) empiler eN ... empiler e1 empiler e CALL (dépile une adresse de code et s'y branche) Pour les variables: accès direct à une profondeur N acc(N): empiler une copie du N-ième mot à partir du sommet. Modèle peu employé dans les "vrais" processeurs (exceptions: Transputer, partie flottante de l'Intel x86), mais courant dans les machines virtuelles (Pascal P-code, Java VM, machine abstraite Caml Light) car facile à interpréter par un programme C. * Machines à registres: - un certain nombre de registres (8 - 64), souvent divisés en registres entiers et registres flottants - les opérations prennent leurs arguments en registres et stockent leur résultat dans un registre Exple: loadconst r, cst r <- cst move r1, r2 r1 <- r2 loadword r1, r2 r1 <- mot à l'adresse r2 add r1, r2, r3 r1 <- r2 + r3 addi r1, r2, cst r1 <- r2 + cst Variantes: 3 adresses: add r1, r2, r3 r1 <- r2 + r3 2 adresses: add r1, r2 r1 <- r1 + r2 RISC: les accès à la mémoire passent forcément par un registre CISC: certaines opérandes d'une instruction peuvent être en mémoire add r1, (r2) r1 <- r1 + mot à l'adresse r2 add (r1), r2 mot à l'adresse r1 <- ce mot + r2 Généralement: CISC = 2 adresses et RISC = 3 adresses. Sélection d'instructions pour les expressions et le "let": ---------------------------------------------------------- Le pons asinorum: évaluation d'une expression arithmétique sur une machine à pile [cst] = loadconst cst [prim(e)] = [e]; op (correspondance primitives <-> op) [prim(e1, e2)] = [e1]; [e2]; op (correspondance primitives <-> op) Si la machine a des instructions complexes, on fait un pattern-matching. P.ex.: [+f(*f(e1, e2), e3)] = [e1]; [e2]; [e3]; FMULADD Extension aux variables et au "let": rho = une "carte" de la pile, e.g. *; x; *; *; y [cst]_rho = loadconst cst [prim(e)]_rho = [e]_rho; op [prim(e1, e2)]_rho = [e1]_rho; [e2]_{*;rho}; op [x]_rho = acc(pos(x, rho)) avec pos(x, x;rho) = 1 pos(x, y;rho) = 1 + pos(x,rho) [let x = e1 in e2]_rho = [e1]_rho; [e2]_{x;rho}; drop Extension aux structures de contrôle: voir plus loin. Passage à une machine à registres: on utilise les registres pour représenter la pile. R: ensemble de registres inutilisés r: registre destination rho: carte nom de variable -> numéro de registres [cst]_rho,R,r = loadconst r, cst [prim(e)]_rho,R,r = [e]_rho,R,r; op r, r [prim(e1,e2)]_rho,R,r = [e1]_rho,R,r1; [e2]_rho,R\{r1},r2; op r, r1, r2 où r1, r2 sont choisis dans R, et r1 <> r2 ou bien [prim(e1,e2)]_rho,R,r = [e2]_rho,R,r2; [e1]_rho,R\{r2},r1; op r, r1, r2 [x]_rho,R,r = move r, rho(x) [let x = e1 in e2]_rho,R,r = [e1]_rho,R,r'; [e2]_rho,R\{r'},r où r' est choisi dans R Problème: on peut tomber à cours de registres! Algorithme d'Ershov (pour les expressions arithmétiques): évaluation d'une expression dans le nombre minimal de registres nécessaires. on définit la complexité d'une expression |e| par: |cst| = 1 |prim(e)| = |e| |prim(e1, e2)| = max(|e1|, |e2|) si |e1| <> |e2| = 1 + |e1| si |e1| = |e2| Proposition: |e| est le nombre minimal de registres nécessaires pour évaluer e. 1- On peut évaluer e avec |e| registres: utiliser le schéma précédent et pour les expressions binaires, évaluer la sous-expression la plus complexe d'abord, c.a.d. [prim(e1,e2)]_rho,R,r = [e1]_rho,R,r1; [e2]_rho,R\{r1},r2; op r, r1, r2 si |e1| >= |e2|, et sinon [prim(e1,e2)]_rho,R,r = [e2]_rho,R,r2; [e1]_rho,R\{r2},r1; op r, r1, r2 Dans le premier cas, le nombre de registres nécessaires est max(|e1|, 1 + |e2|) et dans le second cas, max(|e2|, 1 + |e1|) Le min de ces deux quantités est bien égal à max(|e1|, |e2|) si |e1| est différent de |e2|, et |e1| + 1 si |e1| = |e2|. 2- Toute suite d'instructions qui évalue e va prendre au moins autant de registres qu'une suite qui évalue entièrement une des sous-expr, puis l'autre (suite séquentielle). 3- Une suite séquentielle utilise au moins |e| registres. [Pour une preuve complète, étendue à des opérations à plus de 2 arguments, voir Aho et Johnson, "Optimal code generation for expression trees", JACM 23(3), 1976] Très efficace en pratique: toutes les expressions arithmétiques usuelles s'évaluent dans 4 registres au plus. Exercice: trouver une expression qui nécessite 5 registres. L'algorithme d'Ershov ne s'étend pas aux expressions avec "let": let x = e1 in let y = e2 in x + y + e3 Si on applique la stratégie ``la plus grosse sous-expression d'abord'', on obtient: calculer e1 dans r1 calculer e2 dans r2 sans toucher à r1 calculer e3 dans r3 sans toucher à r1,r2 add r1, r1, r2 add r1, r1, r3 Mais il y a des manières de faire le calcul qui laissent plus de registres libres pour calculer e3 (même si on s'impose l'ordre de calcul du "let"): calculer e1 dans r1 calculer e2 dans r2 sans toucher à r1 add r1, r1, r2 (* r2 redevient libre *) calculer e3 dans r2 sans toucher à r1 add r1, r1, r2 Produire du code avec "let" = produire du code pour une expression avec partage (dag). Produire du code optimal pour un dag est NP-dur [Aho, Johnson, Ullman, "Code generation for expressions with common subexpressions", JACM 24(1), 1977]. * Approche plus moderne: séparer la sélection d'instructions de l'affectation de registres ==> utilisation de pseudo-registres en nombre infini. On peut quand même utiliser le critère de taille comme heuristique pour choisir l'ordre d'évaluation. Une deuxième passe (l'allocation de registres) va examiner les durées de vies des pseudo-registres et en déduire une affectation de registres de bonne qualité. Représentations du contrôle --------------------------- 1- Comme dans les machines: suite linéaire d'instructions étiquettes goto et goto conditionnel [if e1 then e2 else e3]_rho,r --> [e1]_rho,r1 branchif r1, L [e3]_rho,r branch L' L: [e2]_rho, r L': suite du programme Problème: difficile à optimiser. P.ex. pour répondre à la question "quelles sont tous les chemins qui peuvent arriver sur l'étiquette L", il faut parcourir tout le programme. 2- Graphe de flot: noeuds = instructions arc de A vers B si B peut s'exécuter après A instructions "normales": un seul arc de sortie conditionnelles: 2 ou plusieurs arcs de sortie instructions finales (return, raise): pas d'arcs de sortie [e1; e2]_rho,r = ... [if e1 then e2 else e3]_rho,r = ... [loop e end]_rho,r = ... [catch e1 with e2]_rho,r = ... Variante: on regroupe en blocs de base (basic blocks) les séquences maximales d'instructions telles que toutes les instructions intermédiaires ont exactement 1 arc entrant et 1 arc sortant. Juste avant d'émettre le code machine: on linéarise le graphe en introduisant des gotos et des étiquettes. 3- Représentation structurée du contrôle: e ::= r <- op(r_1, ..., r_n) e1; e2 if r then e1 else e2 case r in cst1 -> e1 | ... | cstN -> eN loop e end catch e1 with e2 try e1 with r -> e2 Avantage: certaines analyses sont plus simples sur cette forme. Inconvénient: moins expressif que le graphe de flot? Quelques notions sur les graphes de flot: ---------------------------------------- Un noeud A domine un noeud B si tous les chemins de la racine vers B passent par A. Exemples: A domine A. Si A est en séquence avec B, A domine B. Si autre arc menant à B: A ne domine pas B. L'en-tête d'une boucle domine toutes les instructions du corps de la boucle. Un arc arrière (back edge) est un arc B --> A tel que A domine B. Exemple: la boucle "loop". Dans ce cas, A est un point d'entrée dans une boucle. Le corps de la boucle est A plus tous les noeuds C tels qu'il existe un chemin C --> B ne passant pas par A. Propriété intéressante: deux boucles qui n'ont pas le même point d'entrée sont ou bien disjointes, ou bien l'une est entièrement contenue dans l'autre. Problème: il y a des calculs infinis qui ne sont pas des boucles au sens précédent. Exemple: goto de l'extérieur d'une boucle vers le milieu de la boucle. C'est ennuyeux pour les transformations de boucles, en particulier le déplacement des invariants de boucles. Définition: un graphe de flot est réductible si l'ensemble des arcs avant [arcs non arrières] forme un graphe acyclique. Autrement dit, tous les cycles du graphe de flot passent par au moins un arc arrière. Les graphes réductibles sont donc ceux qui ne comportent que des boucles "simples". Exemple: boucles while, do...while, avec sorties au milieu. Plus généralement: tout graphe de flot obtenu à partir de constructions structurées est réductible. La réciproque est également vraie, mais difficile à prouver. Théorème: tout graphe de flot réductible est exprimable avec les constructions structurées de contrôle (Il faut un "catch" multiple, i.e. catch ... exit lbl1 ... exit lbl2 ... exit lbl3 ... with lbl1 -> ... | lbl2 -> ...) Schéma de la preuve: - on identifie les corps de boucles - pour chaque corps de boucle: * étiqueter les arcs sortants de la boucle (lbl1 ... lblN) * remplacer la boucle par catch loop ... exit lbl1 ... exit lblN end with lbl1 -> ... | lbl2 -> ... - lorsque toutes les boucles ont été remplacées ainsi: le reste du graphe est acyclique, il existe donc un terme structuré équivalent qui décrit le même calcul [sans préservation du partage: facile; avec préservation: plus difficile].