Jeu d'instructions et assembleur

Deux lignes de programme :

1somme = 02pour i de 1 à 2 : somme = somme + i

Sept instructions machine, douze exécutions, et pas une seule variable — seulement des registres numérotés. C'est l'écart que ce chapitre doit combler, et il n'y a pas de raccourci : il se comble en traçant, pas en lisant. C'est pourquoi il pèse dix heures à lui seul, un cinquième du cours.

Le jeu d'instructions (instruction set architecture) est le contrat entre le matériel et le logiciel : la liste de ce que la machine sait faire, et la façon exacte de le lui demander. C'est la seule couche du cours qui soit à la fois visible du programmeur et gravée dans le silicium — ce qui explique sa stabilité. Un binaire x86 de 1995 s'exécute encore aujourd'hui.

Une instruction est un entier

Le chapitre 5 l'a posé : dans le registre d'instruction, il n'y a qu'un mot. Le format d'instruction dit comment ce mot se découpe. Prenons MIPS, l'architecture du TP, dont toutes les instructions tiennent sur exactement 32 bits.

1Format R — opérations entre registres2┌────────┬───────┬───────┬───────┬────────┬────────┐3│ op  6  │ rs 5  │ rt 5  │ rd 5  │ sh  5  │ fn  6  │4└────────┴───────┴───────┴───────┴────────┴────────┘5   add $rd, $rs, $rt        rd ← rs + rt6 7Format I — une valeur immédiate ou un déplacement8┌────────┬───────┬───────┬────────────────────────┐9│ op  6  │ rs 5  │ rt 5  │   immédiat        16   │10└────────┴───────┴───────┴────────────────────────┘11   addi $rt, $rs, imm       rt ← rs + imm12 13Format J — un saut14┌────────┬───────────────────────────────────────┐15│ op  6  │        adresse             26         │16└────────┴───────────────────────────────────────┘

Trois enseignements se lisent directement sur ces cases.

Cinq bits pour désigner un registre, donc $2^5 = 32$ registres : le nombre n'est pas choisi, il découle du format. Seize bits pour l'immédiat, donc une constante comprise entre $-32768$ et $32767$ ; charger une valeur plus grande demande deux instructions, ce qui surprend toujours en TD. Et six bits de code opération, soit 64 codes — d'où le champ fn supplémentaire du format R, qui démultiplie les possibilités sans élargir le mot.

C'est l'occasion de nommer un débat vieux de quarante ans. Une architecture CISC (x86) offre des instructions nombreuses, de longueurs variables, dont certaines font beaucoup de travail. Une architecture RISC (MIPS, ARM, RISC-V) n'offre que des instructions simples, toutes de même longueur, et compte sur le compilateur pour les combiner. Le second choix simplifie énormément le décodage et rend le pipeline du chapitre 8 possible ; c'est pourquoi il domine aujourd'hui, y compris à l'intérieur des processeurs x86, qui traduisent en interne leurs instructions vers un jeu de type RISC.

Les registres, et pourquoi ils existent

Un registre est une mémoire de la taille d'un mot, à l'intérieur du processeur. Il n'a pas d'adresse : il a un numéro, et ce numéro tient dans l'instruction elle-même.

Sa raison d'être est le goulot d'étranglement du chapitre 5. Lire un registre coûte une fraction de cycle ; lire la mémoire en coûte plusieurs dizaines, voire des centaines si la donnée n'est pas en cache. Une architecture RISC en tire une règle stricte, dite chargement-rangement : seules deux instructions touchent la mémoire, lw pour charger et sw pour ranger. Tout le calcul se fait entre registres.

Conséquence directe sur la façon d'écrire : on charge, on calcule autant que possible, on range. Un TD où chaque opération commence par un lw et finit par un sw produit du code juste et trois fois trop lent.

Quelques registres MIPS reviennent constamment : $zero, qui vaut toujours 0 et ne peut pas être écrit — c'est lui qui permet de charger une constante par addi $t0, $zero, 5, faute d'instruction « mettre à » ; $t0 à $t9, les registres de travail ; $s0 à $s7, ceux qu'une fonction doit restituer intacte ; $sp, le sommet de pile ; $ra, l'adresse de retour.

Les modes d'adressage

Un opérande peut être désigné de plusieurs façons. Le mode d'adressage est cette façon, et c'est le second point qui coince du chapitre — moins par difficulté que par confusion entre « l'adresse » et « ce qui est à l'adresse ».

