Du code source au binaire qui s’exécute

Le chapitre précédent comparait compilation, interprétation et compilation à la volée. Celui-ci ouvre le compilateur lui-même. Lancer cc -O2 prog.c ressemble à une seule étape, mais une chaîne de compilation C est un pipeline de programmes distincts, chacun transformant une représentation en la suivante :

le préprocesseur développe les #include et les macros ;
le compilateur proprement dit transforme le C en assembleur, en passant par des tokens, un arbre syntaxique et une représentation intermédiaire, et optimise en chemin ;
l’assembleur transforme l’assembleur en fichier objet ;
l’éditeur de liens assemble fichiers objets et bibliothèques en un exécutable.

Les étapes 3 et 4 sont traitées au niveau de l’assembleur, dans assembleur, éditeur de liens et chargeur, et le fichier qu’elles produisent dans les fichiers exécutables. Ce chapitre suit les étapes 1 et 2 sur une petite fonction, avec la vraie sortie de clang à chaque étape :

#define SQUARE(x) ((x) * (x))

int square_sum(int a, int b) {
    return SQUARE(a) + SQUARE(b);
}

1. Le préprocesseur

Avant que le compilateur ne voie quoi que ce soit, le préprocesseur traite chaque ligne qui commence par #. Il colle le contenu des fichiers nommés par #include, garde ou retire du code selon les #if/#ifdef, et développe les macros. Il travaille sur du texte : il ne sait rien des types ni des fonctions du C. clang -E montre sa sortie :

int square_sum(int a, int b) {
    return ((a) * (a)) + ((b) * (b));
}

SQUARE(a) est devenu ((a) * (a)), une pure substitution de texte, comme les macros de l’assembleur. Les parenthèses en plus comptent : sans elles, SQUARE(a + 1) deviendrait a + 1 * a + 1. Et comme la substitution est textuelle, SQUARE(i++) incrémenterait i deux fois. Dans un vrai programme, #include <stdio.h> colle à lui seul des centaines de lignes de déclarations.

2. L’analyse lexicale : des caractères aux tokens

L’analyseur lexical (lexer) découpe le texte en tokens, les mots du langage : mots-clés, identifiants, nombres, opérateurs, ponctuation. Les espaces et les commentaires disparaissent. clang -Xclang -dump-tokens les liste :

int 'int'                 Loc=<sq.c:3:1>
identifier 'square_sum'   Loc=<sq.c:3:5>
l_paren '('               Loc=<sq.c:3:15>
int 'int'                 Loc=<sq.c:3:16>
identifier 'a'            Loc=<sq.c:3:20>
comma ','                 Loc=<sq.c:3:21>
…
return 'return'           Loc=<sq.c:4:5>
l_paren '('               Loc=<sq.c:4:12 <Spelling=sq.c:1:19>>

