Fonctionnement d'un ordinateur/La pile d'appel et les fonctions

Dans ce chapitre, nous allons étudier une fonctionnalité du processeur appelée la pile d'appel. Sans elle, certaines fonctionnalités de nos langages de programmation actuels n'existeraient pas ! Et facilite l'implémentation des fonctions ré-entrantes et des fonctions récursives.

Les fonctions et procédures logicielles

Un programme contient souvent des suites d'instructions dupliquées en plusieurs exemplaires, qui servent à effectuer une tâche bien précise : calculer une fonction mathématique, communiquer avec un périphérique, écrire un fichier sur le disque dur, etc. Dans les langages de programmation modernes, il est possible de ne conserver qu'un seul exemplaire en mémoire et l'utiliser au besoin. L'exemplaire en question est ce qu'on appelle une fonction, ou encore un sous-programme.

C'est au programmeur de « sélectionner » ces suites d'instructions et d'en faire des fonctions. Pour exécuter une fonction, il faut exécuter un branchement dont l'adresse de destination est celle de la fonction : on dit qu'on appelle la fonction. Toute fonction se termine aussi par un branchement, qui permet au processeur de revenir là où il en était avant d'appeler la fonction.

Principe des sous-programmes.

Les langages de programmation actuels ont des fonctionnalités liées aux fonctions, qui simplifient bien la vie des programmeurs.

En premier lieu, une fonction peut calculer des données temporaires, souvent appelées des variables locales. Ces variables locales sont des données accessibles par le code de la fonction mais invisibles pour tout autre code. La variable locale est dite déclarée dans le code de la fonction, mais inaccessible ailleurs. Les variables locales sont opposées aux variables globales, qui sont accessibles dans tout le programme, par toute fonction. L'usage des variables globales est déconseillé, mais on en a parfois besoin.

En second lieu, la fonction peut prendre des opérandes et/ou calculer un résultat. Les fonctions mathématiques complexes sont dans ce cas : elles prennent des opérandes en entrée et fournissent un résultat. Mais ce ne sont pas les seules. Par exemple, une fonction qui ouvre un fichier prend en opérande le nom de ce fichier. Les opérandes envoyées à une fonction sont appelés des arguments ou paramètres. Les résultats sont eux appelés des valeurs de retour et sont récupérés par le programme principal pour qu'il en fasse quelque chose. Généralement, c'est le programmeur qui décide de conserver une donnée et d'en faire une valeur de retour.

Implémenter des fonctions peut se faire sans support de la part du processeur. Cependant, tous les processeurs modernes incorporent des techniques pour accélérer les fonctions ou rendre leur implémentation plus simple. Au-delà des instructions d'appel et de retour de fonction, les processeurs modernes incorporent une technique appelée la pile d'appel, que nous allons voir dans la section suivante.

La sauvegarde des registres

Lorsqu'un sous-programme s'exécute, il va utiliser certains registres qui sont souvent déjà utilisés par le programme principal. Pour éviter d'écraser le contenu des registres, on doit donc conserver une copie de ceux-ci dans la mémoire RAM. Une fois que le sous-programme a fini de s'exécuter, il remet les registres dans leur état original en chargeant la sauvegarde dans les registres adéquats. Ce qui fait que lorsqu'un sous-programme a fini son exécution, tous les registres du processeur reviennent à leur ancienne valeur : celle qu'ils avaient avant que le sous-programme ne s'exécute. Rien n'est effacé !

La gestion des variables locales, des arguments et des valeurs de retour est gérée par la sauvegarde/restauration des registres du processeur. Les arguments sont passés à une fonction dans un registre, qui est préparé avant l'exécution de la fonction. Lorsque la fonction est appelée, elle lit ce registre pour récupérer l'opérande/argument. Les registres pour les arguments ne sont pas sauvegardés ni restaurés après la fin de la fonction. Les valeurs de retour sont gérées de la même manière. Elles sont placées dans un registre spécifique, qui est lu par le programme principal pour consulter cette valeur de retour. Ce registre de retour n'est pas restauré à la fin de la fonction.

La sauvegarde des registres est le plus souvent effectuée par le logiciel, par un petit morceau de code se chargeant de sauvegarder les registres un par un. Plus rarement, certains processeurs ont une instruction pour sauvegarder les registres. C'est le cas sur les processeurs ARM1, qui ont une instruction pour sauvegarder n'importe quel sous-ensemble des registres du processeur. On peut par exemple choisir de sauvegarder le premier et le troisième registre en RAM, sans toucher aux autres. Le processeur se charge alors automatiquement de sauvegarder les registres uns par un en mémoire, bien que cela ne prenne qu'une seule instruction pour le programmeur.

L'implémentation matérielle de cette instruction est décrite dans les deux articles suivants :

• Counting bits in hardware: reverse engineering the silicon in the ARM1 processor
• More ARM1 processor reverse engineering: the priority encoder

La sauvegarde de l'adresse de retour

Une fois le sous-programme fini, il faut reprendre l’exécution du programme principal là où il s'était arrêté. Plus précisément, le programme doit reprendre à l'instruction qui est juste après le branchement d'appel de fonction. L'adresse de celle-ci étant appelée l'adresse de retour. Reprendre au bon endroit demande d'exécuter un branchement inconditionnel vers cette adresse de retour.

Mais vu qu'une fonction apparaît plusieurs fois dans notre programme, il y a plusieurs possibilités de retour, qui dépend de où est appelé la fonction. Mais comment savoir à quelle instruction reprendre l'exécution de notre programme, une fois le sous-programme terminé ? La seule solution est de sauvegarder l'adresse de retour lorsqu'on appelle la fonction. Et cela peut se faire de plusieurs manières différentes, suivant là où est mémorisée l'adresse de retour.

