Décider

Les instructions de ce chapitre

Six branchements et un saut sans condition : c'est tout ce que ce chapitre emploie, et tout ce que RV32I possède en la matière. Les six premiers comparent deux registres et rangent l'adresse d'une étiquette dans le compteur ordinal quand la comparaison est vraie. Aucun n'écrit dans un registre.

Les six branchements forment trois paires opposées, beq contre bne, blt contre bge, bltu contre bgeu, et les apprendre par paires vaut mieux que de les apprendre un par un. Ils n'arrivent pas non plus tous en même temps dans ce chapitre : beq et j ouvrent la marche, blt et bge viennent avec le premier « si … sinon », et la paire non signée attend la section sur les nombres négatifs, qui est la seule où elle se distingue de la paire signée. Les programmes s'appuient par ailleurs sur li, add et addi, posées au premier chapitre.

Le compteur ordinal cesse d'avancer tout seul

Une étiquette est un nom suivi de deux-points, posé devant une instruction. Elle ne produit rien : elle donne un nom à une adresse, pour que le programme puisse la viser sans la connaître. Une instruction de branchement compare deux registres, et, si la comparaison est vraie, range l'adresse de l'étiquette dans le compteur ordinal au lieu de le laisser avancer de quatre.

programme

1. 0x0beq a0, a1, egaux
2. 0x4li t0, 100addi t0, zero, 100
3. 0x8li t1, 7addi t1, zero, 7

registres

t0	0
t1	0
a0	4
a1	4

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.

Deux pas suffisent à ce programme : le branchement, puis li t1, 7. Le registre t0 finit à zéro, non parce que l'instruction qui lui donne cent aurait échoué, mais parce qu'elle n'a pas eu lieu. La figure signale le saut, et l'instruction sautée reste visible à l'écran, intacte et inutile.

Le même programme avec une valeur de départ différente prend l'autre chemin.

programme

1. 0x0beq a0, a1, egaux
2. 0x4li t0, 100addi t0, zero, 100
3. 0x8li t1, 7addi t1, zero, 7

registres

t0	0
t1	0
a0	3
a1	4

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.

Voilà tout le mécanisme. Un programme ne se lit plus de haut en bas : il se lit comme un chemin dont certains embranchements dépendent des données. C'est aussi ce qui rend l'assembleur difficile à parcourir des yeux, et ce qui rend une exécution pas à pas si utile.

Six comparaisons, et aucun registre de drapeaux

RV32I compte six branchements, et pas un de plus : ceux du tableau de tête. Ce qui mérite un regard, c'est ce qui n'y figure pas.

Il manque visiblement « supérieur strictement » et « inférieur ou égal ». Ils n'ont pas été oubliés : a > b s'obtient en demandant b < a, c'est-à-dire en échangeant les deux registres. L'assembleur propose l'échange sous forme de pseudo-instructions, bgt, ble, bgtu, bleu, et la figure montre ce qu'il en fait.

programme

1. 0x0bgt a0, a1, plus_grandblt a1, a0, plus_grand
2. 0x4li t0, 0addi t0, zero, 0
3. 0x8j finjal zero, fin
4. 0xcli t0, 1addi t0, zero, 1

registres

t0	0
a0	7
a1	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.

Ce programme contient aussi la première apparition de j, le saut sans condition. j fin range l'adresse de l'étiquette fin dans le compteur ordinal quoi qu'il arrive, sans comparer quoi que ce soit, et sert ici à empêcher la branche « plus grand » de s'exécuter à la suite de l'autre. La colonne des instructions réelles l'écrit jal zero, fin : une instruction d'appel dont l'adresse de retour est jetée dans zero, et dont le chapitre sur les appels de fonction montrera l'autre visage.

Ces formes commodes sont toutes des pseudo-instructions, et le tableau ci-dessous donne ce que l'assembleur écrit à leur place.

La comparaison à zéro suit la même logique, et les lignes beqz et bnez du tableau la donnent : beqz a0, ou saute quand a0 vaut zéro, bnez a0, ou quand il ne vaut pas zéro, et l'assembleur les ramène toutes deux à une comparaison ordinaire avec le registre zero. Le registre qui ne retient rien sert ici une deuxième fois, après avoir servi à écrire les copies et les constantes du premier chapitre. Ces deux formes sont celles qu'emploieront les boucles du chapitre suivant.

Traduire un « si … sinon » : la condition s'inverse

Un énoncé se formule presque toujours dans le sens positif : « si la mesure atteint le seuil, alors la valider, sinon la rejeter ». Le branchement, lui, sert à sauter par-dessus ce qu'il ne faut pas faire. La condition écrite dans l'instruction est donc l'inverse de celle de l'énoncé.

Pour « si a0 est supérieur ou égal à a1, ranger 1 dans t0, sinon y ranger 2 », le branchement teste a0 < a1 et vise la branche « sinon ».

programme

1. 0x0blt a0, a1, sinon
2. 0x4li t0, 1addi t0, zero, 1
3. 0x8j suitejal zero, suite
4. 0xcli t0, 2addi t0, zero, 2

registres

t0	0
a0	12
a1	20

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.

