source: Deliverables/D2.2/8051/src/ERTL/build.ml @ 486

Last change on this file since 486 was 486, checked in by ayache, 9 years ago

Deliverable D2.2

File size: 4.2 KB
Line 
1(* Pasted from Pottier's PP compiler *)
2
3open ERTL
4open Interference
5
6let 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 (_, sourcer, _)
73            | St_set_hdw (_, 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, r2, _) ->
106                mkppp graph r1 r2
107            | St_get_hdw (r, hwr, _)
108            | St_set_hdw (hwr, 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
Note: See TracBrowser for help on using the repository browser.