Architecture des ordinateurs

dernière mise à jour : 25-11-2014

Objectifs

  • Architecture de Von Neumann
  • Langage d’assemblage miniature

Architecture matérielle et logicielle

Après avoir écrit des programmes, nous allons décrire comment ces programmes sont effectivement exécutés dans un ordinateur. En informatique, le terme architecture désigne l’organisation des éléments d’un système et les relations entre ces éléments. L’architecture logicielle concerne l’organisation de différents programmes entre eux. L’architecture matérielle concerne l’organisation des différents dispositifs physiques que l’on trouve dans un ordinateur. Dans les deux cas, cette organisation se base sur le principe de décomposition.

Principe de décomposition

Il consiste à effectuer un découpage en couches de complexités croissantes. La Figure 1 présente un tel découpage dans le cas général de machines au sens de “dispositifs capables d’effectuer un ensemble d’opérations élémentaires”. Une opération élémentaire d’un niveau supérieur est ansi décomposée en une suite d’opérations élémentaires du niveau inférieur. Le passage d’une suite d’opérations (“programme”) d’un niveau n au niveau inférieur n-1 consistera en une traduction de chaque opération de la suite du niveau n en la suite correspondante de niveau n-1. Vous avez déjà utilisé le principe de décomposition pour la résolution de problèmes (algorithmique): le niveau inférieur était le langage Python lui-même, le niveau supérieur était relatif au problème traité (exemple: tortue). S’agissant des langages de programmation, ce principe est également utilisé dans la définition de machines virtuelles de haut niveau: la définition d’un jeu d’instructions d’une machine fictive permet de faire abstration des machines réélles et d’assurer simplement la portabilité des programmes (Java Virtual Machine de Sun Microsystems, Common Language Interface de Microsoft .Net, ou encore Python Virtual Machine de CPython). S’agissant de l’architecture des ordinateurs, la Figure 2 présente la décomposition traditionnelle du fonctionnement d’un ordinateur. Le niveau supérieur est ici par exemple le langage Python (et plus généralement les langages de programmation), le niveau le plus bas est celui des circuits électroniques (transistors/portes logiques).

Fig 1 : Principe de décomposition

Fig 2 : Décomposition du fonctionnement d’un ordinateur

  • niveau 5: langages de haut niveau - traduits en niveau 4 par des compilateurs
  • niveau 4: langage d’assemblage - langage symbolique du jeu d’instructions associé au processeur
  • niveau 3: système d’exploitation - la gestion des processus (programmes en cours d’exécution) et des entrées/sorties est dévolue au système d’exploitation, on y accède par des suites d’instructions spécifiques (appels systèmes)
  • niveau 2: langage machine - langage binaire du jeu d’instructions du processeur
  • niveau 1: microprogramme - une instruction machine est elle-même décomposée en une suite de micro-instructions
  • niveau 0: circuits - circuits combinatoires, séquentiels, horloges, ..., pilotés par les micro-instructions

Les 3 niveaux supérieurs de la Figure 2 concerne l’architecture logicielle, les 3 niveaux inférieurs concerne l’architecture matérielle. Notez que matériel et logiciel sont conceptuellement équivalents: toute opération effectuée par logiciel peut l’être directement par matériel et toute instruction exécutée par matériel peut être simulée par logiciel. La frontière entre matériel et logiciel (symbolisée par le trait rouge) est donc arbitraire, et son choix est essentiellement facteur de coût. C’est à cette frontière que l’on définit un processeur par la spécification du jeu d’instructions du processeur, de la représentation binaire de ces instructions et de leur sémantique (“ce qu’elles font”). S’y ajoute également la spécification d’une représentation symbolique des instrucions, les mnémoniques, qui constitueront le langage d’assemblage. Pour exprimer ces spécifications, il est nécessaire de disposer d’un modèle formel de la structure d’un ordinateur et d’un processeur.

Modèle de Von Neumann

Le modèle d’architecture de la plupart des ordinateurs actuels provient d’un travail effectué par John Von Neumann pendant le seconde guerre mondiale. L’objectif était la mise au point de calculateurs pour établir les tables de tirs de pièces d’artillerie. D’un point de vue théorique, Alan Turing proposait à la même époque un modèle de machine (machine de Turing) utilisant un ruban infini contenant des données, capable de traiter ces données et d’en réécrire d’autres sur le ruban. Turing a démontré qu’il existe une machine de Turing universelle capable de simuler toutes les autres. Pour cela on dispose sur le ruban une description de la machine à simuler sous forme d’une table d’action, ainsi que les données d’entrèe de la machine à simuler. La machine de Turing universelle calculera alors le même résultat que la machine à simuler. Ce concept de tables d’action correspond aux instructions machine de nos ordinateurs et le ruban à leur mémoire. Von Neumann a également utilisé ce principe de stocker données et instructions dans la même mémoire, pour concevoir son premier ordinateur. La Figure 3 présente un schéma du modèle de Von Neumann.

Fig 3 : Modèle de Von Neumann

Une machine suivant le modèle de Von Neumann est constituée de:

  • une unité centrale composée d’une unité de calcul (Unité Arithmétique et logique - UAL) et d’une unité de contrôle
  • une mémoire centrale composée d’un ensemble de cellules stockant des nombres binaires représentant les programmes et les données
  • un ensemble de périphériques permettant à la machine d’interagir avec le monde extérieur
  • un canal de communications entre ces trois entités, appelé Bus, communément composé de simples fils

