Le code intermédiaire manipule des variables et des appels comme des abstractions. Pour produire du code qui s'exécute, il faut répondre à une question restée en suspens : où vivent ces variables en mémoire, et comment un appel de fonction s'y organise ? C'est l'environnement d'exécution — la convention, fixée par le compilateur, qui régit l'usage de la mémoire pendant que le programme tourne.

Ce chapitre relie enfin deux fils : l'« emplacement mémoire » que la table des symboles (chapitre 6) promettait, et les param, appels et locales du code intermédiaire (chapitre 9). Il explique aussi, au passage, pourquoi la récursivité fonctionne — et pourquoi elle peut faire déborder la pile.

Les segments de mémoire

À l'exécution, la mémoire d'un programme se divise en régions aux rôles distincts :

Deux régions croissent en sens opposés pendant l'exécution, ce qui optimise l'espace : le tas grandit vers le haut au fil des allocations, la pile grandit vers le bas au fil des appels. Les variables globales vivent dans les données statiques (adresse fixe, connue dès la compilation) ; les variables locales vivent sur la pile, et n'existent que le temps de leur fonction. C'est cette dernière région qui fait tout l'intérêt du chapitre.

L'enregistrement d'activation

Chaque appel de fonction reçoit un enregistrement d'activation (ou frame) : un bloc de mémoire, empilé sur la pile, qui contient tout ce dont cet appel a besoin. Un enregistrement typique rassemble :

• les paramètres de la fonction ;
• l'adresse de retour — où reprendre l'exécution une fois la fonction terminée ;
• les variables locales ;
• de quoi retrouver l'enregistrement de l'appelant (le chaînage, plus bas).

Le point essentiel pour le compilateur : à l'intérieur d'une frame, chaque variable occupe une place à un décalage fixe depuis le début de la frame. Une variable locale n'a pas d'adresse absolue — elle a un décalage relatif à sa frame. acc est « à +4 du début de la frame de factoriel ». Ce décalage est calculé à la compilation (en disposant paramètres puis locales à la suite, en cumulant leurs tailles) ; l'adresse réelle ne se connaît qu'à l'exécution : adresse de la frame + décalage.

C'est exactement l'« emplacement mémoire » que la table des symboles (chapitre 6) réservait dans ses entrées : le chapitre 6 promettait un emplacement, le voici — un décalage dans un enregistrement d'activation.

La pile d'appels

Pourquoi une pile ? Parce que les appels suivent une discipline dernier entré, premier sorti : la fonction appelée en dernier est celle qui rend la main en premier. Quand A appelle B qui appelle C, on empile la frame de A, puis de B, puis de C ; C retourne (on dépile), puis B, puis A. La pile grandit à chaque appel, rétrécit à chaque retour, au rythme exact du programme.

Cette organisation offre gratuitement la propriété la plus importante : la récursivité. Comme chaque appel a sa propre frame, un appel récursif de factoriel a son propre k, son propre acc, indépendants de l'appel qui l'a déclenché. Trois appels imbriqués, ce sont trois frames superposées, chacune avec ses variables — les appels ne se marchent pas dessus. La récursion n'a besoin d'aucun mécanisme spécial : elle découle de la pile.

La contrepartie est le débordement de pile (stack overflow) : une récursion trop profonde (ou infinie) empile plus de frames que la mémoire n'en peut contenir. C'est la traduction concrète, à l'exécution, d'une récursion sans cas de base — le pendant du « la pile déborde » qu'évoquait déjà l'analyse descendante (chapitre 4). L'exercice fait dérouler cette pile pas à pas.

Passage de paramètres et valeur de retour

Reste à convenir comment l'appelant et l'appelé s'échangent les données — la convention d'appel, contrat que les deux côtés respectent.

