oxide_core/vm/
ic.rs

1//! Inline caches: one 16-byte entry per cache site, in a store beside the code
2//! store.
3//!
4//! The loop borrows the running unit's code across every heap call, so a
5//! cache cannot live in a [`CodeUnit`]. Entries live here instead, indexed by
6//! the unit's `ic_base` plus the site operand of the instruction. The store
7//! sits inside the [`Heap`], as the register file does, so the collector
8//! prunes it at every collection without a parameter: shape, object, cell and
9//! atom indices are recycled, and an entry naming a dead record would hit on
10//! a recycled id. Entries are weak.
11//!
12//! A unit's entries are one range. A freed dynamic unit returns its range,
13//! emptied, to a free list sorted by position, where it merges with its
14//! neighbours; a unit published later takes the first range that fits.
15//!
16//! [`CodeUnit`]: crate::bytecode::CodeUnit
17//! [`Heap`]: crate::heap::Heap
18
19use crate::bytecode::{CodeUnit, Opcode};
20use crate::heap::arena::Arena;
21use crate::heap::object::{NONE, ObjectHeader, ObjectKind, flags};
22use crate::heap::string::StringRecord;
23use crate::heap::values::ValueHeap;
24use crate::shape::{STATIC_CELL, ValidityCell};
25use crate::value::{ShapeId, ValidityCellId, Value};
26
27/// What a cache site caches; decides how [`IcStore::prune`] reads an entry.
28#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
29#[repr(u8)]
30pub enum IcKind {
31    /// `GetField`: `shape`, `holder`, `slot`, `cell`.
32    Get,
33    /// `SetField`: `shape_before`, `shape_after`, `slot`, `cell`.
34    Set,
35    /// `GetGlobal`, `GetGlobalOrUndefined`, `SetGlobal`: `generation`, `slot`,
36    /// `flags`.
37    Global,
38    /// `New`: `fn_shape`, `proto_slot`, `slots`.
39    Construct,
40}
41
42impl IcKind {
43    /// The kind of cache an opcode's site indexes, if it has one.
44    pub const fn of(op: Opcode) -> Option<IcKind> {
45        match op {
46            Opcode::GetField => Some(IcKind::Get),
47            Opcode::SetField => Some(IcKind::Set),
48            Opcode::GetGlobal | Opcode::GetGlobalOrUndefined | Opcode::SetGlobal => {
49                Some(IcKind::Global)
50            }
51            Opcode::New => Some(IcKind::Construct),
52            _ => None,
53        }
54    }
55
56    pub const fn name(self) -> &'static str {
57        match self {
58            IcKind::Get => "get",
59            IcKind::Set => "set",
60            IcKind::Global => "global",
61            IcKind::Construct => "construct",
62        }
63    }
64}
65
66/// The `c` operand of a `GetField` or `SetField` that has no cache: a unit
67/// with more than 255 named-property sites caches the first 255 and gives
68/// the rest this site, whose entry is reserved and never filled.
69pub const FIELD_NO_SITE: u8 = u8::MAX;
70
71/// The site of a global form past the first 65,535 of a unit: reserved and
72/// never filled, as [`FIELD_NO_SITE`].
73pub const GLOBAL_NO_SITE: u32 = u16::MAX as u32;
74
75/// One cache entry, read by the inline hit paths. The meaning of the words
76/// depends on the site's [`IcKind`].
77#[repr(C)]
78#[derive(Clone, Copy, Debug, PartialEq, Eq)]
79pub struct IcEntry {
80    pub w0: u32,
81    pub w1: u32,
82    pub w2: u32,
83    pub w3: u32,
84}
85
86const _: () = assert!(size_of::<IcEntry>() == 16);
87
88/// Bytes one cache site holds: its entry and its kind.
89pub const ENTRY_BYTES: usize = size_of::<IcEntry>() + size_of::<IcKind>();
90
91/// `w0` of an empty entry: no shape has this index.
92pub const EMPTY_TAG: u32 = NONE;
93/// `w0` of a `GetField` entry filled for a string receiver: the property was
94/// found on `%String.prototype%` or above it.
95pub const STRING_RECEIVER_TAG: u32 = NONE - 1;
96/// `w0` of a polymorphic site; `w1` indexes its row of [`POLY`] entries.
97pub const POLY_TAG: u32 = NONE - 2;
98/// `w0` of a megamorphic site: it saw more than [`POLY`] receiver shapes and
99/// records nothing more.
100pub const MEGA_TAG: u32 = NONE - 3;
101/// `w0` of a `GetField` entry for `length` read on an array or a string: the
102/// array's length or the string's unit count, with no shape to compare.
103pub const LENGTH_TAG: u32 = NONE - 4;
104/// Entries a polymorphic site probes, in order, on the out-of-line path.
105pub const POLY: usize = 4;
106/// Entries of the table megamorphic `GetField` sites share: a direct-mapped
107/// cache keyed by receiver shape and property key, as V8's megamorphic stub
108/// cache is.
109pub const MEGA_ENTRIES: usize = 4096;
110
111impl IcEntry {
112    pub const EMPTY: IcEntry = IcEntry {
113        w0: EMPTY_TAG,
114        w1: NONE,
115        w2: NONE,
116        w3: NONE,
117    };
118
119    #[inline]
120    pub fn is_empty(&self) -> bool {
121        self.w0 == EMPTY_TAG
122    }
123
124    /// Whether the entry is a monomorphic fill rather than empty, a
125    /// polymorphic link or the megamorphic mark.
126    #[inline]
127    pub fn is_filled(&self) -> bool {
128        self.w0 < LENGTH_TAG || self.w0 == STRING_RECEIVER_TAG || self.w0 == LENGTH_TAG
129    }
130
131    /// The validity cell of a filled `GetField` or `SetField` entry.
132    pub fn cell(&self) -> ValidityCellId {
133        ValidityCellId(self.w3)
134    }
135}
136
137/// A `GetField` hit: an own hit is one shape compare and a load; a prototype or
138/// string-receiver hit adds the cell test. It takes the heap's arenas rather
139/// than the heap, so the loop keeps its register window borrowed across it.
140#[inline(always)]
141pub(crate) fn get_hit(
142    objects: &Arena<ObjectHeader>,
143    cells: &Arena<ValidityCell>,
144    values: &ValueHeap,
145    strings: &Arena<StringRecord>,
146    entry: IcEntry,
147    receiver: Value,
148) -> Option<Value> {
149    let holder = if let Some(object) = receiver.as_object() {
150        let header = objects.get(object.0);
151        if header.shape.0 != entry.w0 {
152            if entry.w0 == LENGTH_TAG && header.kind == ObjectKind::Array {
153                return Some(length_value(header.payload as usize));
154            }
155            return None;
156        }
157        if entry.w1 == NONE {
158            return Some(values.get_at(header.slots_start + entry.w2));
159        }
160        entry.w1
161    } else {
162        let string = receiver.as_string()?;
163        if entry.w0 == LENGTH_TAG {
164            return Some(length_value(strings.get(string.index()).len()));
165        }
166        if entry.w0 != STRING_RECEIVER_TAG {
167            return None;
168        }
169        entry.w1
170    };
171    if !cells.get(entry.w3).valid {
172        return None;
173    }
174    Some(values.get_at(objects.get(holder).slots_start + entry.w2))
175}
176
177/// A length as a value: an `Int32` below 2^31.
178#[inline(always)]
179fn length_value(length: usize) -> Value {
180    match i32::try_from(length) {
181        Ok(length) => Value::int32(length),
182        Err(_) => Value::number(length as f64),
183    }
184}
185
186/// A `SetField` hit: a write to an existing own data property when the shape
187/// matches; a transition when the shape matches, the chain's cell holds, the
188/// slot is inside the reserved range and the object is extensible and not a
189/// prototype (whose shape change must invalidate).
190#[inline(always)]
191pub(crate) fn set_hit(
192    objects: &mut Arena<ObjectHeader>,
193    cells: &Arena<ValidityCell>,
194    values: &mut ValueHeap,
195    entry: IcEntry,
196    receiver: Value,
197    value: Value,
198) -> bool {
199    let Some(object) = receiver.as_object() else {
200        return false;
201    };
202    let header = objects.get_mut(object.0);
203    if header.shape.0 != entry.w0 {
204        return false;
205    }
206    if entry.w1 != entry.w0 {
207        let plain = header.flags & (flags::EXTENSIBLE | flags::USED_AS_PROTOTYPE);
208        if entry.w2 >= header.slots().len
209            || plain != flags::EXTENSIBLE
210            || !cells.get(entry.w3).valid
211        {
212            return false;
213        }
214        header.shape = ShapeId(entry.w1);
215    }
216    values.set_at(header.slots_start + entry.w2, value);
217    true
218}
219
220/// Hit and miss counters per cache kind, kept with the `ic-stats` feature and
221/// in debug builds (so tests can see hits): release builds without the feature
222/// carry no counter.
223#[derive(Clone, Debug, Default)]
224pub struct IcStats {
225    /// Monomorphic hits, by [`IcKind`].
226    pub mono_hits: [u64; 4],
227    /// Hits on the out-of-line probe of a polymorphic row.
228    pub poly_hits: [u64; 4],
229    /// Misses that filled or refilled an entry.
230    pub fills: [u64; 4],
231    /// Misses that did not: an accessor, a dictionary, a complete miss, a
232    /// megamorphic site.
233    pub unfilled: [u64; 4],
234    /// Misses per entry, both kinds.
235    pub site_misses: Vec<u64>,
236    /// `IterStart`s that walked a pristine array by index, and the ones that
237    /// ran the protocol.
238    pub iter_pristine: u64,
239    pub iter_generic: u64,
240}
241
242/// Every cache entry of every published unit: unit `u`'s entries are
243/// `entries[u.ic_base..u.ic_base + u.ic_count]`.
244#[derive(Default)]
245pub struct IcStore {
246    pub(crate) entries: Vec<IcEntry>,
247    pub(crate) kinds: Vec<IcKind>,
248    /// The ranges no unit holds, as `(start, len)`, sorted and never
249    /// adjacent; their entries are empty.
250    free: Vec<(u32, u32)>,
251    /// The rows of polymorphic sites, each owned by one site.
252    pub(crate) poly: Vec<[IcEntry; POLY]>,
253    /// The kind of each row's site.
254    poly_kinds: Vec<IcKind>,
255    /// Rows no site owns, reused first.
256    poly_free: Vec<u32>,
257    /// The megamorphic table: `(shape, key)` and a `GetField` entry for that
258    /// shape; empty until a site goes megamorphic.
259    mega: Vec<(u32, u32, IcEntry)>,
260    #[cfg(any(feature = "ic-stats", debug_assertions))]
261    stats: IcStats,
262}
263
264impl IcStore {
265    /// Reserves the entries of a unit about to be published and sets its
266    /// `ic_base`: the first free range that fits, else the end of the store.
267    pub(crate) fn reserve(&mut self, unit: &mut CodeUnit) {
268        let count = unit.ic_count;
269        let end = self.entries.len() as u32;
270        let first = match self.free.iter().position(|&(_, len)| len >= count) {
271            _ if count == 0 => end,
272            Some(position) => {
273                let (start, len) = self.free[position];
274                if len == count {
275                    self.free.remove(position);
276                } else {
277                    self.free[position] = (start + count, len - count);
278                }
279                start
280            }
281            // A free range at the end grows into the new entries.
282            None if self
283                .free
284                .last()
285                .is_some_and(|&(start, len)| start + len == end) =>
286            {
287                let (start, _) = self.free.pop().expect("a free range");
288                start
289            }
290            None => end,
291        };
292        let len = first.checked_add(count).expect("cache store overflow") as usize;
293        if len > self.entries.len() {
294            self.entries.resize(len, IcEntry::EMPTY);
295            self.kinds.resize(len, IcKind::Get);
296            #[cfg(any(feature = "ic-stats", debug_assertions))]
297            self.stats.site_misses.resize(len, 0);
298        }
299        // Sites the instructions do not name (the reserved no-cache field
300        // site) keep the field kind and stay empty.
301        let first = first as usize;
302        self.kinds[first..len].fill(IcKind::Get);
303        for insn in unit.code.iter() {
304            if let (Some(kind), Some(site)) = (IcKind::of(insn.op), insn.site()) {
305                self.kinds[first + site as usize] = kind;
306            }
307        }
308        unit.ic_base = first as u32;
309    }
310
311    /// Empties the entries of a freed unit and returns its range (and the
312    /// polymorphic rows its sites own) to the free lists.
313    pub(crate) fn release(&mut self, unit: &CodeUnit) {
314        let (start, count) = (unit.ic_base, unit.ic_count);
315        if count == 0 {
316            return;
317        }
318        let range = start as usize..(start + count) as usize;
319        for entry in &mut self.entries[range.clone()] {
320            if entry.w0 == POLY_TAG {
321                self.poly[entry.w1 as usize] = [IcEntry::EMPTY; POLY];
322                self.poly_free.push(entry.w1);
323            }
324            *entry = IcEntry::EMPTY;
325        }
326        #[cfg(any(feature = "ic-stats", debug_assertions))]
327        self.stats.site_misses[range].fill(0);
328        let position = self.free.partition_point(|&(free, _)| free < start);
329        let after = self
330            .free
331            .get(position)
332            .is_some_and(|&(free, _)| free == start + count);
333        let before = position > 0 && {
334            let (free, len) = self.free[position - 1];
335            free + len == start
336        };
337        match (before, after) {
338            (true, true) => {
339                let (_, next) = self.free.remove(position);
340                self.free[position - 1].1 += count + next;
341            }
342            (true, false) => self.free[position - 1].1 += count,
343            (false, true) => {
344                let next = &mut self.free[position];
345                *next = (start, next.1 + count);
346            }
347            (false, false) => self.free.insert(position, (start, count)),
348        }
349    }
350
351    /// Entries no unit holds.
352    pub fn free_len(&self) -> usize {
353        self.free.iter().map(|&(_, len)| len as usize).sum()
354    }
355
356    /// Debug check: every free entry is empty and no free row is linked.
357    pub(crate) fn verify_free(&self) {
358        for &(start, len) in &self.free {
359            let range = start as usize..(start + len) as usize;
360            assert!(
361                self.entries[range].iter().all(IcEntry::is_empty),
362                "gc verify: a free cache range at {start} is not empty"
363            );
364        }
365        for &row in &self.poly_free {
366            assert!(
367                self.poly[row as usize].iter().all(IcEntry::is_empty),
368                "gc verify: free polymorphic row {row} is not empty"
369            );
370        }
371    }
372
373    #[inline(always)]
374    pub fn entry(&self, index: usize) -> IcEntry {
375        self.entries[index]
376    }
377
378    pub fn kind(&self, index: usize) -> IcKind {
379        self.kinds[index]
380    }
381
382    /// The row of a polymorphic site.
383    #[inline]
384    pub fn poly_row(&self, index: usize) -> Option<&[IcEntry; POLY]> {
385        let entry = self.entries[index];
386        (entry.w0 == POLY_TAG).then(|| &self.poly[entry.w1 as usize])
387    }
388
389    /// Records a fill of site `index`. A shape-keyed site (`GetField`,
390    /// `SetField`) is monomorphic until a second key arrives, then
391    /// polymorphic up to [`POLY`] keys, then megamorphic; a refill for a key
392    /// it holds replaces that entry. The other kinds hold one entry. Returns
393    /// whether the entry was stored.
394    pub(crate) fn record(&mut self, index: usize, fill: IcEntry) -> bool {
395        let kind = self.kinds[index];
396        let current = self.entries[index];
397        if !matches!(kind, IcKind::Get | IcKind::Set)
398            || (!current.is_filled() && current.w0 != POLY_TAG)
399        {
400            if current.w0 == MEGA_TAG {
401                return false;
402            }
403            self.entries[index] = fill;
404            return true;
405        }
406        if current.is_filled() {
407            if current.w0 == fill.w0 {
408                self.entries[index] = fill;
409            } else {
410                let entries = [current, fill, IcEntry::EMPTY, IcEntry::EMPTY];
411                let row = match self.poly_free.pop() {
412                    Some(row) => {
413                        self.poly[row as usize] = entries;
414                        self.poly_kinds[row as usize] = kind;
415                        row
416                    }
417                    None => {
418                        self.poly.push(entries);
419                        self.poly_kinds.push(kind);
420                        self.poly.len() as u32 - 1
421                    }
422                };
423                self.entries[index] = IcEntry {
424                    w0: POLY_TAG,
425                    w1: row,
426                    w2: NONE,
427                    w3: NONE,
428                };
429            }
430            return true;
431        }
432        let row = &mut self.poly[current.w1 as usize];
433        let slot = row
434            .iter()
435            .position(|entry| entry.w0 == fill.w0)
436            .or_else(|| row.iter().position(IcEntry::is_empty));
437        match slot {
438            Some(slot) => {
439                row[slot] = fill;
440                true
441            }
442            None => {
443                let row = current.w1;
444                self.poly[row as usize] = [IcEntry::EMPTY; POLY];
445                self.poly_free.push(row);
446                self.entries[index] = IcEntry {
447                    w0: MEGA_TAG,
448                    ..IcEntry::EMPTY
449                };
450                false
451            }
452        }
453    }
454
455    #[inline]
456    fn mega_index(shape: u32, key: u32) -> usize {
457        let hash = shape.wrapping_mul(0x9E37_79B9) ^ key.wrapping_mul(0x85EB_CA6B);
458        (hash >> 20) as usize & (MEGA_ENTRIES - 1)
459    }
460
461    /// The megamorphic table's entry for a receiver shape and a key.
462    #[inline]
463    pub(crate) fn mega_entry(&self, shape: u32, key: u32) -> Option<IcEntry> {
464        let &(entry_shape, entry_key, entry) = self.mega.get(Self::mega_index(shape, key))?;
465        (entry_shape == shape && entry_key == key).then_some(entry)
466    }
467
468    /// Records a megamorphic site's fill in the shared table.
469    pub(crate) fn record_mega(&mut self, key: u32, fill: IcEntry) {
470        if self.mega.is_empty() {
471            self.mega
472                .resize(MEGA_ENTRIES, (EMPTY_TAG, NONE, IcEntry::EMPTY));
473        }
474        let index = Self::mega_index(fill.w0, key);
475        self.mega[index] = (fill.w0, key, fill);
476    }
477
478    /// Whether site `index` is megamorphic.
479    #[inline]
480    pub(crate) fn is_megamorphic(&self, index: usize) -> bool {
481        self.entries[index].w0 == MEGA_TAG
482    }
483
484    /// Empties every entry of `kind` (the global generation wrapped).
485    pub(crate) fn clear_kind(&mut self, kind: IcKind) {
486        for (entry, &entry_kind) in self.entries.iter_mut().zip(&self.kinds) {
487            if entry_kind == kind {
488                *entry = IcEntry::EMPTY;
489            }
490        }
491    }
492
493    pub fn len(&self) -> usize {
494        self.entries.len()
495    }
496
497    /// Bytes the entries, their kinds, the free lists and the polymorphic
498    /// and megamorphic tables reserve.
499    pub fn bytes(&self) -> usize {
500        self.entries.capacity() * size_of::<IcEntry>()
501            + self.kinds.capacity() * size_of::<IcKind>()
502            + self.free.capacity() * size_of::<(u32, u32)>()
503            + self.poly.capacity() * size_of::<[IcEntry; POLY]>()
504            + self.poly_kinds.capacity() * size_of::<IcKind>()
505            + self.poly_free.capacity() * size_of::<u32>()
506            + self.mega.capacity() * size_of::<(u32, u32, IcEntry)>()
507    }
508
509    pub fn is_empty(&self) -> bool {
510        self.entries.is_empty()
511    }
512
513    /// Monomorphic entries that are filled.
514    pub fn filled(&self) -> usize {
515        self.entries
516            .iter()
517            .filter(|entry| entry.is_filled())
518            .count()
519    }
520
521    /// Sites by state: monomorphic, polymorphic, megamorphic.
522    pub fn site_states(&self) -> (usize, usize, usize) {
523        let count = |tag: u32| self.entries.iter().filter(|entry| entry.w0 == tag).count();
524        (self.filled(), count(POLY_TAG), count(MEGA_TAG))
525    }
526
527    // ---- ic-stats ----
528
529    #[inline(always)]
530    pub(crate) fn count_hit(&mut self, kind: IcKind) {
531        #[cfg(any(feature = "ic-stats", debug_assertions))]
532        {
533            self.stats.mono_hits[kind as usize] += 1;
534        }
535        let _ = kind;
536    }
537
538    #[inline(always)]
539    pub(crate) fn count_iteration(&mut self, pristine: bool) {
540        #[cfg(any(feature = "ic-stats", debug_assertions))]
541        {
542            if pristine {
543                self.stats.iter_pristine += 1;
544            } else {
545                self.stats.iter_generic += 1;
546            }
547        }
548        let _ = pristine;
549    }
550
551    #[inline(always)]
552    pub(crate) fn count_poly_hit(&mut self, kind: IcKind) {
553        #[cfg(any(feature = "ic-stats", debug_assertions))]
554        {
555            self.stats.poly_hits[kind as usize] += 1;
556        }
557        let _ = kind;
558    }
559
560    #[inline(always)]
561    pub(crate) fn count_miss(&mut self, index: usize, filled: bool) {
562        #[cfg(any(feature = "ic-stats", debug_assertions))]
563        {
564            let kind = self.kinds[index] as usize;
565            if filled {
566                self.stats.fills[kind] += 1;
567            } else {
568                self.stats.unfilled[kind] += 1;
569            }
570            self.stats.site_misses[index] += 1;
571        }
572        let _ = (index, filled);
573    }
574
575    /// The counters, with the `ic-stats` feature or in a debug build.
576    pub fn stats(&self) -> Option<&IcStats> {
577        #[cfg(any(feature = "ic-stats", debug_assertions))]
578        return Some(&self.stats);
579        #[cfg(not(any(feature = "ic-stats", debug_assertions)))]
580        None
581    }
582
583    // ---- collection ----
584
585    /// Every record the filled entries name, for the stress verifier.
586    pub(crate) fn named_records(&self) -> impl Iterator<Item = Record> + '_ {
587        let mono = self
588            .entries
589            .iter()
590            .zip(&self.kinds)
591            .filter(|(entry, _)| entry.is_filled())
592            .flat_map(|(&entry, &kind)| records(kind, entry));
593        let poly = self
594            .poly
595            .iter()
596            .zip(&self.poly_kinds)
597            .flat_map(|(row, &kind)| {
598                row.iter()
599                    .filter(|entry| entry.is_filled())
600                    .flat_map(move |&entry| records(kind, entry))
601            });
602        let mega = self
603            .mega
604            .iter()
605            .filter(|(_, _, entry)| entry.is_filled())
606            .flat_map(|&(_, key, entry)| records(IcKind::Get, entry).chain(key_atom(key)));
607        mono.chain(poly).chain(mega)
608    }
609
610    /// Clears every entry that names a record `live` rejects: one linear pass
611    /// over the entries and the polymorphic rows, run by the collector after
612    /// marking, with `live` reading the mark bits.
613    pub(crate) fn prune(&mut self, mut live: impl FnMut(Record) -> bool) -> usize {
614        let mut cleared = 0;
615        let rows = self.poly.iter_mut().zip(&self.poly_kinds);
616        let poly = rows.flat_map(|(row, kind)| row.iter_mut().map(move |entry| (entry, kind)));
617        for (entry, &kind) in self.entries.iter_mut().zip(&self.kinds).chain(poly) {
618            if entry.is_filled() && !records(kind, *entry).all(&mut live) {
619                *entry = IcEntry::EMPTY;
620                cleared += 1;
621            }
622        }
623        // A megamorphic entry is also keyed by its property key, whose atom
624        // index a dead atom gives up.
625        for (_, key, entry) in &mut self.mega {
626            if entry.is_filled()
627                && !records(IcKind::Get, *entry)
628                    .chain(key_atom(*key))
629                    .all(&mut live)
630            {
631                *entry = IcEntry::EMPTY;
632                cleared += 1;
633            }
634        }
635        cleared
636    }
637}
638
639/// The atom a megamorphic entry's key names, if it is one.
640fn key_atom(key: u32) -> Option<Record> {
641    match crate::heap::atom::PropertyKey::from_raw(key).kind() {
642        crate::heap::atom::KeyKind::String(id) => Some(Record::Atom(id.index())),
643        _ => None,
644    }
645}
646/// A heap record an entry names.
647#[derive(Clone, Copy, Debug, PartialEq, Eq)]
648pub(crate) enum Record {
649    Shape(u32),
650    Object(u32),
651    Cell(u32),
652    Atom(u32),
653}
654
655/// The records a filled entry of `kind` names.
656fn records(kind: IcKind, entry: IcEntry) -> impl Iterator<Item = Record> {
657    let mut found = [None; 3];
658    match kind {
659        IcKind::Get if entry.w0 == LENGTH_TAG => {}
660        IcKind::Get => {
661            if entry.w0 != STRING_RECEIVER_TAG {
662                found[0] = Some(Record::Shape(entry.w0));
663            }
664            if entry.w1 != NONE {
665                found[1] = Some(Record::Object(entry.w1));
666            }
667            if entry.w3 != NONE && entry.w3 != STATIC_CELL.index() {
668                found[2] = Some(Record::Cell(entry.w3));
669            }
670        }
671        IcKind::Set => {
672            found[0] = Some(Record::Shape(entry.w0));
673            found[1] = Some(Record::Shape(entry.w1));
674            if entry.w3 != NONE && entry.w3 != STATIC_CELL.index() {
675                found[2] = Some(Record::Cell(entry.w3));
676            }
677        }
678        IcKind::Global => {}
679        IcKind::Construct => found[0] = Some(Record::Shape(entry.w0)),
680    }
681    found.into_iter().flatten()
682}
683
684#[cfg(test)]
685mod tests {
686    use super::*;
687    use crate::bytecode::CodeBuilder;
688    use crate::bytecode::builder::UnitLayout;
689
690    /// A unit with `sites` cache sites.
691    fn unit(sites: u32) -> CodeUnit {
692        let mut builder = CodeBuilder::new();
693        builder.a(Opcode::Return, 0);
694        let mut unit = builder.finish(UnitLayout {
695            register_count: 1,
696            ..UnitLayout::default()
697        });
698        unit.ic_count = sites;
699        unit
700    }
701
702    fn reserve(store: &mut IcStore, sites: u32) -> CodeUnit {
703        let mut unit = unit(sites);
704        store.reserve(&mut unit);
705        unit
706    }
707
708    #[test]
709    fn freed_ranges_merge_and_split() {
710        let mut store = IcStore::default();
711        let [a, b, c, d] = [4, 6, 3, 5].map(|sites| reserve(&mut store, sites));
712        assert_eq!([a.ic_base, b.ic_base, c.ic_base, d.ic_base], [0, 4, 10, 13]);
713        store.release(&b);
714        store.release(&a);
715        assert_eq!(store.free, [(0, 10)], "adjacent ranges merge");
716        store.release(&c);
717        assert_eq!(store.free, [(0, 13)]);
718        assert_eq!(store.free_len(), 13);
719        // First fit, and the rest stays free.
720        let e = reserve(&mut store, 8);
721        assert_eq!(e.ic_base, 0);
722        assert_eq!(store.free, [(8, 5)]);
723        // Too large for the hole: appended.
724        let f = reserve(&mut store, 9);
725        assert_eq!(f.ic_base, 18);
726        // A free range at the end grows into the new entries.
727        store.release(&f);
728        let g = reserve(&mut store, 12);
729        assert_eq!(g.ic_base, 18);
730        assert_eq!(store.len(), 30);
731        store.verify_free();
732    }
733
734    #[test]
735    fn a_freed_unit_empties_its_entries_and_rows() {
736        let mut store = IcStore::default();
737        let a = reserve(&mut store, 2);
738        store.kinds[0] = IcKind::Get;
739        let fill = |shape: u32| IcEntry {
740            w0: shape,
741            w1: NONE,
742            w2: 0,
743            w3: STATIC_CELL.index(),
744        };
745        assert!(store.record(0, fill(1)));
746        assert!(store.record(0, fill(2)));
747        assert!(store.poly_row(0).is_some());
748        assert!(store.record(1, fill(3)));
749        store.release(&a);
750        assert!(store.entries[..2].iter().all(IcEntry::is_empty));
751        store.verify_free();
752        // The next polymorphic site takes the freed row.
753        let b = reserve(&mut store, 1);
754        assert_eq!(b.ic_base, 0);
755        assert!(store.record(0, fill(4)));
756        assert!(store.record(0, fill(5)));
757        assert_eq!(store.entries[0].w1, 0, "the row is reused");
758        assert_eq!(store.poly.len(), 1);
759    }
760}
oxide_core/vm/ic.rs

oxide_core/vm/
ic.rs
