+ 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 (_) = nil
+
+ fun usehit (X.REG a) = [USE(X.REG a)]
+ | usehit (X.TEMP a) = [USE(X.TEMP a)]
+ | 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.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) = ([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