Appeler

Le vocabulaire de ce chapitre

Ce chapitre est le plus chargé du module, et il vaut mieux le lire en deux fois, en s'arrêtant après la sauvegarde de ra, que d'un seul trait. Deux instructions y prennent enfin leur sens, jal et ret : le mémento les a listées, et la section qui suit ne fait rien d'autre que montrer ce qu'elles rendent possible. Les neuf autres, employées dans les figures, viennent des chapitres précédents et se rappellent en trois lignes.

Mémoire et pile : addi sp, sp, -4 réserve de la place, sw ra, 0(sp) écrit quatre octets à l'adresse contenue dans sp, lw ra, 0(sp) les relit.

Valeurs : li t0, 0 pose une constante dans un registre, mv a0, a1 recopie un registre dans un autre, add t0, t0, a0 additionne deux registres et addi a0, a0, 10 ajoute une constante.

Sauts : j fin saute sans condition, beq t0, a0, sortir saute si deux registres sont égaux, beqz a0, fond saute si un registre vaut zéro.

Le mémento du jeu d'instructions donne la forme complète de chacune, et les variantes que ce chapitre n'emploie pas.

Sauter, et savoir revenir

Un saut ordinaire, j fin, va quelque part et ne revient pas. Pour qu'un fragment de code puisse servir depuis plusieurs endroits, il faut qu'il sache où repartir, et cette information change à chaque appel. Elle ne peut donc pas être écrite dans le fragment : il faut la lui donner.

L'instruction jal fait les deux choses d'un coup. Elle range dans un registre l'adresse de l'instruction qui suit l'appel, puis elle saute. Le registre utilisé par convention est ra, pour return address, l'adresse de retour.

programme

1. 0x0jal ra, doubler
2. 0x4j finjal zero, fin
3. 0x8add a0, a0, a0
4. 0xcretjalr zero, ra, 0

registres

ra	0
a0	21

Reculer Exécuter une instruction Aller à la fin Reprendre Modifier le programme

Rien n'a encore été exécuté. Le compteur ordinal pointe la première instruction, en 0x0.

Le premier pas range 4 dans ra, c'est-à-dire 0x4, et le compteur ordinal saute à 0x8 où commence doubler. Cette valeur 4 n'a pas été choisie par qui a écrit le programme : elle est calculée à l'exécution à partir de l'adresse de l'appel. Le même code appelé depuis un autre endroit y trouverait une autre adresse.

Le retour s'écrit ret, et la figure affiche l'instruction réelle à côté : jalr zero, ra, 0. Ce n'est pas un hasard de notation. jalr est la sœur de jal : elle saute à une adresse contenue dans un registre au lieu d'une adresse écrite dans l'instruction, et elle range elle aussi l'adresse de retour, ici dans zero, c'est-à-dire nulle part. Revenir d'une fonction, c'est sauter à l'adresse que ra contient, sans rien mémoriser.

Les trois écritures tiennent en trois lignes, et tout le chapitre repose sur elles.

Une seule case pour l'adresse de retour

ra est un registre, donc une case unique. Une fonction qui en appelle une autre exécute un second jal, qui range une nouvelle adresse dans cette même case. L'adresse qui s'y trouvait est perdue, et la première fonction ne sait plus où revenir.

Le programme suivant contient exactement cette faute. La fonction f est appelée par le programme principal, puis elle appelle g. Rien d'autre.

programme

1. 0x0jal ra, f
2. 0x4j finjal zero, fin
3. 0x8addi a0, a0, 1
4. 0xcjal ra, g
5. 0x10addi a0, a0, 10
6. 0x14retjalr zero, ra, 0
7. 0x18addi a0, a0, 100
8. 0x1cretjalr zero, ra, 0

registres

ra	0
a0	5

Reculer Exécuter une instruction Aller à la fin Reprendre Modifier le programme

Rien n'a encore été exécuté. Le compteur ordinal pointe la première instruction, en 0x0.

Les deux valeurs prises par ra racontent toute l'histoire. Au premier appel, ra reçoit 4, l'adresse du j fin qui suit. Quand f appelle g, ra reçoit 16, soit 0x10 : l'adresse du addi a0, a0, 10 situé à l'intérieur de f. Le 4 a disparu.

