Tableaux et adresses

Charger une adresse, puis lire à travers elle

Une déclaration données: pose des valeurs en mémoire et donne un nom à l'adresse de la première. Ce nom n'est pas une variable : c'est une adresse, et elle doit passer par un registre avant que quoi que ce soit ne soit lu. Le geste tient en deux temps, la puis lw, et il ne changera plus de tout le module.

Cinq pas, t1 à 12 et t2 à 5. La figure signale les deux accès, à l'adresse 0x1000 puis à l'adresse 0x1004 : quatre octets d'écart pour un élément d'écart. Entre les deux, addi t0, t0, 4 a fait passer t0 de 4096 à 4100, c'est-à-dire de 0x1000 à 0x1004. Le registre t0 ne contient pas une note : il contient l'endroit où en chercher une.

La colonne des instructions réelles mérite un regard. La ligne la t0, notes y donne lui t0, 1, suivie d'un addi zero, zero, 0 qui ne fait rien : l'assembleur réserve deux instructions pour charger une adresse, parce qu'une adresse ne tient pas toujours sur douze bits, et comble avec une instruction neutre quand une seule suffit.

L'indice n'existe pas, il se calcule

L'accès t[i] d'un langage de haut niveau se décompose en quatre choses, dont aucune n'est cachée ici : une adresse de base, un indice, une taille d'élément, et une addition. L'adresse cherchée vaut base plus indice multiplié par la taille de l'élément. Pour des mots de quatre octets, multiplier par quatre revient à décaler de deux bits vers la gauche, ce que slli fait en une instruction, faute de multiplication dans RV32I.

Le registre t1 vaut 8 après le décalage, 4104 après l'addition, et la lecture rapporte -3, le troisième élément. Les trois instructions du milieu sont exactement ce qu'un compilateur produit pour t[i], et elles expliquent d'un coup plusieurs mystères : pourquoi un tableau est indexé à partir de zéro, puisque l'élément zéro est celui qui se trouve à l'adresse de base plus rien ; pourquoi la taille d'élément doit être connue à la compilation ; et pourquoi l'accès à un élément quelconque coûte le même temps quel que soit l'indice.

Parcourir plutôt que recalculer

Rien n'oblige à repartir de la base à chaque tour. Un parcours complet se fait plus simplement en déplaçant le registre d'adresse, une boucle du chapitre précédent tenant le compte des éléments restants.

Trente-cinq pas, t2 à 61, et cinq lectures aux adresses 0x1000, 0x1004, 0x1008, 0x100c et 0x1010. Deux registres suffisent à tenir le parcours : t0 dit où lire, t1 dit combien de fois encore. Le registre t0 finit à 4116, une case au-delà du dernier élément, ce qui est normal et mérite d'être noté : après un parcours, le pointeur désigne la fin, pas le dernier élément.

Écrire dans le tableau se fait avec la même adresse, et l'instruction symétrique.

Trente-deux pas, et le tableau contient à la fin 24, 10, -6 et 80. Chaque tour lit, calcule, range au même endroit. La figure signale les écritures avec la valeur précédente, ce qui rend visible le fait qu'un tableau modifié sur place perd ses valeurs d'origine sans laisser de trace.

Une chaîne est un tableau d'octets

Un texte suit exactement la même convention, avec deux différences. La taille d'un élément vaut un octet et non quatre, donc l'adresse avance de un en un. Et la longueur n'est écrite nulle part : la fin est signalée par un octet nul posé après le dernier caractère. Le parcours ne compte donc pas, il cherche.

Cinquante-cinq pas, et t1 finit à 10, la longueur du mot. Les valeurs prises par t2 sont 97, 115, 115, 101, 109, 98, 108, 101, 117, 114, puis 0 : les codes des lettres, lus un octet à la fois par lb, et le zéro terminal trouvé à l'adresse 0x100a. Le décalage est de 1 à chaque tour, jamais de 4, parce que la taille d'un élément est ici d'un octet.

La taille d'élément n'est donc pas une propriété de la mémoire, c'est un choix de lecture. Rien n'empêche de lire quatre octets d'un texte d'un seul coup.

Les deux lectures d'octet donnent 65 et 68, les codes de A et de D. La lecture de mot, à la même adresse de base, donne 1 145 258 561. Ce nombre n'a aucun sens en tant que nombre, et il est pourtant la lecture exacte des mêmes quatre octets, assemblés dans l'ordre où le processeur les range. Les octets ne changent pas : c'est l'instruction qui décide de les voir comme un caractère ou comme un nombre de trente-deux bits.

Noter au passage le décalage écrit dans l'instruction, 3(t0), qui évite de déplacer le registre. Les deux écritures sont équivalentes, et la première est préférable quand l'adresse de base doit être conservée.

Sortir du tableau ne provoque rien

