Initial import of l1c

[snipe.git] / codegen / igraph.sml

(* interference graph generator
 * Gathers tiberium, fires rockets
 * Takes a list of interfering temps and generates the interference graph
 * Author: Chris Lu <czl@andrew>
 *)

signature IGRAPH =
sig
  type tiberium = x86.oper list list
  type rockets = (Temp.temp * x86.oper list) list
  val gengraph : tiberium -> rockets
end

structure Igraph :> IGRAPH =
struct
  type tiberium = x86.oper list list
  type rockets = (Temp.temp * x86.oper list) list
  structure X = x86
  
  (* val canonicalize : rockets -> rockets
   * canonicalize a => puts a in the canonical form by eliminating repeat nodes and edges
   * does so by sorting them first, then eliminating consecutive temps
   *)
  fun canonicalize orig =
    let
      val sorig = ListMergeSort.sort (fn ((a,_),(b,_)) => X.cmpoper (a,b) = LESS) orig
      fun merge ((x, xl)::(y, yl)::rl) = (case X.cmpoper (x,y) of EQUAL => merge ((x, xl @ yl)::rl) | _ => (x, xl) :: merge ((y, yl)::rl))
        | merge (a::nil) = [a]
        | merge nil = nil
      val ml = merge sorig
      fun uniq l =
        let
          val sl = ListMergeSort.sort (fn (a,b) => X.cmpoper (a,b) = LESS) l
          fun merge' (x::y::rl) = (case X.cmpoper (x,y) of EQUAL => merge' (x::rl) | _ => x :: merge' (y::rl))
            | merge' (x::nil) = [x]
            | merge' nil = nil
        in
          merge' sl
        end
    in
      List.map (fn (a, x) => (a, uniq x)) ml
    end

  (* val proc_one : Temp.temp list * rockets -> rockets
   * helper function to convert a list of interfering registers to a graph
   *)
  fun proc_one x =
        List.map
          (fn item1 => (item1, (List.filter (fn item2 => X.cmpoper(item1, item2) <> EQUAL) x)))
          x

  (* val gengraph : tiberium -> rockets
   * generates the interference graph from a list of interfering temps
   * by creating separate interference graphs for each line, concatenating them,
   * and putting them in canonical form
   *)
  fun gengraph x =
    let
      val igraph' = canonicalize (List.concat (List.map proc_one x))
    in
      foldr
        (fn ((a,l),b) => case a
          of X.REG(_) => b
           | X.TEMP(t) => (t,l)::b 
           | _ => raise ErrorMsg.InternalError "I'm a doooodyyyheaadddd"
        )
        nil
        igraph'
    end

end