Mémoire centrale

La mémoire centrale de l’ordinateur est constituée d’un ensemble ordonné de \(2^m\) cellules, chaque cellule contenant un mot de \(n\) bits. Ces mots permettent de conserver indifféremment programmes et données. On accède à n’importe laquelle de ces cellules au moyen de son adresse, nombre entier compris dans l’intervalle \([0, 2^m - 1]\). Cet accès est en temps constant quelle que soit la valeur de l’adresse (accès direct). Pour communiquer avec la mémoire, le bus est subdivisé en un bus d’adresse et un bus de données. Il existe deux types d’accès:

  • la lecture transfère sur le bus de données le mot contenu dans la cellule dont l’adresse est située sur le bus d’adresse.
  • l’écriture transfère dans la cellule dont l’adresse est sur le bus d’adresse, le mot contenu sur le bus de données

Fig 4 : Mémoire de 32 mots de 8 bits

Périphériques

Les périphériques, ou organes d’Entrée/Sortie(E/S), permettent à l’ordinateur de communiquer avec l’homme ou d’autres machines, et de mémoriser massivement des données ou des programmes dans des fichiers. Ils se présentent à l’unité centrale le plus souvent sous la forme de plages d’adresses mémoire dans lesquelles sont accessibles les registres de contrôle et d’état des contrôleurs de périphériques. L’unité centrale peut par exemple demander la lecture d’un bloc sur un disque dur en écrivant des valeurs prédeterminées aux adresses mémoires qui correspondent aux registres du contrôleur disque. Le contrôleur disque écrira ensuite chaque octet du bloc demandé directement en mémoire centrale en “volant” des accès mémoire à l’unité centrale (Direct Memory Access). Quand le contrôleur aura terminé la lecture du bloc, il signalera à l’unité centrale que le bloc est lu en utilisant un signal de demande d’interruption: ce mécanisme permet d’interrompre le flot courant d’exécution de l’unité centrale pour qu’elle exécute une séquence d’instructions prédeterminées. Une fois la séquence d’interruption exécutée, l’unité centrale reprend le flot courant d’exécution où il avait été interrompu. Ces séquences d’instructions particulières font partie des systèmes d’exploitation et correspondent aux appels systèmes. Les signaux de demande d’interruption font partie du bus, plus spécifiquement du bus de contrôle.

Fig 5 : Entrées/Sorties, DMA, Interruptions

Unité centrale

L’unité centrale (ou processeur) est responsable de l’exécution du programme de l’ordinateur: elle exécute séquentiellement les instructions stockées en mémoire centrale sous forme de code binaire. Elle regroupe:

  • un ensemble de registres R1, R2,..., Rk: un registre est une mémoire de travail pour le processeur, en général de même largeur qu’un mot mémoire. Leur accès est directement codé dans les instructions machine. Ils sont utilisés comme opérandes et résultats de calculs, ou encore pour stocker des adresses en mémoire. Leur présence est indispensable en raison de la relative lenteur de la mémoire centrale par rapport à la vitesse du processeur.
  • une unité de calcul: elle réalise les opérations arithmétiques (addition, soustraction, multiplication, division) et logiques (et logique, ou logique, non logique, opérations bit-à-bit, décalages/rotations). Les opérations flottantes sont souvent réalisées par une seconde unité de calcul spécialisée. En plus du résultat en lui-même, ces unités calculent également des indicateurs booléens (drapeaux): résultat nul, résultat non nul, retenue, dépassement de capacité. Ces unités ont en général deux opérandes en entrée et fournissent un résultat en sortie. Par construction elles calculent en permanence, fournissant un nouveau résultat presque immédiatemment après la modification d’une des opérandes.
  • un ensemble de bus internes au processeur: ils relient entre eux les registres, les entrées des unités de calcul et leurs sorties. Des interrupteurs permettent de commander le passage des données entre les registres et les bus. L’ensemble registres, UAL et bus internes constituent le chemin de données. Les commandes (interrupteurs, UAL, mémoire, ...) s’appelent des signaux de contrôle.
  • une unité de contrôle: elle contrôle dans le temps les unités de calcul et les interrupteurs pour exécuter effectivement chaque instruction machine. Elle a en charge également l’exécution séquentielle du programme: le programme étant stocké en mémoire centrale, l’unité de contrôle dispose d’un registre spécial CP appelé compteur de programme, qui contient l’adresse de la prochaine instruction à exécuter. L’unité de contrôle répète indéfiniment le cycle instruction donné par l’algorithme suivant:
    • Lire le mot stocké à l’adresse mémoire donnée par le registre CP et le stocker dans un second registre spécial RI, appelé registre instruction
    • incrémenter le compteur de programme CP
    • décoder l’instruction stockée dans RI, aller chercher les opérandes éventuelles en mémoire, faire réaliser le calcul éventuel par l’unité de calcul et stocker le résultat dans un registre ou en mémoire

