Une fois cette archive décompressée (par exemple avec tar zxvf ltl-java.tar.gz), vous obtenez un répertoire mini-c/ contenant plusieurs fichiers Java :
| LTL.java | Langage LTL (Location Transfer Language) |
| LTLinterp.java | Interprète de code LTL (pour tester) |
| X86_64.java | Assembleur x86-64 |
Ces classes sont complètes et documentées ici. 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.
class Arcs {
Set<Register> prefs = new HashSet<>();
Set<Register> intfs = new HashSet<>();
}
class Interference {
Map<Register, Arcs> graph;
}
Construire le graphe d'interférence à partir du résultat
de l'analyse de durée de vie, c'est-à-dire
Interference(Liveness lg) {
...
}
Indications :
Pour debugger, on pourra afficher le graphe d'interférence avec la méthode suivante :
void print() {
System.out.println("interference:");
for (Register r: graph.keySet()) {
Arcs a = graph.get(r);
System.out.println(" " + r + " pref=" + a.prefs + " intf=" + a.intfs);
}
}
Avec un programme comme
int main() {
return 42;
}
on doit obtenir quelque chose comme
interference: #3 pref=[%r12] intf=[%rbx, %rax, #1, #2] %rbx pref=[#2] intf=[#3, %rax, %r12] %rax pref=[#1] intf=[#3, %rbx, %r12, #2] %r12 pref=[#3] intf=[%rbx, %rax, #2] #1 pref=[%rax] intf=[#3, #2] #2 pref=[%rbx] intf=[#3, %rax, %r12, #1]
class Coloring {
Map<Register, Operand> colors = new HashMap<>();
int nlocals = 0; // nombre d'emplacements sur la pile
...
}
Le point de départ est le graphe d'interférence, c'est-à-dire
Coloring(Interference ig) {
...
}
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 méthode suivante :
void print() {
System.out.println("coloring output:");
for (Register r: colors.keySet()) {
Operand o = colors.get(r);
System.out.println(" " + r + " --> " + o);
}
}
Avec un programme comme
int main() {
return 42;
}
on doit obtenir quelque chose comme
coloring output: #3 --> %r12 #1 --> %rax #2 --> %rbx
class ToLTL implements ERTLVisitor {
private Coloring coloring; // coloriage de la fonction en cours de traduction
int size_locals; // taille pour les variables locales
LTLgraph graph; // graphe en cours de construction
...
}
On pourra afficher le résultat avec la méthode print de la classe LTLfile. 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%
class Lin implements LTLVisitor {
private LTLgraph cfg; // graphe en cours de traduction
private X86_64 asm; // code en cours de construction
private HashSet<Label> visited; // instructions déjà traduites
...
Le code produit est stocké dans la liste asm. La
table visited retient les instructions déjà traduites.
On se donne une méthode lin :
private void lin(Label l) {
if (visited.contains(l)) {
asm.needLabel(l);
asm.jmp(l.name);
} else {
visited.add(l);
asm.label(l);
cfg.graph.get(l).accept(this);
}
}
La méthode 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.
Cette méthode est mutuellement récursive avec les différentes
méthodes visit de la classe Lin qui traduisent les
différentes sortes d'instructions LTL.
On traduit une fonction LTL f avec le code Java suivant :
cfg = f.body;
asm.label(f.name);
lin(f.entry);
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%