Deux méritent un mot. Le basé avec déplacement est le mode de l'accès aux tableaux et aux champs de structure : l'adresse de base dans un registre, le décalage constant dans l'instruction. T[i] pour un tableau d'entiers de 4 octets devient « adresse de T plus $4i$ » — d'où le décalage de 2 bits, plus rapide qu'une multiplication, que le compilateur génère systématiquement.

Le relatif au compteur ordinal est le mode des branchements. On n'écrit pas l'adresse absolue de la cible mais l'écart par rapport à l'instruction courante, ce qui tient sur 16 bits et rend le code translatable : un programme chargé ailleurs en mémoire continue de fonctionner sans réécriture, ce dont le chargeur du cours de systèmes tire parti.

Quatre familles d'instructions

Arithmétiques et logiques. add, sub, and, or, xor, sll et srl pour les décalages. Elles lisent des registres et écrivent un registre. Chacune correspond à un réglage de l'UAL du chapitre 4, sélectionné par le multiplexeur que le décodage commande.

Transfert. lw et sw entre mémoire et registre, move entre registres. À noter, la distinction annoncée au chapitre 2 : lb charge un octet avec extension de signe, lbu sans. Choisir la mauvaise transforme un $-5$ en 251, silencieusement.

Branchements et sauts. C'est ici que tout le contrôle se joue, et le mécanisme est toujours le même : écrire dans le compteur ordinal. beq et bne le font sous condition d'égalité, j inconditionnellement, jal en sauvegardant au passage l'adresse de retour dans $ra — c'est l'appel de fonction, et jr $ra en est le retour.

Un détail qui déroute : MIPS n'a pas d'instruction « brancher si inférieur ». Il faut deux temps — slt calcule un booléen dans un registre, puis beq ou bne branche dessus. C'est le slti que l'animation ci-dessous exécute, et c'est aussi pourquoi la comparaison signée et la non signée sont deux instructions distinctes, slt et sltu.

Appels système. syscall passe la main au système d'exploitation pour tout ce que le processeur seul ne peut pas faire : afficher, lire, terminer. C'est la frontière que le chapitre 1 du cours de systèmes appellera le passage en mode noyau.

Traduire du haut niveau

Toutes les structures de contrôle se ramènent à des branchements, selon des schémas mécaniques qu'il faut connaître par cœur.

1si (a < b) alors X sinon Y2 3        slt  $t0, $a, $b       # $t0 ← (a < b)4        beq  $t0, $zero, sinon # condition INVERSÉE : on saute si FAUX5        ... X ...6        j    finsi7sinon:  ... Y ...8finsi:

La règle qui surprend : la condition est toujours inversée. En haut niveau on entre dans le bloc si le test réussit ; en assembleur on saute par-dessus le bloc si le test échoue. Une fois cette inversion admise, les trois autres schémas s'écrivent seuls.

1tant que (i < n) faire corps2 3boucle: slt  $t0, $i, $n4        beq  $t0, $zero, fin5        ... corps ...6        j    boucle7fin:

Un pour est un tant que dont l'initialisation précède et l'incrément clôt le corps — c'est exactement le programme de l'animation. Et l'accès T[i] se décompose en trois temps : décaler i de 2 bits pour obtenir l'écart en octets, l'ajouter à l'adresse de base, puis charger.

À vous

L'exercice donne un interpréteur MIPS réduit — une quinzaine d'instructions — et vous demande d'écrire le programme, pas la machine. Trois traductions à produire, dans l'ordre de difficulté : un maximum de deux valeurs (si-sinon), la somme d'un tableau (boucle et accès indexé), puis un compte d'éléments pairs.

L'interpréteur affiche la trace registre par registre. Servez-vous-en comme du tableau de la salle de TD : quand un programme ne donne pas le bon résultat, la trace montre l'instruction exacte où l'état diverge de ce que vous attendiez.

// ── Un interpréteur MIPS réduit ───────────────────────────────────────────
// Une instruction : [mnémonique, destination, source1, source2].
// Registres nommés librement ; "zero" vaut toujours 0.

