codegen/colororder.sml

   1 (* L2 Compiler
   2  * Takes a interference graph and generates an ordering for coloring
   3  * Author: Joshua Wise <jwise@andrew.cmu.edu>
   4  * Author: Chris Lu <czl@aundrew.cmu.edu>
   5  *)
   6
   7 signature COLORORDER =
   8 sig
   9   type igraph = (Temp.temp * x86.oper list) list
  10   type ordering = Temp.temp list
  11
  12   val colororder : igraph -> ordering
  13 end
  14
  15 structure ColorOrder :> COLORORDER =
  16 struct
  17   structure T = Temp
  18   structure X = x86
  19
  20   type igraph = (Temp.temp * x86.oper list) list
  21   type ordering = Temp.temp list
  22
  23   fun colororder graph =
  24     let
  25       val initialWeights = map (fn (t, _) => (t, 0)) graph
  26
  27       fun sortWeights weights = (* Sort the weights such that the largest is at left, ready to be grabbed. *)
  28         ListMergeSort.sort (fn ((_, a), (_, b)) => a < b) weights
  29
  30       (* Chooses one temporary to pick, and updates the weights. *)
  31       fun orderOne (weights : (Temp.temp * int) list) : Temp.temp * (Temp.temp * int) list =
  32         let
  33           val sorted = sortWeights weights
  34           val (chosen, w) = List.hd sorted      (* Grab the temp with the highest weight. *)
  35           val remaining = List.tl sorted
  36           val neighbors =                       (* Grab all the neighbors for some given temp. *)
  37             List.hd
  38               (List.map (fn (_, neighbors) => neighbors)
  39                 (List.filter (fn (t, _) => T.compare (t, chosen) = EQUAL) graph))
  40           val newWeights =
  41             List.map
  42               (fn (t, wt) =>
  43                 (t,
  44                   if (List.exists
  45                         (fn X.TEMP t' => (T.compare (t, t') = EQUAL)
  46                           | _ => false)
  47                         neighbors)
  48                     then (wt + 1)
  49                     else wt
  50                 )
  51               ) remaining
  52         in
  53           (chosen, newWeights)
  54         end
  55
  56       (* Recursively order until we run out of things to order. *)
  57       fun keepOrdering (nil : (Temp.temp * int) list) : Temp.temp list = nil
  58         | keepOrdering (weights) =
  59           let
  60             val (chosen, newWeights) = orderOne weights
  61           in
  62             chosen :: (keepOrdering newWeights)
  63           end
  64     in
  65       (keepOrdering initialWeights)
  66     end
  67 end