Cette séquence implique bien une exécution séquentielle du programme car le compteur de programme est incrémenté à chaque cycle instruction. En l’état l’unité de contrôle parcourerait donc l’intégralité de la mémoire centrale, considérant son contenu binaire comme autant d’instructions machine. Nous disposons donc bien d’une implémentation de la première des structures de contrôle des langages de haut niveau, la séquence. Concernant la structure conditionnelle, il suffit de remarquer que ne pas exécuter la branche d’un if (dans le cas où la condition du if est fausse) revient à ajouter une valeur plus grande que 1 au compteur de programme. Concernant l’itération conditionnelle, passer à l’itération suivante revient à retrancher une valeur (supérieure à 1 également) au compteur de programme. Ces deux structures de contrôle s’implémentent donc en modifiant directement la valeur du compteur de programme. Et cette modification doit pouvoir être conditionnelle: l’unité de contrôle dispose de circuits logiques capables d’évaluer des expressions conditionnelles (prédéterminées) formées à partir des valeurs des drapeaux de l’UAL. Cette nouvelle fonctionnalité de l’unité de contrôle sera exprimée au niveau supérieur des langages d’assemblage par la présence d’instructions de branchement et de saut conditionnel.

On peut se demander à ce point si la description de l’unité de contrôle n’est pas récursive en ce sens où elle est donnée sous la forme d’un algorithme, qui implique l’exécution d’un programme. Cette remarque est tout à fait pertinente car l’unité de contrôle peut-être vue comme un processeur dans le processeur: la différence fondamentale est que l’unité de contrôle exécute toujours le même programme, elle n’est pas capable d’exécuter n’importe quel programme. Cependant, et en vertu du principe de décomposition, les unités de contrôle sont implémentées dans les processeurs suivant un modèle similaire à l’unité centrale, que l’on appelle micro-architecture:

  • l’unité de contrôle dispose d’une mémoire contenant des micro-instructions: une micro-instruction contient une valeur prédéterminée pour chaque signal de contrôle.
  • l’unité de contrôle dispose de 2 registres:
    • le compteur de microprogramme contient l’adresse dans la mémoire de microprogramme de la prochaine micro-instruction à exécuter
    • le registre de micro-instruction contient la micro-instruction en cours d’exécution
  • l’unité de contrôle peut lire le contenu du registre instruction RI du processeur: au début de l’exécution du cycle instruction, la valeur contenue dans ce registre déterminera la prochaine micro-instruction à exécuter (il y a une correspondance entre le code opération de l’instruction machine et l’adresse de début de la séquence correspondante dans le microprogramme).
  • l’unité de contrôle dispose d’un circuit incrémenteur pour calculer l’adresse de la prochaine micro-instruction
  • l’unité de contrôle peut être capable de réaliser des sauts dans le microprogramme grâce à une logique simple de contrôle et à la présence d’une addresse de microprogramme dans les micro-instructions.

Fig 6 : Exemple d’unité centrale: le chemin de données (à gauche), l’unité de contrôle (à droite)

La Figure 6 présente un exemple d’unité centrale comportant 4 registres généraux R0, R1, R2, R3, un registre CP, un registre RI, un registre AM pour fournir une adresse mémoire à la mémoire centrale, un registre DM pour contenir la donnée lue ou écrite en mémoire centrale et un registre SP contenant l’adresse du sommet de pile (voir dans la suite l’intérêt d’utiliser une pile dans les langages d’assemblage). Elle comporte par ailleurs 2 bus A et B en entrée de l’UAL, et un bus C en sortie de l’UAL qui contiendra donc les résultats des calculs. Le contenu de la plupart des registres peut être transféré indifféremment sur les bus A et B, et le contenu du bus C peut être transféré dans la plupart des regsitres également. Le figure contient deux exemples de traduction d’instruction machine en suite de microinstructions. Ainsi pour exécuter une instruction machine d’addition R2<-R1+R0, il suffit d’exécuter 2 micro-instructions sur cet exemple de processeur:

  • transférer le contenu de R0 sur le bus A (A<-R0), transférer le contenu de R1 sur le bus B (B<-R1), ordonner à l’UAL d’effectuer une addition (UAL<-add)
  • transférer le contenu du bus C dans le regsitre R2 (R2<-C)

La première micro-instruction positione simultanément les signaux de contrôle R0 sur BusA, R1 sur BusB, et la commande d’addition pour l’UAL. L’unité de contrôle est cadencée de sorte que l’UAL aura effectué son calcul avant le début de la prochaine microinstruction. La seconde micro-instruction peut donc stocker le résultat dans le registre R2 en positionnant le signal BusC dans R2.

Note

Pour aller plus loin, voici deux références de simulateurs illustrant ces principes:

  • Prima est un simulateur en ligne d’un processeur 8 bits avec une unité de contrôle entièrement cablée
_images/Prima.png
  • Johnny est un simulateur d’un processeur 5 bits avec une unité de contrôle microprogrammée. Le microprogramme est modifiable. Johnny est écrit en Free Pascal et est disponible sous Windows.
_images/Johnny.jpg

Langage d’assemblage

