Fonctions, appels et la pile

Les fonctions sont le principal moyen de structurer un programme : un nom pour un travail qu’on peut utiliser sans savoir comment il est fait. Pour l’appelant, un appel ressemble à une nouvelle opération élémentaire. En dessous, chaque appel a un coût et une structure. Le chapitre sur les conventions d’appel, au niveau de l’assembleur, en montre la mécanique — call, ret, registres d’arguments, pointeur de cadre. Ce chapitre regarde ce qu’elle implique pour le code C : où vivent paramètres et variables locales, combien de temps ils durent, et ce qui en découle.

Chaque appel a son propre cadre

Quand une fonction est appelée, elle reçoit un nouveau cadre de pile (stack frame) : un bloc de mémoire de pile qui contient son adresse de retour, son pointeur de cadre sauvegardé, ses variables locales et ses paramètres. Quand la fonction revient, le cadre est libéré. Le mot important est chaque : deux appels à la même fonction, même actifs en même temps, ont deux cadres distincts. C’est ce qui rend possible la récursivité — une fonction qui s’appelle elle-même :

La démo s’ouvre en pleine récursivité, au point le plus profond. La pile d’appels montre main et cinq cadres de fact, et chaque cadre a son propre n : 5, 4, 3, 2 et 1. Ils s’appellent tous n, mais ce sont cinq variables différentes à cinq adresses différentes, espacées de 32 octets. Continuez à avancer et les cadres se défont un à un, chacun multipliant son propre n dans le résultat : le programme renvoie 120.

L’exemple classique de Tanenbaum est celui des tours de Hanoï : déplacer une pile de disques d’un piquet à un autre, un disque à la fois, sans jamais poser un grand disque sur un petit. La solution récursive tient en trois lignes — écarter n − 1 disques, déplacer le plus grand, reposer les n − 1 disques dessus :

Il affiche les 7 déplacements pour trois disques. Chaque appel actif garde ses propres n, from, to et other dans son cadre pendant que ses sous-appels s’exécutent. Le livre dessine une pile qui monte vers les adresses hautes ; sur x86, ARM et RISC-V, elle descend, et chaque nouveau cadre se place sous celui de son appelant. L’idée reste la même.

Les paramètres sont des copies

Le C passe chaque argument par valeur : la fonction reçoit une copie dans son propre cadre. Modifier le paramètre modifie la copie, jamais la variable de l’appelant :

void reset(int n) {
    n = 0;          // modifie le n de reset
}

int main() {
    int n = 5;
    reset(n);
    return n;       // toujours 5
}

Pour qu’une fonction modifie une variable de l’appelant, on lui passe son adresse, comme la fonction swap de pointeurs et tableaux. Les tableaux semblent faire exception, mais non : ce qui est copié, c’est le pointeur en lequel le tableau se dégrade. Les structures, en revanche, sont copiées en entier, c’est pourquoi on passe en général les grosses structures par pointeur.

Les locales meurent au retour de la fonction

Une variable locale n’existe que tant que le cadre de sa fonction existe. Renvoyer son adresse donne à l’appelant un pointeur vers une mémoire déjà libérée — un pointeur pendant (dangling pointer). L’appel suivant réutilise le même espace de pile :

Il renvoie 7, pas 42. Le cadre de other a été construit exactement au même endroit que celui de make, et son y a atterri là où se trouvait x. Les compilateurs signalent ce cas — clang écrit address of stack memory associated with local variable 'x' returned. gcc va plus loin : il compile silencieusement return &x; en un retour de NULL, si bien que le vrai programme plante sur une erreur de segmentation au lieu de lire des données périmées. Les deux comportements sont permis, car utiliser une variable morte est un comportement indéfini.

La correction dépend de ce que la valeur doit survivre. Renvoyer la valeur elle-même plutôt que son adresse, laisser l’appelant fournir un tampon, ou allouer sur le tas avec malloc, le sujet du chapitre suivant.

Jusqu’où peut-on descendre ?

La pile est une zone de taille fixe réservée au démarrage d’un thread. Sous Linux, elle fait 8 Mio par défaut pour le thread principal (ulimit -s affiche 8192, en Kio), sous Windows 1 Mio. Chaque appel en consomme un cadre, donc une récursivité trop profonde — ou qui ne s’arrête jamais — l’épuise. Au-delà de la limite de la pile, le système laisse une zone de garde jamais projetée : y toucher provoque un défaut, et le processus meurt sur une erreur de segmentation. C’est le débordement de pile (stack overflow).

Le cadre de cette fonction contient un tableau de 4 000 octets, elle consomme donc vite la pile. Appuyez sur Continue pour l’exécuter jusqu’au bout :

