Initial import of l3c

[snipe.git] / codegen / coloring.sml

diff --git a/codegen/coloring.sml b/codegen/coloring.sml
index e1c2bcd1045f73bf535bc30ae1a689a54039ba06..1e08e1d7d6863fb9359eb60cd5126cb60c309610 100644 (file)
--- a/codegen/coloring.sml
+++ b/codegen/coloring.sml
@@ -1,23 +1,35 @@
-(* colorizer
- * Gathers tiberium, fires rockets
+(* L3 compiler
+ * colorizer
  * colors a graph and returns a list of nodes with associated colors
- * Author: Chris Lu <czl@andrew>
+ * Author: Joshua Wise <jwise@andrew.cmu.edu>
+ * Author: Chris Lu <czl@andrew.cmu.edu>
  *)
 
 signature COLORIZER =
 sig
-  type tiberium = Temp.temp list
+  structure OperSet : ORD_SET
+    where type Key.ord_key = x86.oper
+  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 = (Temp.temp * x86.oper list) list
+  type igraph = OperSet.set TempMap.map
 
-  val colorize : tiberium -> igraph -> colorlist
+  val colorize : temps -> Igraph.graph -> colorlist
 end
 
 structure Colorizer :> COLORIZER =
 struct
-  type tiberium = Temp.temp list
+  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 = (Temp.temp * x86.oper list) list
+  type igraph = OperSet.set TempMap.map
   
   structure X = x86
   
@@ -26,19 +38,20 @@ struct
    * 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) =
+  fun color_single (graph: Igraph.graph) (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 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.compare (t, t') = EQUAL
+              (fn X.TEMP t' => Temp.eq (t, t')
                 | _ => false)
               interfere
           ) regs
@@ -56,9 +69,8 @@ struct
           (fn (_,i) => i)
           colorized)
         @ (List.map
-          (fn X.REG X.EAX => 0
-            | X.REG X.EDX => 3
-            | _ => raise ErrorMsg.InternalError "Bad kind of specreg")
+             (fn X.REG a => X.regtonum a
+               | loss => raise ErrorMsg.InternalError ("Bad kind of specreg " ^ (X.prettyprint_oper X.Long loss )))
           fixeds)
       (* Greedy-colorize -- pick the lowest number that isn't used by a neighbor *)
       fun greedy i l =
@@ -67,12 +79,12 @@ struct
           else i
       
       val newcolor = greedy 0 ints
-      val () = print ("  Assigned color "^(Int.toString newcolor)^" to temp "^(Temp.name temp)^"\n")
+      (* val () = print ("  Assigned color "^(Int.toString newcolor)^" to temp "^(Temp.name temp)^"\n") *)
     in
        (temp, (greedy 0 ints)) :: regs
     end
 
-  (* val colorize : tiberium -> igraph -> colorlist
+  (* 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