Comme évoqué précédemment, le langage d’assemblage se situe à (est) la frontière entre matériel et logiciel. Au dessous se trouvent la couche micro-programmée, semblable sur tous les processeurs, puis les circuits eux-mêmes, et qui concernent essentiellement les électroniciens. Au dessus se trouvent les langages de programmation et les systèmes d’exploitation, qui concernent les développeurs (vous jusqu’à présent). Se situer à cette frontière implique de ce point de vue que n’importe quel programme écrit dans n’importe quel langage de programmation sur n’importe quel système d’exploitation est toujours traduit en un programme écrit en langage d’assemblage. Nous ne ferons plus la différence entre langage d’assemblage et langage binaire puisqu’il y a en fait une bijection entre ces deux langages, le second étant un codage arbitraire du premier. L’objectif est dorénavant de comprendre comment cette traduction peut être réalisée. Nous présentons dans un premier temps les caractéristiques des langages d’assemblage ainsi que les instructions machine couramment utilisées sur les processeurs actuels. Nous décrirons ensuite comment traduire les structures des langages de haut niveau à l’aide de ces instructions.

Format des instructions

Pour rappel, les instructions du langage d’assemblage sont représentées par des mnémoniques: une mnémonique est une abbréviation du mot représentant l’opération correspondant à l’instruction (add pour une addition par exemple). Les registres sont également représentés par des symboles, en général leurs noms (R0, R1, R2 dans la suite). Les valeurs littérales sont représentées directement en décimal (10d) ou encore en héxadécimal (10h ou 0x10). L’utilisation des crochets [] signifie “le contenu de”, ainsi [R1] désigne la valeur contenue dans la cellule mémoire dont l’adresse est dans le registre R1 et [1000h] la valeur contenue dans la cellule mémoire d’adresse 1000h.

Le format des instructions décrit l’ensemble des bits des instructions machine telles qu’ils apparaissent en mémoire. Cet ensemble est communément divisé en différents champs de longueurs prédéterminés:

Format d’une instruction avec 2 champs addresse   exemple x86: add ax, [1000h] (check)
code opération modes d’adressage adresse 1 adresse 2   0000 0011 000 00100 0001 0000 0000 0000
  • le code opération spécifie l’opération à effectuer. Il y a une bijection entre ce code et la mnémonique. C’est également ce code qui est utilisé par la micro-architecture pour déterminer l’adresse dans le microprogramme du début de la suite de micro-instructions à exécuter pour réaliser l’instruction machine.
  • le mode d’adressage spécifie le moyen d’accéder aux opérandes de l’instruction à partir des informations contenues dans les champs adresses. Dans l’exemple ci-dessus, ce champ spécifie que la première opérande est un registre et la deuxième opérande une adresse absolue (l’adresse en mémoire centrale de l’opérande est présente dans l’instruction, l’opérande est en mémoire).
  • un champ adresse spécifie l’adresse d’une opérande. La valeur contenue dans le champ adresse peut être
    • une valeur immédiate (l’opérande est présente directement dans l’instruction): mov R1, 10h
    • un numéro de registre: mov R1, R2
    • une adresse mémoire: mov R1, [10h]

La valeur de l’opérande dépend du mode d’addressage. Le nombre de champs adresse dépend de l’organisation des registres dans le processeur et du chemin de données.

  • le processeur dispose de registres généraux. On trouvera dans ce cas des instructions avec
  • 3 champs adresses: destination, source1, source2. add R1, R2, R3 qui calcule R1 <- R2 + R3
  • 2 champs adresses: une des opérandes reçoit le résultat. add R1, R2 qui calcule R1 <- R1 + R2
  • le processeur utilise un accumulateur. L’accumulateur Acc est un registre spécial qui est opérande et destination de toutes les opérations arithmétiques et logiques. Deux instructions spécifiques sont ajoutées pour accéder à l’accumulateur: load X pour charger l’accumulateur avec une donnée X et store X pour sauver le contenu de l’acumulateur en mémoire ou dans un autre registre. Toutes les instructions pour les opérations diadiques n’auront qu’un seul champ adresse, celui de la seconde opérande.

    • 1 champ adresse: source2. add R1 qui calcule Acc <- Acc + R1
  • le processeur utilise une pile. Une pile est une structure de données en mémoire centrale dans laquelle les données sont placées “les unes sur les autres”: la dernière donnée entrant dans la pile sera la première à en sortir. Un registre spécial SP contient l’adresse du sommet de la pile. Deux opérations sont définies sur les structures de pile:

    • push X: empiler une donnée X, c’est à dire la placer au sommet de la pile et faire avancer le registre SP vers la celulle mémoire suivante
    • pop X: dépiler vers une cellule mémoire ou un registre X, c’est à dire placer dans X la donnée au sommet de la pile désigné par SP et faire avancer le registre SP vers la celulle mémoire précédente.

    Dans ce cas, toutes les opérations prennent leurs opérandes en sommet de pile, et stockent le résultat en sommet de pile. De plus les opérandes sont automatiquement dépilées.

    • 0 champ adresse. add qui effectue le calcul [SP-2] <- [SP-2] + [SP-1]; SP <- SP - 1 (dans le cas d’une pile qui croît vers les adresses hautes)

Traduction d’une instruction d’affectation avec évaluation d’une expression

Soit à traduire l’instruction d’affectation Python x=(a+b)*(c+d), où a, b, c et d sont des variables préalablemant définies. Le langage d’assemblage dispose des instructions add pour l’addition, mul pour la multiplication, mov pour le transfert de registre à registre ou de registre à mémoire, et des instructions load et store ou push et pop suivant le cas. On notera respectivement A, B, C et D les adresses des variables a, b, c et d (ces adresses doivent être déteminées par le programmeur). Ecrivons les programmes correspondants aux différentes situations énumérées ci-dessus.