Une solution dédie un registre spécialisé pour l'adresse de retour, appelé le registre d'adresse de retour. Lorsque le processeur appelle une fonction, l'adresse de retour est sauvegardée dans ce registre, grâce à une instruction Branch And Link. Lorsqu'une fonction termine, l'adresse dans ce registre est utilisée par le branchement qui termine la fonction. La technique a été utilisée sur le processeur TMS 1000 de Texas Instrument, et quelques autres processeurs très peu puissants. Ce sont tous des processeurs anciens. Mais les autres processeurs utilisent d'autres solutions bien différentes.

La pile d'adresse de retour de certaines architectures embarquées

La solution précédente sauvegarde l'adresse de retour d'une fonction dans un registre. Elle gère le cas à une seule fonction, mais ne marche pas si une fonction en exécute une autre. C'est une situation très courant, que tout programmeur rencontre dès les premiers cours/exercices portant sur les fonctions. Pour donner un exemple, une fonction mathématique qui calcule le nombre de permutations d'un ensemble devra exécuter la fonction de calcul de la factorielle (une opération mathématique). Ou encore une fonction qui vérifie si un numéro de sécurité sociale est correct devra utiliser plusieurs fonctions, chacune faisant une vérification indépendante (on vérifie que telle partie du numéro colle bien, au nom, telle autre au sexe, telle autre à la date de naissance, et ainsi de suite). Une telle situation porte le nom de fonctions imbriquées.

Et gérer les fonctions imbriquées demande de l'aide de la part du processeur. Il existe plusieurs méthodes pour cela. La solution la plus utilisée de nos jours, utilise une fonctionnalité des processeurs appelée la pile d'appel. Mais nous n'allons pas voir la pile d'appel immédiatement. A la place, nous allons en voir une variante fortement simplifiée, utilisée sur certaines architectures embarquées faible performance. Cette solution simplifiée gère les fonctions imbriquées, mais ne gère pas les fonctions dites récursives, terme qu'on expliquera plus bas.

Les piles : une structure de données ordonnée

Avec des fonctions imbriquées, il faut sauvegarder plusieurs adresses de retour, une par fonction appelée. Par exemple, si une fonction A exécute une fonction B, qui elle-même exécute une fonction C, il faut sauvegarder trois adresses de retour : celle où retourner à la fin de la fonction A (dans le programme principal), celle où retourner à la fin de la fonction B (dans la fonction A), celle où retourner à la fin de la fonction C (dans la fonction B).

De plus, elles doivent être sauvegardées dans un certain ordre : de la plus récente à la plus ancienne. Elles doivent être sauvegardées dans l'ordre A, B, C. Par contre, elles seront utilisées dans l'ordre inverse lors du retour de la fonction. En clair, une fois que la fonction C termine, on utilise l'adresse de retour C associée, puis celle de la fonction B quand elle termine, puis celle de A quand elle termine.

Une manière de décrire ce fonctionnement est de le comparer à une pile d'assiette : on peut parfaitement rajouter une assiette au sommet de la pile d'assiette, ou enlever celle qui est au sommet, mais on ne peut pas toucher aux autres assiettes. On ne peut accéder qu'à l'adresse située au sommet de la pile. Comme pour une pile d'assiette, on peut rajouter ou enlever une adresse au sommet de la pile, mais pas toucher aux adresses en dessous, ni les manipuler. L'idée est d'organiser les adresses de retour de la même manière, en utilisant une structure de donnée appelée une pile, qui est bien connue des programmeurs.

Le nombre de manipulations possibles sur cette pile d'adresse se résume donc à deux manipulations de base qu'on peut combiner pour créer des manipulations plus complexes. On peut ainsi :

• retirer l'adresse de pile au sommet de la pile, pour l'utiliser : on dépile.
• ajouter une adresse au-dessus des adresses existantes : on empile.

Primitives de gestion d'une pile.

Si vous regardez bien, vous remarquerez que l'adresse au sommet de la pile est la dernière donnée à avoir été ajoutée (empilée) sur la pile. Ce sera aussi la prochaine à être dépilée (si on n'empile pas d'adresse au-dessus). Ainsi, on sait que dans cette pile, les données sont dépilées dans l'ordre inverse d'empilement. Il s'agit d'un comportement dit LIFO : dernier arrivé, premier sorti. Ce qui est exactement ce qu'on recherche pour la gestion des adresses de retour.

Stack (data structure) LIFO.

La pile d'adresse de retour

La pile d'adresse de retour est une pile, qui mémorise des adresses de retour des fonctions. Lorsqu'une fonction est exécutée, elle empile son adresse de retour au sommet de la pile. Lorsqu'elle se termine, elle dépile l'adresse de retour, celle qui est au sommet de la pile, et effectue un branchement vers celle-ci. Reste à implémenter la pile d'adresse de retour. Pour cela, il y a deux solutions : l'intégrer au processeur, la placer dans la mémoire RAM;

