signature COLORORDER =
sig
structure OperSet : ORD_SET
- where type Key.ord_key = x86.oper
+ where type Key.ord_key = x86.basicop
structure LiveMap : ORD_MAP
where type Key.ord_key = int
structure TempMap : ORD_MAP
let
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. *)
(OperSet.listItems
(valOf (TempMap.find (graph, chosen))))