Génération et optimisation

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