Deux pas, t0 à 2 : la branche « sinon » a été prise, comme l'énoncé le demande pour une mesure de douze face à un seuil de vingt. Avec a0 = 25, le moteur compte trois pas, t0 reçoit 1, et le j suite de l'adresse 0x8 sert à enjamber la branche « sinon ». Ce saut inconditionnel n'est pas un ornement : sans lui, le programme exécuterait les deux branches l'une après l'autre.

Le programme qui oublie de sauter

Le second piège est plus discret encore. Il vient du fait que la branche « alors » se termine sur l'instruction suivante, qui est le début de la branche « sinon ». Sans saut pour l'éviter, le programme traverse les deux.

programme

1. 0x0bge a0, a1, alors
2. 0x4li t0, 2addi t0, zero, 2
3. 0x8li t0, 1addi t0, zero, 1

registres

t0	0
a0	12
a1	20

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 moteur compte trois pas, et t0 finit à 1. Or il vaut 1 quelle que soit la valeur de a0 : quand le branchement est pris, seule la branche « alors » s'exécute ; quand il ne l'est pas, la branche « sinon » s'exécute d'abord, puis la branche « alors » par-dessus. Le test est devenu décoratif, et la figure le dit en affichant la valeur écrasée : 2 remplacé par 1 au pas suivant est la signature exacte de cette faute.

Enchaîner les cas

Un classement à trois issues s'écrit avec deux comparaisons successives, chacune sautant vers sa branche. L'exemple ci-dessous range une mesure dans trois catégories : en dessous de dix, entre dix et vingt-cinq, au-delà.

programme

1. 0x0li t1, 10addi t1, zero, 10
2. 0x4li t2, 25addi t2, zero, 25
3. 0x8blt a0, t1, bas
4. 0xcblt a0, t2, moyen
5. 0x10li t0, 3addi t0, zero, 3
6. 0x14j finjal zero, fin
7. 0x18li t0, 1addi t0, zero, 1
8. 0x1cj finjal zero, fin
9. 0x20li t0, 2addi t0, zero, 2

registres

t0	0
t1	0
t2	0
a0	18

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.

Avec dix-huit, le moteur compte cinq pas et t0 reçoit 2 : la première comparaison échoue, la seconde réussit, et le programme atterrit sur l'étiquette moyen. Deux détails méritent attention. D'abord, la seconde comparaison n'a pas besoin de vérifier que la mesure dépasse dix : elle ne s'exécute que si la première a échoué, donc cette information est déjà acquise par la position dans le code. Ensuite, chaque branche se termine par un saut vers fin, sauf la dernière, qui n'a rien à enjamber.

Les seuils passent par des registres parce qu'un branchement compare deux registres, jamais un registre et une constante. Là où un langage de haut niveau écrit si x < 10 sans effort, la constante doit ici être chargée d'abord.

Les mêmes bits, deux lectures

Le nombre -1 est rangé dans un registre sous la forme de trente-deux bits à 1, ce qui est aussi l'écriture de 4 294 967 295 si les mêmes bits sont lus comme un nombre positif. Ce codage s'appelle le complément à deux, et il est choisi pour que l'addition fonctionne sans savoir si les nombres sont signés : additionner les bits de -1 et ceux de 1 produit un report qui déborde des trente-deux bits et disparaît, et il reste zéro.

La comparaison, elle, ne peut pas être neutre. Le même motif de bits est le plus petit nombre possible en lecture signée, et l'un des plus grands en lecture non signée. C'est exactement pourquoi il existe blt et bltu.

programme

1. 0x0li t2, 1addi t2, zero, 1
2. 0x4li t3, 1addi t3, zero, 1
3. 0x8blt t0, t1, apres_signe
4. 0xcli t2, 0addi t2, zero, 0
5. 0x10bltu t0, t1, apres_nonsigne
6. 0x14li t3, 0addi t3, zero, 0

registres

t0	-1
t1	1
t2	0
t3	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.

Cinq pas, t2 à 1, t3 à 0. Les deux instructions ont reçu les mêmes deux registres et ont pris des décisions opposées. Pour blt, -1 est inférieur à 1 ; pour bltu, le même motif de bits vaut plus de quatre milliards et n'est certainement pas inférieur à 1. Aucune des deux ne se trompe : elles répondent à deux questions différentes, et c'est au programme de choisir laquelle poser.

Quand l'addition sort du domaine

Les trente-deux bits d'un registre représentent, en lecture signée, les nombres de -2 147 483 648 à 2 147 483 647. Il n'y a rien au-delà. Ajouter 1 au plus grand ne donne pas une erreur, ne donne pas un nombre plus grand : cela donne le plus petit.

programme

1. 0x0addi t1, t0, 1
2. 0x4addi t2, t0, 2

registres

t0	2147483647
t1	0
t2	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 moteur donne t1 à -2 147 483 648 et t2 à -2 147 483 647. Les bits se comportent comme les aiguilles d'une horloge : après la dernière graduation vient la première. Le processeur n'a pas de raison de protester, puisqu'il ne sait pas ce que ces bits représentent.

