Micro-processeur LC-3

Le micro-processeur LC-3 est à vocation pédagogique. Il n'existe pas de réalisation concrète de ce processeur mais il existe des simulateurs permettant d'exécuter des programmes. L'intérêt de ce micro-processeur est qu'il constitue un bon compromis de complexité. Il est suffisamment simple pour qu'il puisse être appréhendé dans son ensemble et que son schéma en portes logiques soit accessible. Il comprend cependant les principaux mécanismes des micro-processeurs (appels système, interruptions) et son jeu d'instructions est assez riche pour écrire des programmes intéressants.

Registres

Le micro-processeur LC-3 dispose de 8 registres généraux 16 bits appelés R0,…,R7. Il possède aussi quelques registres spécifiques dont l'utilisation est abordée plus tard. Le registre PSR (Program Status Register) regroupe plusieurs indicateurs binaires dont l'indicateur de mode (mode utilisateur ou mode privilégié), les indicateurs n, z et p qui sont testés par les branchements conditionnels ainsi que le niveau de priorité des interruptions. Les registres USP (User Stack Pointer) et SSP (System Stack Pointer) permettent de sauvegarder le registre R6 suivant que le programme est en mode privilégié ou non. Comme tous les micro-processeurs, le LC-3 dispose d'un compteur de programme PC et d'un registre d'instruction IR qui sont tous les deux des registres 16 bits.

Schéma des registres du LC-3
Registres du LC-3

Registre PSR

Le registre PSR regroupe plusieurs informations différentes. Le bit de numéro 15 indique si le processeur est en mode utilisateur (0) ou privilégié (1). Les trois bits de numéros 10 à 8 donnent la priorité d'exécution. Les trois bits de numéros 2 à 0 contiennent respectivement les indicateurs n, z et p.

Schéma du registre PSR
Registre PSR

Indicateurs N, Z et P

Les indicateurs sont des registres 1 bit. Les trois indicateurs n, z et p font, en fait, partie du registre spécial PSR. Ils sont positionnés dès qu'une nouvelle valeur est mise dans un des registres généraux R0,…,R7. Ceci a lieu lors de l'exécution d'une instruction logique (NOT et AND), arithmétique (ADD) ou d'une instruction de chargement (LD, LDI, LDR et LEA). Ils indiquent respectivement si cette nouvelle valeur est négative (n), nulle (z) et positive (p). Ces indicateurs sont utilisés par l'instruction de branchement conditionnel BR pour savoir si le branchement doit être pris ou non.

Mémoire

La mémoire du LC-3 est organisée par mots de 16 bits. L'adressage du LC-3 est également de 16 bits. La mémoire du LC-3 est donc formée de 216 mots de 16 bits, c'est-à-dire 128 KiB avec des adresses de 0000 à FFFF en hexadécimal. Cette organisation de la mémoire est inhabituelle mais elle simplifie le câblage. La mémoire de la plupart des micro-processeurs est organisée par octets (mots de 8 bits). Par contre, ces micro-processeurs ont la possibilité de charger directement 2, 4 ou 8 octets. Pour certains, ce bloc doit être aligné sur une adresse multiple de 2, 4 ou 8 alors que ce n'est pas nécessaire pour d'autres.

Schéma de la mémoire du LC-3
Mémoire du LC-3

Instructions

Les instructions du LC-3 se répartissent en trois familles : les instructions arithmétiques et logiques, les instructions de chargement et rangement et les instructions de branchement (appelées aussi instructions de saut ou encore instructions de contrôle).

Les instructions arithmétiques et logiques du LC-3 sont au nombre de trois. Le LC-3 possède une instruction ADD pour l'addition, une instruction AND pour le et logique bit à bit et une instruction NOT pour la négation bit à bit. Le résultat de ces trois opérations est toujours placé dans un registre. Les deux opérandes peuvent être soit les contenus de deux registres soit le contenu d'un registre et une constante pour ADD et AND.

