1 use crate::bitset::BitSet; 2 use crate::ir; 3 use crate::isa::TargetIsa; 4 use alloc::vec::Vec; 5 6 type Num = u32; 7 const NUM_BITS: usize = core::mem::size_of::<Num>() * 8; 8 9 /// Stack maps record which words in a stack frame contain live GC references at 10 /// a given instruction pointer. 11 /// 12 /// Logically, a set of stack maps for a function record a table of the form: 13 /// 14 /// ```text 15 /// +---------------------+-------------------------------------------+ 16 /// | Instruction Pointer | SP-Relative Offsets of Live GC References | 17 /// +---------------------+-------------------------------------------+ 18 /// | 0x12345678 | 2, 6, 12 | 19 /// | 0x1234abcd | 2, 6 | 20 /// | ... | ... | 21 /// +---------------------+-------------------------------------------+ 22 /// ``` 23 /// 24 /// Where "instruction pointer" is an instruction pointer within the function, 25 /// and "offsets of live GC references" contains the offsets (in units of words) 26 /// from the frame's stack pointer where live GC references are stored on the 27 /// stack. Instruction pointers within the function that do not have an entry in 28 /// this table are not GC safepoints. 29 /// 30 /// Because 31 /// 32 /// * offsets of live GC references are relative from the stack pointer, and 33 /// * stack frames grow down from higher addresses to lower addresses, 34 /// 35 /// to get a pointer to a live reference at offset `x` within a stack frame, you 36 /// add `x` from the frame's stack pointer. 37 /// 38 /// For example, to calculate the pointer to the live GC reference inside "frame 39 /// 1" below, you would do `frame_1_sp + x`: 40 /// 41 /// ```text 42 /// Stack 43 /// +-------------------+ 44 /// | Frame 0 | 45 /// | | 46 /// | | | 47 /// | +-------------------+ <--- Frame 0's SP 48 /// | | Frame 1 | 49 /// Grows | | 50 /// down | | 51 /// | | Live GC reference | --+-- 52 /// | | | | 53 /// | | | | 54 /// V | | x = offset of live GC reference 55 /// | | | 56 /// | | | 57 /// +-------------------+ --+-- <--- Frame 1's SP 58 /// | Frame 2 | 59 /// | ... | 60 /// ``` 61 /// 62 /// An individual `StackMap` is associated with just one instruction pointer 63 /// within the function, contains the size of the stack frame, and represents 64 /// the stack frame as a bitmap. There is one bit per word in the stack frame, 65 /// and if the bit is set, then the word contains a live GC reference. 66 /// 67 /// Note that a caller's `OutgoingArg` stack slots and callee's `IncomingArg` 68 /// stack slots overlap, so we must choose which function's stack maps record 69 /// live GC references in these slots. We record the `IncomingArg`s in the 70 /// callee's stack map. 71 #[derive(Clone, Debug, PartialEq, Eq)] 72 #[cfg_attr(feature = "enable-serde", derive(serde::Deserialize, serde::Serialize))] 73 pub struct StackMap { 74 bitmap: Vec<BitSet<Num>>, 75 mapped_words: u32, 76 } 77 78 impl StackMap { 79 /// Create a `StackMap` based on where references are located on a 80 /// function's stack. from_values( args: &[ir::entities::Value], func: &ir::Function, isa: &dyn TargetIsa, ) -> Self81 pub fn from_values( 82 args: &[ir::entities::Value], 83 func: &ir::Function, 84 isa: &dyn TargetIsa, 85 ) -> Self { 86 let loc = &func.locations; 87 let mut live_ref_in_stack_slot = crate::HashSet::new(); 88 // References can be in registers, and live registers values are pushed onto the stack before calls and traps. 89 // TODO: Implement register maps. If a register containing a reference is spilled and reused after a safepoint, 90 // it could contain a stale reference value if the garbage collector relocated the value. 91 for val in args { 92 if let Some(value_loc) = loc.get(*val) { 93 match *value_loc { 94 ir::ValueLoc::Stack(stack_slot) => { 95 live_ref_in_stack_slot.insert(stack_slot); 96 } 97 _ => {} 98 } 99 } 100 } 101 102 let stack = &func.stack_slots; 103 let info = func.stack_slots.layout_info.unwrap(); 104 105 // Refer to the doc comment for `StackMap` above to understand the 106 // bitmap representation used here. 107 let map_size = (info.frame_size + info.inbound_args_size) as usize; 108 let word_size = isa.pointer_bytes() as usize; 109 let num_words = map_size / word_size; 110 111 let mut vec = alloc::vec::Vec::with_capacity(num_words); 112 vec.resize(num_words, false); 113 114 for (ss, ssd) in stack.iter() { 115 if !live_ref_in_stack_slot.contains(&ss) 116 || ssd.kind == ir::stackslot::StackSlotKind::OutgoingArg 117 { 118 continue; 119 } 120 121 debug_assert!(ssd.size as usize == word_size); 122 let bytes_from_bottom = info.frame_size as i32 + ssd.offset.unwrap(); 123 let words_from_bottom = (bytes_from_bottom as usize) / word_size; 124 vec[words_from_bottom] = true; 125 } 126 127 Self::from_slice(&vec) 128 } 129 130 /// Create a vec of Bitsets from a slice of bools. from_slice(vec: &[bool]) -> Self131 pub fn from_slice(vec: &[bool]) -> Self { 132 let len = vec.len(); 133 let num_word = len / NUM_BITS + (len % NUM_BITS != 0) as usize; 134 let mut bitmap = Vec::with_capacity(num_word); 135 136 for segment in vec.chunks(NUM_BITS) { 137 let mut curr_word = 0; 138 for (i, set) in segment.iter().enumerate() { 139 if *set { 140 curr_word |= 1 << i; 141 } 142 } 143 bitmap.push(BitSet(curr_word)); 144 } 145 Self { 146 mapped_words: len as u32, 147 bitmap, 148 } 149 } 150 151 /// Returns a specified bit. get_bit(&self, bit_index: usize) -> bool152 pub fn get_bit(&self, bit_index: usize) -> bool { 153 assert!(bit_index < NUM_BITS * self.bitmap.len()); 154 let word_index = bit_index / NUM_BITS; 155 let word_offset = (bit_index % NUM_BITS) as u8; 156 self.bitmap[word_index].contains(word_offset) 157 } 158 159 /// Returns the raw bitmap that represents this stack map. as_slice(&self) -> &[BitSet<u32>]160 pub fn as_slice(&self) -> &[BitSet<u32>] { 161 &self.bitmap 162 } 163 164 /// Returns the number of words represented by this stack map. mapped_words(&self) -> u32165 pub fn mapped_words(&self) -> u32 { 166 self.mapped_words 167 } 168 } 169 170 #[cfg(test)] 171 mod tests { 172 use super::*; 173 174 #[test] stack_maps()175 fn stack_maps() { 176 let vec: Vec<bool> = Vec::new(); 177 assert!(StackMap::from_slice(&vec).bitmap.is_empty()); 178 179 let mut vec: [bool; NUM_BITS] = Default::default(); 180 let set_true_idx = [5, 7, 24, 31]; 181 182 for &idx in &set_true_idx { 183 vec[idx] = true; 184 } 185 186 let mut vec = vec.to_vec(); 187 assert_eq!( 188 vec![BitSet::<Num>(2164261024)], 189 StackMap::from_slice(&vec).bitmap 190 ); 191 192 vec.push(false); 193 vec.push(true); 194 let res = StackMap::from_slice(&vec); 195 assert_eq!( 196 vec![BitSet::<Num>(2164261024), BitSet::<Num>(2)], 197 res.bitmap 198 ); 199 200 assert!(res.get_bit(5)); 201 assert!(res.get_bit(31)); 202 assert!(res.get_bit(33)); 203 assert!(!res.get_bit(1)); 204 } 205 } 206