]> git.lizzy.rs Git - rust.git/blob - src/boot/be/ra.ml
Populate tree.
[rust.git] / src / boot / be / ra.ml
1 open Il;;
2 open Common;;
3
4 type ctxt =
5     {
6       ctxt_sess: Session.sess;
7       ctxt_n_vregs: int;
8       ctxt_abi: Abi.abi;
9       mutable ctxt_quads: Il.quads;
10       mutable ctxt_next_spill: int;
11       mutable ctxt_next_label: int;
12       (* More state as necessary. *)
13     }
14 ;;
15
16 let new_ctxt
17     (sess:Session.sess)
18     (quads:Il.quads)
19     (vregs:int)
20     (abi:Abi.abi)
21     : ctxt =
22   {
23     ctxt_sess = sess;
24     ctxt_quads = quads;
25     ctxt_n_vregs = vregs;
26     ctxt_abi = abi;
27     ctxt_next_spill = 0;
28     ctxt_next_label = 0;
29   }
30 ;;
31
32 let log (cx:ctxt) =
33   Session.log "ra"
34     cx.ctxt_sess.Session.sess_log_ra
35     cx.ctxt_sess.Session.sess_log_out
36 ;;
37
38 let iflog (cx:ctxt) (thunk:(unit -> unit)) : unit =
39   if cx.ctxt_sess.Session.sess_log_ra
40   then thunk ()
41   else ()
42 ;;
43
44 let list_to_str list eltstr =
45   (String.concat "," (List.map eltstr (List.sort compare list)))
46 ;;
47
48 let next_spill (cx:ctxt) : int =
49   let i = cx.ctxt_next_spill in
50     cx.ctxt_next_spill <- i + 1;
51     i
52 ;;
53
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))
58 ;;
59
60 exception Ra_error of string ;;
61
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 =
65     match c with
66         Il.CodeLabel lab ->
67           let fix =
68             match quad_fixups.(lab) with
69                 None ->
70                   let fix = new_fixup (next_label cx) in
71                     begin
72                       quad_fixups.(lab) <- Some fix;
73                       fix
74                     end
75               | Some f -> f
76           in
77             Il.CodePtr (Il.ImmPtr (fix, Il.CodeTy))
78       | _ -> c
79   in
80   let qp = { Il.identity_processor
81              with Il.qp_code = qp_code }
82   in
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 })
87       quad_fixups;
88 ;;
89
90 let convert_pre_spills
91     (cx:ctxt)
92     (mkspill:(Il.spill -> Il.mem))
93     : int =
94   let n = ref 0 in
95   let qp_mem (_:Il.quad_processor) (a:Il.mem) : Il.mem =
96     match a with
97         Il.Spill i ->
98           begin
99             if i+1 > (!n)
100             then n := i+1;
101             mkspill i
102           end
103       | _ -> a
104   in
105   let qp = Il.identity_processor in
106   let qp = { qp with
107                Il.qp_mem = qp_mem  }
108   in
109     begin
110       Il.rewrite_quads qp cx.ctxt_quads;
111       !n
112     end
113 ;;
114
115 let kill_quad (i:int) (cx:ctxt) : unit =
116   cx.ctxt_quads.(i) <-
117     { Il.deadq with
118         Il.quad_fixup = cx.ctxt_quads.(i).Il.quad_fixup }
119 ;;
120
121 let kill_redundant_moves (cx:ctxt) : unit =
122   let process_quad i q =
123     match q.Il.quad_body with
124         Il.Unary u when
125           ((Il.is_mov u.Il.unary_op) &&
126              (Il.Cell u.Il.unary_dst) = u.Il.unary_src) ->
127             kill_quad i cx
128       | _ -> ()
129   in
130     Array.iteri process_quad cx.ctxt_quads
131 ;;
132
133 let quad_jump_target_labels (q:quad) : Il.label list =
134   let explicits =
135     match q.Il.quad_body with
136         Il.Jmp { Il.jmp_targ = Il.CodeLabel lab } -> [ lab ]
137       | _ -> []
138   in
139     explicits @ q.quad_implicits;
140 ;;
141
142 let quad_used_vregs (q:quad) : Il.vreg list =
143   let vregs = ref [] in
144   let qp_reg _ r =
145     match r with
146         Il.Vreg v -> (vregs := (v :: (!vregs)); r)
147       | _ -> r
148   in
149   let qp_cell_write qp c =
150     match c with
151         Il.Reg _ -> c
152       | Il.Mem (a, b) -> Il.Mem (qp.qp_mem qp a, b)
153   in
154   let qp = { Il.identity_processor with
155                Il.qp_reg = qp_reg;
156                Il.qp_cell_write = qp_cell_write }
157   in
158     ignore (Il.process_quad qp q);
159     !vregs
160 ;;
161
162 let quad_defined_vregs (q:quad) : Il.vreg list =
163   let vregs = ref [] in
164   let qp_cell_write _ c =
165     match c with
166         Il.Reg (Il.Vreg v, _) -> (vregs := (v :: (!vregs)); c)
167       | _ -> c
168   in
169   let qp = { Il.identity_processor with
170                Il.qp_cell_write = qp_cell_write }
171   in
172     ignore (Il.process_quad qp q);
173     !vregs
174 ;;
175
176 let quad_is_unconditional_jump (q:quad) : bool =
177   match q.Il.quad_body with
178       Il.Jmp { jmp_op = Il.JMP } -> true
179     | Il.Ret -> true
180     | _ -> false
181 ;;
182
183 let calculate_live_bitvectors
184     (cx:ctxt)
185     : ((Bits.t array) * (Bits.t array)) =
186
187   log cx "calculating live bitvectors";
188
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
195
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
200
201   let outer_changed = ref true in
202
203   (* Working bit-vector. *)
204   let scratch = new_bitv() in
205
206   (* bit-vector helpers. *)
207     (* Setup pass. *)
208     for i = 0 to n_quads - 1 do
209       let q = quads.(i) in
210         quad_uncond_jmp.(i) <- quad_is_unconditional_jump q;
211         quad_jmp_targs.(i) <- quad_jump_target_labels q;
212         List.iter
213           (fun v -> Bits.set quad_used_vrs.(i) v true)
214           (quad_used_vregs q);
215         List.iter
216           (fun v -> Bits.set quad_defined_vrs.(i) v true)
217           (quad_defined_vregs q)
218     done;
219
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)
226       done;
227       let inner_changed = ref true in
228         while !inner_changed do
229           inner_changed := false;
230           iflog cx
231             (fun _ ->
232                log cx "iterating inner bitvector calculation over %d quads"
233                  n_quads);
234           for i = n_quads - 1 downto 0 do
235
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
241
242               (* Union in the vregs we use. *)
243               note_change (Bits.union live_in used);
244
245               (* Union in all our jump targets. *)
246               List.iter
247                 (fun i -> note_change (Bits.union live_out live_in_vregs.(i)))
248                 (quad_jmp_targs.(i));
249
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));
253
254               (* Propagate live-out to live-in on anything we don't define. *)
255               ignore (Bits.copy scratch defined);
256               Bits.invert scratch;
257               ignore (Bits.intersect scratch live_out);
258               note_change (Bits.union live_in scratch);
259
260           done
261         done;
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, _) }
266                 when
267                   ((Il.is_mov uop) &&
268                      not (Bits.get live_out_vregs.(i) v)) ->
269                   begin
270                     kill_quad i cx;
271                     outer_changed := true;
272                   end
273             | _ -> ()
274         in
275           Array.iteri kill_mov_to_dead_target quads
276     done;
277     iflog cx
278       begin
279         fun _ ->
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)
285               do
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 "   "
290               done;
291               log cx "[%6d] live vregs: %s" q (Buffer.contents buf)
292           done;
293           log cx "========================="
294       end;
295     (live_in_vregs, live_out_vregs)
296 ;;
297
298
299 let is_end_of_basic_block (q:quad) : bool =
300   match q.Il.quad_body with
301       Il.Jmp _ -> true
302     | Il.Ret -> true
303     | _ -> false
304 ;;
305
306 let is_beginning_of_basic_block (q:quad) : bool =
307   match q.Il.quad_fixup with
308       None -> false
309     | Some _ -> true
310 ;;
311
312 let dump_quads cx =
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
321   in
322   let padded_str str maxlen =
323     let pad = String.make (maxlen - (String.length str)) ' ' in
324       Printf.sprintf "%s%s" pad str
325   in
326   let maxlablen = ref 0 in
327   for i = 0 to len
328   do
329     let q = cx.ctxt_quads.(i) in
330     match q.quad_fixup with
331         None -> ()
332       | Some f ->
333           maxlablen := max (!maxlablen) ((String.length f.fixup_name) + 1)
334   done;
335   for i = 0 to len
336   do
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
340         None -> ""
341       | Some f -> f.fixup_name ^ ":"
342     in
343       log cx "[%s] %s %s" (padded_num i len) (padded_str lab (!maxlablen)) qs
344   done
345 ;;
346
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
352     Array.iteri
353       begin
354         fun i q ->
355           abi.Abi.abi_constrain_vregs q constraints;
356           iflog cx
357             begin
358               fun _ ->
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);
362                   let qp_reg _ r =
363                     begin
364                       match r with
365                           Il.Hreg _ -> ()
366                         | Il.Vreg v ->
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)
370                     end;
371                     r
372                   in
373                     ignore (Il.process_quad { Il.identity_processor with
374                                                 Il.qp_reg = qp_reg } q)
375             end;
376       end
377       cx.ctxt_quads;
378     constraints
379 ;;
380
381 (* Simple local register allocator. Nothing fancy. *)
382 let reg_alloc
383     (sess:Session.sess)
384     (quads:Il.quads)
385     (vregs:int)
386     (abi:Abi.abi) =
387  try
388     let cx = new_ctxt sess quads vregs abi in
389     let _ =
390       iflog cx
391         begin
392           fun _ ->
393             log cx "un-allocated quads:";
394             dump_quads cx
395         end
396     in
397
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
401
402     let (live_in_vregs, live_out_vregs) =
403       Session.time_inner "RA liveness" sess
404         (fun _ -> calculate_live_bitvectors cx)
405     in
406     let (vreg_constraints:Bits.t array) = (* vreg idx -> hreg bits.t *)
407       calculate_vreg_constraints cx
408     in
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)),
418               Il.ScalarTy word_ty)
419     in
420     let newq = ref [] in
421     let fixup = ref None in
422     let prepend q =
423       newq := {q with quad_fixup = !fixup} :: (!newq);
424       fixup := None
425     in
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)
431       then
432         let vreg = Hashtbl.find hreg_to_vreg hreg in
433           if Hashtbl.mem dirty_vregs vreg
434           then
435             begin
436               Hashtbl.remove dirty_vregs vreg;
437               if (Bits.get (live_out_vregs.(i)) vreg)
438               then
439                 let spill_idx =
440                   if Hashtbl.mem vreg_to_spill vreg
441                   then Hashtbl.find vreg_to_spill vreg
442                   else
443                     begin
444                       let s = next_spill cx in
445                         Hashtbl.replace vreg_to_spill vreg s;
446                         s
447                     end
448                 in
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);
453                   prepend (Il.mk_quad
454                              (Il.umov spill_cell (Il.Cell (hr hreg))));
455               else ()
456             end
457           else ()
458       else ()
459     in
460
461     let inactivate_hreg hreg =
462       if (Hashtbl.mem hreg_to_vreg hreg) &&
463         (hreg < cx.ctxt_abi.Abi.abi_n_hardregs)
464       then
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);
470       else ()
471     in
472
473     let spill_specific_hreg i hreg =
474       clean_hreg i hreg;
475       inactivate_hreg hreg
476     in
477
478     let rec select_constrained
479         (constraints:Bits.t)
480         (hregs:Il.hreg list)
481         : Il.hreg option =
482       match hregs with
483           [] -> None
484         | h::hs ->
485             if Bits.get constraints h
486             then Some h
487             else select_constrained constraints hs
488     in
489
490     let spill_constrained constrs i =
491       match select_constrained constrs (!active_hregs) with
492           None ->
493             raise (Ra_error ("unable to spill according to constraint"));
494         | Some h ->
495             begin
496               spill_specific_hreg i h;
497               h
498             end
499     in
500
501     let all_hregs = Bits.create abi.Abi.abi_n_hardregs true in
502
503     let spill_all_regs i =
504       while (!active_hregs) != []
505       do
506         let _ = spill_constrained all_hregs i in
507           ()
508       done
509     in
510
511     let reload vreg hreg =
512       if Hashtbl.mem vreg_to_spill vreg
513       then
514         prepend (Il.mk_quad
515                    (Il.umov
516                       (hr hreg)
517                       (Il.Cell (vreg_spill_cell vreg))))
518       else ()
519     in
520
521     let use_vreg def i vreg =
522       if Hashtbl.mem vreg_to_hreg vreg
523       then
524         begin
525           let h = Hashtbl.find vreg_to_hreg vreg in
526           iflog cx (fun _ -> log cx "found cached assignment %s for <v%d>"
527                       (hr_str h) vreg);
528             h
529         end
530       else
531         let hreg =
532           let constrs = vreg_constraints.(vreg) in
533           match select_constrained constrs (!inactive_hregs) with
534               None ->
535                 let h = spill_constrained constrs i in
536                   iflog cx
537                     (fun _ -> log cx "selected %s to spill and use for <v%d>"
538                        (hr_str h) vreg);
539                   h
540             | Some h ->
541                 iflog cx (fun _ -> log cx "selected inactive %s for <v%d>"
542                             (hr_str h) vreg);
543                 h
544         in
545           inactive_hregs :=
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;
550           if def
551           then ()
552           else
553             reload vreg hreg;
554           hreg
555     in
556     let qp_reg def i _ r =
557       match r with
558           Il.Hreg h -> (spill_specific_hreg i h; r)
559         | Il.Vreg v -> (Il.Hreg (use_vreg def i v))
560     in
561     let qp_cell def i qp c =
562       match c with
563           Il.Reg (r, b) -> Il.Reg (qp_reg def i qp r, b)
564         | Il.Mem  (a, b) ->
565             let qp = { qp with Il.qp_reg = qp_reg false i } in
566               Il.Mem (qp.qp_mem qp a, b)
567     in
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 }
572     in
573       cx.ctxt_next_spill <- n_pre_spills;
574       convert_labels cx;
575       for i = 0 to cx.ctxt_abi.Abi.abi_n_hardregs - 1
576       do
577         inactive_hregs := i :: (!inactive_hregs)
578       done;
579       for i = 0 to (Array.length cx.ctxt_quads) - 1
580       do
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
585           begin
586             if List.exists (fun def -> List.mem def clobbers) defined
587             then raise (Ra_error ("clobber and defined sets overlap"));
588             iflog cx
589               begin
590                 fun _ ->
591                   let hr (v:int) : string =
592                     if Hashtbl.mem vreg_to_hreg v
593                     then hr_str (Hashtbl.find vreg_to_hreg v)
594                     else "??"
595                   in
596                   let vr_str (v:int) : string =
597                     Printf.sprintf "v%d=%s" v (hr v)
598                   in
599                   let lstr lab ls fn =
600                     if List.length ls = 0
601                     then ()
602                     else log cx "\t%s: [%s]" lab (list_to_str ls fn)
603                   in
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);
612               end;
613             List.iter (clean_hreg i) clobbers;
614             if is_beginning_of_basic_block quad
615             then
616               begin
617                 spill_all_regs i;
618                 fixup := quad.quad_fixup;
619                 prepend (Il.process_quad (qp i) quad)
620               end
621             else
622               begin
623                 fixup := quad.quad_fixup;
624                 let newq = (Il.process_quad (qp i) quad) in
625                   begin
626                     if is_end_of_basic_block quad
627                     then spill_all_regs i
628                     else ()
629                   end;
630                   prepend newq
631               end
632           end;
633           List.iter inactivate_hreg clobbers;
634           List.iter (fun i -> Hashtbl.replace dirty_vregs i ()) defined;
635       done;
636       cx.ctxt_quads <- Array.of_list (List.rev (!newq));
637       kill_redundant_moves cx;
638
639       iflog cx
640         begin
641           fun _ ->
642             log cx "spills: %d pre-spilled, %d total"
643               n_pre_spills cx.ctxt_next_spill;
644             log cx "register-allocated quads:";
645             dump_quads cx;
646         end;
647       (cx.ctxt_quads, cx.ctxt_next_spill)
648
649   with
650       Ra_error s ->
651         Session.fail sess "RA Error: %s" s;
652         (quads, 0)
653
654 ;;
655
656
657 (*
658  * Local Variables:
659  * fill-column: 78;
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'";
663  * End:
664  *)