Analyse de durée de vie, solutions

L’énoncé est ici.

Analyse de durée de vie

Fonctions defined et used

La difficulté principale dans defined vient de l’instruction ICall, qui redéfinit potentiellement les registres caller-saved (dont fait partie le registre $ra).

(* These are the sets of pseudo-registers and hardware registers
   defined at (written by) an instruction. Note that the [ICall]
   instruction potentially destroys all caller-save hardware
   registers. *)

let defined (i : instruction) : L.t =
  match i with
  | IGetHwReg (r, _, _)
  | IGetStack (r, _, _)
  | IConst (r, _, _)
  | IUnOp (_, r, _, _)
  | IBinOp (_, r, _, _, _)
  | ILoad (r, _, _, _)
  | IGetGlobal (r, _, _) ->
      Register.Set.singleton r, MIPS.RegisterSet.empty
  | ICall _ ->
      Register.Set.empty, MIPS.caller_saved
  | ISetHwReg (hwr, _, _) ->
      Register.Set.empty, MIPS.RegisterSet.singleton hwr
  | INewFrame _
  | IDeleteFrame _
  | ISetStack _
  | IStore _
  | ISetGlobal _
  | IGoto _
  | IUnBranch _
  | IBinBranch _
  | IReturn _ ->
      Register.Set.empty, MIPS.RegisterSet.empty

Il y a un peu plus de difficultés avec used.

Les instructions ILoad et IStore lisent toutes les deux le registre qui contient l’adresse où lire/écrire une valeur.

L’instruction ICall lit les registres physiques où sont passés ses premiers arguments (au plus 4).

L’instruction IReturn lit bien sûr $ra, mais aussi $v0 (pour une fonction) et les registres callee-save qui doivent avoir été restaurés si besoin au moment de retourner à l’appelant.

(* This is the set of pseudo-registers and hardware registers used at
   (read by) an instruction. Note that the [ICall] instruction reads
   the hardware registers that are used to pass actual
   parameters. [IReturn flag] reads not only [$ra], but also the
   callee-save registers, and the result-value register [$v0] (if
   [flag] is set). This is because the caller expects to find
   meaningful values in these registers, so they must be considered
   live immediately before the [IReturn] instruction. *)

let used (i : instruction) : L.t =
  match i with
  | IGetHwReg (_, hwr, _) ->
      Register.Set.empty, MIPS.RegisterSet.singleton hwr
  | INewFrame _
  | IDeleteFrame _
  | IGetStack _
  | IConst _
  | IGoto _
  | IGetGlobal _ ->
      Register.Set.empty, MIPS.RegisterSet.empty
  | IReturn with_a_result ->
      Register.Set.empty,
      MIPS.RegisterSet.add_if with_a_result MIPS.result (
        MIPS.RegisterSet.add MIPS.ra (
          MIPS.callee_saved
        )
      )
  | ISetHwReg (_, r, _)
  | ISetStack (_, r, _)
  | IUnOp (_, _, r, _)
  | ILoad (_, r, _, _)
  | ISetGlobal (_, r, _)
  | IUnBranch (_, r, _, _) ->
      Register.Set.singleton r, MIPS.RegisterSet.empty
  | IBinOp (_, _, r1, r2, _)
  | IStore (r1, _, r2, _)
  | IBinBranch (_, r1, r2, _, _) ->
      Register.Set.couple r1 r2, MIPS.RegisterSet.empty
  | ICall (_, nparams, _) ->
      Register.Set.empty, MIPS.RegisterSet.of_list (Misc.prefix nparams MIPS.parameters)

Sémantique des instructions

La formule de durée de vie se traduit dans le code.

(* This is the abstract semantics of instructions. It defines the
   [out] value of an instruction in terms of its [in] value. That is,
   since liveness analysis is a backward analysis, it defines the
   pseudo-registers that are live before the instruction in terms of
   those that are live after the instruction.

   The standard definition is: a pseudo-register is considered live
   before the instruction if either (1) it is used by the instruction,
   or (2) it is live after the instruction and not defined by the
   instruction. *)

let instruction_semantics (i : instruction) (invalue : L.t) : L.t =
  L.join (used i) (L.diff invalue (defined i))

Optimisation du code inutile

La détection des instructions inutiles est la suivante :

(* An instruction is considered pure if it has no side effect, that is, if
   its only effect is to write a value to its destination pseudo-register or
   hardware register.

   A pure instruction whose destination is dead after the instruction will
   be eliminated during the translation of [ERTL] to [LTL]. This is done by
   replacing the instruction with an [IGoto] instruction.

   [eliminable liveafter i] returns [Some l], where [l] is [i]'s single
   successor, if instruction [i] is eliminable. Otherwise, it returns
   [None]. The parameter [liveafter] is the set of variables that are live
   after the instruction. *)

