cranelift_codegen/binemit/
stack_map.rs

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

cranelift_codegen/binemit/
stack_map.rs
