codegen/liveness.sml

   1 (* L1 Compiler
   2  * Gathers tiberium, fires rockets
   3  * Turns pseudoasm into liveness-annotated pseudoasm
   4  * Author: Joshua Wise <jwise@andrew.cmu.edu>
   5  *)
   6
   7 signature LIVENESS =
   8 sig
   9   type tiberium = x86.insn list
  10   type rockets = x86.oper list list
  11
  12   val liveness : tiberium -> rockets
  13 end
  14
  15 structure Liveness :> LIVENESS =
  16 struct
  17   structure T = Temp
  18   structure X = x86
  19
  20   type tiberium = x86.insn list
  21   type rockets = x86.oper list list
  22
  23   (* This does not 'follow the rules'.
  24    *
  25    * Since this is a straight line, we can just fold starting at the right,
  26    * and accumulate variables.  Thus, the accumulator has two parts: one to
  27    * represent all of the line / liveness pairs that we've accumulated so far;
  28    * and one to represent what was live at the previous line.
  29    *)
  30   fun mashinstr ((instr : x86.insn), (curtemps, output) : x86.oper list * rockets) : x86.oper list * rockets =
  31     let
  32
  33       (* Removes an element from a list. *)
  34       fun blast (X.TEMP(elt)) l =
  35             List.filter (fn a => case a of X.TEMP(b) => (T.compare (b, elt)) <> EQUAL | _ => true) l
  36         | blast (X.REG(reg)) l =
  37             List.filter (fn a => case a of X.REG(b) => b <> reg | _ => true) l
  38         | blast _ l = raise ErrorMsg.InternalError "Why have we declared a CONST as live?"
  39
  40       (* Adds an element to a list iff the element doesn't exist already. *)
  41       fun addonce (X.CONST(_)) l = l
  42         | addonce oper l = oper :: blast oper l
  43
  44       val newtemps =
  45         case instr
  46         of X.DIRECTIVE(_)           => curtemps
  47          | X.COMMENT(_)             => curtemps
  48          | X.MOVL(dest, src)        => addonce src (blast dest curtemps)
  49          | X.SUBL(dest, src)        => addonce src (addonce dest curtemps)
  50          | X.IMUL(dest, src)        => addonce src (addonce dest curtemps)
  51          | X.IMUL3(dest, src, _)    => addonce src (blast dest curtemps)
  52          | X.ADDL(dest, src)        => addonce src (addonce dest curtemps)
  53          | X.LEAL(dest, src1, src2) => addonce src1 (addonce src2 (blast dest curtemps))
  54          | X.IDIVL(src)             => addonce src (addonce (X.REG X.EAX) (addonce (X.REG X.EDX) curtemps))
  55          | X.CLTD                   => blast (X.REG X.EDX) (addonce (X.REG X.EAX) curtemps)
  56          | X.NEG(src)               => (* meh *) curtemps
  57          | X.RET                    => addonce (X.REG X.EAX) curtemps
  58 (*         | _                        => raise ErrorMsg.InternalError "Unable to compute liveness for unused instruction form";*)
  59     in
  60       (newtemps, newtemps :: output)
  61     end
  62
  63   fun liveness (instrs : tiberium) : rockets =
  64     let
  65       val (_, livelist) = foldr mashinstr (nil, nil) instrs
  66     in
  67       livelist
  68     end
  69 end