Code Intermédiaire
Génération de Code
Linéarisation
Canonisation. |
|
| Difficulté de la génération de code |
|
| · | Gestion des environnements: conventions d'appel des fonctions, sauvegarde
en pile, etc.
|
| · | Gestion des registres.
|
| · | Mécanisation des optimisations.
|
Découpage en petites étapes
Approche systématique:
robuste, modulable, réutilisable.
Approche globale:
| · |
| La phase (1) introduit des sources d'inefficacités |
|
| · |
| éliminées par la phase (2). |
|
| Pourquoi un code intermédiaire? |
|
Partage du travail
| · | Entre plusieurs langages, et plusieurs machines
|
|
|
|
|
ü
ï
ý
ï
þ |
|
|
|
ì
ï
í
ï
î |
| MIPS |
| xx86 |
| ... |
| Sparc |
| Byte-code |
|
|
|
| · | Entre les différentes constructions d'une même langage ou d'une même machine
| · | La syntaxe abstraite comporte trop de constructions voisines
| | · | Le code assembleur comporte trop d'instructions voisines
|
| La représentation intermédiaire est plus concise. |
|
| Le principe du code intermédiaire |
|
Le but du code intermédiaire est de passer d'une structure arborescente à
une (bonne) structure linéaire et de préparer la sélection
d'instructions.
Les détails dépendant de l'architecture sont relégués à une phase
ultérieure de sélection d'instructions.
Quelques caractéristiques du code intermédiaire:
| · | Les branchements sont explicites.
|
| · | Code arborescent (expressions) ou linéaire (instructions)
|
| · | Utilise une infinité de registres (temporaires),
dont l'utilisation est privilégiée (réversible) et le coût négligé.
|
| · | L'adressage en mémoire est une forme séparée qui n'est retenue que lorsque
c'est indispensable (irréversible).
|
| · | L'appel de fonction est implicite, et sera résolu dans une phase ultérieure.
(Différentes formes dans différents langages d'assemblage)
|
| Les expressions (Code.exp) |
|
type exp =
Const of int (* Entiers et Booléens *)
| Name of label (* Globaux *)
| Temp of temp (* Lecture d'un temporaire *)
| Mem of exp (* Lecture mémoire *)
| Bin of binop * exp * exp (* Opération binaire *)
| Call of frame * exp list (* Appel de fonction *) |
|
Pour certains langages, il est utile d'ajouter un noeud
pour représenter une séquence retournant un résultat (comme e1; e2 en
ML). Ce n'est pas nécessaire pour Pseudo-Pascal.
| Les instructions (Code.stm) |
|
and stm =
| Label of label (* Étiquette *)
| Move_temp of temp * exp (* Écriture de exp dans un
temporaire *)
| Move_mem of exp * exp (* Écriture en mémoire à
une adresse calculée *)
| Seq of stm list (* Séquence d'instructions *)
| Exp of exp (* Expression avec effet *)
| Jump of label
| Cjump of relop * exp * exp * label * label
and relop = Req | Rne | Rle | Rge | Rlt | Rgt
and binop = Plus | Minus | ... | Eq | Ne |
|
| Utilisation des temporaires |
|
Les étiquettes et les temporaires sont créés à la demande.
Par sécurité on les manipulera de façon abstraite.
Penser
temporaire = registre virtuel
Les temporaires seront associés à des registres réels, et
éventuellement à des emplacements en pile pour les sauvegarder.
La génération de code crée beaucoup de temporaires, mais de durée de vie
très courte. Les temporaires avec une durée de vie très courte n'auront pas
besoin d'être sauvegardés en pile.
|
Plus on en crée, plus leur durée de vie sera courte et plus facilement ils
pourront partager le même registre: ne jamais chercher à réutiliser le même
temporaire, au contraire utiliser des temporaires différents dès que
possible! |
Première partie
Génération de code. |
|
On traduit récursivement expressions et instructions:
[[ _ ]]e :
Pp.expression ® Code.exp
[[ _ ]]s :
Pp.instruction ® Code.stm
de façon la plus simple possible.
[[Int n]]e = Const n
[[Bool true]]e = Const 1
[[Bool false]]e = Const 0
|
|
| [[Bin (op, e1, e2)]]e |
= |
Bin (op, [[e1]]e, [[e2]]e) |
| [[ Sequence (s1; ...; sn)]]s |
= |
Seq ([[ s1]]s; ...; [[ sn]]s) |
| Opérations sur les tableaux (alloués dans le tas): |
| [[Geti (e1, e2)]]e |
= |
Mem (Bin (Plus ,
[[e1]]e, [[e2]]e)) |
| [[ Seti (e1, e2, e3)]]s |
= |
Move_mem (Bin (Plus ,
[[e1]]e, [[e2]]e), [[e3]]e) |
|
| Expressions conditionnelles |
|
Test simple:
|
|
| [[ If
(Bin (op, e1, e2), st, sf)]]s = |
| Seq
|
é
ê
ê
ê
ë |
|
| Cjump (op, [[e1]]e, [[e2]]e, lt, lf); |
| Label lt; [[ st]]s; Jump fi; |
| Label lf; [[ sf]]s; Jump fi; |
| Label fi; |
|
|
ù
ú
ú
ú
û |
|
|
[[ If (e1, st, sf)]]s =
[[ If
(Bin (Ne , e1, Const 0), st, sf)]]s
La boucle while se traite de façon similaire.
| Gestion des environnements |
|
Pour comprendre la traduction des variables, il faut comprendre comment sont
traités les arguments et les variables locales des fonctions.
Cela dépend des constructions du langage.
Par exemple:
| · | L'appel par référence (ou &x en C) permet de passer l'adresse plutôt que
la valeur d'une variable. Ainsi, une variable contient tantôt la valeur
cherchée tantôt l'adresse à laquelle chercher cette valeur.
|
| · | Les tableaux en pile sont (en général) passés par référence.
|
| · | Les fonctions locales obligent à passer par référence soit:
| · | les variables qui s'échappent dans la fonction locale
(remontée des variables),
| | · | le lien statique (fermeture en pile » tableau en pile).
|
|
| Cas simplifié de Pseudo-Pascal |
|
En Pseudo-Pascal, il n'y a pas de fonctions locales,
| · | les arguments sont passés par valeurs, (ie. le contenu des variables
et non la boîte).
|
| · | les tableaux sont alloués dans le tas et passés par référence
(eg. passe leur adresse mais on ne les recopie pas).
|
En particulier, une variable ne peut pas être directement affectée par un
appel de fonction (mais la partie mutable d'une valeur associée à une
variable peut être modifiée).
On place les variables dans des temporaires (qui en général seront
des registres).
On accède à (on écrit dans) à une variable en lisant (en écrivant dans) le
temporaire associé.
L'accès à une variable locale est donc toujours la lecture d'un
temporaire. Son numéro est trouvé dans l'environnement de compilation
(cf. analogue à l'environnement d'évaluation) qu'il faut passer comme
argument à la fonction de compilation.
[[Get x]]er= Temp t
si r(x) = t
(On remplace partout ailleurs [[e]]e et [[ e]]s
par [[e]]er et [[ e]]sr.)
Les globaux sont mémorisés dans un tableau statique alloué au
début du programme à l'adresse symbolique G. Dans r les globaux sont
définis par leur position dans le tableau (w est la taille du mot).
[[Get x]]er=
Mem (Bin
(Plus , Name G, Const (n*w))
si r(x) = n
On pourrait aussi placer Name G dans un temporaire spécial
réservé Temp tG.
Dans l'environnement de compilation, il faut associer
aux variables (chaînes de caractères) des emplacements.
Ce dont sont des temporaires pour les variables locales, soit
un indice dans la table globale. On utilise un type somme:
type access = Local of Gen.temp | Global of int
let rec translate_expr env = function
...
| Get x ->
begin match Env.find_var env x with
| Local t -> Temp t
| Global n ->
let g = Frame.global_space and w = Frame.word_size
in Mem (Bin (Name g , Const (n * w)))
end |
|
| Compilation des affectations |
|
De façon analogue, c'est l'écriture:
| · | dans le temporaire associé à la variable considérée, pour les accès locaux;
|
| · | dans la case du tableau des globaux associé à la variable considérée.
|
Formellement:
| [[ Set x e]]sr= |
| |
Move_temp (t, [[e]]e r) |
si r(x) = t |
| |
Move_mem
(Bin
(Plus , Name G, Const (n*w))
, [[e]]e r) |
si r(x) = n |
| Utilisation la pile en Pseudo-Pascal |
|
La pile ne sert plus qu'à passer les arguments (>4) et à sauvegarder
les registres pendant les appels récursifs, ou lorsqu'il y a trop de
temporaires.
Ces utilisations de la pile seront traités ultérieurement par la
compilation des appels de fonction et par l'allocateur de registres.
En effet, dans le code intermédiaire,
| · | On utilise un nombre arbitraire de temporaires, que l'on suppose
sauvegardés pas les appels de fonctions.
|
| · | On utilise une instruction de haut niveaux pour les appels de fonctions;
elle devra être remplacée ultérieurement par du code qui place les arguments
à des positions conventionnelles et sauvergarde, si nécessaire, les
valeurs des temporaires pendant les appels (eg. récursifs).
|
| Compilation des fonctions |
|
Lors de l'appel de fonction, il faut communiquer entre l'appelant et
l'appelé pour passer les arguments et recevoir les résultats.
Par exemple les premiers arguments sont passés dans les
registres a0 à a3, les suivants sur la pile.
| · | Avant l'appel les arguments sont dans des temporaires de l'appelant.
|
| · | Après, ils sont dans des temporaires de l'appelé, a priori
différents (sauf avec allocation de registres inter-procédurale).
|
L'interface entre la vue externe et la vue interne,
ie. le (code de) transfert des arguments entre l'appelant et l'appelé,
sera inséré ultérieurement
en fonction de la machine cible, lors de la traduction des instructions
Call et en ajoutant un prologue et un épilogue à chaque
fonction.
| L'unité de traduction en code intermédiaire est la fonction
ou procédure. |
Fonction succ en Pseudo-Pascal (syntaxe abstraite):
{ arguments = [ "n", Integer ]; result = Some Integer;
local_vars = [ ];
body = Set ("succ", Bin (Plus, Get "n", Int 1)) } |
|
Son code intermédiaire:
[ Label succ;
Move_temp
(t104, Code.Bin (Code.Plus, Temp t105, Const 1));
Jump succ_end ] |
|
où
ì
ï
í
ï
î |
t104 |
emplacement de l'argument n |
t105 |
emplacement du résultat de succ |
succ |
adresse du prélude (utilisée pour l'appel) |
succ_end |
adresse du prologue (utilisée pour le retour) |
|
Appel de la fonction succ;
|
Function_call ("succ", Const 2) |
|
Code de l'appel:
|
Call (<succ>, [Const 3])] |
|
C'est à la charge de l'instruction Call de placer les arguments dans
le temporaire t104 et de récupérer le résultat dans le temporaire
t105.
Cela sera réalisé dans une phase ultérieure de la compilation, après
l'allocation des registres, par le prélude et le prologue.
L'appel de fonction est compilé par une expression Call
[[Function_call (g, e1, ..., en)]]e =
Call (Fg, [[e1]]e, ..., [[en]]e)
où Fg est une structure décrivant g (appelée frame) comprenant:
| · | L'étiquette pour entrer dans la fonction (celle placée en tout début du code
de g). Plus tard, on y insérera un prélude (avec la sauvegarde éventuelle
de certains registres).
|
| · | Une étiquette pour sortir de la fonction.
Plus tard on y insérera le prologue (restauration des registres)
Pour sortir d'une fonction il faut toujours faire un saut au prologue.
(c'est convention que nous prenons à ce stade.)
|
| · | L'emplacement exact des arguments dans la vue interne:
position en pile, ou numéro de temporaire
(il s'agit toujours d'un temporaire en Pseudo-Pascal).
|
| · | Position du résultat (si c'est une fonction).
|
Le type frame est implémenté dans frame.ml
type frame =
{ name : Gen.label;
return_label : Gen.label;
args : address list;
result : address option;
mutable locals : int; } |
|
Mais, on les manipule de façon abstraite (interface frame.mli) pour
permettre une modification ultérieure si nécessaire.
Le frame est recherché dans l'environnement de compilation:
| Function_call (f, args) ->
let frame_f = Env.find_definition env f in
let args_compilés = List.map (translate_expr env) args
in Call (g, args_compilés) |
|
| Compilation du corps des fonctions |
|
Pour chaque fonction:
-
Créer un nouveau frame, avec des emplacements internes pour les arguments,
et le résultat (optionnel).
(Ce sont simplement des temporaires --fraîchement alloués-- en pseudo-pascal)
- Attribuer des emplacements aux variables locales (idem)
- Augmenter l'environnement de compilation.
- Compiler le corps dans cet environnement.
Récursion
| Comme les fonctions sont récursives en PP, l'étape 1
(allocation des frames) est faite en premier pour toutes les définitions,
avant d'effectuer les autres phases pour chaque définition. |
| Compilation dans le cas général |
|
Pseudo-pascal est un cas simplifié:
| · | Les arguments sont passés par valeurs.
|
| · | Les tableaux sont passés par références.
|
Variables passées par référence:
Il faut distinguer l'adressage direct et indirect (ie. Left- et Right-value).
Tableaux alloués dans la pile:
Idem.
De plus, toutes les variables allouées n'ont plus la même taille
(ce qu'il faut gérer).
Fonctions locales (non retournées comme valeur)
Au choix:
| · | chaîner les blocs d'activation en pile (cf liens statiques), ou
|
| · | remonter les variables pour rendre toutes les fonctions globales.
|
Les variables qui s'échappent sont toujours placées en pile.
Fonctions comme valeur (ML):
fabriquer des fermetures.
Pour les fonctions locales non retournées, la fermeture peut être allouée en
pile. Pour simplifier, supposons que toutes les variables de f s'échappent,
par exemple, elles sont utilisées par une fonction g locale à f,
et sont placées en pile (x1, ... xn):
| |
: |
|
| pointeur de bloc ® |
l |
Lien statique |
| |
x1 |
|
| |
: |
Variables de f |
| |
xn |
|
| pointeur de pile ® |
: |
Registres sauvegardés |
| ¯ |
: |
autres appels |
| |
|
appel à g |
| Explication par remontée des variables |
|
Par remontée des variables il faut passer à g en plus de ses
arguments y1, ...yq, les adresses &x1, ...&xq des
variables de f.
À condition de figer statiquement leur position en pile, il suffit de passer
à g l'adresse du bloc d'activation de f (l'environnement dynamique
dans lequel est défini g) qui marque le début des variables de f. Vu de
g, on l'appelle le lien statique de g.
La fonction g retrouve les xi par décalage (calculer statiquement)
par rapport au lien statique (passé dynamiquement).
| · | elle est compilée comme si elle recevait en plus de ses arguments
un enregistrement lg dont les champs sont x1, .. xn.
|
| · | elle est appelée en passant en plus des arguments y1, ... yq
le lien statique lg.
|
| Vu comme une fermeture en pile |
|
Au lieu d'être représentés à plat les environnements sont vus comme
une chaîne de
petits environnements à plat.
Il peuvent être directement implémentés dans la pile tant que les fonctions
ne sont pas retournées en résultat (leur durée de vie dynamique n'excède par
leur portée lexicale).
Par simplicité, l'unité de compilation est la procédure: nous ne ferons pas
ici d'optimisations ni d'allocation de registres inter-procédurale.
Chaque unité de compilation comporte un frame (bloc
d'activation).
On traite le corps principal de la même façon, en le transformant en une
procédure qui ne reçoit pas d'arguments et sans variables locales.
Les optimisations inter-procédurales sont possibles, mais plus complexes et
plus coûteuses.
Les étapes
| · | Décider des emplacements pour les globaux,
|
| · | Allouer les frames des fonctions globales,
|
| · | Créer l'environnement global,
|
| · | Compiler le corps des procédures (y compris le corps du programme)
|
Le résultat de la compilation:
une structure décrivant:
| · | le nombre de globaux.
|
| · | la procédure principale (distinguée) et les sous-procédures, chacune
comportant un frame et son code (intermédiaire).
|
type 'a procedure = Frame.frame * 'a
type 'a program =
{ number_of_globals : int;
main : 'a procedure; procedures : 'a procedure list}
val program : Pp.program -> Code.code program |
|
Dans le code intermédiaire, on traite les primitives comme des appels
à des fonctions externes.
Il suffit donc de se donner une étiquette réservée par primitive
(en fait un frame dont seule l'étiquette importe).
[[Alloc e)]]e =
Call (alloc, [[e]]e)
où alloc est le frame de la primitive alloc (créé une seule fois).
Le fichier frame.ml contient les déclarations:
let write_int = Frame.new_primitive "write_int" 1 false
let writeln_int = Frame.new_primitive "writeln_int" 1 false
let read_int = Frame.new_primitive "read_int" 0 true
let alloc = Frame.new_primitive "alloc" 1 true |
|
(le premier argument indique l'arité de la primitive, le second si elle
retourne ou non un résultat.)
| · | Les expressions permettent des structures emboîtées telles que
Call (f,e1) + Call (g, (Call (h, e2))).
Or, un appel de fonction est une
opération complexe, qui produit des effets de bords (écriture dans des
registres).
|
| · | Dans la plupart des langages (mais pas en Pseudo-Pascal) les expressions
peuvent contenir des séquences. Par exemple e1 + (s; e2) en ML.
À nouveau s peut modifier la valeur des registres utilisés pour évaluer
e1.
|
La linéarisation est une phase postérieure à la génération de code qui:
| · | extrait les appels de fonctions et les séquences des expressions.
|
| · | aplatit les séquences d'instructions.
|
Le code suivant est non linéaire
(il contient des instructions Call dans les expressions).
Bin (Plus , Call (f,e1), Call (g, (Call (h, e2))))
La linéarisation le transforme en:
|
|
| Move (Temp t1, e1); |
| Move (Temp t2, Call (f, t1)); |
| Move (Temp t3, e2); |
| Move (Temp t4, Call (h, t3)); |
| Move (Temp t5, Call (g, t4)), |
| Bin (Plus , Temp t1, Temp t5) |
|
Par réécriture du code. La règle principale d'extraction
Call (f, e1, e2)
®
Move_temp (t, Call (f, e1, e2)),
Temp t
Plus généralement l'extraction retire d'une expression e une séquence s
en fournissant une expression résiduelle e'. Elle procède récursivement
pour atteindre les expressions les plus internes:
Pour préserver l'ordre d'évaluation, il faut aussi extraire les expressions
qui se trouve sur le chemin et qui ne commutent pas:
| |
|
e1 + e2 ®
Move_temp (t, e1); s,
(Temp t + e2') |
|
|
| · | typiquement, par le changement de l'ordre lecture-écriture,
|
| · | éventuellement, par la levée d'une exception.
|
Une assez bonne approximation est qu'une expression constante
qui ne lit ni n'écrit commute avec toute instruction.
(A priori une instruction extraite écrit quelque chose, donc le cas sans
écriture qui commute évidemment n'est pas intéressant.)
Pour être plus fin, on peut autoriser des lectures et écritures dans des
emplacements (temporaire ou mémoire) disjoints.
On procède de même pour toutes les expressions pouvant contenir des
expressions complexes (call) aux feuilles, et pour les instructions qui
peuvent contenir des expressions...
On en profite pour aplatir les séquences
Attention à ne pas extraire les expressions déjà extraites, ie. les Call qui apparaissent déjà dans l'une des deux configurations:
Move (Temp t,
Call (f, Temp ti))
ou
Exp (Call (f, Temp ti))
| Mise en oeuvre de la linéarisation |
|
Les fonctions principales rewrite_stm et rewrite_exp décrivent les
règles de réécriture en utilisant le pattern matching.
let rec rewrite_exp : exp -> stm list * exp =
function
| Call (f, el) ->
let s, el' = rewrite_args el in
let t = G.new_temp() in
s @ [Move_temp (t, Call (f, el'))], Temp t
| Bin (binop, e1, e2) ->
let s, [e1';e2'] = rewrite_args args in
s, Bin (binop, e1', e2')
| ....... |
|
and rewrite_stm : stm -> stm list =
function
| Move_temp (t, Call (f, el)) ->
let s, el' = rewrite_args el in
s @ [Move_temp (t, Call (f, el'))]
| Move_temp (t, e1) ->
let s, e1' = rewrite_exp e1 in
s @ [Move_temp (t, e1')]
...... |
|
La procédure auxiliaire rewrite_args réécrit une liste
d'expressions (arguments):
|
and rewrite_args : exp list -> stn list * exp list = ... |
|
(Elle doit gérer les problèmes de commutation)
Blocs élémentaires
Calcul des traces . |
|
Un bloc de base est une séquence d'instructions linéaire (une seule entrée,
une seule sortie) la plus longue possible. Il commence par une
étiquette, fini par un saut et ne comporte ni étiquette (point entrée) ni
saut (point de sortie) au milieu.
Le calcul des blocs de base est immédiat: il suffit de parcourir le code en
commençant par le début, et chaque instruction de saut ou étiquette termine
le bloc courant et en commence un nouveau.
On ajoute si nécessaire des instructions Jump lorsque le bloc courant est
fermé par la rencontre d'une étiquette.
Une trace d'exécution est un parcours le plus long possible en enchaînant les
blocs de bases les uns à la suite des autres sans jamais repasser par un
bloc déjà vu.
Cela revient à un parcours de graphe orienté où les sommets sont les blocs
de base et les arcs relient deux blocs lorsqu'il existe un saut du premier
vers le second.
On visite alors tous les noeuds du graphe, en allant le plus loin possible
sans jamais repasser par un noeud déjà vu.
Les traces mettent bout à bout des sauts et le bloc suivant.
On trouve donc fréquemment la configuration suivante que l'on simplifie
(économiser des sauts étant un des buts recherchés):
Jump l; Name l ® Name l
Les instructions de saut conditionnel de tous les assembleurs prennent
l'instruction qui suit immédiatement pour branche ``false''.
On réarrange les sauts conditionnels tels qu'ils soient toujours suivis par
leur branche false, soit en inversant les tests (suffit en général) soit en
introduisant une étiquette intermédiaire.
Cjump (op, e1, e2, l1, l2); Name
l1 ®
Cjump (neg (op), e1, e2, l2, l1); Name
l1 |
Cjump (op, e1, e2, l1, l2) ®
Cjump (op, e1, e2, l1, l3);
Name l3; Jump l2 |
Certaines traces sont meilleures que d'autres.
En effet, il est plus important de minimiser les sauts dans le code
fréquemment parcouru, par exemple dans les boucles les plus internes.
Une telle boucle devra de préférence être toute entière dans sa trace.
(Un seul saut pour le retour dans le cas normal).
Une meilleure approximation consisterait à rechercher les boucles les plus
internes par un tri topologique sur les blocs de base. Puis à commencer par
linéariser dans l'ordre de domination.
| Calcul incrémental des traces |
|
Dans un langage structuré (sans instruction goto), il n'est pas
possible d'entrer dans un bloc ``par le milieu''. On peut se passer du
du calcul des traces, et généré dès le départ du code linéaire canonique...
Le résultat est comparable, voir meilleur qu'un calcul des traces
automatique mais naïf, mais moins bon qu'un calcul qui utilise les
dominateurs.
De plus, l'approche est moins modulaire, car le calcul des traces est
est délocalisé dans la compilation de chaque construction de branchement,
alors que dans l'approche générale il ne dépend que du
code intermédiaire et est indépendant de la compilation de la syntaxe
abstraite en code intermédiaire.
Exercice 1 [Génération du code intermédiaire]
Écire un générateur de code intermédiare pour Pseudo-Pascal.
Le code intermédiaire est donné par l'interface code.mli.
La gestion des étiquettes, des environnements et des frames sont données par
les fichiers
env.mli, gen.mli et frame.mli.
Exercice 2 [Linéarisation et canonisation]
Implémenter la linéarisation, le calcul des blocs de base et la mise sous
forme canonique.
On impose l'interface canon.mli.
Exercice 3 [Interprète du code intermédiaire]
Écire un interprète pour le code intermédiaire. Celui-ci devra fonctionner
aussi bien sur du code arborescent que sur du code linéaire. On pourra
également écrire un imprimeur du code intermédiaire.
This document was translated from LATEX by
HEVEA.