function executer(prog, memoire, tracer) {
  const R = { zero: 0 };
  const lire = (x) => (typeof x === "number" ? x : (R[x] ?? 0));
  const etiquettes = {};
  prog.forEach((ins, i) => { if (ins[0] === "label") etiquettes[ins[1]] = i; });

  let CO = 0, pas = 0;
  while (CO < prog.length && pas++ < 500) {
    const [op, a, b, c] = prog[CO];
    let saut = null;
    if (op === "li")   R[a] = lire(b);
    if (op === "add")  R[a] = lire(b) + lire(c);
    if (op === "sub")  R[a] = lire(b) - lire(c);
    if (op === "addi") R[a] = lire(b) + c;
    if (op === "slt")  R[a] = lire(b) < lire(c) ? 1 : 0;
    if (op === "slti") R[a] = lire(b) < c ? 1 : 0;
    if (op === "andi") R[a] = lire(b) & c;
    if (op === "lw")   R[a] = memoire[lire(b) + c];        // lw a, c(b)
    if (op === "sw")   memoire[lire(b) + c] = lire(a);
    if (op === "beq" && lire(a) === lire(b)) saut = etiquettes[c];
    if (op === "bne" && lire(a) !== lire(b)) saut = etiquettes[c];
    if (op === "j")    saut = etiquettes[a];
    if (tracer && op !== "label") {
      console.log("   " + [op, a, b, c].filter((x) => x !== undefined).join(" ").padEnd(22) +
        JSON.stringify(R));
    }
    CO = saut !== null && saut !== undefined ? saut : CO + 1;
  }
  return R;
}

// ── 1. Maximum de deux valeurs (si-sinon) ─────────────────────────────────
// max = (a < b) ? b : a, avec a en $a et b en $b, résultat dans $max.
const MAX = [
  ["li", "a", 12], ["li", "b", 37],
  ["slt", "t", "a", "b"],          // t = (a < b)
  ["beq", "t", "zero", "sinon"],   // condition INVERSÉE
  // ← branche « alors » : max = b
  ["j", "fin"],
  ["label", "sinon"],
  // ← branche « sinon » : max = a
  ["label", "fin"],
];

// ── 2. Somme d'un tableau (boucle + accès indexé) ─────────────────────────
// Le tableau occupe la mémoire à partir de l'adresse 0, un mot par case.
const TABLEAU = [4, 8, 15, 16, 23, 42];
const SOMME = [
  ["li", "somme", 0],
  ["li", "i", 0],
  ["li", "n", TABLEAU.length],
  ["label", "boucle"],
  // ← à écrire : sortir si i >= n, charger T[i], accumuler, incrémenter i
];

// ── À VOUS ────────────────────────────────────────────────────────────────
// Complétez MAX puis SOMME. Un troisième défi : compter les valeurs paires
// du tableau (indice : andi t, x, 1 met à 1 le bit de parité).

console.log("— maximum —");
console.log("max =", executer(MAX, [], true).max, "| attendu 37");

console.log("— somme —");
console.log("somme =", executer(SOMME, [...TABLEAU], false).somme, "| attendu 108");

function executer(prog, memoire, tracer) {
  const R = { zero: 0 };
  const lire = (x) => (typeof x === "number" ? x : (R[x] ?? 0));
  const etiquettes = {};
  prog.forEach((ins, i) => { if (ins[0] === "label") etiquettes[ins[1]] = i; });

  let CO = 0, pas = 0;
  while (CO < prog.length && pas++ < 500) {
    const [op, a, b, c] = prog[CO];
    let saut = null;
    if (op === "li")   R[a] = lire(b);
    if (op === "add")  R[a] = lire(b) + lire(c);
    if (op === "sub")  R[a] = lire(b) - lire(c);
    if (op === "addi") R[a] = lire(b) + c;
    if (op === "slt")  R[a] = lire(b) < lire(c) ? 1 : 0;
    if (op === "slti") R[a] = lire(b) < c ? 1 : 0;
    if (op === "andi") R[a] = lire(b) & c;
    if (op === "lw")   R[a] = memoire[lire(b) + c];
    if (op === "sw")   memoire[lire(b) + c] = lire(a);
    if (op === "beq" && lire(a) === lire(b)) saut = etiquettes[c];
    if (op === "bne" && lire(a) !== lire(b)) saut = etiquettes[c];
    if (op === "j")    saut = etiquettes[a];
    if (tracer && op !== "label") {
      console.log("   " + [op, a, b, c].filter((x) => x !== undefined).join(" ").padEnd(22) +
        JSON.stringify(R));
    }
    CO = saut !== null && saut !== undefined ? saut : CO + 1;
  }
  return R;
}

// 1. Maximum. Le schéma si-sinon : tester, brancher sur l'ÉCHEC vers la
// branche sinon, écrire la branche alors, sauter par-dessus le sinon.
const MAX = [
  ["li", "a", 12], ["li", "b", 37],
  ["slt", "t", "a", "b"],
  ["beq", "t", "zero", "sinon"],
  ["add", "max", "b", "zero"],     // max = b  (pas d'instruction « copier »)
  ["j", "fin"],
  ["label", "sinon"],
  ["add", "max", "a", "zero"],     // max = a
  ["label", "fin"],
];

