Répéter

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.

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.

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.

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

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