6 ctxt_sess: Session.sess;
9 mutable ctxt_quads: Il.quads;
10 mutable ctxt_next_spill: int;
11 mutable ctxt_next_label: int;
12 (* More state as necessary. *)
34 cx.ctxt_sess.Session.sess_log_ra
35 cx.ctxt_sess.Session.sess_log_out
38 let iflog (cx:ctxt) (thunk:(unit -> unit)) : unit =
39 if cx.ctxt_sess.Session.sess_log_ra
44 let list_to_str list eltstr =
45 (String.concat "," (List.map eltstr (List.sort compare list)))
48 let next_spill (cx:ctxt) : int =
49 let i = cx.ctxt_next_spill in
50 cx.ctxt_next_spill <- i + 1;
54 let next_label (cx:ctxt) : string =
55 let i = cx.ctxt_next_label in
56 cx.ctxt_next_label <- i + 1;
57 (".L" ^ (string_of_int i))
60 exception Ra_error of string ;;
62 let convert_labels (cx:ctxt) : unit =
63 let quad_fixups = Array.map (fun q -> q.quad_fixup) cx.ctxt_quads in
64 let qp_code (_:Il.quad_processor) (c:Il.code) : Il.code =
68 match quad_fixups.(lab) with
70 let fix = new_fixup (next_label cx) in
72 quad_fixups.(lab) <- Some fix;
77 Il.CodePtr (Il.ImmPtr (fix, Il.CodeTy))
80 let qp = { Il.identity_processor
81 with Il.qp_code = qp_code }
83 Il.rewrite_quads qp cx.ctxt_quads;
84 Array.iteri (fun i fix ->
85 cx.ctxt_quads.(i) <- { cx.ctxt_quads.(i) with
86 Il.quad_fixup = fix })
90 let convert_pre_spills
92 (mkspill:(Il.spill -> Il.mem))
95 let qp_mem (_:Il.quad_processor) (a:Il.mem) : Il.mem =
105 let qp = Il.identity_processor in
110 Il.rewrite_quads qp cx.ctxt_quads;
115 let kill_quad (i:int) (cx:ctxt) : unit =
118 Il.quad_fixup = cx.ctxt_quads.(i).Il.quad_fixup }
121 let kill_redundant_moves (cx:ctxt) : unit =
122 let process_quad i q =
123 match q.Il.quad_body with
125 ((Il.is_mov u.Il.unary_op) &&
126 (Il.Cell u.Il.unary_dst) = u.Il.unary_src) ->
130 Array.iteri process_quad cx.ctxt_quads
133 let quad_jump_target_labels (q:quad) : Il.label list =
135 match q.Il.quad_body with
136 Il.Jmp { Il.jmp_targ = Il.CodeLabel lab } -> [ lab ]
139 explicits @ q.quad_implicits;
142 let quad_used_vregs (q:quad) : Il.vreg list =
143 let vregs = ref [] in
146 Il.Vreg v -> (vregs := (v :: (!vregs)); r)
149 let qp_cell_write qp c =
152 | Il.Mem (a, b) -> Il.Mem (qp.qp_mem qp a, b)
154 let qp = { Il.identity_processor with
156 Il.qp_cell_write = qp_cell_write }
158 ignore (Il.process_quad qp q);
162 let quad_defined_vregs (q:quad) : Il.vreg list =
163 let vregs = ref [] in
164 let qp_cell_write _ c =
166 Il.Reg (Il.Vreg v, _) -> (vregs := (v :: (!vregs)); c)
169 let qp = { Il.identity_processor with
170 Il.qp_cell_write = qp_cell_write }
172 ignore (Il.process_quad qp q);
176 let quad_is_unconditional_jump (q:quad) : bool =
177 match q.Il.quad_body with
178 Il.Jmp { jmp_op = Il.JMP } -> true
183 let calculate_live_bitvectors
185 : ((Bits.t array) * (Bits.t array)) =
187 log cx "calculating live bitvectors";
189 let quads = cx.ctxt_quads in
190 let n_quads = Array.length quads in
191 let n_vregs = cx.ctxt_n_vregs in
192 let new_bitv _ = Bits.create n_vregs false in
193 let (live_in_vregs:Bits.t array) = Array.init n_quads new_bitv in
194 let (live_out_vregs:Bits.t array) = Array.init n_quads new_bitv in
196 let (quad_used_vrs:Bits.t array) = Array.init n_quads new_bitv in
197 let (quad_defined_vrs:Bits.t array) = Array.init n_quads new_bitv in
198 let (quad_uncond_jmp:bool array) = Array.make n_quads false in
199 let (quad_jmp_targs:(Il.label list) array) = Array.make n_quads [] in
201 let outer_changed = ref true in
203 (* Working bit-vector. *)
204 let scratch = new_bitv() in
206 (* bit-vector helpers. *)
208 for i = 0 to n_quads - 1 do
210 quad_uncond_jmp.(i) <- quad_is_unconditional_jump q;
211 quad_jmp_targs.(i) <- quad_jump_target_labels q;
213 (fun v -> Bits.set quad_used_vrs.(i) v true)
216 (fun v -> Bits.set quad_defined_vrs.(i) v true)
217 (quad_defined_vregs q)
220 while !outer_changed do
221 iflog cx (fun _ -> log cx "iterating outer bitvector calculation");
222 outer_changed := false;
223 for i = 0 to n_quads - 1 do
224 Bits.clear live_in_vregs.(i);
225 Bits.clear live_out_vregs.(i)
227 let inner_changed = ref true in
228 while !inner_changed do
229 inner_changed := false;
232 log cx "iterating inner bitvector calculation over %d quads"
234 for i = n_quads - 1 downto 0 do
236 let note_change b = if b then inner_changed := true in
237 let live_in = live_in_vregs.(i) in
238 let live_out = live_out_vregs.(i) in
239 let used = quad_used_vrs.(i) in
240 let defined = quad_defined_vrs.(i) in
242 (* Union in the vregs we use. *)
243 note_change (Bits.union live_in used);
245 (* Union in all our jump targets. *)
247 (fun i -> note_change (Bits.union live_out live_in_vregs.(i)))
248 (quad_jmp_targs.(i));
250 (* Union in our block successor if we have one *)
251 if i < (n_quads - 1) && (not (quad_uncond_jmp.(i)))
252 then note_change (Bits.union live_out live_in_vregs.(i+1));
254 (* Propagate live-out to live-in on anything we don't define. *)
255 ignore (Bits.copy scratch defined);
257 ignore (Bits.intersect scratch live_out);
258 note_change (Bits.union live_in scratch);
262 let kill_mov_to_dead_target i q =
263 match q.Il.quad_body with
264 Il.Unary { Il.unary_op=uop;
265 Il.unary_dst=Il.Reg (Il.Vreg v, _) }
268 not (Bits.get live_out_vregs.(i) v)) ->
271 outer_changed := true;
275 Array.iteri kill_mov_to_dead_target quads
280 log cx "finished calculating live bitvectors";
281 log cx "=========================";
282 for q = 0 to n_quads - 1 do
283 let buf = Buffer.create 128 in
284 for v = 0 to (n_vregs - 1)
286 if ((Bits.get live_in_vregs.(q) v)
287 && (Bits.get live_out_vregs.(q) v))
288 then Printf.bprintf buf " %-2d" v
289 else Buffer.add_string buf " "
291 log cx "[%6d] live vregs: %s" q (Buffer.contents buf)
293 log cx "========================="
295 (live_in_vregs, live_out_vregs)
299 let is_end_of_basic_block (q:quad) : bool =
300 match q.Il.quad_body with
306 let is_beginning_of_basic_block (q:quad) : bool =
307 match q.Il.quad_fixup with
313 let f = cx.ctxt_abi.Abi.abi_str_of_hardreg in
314 let len = (Array.length cx.ctxt_quads) - 1 in
315 let ndigits_of n = (int_of_float (log10 (float_of_int n))) in
316 let padded_num n maxnum =
317 let ndigits = ndigits_of n in
318 let maxdigits = ndigits_of maxnum in
319 let pad = String.make (maxdigits - ndigits) ' ' in
320 Printf.sprintf "%s%d" pad n
322 let padded_str str maxlen =
323 let pad = String.make (maxlen - (String.length str)) ' ' in
324 Printf.sprintf "%s%s" pad str
326 let maxlablen = ref 0 in
329 let q = cx.ctxt_quads.(i) in
330 match q.quad_fixup with
333 maxlablen := max (!maxlablen) ((String.length f.fixup_name) + 1)
337 let q = cx.ctxt_quads.(i) in
338 let qs = (string_of_quad f q) in
339 let lab = match q.quad_fixup with
341 | Some f -> f.fixup_name ^ ":"
343 log cx "[%s] %s %s" (padded_num i len) (padded_str lab (!maxlablen)) qs
347 let calculate_vreg_constraints (cx:ctxt) : Bits.t array =
348 let abi = cx.ctxt_abi in
349 let n_vregs = cx.ctxt_n_vregs in
350 let n_hregs = abi.Abi.abi_n_hardregs in
351 let constraints = Array.init n_vregs (fun _ -> Bits.create n_hregs true) in
355 abi.Abi.abi_constrain_vregs q constraints;
359 let hr_str = cx.ctxt_abi.Abi.abi_str_of_hardreg in
360 log cx "constraints for quad %d = %s"
361 i (string_of_quad hr_str q);
367 let hregs = Bits.to_list constraints.(v) in
368 log cx "<v%d> constrained to hregs: [%s]"
369 v (list_to_str hregs hr_str)
373 ignore (Il.process_quad { Il.identity_processor with
374 Il.qp_reg = qp_reg } q)
381 (* Simple local register allocator. Nothing fancy. *)
388 let cx = new_ctxt sess quads vregs abi in
393 log cx "un-allocated quads:";
398 (* Work out pre-spilled slots and allocate 'em. *)
399 let spill_slot (s:Il.spill) = abi.Abi.abi_spill_slot s in
400 let n_pre_spills = convert_pre_spills cx spill_slot in
402 let (live_in_vregs, live_out_vregs) =
403 Session.time_inner "RA liveness" sess
404 (fun _ -> calculate_live_bitvectors cx)
406 let (vreg_constraints:Bits.t array) = (* vreg idx -> hreg bits.t *)
407 calculate_vreg_constraints cx
409 let inactive_hregs = ref [] in (* [hreg] *)
410 let active_hregs = ref [] in (* [hreg] *)
411 let dirty_vregs = Hashtbl.create 0 in (* vreg -> () *)
412 let hreg_to_vreg = Hashtbl.create 0 in (* hreg -> vreg *)
413 let vreg_to_hreg = Hashtbl.create 0 in (* vreg -> hreg *)
414 let vreg_to_spill = Hashtbl.create 0 in (* vreg -> spill *)
415 let (word_ty:Il.scalar_ty) = Il.ValTy abi.Abi.abi_word_bits in
416 let vreg_spill_cell v =
417 Il.Mem ((spill_slot (Hashtbl.find vreg_to_spill v)),
421 let fixup = ref None in
423 newq := {q with quad_fixup = !fixup} :: (!newq);
426 let hr h = Il.Reg (Il.Hreg h, Il.voidptr_t) in
427 let hr_str = cx.ctxt_abi.Abi.abi_str_of_hardreg in
428 let clean_hreg i hreg =
429 if (Hashtbl.mem hreg_to_vreg hreg) &&
430 (hreg < cx.ctxt_abi.Abi.abi_n_hardregs)
432 let vreg = Hashtbl.find hreg_to_vreg hreg in
433 if Hashtbl.mem dirty_vregs vreg
436 Hashtbl.remove dirty_vregs vreg;
437 if (Bits.get (live_out_vregs.(i)) vreg)
440 if Hashtbl.mem vreg_to_spill vreg
441 then Hashtbl.find vreg_to_spill vreg
444 let s = next_spill cx in
445 Hashtbl.replace vreg_to_spill vreg s;
449 let spill_mem = spill_slot spill_idx in
450 let spill_cell = Il.Mem (spill_mem, Il.ScalarTy word_ty) in
451 log cx "spilling <%d> from %s to %s"
452 vreg (hr_str hreg) (string_of_mem hr_str spill_mem);
454 (Il.umov spill_cell (Il.Cell (hr hreg))));
461 let inactivate_hreg hreg =
462 if (Hashtbl.mem hreg_to_vreg hreg) &&
463 (hreg < cx.ctxt_abi.Abi.abi_n_hardregs)
465 let vreg = Hashtbl.find hreg_to_vreg hreg in
466 Hashtbl.remove vreg_to_hreg vreg;
467 Hashtbl.remove hreg_to_vreg hreg;
468 active_hregs := List.filter (fun x -> x != hreg) (!active_hregs);
469 inactive_hregs := hreg :: (!inactive_hregs);
473 let spill_specific_hreg i hreg =
478 let rec select_constrained
485 if Bits.get constraints h
487 else select_constrained constraints hs
490 let spill_constrained constrs i =
491 match select_constrained constrs (!active_hregs) with
493 raise (Ra_error ("unable to spill according to constraint"));
496 spill_specific_hreg i h;
501 let all_hregs = Bits.create abi.Abi.abi_n_hardregs true in
503 let spill_all_regs i =
504 while (!active_hregs) != []
506 let _ = spill_constrained all_hregs i in
511 let reload vreg hreg =
512 if Hashtbl.mem vreg_to_spill vreg
517 (Il.Cell (vreg_spill_cell vreg))))
521 let use_vreg def i vreg =
522 if Hashtbl.mem vreg_to_hreg vreg
525 let h = Hashtbl.find vreg_to_hreg vreg in
526 iflog cx (fun _ -> log cx "found cached assignment %s for <v%d>"
532 let constrs = vreg_constraints.(vreg) in
533 match select_constrained constrs (!inactive_hregs) with
535 let h = spill_constrained constrs i in
537 (fun _ -> log cx "selected %s to spill and use for <v%d>"
541 iflog cx (fun _ -> log cx "selected inactive %s for <v%d>"
546 List.filter (fun x -> x != hreg) (!inactive_hregs);
547 active_hregs := (!active_hregs) @ [hreg];
548 Hashtbl.replace hreg_to_vreg hreg vreg;
549 Hashtbl.replace vreg_to_hreg vreg hreg;
556 let qp_reg def i _ r =
558 Il.Hreg h -> (spill_specific_hreg i h; r)
559 | Il.Vreg v -> (Il.Hreg (use_vreg def i v))
561 let qp_cell def i qp c =
563 Il.Reg (r, b) -> Il.Reg (qp_reg def i qp r, b)
565 let qp = { qp with Il.qp_reg = qp_reg false i } in
566 Il.Mem (qp.qp_mem qp a, b)
568 let qp i = { Il.identity_processor with
569 Il.qp_cell_read = qp_cell false i;
570 Il.qp_cell_write = qp_cell true i;
571 Il.qp_reg = qp_reg false i }
573 cx.ctxt_next_spill <- n_pre_spills;
575 for i = 0 to cx.ctxt_abi.Abi.abi_n_hardregs - 1
577 inactive_hregs := i :: (!inactive_hregs)
579 for i = 0 to (Array.length cx.ctxt_quads) - 1
581 let quad = cx.ctxt_quads.(i) in
582 let clobbers = cx.ctxt_abi.Abi.abi_clobbers quad in
583 let used = quad_used_vregs quad in
584 let defined = quad_defined_vregs quad in
586 if List.exists (fun def -> List.mem def clobbers) defined
587 then raise (Ra_error ("clobber and defined sets overlap"));
591 let hr (v:int) : string =
592 if Hashtbl.mem vreg_to_hreg v
593 then hr_str (Hashtbl.find vreg_to_hreg v)
596 let vr_str (v:int) : string =
597 Printf.sprintf "v%d=%s" v (hr v)
600 if List.length ls = 0
602 else log cx "\t%s: [%s]" lab (list_to_str ls fn)
604 log cx "processing quad %d = %s"
605 i (string_of_quad hr_str quad);
606 (lstr "dirt" (htab_keys dirty_vregs) vr_str);
607 (lstr "clob" clobbers hr_str);
608 (lstr "in" (Bits.to_list live_in_vregs.(i)) vr_str);
609 (lstr "out" (Bits.to_list live_out_vregs.(i)) vr_str);
610 (lstr "use" used vr_str);
611 (lstr "def" defined vr_str);
613 List.iter (clean_hreg i) clobbers;
614 if is_beginning_of_basic_block quad
618 fixup := quad.quad_fixup;
619 prepend (Il.process_quad (qp i) quad)
623 fixup := quad.quad_fixup;
624 let newq = (Il.process_quad (qp i) quad) in
626 if is_end_of_basic_block quad
627 then spill_all_regs i
633 List.iter inactivate_hreg clobbers;
634 List.iter (fun i -> Hashtbl.replace dirty_vregs i ()) defined;
636 cx.ctxt_quads <- Array.of_list (List.rev (!newq));
637 kill_redundant_moves cx;
642 log cx "spills: %d pre-spilled, %d total"
643 n_pre_spills cx.ctxt_next_spill;
644 log cx "register-allocated quads:";
647 (cx.ctxt_quads, cx.ctxt_next_spill)
651 Session.fail sess "RA Error: %s" s;
660 * indent-tabs-mode: nil
661 * buffer-file-coding-system: utf-8-unix
662 * compile-command: "make -k -C ../.. 2>&1 | sed -e 's/\\/x\\//x:\\//g'";