Variables et la pile

En réalité l'espace pour les variables n'est pas alloué statiquement mais (...) sur une pile.

La pile correspond aux règles selon lesquelles une variable commence à être accessible au début d'un bloc/appel d'une fonction et reste accessible à la fin; (si les activations des blocs et fonctions sont imbriquées)

Ce régime permet la récursion, ...

Récursion (et variables plus locales avec un même identificateur) rendent une variable provisoirement inaccessible; mais elle doit garder sa valeur

Un paramètre peut être traité comme une variable (qui reçoit une initialisation de l'extérieur

Selon le lagage d'autres types d'informations seront aussi stockés dans la pile

Accès à des variables (C)

Pour accéder à une variable, il faut savoir où est le bloc (section de la pile) qui la contient et quelle est sa position dans ce bloc.

Dans des langages comme C il n'y a que deux blocs accessibles à un moment donné;
le bloc de l'appel le plus récent d'une fonction et celui des variables statiques

(A notre que l'imbrication de blocs de code ne produit pas de nouveau bloc de pile; la taille du bloc de pile peut changer avec le temps)

Donc probablement 2 pointeurs (adresses en registres) vers ces deux blocs

La position dans le bloc peut être calculée par le compilateur
(complication mineure dans le cas de langages permettant des variables locales de taille inconnue au compilateur); le ``décalage'' d'une variable.

Déclarations et tables de symbôles

Le compilateur doit être capable de savoir quelles sont les variables possédant des déclarations valables à une position dans le programme

Pour chaque bloc il est facile de construire une table de symboles contenant les variables déclarées dans le bloc

Soit on ajoute ces variables à une table globale au début du traitement du bloc (et on les enlève à la fin)
soit on garde une table pour chaque bloc et les tables sont reliées par des pointeurs de chaque bloc à son père

Décalages et types

La table de symbôles peut contenir aussi le décalage et le type de chaque variable déclarée

le type permet de vérifier que le programme respecte les règles de typage

le décalage permet de générer le code d'accès à la variable.

Paramètres et types de fonctions

Quand un identificateur est celui d'une fonction déclarée, l'information dans la table inclura

Cette idée simpliste ne permet pas de traiter des paramètres et/ou variables qui sont des (pointeurs vers) des fonctions...

Appels et retours de fonctions (simples)

Appel: Il faut

Nous avons vu que PUSHJ 255, Etiquette sauvegarde les registres locaux, stocke l'adresse retour en rJ et saute à l'étiquette; POP 0,0 récupère les registres et rentre à rJ.
Si cette fonction peut en appeler une autre, il faudra stocker et récupèrer rJ par (par exemple) PUT rJ R et GET R rJ

Mais cela ne suffit pas si cette procédure en a appelé une autre; Il faut stocker cette adresse dans une location différente pour chaque appel (même plusieurs appels récursifs de la même procédure); on a donc une chaîne d'adresses qui permet de rentrer d'une chaîne d'appels.

(Si le registre R était un registre local en mmix, sa valeur serait automatiquement sauvegardé par le mécanisme PUSHJ ... POP mais ça ne permet forcément pas la gestion de la pile nécessaire pour traiter des exceptions)

Résultat: Il faut qu'une fonction laisse son résultat dans une location connue (pile ou registre); le code qui avait appelé la fonction doit récupérer ce résultat (comme la valeur d'une expression); (avant l'exécution d'autre code qui pourrait utiliser la même location).

Plus concrètement

Initialisation et accès: dans le cas simple (comme C), il suffit d'avoir un pointeur à la fin de la pile (au dernier bloc de la pile), de préférence stocké dans un registre: l'accès à une variable locale est par LD T, pile, D;
(un bloc de la pile pour une fonction, même s'il y a des variables locales à des {...} imbriqués)
les paramètres sont calculés et leurs valeurs stockées dans les adresses après
$pile + espace pour les variables locales et $pile est incrémenté; dans la procédure le code pour accéder à un paramètre pourrait être LD T, pile, D où D est le décalage entre le début du bloc de la pile et la position du paramètre; dans le code pour accéder à une variable locale le décalage doit prendre en compte l'espace occupé par les paramètres (et résultat? et lien dynamique ..).

à la fin de l'appel $pile est récupéré; probablement en utilisant un pointeur au bloc précédent de la pile: la chaîne dynamique)

Paramètres ref: on stocke l'adresse au lieu de la valeur et le code de la procédure ajoute un niveau d'indirection.

ACCES A DES VARIABLES
NI LOCALES NI STATIQUES
Les langages qui le permettent: algol60 et ses descendants (Pascal, modula-2,... Ada, ...): l'imbrication de blocs ne donne pas de problème; c'est l'imbrication de déclarations de fonctions.

Référence par niveau textuel: le compilateur (les attributs) peut calculer, pour chaque variable, son niveau lexical et son décalage; ces deux suffisent à l'exécution pour déterminer la variable; il faut trouver le moyen d'accéder à cette variable

L'adresseur: un tableau avec un élément pour chaque niveau lexical utilisé dans le programme (c'est-à-dire le niveau maximum d'imbrication de déclarations de fonctions); cet élément est un pointeur à la section de la pile active pour une fonction de ce niveau: donc le code pour accéder à une variable:

LD T, adr, I
LD T, T, J

(Mais on évite de répéter les LD T,$adr, I, au moins pour les niveaux I utilisés souvent, en choisissant un registre différent)

TROUVER LA BONNE ACTIVATION
Récursion: Il peut exister plusieurs activations de procédures du même niveau lexical; de la même procédure (récursion normale) ou différentes procédures (récursion mutuelle);
presque toujours c'est l'activation la plus récente qu'il faut utiliser

Pas toujours l'activation la plus récente!
(une fonction peut être un paramètre): après avoir été passée entre plusieurs procédures, elle est enfin appelée; quelles sont les variables accessibles pendant l'appel? réponse normale: les variables qui étaient accessibles là où le paramètre a été passé (la première fois).

La chaîne statique: chaque invocation dans la pile contient un pointeur à l'invocation au niveau lexical inférieur (par 1) dont il dépend; ce pointeur doit être partie de l'information passée pour un paramètre qui est une procédure.

A noter que dans algol-60, la méthode par défaut de transmission de paramètres équivalait à transmettre une fonction qui était exécutée chaque fois qu'il fallait avoir la valeur du paramètre (!)

RECONSTRUCTION DE L'ADRESSEUR
Suivre la chaîne statique pour trouver la bonne activation à chaque niveau lexical.

Appel d'une procédure: pour construire l'adresseur.

Retour d'une procédure: pour réparer l'adresseur éventuellement modifié par la procédure appelée.

A la fin normale d'un appel, la fonction appelée peut réparer elle même la modification qu'elle avait effectuée à l'adresseur; mais ça ne suffit pas quand il y a des goto avec destination non-locale.

Principe à appliquer (autant que possible): les programmes qui n'utilisent pas des facilités coûteuses ne les paient pas.




File translated from TEX by TTH, version 3.05.
On 29 Mar 2005, 12:02.