X-Git-Url: http://git.joshuawise.com/snipe.git/blobdiff_plain/0a24e44d4e9f82f8d3d83de8e58c83c8cf2868b6..5c79bb689ab446551bc7ec4497e6c9b75582837e:/codegen/colororder.sml

diff --git a/codegen/colororder.sml b/codegen/colororder.sml
index f533cea..16dd163 100644
--- 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.basicop
+  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,32 +24,45 @@ 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
-
       (* 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 remaining = List.tl sorted
+          val (chosen, w) =
+            foldr
+              (fn ((t1, w1), (t2, w2)) =>
+                if (w2 > w1)
+                then (t2, w2)
+                else (t1, w1))
+              (Temp.new "emarnus" Temp.Word, ~9999)
+              weights
+              
+          fun ditchOne f nil = nil	(* Special case of filter, which bails out after it removes one. *)
+            | ditchOne f (h::l) =
+              if f h
+              then l
+              else h::(ditchOne f l)
+          val remaining = ditchOne (fn (t, w) => Temp.eq (t, chosen)) weights
+          
           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 +81,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