sv_sim_sim/state/
alias.rs

1//! Window aliases: a ref port (IEEE 1800-2023 23.3.3.2) bound to a *select*
2//! of a variable -- a member of an unpacked struct, an element of an unpacked
3//! array, or a nesting of the two (13.5.2 allows nothing else to be passed by
4//! reference) -- names a sub-range of the target's storage, not a whole
5//! slot.
6//!
7//! A windowed alias owns no storage. Its *view cell* is a [`StateCellId`]
8//! whose value is always derived from the target's cell (the *root*): a read
9//! extracts the window out of the root's value, a write splices the new bits
10//! into the root and commits the root. Processes wait on a view cell exactly
11//! as on any other cell, so an `@(r)` in the child wakes on a change of the
12//! window and never on a change of the rest of the root.
13//!
14//! Every write that changes a root (whichever name it was written through)
15//! reports, besides its own notification, one [`AliasChange`] per overlapping
16//! window plus -- when the write was made through a view -- one for the root
17//! itself; the scheduler drains those after each commit
18//! (`SignalAccess::take_alias_changes`) and notifies the cells through its
19//! ordinary notification path.
20
21use std::cell::{Cell, RefCell};
22use std::collections::HashMap;
23
24use super::write::{ChangeResult, four_state_changed};
25use super::{FourStateValue, StateCellId};
26
27/// A sub-range of a root cell: `width` bits from bit `lo`, of memory row
28/// `row` when the root is a memory (an unpacked array's element).
29#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
30pub struct AliasWindow {
31    pub row: Option<u64>,
32    pub lo: u32,
33    pub width: u32,
34}
35
36/// What a view cell stands for.
37#[derive(Clone, Copy, Debug)]
38pub(crate) struct ViewInfo {
39    pub root: StateCellId,
40    pub window: AliasWindow,
41}
42
43/// A change of a cell the scheduler has to announce because the write that
44/// caused it was made through a *different* name for the same storage.
45#[derive(Clone, Debug)]
46pub struct AliasChange {
47    pub cell: StateCellId,
48    pub old: FourStateValue,
49    pub new: FourStateValue,
50    /// The cell is a whole memory (no meaningful edge).
51    pub no_edge: bool,
52}
53
54/// All view cells of one engine.
55#[derive(Default)]
56pub(crate) struct ViewTable {
57    by_view: HashMap<StateCellId, ViewInfo>,
58    by_key: HashMap<(StateCellId, AliasWindow), StateCellId>,
59    of_root: HashMap<StateCellId, Vec<StateCellId>>,
60    pending: Vec<AliasChange>,
61    /// The view a write in flight was made through.
62    writing: Option<StateCellId>,
63}
64
65impl ViewTable {
66    pub(crate) fn existing(&self, root: StateCellId, window: AliasWindow) -> Option<StateCellId> {
67        self.by_key.get(&(root, window)).copied()
68    }
69
70    pub(crate) fn register(&mut self, view: StateCellId, root: StateCellId, window: AliasWindow) {
71        self.by_view.insert(view, ViewInfo { root, window });
72        self.by_key.insert((root, window), view);
73        self.of_root.entry(root).or_default().push(view);
74    }
75
76    pub(crate) fn info(&self, cell: StateCellId) -> Option<ViewInfo> {
77        self.by_view.get(&cell).copied()
78    }
79
80    pub(crate) fn begin_write(&mut self, view: StateCellId) {
81        self.writing = Some(view);
82    }
83
84    pub(crate) fn end_write(&mut self) {
85        self.writing = None;
86    }
87
88    pub(crate) fn take_pending(&mut self) -> Vec<AliasChange> {
89        std::mem::take(&mut self.pending)
90    }
91
92    /// Records the consequences of `result`, a committed change of `root`
93    /// (row `row` of it, for a memory).
94    fn note(&mut self, root: StateCellId, row: Option<u64>, result: &ChangeResult) {
95        let ViewTable {
96            by_view,
97            of_root,
98            pending,
99            writing,
100            ..
101        } = self;
102        if writing.is_some() {
103            pending.push(AliasChange {
104                cell: root,
105                old: result.old.clone(),
106                new: result.new.clone(),
107                no_edge: row.is_some(),
108            });
109        }
110        let Some(views) = of_root.get(&root) else {
111            return;
112        };
113        for &view in views {
114            if Some(view) == *writing {
115                continue;
116            }
117            let info = &by_view[&view];
118            if info.window.row != row {
119                continue;
120            }
121            let old = window_value(&result.old, info.window);
122            let new = window_value(&result.new, info.window);
123            if four_state_changed(&old, &new) {
124                pending.push(AliasChange {
125                    cell: view,
126                    old,
127                    new,
128                    no_edge: false,
129                });
130            }
131        }
132    }
133}
134
135/// The engine-wide handle on the table, with a one-load fast path for the
136/// (usual) design that has no window alias at all.
137#[derive(Default)]
138pub(crate) struct Views {
139    any: Cell<bool>,
140    table: RefCell<ViewTable>,
141}
142
143impl Views {
144    pub(crate) fn table(&self) -> std::cell::RefMut<'_, ViewTable> {
145        self.table.borrow_mut()
146    }
147
148    pub(crate) fn mark_any(&self) {
149        self.any.set(true);
150    }
151
152    pub(crate) fn info(&self, cell: StateCellId) -> Option<ViewInfo> {
153        if !self.any.get() {
154            return None;
155        }
156        self.table.borrow().info(cell)
157    }
158
159    #[inline]
160    pub(crate) fn note_change(&self, root: StateCellId, row: Option<u64>, result: &ChangeResult) {
161        if self.any.get() && result.changed {
162            self.table.borrow_mut().note(root, row, result);
163        }
164    }
165
166    pub(crate) fn take_pending(&self) -> Vec<AliasChange> {
167        if !self.any.get() {
168            return Vec::new();
169        }
170        self.table.borrow_mut().take_pending()
171    }
172}
173
174/// `(value plane, unknown plane)` of `v`: `val` is the value bit, `unk` the
175/// unknown bit (x is `val=0, unk=1`; z is `val=1, unk=1`).
176fn planes(v: &FourStateValue) -> (Vec<u64>, Vec<u64>) {
177    match v {
178        FourStateValue::Narrow(n) => (vec![*n as u64], vec![(*n >> 64) as u64]),
179        FourStateValue::Wide { aval, bval } => (
180            aval.iter().zip(bval).map(|(a, b)| a ^ b).collect(),
181            bval.clone(),
182        ),
183    }
184}
185
186fn extract_bits(src: &[u64], lo: u32, width: u32) -> Vec<u64> {
187    let n = width.div_ceil(64) as usize;
188    let mut out = Vec::with_capacity(n);
189    for i in 0..n {
190        let bit = lo as usize + 64 * i;
191        let (wi, sh) = (bit / 64, (bit % 64) as u32);
192        let mut w = src.get(wi).copied().unwrap_or(0) >> sh;
193        if sh != 0 {
194            w |= src.get(wi + 1).copied().unwrap_or(0) << (64 - sh);
195        }
196        out.push(w);
197    }
198    if !width.is_multiple_of(64)
199        && let Some(last) = out.last_mut()
200    {
201        *last &= (1u64 << (width % 64)) - 1;
202    }
203    out
204}
205
206fn insert_bits(dst: &mut [u64], lo: u32, width: u32, src: &[u64]) {
207    let n = width.div_ceil(64) as usize;
208    for i in 0..n {
209        let chunk = (width as usize - 64 * i).min(64) as u32;
210        let m = if chunk == 64 {
211            u64::MAX
212        } else {
213            (1u64 << chunk) - 1
214        };
215        let v = src.get(i).copied().unwrap_or(0) & m;
216        let bit = lo as usize + 64 * i;
217        let (wi, sh) = (bit / 64, (bit % 64) as u32);
218        dst[wi] = (dst[wi] & !(m << sh)) | (v << sh);
219        if sh != 0 && sh + chunk > 64 {
220            dst[wi + 1] = (dst[wi + 1] & !(m >> (64 - sh))) | (v >> (64 - sh));
221        }
222    }
223}
224
225/// The value of `window` within `root`: `Narrow` up to 64 bits, `Wide`
226/// beyond, as the storage class of a slot of that width is.
227pub fn window_value(root: &FourStateValue, window: AliasWindow) -> FourStateValue {
228    let (val, unk) = planes(root);
229    let val = extract_bits(&val, window.lo, window.width);
230    let unk = extract_bits(&unk, window.lo, window.width);
231    if window.width <= 64 {
232        FourStateValue::Narrow(u128::from(val[0]) | (u128::from(unk[0]) << 64))
233    } else {
234        FourStateValue::Wide {
235            aval: val.iter().zip(&unk).map(|(v, u)| v ^ u).collect(),
236            bval: unk,
237        }
238    }
239}
240
241/// `root` with `window` replaced by `new` (in `root`'s own representation).
242pub fn splice_window(
243    root: &FourStateValue,
244    window: AliasWindow,
245    new: &FourStateValue,
246) -> FourStateValue {
247    let (mut val, mut unk) = planes(root);
248    let (nv, nu) = planes(new);
249    insert_bits(&mut val, window.lo, window.width, &nv);
250    insert_bits(&mut unk, window.lo, window.width, &nu);
251    match root {
252        FourStateValue::Narrow(_) => {
253            FourStateValue::Narrow(u128::from(val[0]) | (u128::from(unk[0]) << 64))
254        }
255        FourStateValue::Wide { .. } => FourStateValue::Wide {
256            aval: val.iter().zip(&unk).map(|(v, u)| v ^ u).collect(),
257            bval: unk,
258        },
259    }
260}
261
262#[cfg(test)]
263mod tests {
264    use super::*;
265
266    fn w(row: Option<u64>, lo: u32, width: u32) -> AliasWindow {
267        AliasWindow { row, lo, width }
268    }
269
270    #[test]
271    fn narrow_window_round_trips() {
272        let root = FourStateValue::Narrow(0x00AB_CDEF);
273        let win = w(None, 8, 8);
274        match window_value(&root, win) {
275            FourStateValue::Narrow(v) => assert_eq!(v, 0xCD),
276            other => panic!("{other:?}"),
277        }
278        match splice_window(&root, win, &FourStateValue::Narrow(0x12)) {
279            FourStateValue::Narrow(v) => assert_eq!(v, 0x00AB_12EF),
280            other => panic!("{other:?}"),
281        }
282    }
283
284    #[test]
285    fn unknown_bits_travel_with_the_window() {
286        // bits 4..8 are x (val=0, unk=1)
287        let root = FourStateValue::Narrow(0x0000_0000_0000_0005 | (0xF0u128 << 64));
288        let win = w(None, 4, 4);
289        match window_value(&root, win) {
290            FourStateValue::Narrow(v) => assert_eq!(v, 0xF_u128 << 64),
291            other => panic!("{other:?}"),
292        }
293    }
294
295    #[test]
296    fn wide_window_straddling_a_word_boundary() {
297        // 128-bit root, aval/bval planes, all value bits 1 (no unknowns).
298        let root = FourStateValue::Wide {
299            aval: vec![u64::MAX, u64::MAX],
300            bval: vec![0, 0],
301        };
302        let win = w(None, 60, 8);
303        match window_value(&root, win) {
304            FourStateValue::Narrow(v) => assert_eq!(v, 0xFF),
305            other => panic!("{other:?}"),
306        }
307        let cleared = splice_window(&root, win, &FourStateValue::Narrow(0));
308        match cleared {
309            FourStateValue::Wide { aval, bval } => {
310                assert_eq!(aval, vec![0x0FFF_FFFF_FFFF_FFFF, 0xFFFF_FFFF_FFFF_FFF0]);
311                assert_eq!(bval, vec![0, 0]);
312            }
313            other => panic!("{other:?}"),
314        }
315    }
316
317    #[test]
318    fn window_wider_than_a_word_is_wide() {
319        let root = FourStateValue::Wide {
320            aval: vec![0x1111, 0x2222, 0x3333],
321            bval: vec![0, 0, 0],
322        };
323        match window_value(&root, w(None, 64, 100)) {
324            FourStateValue::Wide { aval, bval } => {
325                assert_eq!(aval, vec![0x2222, 0x3333 & 0xF_FFFF_FFFF]);
326                assert_eq!(bval, vec![0, 0]);
327            }
328            other => panic!("{other:?}"),
329        }
330    }
331}
sv_sim_sim/state/alias.rs

sv_sim_sim/state/
alias.rs
