-(* L1 Compiler
- * Gathers tiberium, fires rockets
+(* L2 Compiler
* Turns pseudoasm into liveness-annotated pseudoasm
+ * Author: Chris Lu <czl@andrew.cmu.edu>
* Author: Joshua Wise <jwise@andrew.cmu.edu>
*)
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
git.joshuawise.com / snipe.git / blobdiff