]> Joshua Wise's Git repositories - snipe.git/blobdiff - codegen/liveness.sml
git.joshuawise.com / snipe.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
Add strings to the IR
[snipe.git] / codegen / liveness.sml
diff --git a/codegen/liveness.sml b/codegen/liveness.sml
index 34f5d478aa90bfa50252b63820505f9e6dbdba12..6a7d89b5f65bfbf1c53e0b8054da92dabcddee4c 100644 (file)
--- a/codegen/liveness.sml
+++ b/codegen/liveness.sml
@@ -1,69 +1,289 @@
-(* L1 Compiler
- * Gathers tiberium, fires rockets
+(* L3 Compiler
  * Turns pseudoasm into liveness-annotated pseudoasm
  * Turns pseudoasm into liveness-annotated pseudoasm
+ * Author: Chris Lu <czl@andrew.cmu.edu>
  * Author: Joshua Wise <jwise@andrew.cmu.edu>
  *)
 
 signature LIVENESS =
 sig
  * Author: Joshua Wise <jwise@andrew.cmu.edu>
  *)
 
 signature LIVENESS =
 sig
-  type tiberium = x86.insn list
-  type rockets = x86.oper list list
+  structure OperSet : ORD_SET
+    where type Key.ord_key = Blarg.oper;
+  structure LiveMap : ORD_MAP
+    where type Key.ord_key = int;
 
 
-  val liveness : tiberium -> rockets
+  type live = int * OperSet.set
+  type pseudoasm = Blarg.insn list
+  type livenesses = OperSet.set LiveMap.map
+  
+  type ident = int
+  datatype pred = DEF of Blarg.oper | USE of Blarg.oper | SUCC of ident | ISMOVE
+  
+  type predicates = pred list LiveMap.map
+
+  val uses : pred list -> Blarg.oper list
+  val succs : pred list -> ident list
+  val defs : pred list -> Blarg.oper list
+  val ismove : pred list -> bool
+
+  val liveness : pseudoasm -> predicates * livenesses
+  val listify : livenesses -> OperSet.set list
+  val prettyprint : OperSet.set -> string
 end
 
 structure Liveness :> LIVENESS =
 struct
   structure T = Temp
 end
 
 structure Liveness :> LIVENESS =
 struct
   structure T = Temp
