Répéter

Les instructions de ce chapitre

Une boucle ne demande aucune instruction nouvelle : elle se fait avec les branchements du chapitre précédent, bgt, bge, blt et le saut sans condition j. Deux raccourcis d'écriture s'y ajoutent, et ils sont si commodes qu'ils apparaissent dans presque toute boucle.

Les deux comparent un registre à zéro, ce qui est exactement la question que pose un compteur décompté jusqu'à épuisement. Le reste des programmes s'écrit avec li, add et addi, connues depuis le premier chapitre.

Le saut en arrière

Les étiquettes du chapitre précédent servaient toutes à enjamber du code. Rien n'oblige une étiquette à être placée en aval : posée avant le branchement qui la vise, elle fait revenir le compteur ordinal.

Deux instructions seulement, et la seconde fait tout le travail. bnez a0, boucle saute vers l'étiquette boucle tant que a0 ne vaut pas zéro : c'est la forme courte de bne a0, zero, boucle, que la colonne des instructions réelles affiche telle quelle. La condition d'arrêt est donc l'épuisement du compteur, et rien d'autre.

Six pas au total, pour deux instructions écrites. Le registre a0 prend successivement 2, 1, puis 0, et le branchement de l'adresse 0x4 cesse de sauter au troisième passage, ce qui laisse le compteur ordinal sortir du programme. Trois tours, six pas : la distinction est importante et ne cessera pas de l'être, car un tour coûte ici deux instructions.

Une modification d'une lettre renverse tout. Ouvrir « Modifier le programme », remplacer bnez par beqz et relancer : le programme s'arrête au bout de deux pas, a0 valant 2. beqz saute dès que le registre vaut zéro, donc la condition est fausse au premier passage, et la boucle ne boucle pas. Les deux instructions posent la même question et en retiennent la réponse opposée.

Un « tant que » complet

Une boucle utile a besoin de trois choses : une préparation avant d'entrer, un corps, et une condition qui décide de recommencer. La somme des entiers de un à a0 les montre toutes les trois.

Le moteur compte vingt-trois pas et laisse t0 à 15, t1 à 6. La structure se lit sur les adresses : t0 et t1 sont préparés une fois, avant l'étiquette ; la condition de sortie est testée à l'adresse 0x8, en tête de tour ; le corps occupe 0xc et 0x10 ; le saut inconditionnel de 0x14 revient à boucle.

Trois remarques valent d'être faites. La condition est, comme au chapitre précédent, l'inverse de celle qui décrit la boucle : le compteur tourne tant que t1 ne dépasse pas a0, donc l'instruction sort quand t1 dépasse a0. Ensuite, la valeur finale de t1 est 6 et non 5 : le compteur est incrémenté une dernière fois avant que le test ne le refuse, ce qui surprend toujours. Enfin, le corps et l'incrément ne sont séparés par rien de particulier ; c'est l'auteur qui décide qu'addi t1, t1, 1 fait partie de la mécanique et non du travail.

Une instruction de différence, un tour de différence

Le décalage d'une unité sur la borne est la faute la plus banale de la programmation, et la moins visible. En assembleur, elle tient dans une seule lettre.

Dix-neuf pas au lieu de vingt-trois, t0 à 10 au lieu de 15, t1 à 5 au lieu de 6. Le corps a été exécuté quatre fois au lieu de cinq. La différence entre les deux programmes est bge au lieu de bgt : le premier sort dès que le compteur atteint la borne, le second attend qu'il la dépasse. Le résultat est aussi juste dans les deux cas du point de vue de la machine, et faux dans l'un des deux du point de vue de l'énoncé.

Compter les tours plutôt que la valeur

Une boucle « pour » ne se distingue pas d'un « tant que » dans la machine. Elle en est un cas particulier, celui où la condition porte sur un compteur préparé avant l'entrée et incrémenté à chaque tour. Le programme suivant double une valeur autant de fois que a0 l'indique.

Vingt-trois pas, t0 à 32, t1 à 5. Le compteur va de 0 à 4 inclus et s'arrête à 5, ce qui donne bien cinq tours : c'est la forme « les n premiers », celle qui demande bge et non bgt. Avec a0 = 0, le moteur ne compte que trois pas : les deux préparations, puis le branchement qui sort immédiatement. Le corps n'est jamais exécuté, et t0 reste à 1.

La condition en bas plutôt qu'en haut

Rien n'impose de tester en tête de tour. La même boucle s'écrit avec le test à la fin, et le branchement conditionnel remplace alors à la fois le test et le saut de retour.

Dix-sept pas au lieu de vingt-trois, pour un résultat identique : t0 à 32. Deux raisons à cet écart. Le tour coûte trois instructions au lieu de quatre, puisque le branchement conditionnel sert aussi de retour et qu'il n'y a plus de saut inconditionnel. Et la condition est cette fois écrite dans le sens direct, blt t1, a0, puisqu'elle décide de continuer et non de sortir.

Cette forme est plus courte, et c'est celle qu'un compilateur produit le plus souvent. Elle n'est pourtant pas équivalente, et le cas limite le montre sans ambiguïté.

Cinq pas, et t0 finit à 2. La boucle a tourné une fois alors qu'il ne fallait pas qu'elle tourne du tout, parce que le test n'arrive qu'après le corps. La version à condition en tête, lancée avec la même valeur, compte trois pas et laisse t0 à 1. Un corps exécuté zéro fois et un corps exécuté une fois : l'écart est entier, il apparaît exactement sur le cas vide, et c'est le cas que personne n'essaie.

