X-Git-Url: http://git.joshuawise.com/snipe.git/blobdiff_plain/0a24e44d4e9f82f8d3d83de8e58c83c8cf2868b6..a644da892dbd55a7be1aed029dafebe28d26d27e:/codegen/liveness.sml diff --git a/codegen/liveness.sml b/codegen/liveness.sml index 95f1f90..df411bb 100644 --- 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 * Author: Joshua Wise @@ -6,31 +6,51 @@ 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 - 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 - 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 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 - 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! @@ -40,93 +60,133 @@ struct 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 *) - 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 *) - 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 *) - 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 - List.map gendef l + LiveMap.mapi gendef l 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 = - 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) = - 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 : @@ -138,42 +198,34 @@ struct * live(l,x) *) - fun liveiter l p = + fun liveiter livemap preds = 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 = - 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 *) - 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 - (* 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 @@ -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 *) - 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)) ) - l - p + livemap + preds in - if subsetlive (newl, l) then l else liveiter newl p + 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 *) @@ -201,13 +260,31 @@ struct 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 (_,lives) = ListPair.unzip (liveiter init preds) + val initmap = LiveMap.foldri (fn (n,a,b) => LiveMap.insert (b, n, a)) LiveMap.empty init 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 - - fun prettyprint (a::l) = (X.prettyprint_oper a) ^ ", " ^ prettyprint l - | prettyprint nil = "-\n" - end