instructions à 3 adresses instructions à 2 adresses accumulateur (1 adresse) Pile (0 adresse)
add R1, A, B
add R2, C, D
mul X, R1, R2
mov R1, A
add R1, B
mov R2, C
add R2, D
mul R1, R2
mov X, R1
load A
add B
store T
load C
add D
mul T
store X

T: temporaire

push A
push B
add
push C
push D
add
mul
pop X

Les instructions usuelles

Voici une liste des instructions que l’on rencontre habituellement dans les langages d’assemblage. Elles sont regroupées par thématique. Les mnémoniques présentées sont celles couramment utilsées (pour un processeur réél, voir un datasheet). Nous nous placons dans le cas d’un langage d’assemblage à 2 champs d’adresse. Notez que la plupart des processeurs exige souvent qu’au moins une des opérandes soit un registre.

  • Instructions de transfert de données

    • mov R1, R2: source (R2) vers destination (R1);
    • load R1, var: mémoire (var) vers registre (R1);
    • store var, R1: registre (R1) vers mémoire (var);
    • xchg R1, R2: échange des contenus de R1 et R2;
    • clear R1: mise à zéro des bits de R1;
    • set R1: mise à un des bits de R1;
    • push R1: placer R1 en sommet de pile (Stack Pointer);
    • pop R1: placer le sommet de pile dans R1;
  • Instructions arithmétiques:

    • add R1, R2: addition (R1 <- R1 + R2);
    • sub R1, R2: soustraction (R1 <- R1 - R2);
    • mul R1, R2: multiplication (R1 <- R1 * R2);
    • div R1, R2: division entière (R1 -> R1 / R2);
    • neg R1: complément à 2 (R1 <- Ca2(R1));
    • inc R1: incrémentation (R1 <- R1 + 1);
    • dec R1: décrémentation (R1 <- R1 - 1);
  • Instructions logiques:

    • and R1, R2: et bit à bit (R1 <- R1 & R2);
    • or R1, R2: ou bit à bit (R1 <- R1 | R2);
    • xor R1, R2: ou exclusif bit à bit (R1 <- R1 ^ R2);
    • not R1: complément à 1 (R1 <- Ca1(R1));
  • Instructions de décalages: les décalages sont utilisés pour réaliser rapidement des multiplications et des divisions par puissance de 2. Ils modifient le bit de retenue.

    • décalages logiques (shift): à utiliser avec des nombres non signés;
      • shl R1: décalage à gauche;
      • shr R1: décalage à droite ;
    • décalages arithmétiques (arithmetic shift): à utiliser avec des nombres signés;
      • ashl R1: décalage à gauche;
      • ashr R1: décalage à droite
    • rotations: utilisée en cryptographie ?
      • rol R1: rotation gauche;
      • ror R1: rotation droite;
  • Instructions de comparaison: les instructions de comparaison effectuent un calcul prédeterminé en oubliant le résultat du calcul. Leurs opérandes ne sont donc jamais modifiés. Seuls les drapeaux sont modifiés.

    • cmp R1, R2: comparaison par soustraction (R1 - R2) avec modification des drapeaux (C, Z, N, V). R1 et R2 ne sont pas modifiés.
    • test R1, R2: comparaison par et bit à bit (R1 & R2) avec modification des drapeaux (C, Z, N, V); R1 et R2 ne sont pas modifiés.
Les instructions de comparaison s’utilisent avec les instructions de saut conditionnel et sont utiles à la traduction des structures conditionnelle et itérative.

Les instructions de saut

Les instructions de saut (ou de branchement) sont les instructions qui modifient la valeur du compteur de programme CP. Nous avons vu que le compteur de programme représente l’adresse de la prochaine instruction à exécuter et est par défaut incrémenté par l’unité de contrôle à chaque cycle instruction. En modifiant le compteur de programme, une instruction de saut va ainsi modifier l’adresse de la prochaine instruction à exécuter. Il existe deux moyens pour spécifier l’adresse de la prochaine instruction à exécuter, que nous appelerons adresse de saut.

  • l’adresse de saut est une adresse absolue. Sa valeur est donnée dans le champ adresse de l’instruction, et cette valeur est recopiée dans le registre CP par l’instruction de saut.
  • l’adresse de saut est une adresse relative. Sa valeur représente un déplacement par rapport à la valeur contenue dans le compteur de programme. Elle est donnée dans le champ adresse de l’instruction sous la forme d’un nombre signé. Ce nombre est ajouté au compteur de programme par l’instruction de saut. Lintéret d’un adressage relatif est que le programme n’est pas dépendant de l’adresse où il est chargé en mémoire.

De manière pratique les adresses de saut ne se calculent pas à la main lorsque l’on dispose d’un traducteur en langage binaire (assembleur). Le programmeur utilise des étiquettes. Une étiquette est un identifiant placé devant une instruction quelconque du programme. Un identifiant peut par la suite etre utilisé comme adresse de saut dans les instructions de saut. Nous noterons dans la suite adr une adresse de saut.

