1 | (* Pasted from Pottier's PP compiler *) |
---|
2 | |
---|
3 | open ERTL |
---|
4 | open Interference |
---|
5 | |
---|
6 | let build (int_fun : internal_function) = |
---|
7 | |
---|
8 | (* Perform liveness analysis. *) |
---|
9 | |
---|
10 | let liveafter = Liveness.analyze int_fun in |
---|
11 | |
---|
12 | (* Create an interference graph whose vertices are the procedure's |
---|
13 | pseudo-registers. This graph initially has no edges. *) |
---|
14 | |
---|
15 | let graph = create int_fun.f_locals in |
---|
16 | |
---|
17 | (* Every pseudo register interferes with special forbidden registers. *) |
---|
18 | |
---|
19 | let graph = mkiph graph int_fun.f_locals I8051.forbidden in |
---|
20 | |
---|
21 | (* Iterate over all statements in the control flow graph and populate the |
---|
22 | interference graph with interference and preference edges. *) |
---|
23 | |
---|
24 | let graph = |
---|
25 | Label.Map.fold (fun label stmt graph -> |
---|
26 | let live = liveafter label in |
---|
27 | match Liveness.eliminable live stmt with |
---|
28 | |
---|
29 | | Some _ -> |
---|
30 | |
---|
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. *) |
---|
36 | |
---|
37 | graph |
---|
38 | |
---|
39 | | None -> |
---|
40 | |
---|
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 |
---|
45 | statement executes. |
---|
46 | |
---|
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). |
---|
57 | |
---|
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. *) |
---|
68 | |
---|
69 | let defined = Liveness.defined stmt in |
---|
70 | let exceptions = |
---|
71 | match stmt with |
---|
72 | | St_move (_, RTL.Reg sourcer, _) |
---|
73 | | St_set_hdw (_, RTL.Reg sourcer, _) -> |
---|
74 | Liveness.L.psingleton sourcer |
---|
75 | | St_get_hdw (_, sourcehwr, _) -> |
---|
76 | Liveness.L.hsingleton sourcehwr |
---|
77 | | _ -> |
---|
78 | Liveness.L.bottom |
---|
79 | in |
---|
80 | let graph = |
---|
81 | mki graph (Liveness.L.diff live exceptions) defined |
---|
82 | in |
---|
83 | |
---|
84 | (* |
---|
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. *) |
---|
88 | |
---|
89 | let graph = |
---|
90 | match stmt with |
---|
91 | | St_addr (r1, r2, _, _) -> |
---|
92 | mki graph (Liveness.L.psingleton r1) (Liveness.L.psingleton r2) |
---|
93 | | _ -> |
---|
94 | graph |
---|
95 | in |
---|
96 | *) |
---|
97 | |
---|
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 |
---|
101 | be eliminated. *) |
---|
102 | |
---|
103 | let graph = |
---|
104 | match stmt with |
---|
105 | | St_move (r1, RTL.Reg r2, _) -> |
---|
106 | mkppp graph r1 r2 |
---|
107 | | St_get_hdw (r, hwr, _) |
---|
108 | | St_set_hdw (hwr, RTL.Reg r, _) -> |
---|
109 | mkpph graph r hwr |
---|
110 | | _ -> |
---|
111 | graph |
---|
112 | in |
---|
113 | (* |
---|
114 | |
---|
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. *) |
---|
118 | |
---|
119 | let graph = |
---|
120 | mkiph graph (Zero.nonzeroable i) (MIPS.RegisterSet.singleton MIPS.zero) |
---|
121 | in |
---|
122 | *) |
---|
123 | graph |
---|
124 | |
---|
125 | ) int_fun.f_graph graph |
---|
126 | in |
---|
127 | |
---|
128 | (* Done. *) |
---|
129 | |
---|
130 | liveafter, graph |
---|
131 | |
---|