Les instructions de chargement et rangement comprennent des instructions (avec des noms commencent par LD) permettant de charger un registre avec une valeur et des instructions (avec des noms commencent par ST) permettant de ranger en mémoire le contenu d'un registre. Ces instructions se différencient par leurs modes d'adressage qui peut être immédiat, direct, indirect ou relatif. Les instructions de chargement sont LD, LDI, LDR, LEA et les instructions de rangement sont ST, STI et STR.

Les instructions de branchement comprennent les deux instructions de saut BR et JMP, les deux instructions d'appel de sous-routine JSR et JSRR, une instruction TRAP d'appel système, une instruction RET de retour de sous-routine et une instruction RTI de retour d'interruption.

Description des instructions

Instructions arithmétiques et logiques

Ces instructions du LC-3 n'utilisent que les registres aussi bien pour les sources que pour la destination. Ceci est une caractéristique des architectures RISC. Le nombre d'instructions arithmétiques et logiques du LC-3 est réduit au strict nécessaire. Les micro-processeurs réels possèdent aussi des instructions pour les autres opérations arithmétiques (soustraction, multiplication, division) et les autres opérations logiques (ou logique, ou exclusif). Ils possèdent aussi des instructions pour l'addition avec retenue et les décalages.

Instruction NOT

L'instruction NOT permet de faire le non logique bit à bit d'une valeur 16 bits. Sa syntaxe est NOT DR,SRDR et SR sont les registres destination et source.

Instruction ADD

L'instruction ADD permet de faire l'addition de deux valeurs 16 bits. Elle convient pour les additions pour les nombres signés ou non puisque les nombres sont représentés en complément à 2. Elle a deux formes différentes. Dans la première forme, les deux valeurs sont les contenus de deux registres généraux. Dans la seconde forme, la première valeur est le contenu d'un registre et la seconde est une constante (adressage immédiat). Dans les deux formes, le résultat est rangé dans un registre.

La première forme a la syntaxe ADD DR,SR1,SR2DR est le registre destination où est rangé le résultat et SR1 et SR2 sont les registres sources d'où proviennent les deux valeurs. La seconde forme a la syntaxe ADD DR,SR1,Imm5DR et SR1 sont encore les registres destination et source et Imm5 est une constante codée sur 5 bits (-16 ≤ Imm5 ≤ 15). Avant d'effecteur l'opération, la constante Imm5 est étendue de façon signée sur 16 bits en recopiant le bit 4 sur les bits 5 à 15.

Instruction AND

L'instruction AND permet de faire le et logique bit à bit de deux valeurs 16 bits. Elle a deux formes similaires à celles de l'instruction ADD de syntaxes AND DR,SR1,SR2 et AND DR,SR1,Imm5.

Instructions de chargement et rangement

Les instructions de chargement permettent de charger un des registres généraux avec un mot en mémoire alors que les instructions de rangement permettent de ranger en mémoire le contenu d'un de ces registres. Ce sont les seules instructions faisant des accès à la mémoire. Ces différentes instructions se différencient par leur mode d'adressage. Un mode d'adressage spécifie la façon dont l'adresse mémoire est calculée. Le micro-processeur LC-3 possède les principaux modes d'adressage qui sont les modes d'adressage immédiat, direct, relatif et indirect. La terminologie pour les modes d'adressage n'est pas fixe car chaque constructeur a introduit ses propres termes. Le même mode peut avoir des noms différents chez deux constructeurs et le même nom utilisé par deux constructeurs peut recouvrir des modes différents.

Il faut faire attention au fait que presque tous les modes d'adressage du LC-3 sont relatifs au compteur de programme. Cette particularité est là pour compenser la petite taille des offsets qui permettent un adressage à un espace réduit.

Exceptée l'instruction LEA, les instructions de chargement et rangement vont par paire. Pour chaque mode d'adressage, il y a une instruction de chargement dont le mnémonique commence par LD pour LoaD et une instruction de rangement dont le mnémonique commence par ST pour STore.

Toutes les instructions de chargement et rangement contiennent un offset. Cet offset n'est en général pas donné explicitement par le programmeur. Celui-ci utilise des étiquettes et l'assembleur se charge de calculer les offsets.

Instruction LEA

