Sélection d’instructions, solutions

L’énoncé est ici.

Appel de procédure

Un appel de procédure est très semblable à un appel de fonction, les traductions sont très semblables elles-aussi :

Pour une fonction : 

    (* Function call in translate_expression. *)

  | PP.EFunCall (callee, es) ->
      UPP.EFunCall (callee, List.map (translate_expression genv env) es)

Pour une procédure : 

    (* Procedure call in translate_instruction. *)

  | PP.IProcCall (callee, es) ->
      UPP.IProcCall (callee, List.map (translate_expression genv env) es)

Variables globales

Allocation des variables globales

La fonction allocate_globals est assez compacte en utilisant StringMap.fold :

(* Building the global environment. This involves choosing the offsets
   at which global variables are stored. *)

let allocate_globals (p : PP.program) : genv * int32 =

  (* [next] holds the next available location. All data is word-sized,
     so it is incremented by 4 bytes every time we allocate a new
     global variable, regardless of the type of the data that is being
     allocated. Its final value of [next] is the overall space
     required by the global variables. *)

  StringMap.fold (fun global (_ : PP.typ) (genv, next) ->
    StringMap.add global next genv,
    next + MIPS.word
  ) p.PP.globals (StringMap.empty, 0l)

Accès aux variables globales

Comme précédemment :

    (* Variable access in translate_expression. Distinguish globals and locals. *)

  | PP.EGetVar v ->
      if StringSet.mem v env then

        (* This is a local variable. *)

        UPP.EGetVar v

      else

        (* This is a global variable. Translate to a global variable
           access instruction. *)

        UPP.EGetGlobal (StringMap.find v genv)


    (* Variable update in translate_instruction. Distinguish globals and locals. *)

  | PP.ISetVar (v, e) ->
      if StringSet.mem v env then

        (* This is a local variable. *)

        UPP.ISetVar (v, translate_expression genv env e)

      else

        (* This is a global variable. Translate to a global variable
           update instruction. *)

        UPP.ISetGlobal (StringMap.find v genv, translate_expression genv env e)

Mémoire dynamique

Fonctions utiles

(* Translating a word count into a byte count. This involves
   multiplying by the word size. *)

let w2b e =
  Upp2upp.mkbinop OpMul (UPP.EConst MIPS.word) e

(* Convert a pair of an array base address and element index into an
   element address. This involves adding the base address to the
   index, converted to a byte offset. *)

let element_address base index =
  Upp2upp.mkbinop OpAdd base (w2b index)

(* Memory loads and stores. *)

let mkload = function

    (* An explicit offset is available. Make it part of the
       load instruction. *)

  | UPP.EUnOp (UOpAddi i, e) ->
      UPP.ELoad (e, i)

    (* Default case. *)

  | e ->
      UPP.ELoad (e, 0l)

let mkstore e1 e2 =
  match e1 with

    (* An explicit offset is available. Make it part of the
       store instruction. *)

  | UPP.EUnOp (UOpAddi i1, e1) ->
      UPP.IStore (e1, i1, e2)

    (* Default case. *)

  | _ ->
      UPP.IStore (e1, 0l, e2)

Accès à la mémoire dynamique

    (* Array read in translate_expression. We compute the element's address and access it. *)

  | PP.EArrayGet (earray, eindex) ->

      mkload (
        element_address
          (translate_expression genv env earray)
          (translate_expression genv env eindex)
      )

    (* Array write in translate_instruction. We compute the element's address and access it. *)

  | PP.IArraySet (earray, eindex, evalue) ->

      mkstore (
          element_address
            (translate_expression genv env earray)
            (translate_expression genv env eindex)
        )
        (translate_expression genv env evalue)

Allocation dynamique

    (* Array read in translate_expression. We compute the element's address and access it. *)

  | PP.EArrayAlloc (_, e) ->

      UPP.EFunCall (
        CPrimitiveFunction Alloc,
        [ w2b (translate_expression genv env e) ]
      )

Sélection d’opérations

Optimisations avec constantes et UOpAddi

L’adddition et la soustraction montrent bien les différentes possibilités d’optimisation, la multiplication se traite de même.

Voir les fonctions mkadd et mksub dans upp2upp.ml.

Optimisation des multiplications

Voici la solution complète pour la multiplication, avec le décalage de bits à gauche (vers les bits de poids fort) codé dans mksll.

Voir les fonctions mksll et mkmul dans upp2upp.ml.

Ce document a été traduit de LATEX par HEVEA