X-Git-Url: http://git.joshuawise.com/snipe.git/blobdiff_plain/12aa4087bee3e70f170d7457794921de4e385227..0a24e44d4e9f82f8d3d83de8e58c83c8cf2868b6:/codegen/liveness.sml diff --git a/codegen/liveness.sml b/codegen/liveness.sml index 34f5d47..95f1f90 100644 --- a/codegen/liveness.sml +++ b/codegen/liveness.sml @@ -1,69 +1,213 @@ -(* L1 Compiler - * Gathers tiberium, fires rockets +(* L2 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 - val liveness : tiberium -> rockets + type live = int * x86.oper list + type pseudoasm = x86.insn list + type livenesses = x86.oper list list + + type ident = int + datatype pred = DEF of x86.oper | USE of x86.oper | SUCC of ident + + val liveness : pseudoasm -> livenesses + val prettyprint : x86.oper list -> string end structure Liveness :> LIVENESS = struct structure T = Temp structure X = x86 - - type tiberium = x86.insn list - type rockets = x86.oper list list - (* This does not 'follow the rules'. + + type live = int * x86.oper list + type pseudoasm = X.insn list + type numasm = (int * X.insn) list + type livenesses = X.oper list list + + type ident = int + datatype pred = DEF of X.oper | USE of X.oper | SUCC of ident + + (* val number : pseudoasm -> numasm + * numbers the instructions! + *) + + fun number instrs = + let + val nums = List.tabulate (List.length instrs, (fn i => i)) + in + 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 defhit/usehit : X.oper -> pred list + * helper functions to discard constant operands *) + fun defhit (a as X.CONST(_)) = nil + | defhit (a) = [DEF(a)] + + fun usehit (a as X.CONST(_)) = nil + | usehit (a) = [USE(a)] + + (* 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)]) + in + List.map gendef l + end + + (* val uselive : (ident * pred list) list -> live list + * 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 + ) + ) + preds + + (* val subsetlive : (ident * pred list) * (ident * pred list) -> 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) + + (* val liveiter : live list -> (ident * pred list) list -> live list + * 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 l p = 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 + * 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') - (* 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 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 + | 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 + + (* 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 = List.foldr + (fn ((n, a), b) => List.foldr + (fn (a',b') => if (isndef a' a) then liveadd (n, a') b' else b') + b + (lives b (succs a)) + ) + l + p in - (newtemps, newtemps :: output) + if subsetlive (newl, l) then l else liveiter newl p end - - fun liveness (instrs : tiberium) : rockets = + + (* val liveness : pseudoasm -> livenesses + * analyzes liveness of variables in the given pseudo-asm + *) + + fun liveness instrs = let - val (_, livelist) = foldr mashinstr (nil, nil) instrs + val preds = defusesucc (number instrs) + val init = uselive preds + val (_,lives) = ListPair.unzip (liveiter init preds) in - livelist + lives end + + fun prettyprint (a::l) = (X.prettyprint_oper a) ^ ", " ^ prettyprint l + | prettyprint nil = "-\n" + end