La première utilise une mémoire LIFO, qui n'est autre qu'une pile implémentée avec des transistors. Toute écriture dans ces mémoires ajoute/empile une donnée dedans, toute lecture dépile la donnée la plus récente. Pour rappel, une mémoire LIFO est fabriquée à partir d'une RAM dédiée, qui utilise une case mémoire par adresse. L'idée est de commencer à remplir les cases mémoires à partir de l'adresse 0, à partir du début de la mémoire. La première adresse est placée dans l'adresse 0, la suivante est empilée à l'adresse suivante (l'adresse 1), celle qui suit est placée dans l'adresse encore suivante (l'adresse 2), et ainsi de suite. Les adresses seront alors naturellement mémorisées dans l'ordre, il y a juste à mémoriser où se trouve le sommet de la pile. Pour cela, la mémoire RAM est couplée à un registre qui mémorise où se situe le sommet de la pile dans la mémoire RAM. Le registre est incrémenté à chaque fois qu'on empile une donnée, décrémenté quand on dépile une donnée.

Microarchitecture d'une mémoire LIFO

Si quelques architectures à pile ont utilisé une pile séparée du processeur, c'était une solution loin d'être idéale. Il fallait ajouter un bus dédié entre la mémoire LIFO et le processeur, donc beaucoup de broches. Une alternative est d'intégrer la mémoire LIFO au processeur. Avec l'augmentation du nombre de transistors, intégrer une pile d'adresse de retour au processeur n'est plus un problème. De nombreux microcontrôleurs et microprocesseurs embarqués utilisent cette technique. Mais elle a un défaut : la pile peut contenir un nombre maximal d'adresses, ce qui peut poser certains problèmes. Si l'on souhaite utiliser plus de cadres de pile que possible, il se produit un débordement de pile. En clair, l'ordinateur plante !

Une autre solution place la pile d'adresse de retour en mémoire RAM. L'avantage est qu'on n’est pas limité par la taille de la mémoire LIFO. Le problème est qu'il faut émuler une piler à partir d'un morceau de mémoire RAM. Et la solution est très simple, bien qu'elle vous paraitra un peu contrintuitive. L'idée s'inspire beaucoup de l'implémentation d'une mémoire LIFO, à savoir qu'on commence à remplir la RAM à partir d'une adresse, et qu'on mémorise où se trouve le sommet de la pile.

Pile d'adresse de retour en mémoire RAM.

Cependant, on ne peut pas commencer à remplir la RAM à partir de l'adresse 0 : le programme à exécuter ou des données sont à cet endroit-là. La solution est alors de commencer à remplir à partir de l'adresse haute, la dernière adresse de la mémoire RAM. On remplit alors la pile du haut de la mémoire vers le bas. Les adresses sont empilées dans l'ordre décroissant des adresses, de la dernière adresse vers la première. Le tout est illustré ci-contre.

Une fois cela fait, il suffit d'ajouter un registre qui mémorise où se situe le sommet de la pile. Le registre qui indique où est le sommet de la pile, quelle est son adresse, est appelé le pointeur de pile, ou encore le Stack Pointer (SP). Il est décrémenté lorsqu'on empile une adresse, incrémenté lorsqu'on en dépile une. Il est incrémenté/décrémenté de X si une adresse prend X bytes.

Pile d'adresses de retour

Les instructions d'appel et de retour de fonction

Disposer d'une pile d'adresses de retour est un premier pas. Mais il manque de quoi la manipuler, pour empiler ou dépiler des adresses de retour. Pour cela, une solution est d'utiliser des instructions spécialisées pour les appels et retour de fonction, qui modifient automatiquement la pile d'adresse. Les instructions en question sont des améliorations de l'instruction branch and link vue plus haut.

Appeler une fonction demande d’empiler l'adresse de retour, de modifier le pointeur de pile, puis de brancher vers l'adresse de la fonction. Il existe une instruction pour empiler l'adresse de retour et décrémenter le pointeur de pile. Elle est suivie par un branchement pour appeler la fonction. Le branchement d'appel de fonction, la sauvegarde de l'adresse de retour et la gestion du pointeur de pile sont fusionnés en une seule instruction d'appel de fonction.

De même, le retour de la fonction demande de faire un branchement vers l'adresse de retour et de restaurer le pointeur de pile, etc. Là encore, certains processeurs disposent d'une instruction de retour de fonction dédiée.

L'instruction d'appel de fonction est souvent appelée l'instruction CALL, l'instruction de retour de fonction est souvent appelée l'instruction RET. Des processeurs émulent ces instructions d'appel/retour de fonction avec un branchement complété par d'autres instructions.

Function call in assembly.

Vous remarquerez que ces instructions adressent le pointeur de pile implicitement. Elles manipulent le pointeur de piel, mais n'ont pas besoin qu'on fournisse son nom de registre. Il s'agit là d'un des rares exemple d'adressage implicite. Et encore une fois, il s'agit d'un cas où l'adressage implicite est le fait de branchements.

La sauvegarde des registres et la gestion des arguments sans récursivité

La sauvegarde des registres est réalisée par la fonction elle-même, grâce à un code de sauvegarde au tout début de la fonction et un code de restauration à sa toute fin. Pour cela, le compilateur alloue une petite portion de mémoire, dans laquelle les registres sont copiés lors d'un appel de fonction. La zone de mémoire en question n'a pas de nom consacré par la terminologie, mais je vais l'appeler la register save area. Chaque fonction a sa propre portion de mémoire allouée rien que pour elle. Elle contient juste ce qu'il faut pour sauvegarder les registres, rien de plus. Chaque registre a sa position attitrée dans cette portion de RAM, le code de sauvegarder/restauration des registres en tient compte.

