#Génération de codeCopier le lien

Objectifs d'apprentissage

• Traduire un AST en IR à pile par parcours post-ordre, et prouver l'équilibre pile/consommation.
• Mapper variables → indices et vérifier la correction d'un codegen par exécution comparative.
• Connaître constant folding, élimination de code mort et allocation de registres comme passes classiques.

Prérequis: pages Lexing, Parsing et AST (le fil conducteur Expr est supposé acquis). Le code ci-dessous reprend les nœuds num, var, opérateurs binaires, let/assign, expr, program.

#Étape 1: de l'arbre à la pile (IR)Copier le lien

WASM est une machine à pile: chaque instruction consomme ses opérandes au sommet de la pile et y pousse son résultat. Traduire un AST dans ce modèle tient en une règle unique: pour un nœud ('+', g, d), émettre le code de g, puis celui de d, puis l'opération. C'est le parcours post-ordre de l'arbre.

Pour le fil conducteur 2*(3+4)-5:

1push 2      pile: 22push 3      pile: 2 33push 4      pile: 2 3 44add         pile: 2 75mul         pile: 146push 5      pile: 14 57sub         pile: 9

Invariant à retenir: après l'exécution du code d'une expression, la pile contient exactement un résultat de plus qu'avant. Chaque opération binaire consomme deux valeurs et en produit une. Vérifier cet invariant à chaque construction de fonction est la façon la plus simple d'éviter les modules WASM rejetés à la validation.

#Étape 2: variables et programme completCopier le lien

Les variables du langage deviennent des variables locales WASM, adressées par indice. Le codegen maintient un dictionnaire slot (nom → indice) construit au fil des déclarations, comme l'environnement de l'interpréteur de la page AST. La correspondance est directe: env[nom] = valeur côté interpréteur devient local.set $slot côté codegen.

Deux subtilités du code:

• drop: en WASM, une fonction doit finir avec une pile contenant exactement son résultat déclaré. Un programme à trois instructions produit trois valeurs; on jette les deux premières pour n'en garder qu'une.
• Ordre gauche puis droite: l'ordre d'évaluation des opérandes est fixé par le codegen. Ici gauche-à-droite, comme dans quasiment tous les langages impératifs; l'inverse serait aussi valide en pile mais changerait l'ordre des effets de bord.

#Étape 3: assembler le module WATCopier le lien

L'IR à pile se place telle quelle dans une fonction WASM. Il reste à déclarer les variables locales (autant de i32 que de slots) et l'export:

1(module2  (func (export "main") (result i32)3    (local i32 i32)          ;; slots 0 (x) et 1 (y)4    i32.const 55    local.set 06    local.get 07    i32.const 28    i32.mul9    local.set 110    local.get 111    i32.const 312    i32.add))                ;; pile finale: [13] = le résultat

Ce module est l'équivalent exact du programme interprété dans la page AST: il renvoie 13. La structure d'un module WASM comporte des sections: types (signatures), fonctions, mémoire, exports, code. Le WAT ci-dessus les laisse implicites; l'assemblage wat2wasm les matérialise en binaire.

#Test de correction: exécution comparativeCopier le lien

Le test standard d'un compilateur: comparer l'interpréteur et le code compilé sur un corpus. Avec les pièces des pages précédentes:

1# corpus = liste de programmes Expr (parse('...') ou AST directs)2for ast in corpus:3    out = []4    expected = run(ast, {})                      # interpréteur (page AST)5    got = simulate(compile_expr(ast), nb_locals) # petite VM à pile6    assert got == expected, f"divergence sur {ast}: {got} != {expected}"

Écrire simulate (une boucle qui exécute i32.const, local.get/set, drop et les quatre opérations sur deux structures stack et locals) est l'exercice le plus formateur de cette page: c'est une VM WASM en miniature, et elle transforme le codegen en propriété testable plutôt qu'en acte de foi.

#Combien de registres? L'algorithme de Sethi-UllmanCopier le lien

