Initial import of l5c

[snipe.git] / codegen / igraph.sml

(* L3 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
  structure OperSet : ORD_SET
    where type Key.ord_key = x86.basicop
  structure LiveMap : ORD_MAP
    where type Key.ord_key = int
  structure TempMap : ORD_MAP
    where type Key.ord_key = Temp.temp
      
  type predicates = Liveness.predicates
  type livenesses = Liveness.livenesses
  type graph = OperSet.set TempMap.map
  val gengraph : predicates * livenesses -> graph * Temp.temp list
end

structure Igraph :> IGRAPH =
struct
  structure OperSet = Liveness.OperSet
  structure LiveMap = Liveness.LiveMap

  structure TempSet = BinarySetFn (
    struct
      type ord_key = Temp.temp
      val compare = Temp.compare
    end
  )

  structure TempMap = SplayMapFn (
    struct
      type ord_key = Temp.temp
      val compare = Temp.compare
    end)
  
  type predicates = Liveness.predicates
  type livenesses = Liveness.livenesses
  type graph = OperSet.set TempMap.map
  
  structure X = x86
  
  fun add_temp_interfere g (t, oper) =
    let
      val set = (valOf (TempMap.find (g, t))) handle Option => OperSet.empty
    in
      TempMap.insert (g, t, OperSet.union (set, OperSet.singleton oper))
    end
  
  fun add_interfere g (o1, o2) =
    let
      val g = case o1
        of (X.TEMP t) => add_temp_interfere g (t, o2)
         | _ => g
    in
      case o2
        of (X.TEMP t) => add_temp_interfere g (t, o1)
         | _ => g
    end

  fun alltemps preds =
    LiveMap.foldr
      (fn (ps, ts) => List.foldr
        (fn (Liveness.DEF(X.TEMP t), ts') => TempSet.add (ts', t)
          | (Liveness.USE(X.TEMP t), ts') => TempSet.add (ts', t)
          | (_, ts') => ts')
        ts
        ps
      )
      TempSet.empty
      preds

  (* 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 (preds, lives) : graph * Temp.temp list =
    (LiveMap.foldri
      (fn (ln, predlist, map) =>
        let
          val ismove = Liveness.ismove predlist
        in
          List.foldr
            (fn (oper, map) =>
              List.foldr
                (fn (ln', map) =>
                  let
                    val liveat = valOf (LiveMap.find (lives, ln'))
                    val liveat =
                      if not ismove
                      then liveat
                      else OperSet.difference
                             (liveat,
                              OperSet.addList (OperSet.empty, Liveness.uses predlist))
                  in
                    OperSet.foldr
                      (fn (oper', map) => add_interfere map (oper, oper'))
                      map
                      liveat
                  end)
                map
                (Liveness.succs predlist))
            map
            (Liveness.defs predlist)
        end
        )
      TempMap.empty
      preds,
      TempSet.listItems (alltemps preds))
end