let eliminable ((pliveafter, hliveafter) : L.t) (i : instruction) =
  match i with
  | IGetHwReg (r, _, l)
  | IGetStack (r, _, l)
  | IGetGlobal (r, _, l)
  | IConst (r, _, l)
  | IUnOp (_, r, _, l)
  | IBinOp (_, r, _, _, l)
  | ILoad (r, _, _, l) ->
      if Register.Set.mem r pliveafter then None else Some l
  | ISetHwReg (hwr, _, l) ->
      if MIPS.RegisterSet.mem hwr hliveafter then None else Some l
  | IReturn _
  | INewFrame _
  | IDeleteFrame _
  | ISetStack _
  | ISetGlobal _
  | ICall _
  | IStore _
  | IGoto _
  | IUnBranch _
  | IBinBranch _ ->
      None

Ce qui donne comme nouvelle sémantique des instructions :

(* This is the abstract semantics of instructions. It defines the
   [out] value of an instruction in terms of its [in] value. That is,
   since liveness analysis is a backward analysis, it defines the
   pseudo-registers that are live before the instruction in terms of
   those that are live after the instruction.

   The standard definition is: a pseudo-register is considered live
   before the instruction if either (1) it is used by the instruction,
   or (2) it is live after the instruction and not defined by the
   instruction.

   As an exception to this rule, if the instruction is eliminable,
   then a pseudo-register is considered live before the instruction
   if and only if it is live after the instruction. This anticipates
   on the instruction's elimination.

   This exception means that the source pseudo-registers of a pure
   instruction need not be considered live if the instruction's result
   is unused. This allows a sequence of pure instructions whose end
   result is dead to be considered entirely dead.

   It is a simple, but not entirely trivial, exercise to check that
   this transfer function is monotone. *)

let instruction_semantics (i : instruction) (invalue : L.t) : L.t =
  match eliminable invalue i with
  | None ->
      L.join (L.diff invalue (defined i)) (used i)
  | Some _ ->
      invalue

Calcul des interférences

Une première version

Le code découle de la définition des interférences.

  (* Create interference edges. The general rule is, every
     pseudo-register or hardware register that is defined (written) by
     an instruction interferes with every pseudo-register or hardware
     register (other than itself) that is live immediately after the
     instruction executes. *)

  let graph =
    Label.Map.fold (fun label i graph ->
      let defined = Liveness.defined i in
      let live = liveafter label in
      in
      mki graph live defined
    ) proc.graph graph
  in

Le cas des move

Il faut prendre en compte les différents types de move, notamment entre pseudo-registres, qui se traduit en MIPS par une instruction MIPSOps.UOpAddi 0l.

  (* Create interference edges. The general rule is, every
     pseudo-register or hardware register that is defined (written) by
     an instruction interferes with every pseudo-register or hardware
     register (other than itself) that is live immediately after the
     instruction executes.

     An exception to the general rule can be made for move
     instructions. In a move instruction, we do not need the source
     and destination pseudo-registers to be assigned distinct hardware
     registers, since they contain the same value -- in fact, we would
     like them to be assigned the same hardware register. So, for a
     move instruction, we let the register that is defined (written)
     interfere with every pseudo-register, other than itself *and
     other than the source pseudo-register*, that is live immediately
     after the instruction executes. This optimization is explained in
     Chapter 10 of Appel's book (p. 221).

     This special case is only a hack that works in many cases. There
     are cases where it doesn't suffice. For instance, if two
     successive move instructions have the same source [r0], then
     their destinations [r1] and [r2] *will* be considered as
     interfering, even though it would be in fact be correct and
     desirable to map both of them to the same hardware register. A
     more general solution would be to perform a static analysis that
     determines, for every program point, which pseudo-registers
     definitely hold the same value, and to exploit this information
     to build fewer interference edges. *)

  let graph =
    Label.Map.fold (fun label i graph ->
      let defined = Liveness.defined i in
      let live = liveafter label in
      let exceptions =
        match i with
        | IUnOp (MIPSOps.UOpAddi 0l, _, sourcer, _)
        | ISetHwReg (_, sourcer, _) ->
             Liveness.L.psingleton sourcer
        | IGetHwReg (_, sourcehwr, _) ->
            Liveness.L.hsingleton sourcehwr
        | _ ->
            Liveness.L.bottom
      in
      mki graph (Liveness.L.diff live exceptions) defined
    ) proc.graph graph
  in

Des arêtes de préférence

On applique les fonctions mkppp et mkpph aux instructions exprimant un move.

  (* Create preference edges between pseudo-registers. Two registers
     should preferably be assigned the same color when they are
     related by a move instruction, so that the move instruction can
     be eliminated. *)

  let graph =
    Label.Map.fold (fun label i graph ->
      match i with
      | IUnOp (MIPSOps.UOpAddi 0l, r1, r2, _) ->
          mkppp graph r1 r2
      | IGetHwReg (r, hwr, _)
      | ISetHwReg (hwr, r, _) ->
          mkpph graph r hwr
      | _ ->
          graph
    ) proc.graph graph
  in

Pour finir...

  (* Add interference edges between the hardware register [$zero]
     and every pseudo-register that the instruction renders
     nonzeroable. See [Zero] for an explanation. *)
  
let graph =
  mkiph graph (Zero.nonzeroable i) (MIPS.RegisterSet.singleton MIPS.zero)
in


Ce document a été traduit de LATEX par HEVEA