Partie I
Génération stricto-sensu

1 Sans les variables

Fichier solution. Bon allez, je commente un peu. La compilation des expressions ne fait pas grand chose d'autre que de réaliser les booléens (de Pseudo-Pascal) à l'aide des entiers (du code intermédiaire). Sinon c'est une bête copie.

let rec cexpr env = function | Int i -> Const i | Bool b -> Const (if b then 1 else 0) | Pp.Bin (op,e1,e2) -> Bin (cbinop op, cexpr env e1, cexpr env e2) | _ -> raise PasFini

(cbinop etait donné dans le squelette). Sinon, du point de vue de Caml, on notera une intéressante utilisation de l'expression if ... then ... else....

| Bool b -> Const (if b then 1 else 0)

Bon, mais on aurait pu écrire :

| Bool b -> if b then Const 1 else Const 0

Ou encore

| Bool true -> Const 1 | Bool false -> Const 0

Ça se corse un peu pour les instructions, là il faut realiser la sémantique de la conditionnelle et de la boucle à l'aide des étiquettes et de sauts de la machine. Je trouve assez élégant ici de déléguer les compilations à des fonctions idoines (cinstruction_list pour la séquence, ccond pour la conditionelle etc.). À part ça, pas grand chose à dire en fait.

let rec cinstruction env i = match i with | Sequence is -> Seq (cinstruction_list env is) | If (e,inst,insf) -> begin match e with Pp.Bin (op,e1,e2) when is_relop op -> ccond env op e1 e2 inst insf | _ -> ccond env Pp.Ne e (Bool false) inst insf end | While (e,i) -> begin match e with Pp.Bin (op,e1,e2) when is_relop op -> cwhile env op e1 e2 i | _ -> cwhile env Pp.Ne e (Bool false) i end | Write_int e -> Exp (Call (Frame.write_int, [cexpr env e])) | Writeln_int e -> Exp (Call (Frame.writeln_int, [cexpr env e])) | _ -> raise PasFini and cinstruction_list env is = List.map (cinstruction env) is (* compilation de la conditionnelle ``If'' *) and ccond env op e1 e2 inst insf = let lt = Gen.new_label () and lf = Gen.new_label () and lend = Gen.new_label () in Seq [Cjump (crelop op,cexpr env e1, cexpr env e2,lt,lf) ; Label lt ; cinstruction env inst ; Jump lend ; Label lf ; cinstruction env insf ; Label lend] (* compilation de la boucle ``While'' *) and cwhile env op e1 e2 i = let enter = Gen.new_label () and test = Gen.new_label () and lout = Gen.new_label () in Seq [Jump test ; Label enter ; cinstruction env i ; Label test ; Cjump (crelop op,cexpr env e1,cexpr env e2,enter,lout) ; Label lout]

Du point de vue Caml, on note l'usage de la fonction de librairie List.map, et de l'application partielle :

let rec cinstruction env i = match i with | Sequence is -> Seq (cinstruction_list env is) … and cinstructions env is = List.map (cinstruction env) is

Ici, cinstruction env est une application partielle (i.e. on ne donne pas tous les arguments de cinstruction). Le type de cinstruction est en effet le suivant

val cinstruction : 'a -> Pp.instruction -> Code.stm