Les paramètres se transmettent en les plaçant à un endroit convenu : dans la frame de l'appelé (sur la pile), ou dans des registres pour les premiers arguments (plus rapide, c'est l'usage moderne). La valeur de retour repart de même, typiquement par un registre dédié. Le passage peut se faire par valeur (on copie l'argument — le cas par défaut) ou par référence (on transmet l'adresse, ce qui permet à l'appelé de modifier la variable de l'appelant).

Un détail que la convention doit trancher : qui nettoie la frame au retour, l'appelant ou l'appelé ? Il n'y a pas de bonne réponse universelle, seulement un contrat à respecter des deux côtés — c'est précisément ce qu'est une convention d'appel.

Variables locales et chaînage

Deux liens relient les frames entre elles, et il ne faut pas les confondre.

Le chaînage dynamique (ou lien de contrôle) pointe vers la frame de l'appelant — celui qui a déclenché l'appel. Il sert à restaurer la pile au retour : on sait où reprendre. C'est le lien qui suit la chaîne des appels.

Le chaînage statique (ou lien d'accès) pointe vers la frame de la fonction englobante lexicalement, dans les langages qui autorisent des fonctions imbriquées. Il permet à une fonction interne d'accéder aux variables locales de la fonction qui la contient — la portée statique du chapitre 6, réalisée à l'exécution. Beaucoup de langages (dont C) n'ont pas de fonctions imbriquées et se passent de ce second lien.

La distinction est celle-là même du chapitre 6 : le chaînage dynamique suit les appels, le chaînage statique suit la structure du texte. Les deux coexistent parce qu'ils répondent à deux questions différentes : « d'où viens-je ? » et « qui m'entoure dans le code ? ».

À vous

L'exercice relie les deux moments de la vie d'une variable locale. À la compilation, vous calculez les décalages des paramètres et locales dans l'enregistrement d'activation — l'emplacement que la table des symboles promettait. À l'exécution, vous simulez la pile d'appels pendant une récursion, en empilant une frame par appel.

Vous verrez pourquoi chaque appel a ses propres variables — d'où la récursivité — et ce qu'est concrètement un débordement de pile.

// À l'exécution, chaque APPEL de fonction reçoit un ENREGISTREMENT
// D'ACTIVATION (une « frame ») empilé sur la PILE D'APPELS. Il contient les
// paramètres, l'adresse de retour, et les variables locales — chacune à un
// DÉCALAGE fixe depuis le début de la frame.

// Description d'une fonction : ses paramètres et ses locales, chacun avec sa
// taille en octets.
const FONCTIONS = {
  main:      { params: [], locales: [ ["n", 4] ] },
  factoriel: { params: [ ["k", 4] ], locales: [ ["acc", 4], ["i", 4] ] },
};

// ── À VOUS (1) : calculer les décalages (à la COMPILATION) ───────────────────
// Poser les paramètres puis les locales à la suite, en cumulant les tailles.
// Renvoyer un objet nom -> décalage, et la taille totale de la frame.
function disposition(fn) {
  const f = FONCTIONS[fn];
  const dec = {};
  let offset = 0;
  // à compléter : pour chaque [nom, taille] de f.params PUIS f.locales :
  //   dec[nom] = offset ; offset += taille;
  return { dec, taille: offset };
}

console.log("Disposition des frames (calculée à la compilation) :");
for (const fn of Object.keys(FONCTIONS)) {
  const d = disposition(fn);
  console.log("  " + fn + " : " + JSON.stringify(d.dec) + "  (taille " + d.taille + " o)");
}

// ── À VOUS (2) : simuler la pile d'appels (à l'EXÉCUTION) ────────────────────
const pile = [];
function entrer(fn) {
  // à compléter : empiler une frame { fn, taille } ; afficher la profondeur
  const d = disposition(fn);
  pile.push({ fn, taille: d.taille });
  console.log("  ".repeat(pile.length) + "-> appel " + fn + " (frame " + d.taille + " o), profondeur " + pile.length);
}
function sortir() {
  const f = pile.pop();
  console.log("  ".repeat(pile.length + 1) + "<- retour " + f.fn + ", frame libérée");
}

// main appelle factoriel, qui s'appelle 2 fois récursivement :
console.log("\nDéroulé de la pile :");
entrer("main");
entrer("factoriel");   // factoriel(3)
entrer("factoriel");   // factoriel(2)
entrer("factoriel");   // factoriel(1)
sortir(); sortir(); sortir(); sortir();
console.log("pile vide ? " + (pile.length === 0));

function disposition(fn) {
  const f = FONCTIONS[fn];
  const dec = {};
  let offset = 0;
  for (const [nom, taille] of [...f.params, ...f.locales]) {
    dec[nom] = offset;       // le décalage de la variable dans la frame
    offset += taille;        // on avance de sa taille pour la suivante
  }
  return { dec, taille: offset };
}
// main      : { n: 0 }                 (taille 4)
// factoriel : { k: 0, acc: 4, i: 8 }   (taille 12)
//
// ── Ce que l'exercice enseigne ──────────────────────────────────────────────
//
// 1. Deux moments à ne pas confondre :
//    - À LA COMPILATION, on calcule les DÉCALAGES : « acc est à +4 du début de
//      la frame de factoriel ». C'est l'« emplacement mémoire » que la table
//      des symboles (chapitre 6) promettait — une variable locale n'a pas
//      d'adresse absolue, seulement un décalage relatif à SA frame.
//    - À L'EXÉCUTION, chaque appel EMPILE une frame ; l'adresse réelle d'une
//      variable est « adresse de la frame + décalage ».
//
// 2. La RÉCURSIVITÉ tombe gratuitement : chaque appel de factoriel a SA
//    PROPRE frame sur la pile, donc son propre « k », « acc », « i ». Trois
//    appels imbriqués = trois frames superposées, chacune avec ses variables.
//    C'est pourquoi la récursion fonctionne sans que les appels se marchent
//    dessus — et pourquoi une récursion trop profonde provoque un débordement
//    de pile (stack overflow).
//
// 3. La frame contient aussi l'ADRESSE DE RETOUR (où reprendre après l'appel)
//    et de quoi retrouver la frame appelante (le chaînage). Le passage de
//    PARAMÈTRES place les arguments dans la frame de l'appelé (ici k), la
//    VALEUR DE RETOUR repart par un registre ou un emplacement convenu.
//
// 4. La pile grandit et rétrécit en LIFO, au rythme exact des appels et
//    retours : entrer = empiler, sortir = dépiler. Tout ce qui était local
//    disparaît d'un coup au retour — comme la portée du chapitre 6, mais à
//    l'exécution.

Ce que la suite en fait

L'organisation mémoire est en place : on sait où vivent les variables et comment les appels s'empilent. Il ne reste qu'une étape — produire le code cible réel, celui de la machine, et le rendre efficace.

Le chapitre 11, dernier du cours, traite la génération de code proprement dite — choisir les instructions, placer les valeurs dans les registres — et l'optimisation — rendre le code plus rapide sans changer ce qu'il calcule. C'est le back-end qui referme la chaîne ouverte au chapitre 1.

À retenir

Dernière étape, et fin de la chaîne ouverte au chapitre 1 : produire le code cible réel — celui de la machine — et le rendre efficace. Deux tâches distinctes. La génération de code traduit la représentation intermédiaire en instructions du processeur ; l'optimisation transforme le code pour qu'il soit plus rapide ou plus compact, sans jamais changer ce qu'il calcule.

Ce chapitre présente les principes, pas l'exhaustivité — un compilateur optimisant réel est un objet considérable. L'essentiel est de comprendre les mécanismes de base et la règle d'or qui les gouverne tous.

Sélection d'instructions

La sélection d'instructions choisit, pour chaque opération du code intermédiaire, la ou les instructions machine qui la réalisent. Le passage n'est pas toujours un-pour-un : une instruction à trois adresses peut demander plusieurs instructions machine, et inversement, un processeur offre souvent une instruction unique pour un motif fréquent — une multiplication-addition combinée, un accès mémoire avec décalage intégré.

Le jeu consiste à couvrir l'opération avec les instructions disponibles, au meilleur coût. La difficulté vient de la richesse des jeux d'instructions réels ; le principe, lui, est simple : faire correspondre des motifs de la représentation intermédiaire à des instructions de la cible.

Allocation de registres

Les processeurs calculent dans un petit nombre de registres — quelques dizaines — bien plus rapides que la mémoire. Le code intermédiaire, lui, emploie autant de temporaires qu'il veut. Il faut donc faire tenir une infinité de temporaires dans un nombre fini de registres : c'est l'allocation de registres, l'une des optimisations qui rapporte le plus.

Le modèle est élégant — un coloriage de graphe. On construit le graphe d'interférence : un sommet par variable, une arête entre deux variables vivantes en même temps (dont les durées de vie se chevauchent). Deux variables reliées ne peuvent pas partager un registre, exactement comme deux sommets adjacents ne peuvent pas partager une couleur. Allouer $k$ registres, c'est donc colorier le graphe avec $k$ couleurs.

Quand le graphe n'est pas $k$-coloriable — trop de variables simultanément vivantes —, on doit en reléguer (spill) certaines en mémoire, plus lentes. C'est le lien concret entre un problème de graphes (que la Théorie des langages a côtoyé) et la performance d'un programme. En L3, retenez le principe : interférence = arête, registre = couleur.

Blocs de base et graphe de flot de contrôle

Pour optimiser, on a besoin d'une structure au-dessus de la suite plate d'instructions.

Un bloc de base est une séquence maximale d'instructions sans saut ni étiquette au milieu : on y entre uniquement au début, on en sort uniquement à la fin. À l'intérieur, l'exécution est strictement séquentielle — ce qui en fait l'unité naturelle des optimisations locales.

Le graphe de flot de contrôle (CFG) relie ces blocs : un sommet par bloc, une arête de B1 vers B2 si l'exécution peut passer de l'un à l'autre (par enchaînement ou par saut). Les if et while du chapitre 9, une fois traduits en sauts, dessinent précisément ce graphe — une condition crée un embranchement, une boucle crée un cycle. Le CFG est la carte sur laquelle raisonnent les optimisations globales.

Optimisations locales

Les optimisations locales agissent à l'intérieur d'un seul bloc de base. Trois classiques, que l'exercice met en œuvre :

• Propagation de constantes : remplacer une variable par sa valeur quand celle-ci est une constante connue.
• Calcul de constantes (constant folding) : évaluer dès la compilation une opération entre constantes — 3 + 4 devient 7, pourquoi le calculer à l'exécution ?
• Élimination du code mort : supprimer toute instruction dont le résultat n'est jamais utilisé ensuite. Elle se calcule à rebours, en propageant les variables « vivantes » depuis la sortie.
• Élimination des sous-expressions communes : si a * b est calculé deux fois sans que a ni b ne changent entre-temps, on le calcule une fois et on réutilise le résultat.

Enchaînées, ces transformations se renforcent : la propagation de constantes crée des opérations entre constantes que le folding évalue, ce qui rend d'autres instructions mortes, que l'élimination supprime. Un bloc de six instructions peut fondre à une seule — sans que le résultat observable change.

Optimisations globales, et la règle d'or

Les optimisations globales raisonnent sur tout le graphe de flot de contrôle, entre les blocs. Elles reposent sur une analyse de flot de données — suivre, à travers le CFG, quelles valeurs une variable peut prendre à chaque point. Quelques exemples : sortir d'une boucle un calcul qui ne dépend pas de la boucle (code motion), propager les constantes au-delà d'un bloc, éliminer une variable inutile sur toute la fonction. La forme SSA du chapitre 8 rend ces analyses bien plus simples, en donnant à chaque valeur une définition unique.

Toutes ces transformations, locales comme globales, obéissent à une règle d'or sans exception :

Une optimisation ne doit jamais changer ce que le programme calcule. Elle le rend plus rapide ou plus léger, à sémantique strictement identique.

Un « x = 14 » optimisé doit valoir 14 exactement comme le code d'origine. Une optimisation qui change le résultat n'est pas une optimisation, c'est un bug — et c'est pourquoi la correction d'une optimisation prime toujours sur le gain qu'elle promet.

À vous

Le dernier exercice du cours optimise un bloc de base. Vous appliquez la propagation et le calcul de constantes — évaluer 3 + 4 à la compilation —, puis l'élimination du code mort — jeter les instructions dont le résultat ne sert jamais. Un bloc de six instructions se réduit à l'essentiel.

Vérifiez le point qui compte : la valeur observable en sortie est inchangée. C'est la règle d'or, et la note finale du cours — un compilateur transforme sans trahir.

// Un BLOC DE BASE : une suite d'instructions à trois adresses SANS saut ni
// étiquette au milieu (on y entre au début, on en sort à la fin). C'est
// l'unité sur laquelle agissent les optimisations LOCALES.
//
// Le bloc de départ (a et b sont des constantes) :
//   t1 = 3
//   t2 = 4
//   t3 = t1 + t2      <- 3 + 4, calculable dès la compilation
//   t4 = t3 * 2
//   t5 = t1 + 1       <- t5 n'est utilisé NULLE PART ensuite : code mort
//   x  = t4
//
// Représentation : [ { res, a, op, b } | { res, a } (copie) ]
const bloc = [
  { res: "t1", a: "3" },
  { res: "t2", a: "4" },
  { res: "t3", a: "t1", op: "+", b: "t2" },
  { res: "t4", a: "t3", op: "*", b: "2" },
  { res: "t5", a: "t1", op: "+", b: "1" },
  { res: "x",  a: "t4" },
];
const SORTIES = new Set(["x"]);   // seules ces variables sont « observées » en sortie

const estConst = (v) => /^-?\d+$/.test(v);

// ── À VOUS (1) : propagation + calcul de constantes ─────────────────────────
// Parcourir le bloc en gardant une table 'valeurs' (nom -> constante connue).
// - remplacer tout opérande dont la valeur constante est connue ;
// - si les deux opérandes sont des constantes, CALCULER le résultat.
function propager(bloc) {
  const valeurs = {};
  const sortie = [];
  for (const ins of bloc) {
    const a = valeurs[ins.a] ?? ins.a;
    if (ins.op === undefined) {           // copie : res = a
      if (estConst(a)) valeurs[ins.res] = a;
      sortie.push({ res: ins.res, a });
      continue;
    }
    const b = valeurs[ins.b] ?? ins.b;
    // à compléter : si a et b sont des constantes, calculer (a op b),
    //   enregistrer valeurs[ins.res] et pousser une copie { res, a: valeur } ;
    //   sinon pousser { res, a, op, b } inchangé.
    sortie.push({ res: ins.res, a, op: ins.op, b });   // (branche non optimisée)
  }
  return sortie;
}

// ── À VOUS (2) : élimination du code mort ───────────────────────────────────
// Une instruction est MORTE si son résultat n'est jamais lu ensuite ET n'est
// pas une sortie observée. On parcourt de la FIN vers le début en tenant la
// liste des variables « vivantes ».
function eliminerMort(bloc) {
  const vivantes = new Set(SORTIES);
  const gardees = [];
  for (let i = bloc.length - 1; i >= 0; i--) {
    const ins = bloc[i];
    // à compléter : si ins.res est vivante -> on garde, et ses opérandes non
    //   constants deviennent vivants ; sinon on jette l'instruction.
    gardees.unshift(ins);   // (branche qui garde tout — à corriger)
  }
  return gardees;
}

// ── Enchaînement ────────────────────────────────────────────────────────────
function calc(a, op, b) { a = +a; b = +b; return String(op === "+" ? a+b : op === "*" ? a*b : op === "-" ? a-b : a/b); }
function afficher(t, b) { console.log(t + " (" + b.length + " instr) :"); b.forEach((i) => console.log("   " + i.res + " = " + i.a + (i.op ? " " + i.op + " " + i.b : ""))); }

afficher("Départ", bloc);
const p = propager(bloc);
afficher("\nAprès propagation + calcul", p);
const f = eliminerMort(p);
afficher("\nAprès élimination du code mort", f);

function propager(bloc) {
  const valeurs = {};
  const sortie = [];
  for (const ins of bloc) {
    const a = valeurs[ins.a] ?? ins.a;
    if (ins.op === undefined) {
      if (estConst(a)) valeurs[ins.res] = a;
      sortie.push({ res: ins.res, a });
      continue;
    }
    const b = valeurs[ins.b] ?? ins.b;
    if (estConst(a) && estConst(b)) {
      const v = calc(a, ins.op, b);        // on CALCULE dès la compilation
      valeurs[ins.res] = v;
      sortie.push({ res: ins.res, a: v }); // devient une simple copie res = constante
    } else {
      sortie.push({ res: ins.res, a, op: ins.op, b });
    }
  }
  return sortie;
}

function eliminerMort(bloc) {
  const vivantes = new Set(SORTIES);
  const gardees = [];
  for (let i = bloc.length - 1; i >= 0; i--) {
    const ins = bloc[i];
    if (!vivantes.has(ins.res)) continue;   // résultat jamais utilisé -> MORT, on jette
    gardees.unshift(ins);
    vivantes.delete(ins.res);               // res est produit ici, plus « en attente »
    if (!estConst(ins.a)) vivantes.add(ins.a);         // ses opérandes deviennent vivants
    if (ins.b && !estConst(ins.b)) vivantes.add(ins.b);
  }
  return gardees;
}
// Départ : 6 instructions.
// Après propagation + calcul : t3 devient 7, t4 devient 14, t5 devient 4, etc.
// Après élimination du code mort : il ne reste que « x = 14 » (2 instr après
// propagation des copies, ou 1 seule ligne utile). t5 (= 4) disparaît : mort.
//
// ── Ce que l'exercice enseigne ──────────────────────────────────────────────
//
// 1. Un BLOC DE BASE est une suite d'instructions sans saut ni étiquette au
//    milieu : on y entre en haut, on en sort en bas. C'est l'unité des
//    optimisations LOCALES, celles qui ne raisonnent que sur un seul bloc.
//
// 2. La PROPAGATION DE CONSTANTES remplace une variable par sa valeur connue ;
//    le CALCUL DE CONSTANTES (constant folding) évalue « 3 + 4 » dès la
//    compilation. Ensemble, ils font « remonter » les constantes à travers le
//    bloc — pourquoi calculer à l'exécution ce qu'on connaît déjà ?
//
// 3. L'ÉLIMINATION DU CODE MORT jette toute instruction dont le résultat
//    n'est jamais utilisé ensuite (et n'est pas une sortie observée). On la
//    calcule à REBOURS, en propageant les variables « vivantes ». t5 = 4 ne
//    sert à rien -> supprimé.
//
// 4. Ces optimisations ne changent JAMAIS ce que le programme calcule : x vaut
//    14 avant comme après. C'est la règle d'or de l'optimisation — accélérer
//    ou alléger, à sémantique strictement identique.
//
// Les optimisations GLOBALES (entre blocs) et l'ALLOCATION DE REGISTRES par
// coloriage de graphe (deux variables « vivantes en même temps » ne peuvent
// pas partager un registre — comme deux sommets adjacents ne peuvent pas
// partager une couleur) prolongent ces idées à l'échelle de la fonction.

Ce que ce cours vous laisse

Vous avez suivi un programme d'un bout à l'autre de la chaîne : du texte (analyse lexicale) à l'arbre (analyse syntaxique), de l'arbre vérifié (analyse sémantique) au code intermédiaire, puis au code cible optimisé. Chaque bloc a ajouté une couche au même compilateur, sur le même mini-langage — le fil unique du TP.

Trois idées surnagent, au-delà des techniques :

• Un compilateur est une suite de traductions entre représentations, du texte à la machine, chacune plus proche de l'exécution que la précédente.
• La séparation front-end / back-end, autour d'une représentation intermédiaire, est ce qui rend l'ensemble modulaire, réutilisable et optimisable.
• La théorie paie. Automates, grammaires, analyse LL et LR — tout ce que la Théorie des langages avait posé s'est retrouvé au travail, du lexeur aux tables LR. Ce cours en était la mise en pratique.

De là partent la vérification de programmes, les langages de plus haut niveau, les machines virtuelles, les compilateurs optimisants comme LLVM — mais la carte, elle, ne changera plus : c'est celle du chapitre 1, que vous venez de parcourir en entier.

À retenir