Initial import of l5c

[snipe.git] / codegen / colororder.sml

diff --git a/codegen/colororder.sml b/codegen/colororder.sml
index 588086dd64b988082272ddc49b10c9f8d624c4a5..16dd163067d0c600a8d8c0e544e3c27ee097c01d 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.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 : tiberium -> rockets
+  val colororder : Igraph.graph * Temp.temp list -> ordering
 end
 
 structure ColorOrder :> COLORORDER =
@@ -17,40 +24,45 @@ 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
-      
-      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
+      val initialWeights = TempMap.mapi (fn (t, _) => (t, 0)) graph
       
       (* 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 (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. *)
+            (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 +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