| /* |
| * This file was initially derived from the files |
| * `js/src/jit/BacktrackingAllocator.h` and |
| * `js/src/jit/BacktrackingAllocator.cpp` in Mozilla Firefox, and was |
| * originally licensed under the Mozilla Public License 2.0. We |
| * subsequently relicensed it to Apache-2.0 WITH LLVM-exception (see |
| * https://github.com/bytecodealliance/regalloc2/issues/7). |
| * |
| * Since the initial port, the design has been substantially evolved |
| * and optimized. |
| */ |
| |
| //! Main allocation loop that processes bundles. |
| |
| use super::{ |
| spill_weight_from_constraint, Env, LiveBundleIndex, LiveBundleVec, LiveRangeFlag, |
| LiveRangeIndex, LiveRangeKey, LiveRangeList, LiveRangeListEntry, PRegIndex, RegTraversalIter, |
| Requirement, SpillWeight, UseList, VRegIndex, |
| }; |
| use crate::{ |
| ion::data_structures::{ |
| CodeRange, BUNDLE_MAX_NORMAL_SPILL_WEIGHT, MAX_SPLITS_PER_SPILLSET, |
| MINIMAL_BUNDLE_SPILL_WEIGHT, MINIMAL_FIXED_BUNDLE_SPILL_WEIGHT, |
| }, |
| Allocation, Function, Inst, InstPosition, OperandConstraint, OperandKind, PReg, ProgPoint, |
| RegAllocError, |
| }; |
| use fxhash::FxHashSet; |
| use smallvec::{smallvec, SmallVec}; |
| use std::fmt::Debug; |
| |
| #[derive(Clone, Debug, PartialEq, Eq)] |
| pub enum AllocRegResult { |
| Allocated(Allocation), |
| Conflict(LiveBundleVec, ProgPoint), |
| ConflictWithFixed(u32, ProgPoint), |
| ConflictHighCost, |
| } |
| |
| impl<'a, F: Function> Env<'a, F> { |
| pub fn process_bundles(&mut self) -> Result<(), RegAllocError> { |
| while let Some((bundle, reg_hint)) = self.allocation_queue.pop() { |
| self.stats.process_bundle_count += 1; |
| self.process_bundle(bundle, reg_hint)?; |
| } |
| self.stats.final_liverange_count = self.ranges.len(); |
| self.stats.final_bundle_count = self.bundles.len(); |
| self.stats.spill_bundle_count = self.spilled_bundles.len(); |
| |
| Ok(()) |
| } |
| |
| pub fn try_to_allocate_bundle_to_reg( |
| &mut self, |
| bundle: LiveBundleIndex, |
| reg: PRegIndex, |
| // if the max bundle weight in the conflict set exceeds this |
| // cost (if provided), just return |
| // `AllocRegResult::ConflictHighCost`. |
| max_allowable_cost: Option<u32>, |
| ) -> AllocRegResult { |
| trace!("try_to_allocate_bundle_to_reg: {:?} -> {:?}", bundle, reg); |
| let mut conflicts = smallvec![]; |
| self.conflict_set.clear(); |
| let mut max_conflict_weight = 0; |
| // Traverse the BTreeMap in order by requesting the whole |
| // range spanned by the bundle and iterating over that |
| // concurrently with our ranges. Because our ranges are in |
| // order, and the BTreeMap is as well, this allows us to have |
| // an overall O(n log n) + O(b) complexity, where the PReg has |
| // n current ranges and the bundle has b ranges, rather than |
| // O(b * n log n) with the simple probe-for-each-bundle-range |
| // approach. |
| // |
| // Note that the comparator function on a CodeRange tests for |
| // *overlap*, so we are checking whether the BTree contains |
| // any preg range that *overlaps* with range `range`, not |
| // literally the range `range`. |
| let bundle_ranges = &self.bundles[bundle.index()].ranges; |
| let from_key = LiveRangeKey::from_range(&CodeRange { |
| from: bundle_ranges.first().unwrap().range.from, |
| to: bundle_ranges.first().unwrap().range.from, |
| }); |
| let mut preg_range_iter = self.pregs[reg.index()] |
| .allocations |
| .btree |
| .range(from_key..) |
| .peekable(); |
| trace!( |
| "alloc map for {:?} in range {:?}..: {:?}", |
| reg, |
| from_key, |
| self.pregs[reg.index()].allocations.btree |
| ); |
| let mut first_conflict: Option<ProgPoint> = None; |
| |
| 'ranges: for entry in bundle_ranges { |
| trace!(" -> range LR {:?}: {:?}", entry.index, entry.range); |
| let key = LiveRangeKey::from_range(&entry.range); |
| |
| let mut skips = 0; |
| 'alloc: loop { |
| trace!(" -> PReg range {:?}", preg_range_iter.peek()); |
| |
| // Advance our BTree traversal until it is >= this bundle |
| // range (i.e., skip PReg allocations in the BTree that |
| // are completely before this bundle range). |
| |
| if preg_range_iter.peek().is_some() && *preg_range_iter.peek().unwrap().0 < key { |
| trace!( |
| "Skipping PReg range {:?}", |
| preg_range_iter.peek().unwrap().0 |
| ); |
| preg_range_iter.next(); |
| skips += 1; |
| if skips >= 16 { |
| let from_pos = entry.range.from; |
| let from_key = LiveRangeKey::from_range(&CodeRange { |
| from: from_pos, |
| to: from_pos, |
| }); |
| preg_range_iter = self.pregs[reg.index()] |
| .allocations |
| .btree |
| .range(from_key..) |
| .peekable(); |
| skips = 0; |
| } |
| continue 'alloc; |
| } |
| skips = 0; |
| |
| // If there are no more PReg allocations, we're done! |
| if preg_range_iter.peek().is_none() { |
| trace!(" -> no more PReg allocations; so no conflict possible!"); |
| break 'ranges; |
| } |
| |
| // If the current PReg range is beyond this range, there is no conflict; continue. |
| if *preg_range_iter.peek().unwrap().0 > key { |
| trace!( |
| " -> next PReg allocation is at {:?}; moving to next VReg range", |
| preg_range_iter.peek().unwrap().0 |
| ); |
| break 'alloc; |
| } |
| |
| // Otherwise, there is a conflict. |
| let preg_key = *preg_range_iter.peek().unwrap().0; |
| debug_assert_eq!(preg_key, key); // Assert that this range overlaps. |
| let preg_range = preg_range_iter.next().unwrap().1; |
| |
| trace!(" -> btree contains range {:?} that overlaps", preg_range); |
| if preg_range.is_valid() { |
| trace!(" -> from vreg {:?}", self.ranges[preg_range.index()].vreg); |
| // range from an allocated bundle: find the bundle and add to |
| // conflicts list. |
| let conflict_bundle = self.ranges[preg_range.index()].bundle; |
| trace!(" -> conflict bundle {:?}", conflict_bundle); |
| if self.conflict_set.insert(conflict_bundle) { |
| conflicts.push(conflict_bundle); |
| max_conflict_weight = std::cmp::max( |
| max_conflict_weight, |
| self.bundles[conflict_bundle.index()].cached_spill_weight(), |
| ); |
| if max_allowable_cost.is_some() |
| && max_conflict_weight > max_allowable_cost.unwrap() |
| { |
| trace!(" -> reached high cost, retrying early"); |
| return AllocRegResult::ConflictHighCost; |
| } |
| } |
| |
| if first_conflict.is_none() { |
| first_conflict = Some(ProgPoint::from_index(std::cmp::max( |
| preg_key.from, |
| key.from, |
| ))); |
| } |
| } else { |
| trace!(" -> conflict with fixed reservation"); |
| // range from a direct use of the PReg (due to clobber). |
| return AllocRegResult::ConflictWithFixed( |
| max_conflict_weight, |
| ProgPoint::from_index(preg_key.from), |
| ); |
| } |
| } |
| } |
| |
| if conflicts.len() > 0 { |
| return AllocRegResult::Conflict(conflicts, first_conflict.unwrap()); |
| } |
| |
| // We can allocate! Add our ranges to the preg's BTree. |
| let preg = PReg::from_index(reg.index()); |
| trace!(" -> bundle {:?} assigned to preg {:?}", bundle, preg); |
| self.bundles[bundle.index()].allocation = Allocation::reg(preg); |
| for entry in &self.bundles[bundle.index()].ranges { |
| self.pregs[reg.index()] |
| .allocations |
| .btree |
| .insert(LiveRangeKey::from_range(&entry.range), entry.index); |
| } |
| |
| AllocRegResult::Allocated(Allocation::reg(preg)) |
| } |
| |
| pub fn evict_bundle(&mut self, bundle: LiveBundleIndex) { |
| trace!( |
| "evicting bundle {:?}: alloc {:?}", |
| bundle, |
| self.bundles[bundle.index()].allocation |
| ); |
| let preg = match self.bundles[bundle.index()].allocation.as_reg() { |
| Some(preg) => preg, |
| None => { |
| trace!( |
| " -> has no allocation! {:?}", |
| self.bundles[bundle.index()].allocation |
| ); |
| return; |
| } |
| }; |
| let preg_idx = PRegIndex::new(preg.index()); |
| self.bundles[bundle.index()].allocation = Allocation::none(); |
| for entry in &self.bundles[bundle.index()].ranges { |
| trace!(" -> removing LR {:?} from reg {:?}", entry.index, preg_idx); |
| self.pregs[preg_idx.index()] |
| .allocations |
| .btree |
| .remove(&LiveRangeKey::from_range(&entry.range)); |
| } |
| let prio = self.bundles[bundle.index()].prio; |
| trace!(" -> prio {}; back into queue", prio); |
| self.allocation_queue |
| .insert(bundle, prio as usize, PReg::invalid()); |
| } |
| |
| pub fn bundle_spill_weight(&self, bundle: LiveBundleIndex) -> u32 { |
| self.bundles[bundle.index()].cached_spill_weight() |
| } |
| |
| pub fn maximum_spill_weight_in_bundle_set(&self, bundles: &LiveBundleVec) -> u32 { |
| trace!("maximum_spill_weight_in_bundle_set: {:?}", bundles); |
| let m = bundles |
| .iter() |
| .map(|&b| { |
| let w = self.bundles[b.index()].cached_spill_weight(); |
| trace!("bundle{}: {}", b.index(), w); |
| w |
| }) |
| .max() |
| .unwrap_or(0); |
| trace!(" -> max: {}", m); |
| m |
| } |
| |
| pub fn recompute_bundle_properties(&mut self, bundle: LiveBundleIndex) { |
| trace!("recompute bundle properties: bundle {:?}", bundle); |
| |
| let minimal; |
| let mut fixed = false; |
| let mut fixed_def = false; |
| let mut stack = false; |
| let bundledata = &self.bundles[bundle.index()]; |
| let first_range = bundledata.ranges[0].index; |
| let first_range_data = &self.ranges[first_range.index()]; |
| |
| self.bundles[bundle.index()].prio = self.compute_bundle_prio(bundle); |
| |
| if first_range_data.vreg.is_invalid() { |
| trace!(" -> no vreg; minimal and fixed"); |
| minimal = true; |
| fixed = true; |
| } else { |
| for u in &first_range_data.uses { |
| trace!(" -> use: {:?}", u); |
| if let OperandConstraint::FixedReg(_) = u.operand.constraint() { |
| trace!(" -> fixed operand at {:?}: {:?}", u.pos, u.operand); |
| fixed = true; |
| if u.operand.kind() == OperandKind::Def { |
| trace!(" -> is fixed def"); |
| fixed_def = true; |
| } |
| } |
| if let OperandConstraint::Stack = u.operand.constraint() { |
| trace!(" -> stack operand at {:?}: {:?}", u.pos, u.operand); |
| stack = true; |
| } |
| if stack && fixed { |
| break; |
| } |
| } |
| // Minimal if the range covers only one instruction. Note |
| // that it could cover just one ProgPoint, |
| // i.e. X.Before..X.After, or two ProgPoints, |
| // i.e. X.Before..X+1.Before. |
| trace!(" -> first range has range {:?}", first_range_data.range); |
| let bundle_start = self.bundles[bundle.index()] |
| .ranges |
| .first() |
| .unwrap() |
| .range |
| .from; |
| let bundle_end = self.bundles[bundle.index()].ranges.last().unwrap().range.to; |
| minimal = bundle_start.inst() == bundle_end.prev().inst(); |
| trace!(" -> minimal: {}", minimal); |
| } |
| |
| let spill_weight = if minimal { |
| if fixed { |
| trace!(" -> fixed and minimal"); |
| MINIMAL_FIXED_BUNDLE_SPILL_WEIGHT |
| } else { |
| trace!(" -> non-fixed and minimal"); |
| MINIMAL_BUNDLE_SPILL_WEIGHT |
| } |
| } else { |
| let mut total = SpillWeight::zero(); |
| for entry in &self.bundles[bundle.index()].ranges { |
| let range_data = &self.ranges[entry.index.index()]; |
| trace!( |
| " -> uses spill weight: +{:?}", |
| range_data.uses_spill_weight() |
| ); |
| total = total + range_data.uses_spill_weight(); |
| } |
| |
| if self.bundles[bundle.index()].prio > 0 { |
| let final_weight = (total.to_f32() as u32) / self.bundles[bundle.index()].prio; |
| trace!( |
| " -> dividing by prio {}; final weight {}", |
| self.bundles[bundle.index()].prio, |
| final_weight |
| ); |
| std::cmp::min(BUNDLE_MAX_NORMAL_SPILL_WEIGHT, final_weight) |
| } else { |
| 0 |
| } |
| }; |
| |
| self.bundles[bundle.index()].set_cached_spill_weight_and_props( |
| spill_weight, |
| minimal, |
| fixed, |
| fixed_def, |
| stack, |
| ); |
| } |
| |
| pub fn minimal_bundle(&self, bundle: LiveBundleIndex) -> bool { |
| self.bundles[bundle.index()].cached_minimal() |
| } |
| |
| pub fn recompute_range_properties(&mut self, range: LiveRangeIndex) { |
| let rangedata = &mut self.ranges[range.index()]; |
| let mut w = SpillWeight::zero(); |
| for u in &rangedata.uses { |
| w = w + SpillWeight::from_bits(u.weight); |
| trace!("range{}: use {:?}", range.index(), u); |
| } |
| rangedata.set_uses_spill_weight(w); |
| if rangedata.uses.len() > 0 && rangedata.uses[0].operand.kind() == OperandKind::Def { |
| // Note that we *set* the flag here, but we never *clear* |
| // it: it may be set by a progmove as well (which does not |
| // create an explicit use or def), and we want to preserve |
| // that. We will never split or trim ranges in a way that |
| // removes a def at the front and requires the flag to be |
| // cleared. |
| rangedata.set_flag(LiveRangeFlag::StartsAtDef); |
| } |
| } |
| |
| pub fn get_or_create_spill_bundle( |
| &mut self, |
| bundle: LiveBundleIndex, |
| create_if_absent: bool, |
| ) -> Option<LiveBundleIndex> { |
| let ssidx = self.bundles[bundle.index()].spillset; |
| let idx = self.spillsets[ssidx.index()].spill_bundle; |
| if idx.is_valid() { |
| Some(idx) |
| } else if create_if_absent { |
| let idx = self.create_bundle(); |
| self.spillsets[ssidx.index()].spill_bundle = idx; |
| self.bundles[idx.index()].spillset = ssidx; |
| self.spilled_bundles.push(idx); |
| Some(idx) |
| } else { |
| None |
| } |
| } |
| |
| pub fn split_and_requeue_bundle( |
| &mut self, |
| bundle: LiveBundleIndex, |
| mut split_at: ProgPoint, |
| reg_hint: PReg, |
| // Do we trim the parts around the split and put them in the |
| // spill bundle? |
| trim_ends_into_spill_bundle: bool, |
| ) { |
| self.stats.splits += 1; |
| trace!( |
| "split bundle {:?} at {:?} and requeue with reg hint (for first part) {:?}", |
| bundle, |
| split_at, |
| reg_hint, |
| ); |
| |
| // Split `bundle` at `split_at`, creating new LiveRanges and |
| // bundles (and updating vregs' linked lists appropriately), |
| // and enqueue the new bundles. |
| |
| let spillset = self.bundles[bundle.index()].spillset; |
| |
| // Have we reached the maximum split count? If so, fall back |
| // to a "minimal bundles and spill bundle" setup for this |
| // bundle. See the doc-comment on |
| // `split_into_minimal_bundles()` above for more. |
| if self.spillsets[spillset.index()].splits >= MAX_SPLITS_PER_SPILLSET { |
| self.split_into_minimal_bundles(bundle, reg_hint); |
| return; |
| } |
| self.spillsets[spillset.index()].splits += 1; |
| |
| debug_assert!(!self.bundles[bundle.index()].ranges.is_empty()); |
| // Split point *at* start is OK; this means we peel off |
| // exactly one use to create a minimal bundle. |
| let bundle_start = self.bundles[bundle.index()] |
| .ranges |
| .first() |
| .unwrap() |
| .range |
| .from; |
| debug_assert!(split_at >= bundle_start); |
| let bundle_end = self.bundles[bundle.index()].ranges.last().unwrap().range.to; |
| debug_assert!(split_at < bundle_end); |
| |
| // Is the split point *at* the start? If so, peel off the |
| // first use: set the split point just after it, or just |
| // before it if it comes after the start of the bundle. |
| if split_at == bundle_start { |
| // Find any uses; if none, just chop off one instruction. |
| let mut first_use = None; |
| 'outer: for entry in &self.bundles[bundle.index()].ranges { |
| for u in &self.ranges[entry.index.index()].uses { |
| first_use = Some(u.pos); |
| break 'outer; |
| } |
| } |
| trace!(" -> first use loc is {:?}", first_use); |
| split_at = match first_use { |
| Some(pos) => { |
| if pos.inst() == bundle_start.inst() { |
| ProgPoint::before(pos.inst().next()) |
| } else { |
| ProgPoint::before(pos.inst()) |
| } |
| } |
| None => ProgPoint::before( |
| self.bundles[bundle.index()] |
| .ranges |
| .first() |
| .unwrap() |
| .range |
| .from |
| .inst() |
| .next(), |
| ), |
| }; |
| trace!( |
| "split point is at bundle start; advancing to {:?}", |
| split_at |
| ); |
| } else { |
| // Don't split in the middle of an instruction -- this could |
| // create impossible moves (we cannot insert a move between an |
| // instruction's uses and defs). |
| if split_at.pos() == InstPosition::After { |
| split_at = split_at.next(); |
| } |
| if split_at >= bundle_end { |
| split_at = split_at.prev().prev(); |
| } |
| } |
| |
| debug_assert!(split_at > bundle_start && split_at < bundle_end); |
| |
| // We need to find which LRs fall on each side of the split, |
| // which LR we need to split down the middle, then update the |
| // current bundle, create a new one, and (re)-queue both. |
| |
| trace!(" -> LRs: {:?}", self.bundles[bundle.index()].ranges); |
| |
| let mut last_lr_in_old_bundle_idx = 0; // last LR-list index in old bundle |
| let mut first_lr_in_new_bundle_idx = 0; // first LR-list index in new bundle |
| for (i, entry) in self.bundles[bundle.index()].ranges.iter().enumerate() { |
| if split_at > entry.range.from { |
| last_lr_in_old_bundle_idx = i; |
| first_lr_in_new_bundle_idx = i; |
| } |
| if split_at < entry.range.to { |
| first_lr_in_new_bundle_idx = i; |
| break; |
| } |
| } |
| |
| trace!( |
| " -> last LR in old bundle: LR {:?}", |
| self.bundles[bundle.index()].ranges[last_lr_in_old_bundle_idx] |
| ); |
| trace!( |
| " -> first LR in new bundle: LR {:?}", |
| self.bundles[bundle.index()].ranges[first_lr_in_new_bundle_idx] |
| ); |
| |
| // Take the sublist of LRs that will go in the new bundle. |
| let mut new_lr_list: LiveRangeList = self.bundles[bundle.index()] |
| .ranges |
| .iter() |
| .cloned() |
| .skip(first_lr_in_new_bundle_idx) |
| .collect(); |
| self.bundles[bundle.index()] |
| .ranges |
| .truncate(last_lr_in_old_bundle_idx + 1); |
| self.bundles[bundle.index()].ranges.shrink_to_fit(); |
| |
| // If the first entry in `new_lr_list` is a LR that is split |
| // down the middle, replace it with a new LR and chop off the |
| // end of the same LR in the original list. |
| if split_at > new_lr_list[0].range.from { |
| debug_assert_eq!(last_lr_in_old_bundle_idx, first_lr_in_new_bundle_idx); |
| let orig_lr = new_lr_list[0].index; |
| let new_lr = self.create_liverange(CodeRange { |
| from: split_at, |
| to: new_lr_list[0].range.to, |
| }); |
| self.ranges[new_lr.index()].vreg = self.ranges[orig_lr.index()].vreg; |
| trace!(" -> splitting LR {:?} into {:?}", orig_lr, new_lr); |
| let first_use = self.ranges[orig_lr.index()] |
| .uses |
| .iter() |
| .position(|u| u.pos >= split_at) |
| .unwrap_or(self.ranges[orig_lr.index()].uses.len()); |
| let rest_uses: UseList = self.ranges[orig_lr.index()] |
| .uses |
| .iter() |
| .cloned() |
| .skip(first_use) |
| .collect(); |
| self.ranges[new_lr.index()].uses = rest_uses; |
| self.ranges[orig_lr.index()].uses.truncate(first_use); |
| self.ranges[orig_lr.index()].uses.shrink_to_fit(); |
| self.recompute_range_properties(orig_lr); |
| self.recompute_range_properties(new_lr); |
| new_lr_list[0].index = new_lr; |
| new_lr_list[0].range = self.ranges[new_lr.index()].range; |
| self.ranges[orig_lr.index()].range.to = split_at; |
| self.bundles[bundle.index()].ranges[last_lr_in_old_bundle_idx].range = |
| self.ranges[orig_lr.index()].range; |
| |
| // Perform a lazy split in the VReg data. We just |
| // append the new LR and its range; we will sort by |
| // start of range, and fix up range ends, once when we |
| // iterate over the VReg's ranges after allocation |
| // completes (this is the only time when order |
| // matters). |
| self.vregs[self.ranges[new_lr.index()].vreg.index()] |
| .ranges |
| .push(LiveRangeListEntry { |
| range: self.ranges[new_lr.index()].range, |
| index: new_lr, |
| }); |
| } |
| |
| let new_bundle = self.create_bundle(); |
| trace!(" -> creating new bundle {:?}", new_bundle); |
| self.bundles[new_bundle.index()].spillset = spillset; |
| for entry in &new_lr_list { |
| self.ranges[entry.index.index()].bundle = new_bundle; |
| } |
| self.bundles[new_bundle.index()].ranges = new_lr_list; |
| |
| if trim_ends_into_spill_bundle { |
| // Finally, handle moving LRs to the spill bundle when |
| // appropriate: If the first range in `new_bundle` or last |
| // range in `bundle` has "empty space" beyond the first or |
| // last use (respectively), trim it and put an empty LR into |
| // the spill bundle. (We are careful to treat the "starts at |
| // def" flag as an implicit first def even if no def-type Use |
| // is present.) |
| while let Some(entry) = self.bundles[bundle.index()].ranges.last().cloned() { |
| let end = entry.range.to; |
| let vreg = self.ranges[entry.index.index()].vreg; |
| let last_use = self.ranges[entry.index.index()].uses.last().map(|u| u.pos); |
| if last_use.is_none() { |
| let spill = self |
| .get_or_create_spill_bundle(bundle, /* create_if_absent = */ true) |
| .unwrap(); |
| trace!( |
| " -> bundle {:?} range {:?}: no uses; moving to spill bundle {:?}", |
| bundle, |
| entry.index, |
| spill |
| ); |
| self.bundles[spill.index()].ranges.push(entry); |
| self.bundles[bundle.index()].ranges.pop(); |
| self.ranges[entry.index.index()].bundle = spill; |
| continue; |
| } |
| let last_use = last_use.unwrap(); |
| let split = ProgPoint::before(last_use.inst().next()); |
| if split < end { |
| let spill = self |
| .get_or_create_spill_bundle(bundle, /* create_if_absent = */ true) |
| .unwrap(); |
| self.bundles[bundle.index()] |
| .ranges |
| .last_mut() |
| .unwrap() |
| .range |
| .to = split; |
| self.ranges[self.bundles[bundle.index()] |
| .ranges |
| .last() |
| .unwrap() |
| .index |
| .index()] |
| .range |
| .to = split; |
| let range = CodeRange { |
| from: split, |
| to: end, |
| }; |
| let empty_lr = self.create_liverange(range); |
| self.bundles[spill.index()].ranges.push(LiveRangeListEntry { |
| range, |
| index: empty_lr, |
| }); |
| self.ranges[empty_lr.index()].bundle = spill; |
| self.vregs[vreg.index()].ranges.push(LiveRangeListEntry { |
| range, |
| index: empty_lr, |
| }); |
| trace!( |
| " -> bundle {:?} range {:?}: last use implies split point {:?}", |
| bundle, |
| entry.index, |
| split |
| ); |
| trace!( |
| " -> moving trailing empty region to new spill bundle {:?} with new LR {:?}", |
| spill, |
| empty_lr |
| ); |
| } |
| break; |
| } |
| while let Some(entry) = self.bundles[new_bundle.index()].ranges.first().cloned() { |
| if self.ranges[entry.index.index()].has_flag(LiveRangeFlag::StartsAtDef) { |
| break; |
| } |
| let start = entry.range.from; |
| let vreg = self.ranges[entry.index.index()].vreg; |
| let first_use = self.ranges[entry.index.index()].uses.first().map(|u| u.pos); |
| if first_use.is_none() { |
| let spill = self |
| .get_or_create_spill_bundle(new_bundle, /* create_if_absent = */ true) |
| .unwrap(); |
| trace!( |
| " -> bundle {:?} range {:?}: no uses; moving to spill bundle {:?}", |
| new_bundle, |
| entry.index, |
| spill |
| ); |
| self.bundles[spill.index()].ranges.push(entry); |
| self.bundles[new_bundle.index()].ranges.drain(..1); |
| self.ranges[entry.index.index()].bundle = spill; |
| continue; |
| } |
| let first_use = first_use.unwrap(); |
| let split = ProgPoint::before(first_use.inst()); |
| if split > start { |
| let spill = self |
| .get_or_create_spill_bundle(new_bundle, /* create_if_absent = */ true) |
| .unwrap(); |
| self.bundles[new_bundle.index()] |
| .ranges |
| .first_mut() |
| .unwrap() |
| .range |
| .from = split; |
| self.ranges[self.bundles[new_bundle.index()] |
| .ranges |
| .first() |
| .unwrap() |
| .index |
| .index()] |
| .range |
| .from = split; |
| let range = CodeRange { |
| from: start, |
| to: split, |
| }; |
| let empty_lr = self.create_liverange(range); |
| self.bundles[spill.index()].ranges.push(LiveRangeListEntry { |
| range, |
| index: empty_lr, |
| }); |
| self.ranges[empty_lr.index()].bundle = spill; |
| self.vregs[vreg.index()].ranges.push(LiveRangeListEntry { |
| range, |
| index: empty_lr, |
| }); |
| trace!( |
| " -> bundle {:?} range {:?}: first use implies split point {:?}", |
| bundle, |
| entry.index, |
| first_use, |
| ); |
| trace!( |
| " -> moving leading empty region to new spill bundle {:?} with new LR {:?}", |
| spill, |
| empty_lr |
| ); |
| } |
| break; |
| } |
| } |
| |
| if self.bundles[bundle.index()].ranges.len() > 0 { |
| self.recompute_bundle_properties(bundle); |
| let prio = self.bundles[bundle.index()].prio; |
| self.allocation_queue |
| .insert(bundle, prio as usize, reg_hint); |
| } |
| if self.bundles[new_bundle.index()].ranges.len() > 0 { |
| self.recompute_bundle_properties(new_bundle); |
| let prio = self.bundles[new_bundle.index()].prio; |
| self.allocation_queue |
| .insert(new_bundle, prio as usize, reg_hint); |
| } |
| } |
| |
| /// Splits the given bundle into minimal bundles per Use, falling |
| /// back onto the spill bundle. This must work for any bundle no |
| /// matter how many conflicts. |
| /// |
| /// This is meant to solve a quadratic-cost problem that exists |
| /// with "normal" splitting as implemented above. With that |
| /// procedure, , splitting a bundle produces two |
| /// halves. Furthermore, it has cost linear in the length of the |
| /// bundle, because the resulting half-bundles have their |
| /// requirements recomputed with a new scan, and because we copy |
| /// half the use-list over to the tail end sub-bundle. |
| /// |
| /// This works fine when a bundle has a handful of splits overall, |
| /// but not when an input has a systematic pattern of conflicts |
| /// that will require O(|bundle|) splits (e.g., every Use is |
| /// constrained to a different fixed register than the last |
| /// one). In such a case, we get quadratic behavior. |
| /// |
| /// This method implements a direct split into minimal bundles |
| /// along the whole length of the bundle, putting the regions |
| /// without uses in the spill bundle. We do this once the number |
| /// of splits in an original bundle (tracked by spillset) reaches |
| /// a pre-determined limit. |
| /// |
| /// This basically approximates what a non-splitting allocator |
| /// would do: it "spills" the whole bundle to possibly a |
| /// stackslot, or a second-chance register allocation at best, via |
| /// the spill bundle; and then does minimal reservations of |
| /// registers just at uses/defs and moves the "spilled" value |
| /// into/out of them immediately. |
| pub fn split_into_minimal_bundles(&mut self, bundle: LiveBundleIndex, reg_hint: PReg) { |
| let mut removed_lrs: FxHashSet<LiveRangeIndex> = FxHashSet::default(); |
| let mut removed_lrs_vregs: FxHashSet<VRegIndex> = FxHashSet::default(); |
| let mut new_lrs: SmallVec<[(VRegIndex, LiveRangeIndex); 16]> = smallvec![]; |
| let mut new_bundles: SmallVec<[LiveBundleIndex; 16]> = smallvec![]; |
| |
| let spill = self |
| .get_or_create_spill_bundle(bundle, /* create_if_absent = */ true) |
| .unwrap(); |
| |
| trace!( |
| "Splitting bundle {:?} into minimal bundles with reg hint {}", |
| bundle, |
| reg_hint |
| ); |
| |
| let mut last_lr: Option<LiveRangeIndex> = None; |
| let mut last_bundle: Option<LiveBundleIndex> = None; |
| let mut last_inst: Option<Inst> = None; |
| let mut last_vreg: Option<VRegIndex> = None; |
| |
| for entry_idx in 0..self.bundles[bundle.index()].ranges.len() { |
| // Iterate manually; don't borrow `self`. |
| let entry = self.bundles[bundle.index()].ranges[entry_idx]; |
| let lr_from = entry.range.from; |
| let lr_to = entry.range.to; |
| |
| removed_lrs.insert(entry.index); |
| let vreg = self.ranges[entry.index.index()].vreg; |
| removed_lrs_vregs.insert(vreg); |
| trace!(" -> removing old LR {:?} for vreg {:?}", entry.index, vreg); |
| |
| let mut last_live_pos = entry.range.from; |
| for use_idx in 0..self.ranges[entry.index.index()].uses.len() { |
| let u = self.ranges[entry.index.index()].uses[use_idx]; |
| trace!(" -> use {:?} (last_live_pos {:?})", u, last_live_pos); |
| |
| // If we just created a LR for this inst at the last |
| // pos, add this use to the same LR. |
| if Some(u.pos.inst()) == last_inst && Some(vreg) == last_vreg { |
| self.ranges[last_lr.unwrap().index()].uses.push(u); |
| trace!(" -> appended to last LR {:?}", last_lr.unwrap()); |
| continue; |
| } |
| |
| // The minimal bundle runs through the whole inst |
| // (up to the Before of the next inst), *unless* |
| // the original LR was only over the Before (up to |
| // the After) of this inst. |
| let to = std::cmp::min(ProgPoint::before(u.pos.inst().next()), lr_to); |
| |
| // If the last bundle was at the same inst, add a new |
| // LR to the same bundle; otherwise, create a LR and a |
| // new bundle. |
| if Some(u.pos.inst()) == last_inst { |
| let cr = CodeRange { from: u.pos, to }; |
| let lr = self.create_liverange(cr); |
| new_lrs.push((vreg, lr)); |
| self.ranges[lr.index()].uses.push(u); |
| self.ranges[lr.index()].vreg = vreg; |
| |
| trace!( |
| " -> created new LR {:?} but adding to existing bundle {:?}", |
| lr, |
| last_bundle.unwrap() |
| ); |
| // Edit the previous LR to end mid-inst. |
| self.bundles[last_bundle.unwrap().index()] |
| .ranges |
| .last_mut() |
| .unwrap() |
| .range |
| .to = u.pos; |
| self.ranges[last_lr.unwrap().index()].range.to = u.pos; |
| // Add this LR to the bundle. |
| self.bundles[last_bundle.unwrap().index()] |
| .ranges |
| .push(LiveRangeListEntry { |
| range: cr, |
| index: lr, |
| }); |
| self.ranges[lr.index()].bundle = last_bundle.unwrap(); |
| last_live_pos = ProgPoint::before(u.pos.inst().next()); |
| continue; |
| } |
| |
| // Otherwise, create a new LR. |
| let pos = ProgPoint::before(u.pos.inst()); |
| let pos = std::cmp::max(lr_from, pos); |
| let cr = CodeRange { from: pos, to }; |
| let lr = self.create_liverange(cr); |
| new_lrs.push((vreg, lr)); |
| self.ranges[lr.index()].uses.push(u); |
| self.ranges[lr.index()].vreg = vreg; |
| |
| // Create a new bundle that contains only this LR. |
| let new_bundle = self.create_bundle(); |
| self.ranges[lr.index()].bundle = new_bundle; |
| self.bundles[new_bundle.index()].spillset = self.bundles[bundle.index()].spillset; |
| self.bundles[new_bundle.index()] |
| .ranges |
| .push(LiveRangeListEntry { |
| range: cr, |
| index: lr, |
| }); |
| new_bundles.push(new_bundle); |
| |
| // If this use was a Def, set the StartsAtDef flag for |
| // the new LR. (N.B.: *not* Mod, only Def, because Mod |
| // needs an input. This flag specifically indicates |
| // that the LR does not require the value to be moved |
| // into location at start because it (re)defines the |
| // value.) |
| if u.operand.kind() == OperandKind::Def { |
| self.ranges[lr.index()].set_flag(LiveRangeFlag::StartsAtDef); |
| } |
| |
| trace!( |
| " -> created new LR {:?} range {:?} with new bundle {:?} for this use", |
| lr, |
| cr, |
| new_bundle |
| ); |
| |
| // If there was any intervening range in the LR not |
| // covered by the minimal new LR above, add it to the |
| // spillset. |
| if pos > last_live_pos { |
| let cr = CodeRange { |
| from: last_live_pos, |
| to: pos, |
| }; |
| let spill_lr = self.create_liverange(cr); |
| self.ranges[spill_lr.index()].vreg = vreg; |
| self.ranges[spill_lr.index()].bundle = spill; |
| new_lrs.push((vreg, spill_lr)); |
| self.bundles[spill.index()].ranges.push(LiveRangeListEntry { |
| range: cr, |
| index: spill_lr, |
| }); |
| self.ranges[spill_lr.index()].bundle = spill; |
| trace!( |
| " -> put intervening range {:?} in new LR {:?} in spill bundle {:?}", |
| cr, |
| spill_lr, |
| spill |
| ); |
| } |
| last_live_pos = ProgPoint::before(u.pos.inst().next()); |
| |
| last_lr = Some(lr); |
| last_bundle = Some(new_bundle); |
| last_inst = Some(u.pos.inst()); |
| last_vreg = Some(vreg); |
| } |
| |
| // Clear the use-list from the original LR. |
| self.ranges[entry.index.index()].uses = Default::default(); |
| |
| // If there is space from the last use to the end of the |
| // LR, put that in the spill bundle too. |
| if entry.range.to > last_live_pos { |
| let cr = CodeRange { |
| from: last_live_pos, |
| to: entry.range.to, |
| }; |
| let spill_lr = self.create_liverange(cr); |
| self.ranges[spill_lr.index()].vreg = vreg; |
| self.ranges[spill_lr.index()].bundle = spill; |
| new_lrs.push((vreg, spill_lr)); |
| self.bundles[spill.index()].ranges.push(LiveRangeListEntry { |
| range: cr, |
| index: spill_lr, |
| }); |
| self.ranges[spill_lr.index()].bundle = spill; |
| trace!( |
| " -> put trailing range {:?} in new LR {:?} in spill bundle {:?}", |
| cr, |
| spill_lr, |
| spill |
| ); |
| } |
| } |
| |
| // Clear the LR list in the original bundle. |
| self.bundles[bundle.index()].ranges.clear(); |
| self.bundles[bundle.index()].ranges.shrink_to_fit(); |
| |
| // Remove all of the removed LRs from respective vregs' lists. |
| for vreg in removed_lrs_vregs { |
| self.vregs[vreg.index()] |
| .ranges |
| .retain(|entry| !removed_lrs.contains(&entry.index)); |
| } |
| |
| // Add the new LRs to their respective vreg lists. |
| for (vreg, lr) in new_lrs { |
| let range = self.ranges[lr.index()].range; |
| let entry = LiveRangeListEntry { range, index: lr }; |
| self.vregs[vreg.index()].ranges.push(entry); |
| } |
| |
| // Recompute bundle properties for all new bundles and enqueue |
| // them. |
| for bundle in new_bundles { |
| if self.bundles[bundle.index()].ranges.len() > 0 { |
| self.recompute_bundle_properties(bundle); |
| let prio = self.bundles[bundle.index()].prio; |
| self.allocation_queue |
| .insert(bundle, prio as usize, reg_hint); |
| } |
| } |
| } |
| |
| pub fn process_bundle( |
| &mut self, |
| bundle: LiveBundleIndex, |
| reg_hint: PReg, |
| ) -> Result<(), RegAllocError> { |
| let class = self.spillsets[self.bundles[bundle.index()].spillset.index()].class; |
| // Grab a hint from either the queue or our spillset, if any. |
| let mut hint_reg = if reg_hint != PReg::invalid() { |
| reg_hint |
| } else { |
| self.spillsets[self.bundles[bundle.index()].spillset.index()].reg_hint |
| }; |
| if self.pregs[hint_reg.index()].is_stack { |
| hint_reg = PReg::invalid(); |
| } |
| trace!("process_bundle: bundle {:?} hint {:?}", bundle, hint_reg,); |
| |
| let req = match self.compute_requirement(bundle) { |
| Ok(req) => req, |
| Err(conflict) => { |
| // We have to split right away. We'll find a point to |
| // split that would allow at least the first half of the |
| // split to be conflict-free. |
| debug_assert!( |
| !self.minimal_bundle(bundle), |
| "Minimal bundle with conflict!" |
| ); |
| self.split_and_requeue_bundle( |
| bundle, |
| /* split_at_point = */ conflict.suggested_split_point(), |
| reg_hint, |
| /* trim_ends_into_spill_bundle = */ |
| conflict.should_trim_edges_around_split(), |
| ); |
| return Ok(()); |
| } |
| }; |
| |
| // If no requirement at all (because no uses), and *if* a |
| // spill bundle is already present, then move the LRs over to |
| // the spill bundle right away. |
| match req { |
| Requirement::Any => { |
| if let Some(spill) = |
| self.get_or_create_spill_bundle(bundle, /* create_if_absent = */ false) |
| { |
| let mut list = |
| std::mem::replace(&mut self.bundles[bundle.index()].ranges, smallvec![]); |
| for entry in &list { |
| self.ranges[entry.index.index()].bundle = spill; |
| } |
| self.bundles[spill.index()].ranges.extend(list.drain(..)); |
| return Ok(()); |
| } |
| } |
| _ => {} |
| } |
| |
| // Try to allocate! |
| let mut attempts = 0; |
| loop { |
| attempts += 1; |
| trace!("attempt {}, req {:?}", attempts, req); |
| debug_assert!(attempts < 100 * self.func.num_insts()); |
| |
| let fixed_preg = match req { |
| Requirement::FixedReg(preg) | Requirement::FixedStack(preg) => Some(preg), |
| Requirement::Register => None, |
| Requirement::Stack => { |
| // If we must be on the stack, mark our spillset |
| // as required immediately. |
| self.spillsets[self.bundles[bundle.index()].spillset.index()].required = true; |
| return Ok(()); |
| } |
| |
| Requirement::Any => { |
| self.spilled_bundles.push(bundle); |
| return Ok(()); |
| } |
| }; |
| // Scan all pregs, or the one fixed preg, and attempt to allocate. |
| |
| let mut lowest_cost_evict_conflict_set: Option<LiveBundleVec> = None; |
| let mut lowest_cost_evict_conflict_cost: Option<u32> = None; |
| |
| let mut lowest_cost_split_conflict_cost: Option<u32> = None; |
| let mut lowest_cost_split_conflict_point = ProgPoint::before(Inst::new(0)); |
| let mut lowest_cost_split_conflict_reg = PReg::invalid(); |
| |
| // Heuristic: start the scan for an available |
| // register at an offset influenced both by our |
| // location in the code and by the bundle we're |
| // considering. This has the effect of spreading |
| // demand more evenly across registers. |
| let scan_offset = self.ranges[self.bundles[bundle.index()].ranges[0].index.index()] |
| .range |
| .from |
| .inst() |
| .index() |
| + bundle.index(); |
| |
| self.stats.process_bundle_reg_probe_start_any += 1; |
| for preg in RegTraversalIter::new( |
| self.env, |
| class, |
| hint_reg, |
| PReg::invalid(), |
| scan_offset, |
| fixed_preg, |
| ) { |
| self.stats.process_bundle_reg_probes_any += 1; |
| let preg_idx = PRegIndex::new(preg.index()); |
| trace!("trying preg {:?}", preg_idx); |
| |
| let scan_limit_cost = match ( |
| lowest_cost_evict_conflict_cost, |
| lowest_cost_split_conflict_cost, |
| ) { |
| (Some(a), Some(b)) => Some(std::cmp::max(a, b)), |
| _ => None, |
| }; |
| match self.try_to_allocate_bundle_to_reg(bundle, preg_idx, scan_limit_cost) { |
| AllocRegResult::Allocated(alloc) => { |
| self.stats.process_bundle_reg_success_any += 1; |
| trace!(" -> allocated to any {:?}", preg_idx); |
| self.spillsets[self.bundles[bundle.index()].spillset.index()].reg_hint = |
| alloc.as_reg().unwrap(); |
| return Ok(()); |
| } |
| AllocRegResult::Conflict(bundles, first_conflict_point) => { |
| trace!( |
| " -> conflict with bundles {:?}, first conflict at {:?}", |
| bundles, |
| first_conflict_point |
| ); |
| |
| let conflict_cost = self.maximum_spill_weight_in_bundle_set(&bundles); |
| |
| if lowest_cost_evict_conflict_cost.is_none() |
| || conflict_cost < lowest_cost_evict_conflict_cost.unwrap() |
| { |
| lowest_cost_evict_conflict_cost = Some(conflict_cost); |
| lowest_cost_evict_conflict_set = Some(bundles); |
| } |
| |
| let loop_depth = self.cfginfo.approx_loop_depth |
| [self.cfginfo.insn_block[first_conflict_point.inst().index()].index()]; |
| let move_cost = spill_weight_from_constraint( |
| OperandConstraint::Reg, |
| loop_depth as usize, |
| /* is_def = */ true, |
| ) |
| .to_int(); |
| if lowest_cost_split_conflict_cost.is_none() |
| || (conflict_cost + move_cost) |
| < lowest_cost_split_conflict_cost.unwrap() |
| { |
| lowest_cost_split_conflict_cost = Some(conflict_cost + move_cost); |
| lowest_cost_split_conflict_point = first_conflict_point; |
| lowest_cost_split_conflict_reg = preg; |
| } |
| } |
| AllocRegResult::ConflictWithFixed(max_cost, point) => { |
| trace!(" -> conflict with fixed alloc; cost of other bundles up to point is {}, conflict at {:?}", max_cost, point); |
| |
| let loop_depth = self.cfginfo.approx_loop_depth |
| [self.cfginfo.insn_block[point.inst().index()].index()]; |
| let move_cost = spill_weight_from_constraint( |
| OperandConstraint::Reg, |
| loop_depth as usize, |
| /* is_def = */ true, |
| ) |
| .to_int(); |
| |
| if lowest_cost_split_conflict_cost.is_none() |
| || (max_cost + move_cost) < lowest_cost_split_conflict_cost.unwrap() |
| { |
| lowest_cost_split_conflict_cost = Some(max_cost + move_cost); |
| lowest_cost_split_conflict_point = point; |
| lowest_cost_split_conflict_reg = preg; |
| } |
| } |
| AllocRegResult::ConflictHighCost => { |
| // Simply don't consider -- we already have |
| // a lower-cost conflict bundle option |
| // to evict. |
| continue; |
| } |
| } |
| } |
| |
| // Otherwise, we *require* a register, but didn't fit into |
| // any with current bundle assignments. Hence, we will need |
| // to either split or attempt to evict some bundles. |
| |
| trace!( |
| " -> lowest cost evict: set {:?}, cost {:?}", |
| lowest_cost_evict_conflict_set, |
| lowest_cost_evict_conflict_cost, |
| ); |
| trace!( |
| " -> lowest cost split: cost {:?}, point {:?}, reg {:?}", |
| lowest_cost_split_conflict_cost, |
| lowest_cost_split_conflict_point, |
| lowest_cost_split_conflict_reg |
| ); |
| |
| // If we reach here, we *must* have an option either to split or evict. |
| debug_assert!( |
| lowest_cost_split_conflict_cost.is_some() |
| || lowest_cost_evict_conflict_cost.is_some() |
| ); |
| |
| let our_spill_weight = self.bundle_spill_weight(bundle); |
| trace!(" -> our spill weight: {}", our_spill_weight); |
| |
| // We detect the "too-many-live-registers" case here and |
| // return an error cleanly, rather than panicking, because |
| // the regalloc.rs fuzzer depends on the register |
| // allocator to correctly reject impossible-to-allocate |
| // programs in order to discard invalid test cases. |
| if self.minimal_bundle(bundle) |
| && (attempts >= 2 |
| || lowest_cost_evict_conflict_cost.is_none() |
| || lowest_cost_evict_conflict_cost.unwrap() >= our_spill_weight) |
| { |
| if let Requirement::Register = req { |
| // Check if this is a too-many-live-registers situation. |
| let range = self.bundles[bundle.index()].ranges[0].range; |
| trace!("checking for too many live regs"); |
| let mut min_bundles_assigned = 0; |
| let mut fixed_assigned = 0; |
| let mut total_regs = 0; |
| for preg in self.env.preferred_regs_by_class[class as u8 as usize] |
| .iter() |
| .chain(self.env.non_preferred_regs_by_class[class as u8 as usize].iter()) |
| { |
| trace!(" -> PR {:?}", preg); |
| let start = LiveRangeKey::from_range(&CodeRange { |
| from: range.from.prev(), |
| to: range.from.prev(), |
| }); |
| for (key, lr) in self.pregs[preg.index()].allocations.btree.range(start..) { |
| let preg_range = key.to_range(); |
| if preg_range.to <= range.from { |
| continue; |
| } |
| if preg_range.from >= range.to { |
| break; |
| } |
| if lr.is_valid() { |
| if self.minimal_bundle(self.ranges[lr.index()].bundle) { |
| trace!(" -> min bundle {:?}", lr); |
| min_bundles_assigned += 1; |
| } else { |
| trace!(" -> non-min bundle {:?}", lr); |
| } |
| } else { |
| trace!(" -> fixed bundle"); |
| fixed_assigned += 1; |
| } |
| } |
| total_regs += 1; |
| } |
| trace!( |
| " -> total {}, fixed {}, min {}", |
| total_regs, |
| fixed_assigned, |
| min_bundles_assigned |
| ); |
| if min_bundles_assigned + fixed_assigned >= total_regs { |
| return Err(RegAllocError::TooManyLiveRegs); |
| } |
| } |
| |
| panic!("Could not allocate minimal bundle, but the allocation problem should be possible to solve"); |
| } |
| |
| // If our bundle's weight is less than or equal to(*) the |
| // evict cost, choose to split. Also pick splitting if |
| // we're on our second or more attempt and we didn't |
| // allocate. Also pick splitting if the conflict set is |
| // empty, meaning a fixed conflict that can't be evicted. |
| // |
| // (*) the "equal to" part is very important: it prevents |
| // an infinite loop where two bundles with equal spill |
| // cost continually evict each other in an infinite |
| // allocation loop. In such a case, the first bundle in |
| // wins, and the other splits. |
| // |
| // Note that we don't split if the bundle is minimal. |
| if !self.minimal_bundle(bundle) |
| && (attempts >= 2 |
| || lowest_cost_evict_conflict_cost.is_none() |
| || our_spill_weight <= lowest_cost_evict_conflict_cost.unwrap()) |
| { |
| trace!( |
| " -> deciding to split: our spill weight is {}", |
| self.bundle_spill_weight(bundle) |
| ); |
| let bundle_start = self.bundles[bundle.index()].ranges[0].range.from; |
| let mut split_at_point = |
| std::cmp::max(lowest_cost_split_conflict_point, bundle_start); |
| let requeue_with_reg = lowest_cost_split_conflict_reg; |
| |
| // Adjust `split_at_point` if it is within a deeper loop |
| // than the bundle start -- hoist it to just before the |
| // first loop header it encounters. |
| let bundle_start_depth = self.cfginfo.approx_loop_depth |
| [self.cfginfo.insn_block[bundle_start.inst().index()].index()]; |
| let split_at_depth = self.cfginfo.approx_loop_depth |
| [self.cfginfo.insn_block[split_at_point.inst().index()].index()]; |
| if split_at_depth > bundle_start_depth { |
| for block in (self.cfginfo.insn_block[bundle_start.inst().index()].index() + 1) |
| ..=self.cfginfo.insn_block[split_at_point.inst().index()].index() |
| { |
| if self.cfginfo.approx_loop_depth[block] > bundle_start_depth { |
| split_at_point = self.cfginfo.block_entry[block]; |
| break; |
| } |
| } |
| } |
| |
| self.split_and_requeue_bundle( |
| bundle, |
| split_at_point, |
| requeue_with_reg, |
| /* should_trim = */ true, |
| ); |
| return Ok(()); |
| } else { |
| // Evict all bundles in `conflicting bundles` and try again. |
| self.stats.evict_bundle_event += 1; |
| for &bundle in &lowest_cost_evict_conflict_set.unwrap() { |
| trace!(" -> evicting {:?}", bundle); |
| self.evict_bundle(bundle); |
| self.stats.evict_bundle_count += 1; |
| } |
| } |
| } |
| } |
| } |
