-
Notifications
You must be signed in to change notification settings - Fork 0
/
regAllocSecond.ml
248 lines (239 loc) · 10.9 KB
/
regAllocSecond.ml
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
open Asm
(* for register coalescing *)
(* [XXX] Callがあったら、そこから先は無意味というか逆効果なので追わない。
そのために「Callがあったかどうか」を返り値の第1要素に含める。 *)
let rec target' src (dest, t) = function
| Mr(x) when x = src && is_reg dest ->
assert (t <> Type.Unit);
assert (t <> Type.Float);
false, [dest]
| FMr(x) when x = src && is_reg dest ->
assert (t = Type.Float);
false, [dest]
| IfEq(_, _, e1, e2) | IfLE(_, _, e1, e2) | IfGE(_, _, e1, e2)
| IfFEq(_, _, e1, e2) | IfFLE(_, _, e1, e2) ->
let c1, rs1 = target src (dest, t) e1 in
let c2, rs2 = target src (dest, t) e2 in
c1 && c2, rs1 @ rs2
| CallCls(x, ys, zs) ->
true, (target_args src regs 0 ys @
target_args src fregs 0 zs @
if x = src then [reg_cl] else [])
| CallDir(_, ys, zs) ->
true, (target_args src regs 0 ys @
target_args src fregs 0 zs)
| _ -> false, []
and target src dest = function (* register targeting (caml2html: regalloc_target) *)
| Ans(exp) -> target' src dest exp
| Let(xt, exp, e) ->
let c1, rs1 = target' src xt exp in
if c1 then true, rs1 else
let c2, rs2 = target src dest e in
c2, rs1 @ rs2
and target_args src all n = function (* auxiliary function for Call *)
| [] -> []
| y :: ys when src = y -> all.(n) :: target_args src all (n + 1) ys
| _ :: ys -> target_args src all (n + 1) ys
let rec list_diff la lb =
match la with
| [] -> []
| x :: rest -> if List.mem x lb then list_diff rest lb
else x :: (list_diff rest lb)
type alloc_result = (* allocにおいてspillingがあったかどうかを表すデータ型 *)
| Alloc of Id.t (* allocated register *)
| Spill of Id.t (* spilled variable *)
let rec alloc dest cont regenv x t =
(* allocate a register or spill a variable *)
assert (not (M.mem x regenv));
let all =
(
match t with
| Type.Unit -> ["%r0"] (* dummy *)
(* 定数レジスタにしたレジスタを除いて再度レジスタ割付をする。候補のレジスタのリストの順を変えたくない(S.elementsで並び変わると結果がregAllocと違うものになりやすそう)ので冗長だがlist_diffをとっている*)
| Type.Float -> let unused_fregs = S.elements (S.diff (S.of_list Asm.allfregs) (!RegCollect.used_regs)) in
list_diff allfregs unused_fregs
| _ -> let unused_regs = S.elements (S.diff (S.of_list Asm.allregs) (!RegCollect.used_regs)) in
list_diff allregs unused_regs
) in
if all = ["%r0"] then Alloc("%r0") else (* [XX] ad hoc optimization *)
if is_reg x then Alloc(x) else
let free = fv cont in
try
let (c, prefer) = target x dest cont in
let live = (* 生きているレジスタ *)
List.fold_left
(fun live y ->
if is_reg y then S.add y live else
try S.add (M.find y regenv) live
with Not_found -> live)
S.empty
free in
let r = (* そうでないレジスタを探す *)
List.find
(fun r -> not (S.mem r live))
(prefer @ all) in
(* Format.eprintf "allocated %s to %s@." x r; *)
Alloc(r)
with Not_found ->
Format.eprintf "register allocation failed for %s@." x;
let y = (* 型の合うレジスタ変数を探す *)
List.find
(fun y ->
not (is_reg y) &&
try List.mem (M.find y regenv) all
with Not_found -> false)
(List.rev free) in
Format.eprintf "spilling %s from %s@." y (M.find y regenv);
Spill(y)
(* auxiliary function for g and g'_and_restore *)
let add x r regenv =
if is_reg x then (assert (x = r); regenv) else
M.add x r regenv
(* auxiliary functions for g' *)
exception NoReg of Id.t * Type.t
let find x t regenv =
if is_reg x then x else
try M.find x regenv
with Not_found -> raise (NoReg(x, t))
let find' x' regenv =
match x' with
| V(x) -> V(find x Type.Int regenv)
| c -> c
let rec g dest cont regenv = function (* 命令列のレジスタ割り当て (caml2html: regalloc_g) *)
| Ans(exp) -> g'_and_restore dest cont regenv exp
| Let((x, t) as xt, exp, e) ->
assert (not (M.mem x regenv));
let cont' = concat e dest cont in
let (e1', regenv1) = g'_and_restore xt cont' regenv exp in
(match alloc dest cont' regenv1 x t with
| Spill(y) ->
let r = M.find y regenv1 in
let (e2', regenv2) = g dest cont (add x r (M.remove y regenv1)) e in
let save =
try Save(M.find y regenv, y)
with Not_found -> Nop in
(seq(save, concat e1' (r, t) e2'), regenv2)
| Alloc(r) ->
let (e2', regenv2) = g dest cont (add x r regenv1) e in
(concat e1' (r, t) e2', regenv2))
and g'_and_restore dest cont regenv exp = (* 使用される変数をスタックからレジスタへRestore (caml2html: regalloc_unspill) *)
try g' dest cont regenv exp
with NoReg(x, t) ->
((* Format.eprintf "restoring %s@." x; *)
g dest cont regenv (Let((x, t), Restore(x), Ans(exp))))
and g' dest cont regenv = function (* 各命令のレジスタ割り当て (caml2html: regalloc_gprime) *)
| Nop | Li _ | SetL _ | Comment _ | Restore _ | FLi _ as exp -> (Ans(exp), regenv)
| Mr(x) -> (Ans(Mr(find x Type.Int regenv)), regenv)
| Neg(x) -> (Ans(Neg(find x Type.Int regenv)), regenv)
| Add(x, y') -> (Ans(Add(find x Type.Int regenv, find' y' regenv)), regenv)
| Sub(x, y') -> (Ans(Sub(find x Type.Int regenv, find' y' regenv)), regenv)
| Mul(x, y') -> (Ans(Mul(find x Type.Int regenv, find' y' regenv)), regenv)
| Div(x, y') -> (Ans(Div(find x Type.Int regenv, find' y' regenv)), regenv)
| Slw(x, y') -> (Ans(Slw(find x Type.Int regenv, find' y' regenv)), regenv)
| Xor(x, y') -> (Ans(Xor(find x Type.Int regenv, find' y' regenv)), regenv)
| Lwz(x, y') -> (Ans(Lwz(find x Type.Int regenv, find' y' regenv)), regenv)
| Stw(x, y, z') -> (Ans(Stw(find x Type.Int regenv, find y Type.Int regenv, find' z' regenv)), regenv)
| FMr(x) -> (Ans(FMr(find x Type.Float regenv)), regenv)
| FNeg(x) -> (Ans(FNeg(find x Type.Float regenv)), regenv)
| FAdd(x, y) -> (Ans(FAdd(find x Type.Float regenv, find y Type.Float regenv)), regenv)
| FSub(x, y) -> (Ans(FSub(find x Type.Float regenv, find y Type.Float regenv)), regenv)
| FMul(x, y) -> (Ans(FMul(find x Type.Float regenv, find y Type.Float regenv)), regenv)
| FDiv(x, y) -> (Ans(FDiv(find x Type.Float regenv, find y Type.Float regenv)), regenv)
| Sltf(x, y) -> (Ans(Sltf(find x Type.Float regenv, find y Type.Float regenv)), regenv)
| Slt(x, y) -> (Ans(Slt(find x Type.Int regenv, find y Type.Int regenv)), regenv)
| Sqrt(x) -> (Ans(Sqrt(find x Type.Float regenv)), regenv)
| Floor(x) -> (Ans(Floor(find x Type.Float regenv)), regenv)
| FAbs(x) -> (Ans(FAbs(find x Type.Float regenv)), regenv)
| Ftoi(x) -> (Ans(Ftoi(find x Type.Float regenv)), regenv)
| Itof(x) -> (Ans(Itof(find x Type.Int regenv)), regenv)
| Outb(x) -> (Ans(Outb(find x Type.Int regenv)), regenv)
| In as exp -> (Ans(exp), regenv)
| Inf as exp -> (Ans(exp), regenv)
| Lfd(x, y') -> (Ans(Lfd(find x Type.Int regenv, find' y' regenv)), regenv)
| Stfd(x, y, z') -> (Ans(Stfd(find x Type.Float regenv, find y Type.Int regenv, find' z' regenv)), regenv)
| IfEq(x, y', e1, e2) as exp -> g'_if dest cont regenv exp (fun e1' e2' -> IfEq(find x Type.Int regenv, find' y' regenv, e1', e2')) e1 e2
| IfLE(x, y', e1, e2) as exp -> g'_if dest cont regenv exp (fun e1' e2' -> IfLE(find x Type.Int regenv, find' y' regenv, e1', e2')) e1 e2
| IfGE(x, y', e1, e2) as exp -> g'_if dest cont regenv exp (fun e1' e2' -> IfGE(find x Type.Int regenv, find' y' regenv, e1', e2')) e1 e2
| IfFEq(x, y, e1, e2) as exp -> g'_if dest cont regenv exp (fun e1' e2' -> IfFEq(find x Type.Float regenv, find y Type.Float regenv, e1', e2')) e1 e2
| IfFLE(x, y, e1, e2) as exp -> g'_if dest cont regenv exp (fun e1' e2' -> IfFLE(find x Type.Float regenv, find y Type.Float regenv, e1', e2')) e1 e2
| CallCls(x, ys, zs) as exp ->
if List.length ys > Array.length regs - 2 || List.length zs > Array.length fregs - 1 then
failwith (Format.sprintf "cannot allocate registers for arugments to %s" x)
else
g'_call dest cont regenv exp (fun ys zs -> CallCls(find x Type.Int regenv, ys, zs)) ys zs
| CallDir(Id.L(x), ys, zs) as exp ->
if List.length ys > Array.length regs - 1 || List.length zs > Array.length fregs - 1 then
failwith (Format.sprintf "cannot allocate registers for arugments to %s" x)
else
g'_call dest cont regenv exp (fun ys zs -> CallDir(Id.L(x), ys, zs)) ys zs
| Save(x, y) -> assert false
and g'_if dest cont regenv exp constr e1 e2 = (* ifのレジスタ割り当て (caml2html: regalloc_if) *)
let (e1', regenv1) = g dest cont regenv e1 in
let (e2', regenv2) = g dest cont regenv e2 in
let regenv' = (* 両方に共通のレジスタ変数だけ利用 *)
List.fold_left
(fun regenv' x ->
try
if is_reg x then regenv' else
let r1 = M.find x regenv1 in
let r2 = M.find x regenv2 in
if r1 <> r2 then regenv' else
M.add x r1 regenv'
with Not_found -> regenv')
M.empty
(fv cont) in
(List.fold_left
(fun e x ->
if x = fst dest || not (M.mem x regenv) || M.mem x regenv' then e else
seq(Save(M.find x regenv, x), e)) (* そうでない変数は分岐直前にセーブ *)
(Ans(constr e1' e2'))
(fv cont),
regenv')
and g'_call dest cont regenv exp constr ys zs = (* 関数呼び出しのレジスタ割り当て (caml2html: regalloc_call) *)
(List.fold_left
(fun e x ->
if x = fst dest || not (M.mem x regenv) then e else
seq(Save(M.find x regenv, x), e))
(Ans(constr
(List.map (fun y -> find y Type.Int regenv) ys)
(List.map (fun z -> find z Type.Float regenv) zs)))
(fv cont),
M.empty)
let h { name = Id.L(x); args = ys; fargs = zs; body = e; ret = t } = (* 関数のレジスタ割り当て (caml2html: regalloc_h) *)
let regenv = M.add x reg_cl M.empty in
let (i, arg_regs, regenv) =
List.fold_left
(fun (i, arg_regs, regenv) y ->
let r = regs.(i) in
(i + 1,
arg_regs @ [r],
(assert (not (is_reg y));
M.add y r regenv)))
(0, [], regenv)
ys in
let (d, farg_regs, regenv) =
List.fold_left
(fun (d, farg_regs, regenv) z ->
let fr = fregs.(d) in
(d + 1,
farg_regs @ [fr],
(assert (not (is_reg z));
M.add z fr regenv)))
(0, [], regenv)
zs in
let a =
match t with
| Type.Unit -> Id.gentmp Type.Unit
| Type.Float -> fregs.(0)
| _ -> regs.(0) in
let (e', regenv') = g (a, t) (Ans(Mr(a))) regenv e in
{ name = Id.L(x); args = arg_regs; fargs = farg_regs; body = e'; ret = t }
let f (Prog(data, fundefs, e)) = (* プログラム全体のレジスタ割り当て (caml2html: regalloc_f) *)
Format.eprintf "[regAllocSecond] register allocation: may take some time (up to a few minutes, depending on the size of functions)@.";
let fundefs' = List.map h fundefs in
let e', regenv' = g (Id.gentmp Type.Unit, Type.Unit) (Ans(Nop)) M.empty e in
Printf.eprintf "[regAllocSecond]\n";
(*
print_syntax stderr e';
*)
Prog(data, fundefs', e')