open ERTL open Interference let build (proc : procedure) = (* Perform liveness analysis. *) let liveafter = Liveness.analyze proc in (* Create an interference graph whose vertices are the procedure's pseudo-registers. This graph initially has no edges. *) let graph = create proc.locals in (* Iterate over all instructions in the control flow graph and populate the interference graph with interference and preference edges. *) let graph : graph = Label.Map.fold (fun label i graph -> let live = liveafter label in match Liveness.eliminable live i with Some _ -> (* This instruction is eliminable and should be ignored. Eliminable instructions have not been eliminated yet, because we are still in between ERTL and LTL. They *will* be eliminated soon, though, so there is no reason to take them into account while building the interference graph. *) graph None -> (* 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 defined = Liveness.defined i 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 let graph = mki graph (Liveness.L.diff live exceptions) defined in (* 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 = match i with IUnOp (MIPSOps.UOpAddi 0l, r1, r2, _) -> mkppp graph r1 r2 IGetHwReg (r, hwr, _) ISetHwReg (hwr, r, _) -> mkpph graph r hwr _ -> 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 graph ) proc.graph graph in (* Done. *) liveafter, graph