regalloc2/ion/
spill.rs

1/*
2 * This file was initially derived from the files
3 * `js/src/jit/BacktrackingAllocator.h` and
4 * `js/src/jit/BacktrackingAllocator.cpp` in Mozilla Firefox, and was
5 * originally licensed under the Mozilla Public License 2.0. We
6 * subsequently relicensed it to Apache-2.0 WITH LLVM-exception (see
7 * https://github.com/bytecodealliance/regalloc2/issues/7).
8 *
9 * Since the initial port, the design has been substantially evolved
10 * and optimized.
11 */
12
13//! Spillslot allocation.
14
15use super::{
16    AllocRegResult, Env, LiveRangeKey, PRegIndex, RegTraversalIter, SpillSetIndex, SpillSlotData,
17    SpillSlotIndex,
18};
19use crate::{Allocation, Function, SpillSlot};
20
21impl<'a, F: Function> Env<'a, F> {
22    pub fn try_allocating_regs_for_spilled_bundles(&mut self) {
23        trace!("allocating regs for spilled bundles");
24        let mut scratch = core::mem::take(&mut self.ctx.scratch_conflicts);
25        for i in 0..self.ctx.spilled_bundles.len() {
26            let bundle = self.ctx.spilled_bundles[i]; // don't borrow self
27
28            if self.ctx.bundles[bundle].ranges.is_empty() {
29                continue;
30            }
31
32            let class = self.ctx.spillsets[self.ctx.bundles[bundle].spillset].class;
33            let hint = self.ctx.spillsets[self.ctx.bundles[bundle].spillset]
34                .hint
35                .as_valid();
36
37            // This may be an empty-range bundle whose ranges are not
38            // sorted; sort all range-lists again here.
39            self.ctx.bundles[bundle]
40                .ranges
41                .sort_unstable_by_key(|entry| entry.range.from);
42
43            let mut success = false;
44            self.ctx.output.stats.spill_bundle_reg_probes += 1;
45            let limit = self.bundles[bundle].limit.map(|l| l as usize);
46            for preg in RegTraversalIter::new(self.env, class, None, hint, bundle.index(), limit) {
47                trace!("trying bundle {:?} to preg {:?}", bundle, preg);
48                let preg_idx = PRegIndex::new(preg.index());
49                if let AllocRegResult::Allocated(_) =
50                    self.try_to_allocate_bundle_to_reg(bundle, preg_idx, None, &mut scratch)
51                {
52                    self.ctx.output.stats.spill_bundle_reg_success += 1;
53                    success = true;
54                    break;
55                }
56            }
57
58            if !success {
59                trace!(
60                    "spilling bundle {:?}: marking spillset {:?} as required",
61                    bundle,
62                    self.ctx.bundles[bundle].spillset
63                );
64                self.ctx.spillsets[self.ctx.bundles[bundle].spillset].required = true;
65            }
66        }
67        self.ctx.scratch_conflicts = scratch;
68    }
69
70    pub fn spillslot_can_fit_spillset(
71        &mut self,
72        spillslot: SpillSlotIndex,
73        spillset: SpillSetIndex,
74    ) -> bool {
75        !self.ctx.spillslots[spillslot.index()]
76            .ranges
77            .btree
78            .contains_key(&LiveRangeKey::from_range(
79                &self.ctx.spillsets[spillset].range,
80            ))
81    }
82
83    pub fn allocate_spillset_to_spillslot(
84        &mut self,
85        spillset: SpillSetIndex,
86        spillslot: SpillSlotIndex,
87    ) {
88        self.ctx.spillsets[spillset].slot = spillslot;
89
90        let res = self.ctx.spillslots[spillslot.index()].ranges.btree.insert(
91            LiveRangeKey::from_range(&self.ctx.spillsets[spillset].range),
92            spillset,
93        );
94
95        debug_assert!(res.is_none());
96    }
97
98    pub fn allocate_spillslots(&mut self) {
99        const MAX_ATTEMPTS: usize = 10;
100
101        for spillset in 0..self.ctx.spillsets.len() {
102            trace!("allocate spillslot: {}", spillset);
103            let spillset = SpillSetIndex::new(spillset);
104            if !self.ctx.spillsets[spillset].required {
105                continue;
106            }
107            let class = self.ctx.spillsets[spillset].class as usize;
108            // Try a few existing spillslots.
109            let mut i = self.ctx.slots_by_class[class].probe_start;
110            let mut success = false;
111            // Never probe the same element more than once: limit the
112            // attempt count to the number of slots in existence.
113            for _attempt in
114                0..core::cmp::min(self.ctx.slots_by_class[class].slots.len(), MAX_ATTEMPTS)
115            {
116                // Note: this indexing of `slots` is always valid
117                // because either the `slots` list is empty and the
118                // iteration limit above consequently means we don't
119                // run this loop at all, or else `probe_start` is
120                // in-bounds (because it is made so below when we add
121                // a slot, and it always takes on the last index `i`
122                // after this loop).
123                let spillslot = self.ctx.slots_by_class[class].slots[i];
124
125                if self.spillslot_can_fit_spillset(spillslot, spillset) {
126                    self.allocate_spillset_to_spillslot(spillset, spillslot);
127                    success = true;
128                    self.ctx.slots_by_class[class].probe_start = i;
129                    break;
130                }
131
132                i = self.ctx.slots_by_class[class].next_index(i);
133            }
134
135            if !success {
136                // Allocate a new spillslot.
137                let spillslot = SpillSlotIndex::new(self.ctx.spillslots.len());
138                self.ctx.spillslots.push(SpillSlotData {
139                    ranges: self.ctx.scratch_spillset_pool.pop().unwrap_or_default(),
140                    alloc: Allocation::none(),
141                    slots: self.func.spillslot_size(self.ctx.spillsets[spillset].class) as u32,
142                });
143                self.ctx.slots_by_class[class].slots.push(spillslot);
144                self.ctx.slots_by_class[class].probe_start =
145                    self.ctx.slots_by_class[class].slots.len() - 1;
146
147                self.allocate_spillset_to_spillslot(spillset, spillslot);
148            }
149        }
150
151        // Assign actual slot indices to spillslots.
152        for i in 0..self.ctx.spillslots.len() {
153            self.ctx.spillslots[i].alloc = self.allocate_spillslot(self.ctx.spillslots[i].slots);
154        }
155
156        trace!("spillslot allocator done");
157    }
158
159    pub fn allocate_spillslot(&mut self, size: u32) -> Allocation {
160        let mut offset = self.ctx.output.num_spillslots as u32;
161        // Align up to `size`.
162        debug_assert!(size.is_power_of_two());
163        offset = (offset + size - 1) & !(size - 1);
164        let slot = if self.func.multi_spillslot_named_by_last_slot() {
165            offset + size - 1
166        } else {
167            offset
168        };
169        offset += size;
170        self.ctx.output.num_spillslots = offset as _;
171        Allocation::stack(SpillSlot::new(slot as usize))
172    }
173}
regalloc2/ion/spill.rs

regalloc2/ion/
spill.rs
