La pile

Trente-deux cases, et tout le reste

Un processeur RISC-V a trente-deux registres, dont un qui vaut toujours zéro et deux ou trois qui ont déjà un emploi réservé. Il en reste donc moins de trente pour calculer. C'est beaucoup pour une addition, et très peu dès qu'un programme fait deux choses l'une après l'autre : le fragment qui vient ensuite a lui aussi besoin de registres, et il ne connaît pas ceux que le fragment précédent comptait garder.

Une première réponse consiste à déclarer des données nommées, comme au chapitre 2, et à y ranger ce qui déborde. Elle échoue sur trois points. Une donnée déclarée occupe une adresse fixe, choisie à l'assemblage, alors qu'une valeur temporaire n'a besoin d'exister que pendant quelques instructions. Une donnée déclarée porte un nom, alors qu'il faudrait en inventer un par valeur intermédiaire et par fragment de code. Surtout, une donnée déclarée est unique : si le même fragment de code s'exécute deux fois sans que la première soit terminée, ce qui arrive dès qu'une fonction s'appelle elle-même, les deux exécutions se disputent la même case et l'une écrase l'autre.

Ce qu'il faut est donc une zone de mémoire où l'on prend de la place pour un moment, où l'on repose ce qu'on avait pris, et où la place reprise redevient disponible. Une seule règle suffit à organiser cela sans tenir aucune comptabilité : ce qui est rangé en dernier est repris en premier. Cette règle porte le nom de la chose, une pile, comme une pile d'assiettes dont on ne retire que celle du dessus.

Une mémoire, deux occupants

La mémoire d'un programme est un seul grand tableau d'octets, partagé entre les données déclarées et la pile. Les données, elles, montent : la première déclaration se pose à l'adresse 0x1000, la suivante juste après, et ainsi de suite. Plus un programme déclare de données, plus loin vers le haut il arrive.

Si la pile montait elle aussi, il faudrait décider au départ où les données s'arrêtent et où la pile commence. Ce partage serait faux presque toujours : un programme qui déclare un gros tableau et n'empile presque rien perdrait de la place à un bout, et un programme qui déclare trois mots mais appelle des fonctions profondément imbriquées buterait sur une frontière posée trop bas, avec de la mémoire libre juste derrière.

Faire partir les deux occupants des deux bouts supprime la question. Les données montent depuis le bas, la pile descend depuis le haut, et la seule limite est leur rencontre. Aucune frontière n'est fixée à l'avance ; c'est l'usage réel qui décide du partage, programme par programme et instant par instant.

Le sommet de départ vaut ici 0x2000, soit 8 192 en décimal. Ce n'est pas un nombre magique : c'est le réglage par défaut des figures de ce module, modifiable par une ligne pile:. Sur une machine réelle, l'adresse est bien plus haute et le système d'exploitation la choisit au lancement, mais le principe est identique.

Le programme suivant met les deux occupants dans la même figure : trois mesures déclarées en bas, un mot empilé en haut, et la soustraction qui mesure ce qui reste libre entre les deux.

Quatre mille quatre-vingt-douze octets libres entre le dernier octet utilisé par les données et le sommet courant de la pile. Aucune ligne du programme n'a fixé cette valeur : elle est la conséquence de ce que le programme a réellement déclaré et réellement empilé.

Empiler : réserver, puis écrire

Empiler un mot demande deux instructions, toujours les mêmes, toujours dans cet ordre.

La première instruction réserve : elle retire quatre à sp, qui passe de 0x2000 à 0x1ffc. Rien n'est écrit, mais quatre octets viennent d'être déclarés occupés. La seconde écrit dans la case ainsi réservée, à l'adresse que sp désigne maintenant.

L'ordre des deux n'est pas indifférent. Écrire d'abord à -4(sp) puis déplacer sp donnerait le même contenu, mais il existerait un instant, entre les deux instructions, où un mot serait écrit en dehors de la zone réservée. Sur une machine de bureau ce n'est qu'un détail de style ; sur une machine qui interrompt un programme pour en traiter un autre, l'interruption qui survient à cet instant écrase le mot. La règle est donc : réserver d'abord, écrire ensuite.

La troisième instruction du programme est là pour la démonstration. Une fois le mot empilé, t0 peut servir à autre chose : c'est exactement la raison d'être de la manœuvre.

