Code Intermédiaire
Génération de Code
Linéarisation
Canonisation.
Postscript, PDF Didier Rémy Polytechnique, INRIA


Cours (super, self) Exercises
  1. Code intermédiaire
  2. Génération de code
  3. Linéarisation
  4. Calcul des traces
  1. Travaux dirigés
Cours (super, self) Exercises
  1. Code intermédiaire
  2. Génération de code
  3. Linéarisation
  4. Calcul des traces
  1. Travaux dirigés


La chaîne de compilation




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.


Code Intermédiaire


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
Java
C
...
Caml
Ocaml
ü
ï
ý
ï
þ
  
CI
   ì
ï
í
ï
î
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
  | Eseq of stm * exp
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.
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;
ù
ú
ú
ú
û
Test complexe:
[[ 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é.

Compilation des accès


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.
Mise en oeuvre


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.


Exemple
Fonction succ en Pseudo-Pascal (syntaxe abstraite):
 { arguments = [ "n"Integer ];  result = Some Integer;
   local_vars = [  ];
   body = Set ("succ"Bin (PlusGet "n"Int 1)) }
Son code intermédiaire:
 [ Label succ;
   Move_temp 
     (t104Code.Bin (Code.PlusTemp t105Const 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)


Exemple (suite)
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.

Compilation des appels


L'appel de fonction est compilé par une expression Call 
[[Function_call (g, e1, ..., en)]]e = Call (Fg, [[e1]]e, ..., [[en]]e)
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).
Mise en oeuvre


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 (fargs) -> 
    let frame_f = Env.find_definition env f in
    let args_compilés = List.map (translate_expr envargs
    in Call (gargs_compilés)
Compilation du corps des fonctions


Pour chaque fonction:
  1. 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)
  2. Attribuer des emplacements aux variables locales (idem)
  3. Augmenter l'environnement de compilation.
  4. 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.
Liens statiques


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


L'unité de compilation


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.

Le programme principal


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 procedureprocedures : 'a procedure list} 
    val program : Pp.program -> Code.code program


Les primitives


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

Linéarisation.
Linéarisation (but)


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


Exemple
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)


Linéarisation (méthode)


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:
e1 ® s, e1'
e1 + e2 ® s, (e1' + e2)
  
e2 ® s, e2'   
(e1, s) commutent
e1 + e2 ® s, (e1 + e2')
Pour préserver l'ordre d'évaluation, il faut aussi extraire les expressions qui se trouve sur le chemin et qui ne commutent pas:
e2 ® s, e2'
e1 + e2 ® Move_temp (t, e1); s, (Temp t + e2')
(Règle à n'appliquer qu'en dernier recours.)
Commutation
Il s'agit de ne pas permuter l'évaluation d'une instruction et d'une expression lorsque cela risque de changer le sens du programme.
    ·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.
Linéarisation (suite)


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...
e1 ® s, e1'
Exp (e1) ® s; Exp e1'
  
i ® s'; i'
s; i ® s; s'; i'
   etc.


On en profite pour aplatir les séquences
s ® s'
s0; Seq (s) ® s; s'


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 (fel) ->     
        let sel' = rewrite_args el in
        let t = G.new_temp() in
        s @ [Move_temp (tCall (fel'))], Temp t
    | Bin (binope1e2) ->              
        let s, [e1';e2'] = rewrite_args args in
        sBin (binope1', e2')
    | .......


Mise en oeuvre (suite)


and rewrite_stm : stm -> stm list = 
  function
    | Move_temp (t,  Call (fel)) ->
        let sel' = rewrite_args el in
        s @ [Move_temp (tCall (fel'))]
    | Move_temp (te1) -> 
        let se1' = rewrite_exp e1 in
        s @ [Move_temp (te1')] 
              ......


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 .
Les blocs de base


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.

Les traces


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.

Nettoyage des traces


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


Traces optimales


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.

Exercices


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.