Il existe deux types d’instructions de saut.

  • l’instruction de saut inconditionnel modifie toujours le compteur de programme avec l’adresse de saut. Nous utiliserons la mnémonique branch adr pour l’instruction de saut inconditionnel.

  • les instructions de saut conditionnel modifient le compteur de programme seulement si l’évaluation d’une fonction booléenne des drapeaux renvoie vraie. Il y aura autant d’instructions de saut conditionnel qu’il y a de fonctions booléennes disponibles dans le langage. Le tableau ci-dessous présente les principales fonctions utilisées. Pour rappel, on note Z le drapeau ZERO (résultat nul), N le drapeau NEGATIVE (résultat négatif), C le drapeau CARRY (retenue) et V le drapeau OVERFLOW (dépassement de capacité). Les drapeaux sont en général modifiés en utilisant une instruction de comparaison juste avant l’instruction de saut.

    • fonction conditionnelle sur un drapeau:

           
      jz Jump Zero Z
      jnz Jump Non Zero not(Z)
      jc Jump Carry C
      jnc Jump Not Carry not(C)
           
      jneg Jump Negative N
      jpos Jump Positive not(N)
      jv Jump Overflow V
      jnv Jump Not Overflow not(v)
    • fonction conditionnelle concernant les nombre non signés

           
      ja Jump Above not(C or Z)
      jae Jump Above Equal not(C)
      jeq Jump Equal Z
           
      jb Jump Below C
      jbe Jump Below Equal C or Z
      jneq Jump Not Equal not(Z)
    • fonction conditionnelle concernant les nombre signés

           
      jg Jump Greater not(Z or (N xor V))
      jge Jump Greater Equal not(N xor V)
      jeq Jump Equal Z
           
      jl Jump Lesser (N xor V)
      jle Jump Lesser Equal Z or (N xor V))
      jneq Jump Not Equal not(Z)

Traduction d’une structure conditionnelle

Structure conditionnelle en Python Traduction en langage d’assemblage
if (exp):

    bloc_if

else:
    bloc_else
       ;évaluer exp dans R1
       cmp R1, 0
       je l_else
       ;traduire bloc_if
       branch l_fin
l_else:
       ;traduire bloc_else
l_fin:

Exercice: Traduire en langage d’assemblage une structure conditionnelle Python

if (exp1):
    bloc_if1
elif (exp2):
    bloc_if2
elif (exp3):
    bloc_if3
else:
    bloc_else

Traduction d’une itération conditionnelle

Itération conditionnelle en Python Traduction en langage d’assemblage
while (exp):

    bloc_itere
l_debut:
       ;évaluer exp dans R1
       cmp R1, 0
       je l_fin
       ;traduire bloc_itere
       branch l_debut
l_fin:

Exercice: Traduire en langage d’assemblage une itération bornée Python

for i in range(n):
    bloc_itere

Vous utiliserez le registre R1 pour l’indice i.

Modes d’adressage (facultatif)

Pour rappel, un mode d’adressage spécifie la façon avec laquelle le processeur interprète les informations des champs adresse d’une instruction pour déterminer les adresses des opérandes. La Figure 7 présente les différents modes d’adressage couramment utilisés dans les processeurs actuels.

Fig 7 : Modes d’adressage couramment utilisés

Appels de fonction(facultatif)

La Figure 8 présente un exemple de programme principal utilisant deux fonctions. Elle permet de visualiser les caractéristiques des appels de fonction dans les langages de haut niveau:

  • il y a imbrication des appels: le programme principal appelle la fonction f1, qui appelle elle-même la fonction f2. En règle générale, l’imbrication des appels de fonction peut être quelconque. La traduction d’un appel de fonction en langage d’assemblage doit être correcte quelle que soit l’imbrication des appels.
  • il y a multiplicité des appels: la fonction f1 appelle deux fois (successivement) la fonction f2.
  • il y a récursivité des appels: la fonction f2 s’appelle elle-même.

Les langages d’assemblage proposent deux instructions spécifiques pour les appels de fonctions:

  • call adr: l’instruction d’appel permet d’appeler une fonction dont la première instruction est à l’adresse adr.
    • l’adresse de l’instruction suivant le call (contenue dans le compteur de programme ) est sauvegardée en mémoire. Cette adresse s’appelle l’adresse de retour;
    • le contrôle est donné à la fonction en modifiant directement le compteur de programme avec la valeur adr contenue dans l’instruction;
  • ret: l’instruction de retour permet de redonner le contrôle à une fonction appelante.
    • l’adresse de retour est récupérée depuis la mémoire;
    • le contrôle est rendu à la fonction appelante en modifiant le compteur de programme avec cette adresse;
  • Comment sauvegarder l’adresse de retour?
    • dans un registre spécial: il n’y aura pas d’imbrication possible.
    • dans une cellule mémoire située au début (ou à la fin) des fonctions: il n’y aura pas de récursivité possible.
    • dans une pile d’adresses de retour située en mémoire: imbrication et récusivité sont possibles. Ainsi l’instruction call empile l’adresse de retour (qui est la valeur courante du compteur de programme) avant de donner le contrôle à la fonction appelée, et l’instruction ret dépile le sommet de pile directement dans le compteur de programme. C’est la solution utilisée par tous les processeurs classiques, étant tous dotés d’un registre pointeur de pile SP.