Dépiler : lire, puis rendre

Reprendre le mot demande les deux mêmes instructions, à l'envers.

Le chargement reprend la valeur, l'addition rend la place. Là encore l'ordre compte, et pour la même raison : rendre la place avant d'avoir lu laisserait un instant pendant lequel la valeur à lire se trouve en dehors de la zone réservée.

À la fin de ce programme, sp vaut de nouveau 0x2000 et la figure n'affiche plus aucune case de pile. Le mot 42 est pourtant toujours écrit à l'adresse 0x1ffc : dépiler n'efface rien, cela déclare seulement la place disponible. Le prochain empilement écrira par-dessus.

Voir la pile grandir

Trois empilements de suite, et la figure montre trois cases là où il n'y en avait aucune.

La figure affiche les cases du sommet courant jusqu'au sommet de départ, et signale d'une marque celle que sp désigne. Le mot empilé en dernier, 33, se trouve à l'adresse la plus basse, et c'est celui que lw t3, 0(sp) ramène. Le premier empilé, 11, se trouve tout en haut, à 8(sp), et il faudrait dépiler les deux autres pour l'atteindre par le sommet. Voilà la règle du dernier arrivé, premier sorti, non plus énoncée mais lue sur des adresses.

Les trois derniers chargements montrent au passage qu'une pile n'interdit pas de regarder plus bas que le sommet. Un décalage constant à partir de sp donne accès à n'importe quelle case déjà réservée, sans rien déplacer. C'est ce qui rend l'écriture suivante possible.

Réserver un cadre d'un seul mouvement

Quand un fragment de code sait combien de mots il lui faut, il n'a aucune raison de déplacer sp une fois par mot. Une seule soustraction réserve le tout, et les rangements se font par décalages.

Cette zone réservée en une fois porte un nom, le cadre. Elle contient tout ce dont un fragment de code a besoin le temps de son exécution, et elle disparaît d'un seul addi sp, sp, 12 à la fin. Le chapitre suivant montrera que c'est exactement la forme que prend une fonction : un cadre à l'entrée, un cadre rendu à la sortie, et entre les deux un code qui travaille par décalages à partir de sp.

Un détail de lecture mérite l'attention, parce qu'il surprend au premier abord. Le décalage 0 désigne l'adresse la plus basse du cadre, et le décalage le plus grand l'adresse la plus haute. Les cases se remplissent donc vers le bas quand les décalages diminuent, ce qui est la conséquence directe d'une pile qui descend.

Ce que coûte un rééquilibrage oublié

Le programme suivant contient une faute qui ne déclenche aucune erreur, et c'est justement ce qui la rend intéressante. Un premier fragment empile une valeur qu'il compte retrouver plus tard. Un second fragment empile deux mots et n'en dépile qu'un. Le premier reprend ensuite la main.

Le mot 7 est toujours en mémoire, intact, à l'adresse 0x1ffc. Personne ne l'a effacé. Simplement, sp ne le désigne plus : il pointe une case plus bas, celle du 100 abandonné par le fragment fautif, et le chargement final ramène donc 100. Aucune instruction n'a été refusée, aucun message n'a été affiché, et le programme se termine normalement avec une valeur fausse.

La seconde conséquence est plus insidieuse encore. À la fin, sp vaut 0x1ffc et non 0x2000 : quatre octets de pile sont perdus pour toujours. Un fragment qui dérive ainsi de quatre octets à chaque exécution et qui tourne dans une boucle fait descendre la pile sans fin, jusqu'à ce qu'elle rejoigne les données.

Deux façons de casser la pile

La première est signalée. Déplacer sp d'une quantité qui n'est pas multiple de quatre suffit à rendre le rangement suivant impossible.

L'instruction fautive n'est pas celle qui échoue. Le sw est correct ; c'est le addi d'avant qui a mis sp dans un état où plus aucun rangement de mot ne peut réussir. C'est une situation générale en assembleur, et la raison d'être du bouton qui recule : l'endroit où un programme s'arrête est rarement l'endroit où il s'est trompé.

La seconde façon n'est signalée par rien du tout. Il suffit que la pile descende assez pour atteindre les données.

