Traduction des appels, solutions

Squelette du code

En suivant la signature de rtl2ertlI.mli, on obtient le squelette suivant :

(* This functor implements the central part of the translation of
   [RTL] to [ERTL]. It is called once for each procedure or
   function. It defines the translation of instructions as well as the
   prologue and epilogue that should be added to the procedure. *)

module Make (Env : sig

  (* [allocate()] returns a fresh pseudo-register. *)

  val allocate: unit -> Register.t

  (* [generate instruction] returns a fresh instruction label, which
     it associates with [instruction] in the control flow graph. *)

  val generate: ERTL.instruction -> Label.t

  (* [formals] is a list of the procedure's formal arguments. *)

  val formals: Register.t list

  (* [entry] is the procedure's original entry point. *)

  val entry: Label.t

  (* [result] tells whether this is a procedure or a function and, in
     the latter case, which pseudo-register holds the function's
     result when the exit label is reached. *)

  val result: Register.t option

end) = struct

  open Integer
  open Env

  (* ----------------------------------------------------------------------- *)

  (* [translate_call odestr callee actuals l] translates the [RTL]
     instruction [ICall (odestr, callee, actuals, l)] into an [ERTL]
     instruction, or sequence of instructions, that transfers control
     to [l]. *)

  let translate_call odestr callee actuals l = failwith "Pas implémenté !"

  (* ----------------------------------------------------------------------- *)

  (* Define the prologue that will be inserted in front of the
     existing code. *)

  let prologue = entry

  (* ----------------------------------------------------------------------- *)

  (* Define the epilogue that will be appended at the end of the
     existing code. *)

  let epilogue = entry

end

On a ajouté open Env pour pouvoir accéder directement aux noms des paramètres du foncteur, et open Integer comme précédemment pour pouvoir manipuler des entiers 32 bits (au lieu des entiers 31 bits de OCaml).

Manipulations de registres

Pseudo-registres et registres matériels

On applique la fonction generate pour générer les instructions correspondantes.

  (* Define functions that generate instructions for moving data
     between hardware registers and pseudo-registers. *)

  let sethwreg (desthwr, sourcer) l =
    generate (ERTL.ISetHwReg (desthwr, sourcer, l))

  let sethwregs moves l =
    List.fold_right sethwreg moves l

  let osethwreg (desthwr, osourcer) l =
    match osourcer with
    | None ->
        l
    | Some sourcer ->
        sethwreg (desthwr, sourcer) l

  let gethwreg (destr, sourcehwr) l =
    generate (ERTL.IGetHwReg (destr, sourcehwr, l))

  let gethwregs moves l =
    List.fold_right gethwreg moves l

  let ogethwreg (odestr, sourcehwr) l =
    match odestr with
    | None ->
        l
    | Some destr ->
        gethwreg (destr, sourcehwr) l

Pseudo-registres et emplacements de pile

Les fonctions setstackslots et getstackslots sont strictement symétriques, ce qui est normal puisque les emplacements sortants de l’appelant correspondent aux emplacements entrants de l’appelé, donc l’écriture et la lecture doivent se faire dans le même ordre si on veut que les arguments au site d’appel et les paramètres formels de la fonction appelée correspondent.

  (* Define functions that generate instructions for moving data
     between stack slots and pseudo-registers. These are used in order
     to access the formal parameters stored in the stack's incoming
     area and, when calling a function, to write its actual parameters
     into the stack's outgoing area.

     [offsets rs] turns the list of pseudo-registers [rs] into a list
     of pairs of a pseudo-register and a stack offset. It is here that
     the offsets at which parameters are stored on the stack is
     decided. This function is used both in [setstackslots], for
     storing actual parameters, and in [getstackslots], for fetching
     formal parameters -- this ensures consistency between caller and
     callee. *)

  let offsets rs =
    let _, ros =
      List.fold_right (fun r (offset, ros) ->
        offset + MIPS.word,
        (r, offset) :: ros
      ) rs (0l, [])
    in
    ros   

  let setstackslots sourcers l =
    List.fold_right (fun (sourcer, offset) l ->
      generate (ERTL.ISetStack (ERTL.SlotOutgoing offset, sourcer, l))
    ) (offsets sourcers) l

  let getstackslots destrs l =
    List.fold_right (fun (destr, offset) l ->
      generate (ERTL.IGetStack (destr, ERTL.SlotIncoming offset, l))
    ) (offsets destrs) l

Traduction des appels

On suit la convention d’appel, en utilisant des fonctions auxiliaires de copie dans des registres matériels (sethwregs) ou dans des emplacements de pile (setstackslots), ainsi qu’une fonction qui récupère optionnellement la valeur d’un registre matériel (ogethwreg).

  (* [translate_call odestr callee actuals l] translates the [RTL]
     instruction [ICall (odestr, callee, actuals, l)] into an [ERTL]
     instruction, or sequence of instructions, that transfers control
     to [l]. *)

  (* Before the call, we copy the actual parameters into their
     designated position, as dictated by the calling convention. The
     first few parameters are passed in registers, the rest on the
     stack. For function calls only, after the call, we copy the
     result from its designated position to its desired location. The
     [IGoto] instruction is a convenient way of turning a label into
     an instruction. *)

  let translate_call odestr callee actuals l =
    ERTL.IGoto (
      sethwregs (Misc.combine MIPS.parameters actuals) (
        setstackslots (Misc.subtract actuals MIPS.parameters) (
          generate (ERTL.ICall (
            callee,
            Misc.length actuals,
            ogethwreg (odestr, MIPS.result) l
          ))
        )
      )
    )

Traduction du prologue et de l’épilogue

On commencer par générer une liste de couples (nouveau pseudo-registre, registre matériel à sauvegarder).

  (* Each callee-save hardware register is saved into a distinct
     pseudo-register upon entry, and restored upon exit. Since
     pseudo-registers are preserved across function calls, this
     ensures that the value of the callee-save hardware registers is
     preserved.

     Although register [$ra] is not usually thought of as
     ``callee-save'', its value must also be preserved, because it is
     needed by the final [IReturn] instruction. *)

  let preserved =
    MIPS.RegisterSet.add MIPS.ra MIPS.callee_saved

  let moves =
    MIPS.RegisterSet.fold (fun hwr moves ->
      (allocate(), hwr) :: moves
    ) preserved []

On suit ensuite la convention d’appel, en n’oubliant pas d’allouer une nouvelle trame de pile en début de fonction. On utilise les fonctions symétriques gethwregs et getstackslots de celles utilisées à l’appel.

  (* Define the prologue that will be inserted in front of the
     existing code. The prologue allocates the procedure's frame,
     saves the callee-save hardware registers, and fetches the formal
     parameters from their initial locations in hardware registers or
     on the stack. *)

  let prologue =
    generate (ERTL.INewFrame (
      gethwregs moves (
        gethwregs (Misc.combine formals MIPS.parameters) (
          getstackslots (Misc.subtract formals MIPS.parameters)
            entry
        )
      )
    ))

En fin de fonction, on restaure les registres sauvés et on désalloue la trame de pile, sans oublier de copier la valeur de retour si besoin, avec la fonction ogethwreg symétrique de celle utilisée à l’appel.

  (* Define the epilogue that will be appended at the end of the
     existing code. The epilogue restores the callee-save hardware
     registers, releases the procedure's frame, and transfers control
     back to the caller. If this is a function, as opposed to a
     procedure, then the epilogue also copies the function's return
     value to the designated hardware register. *)

  let epilogue =
    osethwreg (MIPS.result, result) (
      sethwregs (Misc.mirror moves) (
        generate (ERTL.IDeleteFrame (
          generate ERTL.IReturn
        )
      )))

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