Chapitre 1 · 5 h
Représentations intermédiaires
Code à trois adresses ; quadruplets et triplets ; arbre syntaxique abstrait annoté ; aperçu de la forme SSA.
Le front-end est terminé : l'arbre qui en sort est correct et typé. Commence la synthèse — la production de code. Mais on ne saute pas directement de l'arbre au code machine : on passe par une représentation intermédiaire, ce pivot entre front-end et back-end dont le chapitre 1 expliquait l'intérêt combinatoire.
Ce chapitre présente la représentation intermédiaire la plus répandue, le code à trois adresses, et les formes voisines. L'idée maîtresse : linéariser l'arbre en une suite d'instructions élémentaires, proches de la machine mais encore indépendantes d'un processeur précis.
Pourquoi une représentation intermédiaire
L'arbre syntaxique est une structure arborescente ; une machine exécute une suite linéaire d'instructions. Entre les deux, un fossé. On pourrait le franchir d'un coup, mais une représentation intermédiaire apporte trois bénéfices décisifs :
- elle est indépendante de la machine cible : le même code intermédiaire se traduit ensuite vers x86, ARM ou un bytecode — c'est le pivot du chapitre 1 ;
- elle est assez simple pour être optimisée : les optimisations du chapitre 11 travaillent dessus, pas sur l'arbre ni sur le code machine ;
- elle rapproche progressivement de la machine, sans en épouser tous les détails — un bon niveau d'abstraction pour raisonner.
Le code à trois adresses
Le code à trois adresses est une suite d'instructions ayant chacune au plus un opérateur et au plus trois opérandes — d'où le nom : deux sources, une destination.
résultat = opérande1 opérateur opérande2Une expression arborescente comme x * (y + 3) - 4 se linéarise ainsi :
t1 = y + 3t2 = x * t1t3 = t2 - 4Chaque nœud interne de l'arbre devient une instruction, et l'ordre respecte l'évaluation : les
sous-arbres avant leur parent. Les résultats intermédiaires sont rangés dans des temporaires —
t1, t2, t3 — créés à la volée, autant qu'il en faut. On est passé de l'arbre à une suite
d'opérations élémentaires : un vrai pas vers la machine, qui exécute une instruction après l'autre.
La génération suit exactement le schéma dirigé par la syntaxe du chapitre 7. C'est même le même parcours d'arbre que la vérification de types : un attribut synthétisé remonte des feuilles, mais au lieu d'un type, il porte désormais l'adresse (le temporaire) où se trouve le résultat du nœud. On a remplacé l'attribut « type » par l'attribut « code ». L'exercice le construit.
Quiz · 1 question
Pourquoi passe-t-on par une représentation intermédiaire comme le code à trois adresses, plutôt que de traduire l'arbre directement en code machine ?
- Parce que le code machine est trop rapide à produire directement — vitesse
- Parce qu'elle est indépendante de la machine cible (pivot réutilisable) et assez simple pour porter les optimisations, tout en rapprochant l'arbre d'une forme linéaire — pivot + optimisation
- Parce que l'arbre syntaxique ne contient pas assez d'information — information manquante
Réponse : La représentation intermédiaire est le pivot du chapitre 1 : indépendante de la cible, elle se traduit ensuite vers n'importe quelle machine (un back-end par cible). Elle est aussi le bon niveau pour OPTIMISER — ni trop haut (l'arbre), ni trop bas (le code machine, encombré de détails de registres). Enfin, elle linéarise l'arbre en instructions élémentaires, franchissant progressivement le fossé structure → suite. L'arbre typé contient bien toute l'information nécessaire ; c'est justement ce qu'on linéarise.
Quadruplets et triplets
Le code à trois adresses est une notation ; concrètement, on le stocke de deux façons.
Les quadruplets représentent chaque instruction par quatre champs : (opérateur, arg1, arg2, résultat). t1 = y + 3 devient (+, y, 3, t1). Les temporaires y sont nommés explicitement, ce
qui permet de réordonner ou de déplacer les instructions librement — un atout majeur pour
l'optimisation (chapitre 11).
Les triplets économisent le champ résultat : chaque instruction est (opérateur, arg1, arg2), et
l'on désigne son résultat par le numéro de l'instruction qui l'a produit. Plus compact, mais
fragile : réordonner les instructions casse toutes les références par numéro.
| Quadruplets | Triplets | |
|---|---|---|
| Résultat | temporaire nommé | numéro de l'instruction |
| Taille | un champ de plus | plus compact |
| Réordonnancement | facile | casse les références |
En pratique, on privilégie les quadruplets précisément parce que l'optimisation a besoin de déplacer les instructions.
Arbre annoté et forme SSA
Deux compléments, pour situer le paysage.
L'arbre syntaxique abstrait annoté est une représentation intermédiaire de plus haut niveau : on garde l'AST (chapitre 3) et on y accroche les informations calculées — types, temporaires, adresses. Certains compilateurs génèrent le code directement depuis cet arbre annoté ; d'autres le linéarisent d'abord en trois adresses. Les deux approches coexistent.
La forme SSA (Static Single Assignment) est le raffinement moderne du code à trois adresses :
chaque variable n'y est affectée qu'une seule fois. Une variable réaffectée devient une suite de
versions (x1, x2, x3…). Cette contrainte, en apparence anodine, simplifie énormément les
optimisations du chapitre 11 : savoir « d'où vient » une valeur devient trivial, puisque chaque nom a
une définition unique. C'est la représentation interne de LLVM, et le standard des compilateurs
optimisants actuels. En L3, il suffit d'en connaître le principe.
Quiz · 1 question
Pourquoi préfère-t-on souvent les quadruplets aux triplets pour représenter le code à trois adresses ?
- Parce que les triplets ne peuvent pas représenter les opérations arithmétiques — expressivité
- Parce que les quadruplets nomment explicitement les résultats (temporaires), ce qui permet de réordonner et déplacer les instructions librement — indispensable à l'optimisation — réordonnancement pour l'optimisation
- Parce que les triplets occupent plus de mémoire — taille
Réponse : Les triplets sont plus compacts (pas de champ résultat), mais désignent le résultat d'une instruction par son NUMÉRO : déplacer ou réordonner les instructions casse ces références. Les quadruplets nomment chaque résultat par un temporaire explicite (op, arg1, arg2, res), si bien qu'on peut librement déplacer, supprimer ou insérer des instructions — exactement ce dont l'optimisation (chapitre 11) a besoin. Les deux représentent aussi bien les opérations ; l'avantage décisif des quadruplets est le réordonnancement.
À vous
L'exercice engendre la représentation intermédiaire du compilateur du TP : du code à trois adresses
depuis un AST d'expression. C'est le même parcours d'arbre qu'au chapitre 7 — un attribut synthétisé qui
remonte — mais l'attribut est désormais le temporaire portant le résultat, et chaque opération émet
une instruction t = a op b.
Vous verrez l'arbre se linéariser en une suite d'instructions élémentaires, et vous reconnaîtrez les formats quadruplets et triplets. C'est le socle sur lequel le chapitre suivant traduira les vraies constructions du langage.
Exercice de code
Engendrez du code à trois adresses depuis un AST : même parcours qu'au chapitre 7, mais l'attribut synthétisé est désormais le temporaire qui porte le résultat. Chaque opération devient une instruction « t = a op b ». Observez la linéarisation de l'arbre, et les formats quadruplets/triplets.
Point de départ
// Le code à TROIS ADRESSES : chaque instruction a au plus un opérateur et
// trois opérandes -> « resultat = op1 op op2 ». Les résultats intermédiaires
// sont stockés dans des TEMPORAIRES t1, t2, ... créés à la volée.
//
// AST d'une expression, comme au chapitre 7 :
// { op: "nb", val } { op: "var", nom }
// { op: "+"|"-"|"*"|"/", g, d }
const instructions = [];
let compteur = 0;
function nouveauTemp() { return "t" + (++compteur); }
function emettre(txt) { instructions.push(txt); }
// ── À VOUS : engendrer() rend le nom où se trouve le résultat du nœud ────────
// (attribut SYNTHÉTISÉ « adresse » : il remonte, comme le type au ch. 7)
function engendrer(n) {
if (n.op === "nb") return String(n.val); // une constante est déjà une adresse
if (n.op === "var") return n.nom; // une variable aussi
// opération binaire : engendrer d'abord les deux fils (récursion),
// créer un temporaire, émettre « t = adrG op adrD », renvoyer t.
const adrG = engendrer(n.g);
const adrD = engendrer(n.d);
// à compléter : const t = nouveauTemp(); emettre(...); return t;
return "?";
}
// ── Expression : x * (y + 3) - 4 ────────────────────────────────────────────
const ast = {
op: "-",
g: { op: "*", g: { op: "var", nom: "x" },
d: { op: "+", g: { op: "var", nom: "y" }, d: { op: "nb", val: 3 } } },
d: { op: "nb", val: 4 },
};
const adrFinale = engendrer(ast);
console.log("Code à trois adresses :");
instructions.forEach((i, k) => console.log(" " + (k + 1) + ": " + i));
console.log("résultat dans : " + adrFinale);
Solution
function engendrer(n) {
if (n.op === "nb") return String(n.val);
if (n.op === "var") return n.nom;
const adrG = engendrer(n.g); // d'abord le sous-arbre gauche
const adrD = engendrer(n.d); // puis le droit
const t = nouveauTemp();
emettre(t + " = " + adrG + " " + n.op + " " + adrD);
return t; // le résultat du nœud est dans ce temporaire
}
// ── Code engendré pour x * (y + 3) - 4 ──────────────────────────────────────
// 1: t1 = y + 3
// 2: t2 = x * t1
// 3: t3 = t2 - 4
// résultat dans : t3
//
// ── Ce que l'exercice enseigne ──────────────────────────────────────────────
//
// 1. Le code à trois adresses LINÉARISE l'arbre : chaque nœud interne devient
// UNE instruction élémentaire, et l'ordre des instructions respecte
// l'ordre d'évaluation (les fils avant le parent). On est passé d'une
// structure arborescente à une suite d'instructions — un pas vers la
// machine, qui exécute une instruction après l'autre.
//
// 2. Les TEMPORAIRES portent les résultats intermédiaires. « engendrer » est
// un attribut SYNTHÉTISÉ, exactement comme le type au chapitre 7 : il
// remonte des feuilles, mais renvoie une ADRESSE au lieu d'un type. Même
// parcours d'arbre, autre attribut — c'est la traduction dirigée par la
// syntaxe.
//
// 3. Ce format se stocke de deux manières équivalentes :
// - QUADRUPLETS : (op, arg1, arg2, res) — « (+ , y, 3, t1) ». Les
// temporaires sont nommés explicitement ; on peut réordonner les
// instructions librement (utile pour l'optimisation, chapitre 11).
// - TRIPLETS : (op, arg1, arg2), le résultat étant désigné par le NUMÉRO
// de l'instruction. Plus compact, mais réordonner casse les références.
//
// 4. La forme SSA (Static Single Assignment) va plus loin : chaque variable
// n'est affectée QU'UNE fois (x1, x2, ...), ce qui rend les optimisations
// du chapitre 11 beaucoup plus simples à raisonner. C'est la représentation
// interne de LLVM.
Ce que la suite en fait
Vous savez linéariser une expression. Mais un programme, ce sont surtout des constructions de
contrôle : affectations, conditions, boucles, appels de fonctions. Les traduire en code à trois
adresses demande de gérer les sauts — car if et while n'existent pas au niveau intermédiaire,
seulement des branchements conditionnels vers des étiquettes.
Le chapitre 9 s'y attaque, avec une attention particulière à if et while — les plus importants — et
à l'évaluation en court-circuit des expressions booléennes. C'est le chapitre le plus dense du bloc.
À retenir
Flashcards · 4 cartes
- Qu'est-ce que le code à trois adresses, et comment se relie-t-il à l'arbre ?
- Une suite d'instructions ayant au plus un opérateur et trois opérandes : « résultat = op1 opérateur op2 ». Il LINÉARISE l'arbre : chaque nœud interne devient une instruction, dans l'ordre d'évaluation (fils avant parent), les résultats intermédiaires allant dans des TEMPORAIRES créés à la volée. C'est le même parcours d'arbre que la vérification de types, avec un attribut synthétisé « adresse » au lieu de « type ».
- Pourquoi passer par une représentation intermédiaire plutôt que traduire directement en code machine ?
- Trois raisons : elle est indépendante de la machine cible (pivot réutilisable — un back-end par processeur, chapitre 1) ; elle est assez simple pour porter les optimisations (chapitre 11) ; elle rapproche progressivement l'arbre d'une forme linéaire proche de la machine, sans en épouser tous les détails. C'est le bon niveau d'abstraction pour la synthèse.
- Quelle est la différence entre quadruplets et triplets ?
- Quadruplets : (opérateur, arg1, arg2, résultat) — le résultat est un temporaire NOMMÉ, donc on peut réordonner/déplacer librement (bon pour l'optimisation). Triplets : (opérateur, arg1, arg2) — le résultat est désigné par le NUMÉRO de l'instruction, plus compact mais fragile (réordonner casse les références). On préfère les quadruplets pour l'optimisation.
- Qu'est-ce que la forme SSA, et quel est son intérêt ?
- Static Single Assignment : chaque variable n'est affectée QU'UNE seule fois (une variable réaffectée devient x1, x2, x3…). Cette contrainte simplifie énormément les optimisations : « d'où vient cette valeur » a une réponse unique, puisque chaque nom a une définition unique. C'est la représentation interne de LLVM et le standard des compilateurs optimisants.