g revient correctement, puisque ra contient bien ce qu'il faut pour elle. Puis f exécute son ret, qui saute à ra, c'est-à-dire à 0x10, c'est-à-dire à l'intérieur de f juste après l'appel de g. Le programme ajoute dix, revient à 0x10, ajoute dix, revient à 0x10. La figure s'arrête sur le message de limite parce que ce programme ne se termine jamais.

Ce comportement est inhabituel, et c'est ce qui le rend instructif : le programme ne plante pas, ne refuse rien, et boucle sur trois instructions bien écrites. La faute n'est dans aucune d'elles ; elle est dans l'idée qu'un registre unique pourrait retenir deux adresses à la fois.

Sauver ra sur la pile

Il faut donc mettre l'adresse de retour à l'abri pendant l'appel imbriqué, et la reprendre avant de revenir. La pile du chapitre précédent est faite pour cela : un mot réservé à l'entrée, rendu à la sortie.

programme

1. 0x0jal ra, f
2. 0x4j finjal zero, fin
3. 0x8addi sp, sp, -4
4. 0xcsw ra, 0(sp)
5. 0x10addi a0, a0, 1
6. 0x14jal ra, g
7. 0x18addi a0, a0, 10
8. 0x1clw ra, 0(sp)
9. 0x20addi sp, sp, 4
10. 0x24retjalr zero, ra, 0
11. 0x28addi a0, a0, 100
12. 0x2cretjalr zero, ra, 0

registres

ra	0
sp	0x2000
a0	5

Reculer Exécuter une instruction Aller à la fin Reprendre Modifier le programme

Rien n'a encore été exécuté. Le compteur ordinal pointe la première instruction, en 0x0.

Quatre instructions ajoutées, et le programme se termine. Les deux premières forment le prologue de f : réserver un mot, y ranger ra. Les deux dernières forment son épilogue : reprendre ra, rendre le mot. Entre les deux, f peut appeler qui elle veut et autant de fois qu'elle veut, puisque son adresse de retour n'est plus dans un registre que l'appel écrase, mais dans une case de pile qui lui appartient.

La fonction g, elle, n'a pas de prologue et n'en a pas besoin : elle n'appelle personne, donc rien n'écrase son ra. Une fonction qui n'appelle aucune autre fonction s'appelle une fonction feuille, et elle se passe de cadre de pile.

L'accord qui rend un code appelable

Deux fonctions écrites par deux personnes différentes doivent se mettre d'accord sur trois points : où l'appelant dépose les arguments, où l'appelé dépose le résultat, et quels registres survivent à l'appel. Aucun de ces points n'est imposé par le matériel. Les registres n'ont pas de rôle câblé, a0 et t0 sont deux cases identiques, et le processeur exécuterait sans broncher n'importe quelle autre répartition.

L'accord en vigueur pour RISC-V répartit les trente-deux registres en trois groupes, et la question qu'il tranche est toujours la même : qui, de l'appelant ou de l'appelé, paie la sauvegarde d'une valeur qui doit traverser un appel.

Deux lignes de ce tableau se lisent ensemble. Une valeur confiée à un registre t est à la charge de l'appelant : à lui de la recopier ailleurs s'il tient à la retrouver après l'appel. Une valeur confiée à un registre s est à la charge de l'appelé : à lui de la ranger sur la pile s'il veut la place, et de la remettre avant de revenir. Le coût existe dans les deux cas, et la convention ne le supprime pas ; elle dit seulement qui le paie, et elle le dit une fois pour toutes, de façon que les deux moitiés d'un programme puissent être écrites sans se connaître.

programme

1. 0x0jal ra, total
2. 0x4mv s0, a0addi s0, a0, 0
3. 0x8li a0, 100addi a0, zero, 100
4. 0xcli a1, 20addi a1, zero, 20
5. 0x10li a2, 3addi a2, zero, 3
6. 0x14jal ra, total
7. 0x18add s0, s0, a0
8. 0x1cj finjal zero, fin
9. 0x20add a0, a0, a1
10. 0x24add a0, a0, a2
11. 0x28retjalr zero, ra, 0

registres

ra	0
s0	0
a0	4
a1	7
a2	9

