Une machine complète : la Mic-1 exécutant IJVM

Le chapitre sur le microcode a présenté l’idée : une mémoire de contrôle remplie de micro-instructions pilote le chemin de données, un cycle à la fois. Ce chapitre suit une machine complète, en partant des registres. La machine s’appelle la Mic-1, une microarchitecture pédagogique classique. Le jeu d’instructions qu’elle exécute est IJVM, un petit sous-ensemble entier du bytecode Java utilisé pour l’enseignement. L’interpréteur complet fait 112 micro-instructions.

Il vaut la peine de l’étudier en détail pour une raison : il est assez petit pour tenir dans la tête, et pourtant il contient tous les mécanismes dont un vrai CPU microprogrammé a besoin : lecture des instructions, décodage des opérandes, pile, latence mémoire, branchements et appels de procédure.

Le chemin de données de la Mic-1

La Mic-1 a dix registres de 32 bits (MBR n’en fait que 8), une ALU et un décaleur, reliés par deux bus :

À chaque cycle, un registre alimente le bus B, qui est l’entrée droite de l’ALU. L’entrée gauche est toujours H. Le résultat traverse le décaleur jusqu’au bus C, et peut être écrit dans autant de registres qu’on veut à la fois. Ainsi, MAR = SP = SP − 1 tient en un cycle : SP sur le bus B, l’ALU calcule B − 1, et le résultat arrive à la fois dans MAR et dans SP.

Impossible, en revanche, d’additionner deux registres quelconques en un cycle. L’un des deux doit d’abord être copié dans H. Cette limite apparaît dans presque toutes les instructions ci-dessous.

Les deux ports mémoire ne se comportent pas pareil. MAR compte en mots : MAR = 2 lit les octets 8 à 11. PC compte en octets, car les instructions IJVM forment un flot d’octets de longueurs variables. L’octet lu par le port PC arrive dans MBR, et MBR peut aller sur le bus B de deux façons : avec extension de signe (noté MBR) ou complété par des zéros (MBRU).

La mémoire est lente, même dans cette machine idéalisée. Une lecture lancée à la fin du cycle k livre sa donnée à la fin du cycle k + 1 : la valeur n’est utilisable qu’au cycle k + 2. Le microprogramme doit combler ce trou avec du travail utile, ou perdre un cycle.

Chaque micro-instruction fait 36 bits : une adresse suivante de 9 bits, 3 bits JAM pour les branchements, 8 bits pour l’ALU et le décaleur, 9 bits qui choisissent les registres écrits par le bus C, 3 bits mémoire (lecture, écriture, fetch) et un sélecteur de bus B sur 4 bits. La mémoire de contrôle en contient 512. Le chapitre sur le microcode explique comment l’adresse suivante est formée ; ici, on regarde ce que font réellement les micro-instructions.

IJVM : la machine interprétée

IJVM est une machine à pile. Ses instructions ne nomment pas de registres : les opérandes sont empilés, et les opérations les dépilent puis empilent le résultat. La mémoire est divisée en quatre zones, chacune atteinte par un pointeur dédié :

• le réservoir de constantes, en lecture seule, à l’adresse CPP. Il contient des constantes et les adresses des méthodes ;
• le bloc de variables locales de la méthode courante, à l’adresse LV. Les paramètres viennent en premier, puis les variables locales ;
• la pile d’opérandes, juste au-dessus de ce bloc, dont le sommet est en SP ;
• la zone des méthodes, le bytecode du programme, lu octet par octet via PC.

Un programme ne voit jamais d’adresse absolue de donnée. Il peut seulement dire « variable locale 3 » ou « constante 0 », et le microcode ajoute le décalage à LV ou à CPP.

Le jeu d’instructions compte 20 instructions. Les voici, avec les mêmes numéros d’opcode que la vraie JVM :

Les décalages de branchement sont des nombres signés de 16 bits, gros-boutistes (big-endian), relatifs à l’adresse de l’opcode du branchement lui-même.

De Java à IJVM

Voici une méthode Java qui multiplie par additions successives :

int mul(int a, int b) {
    int r = 0;
    while (b != 0) {
        r = r + a;
        b = b - 1;
    }
    return r;
}

Voici ce que produit le javac d’OpenJDK 26, affiché par javap -c :

 0: iconst_0
 1: istore_3
 2: iload_2
 3: ifeq          17
 6: iload_3
 7: iload_1
 8: iadd
 9: istore_3
10: iload_2
11: iconst_1
12: isub
13: istore_2
14: goto          2
17: iload_3
18: ireturn

