commit ec89cc7eb19e39ee2d944fe3a7c2a9f32a491d92
parent 41b9d07f79446774f59af1c4a39d8b5b5f04e366
Author: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date: Fri, 9 Jan 2015 13:24:46 -0500
type surgery
Diffstat:
| M | lo2.ml | | | 40 | ++++++++++++++++++---------------------- |
1 file changed, 18 insertions(+), 22 deletions(-)
diff --git a/lo2.ml b/lo2.ml
@@ -1,35 +1,28 @@
type uop = Neg
type bop = Add | Sub | CLe | CEq
-type ('i) seqi = [ `Nop | `Uop of uop * 'i | `Bop of 'i * bop * 'i ]
-type ('i) blki = [ `Phi of 'i list | 'i seqi ]
-type ('i, 'b) jmpi = [ `Brz of 'i * 'b * 'b | `Jmp of 'b ]
+type bref = int (* Block references. *)
+type 'op seqi = [ `Nop | `Uop of uop * 'op | `Bop of 'op * bop * 'op ]
+type 'op jmpi = [ `Brz of 'op * bref * bref | `Jmp of bref ]
-type ('i, 'b, 'a) bb =
- { bb_phis: [ `Phi of 'i list ] array
- ; bb_inss: ('i seqi) array
- ; bb_jmp: ('i, 'b) jmpi
- ; mutable bb_anno: 'a
+type ('ins, 'op) bb =
+ { bb_phis: [ `Phi of 'op list ] array
+ ; bb_inss: 'ins array
+ ; bb_jmp: 'op jmpi
}
-type bref = int
-type iref = IRPhi of (bref * int) | IRIns of (bref * int)
-
-type 'a program = ((iref, bref, 'a) bb) array
-
-let gb (p: 'a program) (br: bref) = p.(br)
-let gi (p: 'a program) = function
- | IRPhi (br, pr) -> ((gb p br).bb_phis.(pr) :> iref blki)
- | IRIns (br, ir) -> ((gb p br).bb_inss.(ir) :> iref blki)
(* ** Liveness analysis. ** *)
+type iref = IRPhi of (bref * int) | IRIns of (bref * int)
+type iprog = ((iref seqi, iref) bb) array
+
module IRSet = Set.Make(
struct type t = iref let compare = compare end
)
-let liveness (p: 'a program) =
+let liveness (p: iprog) =
let module H = Hashtbl in
let changed = ref true in (* Witness for fixpoint. *)
let lh = H.create 1001 in
@@ -43,7 +36,7 @@ let liveness (p: 'a program) =
H.replace lh ir' (IRSet.add ir lir');
end in
let succs (b, i) = (* Successor nodes of an instruction. *)
- let bb = gb p b in
+ let bb = p.(b) in
if i+1 = Array.length bb.bb_inss then
if b+1 = Array.length p then [] else
match bb.bb_jmp with
@@ -51,7 +44,7 @@ let liveness (p: 'a program) =
| `Jmp b1 -> [(b1, 0)]
else [(b, i+1)] in
let gen (b, i) = IRSet.of_list
- begin match (gb p b).bb_inss.(i) with
+ begin match p.(b).bb_inss.(i) with
| `Uop (_, i1) -> [i1]
| `Bop (i1, _, i2) -> [i1; i2]
| `Nop -> []
@@ -63,7 +56,7 @@ let liveness (p: 'a program) =
while !changed do
changed := false;
for b = Array.length p - 1 downto 0 do
- let bb = gb p b in
+ let bb = p.(b) in
for i = Array.length bb.bb_inss - 1 downto 0 do
let ir = (b, i) in
let live = List.fold_left (fun live ir' ->
@@ -76,10 +69,13 @@ let liveness (p: 'a program) =
| IRPhi (b, _) | IRIns (b, _) -> b in
List.iter (fun ir ->
let br = blk ir in
- let bb = gb p br in
+ let bb = p.(br) in
setlive ir (br, Array.length bb.bb_inss - 1)
) il
) bb.bb_phis;
done
done;
lh (* Return the final hash table. *)
+
+(* ** Register allocation. ** *)
+type loc = LVoid | LReg of int | LSpill of int
