Décider

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.

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.

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.

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.

La comparaison à zéro suit la même logique et s'écrit aussi en raccourci : beqz t0, ou devient beq t0, zero, ou, bnez devient bne, bltz devient blt t0, zero, ou. 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.

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 ».

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.

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à.

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.

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.

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.

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.

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.