Pour la gestion des arguments, la même méthode peut être utilisée. Le compilateur attribue à chaque fonction une petite portion de RAM où les arguments sont écrits avant l'appel de la fonction. Là encore, la zone de mémoire en question n'a pas de nom consacré par la terminologie, mais je vais l'appeler la function argument area. Le code qui appelle la fonction écrit les arguments dans cette portion de RAM, chaque argument a sa position attitrée, le code est conçu pour en tenir compte. Puis il appelle la fonction et celle-ci lit les arguments en RAM quand elle en a besoin, elle connait leur adresse à l'avance.

Et même chose pour les variables locales, avec une function local area.

Dans les deux cas, le processeur ne se préoccupe pas vraiment de la sauvegarde des registres ou des arguments. Il n'a aucun moyen d'accélérer le processus. La seule possibilité est de fournir des instructions dédiées à la sauvegarde des registres, qu'on a mentionné plus haut.

La pile d'appel : le support des fonctions récursives

L'usage d'une pile d'adresses de retour est une solution intelligente, simple, mais avec un gros défaut qu'il faut aborder. Le problème est qu'elle ne gère pas les fonctions dites récursives. Les fonctions récursives sont des fonctions qui s'appellent elles-mêmes. Elles sont assez rares, mais les programmeurs ont tous eu un cours sur le sujet lors de leurs études, c'est un passage obligé. Il existe aussi des fonctions dites indirectement récursives, où une fonction A appelle une fonction B, qui appelle une fonction C, qui appelle la fonction A (mais avec des opérandes/arguments différents).

Les cadres de pile

En soi, une pile d'adresse de retour fonctionne avec des fonctions récursives. Mais le mécanisme de sauvegarde des registres et de gestion des arguments ne fonctionne pas. Un exemple : imaginez une fonction A qui appelle la fonction B, qui appelle la fonction C, qui elle-même appelle la fonction B. Il y a deux instances de la fonction B en même temps : celle appelée par la fonction A, celle appelée par la fonction C. Et les deux instances ont chacune avec ses propres arguments, sans compter que chacune doit sauvegarder les registres qu'elle modifie. Le même problème a lieu dans le cas général : avec une fonction récursive, il est possible que plusieurs instances de la fonction s'exécutent.

Idéalement, il faudrait plusieurs register save area, plusieurs function local area et plusieurs function argument area, une par instance de la fonction. Mais on ne peut pas préallouer plusieurs register save area, plusieurs function local area et plusieurs function argument area, cela prendrait trop de place, sans compter qu'on sera limité en terme de nombre d'instances par fonction. Une autre solution réalloue dynamiquement plusieurs function local area/register save area/function argument area, exactement autant qu'il y a d'instances. C'est ce qui est fait sur les processeurs modernes, qui utilisent pour ce faire une pile d'appel.

L'idée est d'élargir la pile d'adresse de retour, de manière à ce qu'elle mémorise aussi des register save area, des function local area et des function argument area. Précisément, la pile mémorise des cadres de pile, des espèces de blocs de mémoire de taille fixe ou variable suivant le processeur. Chaque cadre de pile mémorise l'adresse de retour d'un appel de fonction, une register save area, une function local area et une function argument area, avec parfois des informations en plus.

Pile d'appel et cadres de pile.

Les cadres sont créés à chaque appel de fonction et respectent l'organisation en pile. La pile d'adresse de retour est remplacée par une pile appelée la pile d'appel, qui contient plusieurs cadres de pile placés les uns à la suite des autres dans la mémoire. Et comme pour la pile d'adresses de retour, la pile d'appel démarre à l'adresse maximale, et descend vers les adresses plus basses, au fur et à mesure qu'on ajoute des cadres de pile, comme illustré ci-dessous.

Pile d'appel avec les cadres de pile.

La pile peut contenir un nombre maximal de cadres, ce qui peut poser certains problèmes. Si l'on souhaite utiliser plus de cadres de pile que possible, il se produit un débordement de pile. En clair, l'ordinateur plante !

Quelques compilateurs gardent une trace des limites de chaque cadre de pile. Pour cela, ils complémentent le pointeur de pile avec une autre adresse, qui indique la base du cadre de pile. Elle est appelée le Frame Pointer (FP), ou pointeur de contexte. Il est surtout utile pour les outils de debogages, mais est souvent omis dans les codes optimisés.

Frame pointer.

Les instructions PUSH et POP pour gérer la pile

Lorsqu'on appelle une fonction, on crée un cadre de pile qui une taille suffisante pour stocker toutes les informations nécessaires pour que l'appel de fonction se passe comme prévu : l'adresse de retour, les arguments/paramètres, la copie de sauvegarde des registres du processeur, les variables locales, etc. Cependant, il nous manque un mécanisme pour ajouter ces données dans un cadre de pile. Les instructions d'appel/retour de fonction permettent d'empiler/dépiler l'adresse de retour, mais pas plus. Heureusement, le processeur intègre des instructions pour empiler ou dépiler des données sur la pile d'appel.

Les données sont ajoutés ou retirés de la pile grâce à deux instructions nommées PUSH et POP.

• L'instruction PUSH permet d'empiler une donnée. Elle prend l'adresse de la donnée à empiler, charge la donnée, et met à jour le pointeur de pile.
• L'instruction POP dépile la donnée au sommet de la pile, la stocke à l'adresse indiquée dans l'instruction, et met à jour le pointeur de pile.

Instruction Push.

Instruction Pop.

Les instructions PUSH/POP ont une source et une destination. L'instruction PUSH prend une source, et empile son contenu sur le sommet de la pile, qui est la destination. La source peut être un registre ou une adresse mémoire, éventuellement une constante intégrée dans l'instruction. L'instruction POP fait l'inverse. Sa source est le sommet de la pile, il est envoyé vers une destination qui est soit un registre, soit une adresse mémoire.

