Initial import of l3c

[snipe.git] / codegen / colororder.sml

diff --git a/codegen/colororder.sml b/codegen/colororder.sml
index f533cead3e680c51c4a88d9e7f37b60f5097cba4..0f25863957933eeeace36c2d402fa82c31ef656e 100644 (file)
--- a/codegen/colororder.sml
+++ b/codegen/colororder.sml
@@ -1,4 +1,4 @@
-(* L2 Compiler
+(* 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>
@@ -6,10 +6,17 @@
 
 signature COLORORDER =
 sig
-  type igraph = (Temp.temp * x86.oper list) 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 : igraph -> ordering
+  val colororder : Igraph.graph * Temp.temp list -> ordering
 end
 
 structure ColorOrder :> COLORORDER =
@@ -17,12 +24,16 @@ struct
   structure T = Temp
   structure X = x86
   
-  type igraph = (Temp.temp * x86.oper list) 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 =
+  fun colororder (graph,temps) =
     let
-      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
@@ -34,15 +45,14 @@ struct
           val (chosen, w) = List.hd sorted     (* Grab the temp with the highest weight. *)
           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))
+            (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)
@@ -61,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