Reculer Exécuter une instruction Aller à la fin Reprendre Modifier le programme

Rien n'a encore été exécuté. Le compteur ordinal pointe la première instruction, en 0x0.

La fonction total ne contient aucune indication sur ses arguments : elle additionne a0, a1 et a2 parce que la convention dit que c'est là qu'ils se trouvent. Elle range son résultat dans a0 pour la même raison. L'appelant, de son côté, remplit a0 à a2 avant chaque appel et lit a0 après. Ni l'un ni l'autre n'a besoin de connaître le code de l'autre.

Un détail passe souvent inaperçu : la fonction écrase a0, qui contenait un argument. C'est permis, et c'est même la norme. Les registres d'arguments appartiennent à l'appelé pendant l'exécution de l'appel, et l'appelant qui tient à son argument doit le recopier ailleurs avant d'appeler.

Les registres que l'appelé peut détruire

La ligne de partage entre les registres t et les registres s n'est pas un raffinement théorique. Elle décide de qui doit recopier quoi, et l'ignorer produit des résultats faux qu'aucun outil ne signale.

Le programme suivant additionne le double de trois valeurs. L'appelant garde son total dans t0. La fonction doubler se sert elle aussi de t0, ce que la convention l'autorise à faire.

programme

1. 0x0li t0, 0addi t0, zero, 0
2. 0x4jal ra, doubler
3. 0x8add t0, t0, a0
4. 0xcmv a0, a1addi a0, a1, 0
5. 0x10jal ra, doubler
6. 0x14add t0, t0, a0
7. 0x18mv a0, a2addi a0, a2, 0
8. 0x1cjal ra, doubler
9. 0x20add t0, t0, a0
10. 0x24j finjal zero, fin
11. 0x28li t0, 0addi t0, zero, 0
12. 0x2cadd t0, a0, a0
13. 0x30mv a0, t0addi a0, t0, 0
14. 0x34retjalr zero, ra, 0

registres

ra	0
t0	0
a0	4
a1	7
a2	9

Reculer Exécuter une instruction Aller à la fin Reprendre Modifier le programme

Rien n'a encore été exécuté. Le compteur ordinal pointe la première instruction, en 0x0.

Le total annoncé est 36, le total juste est 40. Rien n'a été signalé. L'appelant a confié à t0 une valeur qui devait survivre à trois appels, alors que t0 est précisément un registre dont la convention dit qu'il ne survit pas. La fonction appelée n'a commis aucune faute ; l'appelant en a commis une, et c'est lui qui obtient un résultat faux.

La même chose dans les règles

Il suffit de déplacer le total dans un registre sauvegardé. L'appelant range son cumul dans s0, et la convention garantit qu'aucune fonction bien écrite ne le touchera. La contrepartie est du côté de l'appelé : une fonction qui veut utiliser un registre s doit le sauver sur la pile et le rendre tel qu'elle l'a trouvé.

programme

1. 0x0li s0, 0addi s0, zero, 0
2. 0x4jal ra, doubler
3. 0x8add s0, s0, a0
4. 0xcmv a0, a1addi a0, a1, 0
5. 0x10jal ra, doubler
6. 0x14add s0, s0, a0
7. 0x18mv a0, a2addi a0, a2, 0
8. 0x1cjal ra, doubler
9. 0x20add s0, s0, a0
10. 0x24j finjal zero, fin
11. 0x28addi sp, sp, -4
12. 0x2csw s1, 0(sp)
13. 0x30add s1, a0, a0
14. 0x34mv a0, s1addi a0, s1, 0
15. 0x38lw s1, 0(sp)
16. 0x3caddi sp, sp, 4
17. 0x40retjalr zero, ra, 0

registres

ra	0
sp	0x2000
s0	0
s1	0
a0	4
a1	7
a2	9

Reculer Exécuter une instruction Aller à la fin Reprendre Modifier le programme

Rien n'a encore été exécuté. Le compteur ordinal pointe la première instruction, en 0x0.

Le total est maintenant juste. Le prix payé est visible dans la figure : à chaque appel, doubler empile s1, s'en sert, le reprend et rend la place. Deux accès mémoire par appel, pour une fonction qui ne fait qu'une addition. C'est la raison d'être de la distinction entre t et s : elle laisse le programmeur choisir quelle moitié du coût il paie, la recopie par l'appelant pour les t, la sauvegarde par l'appelé pour les s.