Chaque token se souvient de son origine — même la ( venue de la macro de la ligne 1 —, ce qui permet aux messages d’erreur de pointer la bonne ligne et la bonne colonne.

3. L’analyse syntaxique : des tokens à l’arbre

L’analyseur syntaxique (parser) vérifie les tokens par rapport à la grammaire du C et construit un arbre syntaxique abstrait (AST) : la structure du programme, sans la ponctuation. clang -Xclang -ast-dump, légèrement allégé :

FunctionDecl square_sum 'int (int, int)'
|-ParmVarDecl a 'int'
|-ParmVarDecl b 'int'
`-CompoundStmt
  `-ReturnStmt
    `-BinaryOperator 'int' '+'
      |-BinaryOperator 'int' '*'
      | |-ImplicitCastExpr 'int' <LValueToRValue>
      | | `-DeclRefExpr 'a'
      | `-ImplicitCastExpr 'int' <LValueToRValue>
      |   `-DeclRefExpr 'a'
      `-BinaryOperator 'int' '*'
        |-ImplicitCastExpr 'int' <LValueToRValue>
        | `-DeclRefExpr 'b'
        `-ImplicitCastExpr 'int' <LValueToRValue>
          `-DeclRefExpr 'b'

La priorité des opérateurs n’est plus que la forme de l’arbre : les deux * sont sous le +. L’analyse sémantique travaille sur cet arbre. Elle relie chaque nom à sa déclaration, vérifie les types, et insère les conversions implicites qu’exige le C, comme les LValueToRValue qui signifient « lire la valeur stockée dans cette variable ». La plupart des erreurs de compilation — noms non déclarés, types incompatibles — viennent de cette étape.

4. La représentation intermédiaire

L’arbre est ensuite traduit en une représentation intermédiaire (IR) : un jeu d’instructions simple, indépendant de la machine. Clang produit de l’IR LLVM. En -O0, il traduit chaque construction C littéralement :

define i32 @square_sum(i32 %0, i32 %1) {
  %3 = alloca i32, align 4          ; emplacement de pile pour a
  %4 = alloca i32, align 4          ; emplacement de pile pour b
  store i32 %0, ptr %3, align 4
  store i32 %1, ptr %4, align 4
  %5 = load i32, ptr %3, align 4    ; lire a
  %6 = load i32, ptr %3, align 4    ; relire a
  %7 = mul nsw i32 %5, %6
  %8 = load i32, ptr %4, align 4
  %9 = load i32, ptr %4, align 4
  %10 = mul nsw i32 %8, %9
  %11 = add nsw i32 %7, %10
  ret i32 %11
}

L’IR ressemble à l’assembleur d’une machine idéale : des registres virtuels en nombre illimité (%5, %6…), chacun affecté une seule fois, une forme appelée SSA (static single assignment). Cette forme rend explicite le flot des données, ce dont les optimiseurs ont besoin.

nsw signifie « no signed wrap » : le dépassement d’un entier signé est un comportement indéfini en C, donc le compilateur a le droit de supposer qu’il n’arrive jamais, et les optimisations s’appuient sur cette hypothèse. C’est pourquoi un dépassement d’entier signé en C ne se contente pas de « boucler » : le compilateur peut avoir transformé le code en supposant qu’il était impossible.

5. L’optimisation

L’optimiseur applique des dizaines de passes à l’IR, chacune une petite transformation : placer les variables de pile en registres, supprimer les calculs en double et le code mort, intégrer (inline) les petites fonctions, dérouler les boucles, remplacer les divisions par des constantes. En -O2, la même fonction devient :

define i32 @square_sum(i32 %0, i32 %1) {
  %3 = mul nsw i32 %0, %0
  %4 = mul nsw i32 %1, %1
  %5 = add nuw nsw i32 %4, %3
  ret i32 %5
}

Les emplacements de pile, les rangements et les relectures ont disparu. Et l’optimiseur a prouvé que la somme de deux carrés, en l’absence de dépassement, ne peut pas être négative : l’add a gagné un drapeau nuw (no unsigned wrap), un fait qu’il pourra exploiter plus loin.

Comme chaque frontal de langage produit la même IR, le même optimiseur et les mêmes générateurs de code servent le C, le C++, Rust, Swift et d’autres. Cette séparation — frontal, milieu, dorsal (front end, middle end, back end) — explique qu’un nouveau langage ou un nouveau CPU ne demande qu’une seule pièce nouvelle.

6. La génération de code

Le générateur de code traduit l’IR en instructions machine de la cible. Il sélectionne les instructions, alloue les registres virtuels illimités sur les 16 registres du CPU, en débordant sur la pile quand ils manquent, et ordonnance les instructions pour le pipeline. Le résultat est de l’assembleur. Pour x86-64, -O0 face à -O2 :

; -O0                               ; -O2
square_sum:                         square_sum:
    push rbp                            imul edi, edi
    mov  rbp, rsp                       imul esi, esi
    mov  DWORD PTR [rbp-4], edi         lea  eax, [rsi+rdi]
    mov  DWORD PTR [rbp-8], esi         ret
    mov  eax, DWORD PTR [rbp-4]
    imul eax, DWORD PTR [rbp-4]
    mov  ecx, DWORD PTR [rbp-8]
    imul ecx, DWORD PTR [rbp-8]
    add  eax, ecx
    pop  rbp
    ret

La version optimisée ne touche jamais la mémoire : les arguments arrivent dans edi et esi comme le prévoit la convention d’appel, et l’addition finale est faite par lea, qui additionne deux registres dans un troisième en une instruction.

Le compilateur intégré au simulateur fonctionne comme -O0 : chaque variable reçoit un emplacement de pile, et chaque ligne de C correspond visiblement à ses instructions. Zoomez depuis le niveau du C pour comparer :

Live · square_sum compilé dans votre navigateur

C source — click a line number for a breakpoint

int square_sum(int a, int b) {
return a * a + b * b;
}
int main() {
return square_sum(3, 4);
}

step 0

Loading emulator…

Your program as you wrote it: the current line, its variables by name, and its output.

Le programme renvoie 25 après 27 instructions.

Le pilote relie le tout

clang et gcc sont des pilotes (drivers) : de petits programmes qui lancent les vraies étapes avec les bonnes options. clang -### affiche ce qu’il lancerait, sans le lancer : le compilateur proprement dit (clang -cc1 … -O2 -emit-obj), qui effectue ici aussi l’étape d’assemblage en interne, puis l’éditeur de liens du système. Chaque étape a une option pour s’y arrêter, ce qui permet d’inspecter une compilation :

S’arrêter après…	Option	Résultat
le préprocesseur	`-E`	C développé
la compilation	`-S`	assembleur (`.s`) ; ajouter `-masm=intel` pour la syntaxe Intel
la compilation en IR	`-S -emit-llvm` (clang)	IR LLVM (`.ll`)
l’assemblage	`-c`	fichier objet (`.o`)
l’édition de liens	(par défaut)	exécutable

Pour la rétro-ingénierie, ce pipeline explique ce qui reste dans un binaire. Macros, commentaires, noms des variables locales et arbre syntaxique ont tous disparu. Ce qui survit, c’est le résultat optimisé de l’étape 6 — plus, si le binaire n’est pas dépouillé (stripped), les noms des symboles, et les informations de débogage s’il a été compilé avec -g.

À retenir

Une compilation C est un pipeline : préprocesseur → compilateur (analyse lexicale, analyse syntaxique, analyse sémantique, IR, optimiseur, générateur de code) → assembleur → éditeur de liens.
Le préprocesseur substitue du texte (#include, macros) sans connaître le C.
L’analyseur lexical produit des tokens, l’analyseur syntaxique construit un AST, et l’analyse sémantique résout les noms, vérifie les types et ajoute les conversions implicites.
L’IR (l’IR LLVM, en forme SSA) est le lieu de l’optimisation, partagé par tous les langages et toutes les cibles. nsw montre comment le comportement indéfini autorise des optimisations.
Le générateur de code sélectionne les instructions, alloue les registres et ordonnance le code. -O0 garde une correspondance lisible ligne à ligne ; -O2 réduit 11 instructions à 4.