Initial import of l3c

[snipe.git] / codegen / coloring.sml

diff --git a/codegen/coloring.sml b/codegen/coloring.sml
index eeca849b5d10a68ef91e0079a374ba4545dffb8b..1e08e1d7d6863fb9359eb60cd5126cb60c309610 100644 (file)
--- a/codegen/coloring.sml
+++ b/codegen/coloring.sml
@@ -1,4 +1,4 @@
-(* L2 compiler
+(* L3 compiler
  * colorizer
  * colors a graph and returns a list of nodes with associated colors
  * Author: Joshua Wise <jwise@andrew.cmu.edu>
@@ -7,18 +7,29 @@
 
 signature COLORIZER =
 sig
+  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 : temps -> igraph -> colorlist
+  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 = (Temp.temp * x86.oper list) list
+  type igraph = OperSet.set TempMap.map
   
   structure X = x86
   
@@ -27,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
@@ -57,10 +69,8 @@ struct
           (fn (_,i) => i)
           colorized)
         @ (List.map
-          (fn X.REG X.EAX => 0
-            | X.REG X.EDX => 3
-            | X.REG X.ECX => 2
-            | _ => 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 =