1 #![allow(non_snake_case)]
2 #![allow(non_camel_case_types)]
3
4 //! Core implementation of the backtracking allocator.
5
6 use log::{debug, info, log_enabled, Level};
7 use smallvec::SmallVec;
8 use std::default;
9 use std::fmt;
10
11 use crate::analysis_data_flow::{add_raw_reg_vecs_for_insn, does_inst_use_def_or_mod_reg};
12 use crate::analysis_main::{run_analysis, AnalysisInfo};
13 use crate::avl_tree::{AVLTree, AVL_NULL};
14 use crate::bt_coalescing_analysis::{do_coalescing_analysis, Hint};
15 use crate::bt_commitment_map::{CommitmentMap, RangeFragAndRangeId};
16 use crate::bt_spillslot_allocator::SpillSlotAllocator;
17 use crate::bt_vlr_priority_queue::VirtualRangePrioQ;
18 use crate::data_structures::{
19 BlockIx, InstIx, InstPoint, Map, Point, RangeFrag, RangeFragIx, RangeId, RealRange,
20 RealRangeIx, RealReg, RealRegUniverse, Reg, RegClass, RegVecBounds, RegVecs, RegVecsAndBounds,
21 Set, SortedRangeFrags, SpillCost, SpillSlot, TypedIxVec, VirtualRange, VirtualRangeIx,
22 VirtualReg, Writable,
23 };
24 use crate::inst_stream::{
25 edit_inst_stream, ExtPoint, InstExtPoint, InstToInsert, InstToInsertAndExtPoint,
26 };
27 use crate::sparse_set::SparseSetU;
28 use crate::union_find::UnionFindEquivClasses;
29 use crate::{AlgorithmWithDefaults, Function, RegAllocError, RegAllocResult, StackmapRequestInfo};
30
31 #[derive(Clone)]
32 pub struct BacktrackingOptions {
33 /// Should the register allocator generate block annotations?
34 pub request_block_annotations: bool,
35 }
36
37 impl default::Default for BacktrackingOptions {
default() -> Self38 fn default() -> Self {
39 Self {
40 request_block_annotations: false,
41 }
42 }
43 }
44
45 impl fmt::Debug for BacktrackingOptions {
fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result46 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
47 write!(
48 fmt,
49 "backtracking (block annotations: {})",
50 self.request_block_annotations
51 )
52 }
53 }
54
55 //=============================================================================
56 // The per-real-register state
57 //
58 // Relevant methods are expected to be parameterised by the same VirtualRange
59 // env as used in calls to `VirtualRangePrioQ`.
60
61 struct PerRealReg {
62 // The current committed fragments for this RealReg.
63 committed: CommitmentMap,
64
65 // The set of VirtualRanges which have been assigned to this RealReg. The
66 // union of their frags will be equal to `committed` only if this RealReg
67 // has no RealRanges. If this RealReg does have RealRanges the
68 // aforementioned union will be exactly the subset of `committed` not used
69 // by the RealRanges.
70 vlrixs_assigned: Set<VirtualRangeIx>,
71 }
72 impl PerRealReg {
new() -> Self73 fn new() -> Self {
74 Self {
75 committed: CommitmentMap::new(),
76 vlrixs_assigned: Set::<VirtualRangeIx>::empty(),
77 }
78 }
79
80 #[inline(never)]
add_RealRange( &mut self, to_add_rlrix: RealRangeIx, rlr_env: &TypedIxVec<RealRangeIx, RealRange>, frag_env: &TypedIxVec<RangeFragIx, RangeFrag>, )81 fn add_RealRange(
82 &mut self,
83 to_add_rlrix: RealRangeIx,
84 rlr_env: &TypedIxVec<RealRangeIx, RealRange>,
85 frag_env: &TypedIxVec<RangeFragIx, RangeFrag>,
86 ) {
87 // Commit this register to `to_add`, irrevocably. Don't add it to `vlrixs_assigned`
88 // since we will never want to later evict the assignment. (Also, from a types point of
89 // view that would be impossible.)
90 let to_add_rlr = &rlr_env[to_add_rlrix];
91 self.committed.add_indirect(
92 &to_add_rlr.sorted_frags,
93 RangeId::new_real(to_add_rlrix),
94 frag_env,
95 );
96 }
97
98 #[inline(never)]
add_VirtualRange( &mut self, to_add_vlrix: VirtualRangeIx, vlr_env: &TypedIxVec<VirtualRangeIx, VirtualRange>, )99 fn add_VirtualRange(
100 &mut self,
101 to_add_vlrix: VirtualRangeIx,
102 vlr_env: &TypedIxVec<VirtualRangeIx, VirtualRange>,
103 ) {
104 let to_add_vlr = &vlr_env[to_add_vlrix];
105 self.committed
106 .add(&to_add_vlr.sorted_frags, RangeId::new_virtual(to_add_vlrix));
107 assert!(!self.vlrixs_assigned.contains(to_add_vlrix));
108 self.vlrixs_assigned.insert(to_add_vlrix);
109 }
110
111 #[inline(never)]
del_VirtualRange( &mut self, to_del_vlrix: VirtualRangeIx, vlr_env: &TypedIxVec<VirtualRangeIx, VirtualRange>, )112 fn del_VirtualRange(
113 &mut self,
114 to_del_vlrix: VirtualRangeIx,
115 vlr_env: &TypedIxVec<VirtualRangeIx, VirtualRange>,
116 ) {
117 // Remove it from `vlrixs_assigned`
118 // FIXME 2020June18: we could do this more efficiently by inspecting
119 // the return value from `delete`.
120 if self.vlrixs_assigned.contains(to_del_vlrix) {
121 self.vlrixs_assigned.delete(to_del_vlrix);
122 } else {
123 panic!("PerRealReg: del_VirtualRange on VR not in vlrixs_assigned");
124 }
125 // Remove it from `committed`
126 let to_del_vlr = &vlr_env[to_del_vlrix];
127 self.committed.del(&to_del_vlr.sorted_frags);
128 }
129 }
130
131 // HELPER FUNCTION
132 // For a given `RangeFrag`, traverse the commitment tree rooted at `root`,
133 // adding to `running_set` the set of VLRIxs that the frag intersects, and
134 // adding their spill costs to `running_cost`. Return false if, for one of
135 // the 4 reasons documented below, the traversal has been abandoned, and true
136 // if the search completed successfully.
search_commitment_tree<IsAllowedToEvict>( running_set: &mut SparseSetU<[VirtualRangeIx; 4]>, running_cost: &mut SpillCost, tree: &AVLTree<RangeFragAndRangeId>, pair_frag: &RangeFrag, spill_cost_budget: &SpillCost, allowed_to_evict: &IsAllowedToEvict, vlr_env: &TypedIxVec<VirtualRangeIx, VirtualRange>, ) -> bool where IsAllowedToEvict: Fn(VirtualRangeIx) -> bool,137 fn search_commitment_tree<IsAllowedToEvict>(
138 // The running state, threaded through the tree traversal. These
139 // accumulate ranges and costs as we traverse the tree. These are mutable
140 // because our caller (`find_evict_set`) will want to try and allocate
141 // multiple `RangeFrag`s in this tree, not just a single one, and so it
142 // needs a way to accumulate the total evict-cost and evict-set for all
143 // the `RangeFrag`s it iterates over.
144 running_set: &mut SparseSetU<[VirtualRangeIx; 4]>,
145 running_cost: &mut SpillCost,
146 // The tree to search.
147 tree: &AVLTree<RangeFragAndRangeId>,
148 // The RangeFrag we want to accommodate.
149 pair_frag: &RangeFrag,
150 spill_cost_budget: &SpillCost,
151 allowed_to_evict: &IsAllowedToEvict,
152 vlr_env: &TypedIxVec<VirtualRangeIx, VirtualRange>,
153 ) -> bool
154 where
155 IsAllowedToEvict: Fn(VirtualRangeIx) -> bool,
156 {
157 let mut stack = SmallVec::<[u32; 32]>::new();
158 assert!(tree.root != AVL_NULL);
159 stack.push(tree.root);
160
161 while let Some(curr) = stack.pop() {
162 let curr_node = &tree.pool[curr as usize];
163 let curr_node_item = &curr_node.item;
164 let curr_frag = &curr_node_item.frag;
165
166 // Figure out whether `pair_frag` overlaps the root of the current
167 // subtree.
168 let overlaps_curr = pair_frag.last >= curr_frag.first && pair_frag.first <= curr_frag.last;
169
170 // Let's first consider the current node. If we need it but it's not
171 // evictable, we might as well stop now.
172 if overlaps_curr {
173 // This frag is committed to a real range, not a virtual one, and hence is not
174 // evictable.
175 if curr_node_item.id.is_real() {
176 return false;
177 }
178 // Maybe this one is a spill range, in which case, it can't be
179 // evicted.
180 let vlrix_to_evict = curr_node_item.id.to_virtual();
181 let vlr_to_evict = &vlr_env[vlrix_to_evict];
182 if vlr_to_evict.spill_cost.is_infinite() {
183 return false;
184 }
185 // Check that this range alone doesn't exceed our total spill
186 // cost. NB: given the check XXX below, this isn't actually
187 // necessary; however it means that we avoid doing two
188 // SparseSet::contains operations before exiting. This saves
189 // around 0.3% instruction count for large inputs.
190 if !vlr_to_evict.spill_cost.is_less_than(spill_cost_budget) {
191 return false;
192 }
193 // Maybe our caller doesn't want us to evict this one.
194 if !allowed_to_evict(vlrix_to_evict) {
195 return false;
196 }
197 // Ok! We can evict the current node. Update the running state
198 // accordingly. Note that we may be presented with the same VLRIx
199 // to evict multiple times, so we must be careful to add the cost
200 // of it only once.
201 if !running_set.contains(vlrix_to_evict) {
202 let mut tmp_cost = *running_cost;
203 tmp_cost.add(&vlr_to_evict.spill_cost);
204 // See above XXX
205 if !tmp_cost.is_less_than(spill_cost_budget) {
206 return false;
207 }
208 *running_cost = tmp_cost;
209 running_set.insert(vlrix_to_evict);
210 }
211 }
212
213 // Now figure out if we need to visit the subtrees, and if so push the
214 // relevant nodes. Whether we visit the left or right subtree first
215 // is unimportant, at least from a correctness perspective.
216 let must_check_left = pair_frag.first < curr_frag.first;
217 if must_check_left {
218 let left_of_curr = tree.pool[curr as usize].left;
219 if left_of_curr != AVL_NULL {
220 stack.push(left_of_curr);
221 }
222 }
223
224 let must_check_right = pair_frag.last > curr_frag.last;
225 if must_check_right {
226 let right_of_curr = tree.pool[curr as usize].right;
227 if right_of_curr != AVL_NULL {
228 stack.push(right_of_curr);
229 }
230 }
231 }
232
233 // If we get here, it means that `pair_frag` can be accommodated if we
234 // evict all the frags it overlaps in `tree`.
235 //
236 // Stay sane ..
237 assert!(running_cost.is_finite());
238 assert!(running_cost.is_less_than(spill_cost_budget));
239 true
240 }
241
242 impl PerRealReg {
243 // Find the set of VirtualRangeIxs that would need to be evicted in order to
244 // allocate `would_like_to_add` to this register. Virtual ranges mentioned
245 // in `do_not_evict` must not be considered as candidates for eviction.
246 // Also returns the total associated spill cost. That spill cost cannot be
247 // infinite.
248 //
249 // This can fail (return None) for four different reasons:
250 //
251 // - `would_like_to_add` interferes with a real-register-live-range
252 // commitment, so the register would be unavailable even if we evicted
253 // *all* virtual ranges assigned to it.
254 //
255 // - `would_like_to_add` interferes with a virtual range which is a spill
256 // range (has infinite cost). We cannot evict those without risking
257 // non-termination of the overall allocation algorithm.
258 //
259 // - `would_like_to_add` interferes with a virtual range listed in
260 // `do_not_evict`. Our caller uses this mechanism when trying to do
261 // coalesing, to avoid the nonsensicality of evicting some part of a
262 // virtual live range group in order to allocate a member of the same
263 // group.
264 //
265 // - The total spill cost of the candidate set exceeds the spill cost of
266 // `would_like_to_add`. This means that spilling them would be a net loss
267 // per our cost model. Note that `would_like_to_add` may have an infinite
268 // spill cost, in which case it will "win" over all other
269 // non-infinite-cost eviction candidates. This is by design (so as to
270 // guarantee that we can always allocate spill/reload bridges).
271 #[inline(never)]
find_evict_set<IsAllowedToEvict>( &self, would_like_to_add: VirtualRangeIx, allowed_to_evict: &IsAllowedToEvict, vlr_env: &TypedIxVec<VirtualRangeIx, VirtualRange>, ) -> Option<(SparseSetU<[VirtualRangeIx; 4]>, SpillCost)> where IsAllowedToEvict: Fn(VirtualRangeIx) -> bool,272 fn find_evict_set<IsAllowedToEvict>(
273 &self,
274 would_like_to_add: VirtualRangeIx,
275 allowed_to_evict: &IsAllowedToEvict,
276 vlr_env: &TypedIxVec<VirtualRangeIx, VirtualRange>,
277 ) -> Option<(SparseSetU<[VirtualRangeIx; 4]>, SpillCost)>
278 where
279 IsAllowedToEvict: Fn(VirtualRangeIx) -> bool,
280 {
281 // Firstly, if the commitment tree is for this reg is empty, we can
282 // declare success immediately.
283 if self.committed.tree.root == AVL_NULL {
284 let evict_set = SparseSetU::<[VirtualRangeIx; 4]>::empty();
285 let evict_cost = SpillCost::zero();
286 return Some((evict_set, evict_cost));
287 }
288
289 // The tree isn't empty, so we will have to do this the hard way: iterate
290 // over all fragments in `would_like_to_add` and check them against the
291 // tree.
292
293 // Useful constants for the main loop
294 let would_like_to_add_vlr = &vlr_env[would_like_to_add];
295 let evict_cost_budget = would_like_to_add_vlr.spill_cost;
296 // Note that `evict_cost_budget` can be infinite because
297 // `would_like_to_add` might be a spill/reload range.
298
299 // The overall evict set and cost so far. These are updated as we iterate
300 // over the fragments that make up `would_like_to_add`.
301 let mut running_set = SparseSetU::<[VirtualRangeIx; 4]>::empty();
302 let mut running_cost = SpillCost::zero();
303
304 // "wlta" = would like to add
305 for wlta_frag in &would_like_to_add_vlr.sorted_frags.frags {
306 let wlta_frag_ok = search_commitment_tree(
307 &mut running_set,
308 &mut running_cost,
309 &self.committed.tree,
310 &wlta_frag,
311 &evict_cost_budget,
312 allowed_to_evict,
313 vlr_env,
314 );
315 if !wlta_frag_ok {
316 // This fragment won't fit, for one of the four reasons listed
317 // above. So give up now.
318 return None;
319 }
320 // And move on to the next fragment.
321 }
322
323 // If we got here, it means that `would_like_to_add` can be accommodated \o/
324 assert!(running_cost.is_finite());
325 assert!(running_cost.is_less_than(&evict_cost_budget));
326 Some((running_set, running_cost))
327 }
328
329 #[allow(dead_code)]
330 #[inline(never)]
show1_with_envs(&self, _frag_env: &TypedIxVec<RangeFragIx, RangeFrag>) -> String331 fn show1_with_envs(&self, _frag_env: &TypedIxVec<RangeFragIx, RangeFrag>) -> String {
332 //"in_use: ".to_string() + &self.committed.show_with_frag_env(&frag_env)
333 "(show1_with_envs:FIXME)".to_string()
334 }
335 #[allow(dead_code)]
336 #[inline(never)]
show2_with_envs(&self, _frag_env: &TypedIxVec<RangeFragIx, RangeFrag>) -> String337 fn show2_with_envs(&self, _frag_env: &TypedIxVec<RangeFragIx, RangeFrag>) -> String {
338 //"assigned: ".to_string() + &format!("{:?}", &self.vlrixs_assigned)
339 "(show2_with_envs:FIXME)".to_string()
340 }
341 }
342
343 //=============================================================================
344 // Printing the allocator's top level state
345
346 #[inline(never)]
print_RA_state( who: &str, _universe: &RealRegUniverse, prioQ: &VirtualRangePrioQ, _perRealReg: &Vec<PerRealReg>, edit_list_move: &Vec<EditListItem>, edit_list_other: &Vec<EditListItem>, vlr_env: &TypedIxVec<VirtualRangeIx, VirtualRange>, _frag_env: &TypedIxVec<RangeFragIx, RangeFrag>, )347 fn print_RA_state(
348 who: &str,
349 _universe: &RealRegUniverse,
350 // State components
351 prioQ: &VirtualRangePrioQ,
352 _perRealReg: &Vec<PerRealReg>,
353 edit_list_move: &Vec<EditListItem>,
354 edit_list_other: &Vec<EditListItem>,
355 // The context (environment)
356 vlr_env: &TypedIxVec<VirtualRangeIx, VirtualRange>,
357 _frag_env: &TypedIxVec<RangeFragIx, RangeFrag>,
358 ) {
359 debug!("<<<<====---- RA state at '{}' ----====", who);
360 //for ix in 0..perRealReg.len() {
361 // if !&perRealReg[ix].committed.pairs.is_empty() {
362 // debug!(
363 // "{:<5} {}",
364 // universe.regs[ix].1,
365 // &perRealReg[ix].show1_with_envs(&frag_env)
366 // );
367 // debug!(" {}", &perRealReg[ix].show2_with_envs(&frag_env));
368 // debug!("");
369 // }
370 //}
371 if !prioQ.is_empty() {
372 for s in prioQ.show_with_envs(vlr_env) {
373 debug!("{}", s);
374 }
375 }
376 for eli in edit_list_move {
377 debug!("ELI MOVE: {:?}", eli);
378 }
379 for eli in edit_list_other {
380 debug!("ELI other: {:?}", eli);
381 }
382 debug!(">>>>");
383 }
384
385 //=============================================================================
386 // Reftype/stackmap support
387
388 // This creates the artefacts for a safepoint/stackmap at some insn `iix`: the set of reftyped
389 // spill slots, the spills to be placed at `iix.r` (yes, you read that right) and the reloads to
390 // be placed at `iix.s`.
391 //
392 // This consults:
393 //
394 // * the commitment maps, to figure out which real registers are live and reftyped at `iix.u`.
395 //
396 // * the spillslot allocator, to figure out which spill slots are live and reftyped at `iix.u`.
397 //
398 // This may fail, meaning the request is in some way nonsensical; failure is propagated upwards.
399
get_stackmap_artefacts_at( spill_slot_allocator: &mut SpillSlotAllocator, univ: &RealRegUniverse, reftype_class: RegClass, reg_vecs_and_bounds: &RegVecsAndBounds, per_real_reg: &Vec<PerRealReg>, rlr_env: &TypedIxVec<RealRangeIx, RealRange>, vlr_env: &TypedIxVec<VirtualRangeIx, VirtualRange>, iix: InstIx, ) -> Result<(Vec<InstToInsert>, Vec<InstToInsert>, Vec<SpillSlot>), RegAllocError>400 fn get_stackmap_artefacts_at(
401 spill_slot_allocator: &mut SpillSlotAllocator,
402 univ: &RealRegUniverse,
403 reftype_class: RegClass,
404 reg_vecs_and_bounds: &RegVecsAndBounds,
405 per_real_reg: &Vec<PerRealReg>,
406 rlr_env: &TypedIxVec<RealRangeIx, RealRange>,
407 vlr_env: &TypedIxVec<VirtualRangeIx, VirtualRange>,
408 iix: InstIx,
409 ) -> Result<(Vec<InstToInsert>, Vec<InstToInsert>, Vec<SpillSlot>), RegAllocError> {
410 // From a code generation perspective, what we need to compute is:
411 //
412 // * Sbefore: real regs that are live at `iix.u`, that are reftypes
413 //
414 // * Safter: Sbefore - real regs written by `iix`
415 //
416 // Then:
417 //
418 // * for r in Sbefore . add "spill r" at `iix.r` *after* all the reloads that are already
419 // there
420 //
421 // * for r in Safter . add "reload r" at `iix.s` *before* all the spills that are already
422 // there
423 //
424 // Once those spills have been "recorded" by the `spill_slot_allocator`, we can then ask it
425 // to tell us all the reftyped spill slots at `iix.u`, and that's our stackmap! This routine
426 // only computes the stackmap and the vectors of spills and reloads. It doesn't deal with
427 // interleaving them into the final code sequence.
428 //
429 // Note that this scheme isn't as runtime-inefficient as it sounds, at least in the
430 // SpiderMonkey use case and where `iix` is a call insn. That's because SM's calling
431 // convention has no callee saved registers. Hence "real regs written by `iix`" will be
432 // "all real regs" and so Safter will be empty. And Sbefore is in any case pretty small.
433 //
434 // (/me thinks ..) hmm, if Safter is empty, then what is the point of dumping Sbefore on the
435 // stack before the GC? For r in Sbefore, either r is the only reference to some object, in
436 // which case there's no point in presenting that ref to the GC since r is dead after call,
437 // or r isn't the only ref to the object, in which case some other ref to it must exist
438 // elsewhere in the stack, and that will keep the object alive. Maybe this needs a rethink.
439 // Maybe the spills before the call should be only for the set Safter?
440
441 let pt = InstPoint::new_use(iix);
442
443 // Compute Sbefore.
444
445 // FIXME change this to SparseSet
446 let mut s_before = Set::<RealReg>::empty();
447
448 let rci = univ.allocable_by_class[reftype_class.rc_to_usize()];
449 if rci.is_none() {
450 return Err(RegAllocError::Other(
451 "stackmap request: no regs in specified reftype class".to_string(),
452 ));
453 }
454 let rci = rci.unwrap();
455
456 debug!("computing stackmap info at {:?}", pt);
457
458 for rreg_no in rci.first..rci.last + 1 {
459 // Get the RangeId, if any, assigned for `rreg_no` at `iix.u`. From that we can figure
460 // out if it is reftyped.
461 let mb_range_id = per_real_reg[rreg_no].committed.lookup_inst_point(pt);
462 if let Some(range_id) = mb_range_id {
463 // `rreg_no` is live at `iix.u`.
464 let is_ref = if range_id.is_real() {
465 debug!(
466 " real reg {:?} is real-range {:?}",
467 rreg_no,
468 rlr_env[range_id.to_real()]
469 );
470 rlr_env[range_id.to_real()].is_ref
471 } else {
472 debug!(
473 " real reg {:?} is virtual-range {:?}",
474 rreg_no,
475 vlr_env[range_id.to_virtual()]
476 );
477 vlr_env[range_id.to_virtual()].is_ref
478 };
479 if is_ref {
480 // Finally .. we know that `rreg_no` is reftyped and live at `iix.u`.
481 let rreg = univ.regs[rreg_no].0;
482 s_before.insert(rreg);
483 }
484 }
485 }
486
487 debug!("Sbefore = {:?}", s_before);
488
489 // Compute Safter.
490
491 let mut s_after = s_before.clone();
492 let bounds = ®_vecs_and_bounds.bounds[iix];
493 if bounds.mods_len != 0 {
494 // Only the GC is allowed to modify reftyped regs at this insn!
495 return Err(RegAllocError::Other(
496 "stackmap request: safepoint insn modifies a reftyped reg".to_string(),
497 ));
498 }
499
500 for i in bounds.defs_start..bounds.defs_start + bounds.defs_len as u32 {
501 let r_defd = reg_vecs_and_bounds.vecs.defs[i as usize];
502 if r_defd.is_real() && r_defd.get_class() == reftype_class {
503 s_after.delete(r_defd.to_real_reg());
504 }
505 }
506
507 debug!("Safter = {:?}", s_before);
508
509 // Create the spill insns, as defined by Sbefore. This has the side effect of recording the
510 // spill in `spill_slot_allocator`, so we can later ask it to tell us all the reftyped spill
511 // slots.
512
513 let frag = RangeFrag::new(InstPoint::new_reload(iix), InstPoint::new_spill(iix));
514
515 let mut spill_insns = Vec::<InstToInsert>::new();
516 let mut where_reg_got_spilled_to = Map::<RealReg, SpillSlot>::default();
517
518 for from_reg in s_before.iter() {
519 let to_slot = spill_slot_allocator.alloc_reftyped_spillslot_for_frag(frag.clone());
520 let spill = InstToInsert::Spill {
521 to_slot,
522 from_reg: *from_reg,
523 for_vreg: None, // spill isn't associated with any virtual reg
524 };
525 spill_insns.push(spill);
526 // We also need to remember where we stashed it, so we can reload it, if it is in Safter.
527 if s_after.contains(*from_reg) {
528 where_reg_got_spilled_to.insert(*from_reg, to_slot);
529 }
530 }
531
532 // Create the reload insns, as defined by Safter. Except, we might as well use the map we
533 // just made, since its domain is the same as Safter.
534
535 let mut reload_insns = Vec::<InstToInsert>::new();
536
537 for (to_reg, from_slot) in where_reg_got_spilled_to.iter() {
538 let reload = InstToInsert::Reload {
539 to_reg: Writable::from_reg(*to_reg),
540 from_slot: *from_slot,
541 for_vreg: None, // reload isn't associated with any virtual reg
542 };
543 reload_insns.push(reload);
544 }
545
546 // And finally .. round up all the reftyped spill slots. That includes both "normal" spill
547 // slots that happen to hold reftyped values, as well as the "extras" we created here, to
548 // hold values of reftyped regs that are live over this instruction.
549
550 let reftyped_spillslots = spill_slot_allocator.get_reftyped_spillslots_at_inst_point(pt);
551
552 debug!("reftyped_spillslots = {:?}", reftyped_spillslots);
553
554 // And we're done!
555
556 Ok((spill_insns, reload_insns, reftyped_spillslots))
557 }
558
559 //=============================================================================
560 // Allocator top level
561
562 /* (const) For each virtual live range
563 - its sorted RangeFrags
564 - its total size
565 - its spill cost
566 - (eventually) its assigned real register
567 New VirtualRanges are created as we go, but existing ones are unchanged,
568 apart from being tagged with its assigned real register.
569
570 (mut) For each real register
571 - the sorted RangeFrags assigned to it (todo: rm the M)
572 - the virtual LR indices assigned to it. This is so we can eject
573 a VirtualRange from the commitment, as needed
574
575 (mut) the set of VirtualRanges not yet allocated, prioritised by total size
576
577 (mut) the edit list that is produced
578 */
579 /*
580 fn show_commit_tab(commit_tab: &Vec::<SortedRangeFragIxs>,
581 who: &str,
582 context: &TypedIxVec::<RangeFragIx, RangeFrag>) -> String {
583 let mut res = "Commit Table at '".to_string()
584 + &who.to_string() + &"'\n".to_string();
585 let mut rregNo = 0;
586 for smf in commit_tab.iter() {
587 res += &" ".to_string();
588 res += &mkRealReg(rregNo).show();
589 res += &" ".to_string();
590 res += &smf.show_with_fenv(&context);
591 res += &"\n".to_string();
592 rregNo += 1;
593 }
594 res
595 }
596 */
597
598 // VirtualRanges created by spilling all pertain to a single InstIx. But
599 // within that InstIx, there are three kinds of "bridges":
600 #[derive(Clone, Copy, PartialEq)]
601 pub(crate) enum BridgeKind {
602 RtoU, // A bridge for a USE. This connects the reload to the use.
603 RtoS, // a bridge for a MOD. This connects the reload, the use/def
604 // and the spill, since the value must first be reloade, then
605 // operated on, and finally re-spilled.
606 DtoS, // A bridge for a DEF. This connects the def to the spill.
607 }
608
609 impl fmt::Debug for BridgeKind {
fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result610 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
611 match self {
612 BridgeKind::RtoU => write!(fmt, "R->U"),
613 BridgeKind::RtoS => write!(fmt, "R->S"),
614 BridgeKind::DtoS => write!(fmt, "D->S"),
615 }
616 }
617 }
618
619 #[derive(Clone, Copy)]
620 struct EditListItem {
621 // This holds enough information to create a spill or reload instruction,
622 // or both, and also specifies where in the instruction stream it/they
623 // should be added. Note that if the edit list as a whole specifies
624 // multiple items for the same location, then it is assumed that the order
625 // in which they execute isn't important.
626 //
627 // Some of the relevant info can be found via the VirtualRangeIx link:
628 // (1) the real reg involved
629 // (2) the place where the insn should go, since the VirtualRange should
630 // only have one RangeFrag, and we can deduce the correct location
631 // from that.
632 // Despite (2) we also carry here the InstIx of the affected instruction
633 // (there should be only one) since computing it via (2) is expensive.
634 // This however gives a redundancy in representation against (2). Beware!
635 slot: SpillSlot,
636 vlrix: VirtualRangeIx,
637 kind: BridgeKind,
638 iix: InstIx,
639 }
640
641 impl fmt::Debug for EditListItem {
fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result642 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
643 write!(
644 fmt,
645 "(ELI: at {:?} for {:?} add {:?}, slot={:?})",
646 self.iix, self.vlrix, self.kind, self.slot
647 )
648 }
649 }
650
651 // Allocator top level. This function returns a result struct that contains
652 // the final sequence of instructions, possibly with fills/spills/moves
653 // spliced in and redundant moves elided, and with all virtual registers
654 // replaced with real registers. Allocation can fail if there are insufficient
655 // registers to even generate spill/reload code, or if the function appears to
656 // have any undefined VirtualReg/RealReg uses.
657
658 #[inline(never)]
alloc_main<F: Function>( func: &mut F, reg_universe: &RealRegUniverse, stackmap_request: Option<&StackmapRequestInfo>, use_checker: bool, opts: &BacktrackingOptions, ) -> Result<RegAllocResult<F>, RegAllocError>659 pub fn alloc_main<F: Function>(
660 func: &mut F,
661 reg_universe: &RealRegUniverse,
662 stackmap_request: Option<&StackmapRequestInfo>,
663 use_checker: bool,
664 opts: &BacktrackingOptions,
665 ) -> Result<RegAllocResult<F>, RegAllocError> {
666 // -------- Initial arrangements for stackmaps --------
667 let empty_vec_vregs = vec![];
668 let empty_vec_iixs = vec![];
669 let (client_wants_stackmaps, reftype_class, reftyped_vregs, safepoint_insns) =
670 match stackmap_request {
671 Some(&StackmapRequestInfo {
672 reftype_class,
673 ref reftyped_vregs,
674 ref safepoint_insns,
675 }) => (true, reftype_class, reftyped_vregs, safepoint_insns),
676 None => (false, RegClass::INVALID, &empty_vec_vregs, &empty_vec_iixs),
677 };
678
679 // -------- Perform initial liveness analysis --------
680 // Note that the analysis phase can fail; hence we propagate any error.
681 let AnalysisInfo {
682 reg_vecs_and_bounds,
683 real_ranges: rlr_env,
684 virtual_ranges: mut vlr_env,
685 range_frags: frag_env,
686 range_metrics: frag_metrics_env,
687 estimated_frequencies: est_freqs,
688 inst_to_block_map,
689 reg_to_ranges_maps: mb_reg_to_ranges_maps,
690 move_info: mb_move_info,
691 } = run_analysis(
692 func,
693 reg_universe,
694 AlgorithmWithDefaults::Backtracking,
695 client_wants_stackmaps,
696 reftype_class,
697 reftyped_vregs,
698 )
699 .map_err(|err| RegAllocError::Analysis(err))?;
700
701 assert!(reg_vecs_and_bounds.is_sanitized());
702 assert!(frag_env.len() == frag_metrics_env.len());
703 assert!(mb_reg_to_ranges_maps.is_some()); // ensured by `run_analysis`
704 assert!(mb_move_info.is_some()); // ensured by `run_analysis`
705 let reg_to_ranges_maps = mb_reg_to_ranges_maps.unwrap();
706 let move_info = mb_move_info.unwrap();
707
708 // Also perform analysis that finds all coalescing opportunities.
709 let coalescing_info = do_coalescing_analysis(
710 func,
711 ®_universe,
712 &rlr_env,
713 &mut vlr_env,
714 &frag_env,
715 ®_to_ranges_maps,
716 &move_info,
717 );
718 let mut hints: TypedIxVec<VirtualRangeIx, SmallVec<[Hint; 8]>> = coalescing_info.0;
719 let vlrEquivClasses: UnionFindEquivClasses<VirtualRangeIx> = coalescing_info.1;
720 let is_vv_boundary_move: TypedIxVec<InstIx, bool> = coalescing_info.2;
721 assert!(hints.len() == vlr_env.len());
722
723 // -------- Alloc main --------
724
725 // Create initial state
726 info!("alloc_main: begin");
727 info!(
728 "alloc_main: in: {} insns in {} blocks",
729 func.insns().len(),
730 func.blocks().len()
731 );
732 let num_vlrs_initial = vlr_env.len();
733 info!(
734 "alloc_main: in: {} VLRs, {} RLRs",
735 num_vlrs_initial,
736 rlr_env.len()
737 );
738
739 // This is fully populated by the ::new call.
740 let mut prioQ = VirtualRangePrioQ::new(&vlr_env);
741
742 // Whereas this is empty. We have to populate it "by hand", by
743 // effectively cloning the allocatable part (prefix) of the universe.
744 let mut per_real_reg = Vec::<PerRealReg>::new();
745 for _ in 0..reg_universe.allocable {
746 // Doing this instead of simply .resize avoids needing Clone for
747 // PerRealReg
748 per_real_reg.push(PerRealReg::new());
749 }
750 for (rlrix_no, rlr) in rlr_env.iter().enumerate() {
751 let rlrix = RealRangeIx::new(rlrix_no as u32);
752 let rregIndex = rlr.rreg.get_index();
753 // Ignore RealRanges for RealRegs that are not part of the allocatable
754 // set. As far as the allocator is concerned, such RealRegs simply
755 // don't exist.
756 if rregIndex >= reg_universe.allocable {
757 continue;
758 }
759 per_real_reg[rregIndex].add_RealRange(rlrix, &rlr_env, &frag_env);
760 }
761
762 let mut edit_list_move = Vec::<EditListItem>::new();
763 let mut edit_list_other = Vec::<EditListItem>::new();
764 if log_enabled!(Level::Debug) {
765 debug!("");
766 print_RA_state(
767 "Initial",
768 ®_universe,
769 &prioQ,
770 &per_real_reg,
771 &edit_list_move,
772 &edit_list_other,
773 &vlr_env,
774 &frag_env,
775 );
776 }
777
778 // This is also part of the running state. `vlr_slot_env` tells us the
779 // assigned spill slot for each VirtualRange, if any.
780 // `spill_slot_allocator` decides on the assignments and writes them into
781 // `vlr_slot_env`.
782 let mut vlr_slot_env = TypedIxVec::<VirtualRangeIx, Option<SpillSlot>>::new();
783 vlr_slot_env.resize(num_vlrs_initial, None);
784 let mut spill_slot_allocator = SpillSlotAllocator::new();
785
786 // Main allocation loop. Each time round, pull out the longest
787 // unallocated VirtualRange, and do one of three things:
788 //
789 // * allocate it to a RealReg, possibly by ejecting some existing
790 // allocation, but only one with a lower spill cost than this one, or
791 //
792 // * spill it. This causes the VirtualRange to disappear. It is replaced
793 // by a set of very short VirtualRanges to carry the spill and reload
794 // values. Or,
795 //
796 // * split it. This causes it to disappear but be replaced by two
797 // VirtualRanges which together constitute the original.
798 debug!("");
799 debug!("-- MAIN ALLOCATION LOOP (DI means 'direct', CO means 'coalesced'):");
800
801 info!("alloc_main: main allocation loop: begin");
802
803 // ======== BEGIN Main allocation loop ========
804 let mut num_vlrs_processed = 0; // stats only
805 let mut num_vlrs_spilled = 0; // stats only
806 let mut num_vlrs_evicted = 0; // stats only
807
808 'main_allocation_loop: loop {
809 debug!("-- still TODO {}", prioQ.len());
810 if false {
811 if log_enabled!(Level::Debug) {
812 debug!("");
813 print_RA_state(
814 "Loop Top",
815 ®_universe,
816 &prioQ,
817 &per_real_reg,
818 &edit_list_move,
819 &edit_list_other,
820 &vlr_env,
821 &frag_env,
822 );
823 debug!("");
824 }
825 }
826
827 let mb_curr_vlrix = prioQ.get_longest_VirtualRange();
828 if mb_curr_vlrix.is_none() {
829 break 'main_allocation_loop;
830 }
831
832 num_vlrs_processed += 1;
833 let curr_vlrix = mb_curr_vlrix.unwrap();
834 let curr_vlr = &vlr_env[curr_vlrix];
835
836 debug!("-- considering {:?}: {:?}", curr_vlrix, curr_vlr);
837
838 assert!(curr_vlr.vreg.to_reg().is_virtual());
839 assert!(curr_vlr.rreg.is_none());
840 let curr_vlr_regclass = curr_vlr.vreg.get_class();
841 let curr_vlr_rc = curr_vlr_regclass.rc_to_usize();
842
843 // ====== BEGIN Try to do coalescing ======
844 //
845 // First, look through the hints for `curr_vlr`, collecting up candidate
846 // real regs, in decreasing order of preference, in `hinted_regs`. Note
847 // that we don't have to consider the weights here, because the coalescing
848 // analysis phase has already sorted the hints for the VLR so as to
849 // present the most favoured (weighty) first, so we merely need to retain
850 // that ordering when copying into `hinted_regs`.
851 assert!(hints.len() == vlr_env.len());
852 let mut hinted_regs = SmallVec::<[RealReg; 8]>::new();
853
854 // === BEGIN collect all hints for `curr_vlr` ===
855 // `hints` has one entry per VLR, but only for VLRs which existed
856 // initially (viz, not for any created by spilling/splitting/whatever).
857 // Similarly, `vlrEquivClasses` can only map VLRs that existed initially,
858 // and will panic otherwise. Hence the following check:
859 if curr_vlrix.get() < hints.len() {
860 for hint in &hints[curr_vlrix] {
861 // BEGIN for each hint
862 let mb_cand = match hint {
863 Hint::SameAs(other_vlrix, _weight) => {
864 // It wants the same reg as some other VLR, but we can only honour
865 // that if the other VLR actually *has* a reg at this point. Its
866 // `rreg` field will tell us exactly that.
867 vlr_env[*other_vlrix].rreg
868 }
869 Hint::Exactly(rreg, _weight) => Some(*rreg),
870 };
871 // So now `mb_cand` might have a preferred real reg. If so, add it to
872 // the list of cands. De-dup as we go, since that is way cheaper than
873 // effectively doing the same via repeated lookups in the
874 // CommitmentMaps.
875 if let Some(rreg) = mb_cand {
876 if !hinted_regs.iter().any(|r| *r == rreg) {
877 hinted_regs.push(rreg);
878 }
879 }
880 // END for each hint
881 }
882
883 // At this point, we have in `hinted_regs`, the hint candidates that
884 // arise from copies between `curr_vlr` and its immediate neighbouring
885 // VLRs or RLRs, in order of declining preference. And that is a good
886 // start.
887 //
888 // However, it may be the case that there is some other VLR which
889 // is in the same equivalence class as `curr_vlr`, but is not a
890 // direct neighbour, and which has already been assigned a
891 // register. We really ought to take those into account too, as
892 // the least-preferred candidates. Hence we need to iterate over
893 // the equivalence class and "round up the secondary candidates."
894 //
895 // Note that the equivalence class might contain VirtualRanges
896 // that are mutually overlapping. That is handled correctly,
897 // since we always consult the relevant CommitmentMaps (in the
898 // PerRealRegs) to detect interference. To more fully understand
899 // this, see the big block comment at the top of
900 // bt_coalescing_analysis.rs.
901 let n_primary_cands = hinted_regs.len();
902
903 // Work the equivalence class set for `curr_vlrix` to pick up any
904 // rreg hints. Equivalence class info exists only for "initial" VLRs.
905 if curr_vlrix.get() < num_vlrs_initial {
906 // `curr_vlrix` is an "initial" VLR.
907 for vlrix in vlrEquivClasses.equiv_class_elems_iter(curr_vlrix) {
908 if vlrix != curr_vlrix {
909 if let Some(rreg) = vlr_env[vlrix].rreg {
910 // Add `rreg` as a cand, if we don't already have it.
911 if !hinted_regs.iter().any(|r| *r == rreg) {
912 hinted_regs.push(rreg);
913 }
914 }
915 }
916 }
917
918 // Sort the secondary cands, so as to try and impose more consistency
919 // across the group. I don't know if this is worthwhile, but it seems
920 // sensible.
921 hinted_regs[n_primary_cands..].sort_by(|rreg1, rreg2| {
922 rreg1.get_index().partial_cmp(&rreg2.get_index()).unwrap()
923 });
924 }
925
926 if log_enabled!(Level::Debug) {
927 if !hinted_regs.is_empty() {
928 let mut candStr = "pri {".to_string();
929 for (rreg, n) in hinted_regs.iter().zip(0..) {
930 if n == n_primary_cands {
931 candStr = candStr + &" } sec {".to_string();
932 }
933 candStr =
934 candStr + &" ".to_string() + ®_universe.regs[rreg.get_index()].1;
935 }
936 candStr = candStr + &" }";
937 debug!("-- CO candidates {}", candStr);
938 }
939 }
940 }
941 // === END collect all hints for `curr_vlr` ===
942
943 // === BEGIN try to use the hints for `curr_vlr` ===
944 // Now work through the list of preferences, to see if we can honour any
945 // of them.
946 for rreg in &hinted_regs {
947 let rregNo = rreg.get_index();
948
949 // Find the set of ranges which we'd have to evict in order to honour
950 // this hint. In the best case the set will be empty. In the worst
951 // case, we will get None either because (1) it would require evicting a
952 // spill range, which is disallowed so as to guarantee termination of
953 // the algorithm, or (2) because it would require evicting a real reg
954 // live range, which we can't do.
955 //
956 // We take care not to evict any range which is in the same equivalence
957 // class as `curr_vlr` since those are (by definition) connected to
958 // `curr_vlr` via V-V copies, and so evicting any of them would be
959 // counterproductive from the point of view of removing copies.
960
961 let mb_evict_info: Option<(SparseSetU<[VirtualRangeIx; 4]>, SpillCost)> =
962 per_real_reg[rregNo].find_evict_set(
963 curr_vlrix,
964 &|vlrix_to_evict| {
965 // What this means is: don't evict `vlrix_to_evict` if
966 // it is in the same equivalence class as `curr_vlrix`
967 // (the VLR which we're trying to allocate) AND we
968 // actually know the equivalence classes for both
969 // (hence the `Some`). Spill/reload ("non-original")
970 // VLRS don't have entries in `vlrEquivClasses`.
971 vlrEquivClasses.in_same_equivalence_class(vlrix_to_evict, curr_vlrix)
972 != Some(true)
973 },
974 &vlr_env,
975 );
976 if let Some((vlrixs_to_evict, total_evict_cost)) = mb_evict_info {
977 // Stay sane #1
978 assert!(curr_vlr.rreg.is_none());
979 // Stay sane #2
980 assert!(vlrixs_to_evict.is_empty() == total_evict_cost.is_zero());
981 // Can't evict if any in the set are spill ranges
982 assert!(total_evict_cost.is_finite());
983 // Ensure forward progress
984 assert!(total_evict_cost.is_less_than(&curr_vlr.spill_cost));
985 // Evict all evictees in the set
986 for vlrix_to_evict in vlrixs_to_evict.iter() {
987 // Ensure we're not evicting anything in `curr_vlrix`'s eclass.
988 // This should be guaranteed us by find_evict_set.
989 assert!(
990 vlrEquivClasses.in_same_equivalence_class(*vlrix_to_evict, curr_vlrix)
991 != Some(true)
992 );
993 // Evict ..
994 debug!(
995 "-- CO evict {:?}: {:?}",
996 *vlrix_to_evict, &vlr_env[*vlrix_to_evict]
997 );
998 per_real_reg[rregNo].del_VirtualRange(*vlrix_to_evict, &vlr_env);
999 prioQ.add_VirtualRange(&vlr_env, *vlrix_to_evict);
1000 // Directly modify bits of vlr_env. This means we have to abandon
1001 // the immutable borrow for curr_vlr, but that's OK -- we won't need
1002 // it again (in this loop iteration).
1003 debug_assert!(vlr_env[*vlrix_to_evict].rreg.is_some());
1004 vlr_env[*vlrix_to_evict].rreg = None;
1005 num_vlrs_evicted += 1;
1006 }
1007 // .. and reassign.
1008 debug!("-- CO alloc to {}", reg_universe.regs[rregNo].1);
1009 per_real_reg[rregNo].add_VirtualRange(curr_vlrix, &vlr_env);
1010 vlr_env[curr_vlrix].rreg = Some(*rreg);
1011 // We're done!
1012 continue 'main_allocation_loop;
1013 }
1014 } /* for rreg in hinted_regs */
1015 // === END try to use the hints for `curr_vlr` ===
1016
1017 // ====== END Try to do coalescing ======
1018
1019 // We get here if we failed to find a viable assignment by the process of
1020 // looking at the coalescing hints.
1021 //
1022 // So: do almost exactly as we did in the "try for coalescing" stage
1023 // above. Except, instead of trying each coalescing candidate
1024 // individually, iterate over all the registers in the class, to find the
1025 // one (if any) that has the lowest total evict cost. If we find one that
1026 // has zero cost -- that is, we can make the assignment without evicting
1027 // anything -- then stop the search at that point, since searching further
1028 // is pointless.
1029
1030 let (first_in_rc, last_in_rc) = match ®_universe.allocable_by_class[curr_vlr_rc] {
1031 &None => {
1032 return Err(RegAllocError::OutOfRegisters(curr_vlr_regclass));
1033 }
1034 &Some(ref info) => (info.first, info.last),
1035 };
1036
1037 let mut best_so_far: Option<(
1038 /*rreg index*/ usize,
1039 SparseSetU<[VirtualRangeIx; 4]>,
1040 SpillCost,
1041 )> = None;
1042
1043 'search_through_cand_rregs_loop: for rregNo in first_in_rc..last_in_rc + 1 {
1044 //debug!("-- Cand {} ...",
1045 // reg_universe.regs[rregNo].1);
1046
1047 let mb_evict_info: Option<(SparseSetU<[VirtualRangeIx; 4]>, SpillCost)> =
1048 per_real_reg[rregNo].find_evict_set(
1049 curr_vlrix,
1050 // We pass a closure that ignores its arg and returns `true`.
1051 // Meaning, "we are not specifying any particular
1052 // can't-be-evicted VLRs in this call."
1053 &|_vlrix_to_evict| true,
1054 &vlr_env,
1055 );
1056 //
1057 //match mb_evict_info {
1058 // None => debug!("-- Cand {}: Unavail",
1059 // reg_universe.regs[rregNo].1),
1060 // Some((ref evict_set, ref evict_cost)) =>
1061 // debug!("-- Cand {}: Avail, evict cost {:?}, set {:?}",
1062 // reg_universe.regs[rregNo].1, evict_cost, evict_set)
1063 //}
1064 //
1065 if let Some((cand_vlrixs_to_evict, cand_total_evict_cost)) = mb_evict_info {
1066 // Stay sane ..
1067 assert!(cand_vlrixs_to_evict.is_empty() == cand_total_evict_cost.is_zero());
1068 // We can't evict if any in the set are spill ranges, and
1069 // find_evict_set should not offer us that possibility.
1070 assert!(cand_total_evict_cost.is_finite());
1071 // Ensure forward progress
1072 assert!(cand_total_evict_cost.is_less_than(&curr_vlr.spill_cost));
1073 // Update the "best so far". First, if the evict set is empty, then
1074 // the candidate is by definition better than all others, and we will
1075 // quit searching just below.
1076 let mut cand_is_better = cand_vlrixs_to_evict.is_empty();
1077 if !cand_is_better {
1078 if let Some((_, _, best_spill_cost)) = best_so_far {
1079 // If we've already got a candidate, this one is better if it has
1080 // a lower total spill cost.
1081 if cand_total_evict_cost.is_less_than(&best_spill_cost) {
1082 cand_is_better = true;
1083 }
1084 } else {
1085 // We don't have any candidate so far, so what we just got is
1086 // better (than nothing).
1087 cand_is_better = true;
1088 }
1089 }
1090 // Remember the candidate if required.
1091 let cand_vlrixs_to_evict_is_empty = cand_vlrixs_to_evict.is_empty();
1092 if cand_is_better {
1093 best_so_far = Some((rregNo, cand_vlrixs_to_evict, cand_total_evict_cost));
1094 }
1095 // If we've found a no-evictions-necessary candidate, quit searching
1096 // immediately. We won't find anything better.
1097 if cand_vlrixs_to_evict_is_empty {
1098 break 'search_through_cand_rregs_loop;
1099 }
1100 }
1101 } // for rregNo in first_in_rc..last_in_rc + 1 {
1102
1103 // Examine the results of the search. Did we find any usable candidate?
1104 if let Some((rregNo, vlrixs_to_evict, total_spill_cost)) = best_so_far {
1105 // We are still Totally Paranoid (tm)
1106 // Stay sane #1
1107 debug_assert!(curr_vlr.rreg.is_none());
1108 // Can't spill a spill range
1109 assert!(total_spill_cost.is_finite());
1110 // Ensure forward progress
1111 assert!(total_spill_cost.is_less_than(&curr_vlr.spill_cost));
1112 // Now the same evict-reassign section as with the coalescing logic above.
1113 // Evict all evictees in the set
1114 for vlrix_to_evict in vlrixs_to_evict.iter() {
1115 // Evict ..
1116 debug!(
1117 "-- DI evict {:?}: {:?}",
1118 *vlrix_to_evict, &vlr_env[*vlrix_to_evict]
1119 );
1120 per_real_reg[rregNo].del_VirtualRange(*vlrix_to_evict, &vlr_env);
1121 prioQ.add_VirtualRange(&vlr_env, *vlrix_to_evict);
1122 debug_assert!(vlr_env[*vlrix_to_evict].rreg.is_some());
1123 vlr_env[*vlrix_to_evict].rreg = None;
1124 num_vlrs_evicted += 1;
1125 }
1126 // .. and reassign.
1127 debug!("-- DI alloc to {}", reg_universe.regs[rregNo].1);
1128 per_real_reg[rregNo].add_VirtualRange(curr_vlrix, &vlr_env);
1129 let rreg = reg_universe.regs[rregNo].0;
1130 vlr_env[curr_vlrix].rreg = Some(rreg);
1131 // We're done!
1132 continue 'main_allocation_loop;
1133 }
1134
1135 // Still no luck. We can't find a register to put it in, so we'll
1136 // have to spill it, since splitting it isn't yet implemented.
1137 debug!("-- spill");
1138
1139 // If the live range already pertains to a spill or restore, then
1140 // it's Game Over. The constraints (availability of RealRegs vs
1141 // requirement for them) are impossible to fulfill, and so we cannot
1142 // generate any valid allocation for this function.
1143 if curr_vlr.spill_cost.is_infinite() {
1144 return Err(RegAllocError::OutOfRegisters(curr_vlr_regclass));
1145 }
1146
1147 // Generate a new spill slot number, S
1148 /* Spilling vreg V with virtual live range VirtualRange to slot S:
1149 for each frag F in VirtualRange {
1150 for each insn I in F.first.iix .. F.last.iix {
1151 if I does not mention V
1152 continue
1153 if I mentions V in a Read role {
1154 // invar: I cannot mention V in a Mod role
1155 add new VirtualRange I.reload -> I.use,
1156 vreg V, spillcost Inf
1157 add eli @ I.reload V SpillSlot
1158 }
1159 if I mentions V in a Mod role {
1160 // invar: I cannot mention V in a Read or Write Role
1161 add new VirtualRange I.reload -> I.spill,
1162 Vreg V, spillcost Inf
1163 add eli @ I.reload V SpillSlot
1164 add eli @ I.spill SpillSlot V
1165 }
1166 if I mentions V in a Write role {
1167 // invar: I cannot mention V in a Mod role
1168 add new VirtualRange I.def -> I.spill,
1169 vreg V, spillcost Inf
1170 add eli @ I.spill V SpillSlot
1171 }
1172 }
1173 }
1174 */
1175
1176 // We will be spilling vreg `curr_vlr.reg` with VirtualRange `curr_vlr` to
1177 // a spill slot that the spill slot allocator will choose for us, just a
1178 // bit further down this function.
1179
1180 // This holds enough info to create reload or spill (or both)
1181 // instructions around an instruction that references a VirtualReg
1182 // that has been spilled.
1183 struct SpillAndOrReloadInfo {
1184 bix: BlockIx, // that `iix` is in
1185 iix: InstIx, // this is the Inst we are spilling/reloading for
1186 kind: BridgeKind, // says whether to create a spill or reload or both
1187 }
1188
1189 // Most spills won't require anywhere near 32 entries, so this avoids
1190 // almost all heap allocation.
1191 let mut sri_vec = SmallVec::<[SpillAndOrReloadInfo; 32]>::new();
1192
1193 let curr_vlr_vreg = curr_vlr.vreg;
1194 let curr_vlr_reg = curr_vlr_vreg.to_reg();
1195 let curr_vlr_is_ref = curr_vlr.is_ref;
1196
1197 for frag in &curr_vlr.sorted_frags.frags {
1198 for iix in frag.first.iix().dotdot(frag.last.iix().plus(1)) {
1199 let (iix_uses_curr_vlr_reg, iix_defs_curr_vlr_reg, iix_mods_curr_vlr_reg) =
1200 does_inst_use_def_or_mod_reg(®_vecs_and_bounds, iix, curr_vlr_reg);
1201 // If this insn doesn't mention the vreg we're spilling for,
1202 // move on.
1203 if !iix_defs_curr_vlr_reg && !iix_mods_curr_vlr_reg && !iix_uses_curr_vlr_reg {
1204 continue;
1205 }
1206 // USES: Do we need to create a reload-to-use bridge
1207 // (VirtualRange) ?
1208 if iix_uses_curr_vlr_reg && frag.contains(&InstPoint::new_use(iix)) {
1209 debug_assert!(!iix_mods_curr_vlr_reg);
1210 // Stash enough info that we can create a new VirtualRange
1211 // and a new edit list entry for the reload.
1212 let bix = inst_to_block_map.map(iix);
1213 let sri = SpillAndOrReloadInfo {
1214 bix,
1215 iix,
1216 kind: BridgeKind::RtoU,
1217 };
1218 sri_vec.push(sri);
1219 }
1220 // MODS: Do we need to create a reload-to-spill bridge? This
1221 // can only happen for instructions which modify a register.
1222 // Note this has to be a single VirtualRange, since if it were
1223 // two (one for the reload, one for the spill) they could
1224 // later end up being assigned to different RealRegs, which is
1225 // obviously nonsensical.
1226 if iix_mods_curr_vlr_reg
1227 && frag.contains(&InstPoint::new_use(iix))
1228 && frag.contains(&InstPoint::new_def(iix))
1229 {
1230 debug_assert!(!iix_uses_curr_vlr_reg);
1231 debug_assert!(!iix_defs_curr_vlr_reg);
1232 let bix = inst_to_block_map.map(iix);
1233 let sri = SpillAndOrReloadInfo {
1234 bix,
1235 iix,
1236 kind: BridgeKind::RtoS,
1237 };
1238 sri_vec.push(sri);
1239 }
1240 // DEFS: Do we need to create a def-to-spill bridge?
1241 if iix_defs_curr_vlr_reg && frag.contains(&InstPoint::new_def(iix)) {
1242 debug_assert!(!iix_mods_curr_vlr_reg);
1243 let bix = inst_to_block_map.map(iix);
1244 let sri = SpillAndOrReloadInfo {
1245 bix,
1246 iix,
1247 kind: BridgeKind::DtoS,
1248 };
1249 sri_vec.push(sri);
1250 }
1251 }
1252 }
1253
1254 // Now that we no longer need to access `frag_env` or `vlr_env` for
1255 // the remainder of this iteration of the main allocation loop, we can
1256 // actually generate the required spill/reload artefacts.
1257
1258 // First off, poke the spill slot allocator to get an intelligent choice
1259 // of slot. Note that this will fail for "non-initial" VirtualRanges; but
1260 // the only non-initial ones will have been created by spilling anyway,
1261 // any we definitely shouldn't be trying to spill them again. Hence we
1262 // can assert.
1263 assert!(vlr_slot_env.len() == num_vlrs_initial);
1264 assert!(curr_vlrix < VirtualRangeIx::new(num_vlrs_initial));
1265 if vlr_slot_env[curr_vlrix].is_none() {
1266 // It hasn't been decided yet. Cause it to be so by asking for an
1267 // allocation for the entire eclass that `curr_vlrix` belongs to.
1268 spill_slot_allocator.alloc_spill_slots(
1269 &mut vlr_slot_env,
1270 func,
1271 &vlr_env,
1272 &vlrEquivClasses,
1273 curr_vlrix,
1274 );
1275 assert!(vlr_slot_env[curr_vlrix].is_some());
1276 }
1277 let spill_slot_to_use = vlr_slot_env[curr_vlrix].unwrap();
1278
1279 // If we're spilling a reffy VLR, we'll need to tell the spillslot allocator that. The
1280 // VLR will already have been allocated to some spill slot, and relevant RangeFrags in
1281 // the slot should have already been reserved for it, by the above call to
1282 // `alloc_spill_slots` (although possibly relating to a prior VLR in the same
1283 // equivalence class, and not this one). However, those RangeFrags will have all been
1284 // marked non-reffy, because we don't know, in general, at spillslot-allocation-time,
1285 // whether a VLR will actually be spilled, and we don't want the resulting stack maps to
1286 // mention stack entries which are dead at the point of the safepoint insn. Hence the
1287 // need to update those RangeFrags pertaining to just this VLR -- now that we *know*
1288 // it's going to be spilled.
1289 if curr_vlr.is_ref {
1290 spill_slot_allocator
1291 .notify_spillage_of_reftyped_vlr(spill_slot_to_use, &curr_vlr.sorted_frags);
1292 }
1293
1294 for sri in sri_vec {
1295 let (new_vlr_first_pt, new_vlr_last_pt) = match sri.kind {
1296 BridgeKind::RtoU => (Point::Reload, Point::Use),
1297 BridgeKind::RtoS => (Point::Reload, Point::Spill),
1298 BridgeKind::DtoS => (Point::Def, Point::Spill),
1299 };
1300 let new_vlr_frag = RangeFrag {
1301 first: InstPoint::new(sri.iix, new_vlr_first_pt),
1302 last: InstPoint::new(sri.iix, new_vlr_last_pt),
1303 };
1304 debug!("-- new RangeFrag {:?}", &new_vlr_frag);
1305 let new_vlr_sfrags = SortedRangeFrags::unit(new_vlr_frag);
1306 let new_vlr = VirtualRange {
1307 vreg: curr_vlr_vreg,
1308 rreg: None,
1309 sorted_frags: new_vlr_sfrags,
1310 is_ref: curr_vlr_is_ref, // "inherit" refness
1311 size: 1,
1312 // Effectively infinite. We'll never look at this again anyway.
1313 total_cost: 0xFFFF_FFFFu32,
1314 spill_cost: SpillCost::infinite(),
1315 };
1316 let new_vlrix = VirtualRangeIx::new(vlr_env.len() as u32);
1317 debug!(
1318 "-- new VirtRange {:?} := {:?}",
1319 new_vlrix, &new_vlr
1320 );
1321 vlr_env.push(new_vlr);
1322 prioQ.add_VirtualRange(&vlr_env, new_vlrix);
1323
1324 // BEGIN (optimisation only) see if we can create any coalescing hints
1325 // for this new VLR.
1326 let mut new_vlr_hint = SmallVec::<[Hint; 8]>::new();
1327 if is_vv_boundary_move[sri.iix] {
1328 // Collect the src and dst regs for the move. It must be a
1329 // move because `is_vv_boundary_move` claims that to be true.
1330 let im = func.is_move(&func.get_insn(sri.iix));
1331 assert!(im.is_some());
1332 let (wdst_reg, src_reg): (Writable<Reg>, Reg) = im.unwrap();
1333 let dst_reg: Reg = wdst_reg.to_reg();
1334 assert!(src_reg.is_virtual() && dst_reg.is_virtual());
1335 let dst_vreg: VirtualReg = dst_reg.to_virtual_reg();
1336 let src_vreg: VirtualReg = src_reg.to_virtual_reg();
1337 let bridge_eef = est_freqs[sri.bix];
1338 match sri.kind {
1339 BridgeKind::RtoU => {
1340 // Reload-to-Use bridge. Hint that we want to be
1341 // allocated to the same reg as the destination of the
1342 // move. That means we have to find the VLR that owns
1343 // the destination vreg.
1344 for vlrix in ®_to_ranges_maps.vreg_to_vlrs_map[dst_vreg.get_index()] {
1345 if vlr_env[*vlrix].vreg == dst_vreg {
1346 new_vlr_hint.push(Hint::SameAs(*vlrix, bridge_eef));
1347 break;
1348 }
1349 }
1350 }
1351 BridgeKind::DtoS => {
1352 // Def-to-Spill bridge. Hint that we want to be
1353 // allocated to the same reg as the source of the
1354 // move.
1355 for vlrix in ®_to_ranges_maps.vreg_to_vlrs_map[src_vreg.get_index()] {
1356 if vlr_env[*vlrix].vreg == src_vreg {
1357 new_vlr_hint.push(Hint::SameAs(*vlrix, bridge_eef));
1358 break;
1359 }
1360 }
1361 }
1362 BridgeKind::RtoS => {
1363 // A Reload-to-Spill bridge. This can't happen. It
1364 // implies that the instruction modifies (both reads
1365 // and writes) one of its operands, but the client's
1366 // `is_move` function claims this instruction is a
1367 // plain "move" (reads source, writes dest). These
1368 // claims are mutually contradictory.
1369 panic!("RtoS bridge for v-v boundary move");
1370 }
1371 }
1372 }
1373 hints.push(new_vlr_hint);
1374 // END see if we can create any coalescing hints for this new VLR.
1375
1376 // Finally, create a new EditListItem. This holds enough
1377 // information that a suitable spill or reload instruction can
1378 // later be created.
1379 let new_eli = EditListItem {
1380 slot: spill_slot_to_use,
1381 vlrix: new_vlrix,
1382 kind: sri.kind,
1383 iix: sri.iix,
1384 };
1385 if is_vv_boundary_move[sri.iix] {
1386 debug!("-- new ELI MOVE {:?}", &new_eli);
1387 edit_list_move.push(new_eli);
1388 } else {
1389 debug!("-- new ELI other {:?}", &new_eli);
1390 edit_list_other.push(new_eli);
1391 }
1392 }
1393
1394 num_vlrs_spilled += 1;
1395 // And implicitly "continue 'main_allocation_loop"
1396 }
1397 // ======== END Main allocation loop ========
1398
1399 info!("alloc_main: main allocation loop: end");
1400
1401 if log_enabled!(Level::Debug) {
1402 debug!("");
1403 print_RA_state(
1404 "Final",
1405 ®_universe,
1406 &prioQ,
1407 &per_real_reg,
1408 &edit_list_move,
1409 &edit_list_other,
1410 &vlr_env,
1411 &frag_env,
1412 );
1413 }
1414
1415 // ======== BEGIN Do spill slot coalescing ========
1416
1417 debug!("");
1418 info!("alloc_main: create spills_n_reloads for MOVE insns");
1419
1420 // Sort `edit_list_move` by the insn with which each item is associated.
1421 edit_list_move.sort_unstable_by(|eli1, eli2| eli1.iix.cmp(&eli2.iix));
1422
1423 // Now go through `edit_list_move` and find pairs which constitute a
1424 // spillslot-to-the-same-spillslot move. What we have in `edit_list_move` is
1425 // heavily constrained, as follows:
1426 //
1427 // * each entry should reference an InstIx which the coalescing analysis
1428 // identified as a virtual-to-virtual copy which exists at the boundary
1429 // between two VirtualRanges. The "boundary" aspect is important; we
1430 // can't coalesce out moves in which the source vreg is not the "last use"
1431 // or for which the destination vreg is not the "first def". (The same is
1432 // true for coalescing of unspilled moves).
1433 //
1434 // * the each entry must reference a VirtualRange which has only a single
1435 // RangeFrag, and that frag must exist entirely "within" the referenced
1436 // instruction. Specifically, it may only be a R->U frag (bridge) or a
1437 // D->S frag.
1438 //
1439 // * For a referenced instruction, there may be at most two entries in this
1440 // list: one that references the R->U frag and one that references the
1441 // D->S frag. Furthermore, the two entries must carry values of the same
1442 // RegClass; if that isn't true, the client's `is_move` function is
1443 // defective.
1444 //
1445 // For any such pair identified, if both frags mention the same spill slot,
1446 // we skip generating both the reload and the spill instruction. We also
1447 // note that the instruction itself is to be deleted (converted to a
1448 // zero-len nop). In a sense we have "cancelled out" a reload/spill pair.
1449 // Entries that can't be cancelled out are handled the same way as for
1450 // entries in `edit_list_other`, by simply copying them there.
1451 //
1452 // Since `edit_list_move` is sorted by insn ix, we can scan linearly over
1453 // it, looking for adjacent pairs. We'll have to accept them in either
1454 // order though (first R->U then D->S, or the other way round). There's no
1455 // fixed ordering since there is no particular ordering in the way
1456 // VirtualRanges are allocated.
1457
1458 // As a result of spill slot coalescing, we'll need to delete the move
1459 // instructions leading to a mergable spill slot move. The insn stream
1460 // editor can't delete instructions, so instead it'll replace them with zero
1461 // len nops obtained from the client. `iixs_to_nop_out` records the insns
1462 // that this has to happen to. It is in increasing order of InstIx (because
1463 // `edit_list_sorted` is), and the indices in it refer to the original
1464 // virtual-registerised code.
1465 let mut iixs_to_nop_out = Vec::<InstIx>::new();
1466 let mut ghost_moves = vec![];
1467
1468 let n_edit_list_move = edit_list_move.len();
1469 let mut n_edit_list_move_processed = 0; // for assertions only
1470 let mut i_min = 0;
1471 loop {
1472 if i_min >= n_edit_list_move {
1473 break;
1474 }
1475 // Find the bounds of the current group.
1476 debug!("editlist entry (MOVE): min: {:?}", &edit_list_move[i_min]);
1477 let i_min_iix = edit_list_move[i_min].iix;
1478 let mut i_max = i_min;
1479 while i_max + 1 < n_edit_list_move && edit_list_move[i_max + 1].iix == i_min_iix {
1480 i_max += 1;
1481 debug!("editlist entry (MOVE): max: {:?}", &edit_list_move[i_max]);
1482 }
1483 // Current group is from i_min to i_max inclusive. At most 2 entries are
1484 // allowed per group.
1485 assert!(i_max - i_min <= 1);
1486 // Check for a mergeable pair.
1487 if i_max - i_min == 1 {
1488 assert!(is_vv_boundary_move[i_min_iix]);
1489 let vlrix1 = edit_list_move[i_min].vlrix;
1490 let vlrix2 = edit_list_move[i_max].vlrix;
1491 assert!(vlrix1 != vlrix2);
1492 let vlr1 = &vlr_env[vlrix1];
1493 let vlr2 = &vlr_env[vlrix2];
1494 let frags1 = &vlr1.sorted_frags;
1495 let frags2 = &vlr2.sorted_frags;
1496 assert!(frags1.frags.len() == 1);
1497 assert!(frags2.frags.len() == 1);
1498 let frag1 = &frags1.frags[0];
1499 let frag2 = &frags2.frags[0];
1500 assert!(frag1.first.iix() == i_min_iix);
1501 assert!(frag1.last.iix() == i_min_iix);
1502 assert!(frag2.first.iix() == i_min_iix);
1503 assert!(frag2.last.iix() == i_min_iix);
1504 // frag1 must be R->U and frag2 must be D->S, or vice versa
1505 match (
1506 frag1.first.pt(),
1507 frag1.last.pt(),
1508 frag2.first.pt(),
1509 frag2.last.pt(),
1510 ) {
1511 (Point::Reload, Point::Use, Point::Def, Point::Spill)
1512 | (Point::Def, Point::Spill, Point::Reload, Point::Use) => {
1513 let slot1 = edit_list_move[i_min].slot;
1514 let slot2 = edit_list_move[i_max].slot;
1515 if slot1 == slot2 {
1516 // Yay. We've found a coalescable pair. We can just ignore the
1517 // two entries and move on. Except we have to mark the insn
1518 // itself for deletion.
1519 debug!("editlist entry (MOVE): delete {:?}", i_min_iix);
1520 iixs_to_nop_out.push(i_min_iix);
1521 i_min = i_max + 1;
1522 n_edit_list_move_processed += 2;
1523 if use_checker {
1524 let (from_reg, to_reg) = if frag1.last.pt() == Point::Use {
1525 (vlr1.vreg.to_reg(), vlr2.vreg.to_reg())
1526 } else {
1527 (vlr2.vreg.to_reg(), vlr1.vreg.to_reg())
1528 };
1529 ghost_moves.push(InstToInsertAndExtPoint::new(
1530 InstToInsert::ChangeSpillSlotOwnership {
1531 inst_ix: i_min_iix,
1532 slot: slot1,
1533 from_reg,
1534 to_reg,
1535 },
1536 InstExtPoint::new(i_min_iix, ExtPoint::Reload),
1537 ));
1538 }
1539 continue;
1540 }
1541 }
1542 (_, _, _, _) => {
1543 panic!("spill slot coalescing, edit_list_move: unexpected frags");
1544 }
1545 }
1546 }
1547 // If we get here for whatever reason, this group is uninteresting. Copy
1548 // in to `edit_list_other` so that it gets processed in the normal way.
1549 for i in i_min..=i_max {
1550 edit_list_other.push(edit_list_move[i]);
1551 n_edit_list_move_processed += 1;
1552 }
1553 i_min = i_max + 1;
1554 }
1555 assert!(n_edit_list_move_processed == n_edit_list_move);
1556
1557 // ======== END Do spill slot coalescing ========
1558
1559 // ======== BEGIN Create all other spills and reloads ========
1560
1561 debug!("");
1562 info!("alloc_main: create spills_n_reloads for other insns");
1563
1564 // Reload and spill instructions are missing. To generate them, go through
1565 // the "edit list", which contains info on both how to generate the
1566 // instructions, and where to insert them.
1567 let mut spills_n_reloads = Vec::<InstToInsertAndExtPoint>::new();
1568 let mut num_spills = 0; // stats only
1569 let mut num_reloads = 0; // stats only
1570 for eli in &edit_list_other {
1571 debug!("editlist entry (other): {:?}", eli);
1572 let vlr = &vlr_env[eli.vlrix];
1573 let vlr_sfrags = &vlr.sorted_frags;
1574 assert!(vlr_sfrags.frags.len() == 1);
1575 let vlr_frag = &vlr_sfrags.frags[0];
1576 let rreg = vlr.rreg.expect("Gen of spill/reload: reg not assigned?!");
1577 let vreg = vlr.vreg;
1578 match eli.kind {
1579 BridgeKind::RtoU => {
1580 debug_assert!(vlr_frag.first.pt().is_reload());
1581 debug_assert!(vlr_frag.last.pt().is_use());
1582 debug_assert!(vlr_frag.first.iix() == vlr_frag.last.iix());
1583 let insnR = InstToInsert::Reload {
1584 to_reg: Writable::from_reg(rreg),
1585 from_slot: eli.slot,
1586 for_vreg: Some(vreg),
1587 };
1588 let whereToR = InstExtPoint::from_inst_point(vlr_frag.first);
1589 spills_n_reloads.push(InstToInsertAndExtPoint::new(insnR, whereToR));
1590 num_reloads += 1;
1591 }
1592 BridgeKind::RtoS => {
1593 debug_assert!(vlr_frag.first.pt().is_reload());
1594 debug_assert!(vlr_frag.last.pt().is_spill());
1595 debug_assert!(vlr_frag.first.iix() == vlr_frag.last.iix());
1596 let insnR = InstToInsert::Reload {
1597 to_reg: Writable::from_reg(rreg),
1598 from_slot: eli.slot,
1599 for_vreg: Some(vreg),
1600 };
1601 let whereToR = InstExtPoint::from_inst_point(vlr_frag.first);
1602 let insnS = InstToInsert::Spill {
1603 to_slot: eli.slot,
1604 from_reg: rreg,
1605 for_vreg: Some(vreg),
1606 };
1607 let whereToS = InstExtPoint::from_inst_point(vlr_frag.last);
1608 spills_n_reloads.push(InstToInsertAndExtPoint::new(insnR, whereToR));
1609 spills_n_reloads.push(InstToInsertAndExtPoint::new(insnS, whereToS));
1610 num_reloads += 1;
1611 num_spills += 1;
1612 }
1613 BridgeKind::DtoS => {
1614 debug_assert!(vlr_frag.first.pt().is_def());
1615 debug_assert!(vlr_frag.last.pt().is_spill());
1616 debug_assert!(vlr_frag.first.iix() == vlr_frag.last.iix());
1617 let insnS = InstToInsert::Spill {
1618 to_slot: eli.slot,
1619 from_reg: rreg,
1620 for_vreg: Some(vreg),
1621 };
1622 let whereToS = InstExtPoint::from_inst_point(vlr_frag.last);
1623 spills_n_reloads.push(InstToInsertAndExtPoint::new(insnS, whereToS));
1624 num_spills += 1;
1625 }
1626 }
1627 }
1628
1629 // Append all ghost moves.
1630 if use_checker {
1631 spills_n_reloads.extend(ghost_moves.into_iter());
1632 spills_n_reloads.sort_by_key(|inst_and_point| inst_and_point.iep.clone());
1633 }
1634
1635 // ======== END Create all other spills and reloads ========
1636
1637 // ======== BEGIN Create final instruction stream ========
1638
1639 // Gather up a vector of (RangeFrag, VirtualReg, RealReg) resulting from
1640 // the previous phase. This fundamentally is the result of the allocation
1641 // and tells us how the instruction stream must be edited. Note it does
1642 // not take account of spill or reload instructions. Dealing with those
1643 // is relatively simple and happens later.
1644
1645 info!("alloc_main: create frag_map");
1646
1647 let mut frag_map = Vec::<(RangeFrag, VirtualReg, RealReg)>::new();
1648 // For each real register under our control ..
1649 for i in 0..reg_universe.allocable {
1650 let rreg = reg_universe.regs[i].0;
1651 // .. look at all the VirtualRanges assigned to it. And for each such
1652 // VirtualRange ..
1653 for vlrix_assigned in per_real_reg[i].vlrixs_assigned.iter() {
1654 let VirtualRange {
1655 vreg, sorted_frags, ..
1656 } = &vlr_env[*vlrix_assigned];
1657 // All the RangeFrags in `vlr_assigned` require `vlr_assigned.reg`
1658 // to be mapped to the real reg `i`
1659 // .. collect up all its constituent RangeFrags.
1660 for frag in &sorted_frags.frags {
1661 frag_map.push((frag.clone(), *vreg, rreg));
1662 }
1663 }
1664 }
1665
1666 // There is one of these for every entry in `safepoint_insns`.
1667 let mut stackmaps = Vec::<Vec<SpillSlot>>::new();
1668
1669 if !safepoint_insns.is_empty() {
1670 info!("alloc_main: create safepoints and stackmaps");
1671 for safepoint_iix in safepoint_insns {
1672 // Create the stackmap artefacts for `safepoint_iix`. Save the stackmap (the
1673 // reftyped spillslots); we'll have to return it to the client as part of the
1674 // overall allocation result. The extra spill and reload instructions can simply
1675 // be added to `spills_n_reloads` though, and `edit_inst_stream` will correctly
1676 // merge them in.
1677 //
1678 // Note: this modifies `spill_slot_allocator`, since at this point we have to
1679 // allocate spill slots to hold reftyped real regs across the safepoint insn.
1680 //
1681 // Because the SB (spill-before) and RA (reload-after) `ExtPoint`s are "closer" to
1682 // the "core" of an instruction than the R (reload) and S (spill) `ExtPoint`s, any
1683 // "normal" reload or spill ranges that are reftyped will be handled correctly.
1684 // From `get_stackmap_artefacts_at`s point of view, such spill/reload ranges are
1685 // just like any other real-reg live range that it will have to spill around the
1686 // safepoint. The fact that they are for spills or reloads doesn't make any
1687 // difference.
1688 //
1689 // Note also: this call can fail; failure is propagated upwards.
1690 //
1691 // FIXME Passing these 3 small vectors around is inefficient. Use SmallVec or
1692 // (better) owned-by-this-function vectors instead.
1693 let (spills_before, reloads_after, reftyped_spillslots) = get_stackmap_artefacts_at(
1694 &mut spill_slot_allocator,
1695 ®_universe,
1696 reftype_class,
1697 ®_vecs_and_bounds,
1698 &per_real_reg,
1699 &rlr_env,
1700 &vlr_env,
1701 *safepoint_iix,
1702 )?;
1703 stackmaps.push(reftyped_spillslots);
1704 for spill_before in spills_before {
1705 spills_n_reloads.push(InstToInsertAndExtPoint::new(
1706 spill_before,
1707 InstExtPoint::new(*safepoint_iix, ExtPoint::SpillBefore),
1708 ));
1709 }
1710 for reload_after in reloads_after {
1711 spills_n_reloads.push(InstToInsertAndExtPoint::new(
1712 reload_after,
1713 InstExtPoint::new(*safepoint_iix, ExtPoint::ReloadAfter),
1714 ));
1715 }
1716 }
1717 }
1718
1719 info!("alloc_main: edit_inst_stream");
1720
1721 let final_insns_and_targetmap_and_new_safepoints__or_err = edit_inst_stream(
1722 func,
1723 &safepoint_insns,
1724 spills_n_reloads,
1725 &iixs_to_nop_out,
1726 frag_map,
1727 ®_universe,
1728 use_checker,
1729 &stackmaps[..],
1730 &reftyped_vregs[..],
1731 );
1732
1733 // ======== END Create final instruction stream ========
1734
1735 // ======== BEGIN Create the RegAllocResult ========
1736
1737 match final_insns_and_targetmap_and_new_safepoints__or_err {
1738 Ok((ref final_insns, ..)) => {
1739 info!(
1740 "alloc_main: out: VLRs: {} initially, {} processed",
1741 num_vlrs_initial, num_vlrs_processed
1742 );
1743 info!(
1744 "alloc_main: out: VLRs: {} evicted, {} spilled",
1745 num_vlrs_evicted, num_vlrs_spilled
1746 );
1747 info!(
1748 "alloc_main: out: insns: {} total, {} spills, {} reloads, {} nopzs",
1749 final_insns.len(),
1750 num_spills,
1751 num_reloads,
1752 iixs_to_nop_out.len()
1753 );
1754 info!(
1755 "alloc_main: out: spill slots: {} used",
1756 spill_slot_allocator.num_slots_in_use()
1757 );
1758 }
1759 Err(_) => {
1760 info!("alloc_main: allocation failed!");
1761 }
1762 }
1763
1764 let (final_insns, target_map, new_to_old_insn_map, new_safepoint_insns) =
1765 match final_insns_and_targetmap_and_new_safepoints__or_err {
1766 Err(e) => {
1767 info!("alloc_main: fail");
1768 return Err(e);
1769 }
1770 Ok(quad) => {
1771 info!("alloc_main: creating RegAllocResult");
1772 quad
1773 }
1774 };
1775
1776 // Compute clobbered registers with one final, quick pass.
1777 //
1778 // FIXME: derive this information directly from the allocation data
1779 // structures used above.
1780 //
1781 // NB at this point, the `san_reg_uses` that was computed in the analysis
1782 // phase is no longer valid, because we've added and removed instructions to
1783 // the function relative to the one that `san_reg_uses` was computed from,
1784 // so we have to re-visit all insns with `add_raw_reg_vecs_for_insn`.
1785 // That's inefficient, but we don't care .. this should only be a temporary
1786 // fix.
1787
1788 let mut clobbered_registers: Set<RealReg> = Set::empty();
1789
1790 // We'll dump all the reg uses in here. We don't care about the bounds, so just
1791 // pass a dummy one in the loop.
1792 let mut reg_vecs = RegVecs::new(/*sanitized=*/ false);
1793 let mut dummy_bounds = RegVecBounds::new();
1794 for insn in &final_insns {
1795 if func.is_included_in_clobbers(insn) {
1796 add_raw_reg_vecs_for_insn::<F>(insn, &mut reg_vecs, &mut dummy_bounds);
1797 }
1798 }
1799 for reg in reg_vecs.defs.iter().chain(reg_vecs.mods.iter()) {
1800 assert!(reg.is_real());
1801 clobbered_registers.insert(reg.to_real_reg());
1802 }
1803
1804 // And now remove from the set, all those not available to the allocator.
1805 // But not removing the reserved regs, since we might have modified those.
1806 clobbered_registers.filter_map(|®| {
1807 if reg.get_index() >= reg_universe.allocable {
1808 None
1809 } else {
1810 Some(reg)
1811 }
1812 });
1813
1814 assert!(est_freqs.len() as usize == func.blocks().len());
1815 let mut block_annotations = None;
1816 if opts.request_block_annotations {
1817 let mut anns = TypedIxVec::<BlockIx, Vec<String>>::new();
1818 for (estFreq, i) in est_freqs.iter().zip(0..) {
1819 let bix = BlockIx::new(i);
1820 let ef_str = format!("RA: bix {:?}, estFreq {}", bix, estFreq);
1821 anns.push(vec![ef_str]);
1822 }
1823 block_annotations = Some(anns);
1824 }
1825
1826 assert!(stackmaps.len() == safepoint_insns.len());
1827 assert!(new_safepoint_insns.len() == safepoint_insns.len());
1828 let ra_res = RegAllocResult {
1829 insns: final_insns,
1830 target_map,
1831 orig_insn_map: new_to_old_insn_map,
1832 clobbered_registers,
1833 num_spill_slots: spill_slot_allocator.num_slots_in_use() as u32,
1834 block_annotations,
1835 stackmaps,
1836 new_safepoint_insns,
1837 };
1838
1839 info!("alloc_main: end");
1840
1841 // ======== END Create the RegAllocResult ========
1842
1843 Ok(ra_res)
1844 }
1845