(L'argument env ne sert à rien pour le moment, son type est assez indéterminé). Le type de l'application cinstruction env est donc Pp.instruction -> Code.stm. C'est à dire que cinstruction qu'il est commode de voir comme une fonction prenant deux arguments est en réalité une fonction qui rend une fonction, dont le type se lit en fait :

val cinstruction : 'a -> ( Pp.instruction -> Code.stm )

(L'opérateur « -> » penche à droite !)

Bon, si on refuse ces subtilités, on aurait très bien pu écrire :

and cinstructions env is = match is with | [] -> [] | i::rem -> cinstruction env i::cinstruction_list env rem

C'est juste un peu plus long à ecrire (et encore). Enfin, discuter de l'efficacité de l'une ou l'autre de ces écriture n'est guère pertinent.

2 Avec les variables

Fichier solution. Bon une dernière fois, lors de la compilation les variables sont liées à des représentations (adaptées au niveau du code intermédiaire) des cases qui sont les variables lors de l'exécution. Ici ça donne par exemple :

type access = Local of Gen.temp | Address of Code.exp

On notera que la distinction existe justement parce que le code intermédiaire fait la distinction entre deux cases possibles : temporaires et cases de la mémoire.

Là où ça devient amusant c'est que l'on ne fait pas du tout la même chose selon que l'on veut lire le contenu d'une case mémoire ou modifier son contenu. Pour lire :

let rec let rec cexpr env = function … | Get s -> begin match Env.find_var env s with | Local t -> Temp t | Address a -> Mem a end …

On ajoute une lecture explicite de la mémoire (constructeur Mem des expressions du code intermédiaire).

Pour écrire :

let rec cinstruction env i = match i with | Set (s,e) -> let ec = cexpr env e in begin match Env.find_var env s with | Local t -> Move_temp (r,ec) | Address a -> Move_mem (a,ec) end …

Ici, pas de lecture explicite de la mémoire.

Bon ça m'a pas l'air bien sorcier, mais que l'on songe à ce bout langage C :

x = *q ; *p = *q ;

Et que l'on essaie de le compiler dans notre code intermédiaire en supposant que x et p sont des temporaires puis des cases mémoire.

La comprehension complète du traitement des variables doit normalement jaillir quand on s'attaque à la compilation des fonctions. Dans le squelette on avait :

let cfun env (s,{arguments = args ; result = r ; local_vars = locs ; body = is}) = let f =Frame.bidon in let new_env = env in f,Seq (cinstruction_list new_env is)

C'est à dire que le frame de la fonction compilée est bidon, et que l'environnement dans lequel on compile son corps est inchangé. Mais dans la solution on a d'abord.

let cfun env (funname,{arguments = args ; result = r ; local_vars = locs ; body = ins}) = let f = Env.find_definition env s in

Le frame n'est plus bidon, on va le chercher dans l'environnement (mais qui l'a mis là ? Nous bien entendu, nous y reviendrons). On poursuit par la fabrication de l'environnement du corps. D'abord création d'une liste de paires : nom de variable locale × temporaire frais :

let locals = List.map (fun (s,_) -> (s, Local (Gen.new_temp ()))) locs

(Note: locs est extrait de la représentation sous forme de syntaxe abstraite de la fonction compilée, c'est une liste de paires : variable × type).

Puis, création d'une liste de paires nom de paramètre formel × temporaire idoine (pris dans le frame de la fonction compilée) :

and params = List.map2 (fun (s,_) t -> (s, Local t)) args (Frame.frame_args f)

(Utilisation de List.map2).

Enuite, ajout d'une (éventuelle) paire : nom du résultat × temporaire idoine.

and result = match Frame.frame_result f with | Some t -> [funname,Local t] | None -> [] in

Et finalement, fabrication de l'environnement et compilation :

let new_env = Env.change_local_vars env (result @ params @ locals) in Seq (cinstruction_list new_env ins)

Le code de la solution est équivalent, mais moins clair car il évite les concaténations de liste en employant les fonctions de librairie List.fold_right et List.fold_right2.

Bon, nous avons vu comment créer l'environnement nécessaire à la compilation d'une fonction à l'aide de son frame et d'un environnement « initial » passé en argument à cfun. Mais comment fabriquer cet environnement initial, c'est à dire comment

créer les frames,
fabriquer les liaisons de l'environnement initial ?

Pour créer un frame, c'est facile, le module Frame nous fournit une fonction idoine (named_frame). Avec un peu d'embalage, il vient :

let make_frame (funname,{arguments = args ; result = r }) = funname,Frame.named_frame funname args r

Étant donné un index i il est assez facile de créer l'expression du code intermédiaire qui est l'adresse de la i-ième variable globale :

let make_global i = Address (match i with | 0 -> Temp Frame.global_register | _ -> Bin (Uplus, Temp Frame.global_register, Const (i*Frame.wordsize)))

Et étant donné la liste de toutes les variables globales (avec leur type), on produit facilement la liste des paires des variables globales et de leur adresse :

let make_globals vs = let rec map_rec n = function | [] -> [] | (x,_)::xs -> (x, make_global n x) :: map_rec (n+1) xs in map_rec 0 vs

Ouf, on peut enfin écrire la compilation d'un programme complet. En notant bien l'introduction d'une procédure principale, apellée main.

let cprog {global_vars = g ; definitions = defs ; Pp.main = p} = let globals = make_globals g in let main_def = ("main",{arguments = [] ; result = None ; local_vars = [] ; body = p}) in let env_init = Env.create_global globals (List.map make_frame (main_def :: defs)) in let funs = List.map (fun def -> cfun env_init def) defs in let principal = cfun env_init main_def in { number_of_globals = List.length globals ; main = principal ; procedures = funs }

Une autre solution

Une autre solution procède à la génération de code « à plat », sans jamais introduire la séquence (Seq) dans le code produit.

Le truc principal est d'ajouter aux fonctions de compilation un argument continuation (r ici) qui est la liste des instructions à exécuter après celles résultant de la compilation de l'instruction source courante.

On regardera par exemple les appels à check_label dans les fonctions ccond et cwhile dans la solution. (Ces deux fonctions compilent la conditionnelle et la boucle while.)

Cette technique est moins générale que celle du cours, mais suffit pour pseudo-pascal. Elle est actuellement employée dans le compilateur Caml qui ne procède pas à l'optimisation des traces que nous verrons la semaine prochaine. Elle « suffit » dans le sens que le code généré ne contient pas trop d'ineffficacités évidentes du flot de contrôle, c'est à dire pas trop de sauts vers des sauts.

Note sur l'utlisation librairie `List`

Le code présenté utilise systématiquement les fonctions du module List de la bibliothèque standard de Caml pour itérer la compilation.

Par exemple les arguments des appels de fonction sont compilés en utilisant List.map.

| Function_call (f,args) -> Call (Env.find_definition env f,List.map (cexpr env) args)

Plus subtilement, dans l'autre solution de la compilation, les séquences d'instructions sont compilées en utilisant List.fold_right.

| Sequence is -> List.fold_right (cinstruction env) is r

C'est subtil à cause de l'argument « r » placé opportunément en dernière position parmi les arguments de la fonction cinstruction (et du placement de « env » en première position).

Partie II
Canonisation et graphes du contrôle

3 La commutation

Fichier solution complet. Il s'agissait donc d'écrire le test de commutation selon le prinicipe de l'énoncé, c'est à dire

Calculer ce qui est lu (plus exactement peut être lu) par une expression.
Calculer ce qui est écrit par une liste d'instructions.
Vérifer que l'intersection des deux « ce qui » est vide.

Les « ce qui » sont en toute généralité un ensemble de temporaires, plus la mémoire. On choisit, pour se simplifier la vie, de considérer des listes de temporaires (avec d'éventuelles répétitions) et de représenter la mémoire par un temporaire à cette tâche dédié (ou idoine ou ad-hoc).

let memory = Gen.new_temp ()

Dès lors, il est assez facile de trouver la liste des « lus » par une expression.

Le cas d'un appel de fonction (soldé par un assert false) ne doit pas se présenter si l'expression passée en argument à lus_dans_exp est une expression résiduelle, notée c dans les règles de canonisation.

Sur le même principe d'examen du produit des règles de canonisation on remarque que les instructions sur lesquelles on appliquera le test de commutation sont d'une forme très restreinte : ce sont forcément des Move_temp. En effet, comme montré dans les transparents du cours (ici et là), le test de commutation ne s'applique qu'à une suite d'instructions issues de la canonisation des expressions. En outre, la canonisation des expressions ne produit que des Move_temp. Et en outre encore, les appels de fonction ne peuvent apparaître qu'au sommet de l'expression e dans l'instruction Move_temp (t, e).

Ensuite c'est vite codé en utilisant les fonctions de librairie List.for_all et List.mem.

let rec commute e stm = let r = lus_dans_exp e and w = écrits_dans_stm stm in List.for_all (fun x -> not (List.mem x r)) w

On peut très bien argumenter qu'il est raisonnable de faire un peu moins de suppositions sur les instructions passées en argument à la fonction écrits_dans_stm (en anticipant des changements de la nature des expressions, par exemple l'ajout au langage source d'une expression if... then... else...). Une hypothèse minimale et certainement toujours vérifiée est que le code passé en argument est canonique. Le code devient alors celui ci.

Où lever l'exception Universe signifie que le code passé en argument peut écrire partout. C'est une approximation par excès traduisant que nous ne ne cherchons pas à savoir où les sauts peuvent conduire. Nous utilisons cette exception car nous n'avons pas de moyen de représenter tous les temporaires possibles comme une liste de temporaires. (On aurait aussi pu modifier le type des ensembles de temporaires, pour y inclure l'ensemble de tous les temporaires).

L'exception doit être attrapée avant de sortir du code de la fonction commute. Et si elle est levée lors de l'examen du code stm, alors stm et e ne commutent pas.

let rec commute e stm = try let r = lus_dans_exp e and w = écrits_dans_stm stm in List.for_all (fun x -> not (List.mem x r)) w with Universe -> false

On peut affiner un peu le test de commutation en rafinant un peu les règles des saut. En effet, si la cible du saut est dans code passé en argument à la fonction écrits_dans_stm, alors on on est justement en train de calculer les temporaires écrits par le code et le saut n'y change rien.

let écrits_une labs h = match h with … | Jump l -> if List.mem l labs then [] else raise Universe | Cjump (_,_,_,l1,l2) -> if List.mem l1 labs && List.mem l2 labs then [] else raise Universe … let rec get_labels = function | [] -> [] | Label l::rem -> l::get_labels rem | _::rem -> get_labels rem let écrits_dans_stm stms = let labs = get_labels stms in let rec do_rec = function | [] -> [] | h :: rest -> écrits_une labs h @ do_rec rest in do_rec stms

Voilà c'est bien compliqué et un peu inutile, mais je crois bien que ceux qui étaient partis sur l'hypothèse « code canonique » ont mis le problème des sauts sous le tapis. Enfin, vous savez vraiment pourquoi l'hypothèse de restriction des arguments était utile.

4 Les blocs de base

La solution complète.

Le code pertinent est dans le poly. C'est un code légèrement subtil. Il est à mon avis normal de ne pas l'écrire du premier coup.

L'enoncé donnait quelques conseils.

Un fois amorcée la création d'un bloc, on cherche sa fin en un parcours de la liste des instructions, si on trouve...
La définition d'une étiquette Label lab. Alors le bloc en cours de construction est terminé (son champ succ est Jump lab). Un nouveau bloc étiqueté lab commence.
Un saut quel qu'il soit, le bloc en cours se termine par ce saut. L'instruction qui suit est forcément une étiquette commençant un nouveau bloc.
Plus rien (fin de la liste des instructions). Le bloc en cours se termine par un saut vers Frame.frame_return f.
N'importe quelle autre instruction, alors cette instruction est à ajouter en fin de bloc et il faut continuer à chercher la fin du bloc en cours.

C'est une description assez précise de la fonction in_block locale à la fonction cut_blocks dont la mission, abondamment commentée, est de produire une liste de bloc à partir d'un code, deux étiquettes initiale et finale étant données.

let cut_blocks start_label exit_label code = let rec in_block cur_lab cur_ydob = function (* Cas 1. *) | Label lab::rem -> let r = in_block lab [] rem in {enter=cur_lab ; succ=Jump lab ; body=List.rev cur_ydob}::r (* Cas 2. *) | (Jump _ | Cjump (_,_,_,_,_)) as stm::rem -> let r = start_block rem in {enter=cur_lab ; succ=stm ; body=List.rev cur_ydob}::r (* Cas 4. *) | stm::rem -> in_block cur_lab (stm::cur_ydob) rem (* Cas 3. *) | [] -> (* dernier bloc, ajsuccer un saut vers end_label *) [{enter=cur_lab ; succ=Jump exit_label ; body=List.rev cur_ydob}]

Il n'y a pas d'astuce particulière, à part peut être que les instructions du bloc en cours de construction sont accumulées (à l'envers) dans l'argument cur_ydob (ydob à l'envers c'est body).

On note par ailleurs un appel start_block rem (cas 2.), la fonction start_block est chargée de commencer un nouveau bloc. (alors que la mission de in_block est de trouver la fin d'un bloc).

and start_block stms = match stms with | Label lab::rem -> in_block lab [] rem (* on pourrait aussi chercher l'étiquette suivante *) | _ -> assert false in

On complète le corps de la fonction cut_blocks par un appel initial à in_block (et non à start_block car l'étiquette premier bloc, connue, n'est pas présente dans le code).

in_block start_label [] code

Pour la fonction blocks_to_code la pose est à l'inverse de la dépose, il faut donc supprimer l'étiquette du premier bloc, mais pas les autres, voir le poly. On devrait parallèlement supprimer un éventuel saut final vers l'épilogue dans le dernier bloc. Mais, si il y eu des optimisations, c'est un peu plus compliqué. En fait, on supprime les sauts inutiles vers l'épilogue lors de la rectification des sauts bi-étiquettes. Plus précisément c'est seulement plus tard que l'on se préoccupe d'éviter un label parasite derrière un saut conditionel final dont une des cibles est l'épilogue. Alors, tant qu'à faire, on supprimera le saut final inconditionnel vers l'épilogue au même moment.

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

Partie I Génération stricto-sensu