Last change
on this file since 2740 was
2740,
checked in by sacerdot, 8 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  

3  let 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.