Génération de code assembleur

Voici le cours correspondant. La solution est ici.

Présentation

Les sources sont dans l’archive td9-asm.tar.gz, on construit l’exécutable avec la commande make.

Il vous reste deux traductions à implémenter dans le petit compilateur :

de LTL vers LIN, la linéarisation du code.
de LIN vers ASM, la génération de code assembleur.

Les langages LIN et ASM sont décrits dans LIN.mli et ASM.mli.

Vous allez compléter les fichiers ltl2lin.ml et lin2asm.ml.

Linéarisation du code

Il s’agit de compléter ltl2lin.ml.

On va parcourir le code en profondeur d’abord (depth-first traversal) et créer à la volée la liste des instructions LIN correspondantes.

Deux cas se présentent pour un label l qui suit une instruction instr, après avoir traduit instr :

soit ce label n’a pas encore été rencontré, auquel cas on voudrait :
- enregistrer l dans les labels visités.
- générer une instruction LIN.ILabel l.
- traduire ensuite l’instruction correspondant à l.
soit ce label a déjà été rencontré, auquel cas on voudrait :
- générer une instruction LIN.IGoto l.

On vous propose d’implémenter les variables et fonctions suivantes :

(* Set of labels already visited in the depth-first traversal. *)

let visited : Label.Set.t ref = ...
  
(* Reference cell that holds the sequence of instructions generated so far. *)
  
let instructions : LIN.instructions ref = ...
  
(* Function that allows generating a new instruction. *)
  
let generate (instruction : LIN.instruction) : unit = ...
  
(* Traverse the control flow graph with a simple depth-first traversal. *)
  
let visit (l : Label.t) : unit = ...
  
(* [visit_fresh l] is called when [l] has not been visited before. *)
  
let visit_fresh (l : Label.t) : unit = ...

Voir la solution.

Vous pouvez tester votre code avec la commande make lin, et visualiser le code produit avec :

# ./compilo -ilin -dlin <programme>

Le code généré contient de nombreux labels (instructions LIN.ILabel) inutiles, tous ceux qui ne sont pas la destination d’une instruction LIN.IGoto.

Améliorez l’implémentation précédente pour enregistrer à la volée les labels qui sont effectivement destination d’un goto, et utilisez cette information pour enlever après le parcours du code les labels inutiles dans instructions.

Voir la solution.

En fait, la solution implémentée dans ltl2lin.ml est un peu meilleure. Elle repose sur l’utilisation d’une passe dans branch.ml qui élimine les instructions LTL.IGoto avant de traduire le code en LIN.

Génération de code assembleur

Il s’agit de compléter lin2asm.ml.

Le sous-ensemble de l’assembleur MIPS destination de cette traduction est présenté dans ASM.mli.

Les deux problèmes posés par cette traduction sont les suivants :

le registre $sp doit être incrémenté/décrémenté à chaque appel de fonction.
les offsets utilisés pour accéder aux paramètres entrants/sortants et aux variables locales doivent être traduits en offsets par rapport à $sp.

La figure suivante récapitule la convention MIPS lors d’un appel de f à g, pour les arguments qui ne sont pas passés par registres physiques :

Voici ensuite une figure détaillée de l’agencement des trames de pile.

Cela nécessite d’implémenter les variables et fonctions suivantes :


(* [locals proc] is the size of the [proc]'s local stack area. *)

let locals (proc : LIN.procedure) : int32 = ...

(* [formals proc] is the size of the [proc]'s incoming stack area. *)

let formals (proc : LIN.procedure) : int32 = ...

(* [translate_slot proc slot] translates [slot] into an offset off [$sp]. *)

let translate_slot (proc : LIN.procedure) (slot : LIN.slot) : int32 = ...

(* [adjust offset] generates an [ASM] instruction that adjusts the
   stack pointer [sp] by [offset]. *)

let adjust (offset : int32) : ASM.instruction = ...

Voir la solution.

Utilisez les fonctions définies précédemment pour générer les instructions assembleur avec la fonction translate_instruction.

Voir la solution.

Vous pouvez tester votre code avec la commande make test, et visualiser le code produit avec :

# ./compilo -dasm <programme>

La solution complète se trouve dans les fichiers ltl2lin.ml et lin2asm.ml.

Voilà ! Vous avez complètement implémenté un petit compilateur en 9 séances. Vous pouvez maintenant apprécier les épigrammes suivantes dues à Alan J. Perlis :

It is easier to write an incorrect program than understand a correct one.

If a language doesn’t affect the way you think about programming, it’s not worth knowing.

To understand a program you must become the machine that executes it, often the programs that process it.

Good Programmers are not so much to be measured by their ingenuity and their logic as the completeness of their case analysis.

There are two ways to write error-free programs; only the third one works.

Like punning, programming is a play on words.

Fools ignore complexity. Pragmatists suffer it. Some can avoid it. Geniuses remove it.

Within a computer natural language is unnatural.

Ce document a été traduit de L^AT_EX par H^EV^EA