]> 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
Fix caller/callee save impedance mismatch
[snipe.git] / codegen / liveness.sml
diff --git a/codegen/liveness.sml b/codegen/liveness.sml
index 4c8e4ad3fa868b45d00fc179e076b25198be7de7..df411bbf1441fb93f5643bafb34fbc62e2e88cd6 100644 (file)
--- a/codegen/liveness.sml
+++ b/codegen/liveness.sml
@@ -7,22 +7,22 @@
 signature LIVENESS =
 sig
   structure OperSet : ORD_SET
 signature LIVENESS =
 sig
   structure OperSet : ORD_SET
-    where type Key.ord_key = x86.oper;
+    where type Key.ord_key = Blarg.oper;
   structure LiveMap : ORD_MAP
     where type Key.ord_key = int;
   structure LiveMap : ORD_MAP
     where type Key.ord_key = int;
-  
+
   type live = int * OperSet.set
   type live = int * OperSet.set
-  type pseudoasm = x86.insn list
+  type pseudoasm = Blarg.insn list
   type livenesses = OperSet.set LiveMap.map
   
   type ident = int
   type livenesses = OperSet.set LiveMap.map
   
   type ident = int
-  datatype pred = DEF of x86.oper | USE of x86.oper | SUCC of ident | ISMOVE
+  datatype pred = DEF of Blarg.oper | USE of Blarg.oper | SUCC of ident | ISMOVE
   
   type predicates = pred list LiveMap.map
 
   
   type predicates = pred list LiveMap.map
 
-  val uses : pred list -> x86.oper list
+  val uses : pred list -> Blarg.oper list
   val succs : pred list -> ident list
   val succs : pred list -> ident list
-  val defs : pred list -> x86.oper list
+  val defs : pred list -> Blarg.oper list
   val ismove : pred list -> bool
 
   val liveness : pseudoasm -> predicates * livenesses
   val ismove : pred list -> bool
 
   val liveness : pseudoasm -> predicates * livenesses
@@ -33,10 +33,14 @@ end
 structure Liveness :> LIVENESS =
 struct
   structure T = Temp
 structure Liveness :> LIVENESS =
 struct
   structure T = Temp
-  structure X = x86
+  structure X = Blarg
   
   
-  structure OperSet = x86.OperSet
-  structure LiveMap = x86.LiveMap
+  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 live = int * OperSet.set
   type pseudoasm = X.insn list
@@ -45,7 +49,7 @@ struct
 
   type ident = int
   datatype pred = DEF of X.oper | USE of X.oper | SUCC of ident | ISMOVE
 
   type ident = int
   datatype pred = DEF of X.oper | USE of X.oper | SUCC of ident | ISMOVE