La Figure 8 présente l’évolution de la pile avec les adresses de retour pendant l’exécution du programme principal. Dans cette figure, le premier appel à la fonction f2 génère deux appels récursifs (en 3 et 4), le deuxième appel à f2 n’en génère qu’un (en 9). A chaque appel de fonctions l’adresse de l’instruction suivante (notée sous l’appel lui-même dans la figure) est placée en sommet de pile. Notez que cette adresse est déjà calculée (voir le cycle instruction). A chaque retour de fonction le sommet de pile est placé dans le compteur de programme. Le contrôle est ainsi rendu à la fonction appelante (à supposer que la fonction appelée ne modifie pas de manière inconsidérée le contenu de la pile ou le pointeur de pile).

Fig 8 : Appel de fonctions: imbrication, multiplicité, récursivité, contenu de la pile avec les adresses de retour, compteur de programme

Passage de paramètres, valeur de retour, variables locales, sauvegarde des registres (facultatif)

La traduction d’une fonction en langage d’assemblage implique l’accès à ses paramètres, à sa valeur de retour et à ses variables locales. Les paramètres et la valeur de retour sont également utilisés par la fonction appelante. De plus, les registres étant en nombre limité, une fonction doit éviter de modifier ceux qui sont utilisés par les autres fonctions. Cet ensemble de contraintes implique de définir un mécanisme général pour la traduction des fonctions. Ce mécanisme est utilisé par les compilateurs et les interpréteurs, mais aussi lorsque l’on écrit un programme directement en langage d’assemblage.

  • le passage de paramètres par registres consiste à utiliser un ensemble de registres qui contiendront l’ensemble des paramètres, avec éventuellement la valeur de retour. Les fonctions appelantes doivent connaître exactement cet ensemble de registres. Elles doivent par ailleurs sauvegarder ces registres avant l’appel à la fonction si elles les utilisent. Cette méthode est en général limitée au cas de certains appels systèmes.
  • le passage de paramètres par la pile consiste à utiliser la pile pour y placer les paramètres, et souvent également la valeur de retour. Les fonctions appelantes doivent connaître l’ordre d’empilement des paramètres. L’empilement des paramètres se fera avant l’appel à la fonction lui-même . La fonction appelée aura à calculer le déplacement par rapport à son sommet de pile, de ses paramètres et de sa valeur de retour. Ce calcul dépend de l’ordre d’empilement choisi.
  • les variables locales aux fonctions peuvent être soit directement placées dans des registres, soit placées dans la pile si elles sont trop volumineuses. A nouveau la fonction aura à calculer le déplacement par rapport à son sommet de pile, de ses variables locales.
  • la sauvegarde des registres se fait en utilisant la pile pour permettre la récursivité.
  • les options présentées ici sont parfois mixées (1er paramètre dans R0, les autres dans la pile, valeur de retour dans Acc, par exemple) afin d’optimiser la vitesse d’exécution dans certaines situations, l’accès à un registre étant beaucoup plus rapide qu’un accès dans la pile. Cependant, dans le cas général, seule la pile est utilisée.

La Figure 9 , dans sa partie gauche, présente un exemple de traduction d’une fonction d’addition addition(n1,n2) de deux entiers et utilisant une variable locale s. Le contenu de la pile est schématisé afin de calculer les déplacements dans la pile pour accéder aux paramètres, à la variable locale et à la valeur de retour de la fonction. L’ordre d’empilement choisi est valeur de retour de l’appel de fonction, 1er paramètre (n1), 2ème paramètre (n2). C’est la fonction appelante qui empile ces valeurs, en plus de l’adresse de retour qui est empilée par l’instruction call. La fonction addition utilise par ailleurs la pile pour sa variable locale s, et pour sauvegarder le contenu du registre R1 nécessaire à son calcul. Le schéma représente l’état de la pile après la sauvegarde des registres, c’est à dire pendant l’exécution de la fonction addition. Il permet de calculer le déplacement par rapport à SP des paramètres (n1 est à l’adresse SP-5, n2 est à l’adresse SP-4), des variables locales (s est à l’adresse SP-2) et de la valeur de retour de la fonction addition (elle est à l’adresse SP-6). L’appel à cette fonction depuis le programme principal est également traduit. Notez que dans cet exemple la pile croît vers les adresses hautes.

Fig 9 : Traduction d’une fonction, et d’un appel à cette fonction (à gauche). Variabilité des déplacements dans la pile (à droite).

La Figure 9 , dans sa partie droite, présente un exemple pour lequel la valeur de ces déplacements n’est pas constante pendant l’exécution (et surtout l’écriture) d’une fonction. Cela se produit lorsque la pile est modifiée à l’intérieur de la fonction. La fonction doubler présentée ici modifie en effet la pile pour réaliser un appel à la fonction addition. Elle modifie donc la pile pour réaliser cet appel de fonction ce qui a pour conséquence:

  • les déplacements des paramètres, des variables locales et de la valeur de retour de la fonction doubler ne sont pas constants. Ainsi le paramètre x, utilisé dans l’appel de la fonction addition(x, x), doit être empilé deux fois: au premier empilement l’adresse du paramètre x est SP-4, au deuxième empilement, son adresse est SP-5.
  • un même déplacement dans une fonction ne désigne pas toujours la même donnée. Dans cet exemple, le déplacement 4 dans la fonction doubler désigne tantôt le paramètre x de la fonction au moment où est construit l’appel à addition, tantôt la valeur de retour de la fonction au moment où on modifie cette valeur.

