extracted/untrusted/coloring.mli

   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
  13 type decision =
  14   | Spill
  15   | Color of I8051.register
  16
  17 type 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
  27 module Color (G : sig
  28
  29   val graph: Untrusted_interference.graph
  30   val uses: Registers.register -> int
  31   val verbose: bool
  32
  33 end) : sig
  34
  35   val coloring: coloring
  36
  37 end
  38