La récursion, une fois la pile comprise

Une fonction récursive est une fonction qui s'appelle elle-même. Elle ne demande aucun mécanisme nouveau : l'adresse de retour se sauve comme avant, et les valeurs locales se rangent dans un cadre de pile qui appartient à cet appel-là. Deux appels en cours ont deux cadres à deux adresses différentes, et ne se marchent pas dessus.

La fonction suivante calcule la somme des entiers de 1 à a0. Le jeu d'instructions de base ne sait pas multiplier, et cette somme n'en a pas besoin : elle s'écrit avec une addition par appel.

programme

1. 0x0jal ra, somme
2. 0x4j finjal zero, fin
3. 0x8addi sp, sp, -8
4. 0xcsw ra, 4(sp)
5. 0x10sw a0, 0(sp)
6. 0x14beqz a0, fondbeq a0, zero, fond
7. 0x18addi a0, a0, -1
8. 0x1cjal ra, somme
9. 0x20lw t0, 0(sp)
10. 0x24add a0, a0, t0
11. 0x28j retourjal zero, retour
12. 0x2cli a0, 0addi a0, zero, 0
13. 0x30lw ra, 4(sp)
14. 0x34addi sp, sp, 8
15. 0x38retjalr zero, ra, 0

registres

ra	0
sp	0x2000
t0	0
a0	3

Reculer Exécuter une instruction Aller à la fin Reprendre Modifier le programme

Rien n'a encore été exécuté. Le compteur ordinal pointe la première instruction, en 0x0.

Le cadre réservé par chaque appel fait huit octets : un mot pour l'adresse de retour à 4(sp), un mot pour l'argument à 0(sp). L'argument doit être sauvé parce que l'appel récursif va écraser a0, d'abord en le décrémentant, puis en y déposant son résultat. Après le retour de l'appel imbriqué, lw t0, 0(sp) reprend l'argument de cet appel-ci, et l'addition compose le résultat.

La figure montre la pile descendre de 0x1ff8 à 0x1fe0 pendant la descente, puis remonter case par case pendant les retours. Les adresses de retour rangées dans les cadres se lisent aussi : celle du premier cadre vaut 4, l'adresse dans le programme principal, et les trois autres valent 32, c'est-à-dire 0x20, l'adresse de l'instruction qui suit l'appel récursif. Trois appels récursifs, trois copies de la même adresse de retour, chacune rangée dans son propre cadre.

Le bouton « Modifier le programme » rend la vérification immédiate : remplacer a0 = 3 par a0 = 5 dans la première ligne suffit, la figure se réassemble et se relance à la frappe. Le même programme rend alors 15 et la pile descend jusqu'à 0x1fd0. La profondeur de la pile est proportionnelle à l'argument, et c'est la raison pour laquelle une récursion trop profonde finit par rencontrer les données. Le message qu'un langage de haut niveau affiche alors, en parlant de profondeur maximale de récursion, est la traduction de ce qui se voit ici.

L'adresse de retour et les variables locales partagent la pile

Voici le point qui justifie le chapitre entier, et qui n'a rien d'une curiosité.

Un cadre de pile contient l'adresse de retour et les variables locales de la fonction. Ces deux choses sont côte à côte dans la même zone, gérées par le même registre, écrites par les mêmes instructions. Rien ne les sépare, rien ne les distingue, et rien ne vérifie qu'une écriture destinée à une variable locale reste dans les limites de cette variable.

La fonction suivante réserve un cadre de douze octets : deux mots de tampon, à 0(sp) et 4(sp), et l'adresse de retour au-dessus, à 8(sp). Elle remplit ensuite le tampon d'autant de mots que a0 en demande. Avec deux, tout se passe bien.

programme

