-(* L2 Compiler
+(* L3 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 live = int * x86.oper 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 = x86.oper list 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 x86.oper | USE of x86.oper | SUCC of ident | ISMOVE
+
+ type predicates = pred list LiveMap.map
+
+ 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 -> 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 OperSet = x86.OperSet
+ structure LiveMap = x86.LiveMap
-
- 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!
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
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)
+ (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 (a as X.CONST(_)) = nil
- | defhit (a) = [DEF(a)]
+ fun defhit (X.REG a) = [DEF(X.REG a)]
+ | defhit (X.TEMP a) = [DEF(X.TEMP a)]
+ | defhit (_) = nil
+
+ fun 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.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(_)) = (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)),
+ fun gendef (n, X.DIRECTIVE(_)) = (nil)
+ | gendef (n, X.COMMENT(_)) = (nil)
+ | gendef (n, X.LIVEIGN (_)) = ([SUCC (n+1)])
+ | gendef (n, X.SIZE(_, i)) = gendef (n,i)
+ | gendef (n, X.MOV(dest, src)) = (defhit dest @ usehit src @ [SUCC(n+1), ISMOVE])
+ | 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) = (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)])
+ | 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
- 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 :
* 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
* 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.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 (_,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.prettyprint_oper X.Long 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
git.joshuawise.com / snipe.git / blobdiff