-  
+
   type predicates = pred list LiveMap.map
 
   (* val number : pseudoasm -> numasm
   type predicates = pred list LiveMap.map
 
   (* val number : pseudoasm -> numasm
@@ -65,71 +69,74 @@ struct
   (* val defusesucc : numasm -> (ident * pred list) list
    * generates def/use/succ predicates according to rules
    *)
   (* 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
-              (LiveMap.foldri (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 (X.REG a) = [DEF(X.REG 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 (X.TEMP a) = [DEF(X.TEMP a)]
-        | defhit (X.REL(o1, o2)) = usehit o1 @ usehit o2
-        | defhit (X.OSIZE(s, oo)) = defhit oo
         | defhit (_) = nil
     
       and usehit (X.REG a) = [USE(X.REG a)]
         | usehit (X.TEMP a) = [USE(X.TEMP a)]
         | defhit (_) = nil
     
       and usehit (X.REG a) = [USE(X.REG a)]
         | usehit (X.TEMP a) = [USE(X.TEMP a)]
-        | usehit (X.REL(o1, o2)) = usehit o1 @ usehit o2
-        | usehit (X.OSIZE(s, oo)) = usehit oo
         | usehit (_) = nil
 
       fun callhit 0 = nil
         | usehit (_) = nil
 
       fun callhit 0 = nil
-        | callhit 1 = USE(X.REG(X.EDI))::(callhit 0)
-        | callhit 2 = USE(X.REG(X.ESI))::(callhit 1)
-        | callhit 3 = USE(X.REG(X.EDX))::(callhit 2)
-        | callhit 4 = USE(X.REG(X.ECX))::(callhit 3)
-        | callhit 5 = USE(X.REG(X.R8D))::(callhit 4)
-        | callhit 6 = USE(X.REG(X.R9D))::(callhit 5)
-        | callhit _ = callhit 6
+        | 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(_))           = (nil)
-        | gendef (n, X.COMMENT(_))             = (nil)
+      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.LIVEIGN (_))            = ([SUCC (n+1)])
-        | gendef (n, X.MOV(dest, src))         = (defhit dest @ usehit src @ [SUCC(n+1), ISMOVE])
-        | gendef (n, X.LEA(dest, src))         = (defhit dest @ usehit src @ [SUCC(n+1)])
-        | gendef (n, X.SUB(dest, src))         = (defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
-        | gendef (n, X.IMUL(dest, src))        = (defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
-        | gendef (n, X.IMUL3(dest, src, _))    = (defhit dest @ usehit src @ [SUCC(n+1)])
-        | gendef (n, X.ADD(dest, src))         = (defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
-        | gendef (n, X.IDIV(src))              = (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)                   = ([USE(X.REG(X.EAX)), DEF(X.REG(X.EDX)), SUCC(n+1)])
-        | gendef (n, X.SAL(dest, shft))        = (defhit dest @ usehit shft @ usehit dest @ [SUCC(n+1)])
-        | gendef (n, X.SAR(dest, shft))        = (defhit dest @ usehit shft @ usehit dest @ [SUCC(n+1)])
-        | gendef (n, X.NEG(src))               = (defhit src @ usehit src @ [SUCC(n+1)])
-        | gendef (n, X.NOT(src))               = (defhit src @ usehit src @ [SUCC(n+1)])
-        | gendef (n, X.AND(dest, src))         = (defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
-        | gendef (n, X.OR(dest, src))          = (defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
-        | gendef (n, X.XOR(dest, src))         = (defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])
-        | gendef (n, X.CMP(dest, src))         = (usehit dest @ usehit src @ [SUCC(n+1)])
-        | gendef (n, X.TEST(dest, src))        = (usehit dest @ usehit src @ [SUCC(n+1)])
-        | gendef (n, X.SETcc(_,dest))          = (defhit dest @ [SUCC(n+1)])
-        | gendef (n, X.CALL(_, a))             = (callhit a @ [DEF(X.REG(X.EAX)), DEF(X.REG(X.ECX)), DEF(X.REG(X.EDX)),
-                                                                  DEF(X.REG(X.EDI)), DEF(X.REG(X.ESI)), DEF(X.REG(X.R8D)),
-                                                                  DEF(X.REG(X.R9D)), DEF(X.REG(X.R10D)), DEF(X.REG(X.R11D)), SUCC(n+1)])
-        | gendef (n, X.MOVZB(dest, src))       = (defhit dest @ usehit src @ [SUCC(n+1)])
-        | gendef (n, X.RET)                    = ([USE (X.REG X.EAX)])
         | gendef (n, X.LABEL l)                = ([SUCC (n+1)])
         | gendef (n, X.LABEL l)                = ([SUCC (n+1)])
-        | gendef (n, X.JMP l)                  = ([SUCC (findlabel l)])
-        | gendef (n, X.Jcc (_,l))              = ([SUCC (n+1), SUCC (findlabel l)])
+        | 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
         LiveMap.mapi gendef l
     end
     in
         LiveMap.mapi gendef l
     end
@@ -241,8 +248,8 @@ struct
       else liveiter newl preds
     end
 
       else liveiter newl preds
     end
 
-  fun dustostring (DEF(a)) = "DEF(" ^ X.prettyprint_oper X.Long a ^ ")"
-    | dustostring (USE(a)) = "USE(" ^ X.prettyprint_oper X.Long a ^ ")"
+  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"
 
     | dustostring (SUCC(a)) = "SUCC(" ^ Int.toString a ^ ")"
     | dustostring ISMOVE = "ISMOVE"
 
@@ -269,7 +276,7 @@ struct
   
   fun prettyprint (set) =
     OperSet.foldr
   
   fun prettyprint (set) =
     OperSet.foldr
-      (fn (oper, s) => (X.prettyprint_oper X.Long oper) ^ ", " ^ s)
+      (fn (oper, s) => (X.pp_oper oper) ^ ", " ^ s)
       "-\n"
       set
       
       "-\n"
       set
       
Compiler for a C-like language written in SML
This page took 0.031579 seconds and 4 git commands to generate.