L'instruction LEA pour Load Effective Address charge dans un des registres généraux la somme du compteur de programme et d'un offset codé dans l'instruction. Ce mode adressage est généralement appelé adressage absolu ou immédiat car la valeur chargée dans le registre est directement contenue dans l'instruction. Aucun accès supplémentaire à la mémoire n'est nécessaire. Cette instruction est par exemple utilisée pour charger dans un registre l'adresse d'un tableau.

Schéma de l'adressage immédiat
Adressage immédiat

Instructions LD et ST

Les instructions LD et SD sont les instructions générales de chargement et rangement. L'instruction LD charge dans un des registres généraux le mot mémoire à l'adresse égale à la somme du compteur de programme et d'un offset codé dans l'instruction. L'instruction ST range le contenu du registre à cette même adresse. Ce mode adressage est généralement appelé adressage direct. Il nécessite un seul accès à la mémoire.

Schéma de l'adressage direct
Adressage direct

Instructions LDR et STR

L'instruction LDR charge dans un des registres généraux la mot mémoire à l'adresse égale à la somme du registre de base et d'un offset codé dans l'instruction. L'instruction STR range le contenu du registre à cette même adresse. Ce mode adressage est généralement appelé adressage relatif ou basé. Il nécessite un seul accès à la mémoire. La première utilité de ces instructions est de manipuler les objets sur la pile comme par exemple les variables locales des fonctions. Elles servent aussi à accéder aux champs des structures de données. Le registre de base pointe sur le début de la structure et l'offset du champ dans la structure est codé dans l'instruction.

Schéma de l'adressage relatif
Adressage relatif

Instructions LDI et STI

Les instructions LDI et STI sont les instructions les plus complexes de chargement et rangement. Elle mettent en œuvre une double indirection. Elles calculent, comme les instructions LD et SD, la somme du compteur de programme et de l'offset. Elle chargent la valeur contenue à cette adresse puis utilisent cette valeur à nouveau comme adresse pour charger ou ranger le registre. Ce mode adressage est généralement appelé adressage indirect. Il nécessite deux accès à la mémoire.

Schéma de l'adressage indirect
Adressage indirect

Instructions de branchements

Instruction BR

L'instruction générale de branchement est l'instruction BR. Elle modifie le déroulement normal des instructions en changeant la valeur contenue par le registre PC. Cette nouvelle valeur est obtenue en ajoutant à la valeur de PC un offset codé sur 9 bits dans l'instruction.

Le branchement peut être inconditionnel ou conditionnel. Le cas conditionnel signifie que le branchement est réellement exécuté seulement si une condition est vérifiée. Certains des trois indicateurs n, z, et p sont examinés. Si au moins un des indicateurs examinés vaut 1, le branchement est pris. Sinon, le branchement n'est pas pris et le déroulement du programme continue avec l'instruction suivante.

On rappelle que les trois indicateurs n, z et p sont mis à jour dès qu'une nouvelle valeur est chargée dans un des registres généraux. Ceci peut être réalisé par une instruction arithmétique ou logique ou par une instruction de chargement. Les indicateurs qui doivent être pris en compte par l'instruction BR sont ajoutés au mnémonique BR pour former un nouveau mnémonique. Ainsi l'instruction BRnp exécute le branchement si l'indicateur n ou l'indicateur p vaut 1, c'est-à-dire si l'indicateur z vaut 0. Le branchement est alors pris si la dernière valeur chargée dans un registre est non nulle.

Schéma du branchement conditionnel
Branchement conditionnel

Les programmes sont écrits en langage d'assembleur qui autorise l'utilisation d'étiquettes (labels en anglais) qui évitent au programmeur de spécifier explicitement les offsets des branchements. Le programmeur écrit simplement une instruction BR label et l'assembleur se charge de calculer l'offset, c'est-à-dire la différence entre l'adresse de l'instruction de branchement et l'adresse désignée par l'étiquette label.

Comme l'offset est codé sur 9 bits, l'instruction BR peut uniquement atteindre une adresse située de -255 à 256 mots mémoire. Le décalage d'une unité est dû au fait que le calcul de la nouvelle adresse est effectué après l'incrémentation du compteur de programme qui a lieu lors de la phase de chargement de l'instruction.