Une instruction PUSH/POP effectue un accès mémoire pour transférer la source vers la destination. Mais elles altèrent aussi le pointeur de pile. Il est décrémenté à chaque instruction PUSH, incrémenté à chaque instruction POP. Il est incrémenté/décrémenté de la taille d'un registre, donc de 2 octets sur un processeur 16 bits, 4 octets sur un processeur 32 bits, 8 sur un processeur 64 bits. L'incrémentation/décrémentation du pointeur de pile est donc une vulgaire opération arithmétique, réalisée soit dans des circuits spécialisés, soit dans les circuits de calcul normaux.

Les instructions PUSH et POP adressent le pointeur de pile implicitement. Seule la source est adressée explicitement pour les instructions LOAD, la destination pour les instructions STORE. Les instructions PUSH et POP ont donc un encodage assez court, surtout comparé aux instructions LOAD et STORE. Mais fondamentalement, les instructions PUSH et POP sont des instructions d'accès mémoire LOAD/STORE/MEMCOPY couplées à une incrémentation/décrémentation du pointeur de pile.

La sauvegarde/restauration des registres et la valeur de retour

Les instructions PUSH et POP sont utilisées pour sauvegarder les registres et les restaurer. Pour cela, imaginons qu'ils sont sauvegardés et restaurés à l'intérieur de la fonction. Ils sont sauvegardés au tout début de la fonction, la restauration a lieu à la toute fin, juste avant l'instruction de retour de fonction. Sauvegarder un registre se fait avec une instruction PUSH, qui a pour source le registre à sauvegarder. Le registre est alors placé au sommet de la pile, juste après les données déjà empilées. La restauration se fait avec une instruction POP ayant pour destination ce même registre. Les registres sont sauvegardés dans un ordre précis, avec les instructions PUSH dans un certain ordre, les instructions POP pour dépiler se font dans l'ordre inverse.

Par exemple, pour un processeur avec 4 registres nommés R0, R1, R2 et R3, voici ce que donnerait le code de la fonction :

push R0 ;
push R1 ;
push R2 ;
push R3 ;

...

pop R3 ;
pop R2 ;
pop R1 ;
pop R0 ;

Cependant, la restauration doit tenir compte de la valeur de retour de la fonction, qui peut être conservée soit dans les registres, soit dans la pile d'appel. Il est théoriquement possible de la stocker dans un registre, mais il faut faire attention à ce qu'elle ne soit pas écrasée lors de la restauration des registres. Dans ce cas, un registre au moins n'est pas restauré directement, mais laisse la place à la valeur de retour. C'est le code après la fonction qui gère la situation et qui restaure lui-même le registre en question.

Une autre solution est de mettre la valeur de retour sur la pile d'appel, en l'empilant. La valeur de retour est transférée dans la pile avec une instruction PUSH, le code appelant la récupére avec une instruction POP.

Les arguments, les variables locales et la valeur de retour

La transmission des arguments à une fonction peut se faire en les copiant soit dans la pile, soit dans les registres. Avec le passage par la pile, les arguments sont empilés sur la pile et la fonction les récupéré dans la pile directement. Avec le passage par les registres, les paramètres sont copiés dans des registres, qui ne sont pas sauvegardés lors de l'appel de la fonction. Si on utilise le passage par les registres, il faut que le nombre de registres soit suffisant, ce qui dépend du nombre d'argument, mais aussi du nombre de registres. En conséquence, le passage par la pile est très utilisé sur les processeurs avec peu de registres, alors que les processeurs avec beaucoup de registres privilégient le passage par les registres.

La gestion des variables locales, arguments et valeurs de retour sont assez complexes. Et surtout, il y a beaucoup de manière de faire, qui dépendent de comment les compilateurs utilisent la pile d'appel. Les différentes manières sont appelées des conventions d'appel, calling convention en anglais. Ils standardisent des choses assez variées : comment sont organisées les données dans un cadre de pile, dans quel ordre sont envoyés les arguments, etc.

Voyons une version simplifiée de la convention d'appel des processeurs x86, sans frame pointer. Pour simplifier les explications, nous allons introduire les termes de code appelant et de code appelé. Le code appelant est celui qui exécute la fonction, le code appelé est la fonction elle-même.

Voici comment se déroule un appel de fonction :

• En premier lieu, le code appelant PUSH les arguments sur la pile. Il pourrait les passer par les registres, comme c'est le cas sur d'autres architectures avec plus de registres comme les architectures RISC-V, mais passons. Les arguments sont empilés avant d'appeler la fonction, car celle-ci ne sait pas dans quels registres ils sont, ni à quelles adresses.
• En second lieu, une instruction d'appel de fonction est émise. Elle sauvegarde l'adresse de retour et effectue un branchement vers l'adresse de la fonction.
• En troisième lieu, le pointeur de pile est modifié de manière à faire de la place aux variables locales sur la pile, ainsi qu'à la register save area. La zone réservée regroupe la register save area et la function local area. Les variables locales ne sont pas empilées sur la pile, ni dépilées. Le code appelant réserve juste de la place et il lira/écrira dedans comme bon lui semble. Pour cela, on soustrait la taille de la function local area au pointeur de pile.

La pile ressemble donc à ceci :

Pile exécution contenant deux cadres de pile, un pour la fonction drawLine() et un autre pour la fonction drawSquare(). Le bloc d'activation correspond grosso-modo au cadre de pile, auquel on ajoute les arguments (non-compris dans le cadre de pile dans cet exemple, chose plutôt rare).