-  structure X = x86
+  structure X = Blarg
   
   
-  type tiberium = x86.insn list
-  type rockets = x86.oper list list
+  structure OperSet = Blarg.OperSet
+  structure LiveMap = Blarg.LiveMap
+  structure LabelMap = SplayMapFn(struct
+                                    type ord_key = Label.label
+                                    val compare = Label.compare
+                                  end)
+
+  type live = int * OperSet.set
+  type pseudoasm = X.insn list
+  type numasm = X.insn LiveMap.map
+  type livenesses = OperSet.set LiveMap.map
+
+  type ident = int
+  datatype pred = DEF of X.oper | USE of X.oper | SUCC of ident | ISMOVE
 
 
-  (* This does not 'follow the rules'.
+  type predicates = pred list LiveMap.map
+
+  (* val number : pseudoasm -> numasm
+   * numbers the instructions!
+   *)
+
+  fun number instrs =
+    let
+      val nums = List.tabulate (List.length instrs, (fn i => i))
+    in
+      foldr
+        LiveMap.insert'
+        LiveMap.empty
+        (ListPair.zip (nums,instrs))
+    end
+
+  (* val defusesucc : numasm -> (ident * pred list) list
+   * generates def/use/succ predicates according to rules
+   *)
+  fun defusesucc l =
+    let
+      val labelmap = LiveMap.foldri
+        (fn (n, a, b) => LabelMap.insert(b, a, n))
+        (LabelMap.empty)
+        (LiveMap.mapPartial (fn (X.LABEL lb) => SOME(lb) | _ => NONE) l)
+
+      fun findlabel (lb) = valOf (LabelMap.find (labelmap, lb))
+
+      (* val defhit/usehit : X.oper -> pred list
+       * helper functions to discard constant operands *)
+      fun defhit (X.REG X.PC) = raise ErrorMsg.InternalError "cannot define PC"
+        | defhit (X.REG a) = [DEF(X.REG a)]
+        | defhit (X.TEMP a) = [DEF(X.TEMP a)]
+        | defhit (_) = nil
+    
+      and usehit (X.REG a) = [USE(X.REG a)]
+        | usehit (X.TEMP a) = [USE(X.TEMP a)]
+        | usehit (_) = nil
+
+      fun callhit 0 = nil
+        | callhit 1 = USE(X.REG(X.R0))::(callhit 0)
+        | callhit 2 = USE(X.REG(X.R1))::(callhit 1)
+        | callhit 3 = USE(X.REG(X.R2))::(callhit 2)
+        | callhit 4 = USE(X.REG(X.R3))::(callhit 3)
+        | callhit _ = callhit 4
+
+      (* val gendef : ident * X.insn -> ident * pred list
+       * generates the def/use/succ predicates for a single insn
+       *)
+      fun gendef (n, X.DIRECTIVE(_))           = ([SUCC (n+1)])
+        | gendef (n, X.COMMENT(_))             = ([SUCC (n+1)])
+        | gendef (n, X.LIVEIGN (_))            = ([SUCC (n+1)])
+        | gendef (n, X.LABEL l)                = ([SUCC (n+1)])
+        | gendef (n, X.INSN(X.NV, _))          = ([SUCC (n+1)])
+        | gendef (n, X.INSN(_, X.MOVLIT(dest, _))) = (defhit dest @ [SUCC(n+1), ISMOVE])
+        | gendef (n, X.INSN(_, X.MOVSYM(dest, sym))) = (defhit dest @ [SUCC(n+1), ISMOVE])
+        | gendef (n, X.INSN(X.AL, X.MOVLBL(X.REG X.PC, l))) = ([SUCC (findlabel l)])
+        | gendef (n, X.INSN(_, X.MOVLBL(X.REG X.PC, l))) = ([SUCC (n+1), SUCC (findlabel l)])
+        | gendef (n, X.INSN(_, X.MOVLBL(_, _))) = raise ErrorMsg.InternalError "MOVLBL with target neq PC"
+        | gendef (n, X.INSN(_, X.LDR(dest, src))) = (defhit dest @ usehit src @ [SUCC (n+1), ISMOVE])
+        | gendef (n, X.INSN(_, X.STO(dest, src))) = (usehit dest @ usehit src @ [SUCC (n+1)])
+        | gendef (n, X.INSN(_, X.MOV(dest, src))) = (defhit dest @ usehit src @ [SUCC (n+1), ISMOVE])
+        | gendef (n, X.INSN(_, X.MOVS(dest, src))) = (usehit src @ [SUCC (n+1)])
+        | gendef (n, X.INSN(_, X.ADD(dest, src))) = (defhit dest @ usehit dest @ usehit src @ [SUCC (n+1)])
+        | gendef (n, X.INSN(_, X.ADDS(dest, src))) = (usehit dest @ usehit src @ [SUCC (n+1)])
+        | gendef (n, X.INSN(_, X.SUB(dest, src))) = (defhit dest @ usehit dest @ usehit src @ [SUCC (n+1)])
+        | gendef (n, X.INSN(_, X.SUBS(dest, src))) = (usehit dest @ usehit src @ [SUCC (n+1)])
+        | gendef (n, X.INSN(_, X.AND(dest, src))) = (defhit dest @ usehit dest @ usehit src @ [SUCC (n+1)])
+        | gendef (n, X.INSN(_, X.ANDS(dest, src))) = (usehit dest @ usehit src @ [SUCC (n+1)])
+        | gendef (n, X.INSN(_, X.NOT(dest, src))) = (defhit dest @ usehit src @ [SUCC (n+1)])
+        | gendef (n, X.INSN(_, X.NOTS(dest, src))) = (usehit src @ [SUCC (n+1)])
+        | gendef (n, X.INSN(_, X.PUSH(X.REG X.SP, src))) = (usehit src @ [SUCC (n+1)])
+        | gendef (n, X.INSN(_, X.PUSH(_, _))) = raise ErrorMsg.InternalError "PUSH with sp != SP"
+        | gendef (n, X.INSN(X.AL, X.POP(X.REG X.SP, X.REG X.PC))) = ([USE (X.REG X.R0)]) (* kind of like 'ret' *)
+        | gendef (n, X.INSN(_, X.POP(X.REG X.SP, X.REG X.PC))) = ([USE (X.REG X.R0), SUCC(n+1)])
+        | gendef (n, X.INSN(_, X.POP(X.REG X.SP, src))) = (defhit src @ [SUCC (n+1)])
+        | gendef (n, X.INSN(_, X.POP(_, _))) = raise ErrorMsg.InternalError "POP with sp != SP"
+        | gendef (n, X.INSN(_, X.CALL(X.REG X.SP, src, a))) = (callhit a @
+                                                               usehit src @
+                                                               [DEF(X.REG(X.R0)), DEF(X.REG(X.R1)), DEF(X.REG(X.R2)), DEF(X.REG(X.R3)),
+                                                                DEF(X.REG(X.R4)), DEF(X.REG(X.R5)),
+                                                                SUCC(n+1)]
+                                                              )
+        | gendef (n, X.INSN(_, X.CALL(_, _, _))) = raise ErrorMsg.InternalError "CALL with sp != SP"
+        | gendef (n, X.INSN(_, X.SHR(dest, src))) = (defhit dest @ usehit dest @ usehit src @ [SUCC (n+1)])
+        | gendef (n, X.INSN(_, X.SHL(dest, src))) = (defhit dest @ usehit dest @ usehit src @ [SUCC (n+1)])
+    in
+        LiveMap.mapi gendef l
+    end
+
+  (* val uselive : (int * pred list) list -> OperSet.set LiveMap.map
+   * generates liveness for 'use' rules to get the iterative analyzer started
+   *)
+  fun uselive preds =
+    LiveMap.mapi
+      (fn (n, pl) =>
+         foldr
+           (fn (USE (l), set) => OperSet.add (set, l)
+             | (_, set) => set)
+           OperSet.empty
+           pl
+      )
+      preds
+
+  (* val subsetlive : OperSet.set LiveMap.map * OperSet.set LiveMap.map -> bool
+   * true if first is subset of second
+   *)
+
+  fun subsetlive (l1,l2) =
+    LiveMap.foldri
+      (fn (_, _, false) => false
+        | (n, set1, _) => case LiveMap.find (l2, n)
+            of NONE => false
+             | SOME set2 => OperSet.isSubset (set1, set2))
+      true
+      l1
+  
+  (* val succs : pred list -> int list
+   * 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
+
+  fun defs (DEF(a)::l) = a::(defs l)
+    | defs (_::l) = defs l
+    | defs nil = nil
+  
+  fun uses (USE(a)::l) = a::(defs l)
+    | uses (_::l) = defs l
+    | uses nil = nil
+  
+  fun ismove l = List.exists (fn ISMOVE => true | _ => false) l
+
+  (* val liveiter : OperSet.set LiveMap.map -> (int * pred list) list -> OperSet.set LiveMap.map
+   * 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 :
    *
    *
-   * Since this is a straight line, we can just fold starting at the right,
-   * and accumulate variables.  Thus, the accumulator has two parts: one to
-   * represent all of the line / liveness pairs that we've accumulated so far;
-   * and one to represent what was live at the previous line.
+   *    use(l',x)
+   *   !def(l,x)
+   *   succ(l,l')
+   * --------------
+   *   live(l,x)
    *)
    *)
-  fun mashinstr ((instr : x86.insn), (curtemps, output) : x86.oper list * rockets) : x86.oper list * rockets =
+
+  fun liveiter livemap preds =
     let
 
     let
 
-      (* Removes an element from a list. *)
-      fun blast (X.TEMP(elt)) l =
-            List.filter (fn a => case a of X.TEMP(b) => (T.compare (b, elt)) <> EQUAL | _ => true) l
-        | blast (X.REG(reg)) l =
-            List.filter (fn a => case a of X.REG(b) => b <> reg | _ => true) l
-        | blast _ l = raise ErrorMsg.InternalError "Why have we declared a CONST as live?"
-
-      (* Adds an element to a list iff the element doesn't exist already. *)
-      fun addonce (X.CONST(_)) l = l
-        | addonce oper l = oper :: blast oper l
-
-      val newtemps =
-        case instr
-        of X.DIRECTIVE(_)           => curtemps
-         | X.COMMENT(_)             => curtemps
-         | X.MOVL(dest, src)        => addonce src (blast dest curtemps)
-         | X.SUBL(dest, src)        => addonce src (addonce dest curtemps)
-         | X.IMUL(dest, src)        => addonce src (addonce dest curtemps)
-         | X.IMUL3(dest, src, _)    => addonce src (blast dest curtemps)
-         | X.ADDL(dest, src)        => addonce src (addonce dest curtemps)
-         | X.LEAL(dest, src1, src2) => addonce src1 (addonce src2 (blast dest curtemps))
-         | X.IDIVL(src)             => addonce src (addonce (X.REG X.EAX) (addonce (X.REG X.EDX) curtemps))
-         | X.CLTD                   => blast (X.REG X.EDX) (addonce (X.REG X.EAX) curtemps)
-         | X.NEG(src)               => (* meh *) curtemps
-         | X.RET                    => addonce (X.REG X.EAX) curtemps
-(*         | _                        => raise ErrorMsg.InternalError "Unable to compute liveness for unused instruction form";*)
+
+
+      (* val lives : int list -> OperSet.set LiveMap.map -> OperSet.set
+       * scans l for live variables in succeeding lines *)
+      fun lives l' idents =
+        let
+          val lines = List.mapPartial (fn a => LiveMap.find (l', a)) idents
+        in
+          foldr
+            (fn (set', set) => OperSet.union (set', set))
+            OperSet.empty
+            lines
+        end
+
+      (* val isndef : X.oper -> pred list -> bool
+       * checks to see if x is defined in a predicate list *)
+      fun isndef (X.STACKARG(_)) _ = false
+        | 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 liveadd : live -> OperSet.set LiveMap.map -> OperSet.set LiveMap.map *)
+      fun liveadd (n,oper) map = case LiveMap.find (map, n)
+        of SOME(x) => LiveMap.insert (map, n, OperSet.add (x, oper))
+         | NONE => LiveMap.insert (map, n, OperSet.singleton oper)
+
+      (* 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 = LiveMap.foldri
+        (fn (n, a, b) => OperSet.foldr
+          (fn (a',b') => if (isndef a' a) then liveadd (n, a') b' else b')
+          b
+          (lives b (succs a))
+        )
+        livemap
+        preds
+    in
+      if subsetlive (newl, livemap)
+      then livemap
+      else liveiter newl preds
+    end
+
+  fun dustostring (DEF(a)) = "DEF(" ^ X.pp_oper a ^ ")"
+    | dustostring (USE(a)) = "USE(" ^ X.pp_oper a ^ ")"
+    | dustostring (SUCC(a)) = "SUCC(" ^ Int.toString a ^ ")"
+    | dustostring ISMOVE = "ISMOVE"
+
+  (* val liveness : pseudoasm -> livenesses
+   * analyzes liveness of variables in the given pseudo-asm
+   *)
+
+  fun liveness instrs =
+    let
+      val preds = defusesucc (number instrs)
+(*      val (_,l) = ListPair.unzip preds
+      val () = print (
+        String.concatWith "\n" (
+          List.map
+            (fn a => String.concatWith ", " (List.map dustostring a))
+            l
+        )
+      )*)
+      val init = uselive preds
+      val initmap = LiveMap.foldri (fn (n,a,b) => LiveMap.insert (b, n, a)) LiveMap.empty init
     in
     in
-      (newtemps, newtemps :: output)
+      (preds, liveiter initmap preds)
     end
   
     end
   
-  fun liveness (instrs : tiberium) : rockets =
+  fun prettyprint (set) =
+    OperSet.foldr
+      (fn (oper, s) => (X.pp_oper oper) ^ ", " ^ s)
+      "-\n"
+      set
+      
+  fun listify map =
     let
     let
-      val (_, livelist) = foldr mashinstr (nil, nil) instrs
+      val maxln = LiveMap.foldri (fn (a, _, b) => Int.max (a, b)) 0 map
+      val nums = List.tabulate (maxln+1, fn x => x)
     in
     in
-      livelist
+      List.map (fn num => valOf (LiveMap.find (map, num)) handle Option => OperSet.empty) nums
     end
 end
     end
 end
Compiler for a C-like language written in SML
This page took 0.034719 seconds and 4 git commands to generate.