1 (* Pasted from Pottier's PP compiler *)
6 let build (int_fun : internal_function) =
8 (* Perform liveness analysis. *)
10 let liveafter = Liveness.analyze int_fun in
12 (* Create an interference graph whose vertices are the procedure's
13 pseudo-registers. This graph initially has no edges. *)
15 let graph = create int_fun.f_locals in
17 (* Every pseudo register interferes with special forbidden registers. *)
19 let graph = mkiph graph int_fun.f_locals I8051.forbidden in
21 (* Iterate over all statements in the control flow graph and populate the
22 interference graph with interference and preference edges. *)
25 Label.Map.fold (fun label stmt graph ->
26 let live = liveafter label in
27 match Liveness.eliminable live stmt with
31 (* This statement is eliminable and should be ignored. Eliminable
32 statements have not been eliminated yet, because we are still
33 in between ERTL and LTL. They *will* be eliminated soon, though,
34 so there is no reason to take them into account while building
35 the interference graph. *)
41 (* Create interference edges. The general rule is, every
42 pseudo-register or hardware register that is defined (written) by
43 a statement interferes with every pseudo-register or hardware
44 register (other than itself) that is live immediately after the
47 An exception to the general rule can be made for move
48 statements. In a move statement, we do not need the source
49 and destination pseudo-registers to be assigned distinct hardware
50 registers, since they contain the same value -- in fact, we would
51 like them to be assigned the same hardware register. So, for a
52 move statement, we let the register that is defined (written)
53 interfere with every pseudo-register, other than itself *and
54 other than the source pseudo-register*, that is live immediately
55 after the statement executes. This optimization is explained in
56 Chapter 10 of Appel's book (p. 221).
58 This special case is only a hack that works in many cases. There
59 are cases where it doesn't suffice. For instance, if two
60 successive move statements have the same source [r0], then
61 their destinations [r1] and [r2] *will* be considered as
62 interfering, even though it would in fact be correct and
63 desirable to map both of them to the same hardware register. A
64 more general solution would be to perform a static analysis that
65 determines, for every program point, which pseudo-registers
66 definitely hold the same value, and to exploit this information
67 to build fewer interference edges. *)
69 let defined = Liveness.defined stmt in
72 | St_move (_, sourcer, _)
73 | St_set_hdw (_, sourcer, _) ->
74 Liveness.L.psingleton sourcer
75 | St_get_hdw (_, sourcehwr, _) ->
76 Liveness.L.hsingleton sourcehwr
81 mki graph (Liveness.L.diff live exceptions) defined
85 (* Two registers written at the same time are interfering (they
86 obviously should not be associated the same address).
87 Only happens with St_addr. *)
91 | St_addr (r1, r2, _, _) ->
92 mki graph (Liveness.L.psingleton r1) (Liveness.L.psingleton r2)
98 (* Create preference edges between pseudo-registers. Two registers
99 should preferably be assigned the same color when they are
100 related by a move statement, so that the move statement can
105 | St_move (r1, r2, _) ->
107 | St_get_hdw (r, hwr, _)
108 | St_set_hdw (hwr, r, _) ->
115 (* Add interference edges between the hardware register [$zero]
116 and every pseudo-register that the statement renders
117 nonzeroable. See [Zero] for an explanation. *)
120 mkiph graph (Zero.nonzeroable i) (MIPS.RegisterSet.singleton MIPS.zero)
125 ) int_fun.f_graph graph