const TABLEAU = [4, 8, 15, 16, 23, 42];

// 2. Somme. Le schéma tant que : condition en tête, saut de sortie sur
// l'échec, corps, incrément, saut de retour.
const SOMME = [
  ["li", "somme", 0],
  ["li", "i", 0],
  ["li", "n", TABLEAU.length],
  ["label", "boucle"],
  ["slt", "t", "i", "n"],
  ["beq", "t", "zero", "fin"],
  ["lw", "x", "i", 0],             // ici une case = un mot, donc pas de x4
  ["add", "somme", "somme", "x"],
  ["addi", "i", "i", 1],
  ["j", "boucle"],
  ["label", "fin"],
];

// 3. Compter les valeurs paires : même boucle, un test de parité en plus.
const PAIRS = [
  ["li", "compte", 0], ["li", "i", 0], ["li", "n", TABLEAU.length],
  ["label", "boucle"],
  ["slt", "t", "i", "n"],
  ["beq", "t", "zero", "fin"],
  ["lw", "x", "i", 0],
  ["andi", "p", "x", 1],           // p = bit de poids faible = 1 si impair
  ["bne", "p", "zero", "suite"],   // impair : on ne compte pas
  ["addi", "compte", "compte", 1],
  ["label", "suite"],
  ["addi", "i", "i", 1],
  ["j", "boucle"],
  ["label", "fin"],
];

console.log("— maximum —");
console.log("max =", executer(MAX, [], true).max, "| attendu 37");

console.log("— somme —");
console.log("somme =", executer(SOMME, [...TABLEAU], false).somme, "| attendu 108");

console.log("— nombre de valeurs paires —");
console.log("compte =", executer(PAIRS, [...TABLEAU], false).compte, "| attendu 4");

En travaux pratiques

/* en C */                # en assembleur
if (a > b)                bgt  $t0, $t1, vrai
  c = 1;                li   $t2, 0        # sinon
else                      j    fin
  c = 0;              vrai:
                        li   $t2, 1
                      fin:

# votre version                gcc -S -O0
  li   $t0, 1     # i        sw  $zero, -8($fp)   # tout en MÉMOIRE
  li   $t1, 0     # somme    lw  $eax, -8($fp)
boucle:                        addl ...
  bgt  $t0, $a0, fin         sw  $eax, -8($fp)    # relu, réécrit
  add  $t1, $t1, $t0
  addi $t0, $t0, 1
  j    boucle
fin:

carre:
  mul  $v0, $a0, $a0    # argument dans $a0, retour dans $v0
  jr   $ra              # saute à l'adresse rangée dans $ra

main:
  li   $a0, 5
  jal  carre            # jal range l'adresse SUIVANTE dans $ra
  move $s0, $v0

fact:
  ble  $a0, 1, base
  addi $a0, $a0, -1
  jal  fact          # ← ÉCRASE $ra avec l'adresse d'ici
  ...
base:
  jr   $ra           # revient à l'appel INTERNE, pas à l'appelant
                     # → boucle infinie entre fact et lui-même

/* la correction */
  addi $sp, $sp, -4
  sw   $ra, 0($sp)   # empiler avant l'appel
  ...
  lw   $ra, 0($sp)   # dépiler après
  addi $sp, $sp, 4

-O0 : 24 instructions, 12 accès mémoire
-O2 :  7 instructions,  0 accès mémoire (hors résultat)

la variable de boucle n'existe plus en mémoire : elle vit
dans un registre du début à la fin
et si n est une constante, gcc calcule la somme À LA COMPILATION

Ce que la suite en fait

Deux fils partent d'ici. Le premier va au chapitre 7 : lw et sw sont les instructions dont le coût est le plus variable, de un cycle à plusieurs centaines selon que la donnée est en cache ou non, et le principe de localité qui rend le cache efficace se lit directement dans les schémas de boucle qu'on vient d'écrire.

Le second va au chapitre 8. Un jeu d'instructions RISC — longueur fixe, décodage simple, accès mémoire cantonné à deux instructions — n'est pas seulement élégant : c'est ce qui rend le pipeline réalisable. Et les branchements, dont on vient de voir qu'ils sont partout, y deviendront le principal obstacle, d'où la prédiction de branchement.

À retenir