Tout ce qui précède supposait une pile infinie. Dès que la cible est une machine à registres — et non plus une machine à pile comme WASM — une question nouvelle apparaît: combien de registres faut-il pour évaluer une expression, et comment l'évaluer pour en utiliser le moins possible? C'est l'objet de l'algorithme de Sethi-Ullman, aussi appelé nombres d'Ershov. Il est au cœur des cours de compilation, et il est directement évaluable sur une expression: c'est l'un des rares points du pipeline où l'on peut prouver l'optimalité d'un codegen.

#Le nombre d'ErshovCopier le lien

On décore chaque nœud de l'arbre par un entier, de bas en haut:

• une feuille (variable ou constante) reçoit le nombre $1$;
• un nœud interne dont les fils portent $l$ et $r$ reçoit

$e(n) = \begin{cases} l + 1 & \text{si } l = r \\ \max(l, r) & \text{si } l \neq r \end{cases}$

Le nombre obtenu à la racine est exactement le nombre minimal de registres nécessaires pour évaluer l'expression sans code de vidage (spill).

L'intuition de la règle: pour un nœud, il faut évaluer un sous-arbre, en garder le résultat dans un registre, puis évaluer l'autre. Si le second sous-arbre a besoin d'autant de registres que le premier, il faut un registre de plus que ce que demandait le premier (celui qui retient sa valeur). Si le second en demande strictement moins, son évaluation peut se faire dans les registres déjà occupés par le plus gourmand, et aucun registre supplémentaire n'est nécessaire.

#Exemple completCopier le lien

Reprenons le fil conducteur 2*(3+4)-5. L'arbre est (-, (*, 2, (+, 3, 4)), 5):

1-   e = 2          (fils de nombres 2 et 1 -> max = 2)2├── *   e = 2      (fils de nombres 1 et 2 -> max = 2)3│   ├── 2   e = 14│   └── +   e = 2  (fils 1 et 1 -> 1+1 = 2)5│       ├── 3  e = 16│       └── 4  e = 17└── 5   e = 1

Le nœud + a deux fils de nombre 1: il reçoit $1+1 = 2$. Le nœud * a des fils de nombres 1 et 2, donc $\max(1,2) = 2$ — la multiplication n'exige pas plus que son fils gauche, puisque (3+4) est évalué en premier et que la constante 2 tient dans le registre restant. Le nœud - a des fils de nombres 2 et 1, donc $2$. Deux registres suffisent pour 2*(3+4)-5.

Le code à deux registres suit la décoration: on évalue d'abord le fils de plus grand nombre.

1R1 = 32R2 = 43R1 = R1 + R2      ; R1 = 7     (le fils gauche de * est évalué)4R2 = 25R1 = R1 * R2      ; R1 = 146R2 = 57R1 = R1 - R2      ; R1 = 9

Six instructions, deux registres, aucun spill. Comparons avec l'évaluation naïve de gauche à droite sans réordonnancement: elle donne le même nombre de registres ici, mais ce n'est pas toujours le cas. Sur une expression déséquilibrée comme a*(b+(c+(d+e))), l'ordre compte: la règle « plus gourmand d'abord » est ce qui garantit l'optimalité.

#Le cas déséquilibré: pourquoi la règle du plus grand filsCopier le lien

Soit a + (b * (c * (d * e))). Le sous-arbre droit est une chaîne de multiplications à gauche... non, à droite: chaque nœud a un fils gauche feuille (nombre 1) et un fils droit récursif.

• d*e: fils 1 et 1 → 2
• c*(d*e): fils 1 et 2 → max = 2
• b*(...): fils 1 et 2 → 2
• a+(...): fils 1 et 2 → 2

Deux registres suffisent, parce qu'à chaque nœud le sous-arbre gourmand est évalué en premier et que la feuille de gauche tient ensuite dans le registre libre. Le code évalue donc de la droite vers la gauche en profondeur, puis remonte:

1R1 = d2R2 = e3R1 = R1 * R2      ; R1 = d*e4R2 = c5R1 = R1 * R2      ; R1 = c*(d*e)6R2 = b7R1 = R1 * R28R2 = a9R1 = R1 + R2