La pile du simulateur fait 1 Mio, et elle déborde à la profondeur 261 : la pile d’appels se termine par dive(n=261), au-dessus de 260 autres cadres de dive. Le même programme sous Linux, avec sa pile de 8 Mio, descend environ huit fois plus loin — au-delà de 2 000 appels — avant d’être tué avec le code de sortie 139.

La plupart des récursivités ne posent aucun problème : la pile n’a besoin que de la profondeur de la récursivité, et parcourir un arbre équilibré d’un milliard d’éléments demande une trentaine de niveaux. Le danger vient des récursivités dont la profondeur dépend de l’entrée — une liste chaînée, un arbre dégénéré, un document JSON très imbriqué — et des gros tableaux locaux, surtout dans les threads, dont la pile est souvent plus petite.

Ce que l’optimisation fait aux appels

Un appel coûte plus cher que le travail qu’il enveloppe quand la fonction est minuscule : placer les arguments dans les registres, le call, construire puis démonter le cadre, le ret. Les compilateurs optimisants suppriment ce surcoût de deux façons.

L’intégration (inlining) recopie le corps d’une petite fonction dans son appelant. Avec clang -O2 :

static int square(int x) { return x * x; }
int f(int a) { return square(a) + 1; }

f:
    imul edi, edi          ; square, intégrée
    lea  eax, [rdi+1]      ; + 1
    ret

Il ne reste aucun appel, et aucune fonction square dans le résultat. L’intégration rend aussi possibles d’autres optimisations, car le compilateur voit maintenant les deux côtés de l’appel à la fois.

La récursivité peut devenir une boucle. Le fact récursif ci-dessus, compilé par clang -O2 (avec la vectorisation désactivée pour rester lisible), ne contient aucun appel :

fact:
    mov  eax, 1            ; le produit courant
    cmp  edi, 2
    jl   .done
.loop:
    imul eax, edi          ; produit *= n
    cmp  edi, 2
    lea  ecx, [rdi-1]
    mov  edi, ecx          ; n = n - 1
    ja   .loop
.done:
    ret

Le compilateur a remarqué que la multiplication pouvait s’accumuler dans une variable au fil du calcul, et a réécrit la récursivité en une boucle qui n’utilise qu’un cadre au lieu de n. Avec ses réglages par défaut, clang va encore plus loin et vectorise cette boucle avec des instructions SSE, qui multiplient quatre nombres à la fois. Le cas général est l’élimination des appels terminaux (tail calls) : quand un appel est la toute dernière chose que fait une fonction, son cadre peut être réutilisé et l’appel devient un saut — comme le jmp rax de la fonction apply optimisée du chapitre précédent. Les compilateurs C le font comme une optimisation, pas comme une garantie, donc un code C ne peut pas compter dessus ; des langages comme Scheme l’exigent.

Cela compte quand on lit des binaires : dans du code optimisé, les petites fonctions ont disparu dans leurs appelants, les fonctions récursives sont parfois des boucles, et le graphe d’appels du source ne correspond plus à celui du code machine.

Au-delà de la pile : les coroutines

Un appel de fonction suit une imbrication stricte : l’appelé termine avant que l’appelant ne reprenne, donc les cadres peuvent vivre sur une pile. Le livre de Tanenbaum décrit aussi les coroutines, qui enfreignent cette règle : deux routines se relancent l’une l’autre, chacune reprenant là où elle s’était arrêtée. Leur état ne peut pas vivre dans un cadre de pile jeté à chaque bascule.

Les langages modernes ont rendu cela courant. Les générateurs de Python, et les fonctions async de JavaScript, Python, C#, Rust et C++20, peuvent se suspendre en plein milieu et reprendre plus tard. Leurs compilateurs gardent les variables locales de la fonction suspendue dans un objet sur le tas plutôt que dans un cadre de pile, pour qu’elles survivent d’une reprise à l’autre.

À retenir

• Chaque appel reçoit son propre cadre de pile, avec sa propre copie de chaque paramètre et de chaque locale. C’est ce qui rend la récursivité possible : cinq appels actifs à fact, cinq n différents.
• Le C passe les arguments par valeur ; pour modifier la variable de l’appelant, on passe son adresse.
• Les locales meurent au retour de la fonction : un pointeur vers l’une d’elles est pendant, et l’appel suivant réutilise la mémoire.
• La pile est petite et fixe — 8 Mio sous Linux, 1 Mio sous Windows par défaut. Une récursivité trop profonde touche la zone de garde non projetée : c’est le débordement de pile.
• Les optimiseurs intègrent les petites fonctions et transforment la récursivité en boucles (appels terminaux) : le code machine optimisé ne contient pas forcément les appels écrits.
• Les coroutines, les générateurs et les fonctions async se suspendent en cours d’appel ; leur état vit sur le tas plutôt que sur la pile.