Les octets bruts du fichier .class contiennent 99 00 0e (ifeq +14), 60 (iadd), 64 (isub), a7 ff f4 (goto −12) et ac (ireturn) : exactement les opcodes d’IJVM. La différence : la vraie JVM a des formes courtes d’un octet pour les cas fréquents, comme iconst_0 au lieu de BIPUSH 0, ou istore_3 au lieu de ISTORE 3. IJVM les laisse de côté et utilise toujours la forme générale ; la version IJVM est donc un peu plus longue.

La variable locale 0 est this, l’objet sur lequel la méthode est appelée ; a, b et r sont les variables 1, 2 et 3. javap -v indique locals=4, args_size=3.

La boucle principale : une seule micro-instruction

Chaque instruction IJVM commence par la même micro-instruction, Main1 :

Main1   PC = PC + 1; fetch; goto (MBR)

Elle fait trois choses en un cycle. Elle fait avancer PC au-delà de l’opcode. Elle lance la lecture de l’octet suivant, qui sera soit le premier opérande de l’instruction, soit l’opcode suivant. Et elle saute à l’adresse de la mémoire de contrôle égale à l’opcode présent dans MBR : le branchement multiple décrit au chapitre sur le microcode. La routine de IADD commence à l’adresse 0x60 de la mémoire de contrôle, celle de ILOAD à 0x15.

C’est pour cela que chaque micro-instruction désigne explicitement celle qui la suit. Les adresses 0x00 à 0xFF sont réservées à la première micro-instruction de chaque opcode ; le reste de chaque routine doit donc se loger dans les trous, éparpillé dans la mémoire de contrôle.

L’invariant qui fait tout tenir : quand le contrôle revient à Main1, l’opcode suivant doit déjà être dans MBR. Chaque routine est écrite pour le garantir.

IADD : trois micro-instructions

iadd1   MAR = SP = SP − 1; rd       read the word below the top
iadd2   H = TOS                     top of stack into H, while the read completes
iadd3   MDR = TOS = MDR + H; wr; goto Main1

TOS contient déjà le sommet de la pile, donc une seule lecture mémoire suffit. iadd1 fait pointer SP et MAR sur le deuxième mot et lance la lecture. La donnée ne sera utilisable que deux cycles plus tard, alors iadd2 profite du trou pour copier TOS dans H. Dans iadd3, le mot est arrivé dans MDR. La somme va dans MDR (pour être réécrite en mémoire) et dans TOS (pour garder la copie à jour), et l’écriture démarre.

Avec Main1, IADD coûte 4 micro-instructions. ISUB, IAND et IOR sont la même routine avec une autre opération d’ALU.

ILOAD : attendre la mémoire deux fois

iload1  H = LV                      LV into H, to be added to the index
iload2  MAR = MBRU + H; rd          address of the local variable; read it
iload3  MAR = SP = SP + 1           new top of stack; wait for the read
iload4  PC = PC + 1; fetch; wr      fetch the next opcode; write the value on the stack
iload5  TOS = MDR; goto Main1

L’octet d’index a été lu par Main1, et il est complété par des zéros (MBRU) : un numéro de variable n’est jamais négatif. LV doit passer par H, car MBR et LV sont tous deux du côté du bus B. Ensuite la variable est lue, empilée, et copiée dans TOS. 6 micro-instructions, Main1 compris.

GOTO : assembler un décalage de 16 bits

goto1   OPC = PC − 1                save the address of the opcode
goto2   PC = PC + 1; fetch          fetch the second offset byte
goto3   H = MBR << 8                high byte, sign-extended, shifted into place
goto4   H = MBRU OR H               low byte, zero-extended, OR-ed in
goto5   PC = OPC + H; fetch         jump, and fetch the opcode there
goto6   goto Main1                  wait for that fetch to arrive

Le décalage est relatif à l’opcode, mais PC l’a déjà dépassé : goto1 récupère donc l’adresse de l’opcode dans OPC. Les deux octets du décalage arrivent un par un par le port 8 bits. L’octet de poids fort subit l’extension de signe, car un décalage peut être négatif ; celui de poids faible, non. goto6 ne fait rien : il attend seulement que le nouvel opcode arrive dans MBR, comme l’exige Main1. 7 micro-instructions en tout.

Les branchements conditionnels réutilisent ce code. IFEQ dépile le sommet, lit le nouveau sommet dans TOS, et fait passer la valeur dépilée par l’ALU pour positionner l’indicateur Z. Le bit JAMZ de cette micro-instruction rend l’adresse suivante dépendante de Z. Si le branchement est pris, on saute au milieu de la routine de GOTO ; sinon, trois courtes micro-instructions sautent par-dessus le décalage. IFEQ coûte 11 micro-instructions quand il est pris, et 8 sinon.