Si l'on avait évalué naïvement de gauche à droite — charger a d'abord, puis descendre — il aurait fallu conserver a pendant toute la descente, et un troisième registre serait devenu nécessaire. C'est le gain concret de la règle.

#Arbre équilibré: la borne est logarithmiqueCopier le lien

Pour un arbre parfaitement équilibré à $2^k$ feuilles (tous les nœuds internes ont deux fils de même nombre), la règle $l = r \Rightarrow l+1$ s'applique à chaque niveau:

$e = 1 + 1 + \dots + 1 \quad (k \text{ fois}) = k + 1$

Donc une expression équilibrée à $n = 2^k$ feuilles demande $\log_2(n) + 1$ registres, alors qu'une chaîne de même taille (arbre peigné) n'en demande que 2. La forme de l'arbre détermine la pression sur les registres, pas seulement sa taille. C'est une raison supplémentaire de réassocier les expressions dans une passe d'optimisation: rééquilibrer un arbre peigné fait passer le besoin de 2 à $\log n + 1$, ce qui est pire — mais rend le calcul parallélisable. Le compromis est explicite, et Sethi-Ullman en donne la mesure.

#Quand les registres manquent: le spillCopier le lien

Si la machine ne dispose que de $k$ registres et que $e(\text{racine}) > k$, il faut vider des valeurs en mémoire (spill) et les recharger plus tard. La stratégie optimale se lit aussi sur la décoration: on place le spill à la frontière des deux sous-arbres de la racine, en évaluant entièrement le premier, en le sauvegardant, puis en évaluant le second.

Sur une expression dont la racine porte $e = 4$ et dont les deux fils portent $e = 3$, avec seulement 3 registres disponibles:

1; sous-arbre gauche, 3 registres, aucun spill (e = 3)2<code du sous-arbre gauche>3M0 = R1               ; SPILL : le resultat gauche part en memoire4 5; sous-arbre droit, 3 registres, aucun spill (e = 3)6<code du sous-arbre droit>7 8R2 = M0               ; recharge9R1 = R2 <op> R1       ; combinaison finale

Le coût est de deux accès mémoire pour un seul spill, et c'est optimal: le nombre d'Ershov de la racine vaut 4, donc au moins une valeur doit être vidée; une seule suffit, car chaque sous-arbre tient dans les 3 registres.

#Optimisations classiquesCopier le lien

#Exercice : étendre le codegen aux comparaisonsCopier le lien

Objectif: compiler ('lt', g, d), ('eq', g, d) (et leurs cousins) qui valent 1 ou 0, puis ('if', cond, alors, sinon) qui choisit une branche.

#InstructionsCopier le lien

1. Ajoutez au dictionnaire d'opérations les entrées lt → i32.lt_s, eq → i32.eq, gt → i32.gt_s.
2. Pour if, émettez le code de la condition, puis if (result i32), le code de la branche alors, else, celle de sinon, end.
3. Vérifiez sur ('if', ('lt', ('num',1), ('num',2)), ('num',10), ('num',20)) que le résultat simulé vaut 10.

#CorrectionCopier le lien

1elif tag in ('lt', 'eq', 'gt'):2    gen(node[1], slot, out)3    gen(node[2], slot, out)4    out.append({'lt': 'i32.lt_s', 'eq': 'i32.eq', 'gt': 'i32.gt_s'}[tag])5elif tag == 'if':6    gen(node[1], slot, out)      # condition: 1 ou 0 au sommet7    out.append("if (result i32)")8    gen(node[2], slot, out)      # branche alors: pousse une valeur9    out.append("else")10    gen(node[3], slot, out)      # branche sinon: pousse aussi une valeur11    out.append("end")            # la pile garde exactement un résultat

L'invariant pile est respecté: la condition consomme sa valeur, chaque branche en produit exactement une, donc if (result i32) en laisse une au sommet, comme un opérateur. C'est la même discipline que pour les binaires, étendue au contrôle.

#Mini‑quizCopier le lien