1 //! User-defined stack maps.
2 //!
3 //! This module provides types allowing users to define stack maps and associate
4 //! them with safepoints.
5 //!
6 //! A **safepoint** is a program point (i.e. CLIF instruction) where it must be
7 //! safe to run GC. Currently all non-tail call instructions are considered
8 //! safepoints. (This does *not* allow, for example, skipping safepoints for
9 //! calls that are statically known not to trigger collections, or to have a
10 //! safepoint on a volatile load to a page that gets protected when it is time
11 //! to GC, triggering a fault that pauses the mutator and lets the collector do
12 //! its work before resuming the mutator. We can lift this restriction in the
13 //! future, if necessary.)
14 //!
15 //! A **stack map** is a description of where to find all the GC-managed values
16 //! that are live at a particular safepoint. Stack maps let the collector find
17 //! on-stack roots. Each stack map is logically a set of offsets into the stack
18 //! frame and the type of value at that associated offset. However, because the
19 //! stack layout isn't defined until much later in the compiler's pipeline, each
20 //! stack map entry instead includes both an `ir::StackSlot` and an offset
21 //! within that slot.
22 //!
23 //! These stack maps are **user-defined** in that it is the CLIF producer's
24 //! responsibility to identify and spill the live GC-managed values and attach
25 //! the associated stack map entries to each safepoint themselves (see
26 //! `cranelift_frontend::Function::declare_needs_stack_map` and
27 //! `cranelift_codegen::ir::DataFlowGraph::append_user_stack_map_entry`). Cranelift
28 //! will not insert spills and record these stack map entries automatically.
29 //!
30 //! Logically, a set of stack maps for a function record a table of the form:
31 //!
32 //! ```text
33 //! +---------------------+-------------------------------------------+
34 //! | Instruction Pointer | SP-Relative Offsets of Live GC References |
35 //! +---------------------+-------------------------------------------+
36 //! | 0x12345678          | 2, 6, 12                                  |
37 //! | 0x1234abcd          | 2, 6                                      |
38 //! | ...                 | ...                                       |
39 //! +---------------------+-------------------------------------------+
40 //! ```
41 //!
42 //! Where "instruction pointer" is an instruction pointer within the function,
43 //! and "offsets of live GC references" contains the offsets (in units of words)
44 //! from the frame's stack pointer where live GC references are stored on the
45 //! stack. Instruction pointers within the function that do not have an entry in
46 //! this table are not GC safepoints.
47 //!
48 //! Because
49 //!
50 //! * offsets of live GC references are relative from the stack pointer, and
51 //! * stack frames grow down from higher addresses to lower addresses,
52 //!
53 //! to get a pointer to a live reference at offset `x` within a stack frame, you
54 //! add `x` to the frame's stack pointer.
55 //!
56 //! For example, to calculate the pointer to the live GC reference inside "frame
57 //! 1" below, you would do `frame_1_sp + x`:
58 //!
59 //! ```text
60 //!           Stack
61 //!         +-------------------+
62 //!         | Frame 0           |
63 //!         |                   |
64 //!    |    |                   |
65 //!    |    +-------------------+ <--- Frame 0's SP
66 //!    |    | Frame 1           |
67 //!  Grows  |                   |
68 //!  down   |                   |
69 //!    |    | Live GC reference | --+--
70 //!    |    |                   |   |
71 //!    |    |                   |   |
72 //!    V    |                   |   x = offset of live GC reference
73 //!         |                   |   |
74 //!         |                   |   |
75 //!         +-------------------+ --+--  <--- Frame 1's SP
76 //!         | Frame 2           |
77 //!         | ...               |
78 //! ```
79 //!
80 //! An individual `UserStackMap` is associated with just one instruction pointer
81 //! within the function, contains the size of the stack frame, and represents
82 //! the stack frame as a bitmap. There is one bit per word in the stack frame,
83 //! and if the bit is set, then the word contains a live GC reference.
84 //!
85 //! Note that a caller's outgoing argument stack slots (if any) and callee's
86 //! incoming argument stack slots (if any) overlap, so we must choose which
87 //! function's stack maps record live GC references in these slots. We record
88 //! the incoming arguments in the callee's stack map. This choice plays nice
89 //! with tail calls, where by the time we transfer control to the callee, the
90 //! caller no longer exists.
91 
92 use crate::ir;
93 use cranelift_bitset::CompoundBitSet;
94 use cranelift_entity::PrimaryMap;
95 use smallvec::SmallVec;
96 
97 pub(crate) type UserStackMapEntryVec = SmallVec<[UserStackMapEntry; 4]>;
98 
99 /// A stack map entry describes a single GC-managed value and its location on
100 /// the stack.
101 ///
102 /// A stack map entry is associated with a particular instruction, and that
103 /// instruction must be a safepoint. The GC-managed value must be stored in the
104 /// described location across this entry's instruction.
105 #[derive(Clone, Debug, PartialEq, Hash)]
106 #[cfg_attr(
107     feature = "enable-serde",
108     derive(serde_derive::Serialize, serde_derive::Deserialize)
109 )]
110 pub struct UserStackMapEntry {
111     /// The type of the value stored in this stack map entry.
112     pub ty: ir::Type,
113 
114     /// The stack slot that this stack map entry is within.
115     pub slot: ir::StackSlot,
116 
117     /// The offset within the stack slot where this entry's value can be found.
118     pub offset: u32,
119 }
120 
121 /// A compiled stack map, describing the location of many GC-managed values.
122 ///
123 /// A stack map is associated with a particular instruction, and that
124 /// instruction is a safepoint.
125 #[derive(Clone, Debug, PartialEq)]
126 #[cfg_attr(
127     feature = "enable-serde",
128     derive(serde_derive::Deserialize, serde_derive::Serialize)
129 )]
130 pub struct UserStackMap {
131     // Offsets into the frame's sized stack slots that are GC references, by type.
132     by_type: SmallVec<[(ir::Type, CompoundBitSet); 1]>,
133 
134     // The offset of the sized stack slots, from SP, for this stack map's
135     // associated PC.
136     //
137     // This is initially `None` upon construction during lowering, but filled in
138     // after regalloc during emission when we have the precise frame layout.
139     sp_to_sized_stack_slots: Option<u32>,
140 }
141 
142 impl UserStackMap {
143     /// Coalesce the given entries into a new `UserStackMap`.
new( entries: &[UserStackMapEntry], stack_slot_offsets: &PrimaryMap<ir::StackSlot, u32>, ) -> Self144     pub(crate) fn new(
145         entries: &[UserStackMapEntry],
146         stack_slot_offsets: &PrimaryMap<ir::StackSlot, u32>,
147     ) -> Self {
148         let mut by_type = SmallVec::<[(ir::Type, CompoundBitSet); 1]>::default();
149 
150         for entry in entries {
151             let offset = stack_slot_offsets[entry.slot] + entry.offset;
152             let offset = usize::try_from(offset).unwrap();
153 
154             // Don't bother trying to avoid an `O(n)` search here: `n` is
155             // basically always one in practice; even if it isn't, there aren't
156             // that many different CLIF types.
157             let index = by_type
158                 .iter()
159                 .position(|(ty, _)| *ty == entry.ty)
160                 .unwrap_or_else(|| {
161                     by_type.push((entry.ty, CompoundBitSet::with_capacity(offset + 1)));
162                     by_type.len() - 1
163                 });
164 
165             by_type[index].1.insert(offset);
166         }
167 
168         UserStackMap {
169             by_type,
170             sp_to_sized_stack_slots: None,
171         }
172     }
173 
174     /// Finalize this stack map by filling in the SP-to-stack-slots offset.
finalize(&mut self, sp_to_sized_stack_slots: u32)175     pub(crate) fn finalize(&mut self, sp_to_sized_stack_slots: u32) {
176         debug_assert!(self.sp_to_sized_stack_slots.is_none());
177         self.sp_to_sized_stack_slots = Some(sp_to_sized_stack_slots);
178     }
179 
180     /// Iterate over the entries in this stack map.
181     ///
182     /// Yields pairs of the type of GC reference that is at the offset, and the
183     /// offset from SP. If a pair `(i64, 0x42)` is yielded, for example, then
184     /// when execution is at this stack map's associated PC, `SP + 0x42` is a
185     /// pointer to an `i64`, and that `i64` is a live GC reference.
entries(&self) -> impl Iterator<Item = (ir::Type, u32)> + '_186     pub fn entries(&self) -> impl Iterator<Item = (ir::Type, u32)> + '_ {
187         let sp_to_sized_stack_slots = self.sp_to_sized_stack_slots.expect(
188             "`sp_to_sized_stack_slots` should have been filled in before this stack map was used",
189         );
190         self.by_type.iter().flat_map(move |(ty, bitset)| {
191             bitset.iter().map(move |slot_offset| {
192                 (
193                     *ty,
194                     sp_to_sized_stack_slots + u32::try_from(slot_offset).unwrap(),
195                 )
196             })
197         })
198     }
199 }
200