Initial import of l2c

[snipe.git] / codegen / liveness.sml

(* L2 Compiler
 * Turns pseudoasm into liveness-annotated pseudoasm
 * Author: Chris Lu <czl@andrew.cmu.edu>
 * Author: Joshua Wise <jwise@andrew.cmu.edu>
 *)

signature LIVENESS =
sig

  type live = int * x86.oper list
  type pseudoasm = x86.insn list
  type livenesses = x86.oper list list

  type ident = int
  datatype pred = DEF of x86.oper | USE of x86.oper | SUCC of ident

  val liveness : pseudoasm -> livenesses
  val prettyprint : x86.oper list -> string
end

structure Liveness :> LIVENESS =
struct
  structure T = Temp
  structure X = x86


  type live = int * x86.oper list
  type pseudoasm = X.insn list
  type numasm = (int * X.insn) list
  type livenesses = X.oper list list

  type ident = int
  datatype pred = DEF of X.oper | USE of X.oper | SUCC of ident

  (* val number : pseudoasm -> numasm
   * numbers the instructions!
   *)

  fun number instrs =
    let
      val nums = List.tabulate (List.length instrs, (fn i => i))
    in
      ListPair.zip (nums,instrs)
    end

  (* val defusesucc : numasm -> (ident * pred list) list
   * generates def/use/succ predicates according to rules
   *)

  fun defusesucc l =
    let
      fun findlabel (lb) =
            Option.valOf
              (foldr (fn ((n, X.LABEL lb'), NONE) => if (Label.compare (lb, lb') = EQUAL) then SOME n else NONE
                       | (_, old) => old) NONE l)
      
      (* val defhit/usehit : X.oper -> pred list
       * helper functions to discard constant operands *)
      fun defhit (a as X.CONST(_)) = nil
        | defhit (a) = [DEF(a)]

      fun usehit (a as X.CONST(_)) = nil
        | usehit (a) = [USE(a)]

      (* val gendef : ident * X.insn -> ident * pred list
       * generates the def/use/succ predicates for a single insn
       *)
      fun gendef (n, X.DIRECTIVE(_))           = (n, nil)
        | gendef (n, X.COMMENT(_))             = (n, nil)
        | gendef (n, X.MOVL(dest, src))        = (n, defhit dest @ usehit src @ [SUCC(n+1)])
        | gendef (n, X.SUBL(dest, src))        = (n, defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
        | gendef (n, X.IMUL(dest, src))        = (n, defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
        | gendef (n, X.IMUL3(dest, src, _))    = (n, defhit dest @ usehit src @ [SUCC(n+1)])
        | gendef (n, X.ADDL(dest, src))        = (n, defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
        | gendef (n, X.IDIVL(src))             = (n, usehit src @ [DEF(X.REG(X.EAX)), DEF(X.REG(X.EDX)),
                                                                   USE(X.REG(X.EAX)), USE(X.REG(X.EDX)),
                                                                   SUCC(n+1)])
        | gendef (n, X.CLTD)                   = (n, [USE(X.REG(X.EAX)), DEF(X.REG(X.EDX)), SUCC(n+1)])
        | gendef (n, X.SALL(dest, shft))       = (n, defhit dest @ usehit shft @ usehit dest @ [SUCC(n+1)])
        | gendef (n, X.SARL(dest, shft))       = (n, defhit dest @ usehit shft @ usehit dest @ [SUCC(n+1)])
        | gendef (n, X.NEG(src))               = (n, defhit src @ usehit src @ [SUCC(n+1)])
        | gendef (n, X.NOTL(src))              = (n, defhit src @ usehit src @ [SUCC(n+1)])
        | gendef (n, X.ANDL(dest, src))        = (n, defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
        | gendef (n, X.ORL(dest, src))         = (n, defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
        | gendef (n, X.XORL(dest, src))        = (n, defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
        | gendef (n, X.CMPL(dest, src))        = (n, usehit dest @ usehit src @ [SUCC(n+1)])
        | gendef (n, X.TEST(dest, src))        = (n, usehit dest @ usehit src @ [SUCC(n+1)])
        | gendef (n, X.SETNE(dest))            = (n, defhit dest @ [SUCC(n+1)])
        | gendef (n, X.SETE(dest))             = (n, defhit dest @ [SUCC(n+1)])
        | gendef (n, X.SETLE(dest))            = (n, defhit dest @ [SUCC(n+1)])
        | gendef (n, X.SETL(dest))             = (n, defhit dest @ [SUCC(n+1)])
        | gendef (n, X.SETGE(dest))            = (n, defhit dest @ [SUCC(n+1)])
        | gendef (n, X.SETG(dest))             = (n, defhit dest @ [SUCC(n+1)])
        | gendef (n, X.MOVZBL(dest, src))      = (n, defhit dest @ usehit src @ [SUCC(n+1)])
        | gendef (n, X.RET)                    = (n, nil)
        | gendef (n, X.LABEL l)                = (n, [SUCC (n+1)])
        | gendef (n, X.JMP l)                  = (n, [SUCC (findlabel l)])
        | gendef (n, X.JE l)                   = (n, [SUCC (n+1), SUCC (findlabel l)])
        | gendef (n, X.JNE l)                  = (n, [SUCC (n+1), SUCC (findlabel l)])
    in
        List.map gendef l
    end

  (* val uselive : (ident * pred list) list -> live list
   * generates liveness for 'use' rules to get the iterative analyzer started
   *)
  fun uselive preds =
    List.map
      (fn (n, l) => (n, List.foldr 
        (fn (a,b) => case a of USE(x) => x::b | _ => b)
        nil
        l
      )
    )
    preds

  (* val subsetlive : (ident * pred list) * (ident * pred list) -> bool
   * true if first is subset of second
   *)

  fun subsetlive (l1,l2) =
    ListPair.all
      (fn ((n1,a),(n2,b)) => (n1 = n2) andalso List.all
        (fn x => List.exists (fn y => X.opereq (x,y)) b)
        a
      )
      (l1,l2)

  (* val liveiter : live list -> (ident * pred list) list -> live list
   * iteratively generates livenesses from def/use/succ rules
   * it must be fed a liveness list generated from the use rule as it only
   * processes the second rule :
   *
   *    use(l',x)
   *   !def(l,x)
   *   succ(l,l')
   * --------------
   *   live(l,x)
   *)

  fun liveiter l p =
    let
      (* val succs : pred list -> l
       * generates a list of lines that succeed a line given the predicates
       * for that line
       *)
      fun succs (SUCC(a)::l) = a::(succs l)
        | succs (_::l) = succs l
        | succs nil = nil

      (* val lives : ident list -> live list -> X.oper list
       * scans l for live variables in succeeding lines *)
      fun lives l' idents =
        List.foldr
          (fn ((_,a),b) => a @ b)
          nil
          (List.filter (fn (n,_) => List.exists (fn a => a = n) idents) l')

      (* val isndef : X.oper -> pred list -> bool
       * checks to see if x is defined in a predicate list *)
      fun isndef x (DEF(y)::l) = not (X.opereq (x,y)) andalso isndef x l
        | isndef x (a::l) = isndef x l
        | isndef x nil = true

      (* val addonce : X.oper list -> X.oper -> X.oper list
       * eliminates duplicates, which speeds up compilation
       *)
      fun addonce l oper =
        if (List.exists (fn x => X.opereq (x,oper)) l)
        then l
        else oper::l

      (* val liveadd : live -> live list -> live list *)
      fun liveadd (n,oper) lives = List.map
        (fn (x,a) => if (x = n) then (x,addonce a oper) else (x,a))
        lives

      (* this does the dirty work!
       * for each line, checks if the live variables in succeeding lines are
       * not defined here; if so, it accumulates them onto the inital list
       *
       * changing the first foldr to a foldl slows down liveness by a factor
       * of at least 100 on cedar-anastulate.l2
       *)
      val newl = List.foldr
        (fn ((n, a), b) => List.foldr
          (fn (a',b') => if (isndef a' a) then liveadd (n, a') b' else b')
          b
          (lives b (succs a))
        )
        l
        p
    in
      if subsetlive (newl, l) then l else liveiter newl p
    end

  (* val liveness : pseudoasm -> livenesses
   * analyzes liveness of variables in the given pseudo-asm
   *)

  fun liveness instrs =
    let
      val preds = defusesucc (number instrs)
      val init = uselive preds
      val (_,lives) = ListPair.unzip (liveiter init preds)
    in
      lives
    end

  fun prettyprint (a::l) = (X.prettyprint_oper a) ^ ", " ^ prettyprint l
    | prettyprint nil = "-\n"

end