first version of the package

[pkg-cerco/acc.git] / src / utilities / coloring.ml

(* Pasted from Pottier's PP compiler *)

open ERTL
open Interference
open Printf

(* ------------------------------------------------------------------------- *)
(* Decisions. *)

(* A decision is of the form either [Spill] -- the vertex could
   not be colored and should be spilled into a stack slot -- or
   [Color] -- the vertex was assigned a hardware register. *)

type decision =
  | Spill
  | Color of I8051.register

(* [print_decision] turns a decision into a string. *)

let print_decision = function
  | Spill ->
      "spilled"
  | Color hwr ->
      Printf.sprintf "colored $%s" (I8051.print_register hwr)

(* ------------------------------------------------------------------------- *)
(* Colorings. *)

(* A coloring is a partial function of graph vertices to decisions.
   Vertices that are not in the domain of the coloring are waiting for
   a decision to be made. *)

type coloring =
    decision Vertex.Map.t

(* ------------------------------------------------------------------------- *)
(* Sets of colors. *)

module ColorSet =
  I8051.RegisterSet

(* [add_color coloring r colors] returns the union of the set [colors] with
   the element [color], if the vertex [r] was assigned color [color], and
   returns [colors] if [r] was spilled. *)

let add_color coloring r colors =
  match Vertex.Map.find r coloring with
  | Spill ->
      colors
  | Color color ->
      ColorSet.add color colors

(* These are the colors that we work with. *)

let colors : ColorSet.t =
  I8051.allocatable

(* This is the number of available colors. *)

let k : int =
  ColorSet.cardinal colors

(* ------------------------------------------------------------------------- *)
(* Choices of colors. *)

(* [forbidden_colors graph coloring v] is the set of colors that cannot be
   assigned to [v] considering [coloring], a coloring of every vertex in
   [graph] except [v]. *)
(* This takes into account [v]'s possible interferences with hardware
   registers, which are viewed as forbidden colors. *)

let forbidden_colors graph coloring v =
  Vertex.Set.fold (add_color coloring) (ipp graph v) (iph graph v)

(* ------------------------------------------------------------------------- *)
(* Low and high vertices. *)

(* A vertex is low (or insignificant) if its degree is less than [k].
   It is high (or significant) otherwise. *)

let high graph v =
  degree graph v >= k

(* [high_neighbors graph v] is the set of all high neighbors of [v]. *)

let high_neighbors graph v =
  Vertex.Set.filter (high graph) (ipp graph v)

(* ------------------------------------------------------------------------- *)
(* George's conservative coalescing criterion. *)

(* According to this criterion, two vertices [a] and [b] can be
   coalesced, suppressing [a] and keeping [b], if the following
   two conditions hold:

     1. (pseudo-registers) every high neighbor of [a] is a neighbor of [b];
     2. (hardware registers) every hardware register that interferes with
        [a] also interferes with [b].

   This means that, after all low vertices have been removed, any color that
   is suitable for [b] is also suitable for [a]. *)

let georgepp graph (a, b) =
  Vertex.Set.subset (high_neighbors graph a) (ipp graph b) &&
  I8051.RegisterSet.subset (iph graph a) (iph graph b)

(* According to this criterion, a vertex [a] and a hardware register
   [c] can be coalesced (that is, [a] can be assigned color [c]) if
   every high neighbor of [a] interferes with [c]. *)

let georgeph graph (a, c) =
  Vertex.Set.fold (fun neighbor accu ->
    accu &&
    I8051.RegisterSet.mem c (iph graph neighbor)
  ) (high_neighbors graph a) true

(* ------------------------------------------------------------------------- *)
(* Here is the coloring algorithm. *)

module Color (G : sig

  val graph: graph
  val uses: Register.t -> int
  val verbose: bool

end) = struct

  (* The cost function heuristically evaluates how much it might cost
     to spill vertex [v]. Here, the cost is the ratio of the number of
     uses of the pseudo-registers represented by [v] by the degree of
     [v]. One could also take into account the number of nested loops
     that the uses appear within, but that is not done here. *)

  let cost graph v =
    let uses =
      Register.Set.fold (fun r uses ->
        G.uses r + uses
      ) (registers graph v) 0
    in
    (float_of_int uses) /. (float_of_int (degree graph v))

  (* The algorithm maintains a transformed graph as it runs. It is
     obtained from the original graph by removing, coalescing, and
     freezing vertices. *)

  (* Each of the functions that follow returns a coloring of the graph
     that it is passed. These functions correspond to the various
     states of the algorithm (simplification, coalescing, freezing,
     spilling, selection). The function [simplification] is the
     initial state. *)

  (* [simplification] removes non-move-related nodes of low degree. *)

  let rec simplification graph : coloring =

    match lowest_non_move_related graph with

    | Some (v, d) when d < k ->

        (* We found a non-move-related node [v] of low degree. Color
           the rest of the graph, then color [v]. This is what I call
           selection. *)

        if G.verbose then
          printf "Simplifying low vertex: %s.\n%!" (print_vertex graph v);

        selection graph v

    | _ ->

        (* There are no non-move-related nodes of low degree.
           Could not simplify further. Start coalescing. *)

        coalescing graph

  (* [coalescing] looks for a preference edge that can be collapsed.
     It is called after [simplification], so it is known, at this
     point, that all nodes of low degree are move-related. *)

  and coalescing graph : coloring =

    (* Find a preference edge between two vertices that passes
       George's criterion.

       [pppick] examines all preference edges in the graph, so its use
       is inefficient. It would be more efficient instead to examine
       only areas of the graph that have changed recently. More
       precisely, it is useless to re-examine a preference edge that
       did not pass George's criterion the last time it was examined
       and whose neighborhood has not been modified by simplification,
       coalescing or freezing. Indeed, in that case, and with a
       sufficiently large definition of ``neighborhood'', this edge is
       guaranteed to again fail George's criterion. It would be
       possible to modify the [Interference.graph] data structure so
       as to keep track of which neighborhoods have been modified and
       provide a specialized, more efficient version of [pppick]. This
       is not done here. *)

    match pppick graph (georgepp graph) with

    | Some (a, b) ->

        if G.verbose then
          printf "Coalescing %s with %s.\n%!" (print_vertex graph a) (print_vertex graph b);

        (* Coalesce [a] with [b] and color the remaining graph. *)

        let coloring = simplification (coalesce graph a b) in

        (* Assign [a] the same color as [b]. *)

        Vertex.Map.add a (Vertex.Map.find b coloring) coloring

    | None ->

        (* Find a preference edge between a vertex and a hardware
           register that passes George's criterion. Like [pppick],
           [phpick] is slow. *)

        match phpick graph (georgeph graph) with

        | Some (a, c) ->

            if G.verbose then
              printf "Coalescing %s with $%s.\n%!" (print_vertex graph a) (I8051.print_register c);

            (* Coalesce [a] with [c] and color the remaining graph. *)

            let coloring = simplification (coalesceh graph a c) in

            (* Assign [a] the color [c]. *)

            Vertex.Map.add a (Color c) coloring

        | None ->

            (* Could not coalesce further. Start freezing. *)

            freezing graph

  (* [freezing] begins after [simplification] and [coalescing] are
     finished, so it is known, at this point, that all nodes of low
     degree are move-related and no coalescing is possible. [freezing]
     looks for a node of low degree (which must be move-related) and
     removes the preference edges that it carries. This potentially
     opens new opportunities for simplification and coalescing. *)

  and freezing graph : coloring =

    match lowest graph with

    | Some (v, d) when d < k ->

        (* We found a move-related node [v] of low degree.
           Freeze it and start over. *)

        if G.verbose then
          printf "Freezing low vertex: %s.\n%!" (print_vertex graph v);

        simplification (freeze graph v)

    | _ ->

        (* Could not freeze further. Start spilling. *)

        spilling graph

  (* [spilling] begins after [simplification], [coalescing], and
     [freezing] are finished, so it is known, at this point, that
     there are no nodes of low degree.

     Thus, we are facing a potential spill. However, we do optimistic
     coloring: we do not spill a vertex right away, but proceed
     normally, just as if we were doing simplification. So, we pick a
     vertex [v], remove it, and check whether a color can be assigned
     to [v] only after coloring what remains of the graph.

     It is crucial to pick a vertex that has few uses in the code. It
     would also be good to pick one that has high degree, as this will
     help color the rest of the graph. Thus, we pick a vertex that has
     minimum cost, where the cost is obtained as the ratio of the
     number of uses of the pseudo-registers represented by this vertex
     in the code by the degree of the vertex. One could also take into
     account the number of nested loops that the uses appear within,
     but that is not done here.

     The use of [minimum] is inefficient, because this function
     examines all vertices in the graph. It would be possible to
     augment the [Interference.graph] data structure so as to keep
     track of the cost associated with each vertex and provide
     efficient access to a minimum cost vertex. This is not done
     here. *)

  and spilling graph : coloring =

    match minimum (cost graph) graph with
    | Some v ->
        
        if G.verbose then
          printf "Spilling high vertex: %s.\n%!" (print_vertex graph v);
        
        selection graph v

    | None ->

        (* The graph is empty. Return an empty coloring. *)

        Vertex.Map.empty

  (* [selection] removes the vertex [v] from the graph, colors the
     remaining graph, then selects a color for [v].

     If [v] is low, that is, if [v] has degree less than [k], then at
     least one color must still be available for [v], regardless of
     how the remaining graph was colored.

     If [v] was a potential spill, then it is not certain that a color
     is still available. If one is, though, then we are rewarded for
     being optimistic. If none is, then [v] becomes an actual
     spill. *)

  and selection graph v : coloring =

    (* Remove [v] from the graph and color what remains. *)

    let coloring = simplification (remove graph v) in

    (* Determine which colors are allowed. *)

    let allowed = ColorSet.diff colors (forbidden_colors graph coloring v) in

    (* Make a decision.

       We pick a color randomly among those that are allowed. One could
       attempt to use biased coloring, that is, to pick a color that seems
       desirable (or not undesirable) according to the preference edges
       found in the initial graph. But that is probably not worth the
       trouble. *)

    let decision =
      try
        Color (ColorSet.choose allowed)
      with Not_found ->
        Spill
    in

    if G.verbose then
      printf "Decision concerning %s: %s.\n%!" (print_vertex graph v) (print_decision decision);

    (* Record our decision and return. *)

    Vertex.Map.add v decision coloring

  (* Run the algorithm. *)

  let coloring =
    simplification G.graph

end