Analyse de durée de vie, solutions |
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)
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))
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
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
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
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
(* 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