La boucle qui ne s'arrête jamais

Une boucle s'arrête si, et seulement si, quelque chose fait évoluer la condition d'arrêt vers sa réalisation. Le programme ci-dessous a l'air correct, et ne s'arrête pas.

Le moteur s'arrête de lui-même au bout de quarante instructions, avec le message qui l'explique. La cause se lit sur les deux registres suivis côte à côte : a0 monte de 0 à 10, mais a1 monte de 10 à 20 pendant ce temps. L'écart entre les deux ne se réduit jamais, donc a0 ne rattrape jamais a1. Le bug n'est pas dans la condition, qui est correcte, mais dans le corps, qui modifie une valeur qu'il aurait fallu laisser tranquille.

C'est la forme la plus courante de boucle sans fin, et elle est bien plus fréquente que l'oubli pur et simple de l'incrément. La bonne question à poser devant une boucle n'est donc pas « la condition est-elle juste », mais « quelle instruction du corps rapproche la condition de sa réalisation, et cette instruction est-elle exécutée à chaque tour ».

Multiplier sans instruction de multiplication

RV32I ne sait pas multiplier. L'instruction mul existe dans une extension du jeu, mais pas dans la base, et un processeur qui ne l'implémente pas doit s'en passer. La multiplication devient donc une boucle : multiplier a0 par a1 consiste à ajouter a0 à un total, a1 fois.

Le test d'arrêt emploie ici beqz a1, fin, le miroir de bnez : il saute vers la sortie dès que a1 atteint zéro, et laisse le corps s'exécuter tant que ce n'est pas le cas. Placer le test en tête avec beqz plutôt qu'en fin de corps avec bnez est ce qui rend cette boucle correcte pour un multiplicateur nul.

Trente pas, et t0 finit à 42. Le compteur est ici la valeur a1 elle-même, décomptée jusqu'à zéro : c'est plus court qu'un compteur séparé, et cela détruit a1 au passage, ce dont il faudra se souvenir. En échangeant les deux valeurs de départ, c'est-à-dire en calculant sept fois six au lieu de six fois sept, le moteur ne compte plus que vingt-six pas pour le même résultat.

Cette différence de quatre pas n'a rien d'anecdotique. Le produit est le même, le programme est le même, seul le nombre de tours change, parce que la boucle tourne autant de fois que le second opérande. Multiplier par un petit nombre coûte peu, multiplier par un grand nombre coûte beaucoup : un mul matériel, lui, coûte le même temps quelles que soient les valeurs. Ranger le plus petit des deux dans a1 est donc une optimisation réelle, et c'est exactement le genre de raisonnement qui disparaît derrière l'étoile d'un langage de haut niveau.

La méthode

1. Énoncer l'invariant avant toute écriture : ce que contient chaque registre au début de chaque tour, et ce qui reste à faire.
2. Décider si la borne est incluse, puis en déduire la comparaison : incluse demande bgt ou bgtu, exclue demande bge ou bgeu.
3. Écrire la préparation avant l'étiquette, le corps après, et le retour en dernier. Une instruction d'initialisation placée après l'étiquette par mégarde repart à chaque tour.
4. Vérifier qu'une instruction du corps rapproche la condition de sa réalisation, et qu'elle est exécutée sur tous les chemins possibles du corps.
5. Éprouver la boucle sur l'entrée vide, zéro élément, avant de l'éprouver sur une entrée normale. C'est le cas qui sépare les deux formes de boucle, et celui qui n'est jamais essayé.
6. Compter les tours et les pas séparément, puisqu'un tour vaut trois ou quatre instructions, et que le compte de pas de la figure est le seul chiffre qui ne se discute pas.

Synthèse

• Les boucles n'apportent qu'un raccourci d'écriture, la comparaison à zéro : bnez revient tant que le registre n'est pas nul, beqz sort dès qu'il l'est, et l'assembleur les ramène à bne et beq face au registre zero.
• Une boucle est un branchement dont la destination est placée plus haut dans le programme. Le processeur ne connaît ni pour ni tant que : il range une adresse dans le compteur ordinal, en avant ou en arrière, sans faire de différence.
• Une boucle complète tient en trois morceaux : une préparation avant l'étiquette, un corps, et une condition qui décide de recommencer. Testée en tête, elle sort sur la condition inverse ; testée en fin de corps, elle revient sur la condition directe.
• Le décalage d'une unité se joue sur une seule instruction : bgt et bge sur la même boucle donnent cinq tours et vingt-trois pas dans un cas, quatre tours et dix-neuf pas dans l'autre, pour des sommes de 15 et de 10.
• La boucle à condition en fin de corps est plus courte, dix-sept pas contre vingt-trois, mais exécute son corps au moins une fois : sur une entrée vide, elle donne 2 là où l'autre donne 1.
• Une boucle ne s'arrête que si le corps rapproche la condition d'arrêt de sa réalisation. Un compteur qui monte vers une borne qui monte aussi produit une boucle sans fin, que le moteur signale en s'arrêtant d'autorité.
• RV32I n'ayant aucune instruction de multiplication, un produit s'écrit par additions répétées, et son coût dépend de l'opérande choisi comme compteur : trente pas pour six fois sept, vingt-six pour sept fois six.

Une boucle qui répète un calcul sur le même registre reste limitée à ce qu'un registre peut contenir. Tableaux et adresses fait porter la répétition sur une suite de cases mémoire, et montre que l'indice d'un tableau n'existe pas : il se calcule.