source: extracted/untrusted/compute_colouring.ml @ 2740

Last change on this file since 2740 was 2740, checked in by sacerdot, 7 years ago

Graph colouring terminated up to Uses that will be implemented
in Matita.

File size: 1.7 KB
Line 
1(* Adapted from Pottier's PP compiler *)
2
3let colour_graph globals int_fun liveafter =
4  (* Build an interference graph for this function, and color
5     it. Define a function that allows consulting the coloring. *)
6
7  let module G = struct
8    let graph = Build.build globals int_fun liveafter
9    let uses = Uses.examine_internal int_fun
10    let verbose = false
11(*
12    let () =
13      if verbose then
14        Printf.printf "Starting hardware register allocation for %s.\n" f
15*)
16  end in
17
18  let module C = Coloring.Color (G) in
19
20  let lookup r =
21    Untrusted_interference.Vertex.Map.find (Untrusted_interference.lookup G.graph r) C.coloring
22  in
23
24  (* Restrict the interference graph to concern spilled vertices only,
25     and color it again, this time using stack slots as colors. *)
26
27  let module H = struct
28    let graph = Untrusted_interference.droph (Untrusted_interference.restrict G.graph (fun v ->
29      match Untrusted_interference.Vertex.Map.find v C.coloring with
30      | Coloring.Spill ->
31          true
32      | Coloring.Color _ ->
33          false
34    ))
35    let verbose = false
36(*
37    let () =
38      if verbose then
39        Printf.printf "Starting stack slot allocation for %s.\n" f
40*)
41  end in
42
43  let module S = Spill.Color (H) in
44
45  (* Define a new function that consults both colorings at once. *)
46
47  let lookup r =
48   match r with
49      Types.Inl r ->
50       (match lookup r with
51       | Coloring.Spill ->
52           Interference.Decision_spill (Glue.matitanat_of_int (Untrusted_interference.Vertex.Map.find (Untrusted_interference.lookup H.graph r) S.coloring))
53       | Coloring.Color color ->
54           Interference.Decision_colour color)
55    | Types.Inr r -> Interference.Decision_colour r
56  in
57
58   { Interference.colouring = lookup; 
59     spilled_no = Glue.matitanat_of_int S.locals
60   }
Note: See TracBrowser for help on using the repository browser.