Le retour d'une fonction effectue le même processus, mais en sens inverse.

• Premièrement, les registres sont restaurés, en les lisant depuis la register save area. Sauf pour le registre qui contient la valeur de retour de la fonction, si elle existe.
• Deuxièmement, la place prise par les variables locales et les registres est libérée. Pour cela, on ajoute/retire la taille de la function local area du pointeur de pile, pour qu'il pointe avant la function local area, plutôt que après. Mais cela n'est possible que si le pointeur de pile est un registre nommé ou adressable explicitement.
• Troisièmement, on effectue une instruction de retour de fonction, qui lit l'adresse de retour depuis la pile et effectue un branchement dessus. Le pointeur de pile est aussi mis à jour.
• Enfin, les arguments sont enlevés de la pile. Les arguments ne sont pas dépilés, ils sont juste "effacés". L'idée est de modifier le pointeur de pile de manière à ce qu'il pointe avant la function argument area, plutôt que après, comme pour le retrait des variables locales.

L'exemple qu'on vient de effectue le retrait des arguments de la pile après l'instruction de retour de fonction. En clair, il délègue le retrait des arguments au code appelant. Le retrait des arguments s'appelle le nettoyage de la pile et il peut être délégué au code appelant ou à la fonction, tout dépend de la convention d'appel utilisée. L'exemple précédent a montré comment le code appelant s'occupe de nettoyer la pile. Mais on aurait pu montrer un autre exemple où le nettoyage est fait par la fonction, avant l'instruction de retour.

Dans l'exemple précédent, vous aurez remarqué que les arguments sont situés sous l'adresse de retour dans la pile. Comment donc la fonction pourrait s'occuper de nettoyer la pile ? La réponse est que l'instruction de retour de fonction s'en occupe ! Pour cela, elle a juste à soustraire la taille de la function argument area du pointeur de pile. Rien de compliqué, elle s'occupe déjà de faire une soustraction sur ce pointeurt en dépilant l'adresse de retour. Pour gérer le nettoyage de la pile, elle peut recevoir une opérande qui lui dit combien soustraire pour dépiler les arguments.

L'adressage du pointeur de pile

La section précédente a introduit un concept assez important : on doit parfois additionner ou soustraire une constante du pointeur de pile. Le pointeur de pile n'est plus seulement altéré par les instructions CALL, RET, PUSH et POP. Il est aussi altéré par des instructions d'addition et de soustraction. Pour cela, il y a deux solutions.

• La première est d'ajouter une instruction spécifique pour additionner/soustraire une constante au pointeur de pile.
• La seconde est de rendre le registre pointeur de pile adressable, de lui donner un nom/numéro de registre.

La seconde solution a un désavantage : on perd un registre adressable. Par exemple, sur un processeur avec des numéros de registres sur 4 bits, on peut adresser 16 registres. Un pointeur de pile adressable fait qu'on a 15 registres généraux et un pointeur de pile adressable. Avec un pointeur de pile sans numéro de registre, on a 16 registres généraux et un pointeur de pile séparé.

Les processeurs CISC utilisaient autrefois un registre dédié au pointeur de pile, qui était adressé implicitement ou explicitement. Sur les architectures RISC, le pointeur de pile a disparu et un registre général est utilisé à la place. Il faut dire que le pointeur de pile contient une adresse encodée avec un nombre entier, qui est incrémentée/décrémentée avec des opérations entières classiques. Autant utiliser un registre entier pour le pointeur de pile et effectuer des instructions arithmétiques normales.

La function local area et la function argument area sont donc deux zones mémoire séparées, mais placées dans un cadre de pile. Reste à récupérer les arguments ou les variables locales pour les charger dans les registres, quand on en a besoin. Pour cela, les instructions LOAD et STORE ne peuvent pas utiliser leur adresse mémoire, vu qu'elle change selon la position dans la pile. A la place, les instructions LOAD et STORE utilise une variante du mode d'adressage base + décalage, adaptée pour la pile.

Elles adressent arguments et variables locales par leur position dans le cadre de pile. Ils disent que telle variable locale est 8 octets avant le sommet de la pile, que tel argument est 16 octets avant, etc. L'adresse à lire/écrire se calcule en prenant le pointeur de pile et en additionnant/soustrayant la position, le décalage. Une instruction LOAD/STORE précise alors le décalage/position avec une constante immédiate, le pointeur de pile est lui adressé implicitement. L'instruction LOAD/STORE ajoute alors automatiquement cette position au pointeur de pile, pour générer l'adresse à lire/écrire.

Du moins, tout cela est valable si c'est un registre dédié. Si le pointeur de pile est adressable, l'adresse peut être calculée dans les registres et accédée via un simple adressage indirect.

Les optimisations et fonctionnalités de la pile d'appel

Les processeurs modernes incorporent de nombreuses fonctionnalités de sécurité, ainsi que des optimisations de la pile d'appel. Dans cette section, nous allons voir certaines d'entre elles.

L'instruction branch and link et le link register

L'optimisation que nous allons voir porte sur la gestion de l'adresse de retour. Plus haut, nous avons vu qu'elle est empilée sur la pile d'appel, donc en mémoire RAM. L'instruction d'appel de fonction effectue cette sauvegarde automatiquement, ou alors c'est le fait d'une instruction dédiée, peu importe. L'optimisation que nous allons voir sauvegarde l'adresse de retour dans les registres, soit dans un registre dédié, soit dans les registres généraux. Il s'agit d'une technique utilisée sur les processeurs RISC, qui ont beaucoup de registres. Ils peuvent donc dédier des registres pour l'adresse de retour, pour optimiser les appels de fonction.