1. 0x0jal ra, remplir
2. 0x4li t6, 1addi t6, zero, 1
3. 0x8j finjal zero, fin
4. 0xcaddi sp, sp, -12
5. 0x10sw ra, 8(sp)
6. 0x14li t0, 0addi t0, zero, 0
7. 0x18mv t1, spaddi t1, sp, 0
8. 0x1cbeq t0, a0, sortir
9. 0x20li t2, 0x41414141lui t2, 267284
10. 0x24addi t2, t2, 321
11. 0x28sw t2, 0(t1)
12. 0x2caddi t1, t1, 4
13. 0x30addi t0, t0, 1
14. 0x34j bouclejal zero, boucle
15. 0x38lw ra, 8(sp)
16. 0x3caddi sp, sp, 12
17. 0x40retjalr zero, ra, 0

registres

ra	0
sp	0x2000
t0	0
t1	0
t2	0
a0	2
t6	0

Reculer Exécuter une instruction Aller à la fin Reprendre Modifier le programme

Rien n'a encore été exécuté. Le compteur ordinal pointe la première instruction, en 0x0.

La valeur écrite, 0x41414141, est le mot formé de quatre octets valant 0x41, le code de la lettre A. Elle est choisie pour être reconnaissable, et la figure montre d'ailleurs que li la produit en deux instructions, lui puis addi, puisqu'elle dépasse largement les douze bits d'un immédiat.

Il suffit maintenant de demander trois mots au lieu de deux. Une seule valeur change dans tout le programme.

programme

1. 0x0jal ra, remplir
2. 0x4li t6, 1addi t6, zero, 1
3. 0x8j finjal zero, fin
4. 0xcaddi sp, sp, -12
5. 0x10sw ra, 8(sp)
6. 0x14li t0, 0addi t0, zero, 0
7. 0x18mv t1, spaddi t1, sp, 0
8. 0x1cbeq t0, a0, sortir
9. 0x20li t2, 0x41414141lui t2, 267284
10. 0x24addi t2, t2, 321
11. 0x28sw t2, 0(t1)
12. 0x2caddi t1, t1, 4
13. 0x30addi t0, t0, 1
14. 0x34j bouclejal zero, boucle
15. 0x38lw ra, 8(sp)
16. 0x3caddi sp, sp, 12
17. 0x40retjalr zero, ra, 0

registres

ra	0
sp	0x2000
t0	0
t1	0
t2	0
a0	3
t6	0

Reculer Exécuter une instruction Aller à la fin Reprendre Modifier le programme

Rien n'a encore été exécuté. Le compteur ordinal pointe la première instruction, en 0x0.

Le troisième tour de boucle écrit à 8(sp), qui n'est plus du tampon mais la case où le prologue avait rangé l'adresse de retour. Le 4 qui s'y trouvait est remplacé par 1 094 795 585, c'est-à-dire 0x41414141. Aucune erreur n'est signalée à ce moment-là : une écriture en mémoire est une écriture en mémoire, et cette case est aussi légitime qu'une autre.

L'épilogue s'exécute ensuite normalement. lw ra, 8(sp) recharge consciencieusement ce qu'il trouve, addi sp, sp, 12 rend le cadre, et ret saute à l'adresse contenue dans ra. Le compteur ordinal prend donc la valeur 0x41414140, et le programme s'arrête là : il n'y a aucune instruction à cette adresse.

Ce qui se produit ensuite dépend de la machine. Ici, le compteur ordinal tombe sur une adresse vide et la figure le dit. Sur un ordinateur ordinaire, l'adresse existe, elle contient des octets, et le processeur les exécute comme des instructions : soit il rencontre très vite quelque chose d'impossible et le système arrête le programme, soit l'adresse a été choisie avec soin et le programme continue de tourner en faisant autre chose que ce que son auteur a écrit.

Les protections modernes ne suppriment pas ce mécanisme, elles le rendent difficile à exploiter : disposition de la mémoire tirée au hasard à chaque lancement, valeur témoin posée devant l'adresse de retour et vérifiée avant le ret, zones de mémoire marquées comme non exécutables. Chacune de ces défenses se comprend d'un coup quand on a vu la figure précédente, et reste une formule creuse tant qu'on ne l'a pas vue.

1.Que fait exactement jal ra, doubler ?

Elle saute à doubler et empile l'adresse de retour sur la pileElle copie le contenu de ra dans le compteur ordinalElle range dans ra l'adresse de l'instruction qui suit l'appel, puis saute à doubler

2.Une fonction f appelle g sans rien sauver. Que devient l'adresse de retour de f ?