INVOKEVIRTUAL : construire un bloc d’activation

L’instruction d’appel est de loin la plus longue : 22 micro-instructions après Main1. Son opérande est un index dans le réservoir de constantes, où est rangée l’adresse de la méthode. La méthode elle-même commence par deux nombres de 16 bits, son nombre de paramètres (référence à l’objet comprise) et son nombre de variables locales, suivis de son premier opcode.

Le microcode lit tout cela octet par octet, puis construit le nouveau bloc. Voici la pile dans la démo ci-dessous, juste après que INVOKEVIRTUAL a appelé mul(6, 7) :

word 13   caller's LV = 8           ← SP
word 12   caller's PC = 9
word 11   r                         (local 3)
word 10   b = 7                     (local 2)
word  9   a = 6                     (local 1)
word  8   link pointer = 12         ← LV   (was the object reference)

L’appelant avait empilé la référence à l’objet et les deux arguments. Le microcode fait pointer LV sur la référence à l’objet et l’écrase avec un pointeur de liaison (link pointer) : l’adresse, au-dessus des variables locales, où il sauvegarde le PC et le LV de l’appelant. La pile d’opérandes de la nouvelle méthode commence juste au-dessus.

IRETURN défait tout cela en 8 micro-instructions. Il suit le pointeur de liaison pour restaurer PC et LV, et écrit la valeur de retour là où se trouvait la référence à l’objet : l’appelant trouve ainsi le résultat au sommet de sa pile.

Faire tourner la Mic-1

La démo ci-dessous est la Mic-1 écrite en C. Les variables globales sont les registres de la Mic-1, et chaque ligne qui se termine par cycle() est une micro-instruction du microprogramme de la Mic-1, avec son étiquette en commentaire. cycle() modélise le délai mémoire : une lecture lancée pendant un cycle n’atteint MDR ou MBR qu’à la fin du cycle suivant. Le programme IJVM est la méthode mul ci-dessus, assemblée à la main, appelée sous la forme mul(6, 7). (IJVM n’a pas d’instruction pour arrêter la machine ; la démo ajoute donc un opcode HALT, 0xFF, à son programme principal.)

Appuyez sur Continue. Le programme renvoie 42 et affiche le coût de chaque instruction la première fois qu’elle apparaît :

BIPUSH: 4 microinstructions
INVOKEVIRTUAL: 23 microinstructions
ISTORE: 7 microinstructions
ILOAD: 6 microinstructions
IFEQ: 8 microinstructions
IADD: 4 microinstructions
ISUB: 4 microinstructions
GOTO: 7 microinstructions
IFEQ: 11 microinstructions
IRETURN: 9 microinstructions
87 IJVM instructions, 533 microinstructions

Ce sont exactement les longueurs des routines du microprogramme de la Mic-1, Main1 compris. En moyenne, une instruction IJVM a pris un peu plus de 6 cycles. Avancez pas à pas dans la boucle while et regardez MAR, MDR, PC, MBR, SP, LV, TOS et H évoluer dans le panneau Variables.

Le minutage n’est pas décoratif. Supprimez le cycle(); qui suit H = TOS; dans le cas IADD, pour que iadd2 et iadd3 ne forment plus qu’un cycle. Le programme renvoie alors 12 au lieu de 42 : IADD et ISUB lisent MDR avant que le mot de la pile soit arrivé, et additionnent une valeur périmée. Un vrai microprogrammeur doit respecter ces délais dans chaque routine.

Ce code C ne prétend pas être un interpréteur rapide. Le chapitre sur le bytecode exécute le même genre de bytecode JVM avec une simple boucle switch en C, et mesure ce que cela coûte ; ici, le but est de voir les registres et les cycles du matériel.

Aller plus vite : Mic-2, Mic-3, Mic-4

On peut accélérer la Mic-1 par étapes. Il y a trois leviers de base : moins de cycles par instruction (un chemin d’exécution plus court, path length), un cycle plus court, ou le recouvrement des instructions.

Des chemins plus courts. Deux changements peu coûteux d’abord. Main1 peut être fusionnée à la fin de chaque routine, où un cycle est parfois inutilisé de toute façon. Et un troisième bus permet à l’ALU de prendre n’importe quel registre en entrée gauche : H = LV disparaît de ILOAD, qui passe de 6 à 5 cycles.

Mic-2 : une unité de chargement des instructions. Le gros gain consiste à ne plus utiliser l’ALU pour lire le programme. L’IFU (Instruction Fetch Unit) a un incrémenteur dédié, lit à l’avance des mots entiers de 4 octets dans un registre à décalage, et présente l’octet suivant dans MBR1 et les deux octets suivants, déjà réunis en une valeur de 16 bits, dans MBR2. Elle fait avancer PC elle-même au fur et à mesure que les octets sont consommés. Main1 disparaît complètement : chaque routine se termine par goto (MBR1), qui saute directement à l’instruction suivante. En comptant les micro-instructions des microprogrammes de la Mic-1 et de la Mic-2 :