Dans ce qui suit, nous désignerons le registre où est sauvegardé l'adresse de retour par le terme Link Register, qui sera abrévié LR dans ce qui suit. Il peut désigner soit un registre dédié, soit un registre général. Les architectures PA-RISC, RISC-V, SPARC et ARM utilisent un registre général comme link register, les processeurs POWER PC utilisaient un link register dédié, qui ne sert qu'à stocker l'adresse de retour et ne sert pas à autre chose. Le cas le plus simple est clairement celui où l'adresse de retour est sauvegardée dans un registre général arbitraire, donc le premier cas de la liste précédente. Mais nous ferons un abus de langage : nous parlerons de processeur à link register dans les trois cas précédents.

Les processeurs avec un Link Register disposent de deux instructions simplifiées pour les appels et retour de fonction. L'instruction d'appel de fonction est l'instruction Branch And Link. Elle effectue deux opérations : un branchement pour appeler la fonction, une copie de l'adresse de retour dans le link register. L'instruction Branch From Link Register est l'instruction de retour de fonction. Elle récupére l'adresse de retour dans le link register et effectue un branchement vers celle-ci. Il s'agit donc d'un simple branchement indirect, rien de plus.

L'idée est que la sauvegarde de l'adresse de retour sur la pile se fait en deux temps : la sauvegarde de l'adresse de retour dans le link register, puis la copie de ce registre dans la pile d'appel. Les instructions d'appel et de retour de fonction sont donc fortement simplifiées, vu qu'elles ne font pas d'accès mémoire. L'instruction Branch And Link est suivie par une instruction PUSH pour sauvegarder l'adresse de retour sur la pile. A l'inverse, un retour de fonction demande d'exécuter une instruction POP pour copier l'adresse de retour depuis la pile, puis de faire un branchement Branch From Link Register pour le retour de fonction.

L'avantage est que cela découple le branchement de la sauvegarde de l'adresse de retour sur la pile. L'instruction Branch And Link n'accède qu'aux registres, idem avec l'instruction Branch From Link Register. Et c'est pour ça qu'on doit les coupler avec une instruction PUSH ou POP. On utilise deux instructions pour l'appel d'une fonction, idem pour le retour, mais le tout est plus flexible. Les instructions PUSH et POP peuvent être éliminées dans certains cas, notamment pour ce qui s'appelle les fonctions terminales.

Une fonction terminale est une fonction qui n'appelle pas d'autres fonctions lors de son exécution. De telles fonctions tendent à être assez simples, surtout avec les pratiques de programmation actuelles. En conséquence, elles utilisent peu de registres, bien que ce ne soit qu'une tendance, pas une généralité. Sur les processeurs RISC, il y a assez de registres pour ne pas avoir besoin de sauvegarder l'adresse de retour sur la pile, elle peut rester dans les registres, il y en aura assez pour exécuter la fonction. Elles sauvegardent leur adresse de retour dans le link register, utilisent les registres généraux pour faire leur travail, et branchent vers l'adresse dans le link register une fois qu'elles ont terminé leur travail, pas besoin d’accéder à la pile. On évite donc deux accès mémoire pour de telles fonctions terminales, ce qui est plus rapide.

Le cas des fonctions imbriquées est cependant assez simple à gérer. L'adresse de retour étant dans un registre général, elle est sauvegardée en même temps que les autres, idem pour sa restauration. Imaginons le cas où une fonction A appelle une fonction B, qui appelle une fonction C. La fonction A effectue un appel de fonction avec l'instruction branch and link. La fonction B fait ses calculs, puis vient le moment d'exécuter la fonction C. Elle sauvegarde alors le link register, puis effectue l'instruction branch and link et exécute la fonction C. La fonction C est une fonction terminale : elle s'exécute et retourne en utilisant l'adresse dans le link register. La fonction B reprend la main et restaure alors le link register qu'elle avait sauvegardée, pour restaurer la bonne adresse de retour, celle de A. Lorsqu'elle retourne, elle utilise l'adresse dans le link register et reprend à la fonction A.

Les processeurs RISC sauvegardent l'adresse de retour dans un registre général. Sur les processeurs PA-RISC, RISC-V, IBM System/360 et z/Architecture, n'importe quel registre général peut mémoriser l'adresse de retour, le programme est codé pour en choisir un bien précis, de préférence un registre inoccupé ou à écraser. Les instructions branch and link et branch from link register adressent le registre choisit avec l'adressage inhérent, avec son nom de registre.

Sur les processeurs SPARC et ARM, le link register est un registre général, mais où les instructions branch and link et branch from link register adressent un registre général précis. Par exemple, sur les processeurs ARMv7, le link register est le registre général R14. L'adresse de retour est automatiquement sauvegardée dans le registre R14 par branch and link, elle est lue depuis ce registre par l'instruction branch from link register. Mais pendant l'exécution de la fonction, l'adresse peut être envoyée sur la pile d'appel ou déplacée dans un autre registre. Le link register est unique, il est adressé implicitement par des instructions.

Sur les architectures POWER PC, le link register est un registre dédié, qui n'est pas un registre général. Il ne sert qu'à stocker l'adresse de retour, pas autre chose. Mais il est possible de sauvegarder/restaurer le link register sur la pile d'appel. Il faut pour cela utiliser des instructions spéciales, qui copient le link register vers un registre général, ou directement sur la pile d'appel.

Le fenêtrage de registres

