X-Git-Url: http://git.joshuawise.com/snipe.git/blobdiff_plain/1144856ba9d6018d9922c6ede7e97779a0fe6373..fe2f67179a5ea776444fdc8b30a27245867220ca:/codegen/liveness.sml diff --git a/codegen/liveness.sml b/codegen/liveness.sml index 4c8e4ad..df411bb 100644 --- a/codegen/liveness.sml +++ b/codegen/liveness.sml @@ -7,22 +7,22 @@ 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; - + type live = int * OperSet.set - type pseudoasm = x86.insn list + type pseudoasm = Blarg.insn list 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 - val uses : pred list -> x86.oper list + val uses : pred list -> Blarg.oper 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 @@ -33,10 +33,14 @@ end 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 @@ -45,7 +49,7 @@ struct 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 @@ -65,71 +69,74 @@ struct (* val defusesucc : numasm -> (ident * pred list) list * generates def/use/succ predicates according to rules *) - 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 *) - 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.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)] - | usehit (X.REL(o1, o2)) = usehit o1 @ usehit o2 - | usehit (X.OSIZE(s, oo)) = usehit oo | 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 *) - 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.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.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 @@ -241,8 +248,8 @@ struct 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" @@ -269,7 +276,7 @@ struct 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