Solution, génération de code Mips

1  Première étape

La solution est spim-sol.ml.

Je ne reviens pas trop sur la sélection des expression, puisque donnée dans le squelette et dans le poly. Tout de même, le sélecteur des expressions donné diffère un peu de celui du poly : il abuse du filtrage pour bien montrer les tuiles. Voici par exemple la sélection de l'instruction « lw »
  | Mem (Bin ((Plus|Uplus), Const ne))
  | Mem (Bin ((Plus|Uplus), eConst n))  when seize_bits n ->
      let d = new_temp () and s = emit_exp e in
      emit_lw d n s
 ; d
  | Mem (Bin (MinuseConst n))  when seize_bits (-n) ->
      let d = new_temp () and s = emit_exp e in
      emit_lw d
 (-ns ; d
  | Mem e ->
      let d = new_temp () and s = emit_exp e in
      emit_lw d
 0 s ; d

La selection des instruction n'est pas bien sorcière non plus.

Les complications proviennent plutôt du type Ass.instr bizarre des instructions de l'assembleur. Voici par exemple l'emission d'un saut conditionel.
let emit_bcc op s0  s1 lab1 lab2 =
  emit
    (Oper
       (branch_of_relop op^"  ^s0, ^s1, "^Gen.label_string lab1,
        [s0 ; s1], [], Some [lab1 ; lab2]))

let emit_stm frame = function

  | Cjump (ope1e2lab1lab2) ->
      let s1 = emit_exp e1
      and s2
 = emit_exp e2 in
      emit_bcc op s1 s2 lab1 lab2

En fait, le MIPS a tellement peu d'instructions que la sélection s'impose d'elle même. On peut juste faire un petit effort pour la selection de l'instruction d'écriture en mémoire « sw ».
let emit_sw s0 i s1 =
  emit (Oper ("sw   ^s0,"^string_of_int i^"(^s1)",  [s0 ; s1], [], None))

let emit_stm frame = function

  | Move_mem
      ((Bin ((Plus|Uplus), Const nea)|Bin ((Plus|Uplus), eaConst n)),
       e)
      when seize_bits n ->
     let s0 = emit_exp ea
     and s1
 = emit_exp e in
     emit_sw s1 n s0

  | Move_mem (Bin (MinuseaConst n), e)
      when seize_bits (-n) ->
     let s0 = emit_exp ea
     and s1
 = emit_exp e in
     emit_sw s1
 (-ns0
  | Move_mem(eae) ->
      let s0 = emit_exp ea
      and s1
 = emit_exp e in
      emit_sw s1
 0 s0
On note que les motifs d'adresse à identifier (le premier argument de Move_mem) sont les mêmes que dans le cas de la lecture en mémoire (constructeur Mem des expressions).

Le morceau le plus difficile est sans doute la selection des appels de fonction. Commençons par écrire une petite fonction emit_jal, chargée d'émettre l'instruction « jal ». Cette fonction prend un frame en argument.
let rec nfirsts n rs =
  if n = 0 then []
  else
    match rs with

    | [] -> []
    | r::rs -> r::nfirsts (n-1) rs

let emit_jal f
 =
  let srcs = nfirsts (List.length (Frame.frame_args f)) arg_registers
  and dests
 = trash f in
  emit

    (Oper
       ("jal "^Gen.label_string (Frame.frame_name f),
       destssrcsNone))
On voit bien comment est fabriqué l'instruction MIPS, l'étiquette d'entrée de la fonction appelée est d'abord extraite du frame f, puis convertie en chaîne. Les sources sont les registres de passage des argument effectivement utilisés (et ça il fallait l'écrire), les destinations étaient données (appel à la fonction trash). Pour préciser, les destinations sont le registre ra dont l'instruction jal détruit certainement le contenu, plus tous les registres dont la fonction appelée a conventionellement le droit de détruire le contenu (c'est à dire call_trash en général).

Il faut aussi émettre le code qui range les arguments dans les registres conventionnels.
let rec emit_args regs args = match regsargs with
r::rse::es ->
    let s = emit_exp e in
    emit_move r s
 ;
    emit_args rs es
_, [] -> ()
| [], _ -> assert false (* Par hypothèse *)
Bon, c'est de la manipulation standard de listes. On note qu'il y a échec au cas où le nombre de registres réservé au passage des argument se révèle insuffisant.

Ensuite c'est fini :
let emit_call caller_frame callee_frame args =
  emit_args arg_registers args ;
  emit_jal callee_frame ;
  v0

2  La totale

La solution est spim.ml.

Le but du jeu était donc de dépasser la limitation « tous les arguments sont passés en registres ». Puisque certains paramètres effectifs sont passés en pile, il faut d'une part les y mettre (au moment de l'appel) et d'autre part allez les y chercher (dans le prologue).

Commençons par la pose. Il faut modifier emit_call et plus spécifiquement emit_args réalisés à la question précédente. Voici un code possible :
let emit_store_sp_offset i s0 =
    let offset = string_of_int i in
    emit
 (Oper ("sw   ^s0, "^offset^"($sp)", [s0], [], None))

let rec emit_args regs args = match regsargs with
   ... (* Comme avant *)
| [], _ -> (* Plus de registres, encore des arguments effectifs *)
   let rec to_stack i = function
   | [] -> ()
   | e :: es ->
      let s = emit_exp e in
      emit_store_sp_offset
 (Frame.wordsize * is ;
      to_stack (i+1) es in
   to_stack
 0 args
Il n'y a rien de bien compliqué, le (disons) cinquième argument va en sommet de pile (adresse « 0($sp) », le sixième juste en deça (adresse « 4($sp) »), etc. Il faut également informer l'appelant qu'il doit reserver les mots correspondant dans le sommet de son frame.
let emit_call caller_frame callee_frame args =
  emit_args arg_registers args ;
  let nargs_instack =
     let nregs = List.length arg_registers and nargs = List.length args in
     if
 nargs
 <= nregs then
        0
     else
       nargs-nregs in
  Frame
.make_space_for_args caller_frame nargs_instack ;
  emit_jal callee_frame ;
  v0
(Le code de spim.ml est un peu différent, il évite les appels à List.length, mais bon).

Voyons la dépose, il faut modifier le prologue tel que donné dans le squelette :
let emit_prolog f decr_sp =
(* Émission du point d'entrée *)
  emit_label (Frame.frame_name f) ;

(* Allouer le frame en décrémentant sp *)
  emit (Oper (decr_sp, [], [], None)) ;

(* Sauvegarder les callee_save *)
  let saved_callee_save =
    Gen.new_temp ()::
    List.map (fun _ -> Gen.new_temp ()) callee_save_registers in
  emit_moves saved_callee_save
 (ra::callee_save_registers) ;

(* Copier les arguments des registres conventionnels vers
   les temporaires idoines *)

  let rec get_args  temps regs = match tempsregs with
  | t::tsr::rs ->
      emit_move t r ; get_args ts rs
  | [],_ -> ()
  | _,[] ->
      failwith
        (Printf.sprintf "Plus de %i arguments" (List.length arg_registers)) in
  get_args (Frame.frame_args farg_registers ;

(* Finalement renvoyer les sauvegardes des callee-saves *)
  saved_callee_save
Il est clair que l'intervention doit porter sur la fonction get_args et plus précisément que l'on doit remplacer l'echec final par la lecture de la pile. Mais attention, le pointeur de pile a dejà été diminué !. C'est à dire que le (disons) cinquième argument est à l'adresse F+0($sp), le sixième à l'adresse F+0($sp) etc. où F est la taille du frame de la fonction f dont nous sommes en train d'émettre le prologue. La constante F est pour le moment inconnue, mais nous savons qu'elle sera connue de l'assembleur sous le nom Frame.frame_size_label f. Bref on pourra se débrouiller (mais ici la glace est mince) comme ceci :
let emit_load_fp_offset frame_size i d0 =
  let sp_offset = (string_of_int i) ^ "+" ^ frame_size in
  emit
 (Oper ("lw   ^d0, "^sp_offset ^"($sp)", [], [d0], None))

let emit_prolog  f decr_sp =
  ...
  let rec get_args  temps regs = match tempsregs with
    | t::tsr::rs ->
        emit_move t r ; get_args ts rs
    | [],_ -> ()
    | _,[] ->
        let frame_size = Frame.frame_size_label f in
        let rec
 from_stack i
 = function
        | [] -> ()
        | arg :: args ->
            emit_load_fp_offset frame_size (Frame.wordsize * iarg ;
            from_stack (i+1) args in
        from_stack
 0 temps in
  ...

Un exemple de code produit ne nuiera pas. Compilons donc l'exemple test/quick.p (quicksort) qui contient une fonction tri prenant trois arguments. Nous compilons en mode « -3 » où un seul registre (a0) est affecté au passage des arguments. Voici un appel de la fonction tri
    lw   $a0, 0($gp)
    sw   $zero, 0($sp)
    lw   $156, 4($gp)
    sw   $156, 4($sp)
    jal  tri
Et voici le prologue de la fonction tri
# Point d'entrée
tri:
# Allocation du frame
    subu $sp$sptri_f
# Sauvegarde des callee-saves
    move $125
$ra
# Copie des paramètres effectifs dans les temporaires idoines
    move $106$a0
    lw   $107, 0+tri_f($sp)
    lw   $108, 4+tri_f($sp)

Il faut bien comprendre que la sortie finale du compilateur comprendra une définition de tri_f, par exemple (option « -spill »)
    tri_f=136
L'assembleur est ensuite à même de calculer les sommes 0+tri_f et 4+tri_f de sorte que ce seront les entiers 136 et 140 qui se retrouvent dans le code machine final.

3  Quelques commentaires sur la solution

En fait la solution finale spim.ml diffère de la solution intermédaire sur d'autres points.

Mon code tente de ne pas trop générer de ``moves'' inutiles (un ``move'' est un transfert d'un registre dans un autre). Ce n'est pas indispensable, puisque les phases suivantes de la compilation se chargeront justement, entre autres, d'éliminer ces ``moves'' inutiles, mais c'est assez facile et ne peut pas faire de mal. C'est une question de philosophie, inutile de faire des efforts déments pour éviter ces ``moves'' quand c'est compliqué, mais c'est tout de même plus beau de les éviter quand c'est facile. En outre, donner une entrée plus simple aux phases suivantes ne peut que leur faire du bien.

Dans la pratique, la fonction emit_stm passe un registre (plus exactement une option de registre) à la fonction emit_exp. Si la fonction emit_exp a besoin d'un registre pour rendre le résultat de sa compilation, alors elle utlisera plutôt le registre qu'on lui a donné. Cela donne par exemple :
let rec emit_stm = function
   ...

Move_temp (de) ->
      let s = emit_exp (Some din
      if
 s
 <> then emit_move d s

Un simplification du codage intervient également. En effet, les accès mémoire indexés se traitent en une seule instruction Mips (lw r1,i(r2) en lecture, sw r1,i(r2) en écriture). La fonction emit_addr traite l'émission des adresses et est apellée à la fois par emit_exp et emit_stm. Il en result un codage plus compact, mais qui obscursit un peu le principe de couverture par des tuiles.

Enfin le code optimise les multiplication (et les divisions) par certaines constantes. Pour ce qui est de la multiplication, si un des arguments est un entier connu qui est une puissance de deux, on peut remplacer la multiplication par un décalage vers la gauche (instruction Mips sll). Plus généralement on peut remplacer une multiplication par un entier connu par un enchaînement de décalages à gauche et d'additions.

Or, un décalage est nettement plus rapide qu'une multiplication, le processeur mettra un seul cycle pour faire le décalage, contre plusieurs pour la multiplication. Un truc similaire s'applique pour la division et le décalage à droite (sra) mais c'est moins important, car un code typique contient bien plus de multiplications par des constantes que de divisions, en raison principalement des accès dans les tableaux qui entraînent pas mal de multiplications par la taille du mot machine (ici 4). Le code proposé fait l'effort minimal (multiplication et division par 2 et par 4)

Un autre code un peu excessif identifie les multiplications qui se compilent par au plus cinq décalages (cf. la fonction suivante mult_by_bits). Dans la pratique, au plus un décalage est probablement suffisant.
(* Les bits a` un d'un nombre positif, plus significatifs en premier *)
let bits =
  let rec bits_rec r k = function
    | 0 -> r
    | i ->
        if i mod 2 = 0 then
          bits_rec r (k+1) (i/2)
        else
          bits_rec (k::r) (k+1) (i/2) in
  bits_rec [] 0

(* Multiplication par un nombre constant *)

let mult_by_bits d s = function
  | 0 -> zero
  | 1 -> s
  | i ->
      let iabs = if i < 0 then -else i in
      let
 ibits
 = bits iabs in
      if
 List
.length ibits >= 5 then
        emit_const_arg Times d s i
      else begin
        let
 t
 = if d = then Gen.new_temp () else in

        let rec
 sll_rec
 = function
        | k1::k2::rest ->
            emit_add t t s ;
            emit_sll t t (k1-k2) ;
            sll_rec (k2::rest)
        | [0] ->
            emit_add t t s
        | [k] ->
            emit_add t t s ;
            emit_sll t t k
        | [] -> assert false in
        begin match
 ibits
 with
        | k1::k2::rest ->
            emit_sll t s (k1-k2) ;
            sll_rec (k2::rest) ;
        | [k] ->
            emit_sll t s k ;
        | [] -> assert false
        end ;
        if i > 0 then t
        else begin
          emit_neg d t
 ; d
        end
      end


Ce document a été traduit de LATEX par HEVEA.