Initial import of l3c

[snipe.git] / codegen / colororder.sml

diff --git a/codegen/colororder.sml b/codegen/colororder.sml
index 588086dd64b988082272ddc49b10c9f8d624c4a5..0f25863957933eeeace36c2d402fa82c31ef656e 100644 (file)
--- a/codegen/colororder.sml
+++ b/codegen/colororder.sml
@@ -1,15 +1,22 @@
-(* L1 Compiler
- * Gathers tiberium, fires rockets
+(* L3 Compiler
  * Takes a interference graph and generates an ordering for coloring
  * Author: Joshua Wise <jwise@andrew.cmu.edu>
+ * Author: Chris Lu <czl@aundrew.cmu.edu>
  *)
 
 signature COLORORDER =
 sig
-  type tiberium = (Temp.temp * x86.oper list) list
-  type rockets = 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 igraph = OperSet.set TempMap.map
+  type ordering = Temp.temp list
   
-  val colororder : tiberium -> rockets
+  val colororder : Igraph.graph * Temp.temp list -> ordering
 end
 
 structure ColorOrder :> COLORORDER =
@@ -17,40 +24,35 @@ struct
   structure T = Temp
   structure X = x86
   
-  type tiberium = (Temp.temp * x86.oper list) list
-  type rockets = Temp.temp list
+  structure OperSet = Igraph.OperSet
+  structure LiveMap = Igraph.LiveMap
+  structure TempMap = Igraph.TempMap
+  
+  type igraph = OperSet.set TempMap.map
+  type ordering = Temp.temp list
   
-  fun colororder (graph : tiberium) : rockets =
+  fun colororder (graph,temps) =
     let
-      val () = print ("Ordering colors...\n");
-      val initialWeights = map (fn (t, _) => (t, 0)) graph
+      val initialWeights = TempMap.mapi (fn (t, _) => (t, 0)) graph
       
       fun sortWeights weights =        (* Sort the weights such that the largest is at left, ready to be grabbed. *)
         ListMergeSort.sort (fn ((_, a), (_, b)) => a < b) weights
-      
+
       (* Chooses one temporary to pick, and updates the weights. *)
       fun orderOne (weights : (Temp.temp * int) list) : Temp.temp * (Temp.temp * int) list =
         let
           val sorted = sortWeights weights
           val (chosen, w) = List.hd sorted     (* Grab the temp with the highest weight. *)
-          val () = print ("  Chose "^(Temp.name chosen)^" with weight "^(Int.toString w)^"\n");
           val remaining = List.tl sorted
-          val neighbors =      (* Grab all the neighbors for some given temp. *)
-            List.hd
-              (List.map (fn (_, neighbors) => neighbors)
-                (List.filter (fn (t, _) => T.compare (t, chosen) = EQUAL) graph))
-          val () = List.app
-                     (fn (X.TEMP t) => (print ("    Neighbor "^(Temp.name t)^"\n"))
-                       | (X.REG X.EAX) => (print "    Fixed color EAX\n")
-                       | (X.REG X.EDX) => (print "    Fixed color EDX\n")
-                       | _ => raise ErrorMsg.InternalError "Unknown neighbor type -- const?"
-                     ) neighbors;
+          val neighbors =                      (* Grab all the neighbors for some given temp. *)
+            (OperSet.listItems
+              (valOf (TempMap.find (graph, chosen))))
           val newWeights =
             List.map
               (fn (t, wt) =>
                 (t,
                   if (List.exists 
-                        (fn X.TEMP t' => (T.compare (t, t') = EQUAL)
+                        (fn X.TEMP t' => (T.eq (t, t'))
                           | _ => false)
                         neighbors)
                     then (wt + 1)
@@ -69,7 +71,9 @@ struct
           in
             chosen :: (keepOrdering newWeights)
           end
+
+      val ordered = keepOrdering (TempMap.listItems initialWeights)
     in
-      (keepOrdering initialWeights)
+      ordered @ (List.filter (fn a => not (List.exists (fn b => Temp.eq (a,b)) ordered)) temps)
     end
 end