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
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 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
(* 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
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"
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
git.joshuawise.com / snipe.git / blobdiff