codegen/coloring.sml

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