Voici la différence la plus nette entre ce module et un langage de haut niveau. En Python, lire t[7] dans une liste de trois éléments lève une exception qui arrête tout. Ici, il ne se passe rien du tout.

Le tableau notes occupe douze octets, de 0x1000 à 0x100b. La première lecture, au décalage 8, atteint son dernier élément et donne -3. La deuxième, au décalage 12, sort du tableau et donne 777 : c'est la valeur de seuil, déclarée juste après et posée à l'adresse 0x100c. La troisième, au décalage 16, atteint une case où rien n'a jamais été écrit et donne 0. Aucune des trois n'est signalée comme une faute, et le programme se termine normalement.

Une erreur est bien signalée, mais elle porte sur autre chose : l'alignement. Un mot de quatre octets se lit à une adresse multiple de quatre, et le moteur refuse toute autre adresse.

L'exécution s'interrompt avec le message qui désigne 0x1001 comme non multiple de quatre. La contrainte vient du matériel, qui va chercher la mémoire par blocs alignés, et elle explique une part des règles de disposition que les langages système imposent aux structures de données. Il est donc parfaitement possible de sortir d'un tableau sans être inquiété, et parfaitement impossible de lire un mot une case trop loin dans le mauvais sens.

Deux dimensions dans une seule suite de cases

Une grille n'a pas d'existence propre non plus. Elle est rangée ligne après ligne dans la même suite de cases, et l'élément de coordonnées ligne et colonne occupe l'indice ligne × largeur + colonne. La formule ajoute une multiplication à celle qui convertit l'indice en octets.

Sept pas, et t2 reçoit 31. Le registre t1 passe par 8, la ligne multipliée par la largeur, puis 9, l'indice dans la suite, puis 36, le même indice converti en octets, puis 4132, soit 0x1024, l'adresse finale. Les deux slli valent tous deux « multiplier par quatre », mais pour des raisons distinctes : le premier parce que la grille a quatre colonnes, le second parce qu'un mot occupe quatre octets. Les deux coïncident ici, et il serait imprudent d'en tirer une règle. Une grille de trois colonnes demanderait une multiplication par trois, donc des additions répétées, puisque RV32I ne multiplie pas.

La méthode

1. Charger l'adresse de base dans un registre avec la, et considérer ce registre comme un point de lecture, jamais comme une valeur.
2. Écrire l'adresse cherchée sous forme de somme avant de coder : base plus indice multiplié par la taille d'un élément. Les trois quantités doivent être nommées, y compris la taille.
3. Convertir l'indice en octets par un décalage à gauche de deux pour des mots, de zéro pour des octets, et par des additions répétées pour toute autre taille.
4. Choisir entre déplacer le pointeur et recalculer l'adresse : le déplacement convient à un parcours complet, le recalcul à un accès isolé ou désordonné.
5. Décider la condition d'arrêt avec le tableau lui-même : un compteur d'éléments pour une suite de mots, l'octet nul pour une chaîne. Un parcours sans condition d'arrêt fiable sort du tableau sans prévenir.
6. Relire les adresses affichées par la figure plutôt que les valeurs obtenues : une valeur plausible lue à la mauvaise adresse est le défaut le plus coûteux du chapitre.

Synthèse

• Une adresse se charge dans un registre avec la, puis la case visée se lit avec lw. Le nom d'une donnée n'est pas une variable, c'est une adresse, et elle ne se lit jamais directement.
• t[i] n'existe pas : l'adresse d'un élément vaut base plus indice multiplié par la taille d'un élément. Pour des mots de quatre octets, la multiplication s'écrit slli de deux bits.
• Un parcours déplace le registre d'adresse de quatre en quatre pour des mots, sans repartir de la base. À la sortie, le registre désigne la case qui suit le dernier élément.
• Une chaîne est un tableau d'octets : la taille d'élément vaut un, le décalage se fait de un en un avec lb, et la fin est marquée par un octet nul. Les mêmes quatre octets lus par lw donnent un nombre, ici 1 145 258 561, sans que rien n'ait changé en mémoire.
• Sortir d'un tableau ne provoque aucune erreur : la lecture rapporte la donnée voisine, ici 777, ou zéro si rien n'a été écrit. C'est toute la différence avec un langage qui vérifie l'indice.
• Une erreur est en revanche signalée sur l'alignement : un mot se lit à une adresse multiple de quatre, et 0x1001 est refusée.
• Une grille se range ligne après ligne, et l'indice de la case vaut ligne multipliée par la largeur, plus la colonne, avant d'être converti en octets.

Les tableaux traités ici ont une adresse connue avant l'exécution. La pile ouvre la zone de mémoire dont les adresses se décident pendant l'exécution, celle qui sert à ranger ce qu'un calcul doit mettre de côté, et qui descend au lieu de monter.