Représentations intermédiaires

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.

1résultat = opérande1  opérateur  opérande2

Une expression arborescente comme x * (y + 3) - 4 se linéarise ainsi :

1t1 = y + 32t2 = x * t13t3 = t2 - 4

Chaque 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.

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.

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.

À 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.

// 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);

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