codegen/liveness.sml

   1 (* L2 Compiler
   2  * Turns pseudoasm into liveness-annotated pseudoasm
   3  * Author: Chris Lu <czl@andrew.cmu.edu>
   4  * Author: Joshua Wise <jwise@andrew.cmu.edu>
   5  *)
   6
   7 signature LIVENESS =
   8 sig
   9
  10   type live = int * x86.oper list
  11   type pseudoasm = x86.insn list
  12   type livenesses = x86.oper list list
  13
  14   type ident = int
  15   datatype pred = DEF of x86.oper | USE of x86.oper | SUCC of ident
  16
  17   val liveness : pseudoasm -> livenesses
  18   val prettyprint : x86.oper list -> string
  19 end
  20
  21 structure Liveness :> LIVENESS =
  22 struct
  23   structure T = Temp
  24   structure X = x86
  25
  26
  27   type live = int * x86.oper list
  28   type pseudoasm = X.insn list
  29   type numasm = (int * X.insn) list
  30   type livenesses = X.oper list list
  31
  32   type ident = int
  33   datatype pred = DEF of X.oper | USE of X.oper | SUCC of ident
  34
  35   (* val number : pseudoasm -> numasm
  36    * numbers the instructions!
  37    *)
  38
  39   fun number instrs =
  40     let
  41       val nums = List.tabulate (List.length instrs, (fn i => i))
  42     in
  43       ListPair.zip (nums,instrs)
  44     end
  45
  46   (* val defusesucc : numasm -> (ident * pred list) list
  47    * generates def/use/succ predicates according to rules
  48    *)
  49
  50   fun defusesucc l =
  51     let
  52       fun findlabel (lb) =
  53             Option.valOf
  54               (foldr (fn ((n, X.LABEL lb'), NONE) => if (Label.compare (lb, lb') = EQUAL) then SOME n else NONE
  55                        | (_, old) => old) NONE l)
  56
  57       (* val defhit/usehit : X.oper -> pred list
  58        * helper functions to discard constant operands *)
  59       fun defhit (a as X.CONST(_)) = nil
  60         | defhit (a) = [DEF(a)]
  61
  62       fun usehit (a as X.CONST(_)) = nil
  63         | usehit (a) = [USE(a)]
  64
  65       (* val gendef : ident * X.insn -> ident * pred list
  66        * generates the def/use/succ predicates for a single insn
  67        *)
  68       fun gendef (n, X.DIRECTIVE(_))           = (n, nil)
  69         | gendef (n, X.COMMENT(_))             = (n, nil)
  70         | gendef (n, X.MOVL(dest, src))        = (n, defhit dest @ usehit src @ [SUCC(n+1)])
  71         | gendef (n, X.SUBL(dest, src))        = (n, defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
  72         | gendef (n, X.IMUL(dest, src))        = (n, defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
  73         | gendef (n, X.IMUL3(dest, src, _))    = (n, defhit dest @ usehit src @ [SUCC(n+1)])
  74         | gendef (n, X.ADDL(dest, src))        = (n, defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
  75         | gendef (n, X.IDIVL(src))             = (n, usehit src @ [DEF(X.REG(X.EAX)), DEF(X.REG(X.EDX)),
  76                                                                    USE(X.REG(X.EAX)), USE(X.REG(X.EDX)),
  77                                                                    SUCC(n+1)])
  78         | gendef (n, X.CLTD)                   = (n, [USE(X.REG(X.EAX)), DEF(X.REG(X.EDX)), SUCC(n+1)])
  79         | gendef (n, X.SALL(dest, shft))       = (n, defhit dest @ usehit shft @ usehit dest @ [SUCC(n+1)])
  80         | gendef (n, X.SARL(dest, shft))       = (n, defhit dest @ usehit shft @ usehit dest @ [SUCC(n+1)])
  81         | gendef (n, X.NEG(src))               = (n, defhit src @ usehit src @ [SUCC(n+1)])
  82         | gendef (n, X.NOTL(src))              = (n, defhit src @ usehit src @ [SUCC(n+1)])
  83         | gendef (n, X.ANDL(dest, src))        = (n, defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
  84         | gendef (n, X.ORL(dest, src))         = (n, defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
  85         | gendef (n, X.XORL(dest, src))        = (n, defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
  86         | gendef (n, X.CMPL(dest, src))        = (n, usehit dest @ usehit src @ [SUCC(n+1)])
  87         | gendef (n, X.TEST(dest, src))        = (n, usehit dest @ usehit src @ [SUCC(n+1)])
  88         | gendef (n, X.SETNE(dest))            = (n, defhit dest @ [SUCC(n+1)])
  89         | gendef (n, X.SETE(dest))             = (n, defhit dest @ [SUCC(n+1)])
  90         | gendef (n, X.SETLE(dest))            = (n, defhit dest @ [SUCC(n+1)])
  91         | gendef (n, X.SETL(dest))             = (n, defhit dest @ [SUCC(n+1)])
  92         | gendef (n, X.SETGE(dest))            = (n, defhit dest @ [SUCC(n+1)])
  93         | gendef (n, X.SETG(dest))             = (n, defhit dest @ [SUCC(n+1)])
  94         | gendef (n, X.MOVZBL(dest, src))      = (n, defhit dest @ usehit src @ [SUCC(n+1)])
  95         | gendef (n, X.RET)                    = (n, nil)
  96         | gendef (n, X.LABEL l)                = (n, [SUCC (n+1)])
  97         | gendef (n, X.JMP l)                  = (n, [SUCC (findlabel l)])
  98         | gendef (n, X.JE l)                   = (n, [SUCC (n+1), SUCC (findlabel l)])
  99         | gendef (n, X.JNE l)                  = (n, [SUCC (n+1), SUCC (findlabel l)])
 100     in
 101         List.map gendef l
 102     end
 103
 104   (* val uselive : (ident * pred list) list -> live list
 105    * generates liveness for 'use' rules to get the iterative analyzer started
 106    *)
 107   fun uselive preds =
 108     List.map
 109       (fn (n, l) => (n, List.foldr
 110         (fn (a,b) => case a of USE(x) => x::b | _ => b)
 111         nil
 112         l
 113       )
 114     )
 115     preds
 116
 117   (* val subsetlive : (ident * pred list) * (ident * pred list) -> bool
 118    * true if first is subset of second
 119    *)
 120
 121   fun subsetlive (l1,l2) =
 122     ListPair.all
 123       (fn ((n1,a),(n2,b)) => (n1 = n2) andalso List.all
 124         (fn x => List.exists (fn y => X.opereq (x,y)) b)
 125         a
 126       )
 127       (l1,l2)
 128
 129   (* val liveiter : live list -> (ident * pred list) list -> live list
 130    * iteratively generates livenesses from def/use/succ rules
 131    * it must be fed a liveness list generated from the use rule as it only
 132    * processes the second rule :
 133    *
 134    *    use(l',x)
 135    *   !def(l,x)
 136    *   succ(l,l')
 137    * --------------
 138    *   live(l,x)
 139    *)
 140
 141   fun liveiter l p =
 142     let
 143       (* val succs : pred list -> l
 144        * generates a list of lines that succeed a line given the predicates
 145        * for that line
 146        *)
 147       fun succs (SUCC(a)::l) = a::(succs l)
 148         | succs (_::l) = succs l
 149         | succs nil = nil
 150
 151       (* val lives : ident list -> live list -> X.oper list
 152        * scans l for live variables in succeeding lines *)
 153       fun lives l' idents =
 154         List.foldr
 155           (fn ((_,a),b) => a @ b)
 156           nil
 157           (List.filter (fn (n,_) => List.exists (fn a => a = n) idents) l')
 158
 159       (* val isndef : X.oper -> pred list -> bool
 160        * checks to see if x is defined in a predicate list *)
 161       fun isndef x (DEF(y)::l) = not (X.opereq (x,y)) andalso isndef x l
 162         | isndef x (a::l) = isndef x l
 163         | isndef x nil = true
 164
 165       (* val addonce : X.oper list -> X.oper -> X.oper list
 166        * eliminates duplicates, which speeds up compilation
 167        *)
 168       fun addonce l oper =
 169         if (List.exists (fn x => X.opereq (x,oper)) l)
 170         then l
 171         else oper::l
 172
 173       (* val liveadd : live -> live list -> live list *)
 174       fun liveadd (n,oper) lives = List.map
 175         (fn (x,a) => if (x = n) then (x,addonce a oper) else (x,a))
 176         lives
 177
 178       (* this does the dirty work!
 179        * for each line, checks if the live variables in succeeding lines are
 180        * not defined here; if so, it accumulates them onto the inital list
 181        *
 182        * changing the first foldr to a foldl slows down liveness by a factor
 183        * of at least 100 on cedar-anastulate.l2
 184        *)
 185       val newl = List.foldr
 186         (fn ((n, a), b) => List.foldr
 187           (fn (a',b') => if (isndef a' a) then liveadd (n, a') b' else b')
 188           b
 189           (lives b (succs a))
 190         )
 191         l
 192         p
 193     in
 194       if subsetlive (newl, l) then l else liveiter newl p
 195     end
 196
 197   (* val liveness : pseudoasm -> livenesses
 198    * analyzes liveness of variables in the given pseudo-asm
 199    *)
 200
 201   fun liveness instrs =
 202     let
 203       val preds = defusesucc (number instrs)
 204       val init = uselive preds
 205       val (_,lives) = ListPair.unzip (liveiter init preds)
 206     in
 207       lives
 208     end
 209
 210   fun prettyprint (a::l) = (X.prettyprint_oper a) ^ ", " ^ prettyprint l
 211     | prettyprint nil = "-\n"
 212
 213 end