Initial import of l2c

[snipe.git] / codegen / igraph.sml

(* L2 compiler
 * interference graph generator
 * Takes a list of interfering temps and generates the interference graph
 * Author: Chris Lu <czl@andrew.cmu.edu>
 *)

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

structure Igraph :> IGRAPH =
struct
  type interferences = x86.oper list list
  type graph = (Temp.temp * x86.oper list) list
  structure X = x86
  
  (* val canonicalize : graph -> graph
   * 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) = (if X.opereq (x,y) then merge ((x, List.revAppend(yl,xl))::rl) else (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) = (if X.opereq (x,y) then merge' (x::rl) else 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 * graph -> graph
   * 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 => not (X.opereq(item1, item2))) x)))
          x

  (* val gengraph : interferences -> graph
   * 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 "Non-live register type found in igraph"
        )
        nil
        igraph'
    end

end