cove_ir/repr.rs
1//! What one eight-byte word means.
2//!
3//! [ADR 0034](../../../docs/adr/0034-one-physical-word-stack.md) keeps the
4//! word untagged and puts its meaning in static metadata. This is that
5//! metadata at its smallest unit: one `Repr` per slot, per field, per array
6//! element.
7//!
8//! **A `Repr` describes one word, not one value.** A value may occupy several
9//! consecutive slots, and what says how many is a
10//! [`Layout`](crate::Layout) — a run of these. The two are separate for the
11//! reason the collector is: it asks exactly one question, of one word at a
12//! time, and a reference map that is one bit per slot answers it without a
13//! range table.
14
15/// The interpretation of one word.
16///
17/// The collector consults exactly one thing about a `Repr`: whether it is
18/// [`Repr::Ref`]. Everything else is for the boundary, the verifier and the
19/// printer, all of which run outside the dispatch loop.
20#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
21pub enum Repr {
22 /// Nothing. The word is zero.
23 ///
24 /// `Unit` is a value in Cove — `fn f() {}` answers one — so it takes a
25 /// slot rather than being absent, which keeps the slot numbering and the
26 /// calling convention free of a special case.
27 Unit,
28 /// `0` or `1`.
29 Bool,
30 /// A two's-complement `i64`.
31 Int,
32 /// An IEEE-754 double, bit-cast into the word.
33 ///
34 /// Bit-cast rather than converted: `f64::to_bits` round-trips every
35 /// value including the NaN payloads, and the word is never read as an
36 /// integer by anything that did not write it as one.
37 Float,
38 /// Nanoseconds, as an `i64`.
39 ///
40 /// A separate `Repr` from [`Repr::Int`] although the bits are the same,
41 /// because the boundary has to know which one to materialise and asking
42 /// the slot is cheaper than carrying a second table.
43 Duration,
44 /// The linear address of a heap object's header, or `0` for none.
45 ///
46 /// This is the only `Repr` the collector treats as a root. Heap
47 /// addresses start at `STACK_WORDS`, so `0` can never name an object and
48 /// is free to mean null — which is what a frame full of zeroes gives a
49 /// `Ref` slot that has not been written yet.
50 Ref,
51 /// The linear address of one mutable word: a place.
52 ///
53 /// Not a root. The object an interior address points into is kept alive
54 /// by the `Ref` slot the lowering holds it in, and the heap does not
55 /// move, so the address stays correct across a collection without the
56 /// collector knowing it exists.
57 Addr,
58 /// An index into the run's host resource table.
59 ///
60 /// A host resource is owned by the host, not by Cove, so it is not an
61 /// object in the heap and not a root. The word names it; the host owns
62 /// its lifetime.
63 Host,
64 /// A task handle: one past an index into the task's scheduler table, or
65 /// `0` for none.
66 ///
67 /// Not a root, and for the same reason [`Repr::Host`] is not: what the
68 /// word names is not storage this collector allocated. A task is a
69 /// thread, a cancellation flag and a place to put an answer, and none of
70 /// those is a Cove value. The answer *is* an object in the run's heap,
71 /// and the table names its address — which makes the table a provider of
72 /// roots rather than a second place to keep a value, because nothing a
73 /// program can write down could be put in one.
74 ///
75 /// One past the index, so that a slot a zeroed frame has not written
76 /// names no task. That is [`Repr::Host`]'s rule, kept because the reason
77 /// for it is the same one.
78 Task,
79 /// A task scope: one past an index into the task's scheduler table, or
80 /// `0` for none.
81 ///
82 /// The other half of what [`Repr::Task`] names, under the same rules. A
83 /// scope owns the tasks spawned into it, which is what lets leaving one
84 /// wait for or cancel them, and it holds nothing else.
85 ///
86 /// Neither of these two crosses a task boundary — the task-safety rule
87 /// says so — so the table they index is the *task's* own and never a
88 /// second task's. Two tasks cannot form one another's handles, which is
89 /// the same disjointness by construction that keeps two stack segments
90 /// apart.
91 Scope,
92 /// An enum's case index: which case an enum value holds.
93 ///
94 /// Physically an integer word and semantically not an integer. It is
95 /// produced by [`Inst::Tag`](crate::Inst::Tag), consumed by
96 /// [`Inst::Switch`](crate::Inst::Switch), copied and cleared like any
97 /// other word, and refused by arithmetic, ordering and integer equality —
98 /// which is the whole of why it is a `Repr` of its own rather than
99 /// [`Repr::Int`] with a comment.
100 Tag,
101}
102
103impl Repr {
104 /// Whether a word of this `Repr` is a garbage-collection root.
105 ///
106 /// This is the whole of what the collector asks the static side.
107 pub fn is_ref(self) -> bool {
108 matches!(self, Repr::Ref)
109 }
110
111 /// The name this `Repr` prints under in a disassembly.
112 pub fn name(self) -> &'static str {
113 match self {
114 Repr::Unit => "unit",
115 Repr::Bool => "bool",
116 Repr::Int => "int",
117 Repr::Float => "float",
118 Repr::Duration => "duration",
119 Repr::Ref => "ref",
120 Repr::Addr => "addr",
121 Repr::Host => "host",
122 Repr::Task => "task",
123 Repr::Scope => "scope",
124 Repr::Tag => "tag",
125 }
126 }
127}
128
129impl std::fmt::Display for Repr {
130 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
131 f.write_str(self.name())
132 }
133}
134
135/// Which slots of a frame are [`Repr::Ref`], as one bit each.
136///
137/// A frame's roots are a static fact here rather than a program-counter
138/// dependent one, and that is the point of the register machine: a stack
139/// machine's live-reference set changes as operands are pushed and popped,
140/// so its map has to be indexed by pc. Here the answer does not change
141/// between the first instruction of a function and the last.
142///
143/// The lowering guarantees the one fact this relies on: **a slot's `Repr` is
144/// fixed for the whole function.** A slot may be reused by a later value of
145/// the *same* `Repr` — that is what keeps a frame from growing with every
146/// temporary a long body mentions — but never by one of a different `Repr`,
147/// because then no single bit would be right at every program counter.
148///
149/// A static map says which slots the collector reads. It cannot say when the
150/// value in one stopped being needed, because that is a fact about a program
151/// point. The lowering answers that in the data instead: it emits
152/// [`Clear`](crate::Inst::Clear) at a reference's last use, so a dead slot
153/// holds null and the collector traces nothing from it.
154#[derive(Clone, Debug, Default, PartialEq, Eq)]
155pub struct RefMap {
156 words: Vec<u64>,
157 slots: u32,
158}
159
160impl RefMap {
161 /// The map for a frame of `slots` words, with `reprs[i]` at slot `i`.
162 pub fn of(reprs: &[Repr]) -> RefMap {
163 let slots = reprs.len() as u32;
164 let mut map = RefMap {
165 words: vec![0; reprs.len().div_ceil(64)],
166 slots,
167 };
168 for (slot, repr) in reprs.iter().enumerate() {
169 if repr.is_ref() {
170 map.words[slot / 64] |= 1 << (slot % 64);
171 }
172 }
173 map
174 }
175
176 /// How many slots the map covers.
177 pub fn slots(&self) -> u32 {
178 self.slots
179 }
180
181 /// Whether slot `slot` holds a reference.
182 ///
183 /// Out of range answers `false` rather than panicking: the collector
184 /// walks a frame whose size it took from the same [`crate::Function`] as
185 /// this map, so a disagreement is a bug in the lowering, and a
186 /// collection is the worst place to discover one by unwinding.
187 pub fn is_ref(&self, slot: u32) -> bool {
188 let slot = slot as usize;
189 match self.words.get(slot / 64) {
190 Some(word) => word & (1 << (slot % 64)) != 0,
191 None => false,
192 }
193 }
194
195 /// Every reference slot, ascending.
196 ///
197 /// Iterating the set bits rather than every slot is what makes a frame
198 /// of mostly scalars cheap to scan: a frame with no references at all
199 /// costs one word read per 64 slots.
200 pub fn iter(&self) -> impl Iterator<Item = u32> + '_ {
201 self.words
202 .iter()
203 .copied()
204 .enumerate()
205 .flat_map(|(i, word)| {
206 let mut rest = word;
207 std::iter::from_fn(move || {
208 if rest == 0 {
209 return None;
210 }
211 let bit = rest.trailing_zeros();
212 rest &= rest - 1;
213 Some(i as u32 * 64 + bit)
214 })
215 })
216 }
217
218 /// Whether the frame holds no references at all.
219 pub fn is_empty(&self) -> bool {
220 self.words.iter().all(|&word| word == 0)
221 }
222}
223
224#[cfg(test)]
225mod tests {
226 use super::*;
227
228 #[test]
229 fn a_scalar_frame_has_no_roots() {
230 let map = RefMap::of(&[Repr::Int, Repr::Bool, Repr::Float]);
231 assert!(map.is_empty());
232 assert_eq!(map.iter().collect::<Vec<_>>(), Vec::<u32>::new());
233 }
234
235 #[test]
236 fn the_map_names_exactly_the_ref_slots() {
237 let map = RefMap::of(&[Repr::Int, Repr::Ref, Repr::Addr, Repr::Ref]);
238 assert_eq!(map.iter().collect::<Vec<_>>(), vec![1, 3]);
239 assert!(!map.is_ref(0));
240 assert!(map.is_ref(1));
241 assert!(!map.is_ref(2));
242 assert!(map.is_ref(3));
243 }
244
245 #[test]
246 fn a_place_is_not_a_root() {
247 // ADR 0034: an address is not itself a root. What it points into is
248 // kept alive by the `Ref` slot holding the base object.
249 assert!(!Repr::Addr.is_ref());
250 assert!(!Repr::Host.is_ref());
251 assert!(Repr::Ref.is_ref());
252 }
253
254 /// A task and a scope name scheduler state, which is not storage this
255 /// collector allocated. What a settled task's answer *is* — an object in
256 /// the run's heap — is reached through the table rather than through the
257 /// word.
258 #[test]
259 fn scheduler_state_is_not_a_root() {
260 assert!(!Repr::Task.is_ref());
261 assert!(!Repr::Scope.is_ref());
262 let map = RefMap::of(&[Repr::Task, Repr::Ref, Repr::Scope]);
263 assert_eq!(map.iter().collect::<Vec<_>>(), vec![1]);
264 }
265
266 #[test]
267 fn the_map_spans_more_than_one_word() {
268 let mut reprs = vec![Repr::Int; 130];
269 reprs[0] = Repr::Ref;
270 reprs[64] = Repr::Ref;
271 reprs[129] = Repr::Ref;
272 let map = RefMap::of(&reprs);
273 assert_eq!(map.slots(), 130);
274 assert_eq!(map.iter().collect::<Vec<_>>(), vec![0, 64, 129]);
275 }
276
277 #[test]
278 fn out_of_range_is_not_a_root() {
279 let map = RefMap::of(&[Repr::Ref]);
280 assert!(map.is_ref(0));
281 assert!(!map.is_ref(9999));
282 }
283}