Instruction JMP

L'instruction JMP permet de charger le compteur de programme PC avec le contenu d'un des registres généraux. L'intérêt de cette instruction est multiple.

  1. L'instruction JMP compense la faiblesse de l'instruction BR qui peut uniquement effectuer un branchement proche. L'instruction JMP permet de sauter à n'importe quelle adresse. Si l'étiquette label désigne une adresse trop éloignée, le branchement à cette adresse peut être effectuée par le code suivant.
    	LD R7,labelp
    	JMP R7
    labelp:	.FILL label
            ...
    label:  ...
      
  2. L'instruction JMP est indispensable pour tout les langages de programmation qui manipulent explicitement comme C et C++ ou implicitement des pointeurs sur des fonctions. Tous les langages de programmation objet manipulent des pointeurs sur des fonctions dans la mesure où chaque objet a une table de ses méthodes.
  3. L'instruction JMP permet aussi les retours de sous-routines puisque l'instruction RET est en fait une abréviation pour l'instruction JMP R7.

Schéma du branchement par registre
Branchement par registre

Récapitulatif des Instructions

La table suivante donne une description concise de chacune des instructions. Cette description comprend la syntaxe, l'action ainsi que le codage de l'instruction. La colonne nzp indique par une étoile * si les indicateurs n, z et p sont affectés par l'instruction.

Syntaxe Action nzp Codage
Op-code Arguments
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
NOT DR,SR DR ← not SR * 1 0 0 1 DR SR 1 1 1 1 1 1
ADD DR,SR1,SR2 DR ← SR1 + SR2 * 0 0 0 1 DR SR1 0 0 0 SR2
ADD DR,SR1,Imm5 DR ← SR1 + SEXT(Imm5) * 0 0 0 1 DR SR1 1 Imm5
AND DR,SR1,SR2 DR ← SR1 and SR2 * 0 1 0 1 DR SR1 0 0 0 SR2
AND DR,SR1,Imm5 DR ← SR1 and SEXT(Imm5) * 0 1 0 1 DR SR1 1 Imm5
LEA DR,label DR ← PC + SEXT(PCoffset9) * 1 1 1 0 DR PCoffset9
LD DR,label DR ← mem[PC + SEXT(PCoffset9)] * 0 0 1 0 DR PCoffset9
ST SR,label mem[PC + SEXT(PCoffset9)] ← SR 0 0 1 1 SR PCoffset9
LDR DR,BaseR,Offset6 DR ← mem[BaseR + SEXT(Offset6)] * 0 1 1 0 DR BaseR Offset6
STR SR,BaseR,Offset6 mem[BaseR + SEXT(Offset6)] ← SR 0 1 1 1 SR BaseR Offset6
LDI DR,label DR ← mem[mem[PC + SEXT(PCoffset9)]] * 1 0 1 0 DR PCoffset9
STI SR,label mem[mem[PC + SEXT(PCoffset9)]] ← SR 1 0 1 1 SR PCoffset9
BR[n][z][p] label Si (cond) PC ← PC + SEXT(PCoffset9) 0 0 0 0 n z p PCoffset9
NOP No Operation 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
JMP BaseR PC ← BaseR 1 1 0 0 0 0 0 BaseR 0 0 0 0 0 0
RET (≡ JMP R7) PC ← R7 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0
JSR label R7 ← PC; PC ← PC + SEXT(PCoffset11) 0 1 0 0 1 PCoffset11
JSRR BaseR R7 ← PC; PC ← BaseR 0 1 0 0 0 0 0 BaseR 0 0 0 0 0 0
RTI cf. interruptions 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
TRAP Trapvect8 R7 ← PC; PC ← mem[Trapvect8] 1 1 1 1 0 0 0 0 Trapvect8
Réservé 1 1 0 1

Codage des instructions

Chaque instruction est représentée en mémoire par un code. Il est important que le codage des instructions soit réfléchi et régulier pour simplifier les circuits de décodage.

Toutes les instructions du LC-3 sont codées sur un mot de 16 bits. Les quatre premiers bits contiennent l'op-code qui détermine l'instruction. Les 12 bits restant codent les paramètres de l'instruction qui peuvent être des numéros de registres ou des constantes.