La ligne pile: 0x1010 rapproche artificiellement les deux occupants, parce qu'il faudrait un millier d'empilements pour provoquer la même chose avec le réglage habituel. Le mécanisme, lui, est exactement celui d'un programme réel : le second empilement écrit à l'adresse 0x1008, qui est le troisième mot du tableau mesures. La mesure 30 devient 222. Le tableau n'a pas été déclaré trop court, le programme n'a pas dépassé un indice, et pourtant sa troisième valeur est fausse.

Un travail complet : renverser une suite

La pile ne sert pas qu'à ranger des valeurs en attente. Sa règle du dernier arrivé, premier sorti est un outil de calcul à elle seule. Le programme suivant lit un tableau de quatre valeurs, empile chacune, puis les ressort une à une dans un second tableau : l'ordre se trouve inversé sans qu'aucune instruction n'ait eu à s'en occuper.

Le parcours du tableau reprend le calcul d'adresse du chapitre 7 : slli t3, t1, 2 multiplie l'indice par quatre, l'addition à l'adresse de base donne l'adresse de l'élément. La nouveauté tient en quatre instructions, deux pour empiler et deux pour dépiler, et c'est tout ce qu'il faut pour renverser une suite de longueur quelconque.

Au dernier pas, sp est revenu à 0x2000. Les deux boucles empilent et dépilent le même nombre de mots, la pile est donc rendue dans l'état où elle a été trouvée. C'est la propriété que le chapitre suivant va exiger de chaque fonction.

Un dernier exercice de lecture

Le programme suivant échange le contenu de deux registres en passant par la pile, sans faire appel à un troisième registre. Prévoir, avant de lancer la figure, l'adresse touchée par chacun des deux rangements, puis les valeurs de t0 et de t1 à la fin.

La méthode

1. Compter les mots nécessaires avant d'écrire la première instruction, puis réserver le cadre d'un seul addi sp, sp, -4n, plutôt que de déplacer sp une fois par valeur.
2. Écrire le rééquilibrage en même temps que la réservation : taper la ligne addi sp, sp, +4n immédiatement après avoir tapé la ligne négative, et remplir le corps entre les deux.
3. Ranger par décalages constants à partir de sp, le décalage 0 pour la case la plus basse, et noter en commentaire ce que contient chaque décalage du cadre.
4. Vérifier l'alignement : tout déplacement de sp est un multiple de quatre, sans exception.
5. Relever sp au début et à la fin d'un fragment dans la figure : les deux valeurs doivent être identiques. Un écart signale un rééquilibrage manquant, même quand le résultat affiché semble correct.
6. Chercher la faute en amont de l'arrêt : reculer d'un pas depuis l'instruction qui échoue, car c'est presque toujours celle qui a placé sp ou une adresse dans un état impossible.

Synthèse

• La pile existe parce que les registres sont trente-deux et qu'un programme a besoin de retenir plus de valeurs que cela, pour une durée courte, sans leur donner de nom ni d'adresse fixe.
• Les données montent depuis 0x1000, la pile descend depuis 0x2000. Faire partir les deux occupants des deux bouts de la mémoire évite de fixer une frontière à l'assemblage, et laisse l'usage réel décider du partage.
• Empiler, c'est réserver puis écrire : addi sp, sp, -4 puis sw. Dépiler, c'est lire puis rendre : lw puis addi sp, sp, 4. Les deux ordres sont imposés, pour qu'aucun mot ne soit jamais écrit ou lu en dehors de la zone réservée.
• La figure affiche la pile case par case, du sommet courant au sommet de départ, avec une marque sur la case que sp désigne. Le dernier mot empilé occupe l'adresse la plus basse et se lit à 0(sp).
• Un cadre se réserve d'un seul mouvement, addi sp, sp, -12 pour trois mots, et se remplit par décalages, le décalage 0 désignant la case la plus basse.
• Un rééquilibrage oublié ne déclenche aucune erreur : sp reste décalé, le code suivant lit la case du voisin, et la pile perd quelques octets à chaque passage.
• Rien ne surveille la frontière entre la pile et les données. Une pile qui descend trop loin écrase les données en silence, et un déplacement de sp qui n'est pas multiple de quatre rend impossible le rangement suivant.

La pile est maintenant un outil. Appeler en fait le cœur du langage machine : une fonction appelée doit savoir où revenir, et cette adresse de retour se range, comme le reste, sur la pile.