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 (in 29 //! contrast to the old system and its `r64` values). 30 31 use crate::ir; 32 use cranelift_bitset::CompoundBitSet; 33 use cranelift_entity::PrimaryMap; 34 use smallvec::SmallVec; 35 36 pub(crate) type UserStackMapEntryVec = SmallVec<[UserStackMapEntry; 4]>; 37 38 /// A stack map entry describes a single GC-managed value and its location on 39 /// the stack. 40 /// 41 /// A stack map entry is associated with a particular instruction, and that 42 /// instruction must be a safepoint. The GC-managed value must be stored in the 43 /// described location across this entry's instruction. 44 #[derive(Clone, Debug, PartialEq, Hash)] 45 #[cfg_attr( 46 feature = "enable-serde", 47 derive(serde_derive::Serialize, serde_derive::Deserialize) 48 )] 49 pub struct UserStackMapEntry { 50 /// The type of the value stored in this stack map entry. 51 pub ty: ir::Type, 52 53 /// The stack slot that this stack map entry is within. 54 pub slot: ir::StackSlot, 55 56 /// The offset within the stack slot where this entry's value can be found. 57 pub offset: u32, 58 } 59 60 /// A compiled stack map, describing the location of many GC-managed values. 61 /// 62 /// A stack map is associated with a particular instruction, and that 63 /// instruction is a safepoint. 64 #[derive(Clone, Debug, PartialEq)] 65 #[cfg_attr( 66 feature = "enable-serde", 67 derive(serde_derive::Deserialize, serde_derive::Serialize) 68 )] 69 pub struct UserStackMap { 70 // Offsets into the frame's sized stack slots that are GC references, by type. 71 by_type: SmallVec<[(ir::Type, CompoundBitSet); 1]>, 72 73 // The offset of the sized stack slots, from SP, for this stack map's 74 // associated PC. 75 // 76 // This is initially `None` upon construction during lowering, but filled in 77 // after regalloc during emission when we have the precise frame layout. 78 sp_to_sized_stack_slots: Option<u32>, 79 } 80 81 impl UserStackMap { 82 /// Coalesce the given entries into a new `UserStackMap`. 83 pub(crate) fn new( 84 entries: &[UserStackMapEntry], 85 stack_slot_offsets: &PrimaryMap<ir::StackSlot, u32>, 86 ) -> Self { 87 let mut by_type = SmallVec::<[(ir::Type, CompoundBitSet); 1]>::default(); 88 89 for entry in entries { 90 let offset = stack_slot_offsets[entry.slot] + entry.offset; 91 let offset = usize::try_from(offset).unwrap(); 92 93 // Don't bother trying to avoid an `O(n)` search here: `n` is 94 // basically always one in practice; even if it isn't, there aren't 95 // that many different CLIF types. 96 let index = by_type 97 .iter() 98 .position(|(ty, _)| *ty == entry.ty) 99 .unwrap_or_else(|| { 100 by_type.push((entry.ty, CompoundBitSet::with_capacity(offset + 1))); 101 by_type.len() - 1 102 }); 103 104 by_type[index].1.insert(offset); 105 } 106 107 UserStackMap { 108 by_type, 109 sp_to_sized_stack_slots: None, 110 } 111 } 112 113 /// Finalize this stack map by filling in the SP-to-stack-slots offset. 114 pub(crate) fn finalize(&mut self, sp_to_sized_stack_slots: u32) { 115 debug_assert!(self.sp_to_sized_stack_slots.is_none()); 116 self.sp_to_sized_stack_slots = Some(sp_to_sized_stack_slots); 117 } 118 119 /// Iterate over the entries in this stack map. 120 /// 121 /// Yields pairs of the type of GC reference that is at the offset, and the 122 /// offset from SP. If a pair `(i64, 0x42)` is yielded, for example, then 123 /// when execution is at this stack map's associated PC, `SP + 0x42` is a 124 /// pointer to an `i64`, and that `i64` is a live GC reference. 125 pub fn entries(&self) -> impl Iterator<Item = (ir::Type, u32)> + '_ { 126 let sp_to_sized_stack_slots = self.sp_to_sized_stack_slots.expect( 127 "`sp_to_sized_stack_slots` should have been filled in before this stack map was used", 128 ); 129 self.by_type.iter().flat_map(move |(ty, bitset)| { 130 bitset.iter().map(move |slot_offset| { 131 ( 132 *ty, 133 sp_to_sized_stack_slots + u32::try_from(slot_offset).unwrap(), 134 ) 135 }) 136 }) 137 } 138 } 139