La conséquence pratique est qu'un test de dépassement écrit dans l'ordre naturel ne détecte rien.

programme

1. 0x0li t2, 2000000000lui t2, 488281
2. 0x4addi t2, t2, 1024
3. 0x8add t0, t0, t1
4. 0xcbge t0, t2, alerte
5. 0x10li t3, 0addi t3, zero, 0
6. 0x14j finjal zero, fin
7. 0x18li t3, 1addi t3, zero, 1

registres

t0	2147483000
t1	1000
t2	0
t3	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 total de départ vaut 2 147 483 000, l'ajout vaut 1 000, le seuil d'alerte vaut 2 000 000 000. La somme dépasse largement le seuil, et pourtant t3 finit à zéro : aucune alerte. Le troisième pas montre pourquoi, en affichant t0 qui passe de 2 147 483 000 à -2 147 483 296. Le total est devenu négatif, donc inférieur au seuil, donc parfaitement rassurant. Un compteur qui surveille son propre dépassement en comparant son total à un seuil surveille une quantité qui a déjà cessé d'exister.

La parade consiste à tester avant d'additionner, en comparant l'ajout à ce qui reste de place. Le chapitre sur la pile montrera un autre visage du même problème, quand la quantité qui déborde n'est plus un total mais une zone de mémoire.

1.L'énoncé dit « si a0 est supérieur ou égal à a1, alors faire ceci ». Quel branchement ouvre la traduction ?

beq a0, a1, sinon, puisque le cas d'égalité est inclusbge a0, a1, sinon, qui reprend la condition de l'énoncéblt a0, a1, sinon, qui saute quand la condition de l'énoncé est fausse

2.Deux registres contiennent respectivement -1 et 1. Quelle décision prennent blt puis bltu ?

blt saute, bltu ne saute pasAucune des deux ne sauteLes deux sautent, puisque les registres sont les mêmes

3.Un registre contient le plus grand entier signé représentable. Que donne addi t1, t0, 1 ?

La même valeur, l'addition étant bloquée à la limiteUne erreur d'exécution signalée par le processeurLe plus petit entier signé, soit -2 147 483 648

4.Pourquoi un test « si le total dépasse le seuil » ne détecte-t-il pas un débordement ?

Parce que le seuil ne tient pas sur douze bitsParce que le total a déjà basculé dans les négatifs quand le test s'exécuteParce que le branchement compare toujours sans signe

5.Dans quel cas faut-il préférer bgeu à bge ?

Quand les valeurs comparées sont des adresses, des tailles ou des compteurs, jamais négatifsJamais : bge est toujours plus sûrQuand l'un des deux registres peut contenir un nombre négatif

La méthode

1. Écrire l'énoncé en français d'abord, avec sa condition et ses deux branches, avant de choisir la moindre instruction.
2. Inverser la condition au moment de la traduire : le branchement saute vers la branche qui ne doit pas être exécutée en séquence.
3. Poser les étiquettes avant le corps, une par branche et une pour le point de convergence, puis remplir. Une étiquette porte un nom qui dit le cas, pas un numéro.
4. Terminer chaque branche par un saut vers le point de convergence, sauf la dernière, et vérifier ce point en particulier : une branche qui déborde sur la suivante est la faute la plus silencieuse du chapitre.
5. Choisir entre la famille signée et la famille non signée en se demandant si la valeur comparée peut être négative. Les adresses, les tailles et les compteurs relèvent de bltu et bgeu.
6. Vérifier les deux chemins, pas seulement celui de l'exemple : relancer la figure avec des valeurs qui forcent l'autre branche, et comparer les comptes de pas.

Synthèse

• RV32I compte six branchements : beq, bne, blt, bge, bltu, bgeu. Chacun compare deux registres et, si la comparaison est vraie, range dans le compteur ordinal l'adresse d'une étiquette. Aucun n'écrit dans un registre.
• La comparaison tient dans l'instruction de saut : RISC-V n'a pas de registre de drapeaux, rien ne persiste entre le test et la décision. Les autres formes de branchement, bgt, ble, beqz, sont des raccourcis qui échangent les registres ou en remplacent un par zero.
• Traduire un si … sinon demande de brancher sur la condition inverse de celle de l'énoncé, et de terminer la première branche par un saut inconditionnel. L'oubli de ce saut produit un programme qui exécute les deux branches et donne toujours la même réponse.
• Le complément à deux fait que les mêmes trente-deux bits valent -1 en lecture signée et plus de quatre milliards en lecture non signée. Sur -1 et 1, blt saute et bltu ne saute pas.
• Un débordement ne se signale pas : ajouter 1 au plus grand entier signé donne le plus petit. Un test de seuil placé après l'addition compare un total qui a déjà basculé dans les négatifs, et ne déclenche aucune alerte.
• Le choix entre famille signée et famille non signée appartient au programme, puisque les bits ne portent aucun type. Les adresses et les tailles se comparent sans signe.

Un branchement qui vise une étiquette placée plus haut dans le programme fait revenir le compteur ordinal en arrière, et tout recommence. Répéter construit les boucles à partir de ce seul geste, et montre pourquoi le processeur n'a jamais entendu parler de boucle.