Pile en mémoire
L'instruction JMP permet de transférer l'exécution du programme à une adresse contenue dans un des 8 registres R0,…,R7. Ce genre d'instruction est nécessaire à tout programme qui gère dynamiquement les appels de fonction. C'est le cas de tout programme en C qui manipule des pointeurs sur des fonctions. C'est aussi le cas des langages objets comme C++ dont les objets contiennent une table des méthodes sous forme de pointeurs de fonctions. Dans le cas du LC-3, cette instruction permet de compenser la faiblesse de l'instruction BR qui peut uniquement sauter à une adresse éloignée d'au plus 256 mots (l'offset est codé sur 9 bits en complément à 2). L'instruction JMP est aussi indispensable pour réaliser les retours de sous-routine comme nous allons le voir.
La réalisation d'une boucle se fait par exemple de la manière suivante.
LD R0,nbiter ; Nombre d'itérations de la boucle
; Boucle
loop: ... ; Début de la boucle
...
ADD R0,R0,-1 ; Décrémentation du compteur
BRp loop ; Retour au début de la boucle
; Suite du programme
...
Lorsqu'un programme appelle une sous-routine, il faut d'une certaine manière mémoriser l'adresse à laquelle doit revenir s'exécuter le programme à la fin de la routine. Dans le micro-processeur LC-3, l'adresse de retour, c'est-à-dire l'adresse de l'instruction suivante est mise dans le registre R7 lors d'un appel de sous-routine. Ce registre a donc un rôle particulier.
Il existe deux instructions JSR et JSRR permettant d'appeler une sous-routine. L'instruction JSR est semblable à l'instruction BR de branchement inconditionnel. Il n'y a pas de variante conditionnelle de l'instruction JSR. Les trois bits utilisés pour la condition dans le codage l'instruction BR sont récupérés pour avoir un offset de 11 bits au lieu de 9 bits pour BR. Un bit est aussi nécessaire pour distinguer JSR et JSRR qui utilisent le même op-code (cf. codage des instructions du LC-3). L'adresse de la sous-routine est stockée dans le code l'instruction sous forme d'un offset de 11 bits. L'instruction JSRR est semblable à l'instruction JMP. Elle permet d'appeler une sous-routine dont l'adresse est contenue dans un des 8 registres. Cette deux instructions ont en commun de transférer la valeur du compteur de programme PC incrémenté (adresse de l'instruction suivante) dans le registre R7 avant de charger PC avec l'adresse de la sous-routine.
Lors d'un appel à une sous-routine, l'adresse de retour est mise dans le registre R7. La sous-routine se termine donc par un saut à cette adresse avec l'instruction JMP R7. Cette instruction peut aussi être désignée par le mnémonique RET.
; Appel de la sous-routine sub
...
JSR sub ; Adresse de l'instruction suivante dans R7
...
; Sous-routine sub
sub: ...
...
RET ; JMP R7
On reprend le fragment de programme pour calculer la longueur d'une chaîne sous la forme d'une sous-routine appelée par un programme principal.
.ORIG x3000
; Programme principal
...
; Premier appel
LEA R0,chaine ; Chargement dans R0 de l'adresse de la chaîne
JSR strlen ; Appel de la sous-routine
...
; Autre appel
JSR strlen
...
; Chaine constante
chaine: .STRINGZ "Hello World"
.END
; Sous-routine pour calculer la longueur d'une chaîne terminée par '\0'
; @param R0 adresse de la chaîne
; @return R0 longueur de la chaîne
; L'adresse de retour est dans R7
strlen: AND R1,R1,0 ; Mise à 0 du compteur : c = 0
loop: LDR R2,R0,0 ; Chargement dans R2 du caractère pointé par R0
BRz fini ; Test de fin de chaîne
ADD R0,R0,1 ; Incrémentation du pointeur : p++
ADD R1,R1,1 ; Incrémentation du compteur : c++
BR loop
fini: ADD R0,R1,0 ; R0 = R1
RET ; Retour par JMP R7
La routine strlen utilise le registre R1 pour effectuer ses calculs. Si le programme principal utilise également ce registre R1, le contenu de ce registre doit être sauvegardé pendant l'appel à strlen. Cette question est abordée ci-dessous.
Les registres du micro-processeur LC-3 sont en nombre limité. Lorsque qu'une routine a besoin de registres pour faire des calculs intermédiaires, il est préférable de sauvegarder le contenu de ces registres. Cela évite de détruire le contenu du registre qui est peut-être utilisé par le programme appelant la routine. En particulier si une routine doit appeler une autre sous-routine, elle doit préserver le registre R7 qui contient l'adresse de retour.
Une routine sub qui appelle une autre routine subsub peut utiliser un registre, par exemple R5 pour sauvegarder le registre R7 qui contient l'adresse de retour de sub. Cette méthode donne un code efficace car il n'utilise que les registres. Par contre, on arrive rapidement à cours de registres. Il faut donc utiliser d'autres techniques.
sub: ADD R5,R7,0 ; Sauvegarde de R7 dans R5
...
JSR subsub
...
ADD R7,R5,0 ; Restauration de R7
RET
subsub: ...
RET
Une autre méthode consiste à réserver des emplacements mémoire pour la sauvegarde des registres pendant l'exécution d'une routine. Les contenus des registres sont rangés dans ces emplacements au début de la routine et ils sont restaurés à la fin de celle-ci. Cette méthode a deux inconvénients majeurs. D'une part, elle nécessite de réserver de la mémoire pour chaque routine. Cela peut gaspiller beaucoup de mémoire si le programme est conséquent. De plus, l'espace réservé pour les routines non appelées est perdu. D'autre part, cette méthode conduit à du code qui n'est pas réentrant.
; Sous-routine sub sauvegardant R0 et R1
sub: ST R0,saveR0 ; Sauvegarde de R0
ST R1,saveR1 ; Sauvegarde de R1
... ; Corps de la procédure
LD R1,saveR1 ; Restauration de R1
LD R0,saveR0 ; Restauration de R0
RET
saveR0: .BLKW 1 ; Emplacement de sauvegarde de R0
saveR1: .BLKW 1 ; Emplacement de sauvegarde de R1
; Appel de la sous-routine
; Le registre R7 est détruit
JSR sub
La meilleure méthode est d'utiliser une pile. Cela s'apparente à la méthode des emplacements réservés mais dans le cas d'une pile, c'est un espace global qui est partagé par toutes les sous-routines. Par contre, cette méthode nécessite de réserver un des registres à la gestion de la pile. Dans le cas du micro-processeur LC-3, c'est le registre R6 qui est généralement utilisé.
Pile en mémoire
Le registre R6 est utilisé comme pointeur de pile. Pendant toute l'exécution du programme, le registre R6 donne l'adresse de la dernière valeur mise sur la pile. La pile croît vers les adresses décroissantes. N'importe quel autre registre (hormis R7) aurait pu être utilisé mais il est préférable d'utiliser R6 en cas d'interruption.
Un empilement est réalisé en déplaçant vers les adresses basses le pointeur de pile pour le faire pointer sur le premier emplacement libre. Ensuite le contenu du registre y est rangé en employant un rangement avec adressage relatif avec offset de 0.
ADD R6,R6,-1 ; Déplacement du haut de pile
STR Ri,R6,0 ; Rangement de la valeur
Le dépilement est bien sûr l'opération inverse. Le contenu du registre est récupéré avec un chargement avec adressage relatif. Ensuite le pointeur de pile est incrémenté pour le faire pointer sur le haut de la pile.
LDR Ri,R6,0 ; Récupération de la valeur
ADD R6,R6,1 ; Restauration du haut de pile
Aucune vérification n'est faite pour savoir si la pile déborde. Il appartient au programmeur de vérifier que dans chaque routine, il effectue autant de dépilements que d'empilements.
Lors de l'empilement ou du dépilement de plusieurs registres, l'offset de l'adressage relatif permet de faire en une seule instruction les différentes incrémentations ou décrémentations du registre de pile. L'empilement des registres R0, R1 et R2 (dans cet ordre peut par exemple être réalisé de la manière suivante.
ADD R6,R6,-3 ; Déplacement du haut de pile
STR R0,R6,2 ; Empilement de R0
STR R1,R6,1 ; Empilement de R1
STR R2,R6,0 ; Empilement de R2
Le fait de placer la décrémentation du registre de pile R6 avant de placer les contenus des registres R0, R1 et R2 sur la pile n'est pas anodin. Il semble à première vue que l'instruction ADD R6,R6,-3 pourrait être placée après les trois instructions STR en changeant bien sûr les offsets utilisés par ces trois dernières par les valeurs -1, -2 et -3. Ceci est en fait faux. Si une interruption survient entre le placement des contenus des registres sur la pile et la décrémentation de R6, le contenu de la pile peut être altéré par de valeurs que l'interruption mettrait sur la pile. Le fait de décrémenter d'abord R6 peut être considéré comme une façon de réserver sur la pile les emplacements pour les contenus de R0, R1 et R2. Dans le cas du LC-3, les programmes utilisateur sont en quelque sorte protégés de ce type de problèmes car les interruptions utilisent la pile système qui est distincte de la pile utilisateur. Par contre, le code exécuté en mode privilégié doit respecter cette contrainte.
Le dépilement des registres R2, R1 et R0 se fait la même manière. L'ordre des trois dépilements effectués par les instructions LDR n'est pas imposé. Le résultat serait le même en les mettant dans un ordre différent. Par contre, on a respecté l'ordre inverse des empilements pour bien montrer qu'il s'agit de l'utilisation d'une pile.
LDR R0,R6,2 ; Dépilement de R0
LDR R1,R6,1 ; Dépilement de R1
LDR R2,R6,0 ; Dépilement de R2
ADD R6,R6,3 ; Restauration du haut de pile
La raison pour laquelle l'incrémentation de R6 est placée après le chargement des registres avec les valeurs sur la pile est identique à la raison pour laquelle la décrémentation de R6 est placée avant le placement des contenus des registres sur la pile.
La pile permet en particulier d'échanger les contenus de deux registres sans utiliser de registre supplémentaire autre que le pointeur de pile R6. Le morceau de code suivant échange par exemple les contenus des registres R1 et R2.
ADD R6,R6,-2 ; Déplacement du haut de pile
STR R1,R6,1 ; Empilement de R1
STR R2,R6,0 ; Empilement de R2
LDR R2,R6,1 ; Dépilement du contenu de R1 dans R2
LDR R1,R6,0 ; Dépilement du contenu de R2 dans R1
ADD R6,R6,2 ; Restauration du haut de pile
Si un micro-processeur possède une opération de ou exclusif bit à bit appelée XOR, l'échange des contenus de deux registres peut aussi se faire de la manière compliquée suivante.
; R1 : x R2 : y
XOR R1,R1,R2 ; R1 : x ^ y R2 : y
XOR R2,R1,R2 ; R1 : x ^ y R2 : x
XOR R1,R1,R2 ; R1 : y R2 : x
Dans le cas d'appels de sous-routine imbriqués, c'est-à-dire d'une sous-routine sub appelant une (autre) sous-routine subsub, il est nécessaire de sauvegarder sur la pile l'adresse de retour de sub contenue dans le registre R7. À l'appel de la seconde sous-routine subsub, le registre R7 reçoit l'adresse de retour de celle-ci et son contenu précédent est écrasé.
sub: ADD R6,R6,-2 ; Sauvegarde sur la pile de
STR R7,R6,1 ; - l'adresse de retour
STR R0,R6,0 ; - registre R0
...
JSR subsub
...
LDR R0,R6,0 ; Restauration de la pile de
LDR R7,R6,1 ; - registre R0
ADD R6,R6,2 ; - l'adresse de retour
RET ; Retour par JMP R7
subsub: ... ; R7 contient l'adresse de retour
; c'est-à-dire l'adresse de l'instruction
; suivant JSR subsub
RET ; Retour par JMP R7
L'initialisation de la pile se fait en mettant dans le registre R6 l'adresse du haut de la pile. Il s'agit en fait de l'adresse du premier emplacement mémoire après l'espace réservé à la pile. Comme tout utilisation de la pile commence par décrémenter le registre R6, cet emplacement n'est normalement jamais utilisé par la pile.
; Initialisation de la pile au début du programme
psp: .FILL stackend
main: LD R6,psp ; Équivalent à LEA R6,stackend
...
; Réservation de l'espace pour la pile
.ORIG 0x6000
.BLKW 0x100 ; Taille de la pile : 256 octets
stackend: ; Adresse de mot mémoire suivant
Pour illustrer l'utilisation de la pile, un programme récursif (source) calculant la solution du problème des tours de Hanoï est donné ci-dessous.
; Tours de Hanoï
.ORIG x3000
; Programme principal
; Le pointeur de pile R6 est initialisé par le simulateur
hanoim: LD R0,nbrdisk ; Nombre de disques
LD R1,startst ; Piquet de depart
LD R2,endst ; Piquet d'arrivée
JSR hanoi
TRAP x25 ; HALT
; Constantes
nbrdisk:.FILL 3 ; Nombre de disques
startst:.FILL 1 ; Piquet de depart
endst: .FILL 2 ; Piquet d'arrivée
; Calcul du piquet intermédiaire avant de lancer la procédure récursive
; @param R0 nombre de disques
; @param R1 piquet de départ
; @param R2 piquet d'arrivée
hanoi:
; Calcul du troisième piquet : R3 = 6 - R1 - R2
ADD R3,R2,R1
NOT R3,R3
ADD R3,R3,7 ; 7 = 6 + 1
; Procédure récursive
; @param R0 nombre de disques
; @param R1 piquet de départ
; @param R2 piquet d'arrivée
; @param R3 piquet intermédiaire
hanoirec:
; Décrémentation du nombre de disques
ADD R0,R0,-1
; Test si le nombre de disques est 0
BRn hanoiend
; Empilement de l'adresse de retour
ADD R6,R6,-1
STR R7,R6,0
JSR swapR2R3
JSR hanoirec
JSR swapR2R3
JSR print
JSR swapR1R3
JSR hanoirec
JSR swapR1R3
; Dépilement de l'adresse de retour
LDR R7,R6,0
ADD R6,R6,1
; Restauration du nombre de piquets
hanoiend:
ADD R0,R0,1
RET
; Échange des contenus de R1 et R3
swapR1R3:
ADD R4,R3,0
ADD R3,R1,0
ADD R1,R4,0
RET
; Échange des contenus de R2 et R3
swapR2R3:
ADD R4,R3,0
ADD R3,R2,0
ADD R2,R4,0
RET
; Affichage de R1 -> R2
print: ; Empilement de R7 et R0
ADD R6,R6,-2
STR R7,R6,1
STR R0,R6,0
; Affichage du caractère '0' + R1
LD R0,char0
ADD R0,R0,R1
TRAP x21 ; Appel système putc
; Affichage de la chaîne " --> "
LEA R0,arrow
TRAP x22 ; Appel système puts
; Affichage du caractère '0' + R2
LD R0,char0
ADD R0,R0,R2
TRAP x21 ; Appel système putc
; Retour à la ligne
LD R0,charnl
TRAP x21 ; Appel système putc
; Dépilement de R0 et R7
LDR R0,R6,0
LDR R7,R6,1
ADD R6,R6,2
RET
; Constantes pour l'affichage
char0: .FILL '0'
charnl: .FILL '\n'
arrow: .STRINGZ " --> "
.END
Beaucoup de micro-processeurs (surtout CISC comme le 80x86) possèdent un registre, généralement appelé SP, dédié à la gestion de la pile. Il y a alors des instructions spécifiques pour manipuler la pile. La pile est alors systématiquement utilisée pour les appels à des sous-routines. Certaines instructions permettent en effet les appels et les retours de sous-routines. D'autres instruction permettent d'empiler ou de dépiler un ou plusieurs registres afin de simplifier la sauvegarde des registres.
Les instructions d'appels de sous-routine empilent alors l'adresse de retour plutôt que de la mettre dans un registre particulier. Comme l'adresse de retour d'une sous-routine se trouve toujours sur la pile, il existe une instruction spécifique, généralement appelée RET pour terminer les sous-routines. Cette instruction dépile l'adresse de retour puis la met dans le compteur de programme PC. Ceci explique pourquoi l'instruction JMP R7 du LC-3 est aussi appelée RET.
Les micro-processeurs ayant un registre dédié à la pile possèdent des instructions, généralement appelées PUSH et POP permettant d'empiler et de dépiler un registre sur la pile. Ces instructions décrémentent et incrémentent automatiquement le registre de pile pour le mettre à jour. Certains micro-processeurs comme le 80x86 ont même des instructions permettant d'empiler et de dépiler tous les registres ou un certain nombre d'entre eux.
L'instruction TRAP permet de faire un appel au système. Les mots mémoire des adresses 0x00 à 0xFF contiennent une table des appels système. Chaque emplacement mémoire contient l'adresse d'un appel système. Il y a donc 256 appels système possibles. L'instruction TRAP contient le numéro d'un appel système, c'est-à-dire l'indice d'une entrée de la table des appels systèmes.
Comme l'instruction JSR, l'instruction TRAP sauvegarde le compteur de programme PC dans le registre R7 puis charge PC avec l'entrée de la table des appels système dont le numéro est indiqué par l'instruction. Le retour d'un appel système se fait par l'instruction RET.
La table des appels système procure une indirection qui a l'intérêt de rendre les programmes utilisateurs indépendant du système. Dans la mesure où l'organisation (c'est-à-dire la correspondance entre les numéros de la table et les appels système) de la table reste identique, il n'est pas nécessaire de changer (recompiler) les programmes utilisateurs.
Sur les micro-processeurs usuels, l'instruction TRAP fait passer le micro-processeur en mode privilégié (aussi appelé mode système). C'est d'ailleurs souvent la seule instruction permettant de passer en mode privilégié. Ceci garantit que seul le code du système d'exploitation soit exécuté en mode privilégié. Par contre, il faut une instruction capable de sortir du mode privilégié avant d'effectuer le retour au programme principal. Le processeur LC-3 ne possède pas de telle instruction.
Les interruptions sont un mécanisme permettant à un circuit extérieur au micro-processeur d'interrompre le programme en cours d'exécution afin de faire exécuter une routine spécifique. Les interruptions sont en particulier utilisées pour la gestion des entrées/sorties et pour la gestion des processus.
Le micro-processeur possède une ou plusieurs broches permettant de recevoir des signaux provenant des circuits extérieurs susceptibles de provoquer des interruptions. Avant d'exécuter chaque instruction, le micro-processeur vérifie s'il y a un signal (de valeur 1) sur une de ces broches. Si aucun signal n'est présent, il continue le programme et il exécute l'instruction suivante. Si au contraire un signal est présent, il interrompt le programme en cours et il commence à exécuter une sous-routine spécifique appelée sous-routine d'interruption. Lorsque cette sous-routine se termine, le micro-processeur reprend l'exécution du programme en cours à l'instruction où il en était.
L'exécution d'une sous-routine d'interruption s'apparente à l'exécution d'une sous-routine du programme. Par contre elle n'est initiée par aucune instruction du programme. Elle est initiée par le signal d'interruption et elle peut intervenir à n'importe quel moment de l'exécution du programme interrompu. Pour cette raison, cette sous-routine d'interruption ne doit modifier aucun des registres R0,…,R6 et R7 du micro-processeur. De la même façon, elle ne doit pas modifier aucun des indicateurs n, z et p car l'interruption peut intervenir entre une instruction qui positionne ces indicateurs (comme LD et ADD) et une instruction de branchement conditionnel (comme BRz) qui les utilise.
Afin de pouvoir revenir à l'instruction à exécuter, le micro-processeur doit sauvegarder le compteur de programme. Comme aucun registre ne peut être modifié, le compteur de programme ne peut être transféré dans le registre R7 comme les instructions JSR, JSRR et TRAP le font. Le compteur de programme est empilé sur la pile ainsi que le registre PSR qui contient les indicateurs n, z et p. Ensuite le compteur de programme est chargé avec l'adresse de la routine d'interruption. La routine d'interruption se charge elle-même d'empiler les registres dont elle a besoin afin de les restaurer lorsqu'elle se termine. La routine d'interruption se termine par une instruction spécifique RTI (pour ReTurn Interrupt). Il faut d'abord dépiler le registre PSR puis sauter à l'instruction dont l'adresse est sur la pile. Comme le registre R7 doit être préservé, l'instruction RET ne peut être utilisée. L'instruction RTI se charge de dépiler PSR et de dépiler l'adresse de retour pour la charger dans le registre PC.
Dans les micro-processeurs très simples, l'adresse de la routine d'interruption est fixe. S'il y a plusieurs circuits extérieurs susceptibles de provoquer une interruption, le premier travail de la routine d'interruption est de déterminer quel est le circuit qui a effectivement provoqué l'interruption. Ceci est fait en interrogeant les registres d'état (Status Register) de chacun de ces circuits.
S'il y a beaucoup de circuits pouvant provoquer une interruption, il peut être long de déterminer lequel a provoqué l'interruption. Comme le temps pour gérer chaque interruption est limité, les micro-processeurs possèdent plusieurs routines d'interruption. Chacune d'entre elles gère un des circuits extérieurs. Comme pour les appels systèmes, il existe une table des interruptions qui contient les adresses des différentes routines d'interruption. Pour le micro-processeur LC-3, celle-ci se trouve aux adresses de 0x100 à 0x1FF. Lorsqu'un circuit engendre une interruption, il transmet au micro-processeur via le bus de données un vecteur d'interruption. Ce vecteur est en fait l'indice d'une entrée de la table des interruptions. Pour le micro-processeur LC-3, il s'agit d'une valeur 8 bits auquel le micro-processeur ajoute 0x100 pour trouver l'entrée dans la table. Chaque circuit externe reçoit le vecteur d'interruption qui lui est attribué lors de son initialisation par le micro-processeur.
Tables des appels systèmes et interruptions
Dans le micro-processeur LC-3, chaque programme est exécuté avec une certaine priorité allant de 0 à 7. Celle-ci est stockée dans 3 bits du registre PSR. Lorsqu'une interruption est demandée par un circuit extérieur, celle-ci a aussi une priorité. Elle est alors effectivement effectuée si sa priorité est supérieure à la priorité du programme en cours d'exécution. Sinon, elle est ignorée.
Lorsqu'une interruption est acceptée, la routine d'interruption est exécutée avec la priorité de l'interruption. Cette priorité est mise dans le registre PSR après la sauvegarde de celui-ci sur la pile. À la fin de la routine, l'instruction RTI restaure le registre PSR en le dépilant. Le programme interrompu retrouve ainsi sa priorité.
Il est possible qu'une demande d'interruption intervienne pendant l'exécution d'une autre routine d'interruption. Cette interruption est prise en compte si elle a une priorité supérieure à celle en cours. Ce mécanisme permet de gérer les urgences différentes des interruptions. Une interruption liée à un défaut de cache est nettement plus urgente qu'une autre liée à l'arrivée d'un caractère d'un clavier.
Imbrications des interruptions
Certains micro-processeurs comme le 8086 ne disposent que de deux interruptions. Chacune de ses deux interruptions correspond à une broche du circuit du micro-processeur. Une première interruption appelée NMI (Non Maskable Interrupt) est une interruption de priorité maximale puisqu'elle ne peut pas être ignorée par le micro-processeur. Celle-ci est généralement utilisée pour les problèmes graves comme un défaut de mémoire. Une seconde interruption appelée INTR est utilisée par tous les autres circuits extérieurs. Afin de gérer des priorités et une file d'attente des interruptions, un circuit spécialisé appelé PIC (Programmable Interrupt Controler) est adjoint au micro-processeur. Ce circuit reçoit les demandes d'interruption des circuits et les transmet au micro-processeur. Le micro-processeur dispose d'une sortie INTA (Interrupt Acknowledge) pour indiquer au PIC qu'une interruption est traitée et qu'il peut en envoyer une autre.
Contrôleur d'interruptions
Pour plusieurs raisons, il est préférable que la pile utilisée par le système soit distincte de la pile de chacun des programmes utilisateurs. D'abord, si un programme gère mal sa pile et que celle-ci déborde, cela n'empêche pas le système de fonctionner correctement. D'autre part, si la pile est partagée, un programme peut en inspectant sa pile trouver des informations de sécurité qu'il ne devrait pas avoir.
Pour ces raisons, le micro-processeur LC-3 permet d'utiliser deux piles distinctes. Ceci est mis en œuvre de la manière suivante. Le micro-processeur dispose de deux registres USP (User Stack Pointer) et SSP (System Stack Pointer) qui sauvegardent le registre R6 utilisé comme pointeur de pile. Lorsque le micro-processeur LC-3 passe en mode privilégié (lors d'une interruption), le registre R6 est sauvegardé dans USP et R6 est chargé avec le contenu de SSP. Lorsqu'il sort du mode privilégié, R6 est sauvegardé dans SSP et R6 est chargé avec le contenu de USP. Ce mécanisme impose bien sûr que le pointeur de pile soit le registre R6.