Initial import of l2c

[snipe.git] / codegen / coloring.sml

(* L2 compiler
 * colorizer
 * colors a graph and returns a list of nodes with associated colors
 * Author: Joshua Wise <jwise@andrew.cmu.edu>
 * Author: Chris Lu <czl@andrew.cmu.edu>
 *)

signature COLORIZER =
sig
  type temps = Temp.temp list
  type colorlist = (Temp.temp * int) list
  type igraph = (Temp.temp * x86.oper list) list

  val colorize : temps -> igraph -> colorlist
end

structure Colorizer :> COLORIZER =
struct
  type temps = Temp.temp list
  type colorlist = (Temp.temp * int) list
  type igraph = (Temp.temp * x86.oper list) list
  
  structure X = x86
  
  (* val color_single : igraph -> Temp.temp * colorlist -> colorlist
   * color_single graph (temp, regs) => takes an interference graph, the temp to be colored, and the 
   * already-colored nodes, colors the temp, and adds it to the list
   * this is a helper function for the foldr in colorize
   *)
  fun color_single (graph: igraph) (temp, regs) =
    let
      (* Grab the list of interfering operands from the graph *)
      val interfere = case List.find (fn (temp',_) => Temp.compare (temp', temp) = EQUAL) graph
        of SOME(_, l) => l
         | NONE => raise ErrorMsg.InternalError "Temporary not found in graph"
      
      (* Grab the subset of those that are already colorized *)
      val colorized =
        List.filter
          (fn (t,_) =>
            List.exists
              (fn X.TEMP t' => Temp.compare (t, t') = EQUAL
                | _ => false)
              interfere
          ) regs
      
      (* Grab the subset of those that are fixed colors *)
      val fixeds =
        List.filter
          (fn X.REG _ => true
            | _ => false)
          interfere
      
      (* Grab the register number of the already-colorized ones *)
      val ints =
        (List.map
          (fn (_,i) => i)
          colorized)
        @ (List.map
          (fn X.REG X.EAX => 0
            | X.REG X.EDX => 3
            | X.REG X.ECX => 2
            | _ => raise ErrorMsg.InternalError "Bad kind of specreg")
          fixeds)
      (* Greedy-colorize -- pick the lowest number that isn't used by a neighbor *)
      fun greedy i l =
        if (List.exists (fn a => a = i) l)
          then greedy (i+1) l
          else i
      
      val newcolor = greedy 0 ints
      (* val () = print ("  Assigned color "^(Int.toString newcolor)^" to temp "^(Temp.name temp)^"\n") *)
    in
       (temp, (greedy 0 ints)) :: regs
    end

  (* val colorize : temps -> igraph -> colorlist
   * colorizes a graph given the graph representation and the order in which to color
   * nodes, returns a list of nodes numbered with their respective color *)
  fun colorize order graph = foldl (color_single graph) nil order

end