source: extracted/untrusted/coloring.mli @ 2968

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

Porting the graph colouring stuff from the untrusted prototype to the extracted
code.

File size: 1.1 KB
Line 
1(* Pasted from Pottier's PP compiler *)
2
3(** This module performs graph coloring. It is used for register
4    allocation. *)
5
6(* A coloring is a partial function of graph vertices to decisions,
7   where a decision is of the form either [Spill] -- the vertex could
8   not be colored and should be spilled into a stack slot -- or
9   [Color] -- the vertex was assigned a hardware register. Vertices
10   that are not in the domain of the coloring are waiting for a
11   decision to be made. *)
12
13type decision =
14  | Spill
15  | Color of I8051.register
16
17type coloring =
18    decision Untrusted_interference.Vertex.Map.t
19
20(* Here is the coloring algorithm. Out of an interference graph, it
21   produces a coloring. The client should provide information about
22   the number of uses of each pseudo-register; the higher the number,
23   the more undesirable it is to spill that pseudo-register. If the
24   [verbose] flag is set, the algorithm prints information messages to
25   the standard output channel. *)
26
27module Color (G : sig
28
29  val graph: Untrusted_interference.graph
30  val uses: Registers.register -> int
31  val verbose: bool
32
33end) : sig
34
35  val coloring: coloring
36
37end
38
Note: See TracBrowser for help on using the repository browser.