À titre d'exemple, les codages des deux instructions ADD et BR sont détaillés ci-dessous.

Codage de ADD

L'instruction ADD peut prendre deux formes. Une première forme est ADD DR,SR1,SR2DR, SR1 et SR2 sont les trois registres destination, source 1 et source 2. Une seconde forme est ADD DR,SR1,Imm5DR et SR1 sont deux registres destination et source et Imm5 est une constante signée sur 5 bits.

Le codage de l'instruction ADD est le suivant. Les quatre premiers bits de numéros 15 à 12 contiennent l'op-code 0001 de l'instruction ADD. Les trois bits suivants de numéros 11 à 9 contiennent le numéro du registre destination DR. Les trois bits suivants de numéros 8 à 6 contiennent le numéro du registre source SR1. Les six derniers bits contiennent le codage du troisième paramètre SR2 ou Imm5. Le premier de ces six bits de numéro 5 permet de distinguer entre les deux formes de l'instruction. Il vaut 0 pour la première forme et 1 pour la seconde forme. Dans la première forme, les bits de numéros 2 à 0 contiennent le numéro du registre SR2 et les bits de numéros 4 et 3 sont inutilisés et forcés à 0. Dans la seconde forme, les cinq derniers bits de numéro 4 à 0 contiennent la constante Imm5.

Le tableau ci-dessous donne un exemple de codage pour chacune des formes de l'instruction ADD.

Instruction Codage Code en hexa
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Op-code DR SR1 0 0 0 SR2
ADD R2,R7,R5 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 0x16C5
Op-code DR SR1 1 Imm5
ADD R6,R6,-1 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0x1DBF

Codage de BR

Le codage de l'instruction BR est le suivant. Les quatre premiers bits de numéros 15 à 12 contiennent l'op-code 0000 de l'instruction BR. Les trois bits suivants de numéros 11 à 9 déterminent respectivement si l'indicateur n, z et p est pris en compte dans la condition. Si ces trois bits sont b11, b10 et b9, la condition cond est donnée par la formule suivante.

cond = (b11 ∧ n) ∨ (b10 ∧ z) ∨ (b9 ∧ p)

Les 9 derniers bits de numéros 8 à 0 codent l'offset du branchement.

Si les trois bits b11, b10 et b9 valent 1, la condition est toujours vérifiée puisque n + z + p = 1. Il s'agit alors de l'instruction de branchement inconditionnel BR. Si au contraire les trois bits b11, b10 et b9 valent 0, la condition n'est jamais vérifiée et le branchement n'est jamais pris. Il s'agit alors de l'instruction NOP qui ne fait rien. En prenant un offset égal à 0, le code de l'instruction NOP est 0x0000.

Le tableau ci-dessous donne un exemple de codage pour trois formes typiques de l'instruction BR. Dans les exemples ci-dessous, on a donné des valeurs explicites aux offsets afin d'expliquer leur codage mais cela ne correspond pas à la façon dont l'instruction BR est utilisée dans les programmes.

Instruction Codage Code en hexa
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Op-code n z p PCoffset9
BRnz -137 0 0 0 0 1 0 1 1 0 1 1 1 0 1 1 1 0x0B77
BR 137 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 1 0x0E89
NOP 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0x0000

Répartition des op-code

On peut remarquer les op-code des instructions n'ont pas été affectés de manière aléatoire. On peut même observer une certaine régularité qui facilite le décodage. Les op-code des instructions de chargement et de rangement qui se correspondent (LD et ST, LDR et STR, …) ne différent que d'un seul bit.

MSB LSB
0 0 0 1 1 0 1 1
0 0 BR ADD LD ST
0 1 JSR(R) AND LDR STR
1 0 RTI NOT LDI STI
1 1 JMP LEA TRAP

Schéma interne du LC-3

Le schéma ci-dessous donne une réalisation du processeur LC-3 avec les différents éléments : registres, ALU, unité de contrôle, …. Les détails des entrées/sorties sont donnés dans un schéma ultérieur.

Schéma des chemins de données du LC-3
Chemins de données du LC-3