Code generation.

[snipe.git] / codegen / coloring.sml

(* L3 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
  structure OperSet : ORD_SET
    where type Key.ord_key = x86.basicop
  structure LiveMap : ORD_MAP
    where type Key.ord_key = int
  structure TempMap : ORD_MAP
    where type Key.ord_key = Temp.temp

  type temps = Temp.temp list
  type colorlist = (Temp.temp * int) list
  type igraph = OperSet.set TempMap.map

  val colorize : temps -> Igraph.graph -> colorlist
end

structure Colorizer :> COLORIZER =
struct
  structure OperSet = Igraph.OperSet
  structure LiveMap = Igraph.LiveMap
  structure TempMap = Igraph.TempMap

  type temps = Temp.temp list
  type colorlist = (Temp.temp * int) list
  type igraph = OperSet.set TempMap.map
  
  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.graph) (temp, regs) =
    let
      (* Grab the set of interfering operands from the graph *)
      val interfere = case TempMap.find (graph, temp)
        of SOME(l) => OperSet.listItems l
         | NONE => []
(*       | 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.eq (t, t')
                | _ => 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 a => X.regtonum a
               | loss => raise ErrorMsg.InternalError ("Bad kind of specreg " ^ (X.pp_oper (loss, Temp.Long))))
          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