cranelift_codegen/binemit/
stack_map.rs

1use cranelift_bitset::CompoundBitSet;
2
3/// Stack maps record which words in a stack frame contain live GC references at
4/// a given instruction pointer.
5///
6/// Logically, a set of stack maps for a function record a table of the form:
7///
8/// ```text
9/// +---------------------+-------------------------------------------+
10/// | Instruction Pointer | SP-Relative Offsets of Live GC References |
11/// +---------------------+-------------------------------------------+
12/// | 0x12345678          | 2, 6, 12                                  |
13/// | 0x1234abcd          | 2, 6                                      |
14/// | ...                 | ...                                       |
15/// +---------------------+-------------------------------------------+
16/// ```
17///
18/// Where "instruction pointer" is an instruction pointer within the function,
19/// and "offsets of live GC references" contains the offsets (in units of words)
20/// from the frame's stack pointer where live GC references are stored on the
21/// stack. Instruction pointers within the function that do not have an entry in
22/// this table are not GC safepoints.
23///
24/// Because
25///
26/// * offsets of live GC references are relative from the stack pointer, and
27/// * stack frames grow down from higher addresses to lower addresses,
28///
29/// to get a pointer to a live reference at offset `x` within a stack frame, you
30/// add `x` from the frame's stack pointer.
31///
32/// For example, to calculate the pointer to the live GC reference inside "frame
33/// 1" below, you would do `frame_1_sp + x`:
34///
35/// ```text
36///           Stack
37///         +-------------------+
38///         | Frame 0           |
39///         |                   |
40///    |    |                   |
41///    |    +-------------------+ <--- Frame 0's SP
42///    |    | Frame 1           |
43///  Grows  |                   |
44///  down   |                   |
45///    |    | Live GC reference | --+--
46///    |    |                   |   |
47///    |    |                   |   |
48///    V    |                   |   x = offset of live GC reference
49///         |                   |   |
50///         |                   |   |
51///         +-------------------+ --+--  <--- Frame 1's SP
52///         | Frame 2           |
53///         | ...               |
54/// ```
55///
56/// An individual `StackMap` is associated with just one instruction pointer
57/// within the function, contains the size of the stack frame, and represents
58/// the stack frame as a bitmap. There is one bit per word in the stack frame,
59/// and if the bit is set, then the word contains a live GC reference.
60///
61/// Note that a caller's `OutgoingArg` stack slots and callee's `IncomingArg`
62/// stack slots overlap, so we must choose which function's stack maps record
63/// live GC references in these slots. We record the `IncomingArg`s in the
64/// callee's stack map.
65#[derive(Clone, Debug, PartialEq, Eq)]
66#[cfg_attr(
67    feature = "enable-serde",
68    derive(serde_derive::Deserialize, serde_derive::Serialize)
69)]
70pub struct StackMap {
71    bitset: CompoundBitSet,
72    mapped_words: u32,
73}
74
75impl StackMap {
76    /// Create a stack map from a slice of booleans.
77    pub fn from_slice(bools: &[bool]) -> Self {
78        let mut bitset = CompoundBitSet::with_capacity(bools.len());
79        for (i, b) in bools.iter().enumerate() {
80            if *b {
81                bitset.insert(i);
82            }
83        }
84        Self {
85            mapped_words: u32::try_from(bools.len()).unwrap(),
86            bitset,
87        }
88    }
89
90    /// Returns a specified bit.
91    pub fn get_bit(&self, bit_index: usize) -> bool {
92        self.bitset.contains(bit_index)
93    }
94
95    /// Returns the raw bitmap that represents this stack map.
96    pub fn into_bitset(self) -> CompoundBitSet {
97        self.bitset
98    }
99
100    /// Returns the number of words represented by this stack map.
101    pub fn mapped_words(&self) -> u32 {
102        self.mapped_words
103    }
104}
105
106#[cfg(test)]
107mod tests {
108    use super::*;
109    use alloc::vec::Vec;
110
111    type Num = u32;
112    const NUM_BITS: usize = core::mem::size_of::<Num>() * 8;
113
114    #[test]
115    fn stack_maps() {
116        let vec: Vec<bool> = Vec::new();
117        assert!(StackMap::from_slice(&vec).bitset.is_empty());
118
119        let mut vec: [bool; NUM_BITS] = Default::default();
120        let set_true_idx = [5, 7, 24, 31];
121
122        for &idx in &set_true_idx {
123            vec[idx] = true;
124        }
125
126        let mut vec = vec.to_vec();
127        let stack_map = StackMap::from_slice(&vec);
128        for idx in 0..32 {
129            assert_eq!(stack_map.get_bit(idx), set_true_idx.contains(&idx));
130        }
131
132        vec.push(false);
133        vec.push(true);
134        let res = StackMap::from_slice(&vec);
135        for idx in 0..32 {
136            assert_eq!(stack_map.get_bit(idx), set_true_idx.contains(&idx));
137        }
138        assert!(!res.get_bit(32));
139        assert!(res.get_bit(33));
140    }
141}
cranelift_codegen/binemit/stack_map.rs

cranelift_codegen/binemit/
stack_map.rs