Cette variabilité des déplacements à l’intérieur d’une fonction rend complexe l’écriture et la mise au point de programmes d’assemblage par un humain. Une solution consiste à utiliser un registre contenant une photographie de la valeur du pointeur de pile au début de l’exécution de chaque fonction, registre que l’on appelle le pointeur de cadre.

Utilisation d’un pointeur de cadres (Frame Pointer) pour la traduction des fonctions

Le pointeur de cadres FP (Frame Pointer) désigne un registre utilisé pour sauvegarder la valeur du pointeur de pile SP au début de l’exécution des fonctions. Son utilité est de rendre constantes, à l’intérieur d’une fonction, les valeurs de déplacement des paramètres, des variables locales et de la valeur de retour de la fonction. La sauvegarde du pointeur de pile SP dans FP est faite au tout début des fonctions, avant la réservation des variables locales dans la pile, et avant la sauvegarde des autres registres dans la pile. Notez que FP doit être lui-même sauvegardé dans la pile avant d’être modifié. Chaque fonction débutera ainsi par un empilement du pointeur de cadre FP de la fonction appelante pour en sauvegarder la valeur, suivi d’une copie du pointeur de pile SP dans le pointeur de cadre FP. Puis la réservation de l’espace utilisé par les variables locales se traduira par une simple incrémentation du pointeur de pile. De cette manière, les paramètres seront situés au dessous du pointeur de cadre FP à un déplacement constant. De même, les variables locales seront situées au dessus du pointeur de cadre FP à un déplacement constant. La fonction, et donc le programmeur, peut utiliser la pile à sa guise à partir de ce moment. Il faut cependant veiller à la laisser dans le même état après traduction du corps de la fonction. A la fin de la fonction, l’espace utilisé par les variables locales est libéré en décrémentant le pointeur de pile, puis la valeur du pointeur de cadre FP est restauré par dépilement. La Figure 10 présente le contenu de la pile dans le cas d’une fonction ayant n paramètres et utilisant k variables locales. La valeur des déplacements y est représenté dans le cas d’une pile qui croît vers les adresses hautes, et dans le cas d’une pile qui croît vers les adresses basses.

Fig 10 : Contenu de la pile et pointeur de cadre lors d’un appel de fonction. A gauche la pile croît vers les adresses hautes, à droite la pile croît vers les adresses basses.

Ce mécanisme peut être utilisé de manière systématique pour la traduction des fonctions et des appels de fonctions. Tous les compilateurs utilisent ce mécanisme. Seul l’ordre d’empilement des paramètres, des variables locales et de la valeur de retour varient d’un compilateur à l’autre. Il est recommandé d’utiliser le même mécanisme lorque l’on écrit des programmes directement en langage d’assemblage. L’appel à des fonctions de librairies exige d’ailleurs dans ce cas de connaître l’ordre d’empilement utilisé par le compilateur. L’encadré ci-dessous présente la traduction systématique d’une fonction et d’un appel de fonction avec un ordre d’empilement déterminé.

Traduction d’une fonction et d’un appel de fonction

L’ordre d’empilement des paramètres est de gauche à droite (pf1, pf2, ..., pfn ci-dessous), la valeur de retour des fonctions étant placée avant les paramètres. Les variables locales sont allouées par ordre d’apparition (l1, l2,..., lk ci-dessous). La pile croît dans le sens des adresses basses.

Fontion en Python (défintion/appel) Traduction en langage d’assemblage Commentaires
def foo(pf1, pf2,...,pfn):
    l1, l2,..., lk=...
    bloc_fonction











r=foo(pe1, pe2,...,pen)
foo:
    push FP
    mov FP, SP
    sub SP, k
    ;traduire bloc_fonction
    ; avec adresse paramètres
    ;   pfi = FP + 2 + (n - i + 1)
    ; avec adresse variables locales
    ;   lj = FP - j - 1
    ; avec adresse valeur retour
    ;      = FP + 2 + n  + 1
    .........
    add SP, k
    pop FP
    ret

sub SP, 1
push pe1
push pe2
push ...
push pen
call foo
add SP, n
pop r
fonction foo
  sauvegarde FP
  FP <- SP
  variables locales

  compter sauvegarde FP
  et adresse retour
  FP pointe la 1ere
   variable locale



  variables locales
  restauration FP
  retour foo

valeur retour foo
empiler parametres



appel foo
dépiler paramètres
dépiler valeur retour

La Figure 11 présente la traduction des fonctions utilisées précédemment en Figure 9. On constate dans la traduction de la fonction doubler que le déplacement du paramètre x est bien constant par rapport au pointeur de cadre FP. Dans la pratique, si vous avez à écrire un programme en langage d’assemblage, il est recommandé de faire les schémas correspondant au cadre de chaque fonction comme présenté dans la figure. De même un tel schéma aidera à la compréhension d’un code généré par un compilateur.

Fig 11 : Exemple de traduction de fonctions avec utilisation du pointeur de cadre. Les déplacements sont constants par rapport au pointeur de cadre.