codegen/igraph.sml

   1 (* L2 compiler
   2  * interference graph generator
   3  * Takes a list of interfering temps and generates the interference graph
   4  * Author: Chris Lu <czl@andrew.cmu.edu>
   5  *)
   6
   7 signature IGRAPH =
   8 sig
   9   type interferences = x86.oper list list
  10   type graph = (Temp.temp * x86.oper list) list
  11   val gengraph : interferences -> graph
  12 end
  13
  14 structure Igraph :> IGRAPH =
  15 struct
  16   type interferences = x86.oper list list
  17   type graph = (Temp.temp * x86.oper list) list
  18   structure X = x86
  19
  20   (* val canonicalize : graph -> graph
  21    * canonicalize a => puts a in the canonical form by eliminating repeat nodes and edges
  22    * does so by sorting them first, then eliminating consecutive temps
  23    *)
  24   fun canonicalize orig =
  25     let
  26       val sorig = ListMergeSort.sort (fn ((a,_),(b,_)) => X.cmpoper (a,b) = LESS) orig
  27       fun merge ((x, xl)::(y, yl)::rl) = (if X.opereq (x,y) then merge ((x, List.revAppend(yl,xl))::rl) else (x, xl) :: merge ((y, yl)::rl))
  28         | merge (a::nil) = [a]
  29         | merge nil = nil
  30       val ml = merge sorig
  31       fun uniq l =
  32         let
  33           val sl = ListMergeSort.sort (fn (a,b) => X.cmpoper (a,b) = LESS) l
  34           fun merge' (x::y::rl) = (if X.opereq (x,y) then merge' (x::rl) else x :: merge' (y::rl))
  35             | merge' (x::nil) = [x]
  36             | merge' nil = nil
  37         in
  38           merge' sl
  39         end
  40     in
  41       List.map (fn (a, x) => (a, uniq x)) ml
  42     end
  43
  44   (* val proc_one : Temp.temp list * graph -> graph
  45    * helper function to convert a list of interfering registers to a graph
  46    *)
  47   fun proc_one x =
  48         List.map
  49           (fn item1 => (item1, (List.filter (fn item2 => not (X.opereq(item1, item2))) x)))
  50           x
  51
  52   (* val gengraph : interferences -> graph
  53    * generates the interference graph from a list of interfering temps
  54    * by creating separate interference graphs for each line, concatenating them,
  55    * and putting them in canonical form
  56    *)
  57   fun gengraph x =
  58     let
  59       val igraph' = canonicalize (List.concat (List.map proc_one x))
  60     in
  61       foldr
  62         (fn ((a,l),b) => case a
  63           of X.REG(_) => b
  64            | X.TEMP(t) => (t,l)::b
  65            | _ => raise ErrorMsg.InternalError "Non-live register type found in igraph"
  66         )
  67         nil
  68         igraph'
  69     end
  70
  71 end