Le fenêtrage de registres est une amélioration de la technique précédente, qui est adaptée non pas aux interruptions, mais aux appels de fonction/sous-programmes. Là encore, lors de l'appel d'une fonction, on doit sauvegarder les registres du processeur sur la pile, avant qu'ils soient utilisés par la fonction. Plus un processeur a de registres architecturaux, plus leur sauvegarde prend du temps. Et là encore, on peut dupliquer les registres pour éviter cette sauvegarde. Pour limiter le temps de sauvegarde des registres, certains processeurs utilisent le fenêtrage de registres, une technique qui permet d'intégrer cette pile de registre directement dans les registres du processeur.

Fenêtre de registres.

La technique de fenêtrage de registres la plus simple duplique chaque registre architectural en plusieurs exemplaires qui portent le même nom. Chaque ensemble de registres architecturaux forme une fenêtre de registre, qui contient autant de registres qu'il y a de registres architecturaux. Lorsqu'une fonction s’exécute, elle se réserve une fenêtre inutilisée, et peut utiliser les registres de la fenêtre comme bon lui semble. Mais elle ne peut pas toucher aux registres dans les autres fenêtres, les fenêtres sont isolées les unes des autres. S'il ne reste pas de fenêtre inutilisée, on est obligé de sauvegarder une fenêtre complète dans la pile.

L'implémentation précédente a des fenêtres de taille fixe. C'était le fenêtrage de registre implémenté sur le processeur Berkeley RISC, et quelques autres processeurs. Des techniques similaires permettent cependant d'avoir des fenêtres de taille variable ! Avec des fenêtres de registre de taille variable, chaque fonction peut réserver un nombre de registres différent des autres fonctions. Une fonction peut réserver 5 registres, une autre 8, une autre 6, etc. Par contre, il y a une taille maximale. Les registres du processeur se comportent alors comme une pile de registres. Un exemple est celui du processeur AMD 29000, qui implémente des fenêtres de taille variable, chaque fenêtre pouvant aller de 1 à 8 registres. C'était la même chose sur les processeurs Itanium.

Il faut noter que les processeurs Itanium et AMD 29000 n'utilisaient le fenêtrage de registres que sur une partie des registres généraux. Par exemple, l'AMD 29000 disposait de 196 registres, soit 64 + 128. Les registres sont séparés en deux groupes : un de 64, un autre de 128. Les 128 registres sont ceux avec le fenêtrage de registres, à savoir qu'ils forment une pile de registres utilisée pour les appels de fonction. Les 64 registres restants sont des registres généraux normaux, où le fenêtrage de registre ne s'applique pas, et qui est accessible par toute fonction. Cette distinction entre pile de registres (avec fenêtrage) et registres globaux (sans fenêtrage) existe aussi sur l'Itanium, qui avait 32 registres globaux et 96 registres avec fenêtrage.

La pile fantôme pour vérifier les adresses de retour

Les compilateurs modernes peuvent complémenter la pile d'appel avec une pile d'adresse de retour. La pile d'appel stocke toujours les adresses stockées dans la pile d'appel, ce qui fait que la pile d'appel est redondante. Et c'est justement cette redondance qui est utile, dans le sens où certaines techniques de sécurité sont plus faciles à implémenter avec une pile d'appel séparée, comme on le verra plus bas.

Diverses attaques informatiques modifient l'adresse de retour d'une fonction pour exécuter du code malicieux. L'attaque insère un code malicieux dans un programme (par exemple, un virus) et l’exécute lors d'un retour de fonction. Pour cela, l'assaillant trouve un moyen de modifier l'adresse de retour d'une fonction mal codée, puis en détourne le retour pour que le processeur ne reprenne pas là où il le devrait, mais reprenne l’exécution sur le virus/code malicieux. Le code malicieux est programmé pour que, une fois son travail accompli, le programme reprenne là où il le devait une fois la fonction détournée terminée. Notons que les failles de sécurité de ce type sont plus compliquées si la pile d'adresse de retour est séparée de la pile d'appel, mais que ce n'est pas le cas sur les PC actuels.

Il existe diverses techniques pour éviter cela et certaines de ces techniques se basent sur une shadow stack, une pile fantôme. Celle-ci est une pile d'adresse de retour, mémorisée en mémoire ou dans le processeur, qui est utilisée pour vérifier que les retours de fonction se passent bien. L'avantage est que ces attaques consistent généralement à injecter des données volumineuses dans un cadre de pile, afin de déborder d'un cadre de pile, voire de déborder de la mémoire allouée à la pile. Autant c'est possible avec les cadres de la pile d'appel, autant ce n'est pas possible avec la pile fantôme, vu qu'on n'y insère pas ces données. De plus, les deux piles d'appel sont éloignées en mémoire, ce qui fait que toute modification de l'une a peu de chances de se répercuter sur l'autre.

La pile d'appel fantôme peut être gérée soit au niveau logiciel, par le langage de programmation ou le système d'exploitation, mais aussi directement en matériel. C'est le cas sur les processeurs x86 récents, depuis l'intégration par Intel de la technologie Control-flow Enforcement Technology. Il s'agit d'une pile fantôme gérée directement par le processeur. Quand le processeur exécute une instruction de retour de fonction RET, il vérifie automatiquement que l'adresse de retour est la même dans la pile d'appel et la pile fantôme. Si il y a une différence, il stoppe l’exécution du programme et prévient le système d'exploitation (pour ceux qui a ont déjà lu le chapitre sur les interruptions : il démarre une exception matérielle spécialisée appelée Control Flow Protection Fault.