Elle est empilée automatiquement par le processeurElle est conservée, car g la remet en place en revenantElle est écrasée par le jal qui appelle g, et le ret de f renvoie à l'intérieur de f

3.Quelle fonction n'a pas besoin de sauver ra ?

Une fonction qui n'appelle aucune autre fonctionUne fonction qui ne modifie aucun registre sUne fonction dont le résultat tient dans a0

4.Un appelant garde un cumul dans t0 pendant trois appels de fonction. Que peut-il en attendre ?

Rien : la convention autorise l'appelé à détruire t0, et le cumul sera faux sans qu'aucune erreur soit signaléeQue le cumul survive, car les fonctions bien écrites ne touchent pas aux registres de l'appelantUn refus à l'assemblage

5.Dans une fonction récursive, pourquoi l'argument est-il rangé sur la pile ?

Parce que l'appel récursif écrase a0, et que chaque appel a besoin de retrouver le sien après le retourParce que la pile est plus rapide que les registresParce que les arguments doivent toujours être sauvés en mémoire

6.Une écriture dépasse un tampon local de deux mots et en écrit trois. Que se passe-t-il au ret ?

Le compteur ordinal prend la valeur écrite par erreur, parce que le troisième mot a remplacé l'adresse de retourLe programme continue normalement, le tampon étant agrandi automatiquementL'écriture est refusée dès le troisième mot

La méthode

1. Écrire le prologue et l'épilogue avant le corps de toute fonction qui contient un appel : réserver le cadre, y ranger ra, et taper immédiatement les deux instructions symétriques de sortie.
2. Compter le cadre en mots : un mot pour ra, un mot par valeur locale qui doit survivre à un appel, arrondi au multiple de quatre octets.
3. Choisir les registres selon leur durée de vie, et non selon leur nom : un t pour ce qui ne franchit aucun appel, un s pour ce qui doit survivre, sachant qu'un s employé par une fonction doit être sauvé par elle.
4. Relever ra dans la figure juste après chaque jal, et vérifier que la valeur correspond bien à l'adresse de l'instruction suivante dans la colonne de gauche.
5. Vérifier que sp retrouve sa valeur d'entrée à la sortie de chaque fonction, exactement comme au chapitre précédent : un écart signale un cadre mal rendu, qui fera revenir la fonction n'importe où.
6. Comparer la taille réservée et la quantité écrite dès qu'un tampon local est rempli par une boucle, puisque c'est la seule chose qui sépare un programme correct d'un programme dont un tiers choisit la suite.

Synthèse

• jal range dans ra l'adresse de l'instruction suivante, puis saute. ret est jalr zero, ra, 0 : le compteur ordinal prend la valeur de ra. Il n'existe aucune instruction « appeler une fonction » au-delà de cela.
• ra est une case unique : une fonction qui en appelle une autre perd son adresse de retour et revient à l'intérieur d'elle-même, ce qui produit une boucle sans fin plutôt qu'une erreur. La solution est de sauver ra sur la pile à l'entrée et de le reprendre à la sortie.
• La convention d'appel place les arguments dans a0 à a7 et le résultat dans a0, laisse t0 à t6 à la disposition de l'appelé, et exige que s0 à s11 soient rendus intacts. Ce n'est pas une règle du matériel : c'est un accord, et l'enfreindre rend simplement un code inappelable.
• Confier une valeur à un registre t pendant un appel donne un résultat faux sans message : le programme annonce 36 là où la somme vaut 40.
• Une fonction récursive réserve un cadre par appel, ce qui permet à plusieurs exécutions de la même fonction de coexister. La pile descend pendant la descente et remonte pendant les retours, et sa profondeur suit celle de la récursion.
• L'adresse de retour et les variables locales partagent le même cadre. Une écriture qui dépasse un tampon local écrase l'adresse de retour, et le ret saute là où la donnée écrite le dit : ici 0x41414140, où il n'y a aucune instruction.

Tout ce que ce chapitre construit à la main, un compilateur l'écrit des milliers de fois par programme. Ce que le compilateur écrit met une fonction de haut niveau en regard de l'assembleur qu'elle devient, et y retrouve le prologue, le cadre et l'épilogue.