X-Git-Url: http://git.joshuawise.com/snipe.git/blobdiff_plain/12aa4087bee3e70f170d7457794921de4e385227..1144856ba9d6018d9922c6ede7e97779a0fe6373:/codegen/liveness.sml diff --git a/codegen/liveness.sml b/codegen/liveness.sml index 34f5d47..4c8e4ad 100644 --- a/codegen/liveness.sml +++ b/codegen/liveness.sml @@ -1,15 +1,33 @@ -(* L1 Compiler - * Gathers tiberium, fires rockets +(* L3 Compiler * Turns pseudoasm into liveness-annotated pseudoasm + * Author: Chris Lu * Author: Joshua Wise *) signature LIVENESS = sig - type tiberium = x86.insn list - type rockets = x86.oper list list + structure OperSet : ORD_SET + where type Key.ord_key = x86.oper; + structure LiveMap : ORD_MAP + where type Key.ord_key = int; + + type live = int * OperSet.set + type pseudoasm = x86.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 + + type predicates = pred list LiveMap.map - val liveness : tiberium -> rockets + val uses : pred list -> x86.oper list + val succs : pred list -> ident list + val defs : pred list -> x86.oper list + val ismove : pred list -> bool + + val liveness : pseudoasm -> predicates * livenesses + val listify : livenesses -> OperSet.set list + val prettyprint : OperSet.set -> string end structure Liveness :> LIVENESS = @@ -17,53 +35,249 @@ struct structure T = Temp structure X = x86 - type tiberium = x86.insn list - type rockets = x86.oper list list + structure OperSet = x86.OperSet + structure LiveMap = x86.LiveMap + + type live = int * OperSet.set + type pseudoasm = X.insn 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 | ISMOVE + + type predicates = pred list LiveMap.map + + (* val number : pseudoasm -> numasm + * numbers the instructions! + *) + + fun number instrs = + let + val nums = List.tabulate (List.length instrs, (fn i => i)) + in + 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 + (LiveMap.foldri (fn (n, X.LABEL lb', NONE) => if (Label.compare (lb, lb') = EQUAL) then SOME n else NONE + | (_, _, old) => old) NONE l) + + (* val defhit/usehit : X.oper -> pred list + * helper functions to discard constant operands *) + fun 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 + + (* 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) + | 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)]) + in + LiveMap.mapi gendef l + end + + (* val uselive : (int * pred list) list -> OperSet.set LiveMap.map + * generates liveness for 'use' rules to get the iterative analyzer started + *) + fun uselive preds = + LiveMap.mapi + (fn (n, pl) => + foldr + (fn (USE (l), set) => OperSet.add (set, l) + | (_, set) => set) + OperSet.empty + pl + ) + preds + + (* val subsetlive : OperSet.set LiveMap.map * OperSet.set LiveMap.map -> bool + * true if first is subset of second + *) + + fun subsetlive (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 - (* This does not 'follow the rules'. + 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 : 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 : * - * Since this is a straight line, we can just fold starting at the right, - * and accumulate variables. Thus, the accumulator has two parts: one to - * represent all of the line / liveness pairs that we've accumulated so far; - * and one to represent what was live at the previous line. + * use(l',x) + * !def(l,x) + * succ(l,l') + * -------------- + * live(l,x) *) - fun mashinstr ((instr : x86.insn), (curtemps, output) : x86.oper list * rockets) : x86.oper list * rockets = + + fun liveiter livemap preds = let - (* Removes an element from a list. *) - fun blast (X.TEMP(elt)) l = - List.filter (fn a => case a of X.TEMP(b) => (T.compare (b, elt)) <> EQUAL | _ => true) l - | blast (X.REG(reg)) l = - List.filter (fn a => case a of X.REG(b) => b <> reg | _ => true) l - | blast _ l = raise ErrorMsg.InternalError "Why have we declared a CONST as live?" - - (* Adds an element to a list iff the element doesn't exist already. *) - fun addonce (X.CONST(_)) l = l - | addonce oper l = oper :: blast oper l - - val newtemps = - case instr - of X.DIRECTIVE(_) => curtemps - | X.COMMENT(_) => curtemps - | X.MOVL(dest, src) => addonce src (blast dest curtemps) - | X.SUBL(dest, src) => addonce src (addonce dest curtemps) - | X.IMUL(dest, src) => addonce src (addonce dest curtemps) - | X.IMUL3(dest, src, _) => addonce src (blast dest curtemps) - | X.ADDL(dest, src) => addonce src (addonce dest curtemps) - | X.LEAL(dest, src1, src2) => addonce src1 (addonce src2 (blast dest curtemps)) - | X.IDIVL(src) => addonce src (addonce (X.REG X.EAX) (addonce (X.REG X.EDX) curtemps)) - | X.CLTD => blast (X.REG X.EDX) (addonce (X.REG X.EAX) curtemps) - | X.NEG(src) => (* meh *) curtemps - | X.RET => addonce (X.REG X.EAX) curtemps -(* | _ => raise ErrorMsg.InternalError "Unable to compute liveness for unused instruction form";*) + + + (* val lives : int list -> OperSet.set LiveMap.map -> OperSet.set + * scans l for live variables in succeeding lines *) + fun lives l' idents = + 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.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 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 + * not defined here; if so, it accumulates them onto the inital list + * + * changing the first foldr to a foldl slows down liveness by a factor + * of at least 100 on cedar-anastulate.l2 + *) + 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)) + ) + livemap + preds + in + if subsetlive (newl, livemap) + then livemap + 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 ^ ")" + | dustostring (SUCC(a)) = "SUCC(" ^ Int.toString a ^ ")" + | dustostring ISMOVE = "ISMOVE" + + (* val liveness : pseudoasm -> livenesses + * analyzes liveness of variables in the given pseudo-asm + *) + + 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 initmap = LiveMap.foldri (fn (n,a,b) => LiveMap.insert (b, n, a)) LiveMap.empty init in - (newtemps, newtemps :: output) + (preds, liveiter initmap preds) end - fun liveness (instrs : tiberium) : rockets = + fun prettyprint (set) = + OperSet.foldr + (fn (oper, s) => (X.prettyprint_oper X.Long oper) ^ ", " ^ s) + "-\n" + set + + fun listify map = let - val (_, livelist) = foldr mashinstr (nil, nil) instrs + val maxln = LiveMap.foldri (fn (a, _, b) => Int.max (a, b)) 0 map + val nums = List.tabulate (maxln+1, fn x => x) in - livelist + List.map (fn num => valOf (LiveMap.find (map, num)) handle Option => OperSet.empty) nums end end