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-java.tar.gz

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.

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 LTLfile. On affichera le résultat avec la méthode print de la classe LTL.

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 suivant :
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 :
  1. faire un premier parcours des instructions ERTL (contenues dans le champ instr du type LiveInfo) 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 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]

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 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 et le nombre d'emplacements utilisés sur la pile pour les registres spillés.
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 :

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

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 (cf 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). On pourra utiliser le visiteur ERTLVisitor fourni et écrire quelque chose comme
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

1.4. Tests

Ajouter au compilateur une option --interp-ltl pour exécuter ce code avec la classe LTLinterp 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. La classe X86_64 fournie 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 peut se servir du visiteur fourni avec la classe LTL, de la manière suivante :
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);

2.2 Traduction d'un programme LTL

Pour traduire un programme LTL, il suffit de traduire chacune de ses fonctions. Ne pas oublier de rendre main visible pour ld avec asm.globl("main");. Il ne reste plus qu'à imprimer le programme assembleur dans un fichier avec la méthode X86_64.printToFile.

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