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.
On suggère très fortement de procéder construction par construction, en testant systématiquement à chaque fois.
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 -> igraphIndications :
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
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 * intLe 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 :
Pour choisir un registre à colorier, on pourra choisir par ordre de préférence
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
let instr c frame_size = function
| Ertltree.Econst (n, r, l) ->
Econst (n, lookup c r, l)
...
où 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
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%
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.
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
> ./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%