codegen/coloring.sml

   1 (* L3 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   structure OperSet : ORD_SET
  11     where type Key.ord_key = x86.oper
  12   structure LiveMap : ORD_MAP
  13     where type Key.ord_key = int
  14   structure TempMap : ORD_MAP
  15     where type Key.ord_key = Temp.temp
  16
  17   type temps = Temp.temp list
  18   type colorlist = (Temp.temp * int) list
  19   type igraph = OperSet.set TempMap.map
  20
  21   val colorize : temps -> Igraph.graph -> colorlist
  22 end
  23
  24 structure Colorizer :> COLORIZER =
  25 struct
  26   structure OperSet = Igraph.OperSet
  27   structure LiveMap = Igraph.LiveMap
  28   structure TempMap = Igraph.TempMap
  29
  30   type temps = Temp.temp list
  31   type colorlist = (Temp.temp * int) list
  32   type igraph = OperSet.set TempMap.map
  33
  34   structure X = x86
  35
  36   (* val color_single : igraph -> Temp.temp * colorlist -> colorlist
  37    * color_single graph (temp, regs) => takes an interference graph, the temp to be colored, and the
  38    * already-colored nodes, colors the temp, and adds it to the list
  39    * this is a helper function for the foldr in colorize
  40    *)
  41   fun color_single (graph: Igraph.graph) (temp, regs) =
  42     let
  43       (* Grab the set of interfering operands from the graph *)
  44       val interfere = case TempMap.find (graph, temp)
  45         of SOME(l) => OperSet.listItems l
  46          | NONE => []
  47 (*       | NONE => raise ErrorMsg.InternalError "Temporary not found in graph" *)
  48
  49       (* Grab the subset of those that are already colorized *)
  50       val colorized =
  51         List.filter
  52           (fn (t,_) =>
  53             List.exists
  54               (fn X.TEMP t' => Temp.eq (t, t')
  55                 | _ => false)
  56               interfere
  57           ) regs
  58
  59       (* Grab the subset of those that are fixed colors *)
  60       val fixeds =
  61         List.filter
  62           (fn X.REG _ => true
  63             | _ => false)
  64           interfere
  65
  66       (* Grab the register number of the already-colorized ones *)
  67       val ints =
  68         (List.map
  69           (fn (_,i) => i)
  70           colorized)
  71         @ (List.map
  72              (fn X.REG a => X.regtonum a
  73                | loss => raise ErrorMsg.InternalError ("Bad kind of specreg " ^ (X.prettyprint_oper X.Long loss )))
  74           fixeds)
  75       (* Greedy-colorize -- pick the lowest number that isn't used by a neighbor *)
  76       fun greedy i l =
  77         if (List.exists (fn a => a = i) l)
  78           then greedy (i+1) l
  79           else i
  80
  81       val newcolor = greedy 0 ints
  82       (* val () = print ("  Assigned color "^(Int.toString newcolor)^" to temp "^(Temp.name temp)^"\n") *)
  83     in
  84        (temp, (greedy 0 ints)) :: regs
  85     end
  86
  87   (* val colorize : temps -> igraph -> colorlist
  88    * colorizes a graph given the graph representation and the order in which to color
  89    * nodes, returns a list of nodes numbered with their respective color *)
  90   fun colorize order graph = foldl (color_single graph) nil order
  91
  92 end