INF564 - TD 8-9 - Production de code LTL, linéarisation

Le but de ces deux TD est de réaliser la production de code intermédiaire LTL pour le langage mini-C, puis sa traduction vers l'assembleur x86_64.

Code fourni

Archive à télécharger : ltl-ocaml.tar.gz

Une fois cette archive décompressée (par exemple avec tar zxvf ltl-ocaml.tar.gz), vous obtenez un répertoire mini-c/ contenant des modules OCaml :

Ltltree Location Transfer Language (LTL)
Ltlinterp Interprète de code LTL (pour tester)
X86_64 Assembleur X86_64

Ces modules sont complets. Cliquer sur le nom du module pour accéder à sa documentation. On prendra le temps de bien comprendre le code fourni.

1. Production de code LTL

L'objectif est d'ajouter au compilateur mini-C une fonction traduisant le code ERTL en code LTL, c'est-à-dire en une valeur du type Ltltree.file. On affichera le résultat avec la fonction Ltltree.print_file.

On suggère très fortement de procéder construction par construction, en testant systématiquement à chaque fois.

1.1. Construction du graphe d'interférence

Un graphe d'interférence a pour sommets des registres et deux sortes d'arêtes (interférence ou préférence). On peut lui donner le type OCaml suivant :
type arcs = { prefs: Register.set; intfs: Register.set }
type igraph = arcs Register.map
Écrire une fonction qui construit un tel graphe à partir du résultat de l'analyse de durée de vie, c'est-à-dire une fonction du type
val make: live_info Label.map -> igraph
Indications :
  1. faire un premier parcours des instructions ERTL (contenues dans le champ instr du type live_info) pour ajouter une arête de préférence pour chaque instruction mov x y (avec x et y distincts).
  2. faire un second parcours des instructions ERTL pour ajouter les arêtes d'interférences.
Prendre soin de construire un graphe non orienté (pour toute arête x-y on a aussi une arête y-x).

Pour debugger, on pourra afficher le graphe d'interférence avec la fonction suivante :

let print ig =
  Register.M.iter (fun r arcs ->
    Format.printf "%s: prefs=@[%a@] intfs=@[%a@]@." (r :> string)
      Register.print_set arcs.prefs Register.print_set arcs.intfs) ig
Avec un programme comme
int main() {
  return 42;
}
on doit obtenir quelque chose comme
#1: prefs=%rax intfs=#2, #3
#2: prefs=%rbx intfs=#1, #3, %r12, %rax
#3: prefs=%r12 intfs=#1, #2, %rax, %rbx
%r12: prefs=#3 intfs=#2, %rax, %rbx
%rax: prefs=#1 intfs=#2, #3, %r12, %rbx
%rbx: prefs=#2 intfs=#3, %r12, %rax

1.2. Coloration du graphe d'interférence

On va maintenant colorier le graphe d'interférence, c'est-à-dire associer une valeur de type Ltltree.operand (un registre physique ou un emplacement de pile) à chaque pseudo-registre. Le résultat du coloriage est un dictionnaire donnant la couleur de chaque pseudo-registre :
type color = Ltltree.operand
type coloring = color Register.map
Écrire une fonction qui réalise le coloriage, avec le type suivant :
val color: igraph -> coloring * int
Le second résultat est le nombre d'emplacements nécessaires sur la pile pour les pseudo-registres qui n'ont pas pu être alloués dans des registres physiques.

On ne demande pas d'écrire l'algorithme de George-Appel présenté en cours. On peut se contenter de quelque chose de plus simple, de la manière suivante :

  1. mettre tous les pseudo-registres dans un ensemble todo
  2. pour chacun, maintenir l'ensemble de ses couleurs potentielles ; initialement, c'est la différence de Register.allocatable et de ses interférences
  3. tant que todo n'est pas vide

Pour choisir un registre à colorier, on pourra choisir par ordre de préférence

