]> 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 string pasting support to the gramamr.
[snipe.git] / codegen / liveness.sml
diff --git a/codegen/liveness.sml b/codegen/liveness.sml
index 95f1f90ce3b35f13ebcd217154ffc1825bf915f3..df411bbf1441fb93f5643bafb34fbc62e2e88cd6 100644 (file)
--- a/codegen/liveness.sml
+++ b/codegen/liveness.sml
@@ -1,4 +1,4 @@
-(* L2 Compiler
+(* L3 Compiler
  * Turns pseudoasm into liveness-annotated pseudoasm
  * Author: Chris Lu <czl@andrew.cmu.edu>
  * Author: Joshua Wise <jwise@andrew.cmu.edu>
  * Turns pseudoasm into liveness-annotated pseudoasm
  * Author: Chris Lu <czl@andrew.cmu.edu>
  * Author: Joshua Wise <jwise@andrew.cmu.edu>
@@ -6,31 +6,51 @@
 
 signature LIVENESS =
 sig
 
 signature LIVENESS =
 sig
+  structure OperSet : ORD_SET
+    where type Key.ord_key = Blarg.oper;
+  structure LiveMap : ORD_MAP
+    where type Key.ord_key = int;
 
 
-  type live = int * x86.oper list
-  type pseudoasm = x86.insn list
-  type livenesses = x86.oper list list
-
+  type live = int * OperSet.set
+  type pseudoasm = Blarg.insn list
+  type livenesses = OperSet.set LiveMap.map
+  
   type ident = int
   type ident = int
-  datatype pred = DEF of x86.oper | USE of x86.oper | SUCC of ident
+  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 -> livenesses
-  val prettyprint : x86.oper list -> string
+  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
+  
+  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 * x86.oper list
+  type live = int * OperSet.set
   type pseudoasm = X.insn list
   type pseudoasm = X.insn list
-  type numasm = (int * X.insn) list
-  type livenesses = X.oper list list
+  type numasm = X.insn LiveMap.map
+  type livenesses = OperSet.set LiveMap.map
 
   type ident = int
 
   type ident = int
-  datatype pred = DEF of X.oper | USE of X.oper | SUCC of ident
+  datatype pred = DEF of X.oper | USE of X.oper | SUCC of ident | ISMOVE
+
+  type predicates = pred list LiveMap.map
 
   (* val number : pseudoasm -> numasm
    * numbers the instructions!
 
   (* val number : pseudoasm -> numasm
    * numbers the instructions!
@@ -40,93 +60,133 @@ struct
     let
       val nums = List.tabulate (List.length instrs, (fn i => i))
     in
     let
       val nums = List.tabulate (List.length instrs, (fn i => i))
     in
-      ListPair.zip (nums,instrs)
+      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
    *)
     end
 
   (* val defusesucc : numasm -> (ident * pred list) list
    * generates def/use/succ predicates according to rules
    *)
-
   fun defusesucc l =
     let
   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 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 *)
       (* 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 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 usehit (a as X.CONST(_)) = nil
-        | usehit (a) = [USE(a)]
+      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
        *)
 
       (* 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)])
+      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.MOVSTR(dest, str))) = (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
     in
-        List.map gendef l
+        LiveMap.mapi gendef l
     end
 
     end
 
-  (* val uselive : (ident * pred list) list -> live list
+  (* val uselive : (int * pred list) list -> OperSet.set LiveMap.map
    * generates liveness for 'use' rules to get the iterative analyzer started
    *)
   fun uselive preds =
    * 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
+    LiveMap.mapi
+      (fn (n, pl) =>
+         foldr
+           (fn (USE (l), set) => OperSet.add (set, l)
+             | (_, set) => set)
+           OperSet.empty
+           pl
       )
       )
-    )
-    preds
+      preds
 
 
-  (* val subsetlive : (ident * pred list) * (ident * pred list) -> bool
+  (* val subsetlive : OperSet.set LiveMap.map * OperSet.set LiveMap.map -> bool
    * true if first is subset of second
    *)
 
   fun subsetlive (l1,l2) =
    * 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)
+    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 : live list -> (ident * pred list) list -> live list
+  (* 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 :
    * 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 :
@@ -138,42 +198,34 @@ struct
    *   live(l,x)
    *)
 
    *   live(l,x)
    *)
 
-  fun liveiter l p =
+  fun liveiter livemap preds =
     let
     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
+
+
+      (* val lives : int list -> OperSet.set LiveMap.map -> OperSet.set
        * scans l for live variables in succeeding lines *)
       fun lives l' idents =
        * 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')
+        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 *)
 
       (* 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
+      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
 
         | 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
+      (* 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
 
       (* this does the dirty work!
        * for each line, checks if the live variables in succeeding lines are
@@ -182,18 +234,25 @@ struct
        * changing the first foldr to a foldl slows down liveness by a factor
        * of at least 100 on cedar-anastulate.l2
        *)
        * 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
+      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))
         )
           (fn (a',b') => if (isndef a' a) then liveadd (n, a') b' else b')
           b
           (lives b (succs a))
         )
-        l
-        p
+        livemap
+        preds
     in
     in
-      if subsetlive (newl, l) then l else liveiter newl p
+      if subsetlive (newl, livemap)
+      then livemap
+      else liveiter newl preds
     end
 
     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
    *)
   (* val liveness : pseudoasm -> livenesses
    * analyzes liveness of variables in the given pseudo-asm
    *)
@@ -201,13 +260,31 @@ struct
   fun liveness instrs =
     let
       val preds = defusesucc (number instrs)
   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 init = uselive preds
-      val (_,lives) = ListPair.unzip (liveiter init preds)
+      val initmap = LiveMap.foldri (fn (n,a,b) => LiveMap.insert (b, n, a)) LiveMap.empty init
     in
     in
-      lives
+      (preds, liveiter initmap preds)
+    end
+  
+  fun prettyprint (set) =
+    OperSet.foldr
+      (fn (oper, s) => (X.pp_oper oper) ^ ", " ^ s)
+      "-\n"
+      set
+      
+  fun listify map =
+    let
+      val maxln = LiveMap.foldri (fn (a, _, b) => Int.max (a, b)) 0 map
+      val nums = List.tabulate (maxln+1, fn x => x)
+    in
+      List.map (fn num => valOf (LiveMap.find (map, num)) handle Option => OperSet.empty) nums
     end
     end
-
-  fun prettyprint (a::l) = (X.prettyprint_oper a) ^ ", " ^ prettyprint l
-    | prettyprint nil = "-\n"
-
 end
 end
Compiler for a C-like language written in SML
This page took 0.037771 seconds and 4 git commands to generate.