codegen/coloring.sml

   1 (* L2 compiler
   2  * colorizer
   3  * colors a graph and returns a list of nodes with associated colors
   4  * Author: Joshua Wise <jwise@andrew.cmu.edu>
   5  * Author: Chris Lu <czl@andrew.cmu.edu>
   6  *)
   7
   8 signature COLORIZER =
   9 sig
  10   type temps = Temp.temp list
  11   type colorlist = (Temp.temp * int) list
  12   type igraph = (Temp.temp * x86.oper list) list
  13
  14   val colorize : temps -> igraph -> colorlist
  15 end
  16
  17 structure Colorizer :> COLORIZER =
  18 struct
  19   type temps = Temp.temp list
  20   type colorlist = (Temp.temp * int) list
  21   type igraph = (Temp.temp * x86.oper list) list
  22
  23   structure X = x86
  24
  25   (* val color_single : igraph -> Temp.temp * colorlist -> colorlist
  26    * color_single graph (temp, regs) => takes an interference graph, the temp to be colored, and the
  27    * already-colored nodes, colors the temp, and adds it to the list
  28    * this is a helper function for the foldr in colorize
  29    *)
  30   fun color_single (graph: igraph) (temp, regs) =
  31     let
  32       (* Grab the list of interfering operands from the graph *)
  33       val interfere = case List.find (fn (temp',_) => Temp.compare (temp', temp) = EQUAL) graph
  34         of SOME(_, l) => l
  35          | NONE => raise ErrorMsg.InternalError "Temporary not found in graph"
  36
  37       (* Grab the subset of those that are already colorized *)
  38       val colorized =
  39         List.filter
  40           (fn (t,_) =>
  41             List.exists
  42               (fn X.TEMP t' => Temp.compare (t, t') = EQUAL
  43                 | _ => false)
  44               interfere
  45           ) regs
  46
  47       (* Grab the subset of those that are fixed colors *)
  48       val fixeds =
  49         List.filter
  50           (fn X.REG _ => true
  51             | _ => false)
  52           interfere
  53
  54       (* Grab the register number of the already-colorized ones *)
  55       val ints =
  56         (List.map
  57           (fn (_,i) => i)
  58           colorized)
  59         @ (List.map
  60           (fn X.REG X.EAX => 0
  61             | X.REG X.EDX => 3
  62             | X.REG X.ECX => 2
  63             | _ => raise ErrorMsg.InternalError "Bad kind of specreg")
  64           fixeds)
  65       (* Greedy-colorize -- pick the lowest number that isn't used by a neighbor *)
  66       fun greedy i l =
  67         if (List.exists (fn a => a = i) l)
  68           then greedy (i+1) l
  69           else i
  70
  71       val newcolor = greedy 0 ints
  72       (* val () = print ("  Assigned color "^(Int.toString newcolor)^" to temp "^(Temp.name temp)^"\n") *)
  73     in
  74        (temp, (greedy 0 ints)) :: regs
  75     end
  76
  77   (* val colorize : temps -> igraph -> colorlist
  78    * colorizes a graph given the graph representation and the order in which to color
  79    * nodes, returns a list of nodes numbered with their respective color *)
  80   fun colorize order graph = foldl (color_single graph) nil order
  81
  82 end