Les registres spillés pourront être alloués linéairement sur la pile (i.e. chaque nouveau pseudo-registre spillé prend l'emplacement suivant). On pourrait bien évidemment faire beaucoup mieux.

Pour debugger, on pourra afficher le résultat du coloriage avec la fonction suivante :

open Format
let print_color fmt = function
  | Reg hr    -> fprintf fmt "%a" Register.print hr
  | Spilled n -> fprintf fmt "stack %d" n
let print cm =
  RM.iter
    (fun r cr -> printf "%a -> %a@\n" Register.print r print_color cr) cm
Avec un programme comme
int main() {
  return 42;
}
on doit obtenir quelque chose comme
  #1 -> %rax
  #2 -> %rbx
  #3 -> %r12

1.3. Construction du code LTL

Pour traduire une fonction ERTL en une fonction LTL, il faut
  1. faire l'analyse de durée de vie (fonction liveness du TD 7)
  2. construire le graphe d'interférence
  3. le colorier
  4. traduire chaque instruction ERTL en une ou plusieurs instructions
Cette dernière étape est très semblable à la traduction RTL vers ERTL (TD 7). Comme pour cette dernière, on pourra stocker le graphe de flot de contrôle en cours de construction dans une référence globale et écrire une fonction instr traduisant une instruction. Cette fonction prend la forme
let instr c frame_size = function
  | Ertltree.Econst (n, r, l) ->
      Econst (n, lookup c r, l)
  ...
c est le résultat du coloriage et frame_size la taille occupée par les variables locales.

On pourra utiliser la fonction lookup suivante qui remplace un pseudo-registre par sa couleur :

let lookup c r =
  if is_hw r then Reg r else M.find r c

On pourra afficher le résultat avec la fonction Ltltree.print_file. Avec un programme comme

int main() {
  return 42;
}
on doit obtenir quelque chose comme
=== LTL ==================================================
main()
  entry : L5
  L5: goto L4
  L4: goto L3
  L3: goto L2
  L2: mov $42 %rax  --> L1
  L1: goto L10
  L10: goto L9
  L9: goto L8
  L8: goto L7
  L7: goto L6
  L6: return

1.4. Tests

Ajouter au compilateur une option --interp-ltl pour exécuter ce code avec la fonction Ltlinterp.program fournie.

On teste alors comme pour le code ERTL :

> ./run -i  "mon/chemin/vers/mini-c --interp-ltl"
Test de mon/chemin/vers/mini-c --interp-ltl

Interprétation
Execution normale
-----------------
...........................................................
Execution conduisant à un échec
-------------------------------
...
Compilation:
Compilation : 62/62 : 100%
Comportement du code : 62/62 : 100%

2. Production de code assembleur x86-64

La dernière étape de notre compilateur consiste à transformer le code LTL en code assembleur x86-64. Il s'agit essentiellement de linéariser le graphe de flot de contrôle LTL. Le module X86_64 fourni permet de construire du code assembleur x86_64 facilement puis de l'imprimer dans un fichier.

2.1 Traduction d'une fonction LTL

Pour traduire le graphe de flot de contrôle LTL en code assembleur, on se donne les variables globales suivantes :
let visited = Hashtbl.create 17
type instr = Code of X86_64.text | Label of Label.t
let code = ref []
let emit l i = code := Code i :: Label l :: !code
let emit_wl i = code := Code i :: !code
let labels = Hashtbl.create 17
let need_label l = Hashtbl.add labels l ()
Le code produit est stocké dans la liste !code (à l'envers). Une instruction y est ajoutée, avec une étiquette, grâce à la fonction emit. La table visited retient les instructions déjà traduites. La table labels retient les étiquettes qui devront rester dans le code assembleur au final (car destinations de sauts).

On peut alors écrire deux fonctions mutuellement récursives :

let rec lin g l =
  if not (Hashtbl.mem visited l) then begin
    Hashtbl.add visited l ();
    instr g l (Label.M.find l g)
  end else begin
    need_label l;
    emit_wl (jmp (l :> string))
  end

and instr g l = function
  | Econst (n, r, l1) ->
      emit l (movq (imm32 n) (operand r)); lin g l1
  ...
La fonction lin produit le code à partir d'une étiquette donnée, s'il n'a pas déjà été produit, et une instruction de saut vers cette étiquette sinon. La fonction instr produit le code à partir d'une étiquette et de l'instruction correspondante, sans condition.

La fonction operand, qu'il faut écrire, traduit une opérande LTL de type Ltltree.operand en une opérande x86-64 de type X86_64.operand. Pour traduire un registre de type Register.t en un registre de type X86_64.register, il y a une fonction X86_64.register64 fournie.

Une fois le graphe entièrement traduit (en appelant lin sur le point d'entrée de la fonction), il suffit de filtrer !code pour y supprimer les étiquettes qui ne sont pas dans la table labels puis de concaténer ce qui reste avec l'opérateur ++ du module X86_64.

2.2 Traduction d'un programme LTL

Pour traduire un programme LTL, il suffit de traduire chacune de ses fonctions et concaténer le code obtenu (avec l'opérateur ++ du module X86_64). Ne pas oublier de déclarer main avec globl. Il ne reste plus qu'à imprimer le programme assembleur dans un fichier avec la fonction X86_64.print_program.

Avec un programme comme

int main() {
  return 42;
}
on doit obtenir un programme assembleur de la forme
        .text
	.globl main
main:
	movq $42, %rax
	ret
        .data

2.3 Tests

On peut enfin tester le compilateur de la manière suivante :
> ./run -3  mon/chemin/vers/mini-c
Test de mon/chemin/vers/mini-c

Partie 3
Execution normale
-----------------
...........................................................
Execution conduisant à un échec
-------------------------------
../run: line 266: 12739 Segmentation fault      ./a.out > out
../run: line 266: 12751 Floating point exception./a.out > out
../run: line 266: 12763 Floating point exception./a.out > out

Compilation:
Compilation : 62/62 : 100%
Code produit : 62/62 : 100%
Comportement du code : 62/62 : 100%

retour à la page du cours