La même exécution prendrait 326 cycles au lieu de 533.

Mic-3 : le pipeline. Le cycle de la Mic-2 enchaîne la commande des bus, l’ALU, puis l’écriture des résultats. La Mic-3 place des verrous (latches) sur les bus A, B et C, ce qui découpe le chemin de données en trois étages plus courts, qui travaillent sur trois micro-instructions différentes à la fois. Une micro-instruction prend désormais trois cycles plus courts, mais une nouvelle peut démarrer à chaque cycle. Quand l’une a besoin d’une valeur que la précédente n’a pas encore produite (une dépendance RAW), elle attend. SWAP prend 11 cycles courts au lieu de 6 longs : environ 11 contre 18 dans la même unité de temps, si un cycle court vaut un tiers d’un cycle long. Le chapitre sur le pipeline détaille les aléas.

Mic-4 : un pipeline à sept étages. La dernière conception cesse de traiter le microprogramme comme un programme. Une unité de décodage découpe le flot d’octets en instructions grâce à une table des longueurs d’instruction, et cherche dans une ROM où commencent les micro-opérations de chacune. Une unité de mise en file copie ces micro-opérations dans une file d’attente. Quatre registres MIR, un par étage, font descendre chaque micro-opération le long du pipeline : opérandes, exécution, écriture du résultat, mémoire. Les sept étages sont : IFU, décodeur, file, opérandes, exécution, écriture et mémoire.

C’est la forme d’un vrai front end x86 : les décodeurs transforment les instructions en µops, qui attendent dans une file avant d’être exécutées. Le chapitre sur les cœurs réels regarde le Core i7 d’Intel et ses versions actuelles.

La vraie JVM aujourd’hui

Les opcodes d’IJVM sont ceux de la JVM, mais aucune JVM courante ne tourne sur du microcode. Quelques processeurs ont bien exécuté du bytecode Java en matériel, comme l’extension Jazelle de certaines puces ARM 32 bits des années 2000, mais les compilateurs à la volée l’ont rendue inutile, et l’ARM 64 bits l’a abandonnée.

HotSpot, la JVM d’OpenJDK, commence par interpréter le bytecode avec un interpréteur par gabarits (template interpreter) : un petit morceau de code machine généré au démarrage pour chaque opcode, et un aiguillage qui ressemble beaucoup à goto (MBR). Quand une méthode devient chaude, elle est compilée en code natif, d’abord rapidement (le compilateur C1, niveau 3), puis avec toutes les optimisations (C2, niveau 4). Exécuter mul 20 millions de fois sur OpenJDK 26 avec -XX:+PrintCompilation le montre dans les 20 premières millisecondes :

17    8       3       Hot::mul (19 bytes)
17    9       4       Hot::mul (19 bytes)

Les 19 octets sont le bytecode ci-dessus. Sur le M2 Ultra sur lequel ce chapitre a été écrit, l’exécution complète a pris environ 1,1 s avec -Xint (interpréteur seul) et 0,05 s avec le JIT, démarrage de la JVM compris. Le chapitre sur les compilateurs explique le fonctionnement des niveaux de JIT.

À retenir

• La Mic-1 est un CPU microprogrammé complet : dix registres, une ALU alimentée par H et le bus B, un port par mots (MAR/MDR) pour les données, un port par octets (PC/MBR) pour le code, et une mémoire de contrôle de 512 × 36 bits.
• IJVM est une machine à pile qui reprend les opcodes de la JVM. Les données ne sont accessibles que via LV (variables locales), SP (pile) et CPP (réservoir de constantes).
• Main1 lit l’octet suivant et aiguille sur l’opcode en un seul cycle. Les routines prennent ensuite de 4 cycles (IADD) à 23 (INVOKEVIRTUAL), environ 6 en moyenne dans notre exécution.
• Le microprogramme masque la latence mémoire en faisant du travail utile pendant qu’une lecture est en cours ; un minutage faux donne un résultat faux.
• La Mic-2 ajoute une unité de chargement des instructions (533 → 326 cycles pour notre exécution), la Mic-3 met le chemin de données en pipeline, et la Mic-4 décode en micro-opérations mises en file, l’organisation des vrais CPU.
• La vraie JVM utilise le même bytecode, mais l’exécute avec un interpréteur et des compilateurs à la volée, pas avec du microcode.