diff options
Diffstat (limited to 'third_party/rust/cranelift-codegen/src/binemit/stack_map.rs')
| -rw-r--r-- | third_party/rust/cranelift-codegen/src/binemit/stack_map.rs | 205 |
1 files changed, 205 insertions, 0 deletions
diff --git a/third_party/rust/cranelift-codegen/src/binemit/stack_map.rs b/third_party/rust/cranelift-codegen/src/binemit/stack_map.rs new file mode 100644 index 0000000000..c3055a0154 --- /dev/null +++ b/third_party/rust/cranelift-codegen/src/binemit/stack_map.rs @@ -0,0 +1,205 @@ +use crate::bitset::BitSet; +use crate::ir; +use crate::isa::TargetIsa; +use alloc::vec::Vec; + +type Num = u32; +const NUM_BITS: usize = core::mem::size_of::<Num>() * 8; + +/// Stack maps record which words in a stack frame contain live GC references at +/// a given instruction pointer. +/// +/// Logically, a set of stack maps for a function record a table of the form: +/// +/// ```text +/// +---------------------+-------------------------------------------+ +/// | Instruction Pointer | SP-Relative Offsets of Live GC References | +/// +---------------------+-------------------------------------------+ +/// | 0x12345678 | 2, 6, 12 | +/// | 0x1234abcd | 2, 6 | +/// | ... | ... | +/// +---------------------+-------------------------------------------+ +/// ``` +/// +/// Where "instruction pointer" is an instruction pointer within the function, +/// and "offsets of live GC references" contains the offsets (in units of words) +/// from the frame's stack pointer where live GC references are stored on the +/// stack. Instruction pointers within the function that do not have an entry in +/// this table are not GC safepoints. +/// +/// Because +/// +/// * offsets of live GC references are relative from the stack pointer, and +/// * stack frames grow down from higher addresses to lower addresses, +/// +/// to get a pointer to a live reference at offset `x` within a stack frame, you +/// add `x` from the frame's stack pointer. +/// +/// For example, to calculate the pointer to the live GC reference inside "frame +/// 1" below, you would do `frame_1_sp + x`: +/// +/// ```text +/// Stack +/// +-------------------+ +/// | Frame 0 | +/// | | +/// | | | +/// | +-------------------+ <--- Frame 0's SP +/// | | Frame 1 | +/// Grows | | +/// down | | +/// | | Live GC reference | --+-- +/// | | | | +/// | | | | +/// V | | x = offset of live GC reference +/// | | | +/// | | | +/// +-------------------+ --+-- <--- Frame 1's SP +/// | Frame 2 | +/// | ... | +/// ``` +/// +/// An individual `StackMap` is associated with just one instruction pointer +/// within the function, contains the size of the stack frame, and represents +/// the stack frame as a bitmap. There is one bit per word in the stack frame, +/// and if the bit is set, then the word contains a live GC reference. +/// +/// Note that a caller's `OutgoingArg` stack slots and callee's `IncomingArg` +/// stack slots overlap, so we must choose which function's stack maps record +/// live GC references in these slots. We record the `IncomingArg`s in the +/// callee's stack map. +#[derive(Clone, Debug, PartialEq, Eq)] +#[cfg_attr(feature = "enable-serde", derive(serde::Deserialize, serde::Serialize))] +pub struct StackMap { + bitmap: Vec<BitSet<Num>>, + mapped_words: u32, +} + +impl StackMap { + /// Create a `StackMap` based on where references are located on a + /// function's stack. + pub fn from_values( + args: &[ir::entities::Value], + func: &ir::Function, + isa: &dyn TargetIsa, + ) -> Self { + let loc = &func.locations; + let mut live_ref_in_stack_slot = crate::HashSet::new(); + // References can be in registers, and live registers values are pushed onto the stack before calls and traps. + // TODO: Implement register maps. If a register containing a reference is spilled and reused after a safepoint, + // it could contain a stale reference value if the garbage collector relocated the value. + for val in args { + if let Some(value_loc) = loc.get(*val) { + match *value_loc { + ir::ValueLoc::Stack(stack_slot) => { + live_ref_in_stack_slot.insert(stack_slot); + } + _ => {} + } + } + } + + let stack = &func.stack_slots; + let info = func.stack_slots.layout_info.unwrap(); + + // Refer to the doc comment for `StackMap` above to understand the + // bitmap representation used here. + let map_size = (info.frame_size + info.inbound_args_size) as usize; + let word_size = isa.pointer_bytes() as usize; + let num_words = map_size / word_size; + + let mut vec = alloc::vec::Vec::with_capacity(num_words); + vec.resize(num_words, false); + + for (ss, ssd) in stack.iter() { + if !live_ref_in_stack_slot.contains(&ss) + || ssd.kind == ir::stackslot::StackSlotKind::OutgoingArg + { + continue; + } + + debug_assert!(ssd.size as usize == word_size); + let bytes_from_bottom = info.frame_size as i32 + ssd.offset.unwrap(); + let words_from_bottom = (bytes_from_bottom as usize) / word_size; + vec[words_from_bottom] = true; + } + + Self::from_slice(&vec) + } + + /// Create a vec of Bitsets from a slice of bools. + pub fn from_slice(vec: &[bool]) -> Self { + let len = vec.len(); + let num_word = len / NUM_BITS + (len % NUM_BITS != 0) as usize; + let mut bitmap = Vec::with_capacity(num_word); + + for segment in vec.chunks(NUM_BITS) { + let mut curr_word = 0; + for (i, set) in segment.iter().enumerate() { + if *set { + curr_word |= 1 << i; + } + } + bitmap.push(BitSet(curr_word)); + } + Self { + mapped_words: len as u32, + bitmap, + } + } + + /// Returns a specified bit. + pub fn get_bit(&self, bit_index: usize) -> bool { + assert!(bit_index < NUM_BITS * self.bitmap.len()); + let word_index = bit_index / NUM_BITS; + let word_offset = (bit_index % NUM_BITS) as u8; + self.bitmap[word_index].contains(word_offset) + } + + /// Returns the raw bitmap that represents this stack map. + pub fn as_slice(&self) -> &[BitSet<u32>] { + &self.bitmap + } + + /// Returns the number of words represented by this stack map. + pub fn mapped_words(&self) -> u32 { + self.mapped_words + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn stack_maps() { + let vec: Vec<bool> = Vec::new(); + assert!(StackMap::from_slice(&vec).bitmap.is_empty()); + + let mut vec: [bool; NUM_BITS] = Default::default(); + let set_true_idx = [5, 7, 24, 31]; + + for &idx in &set_true_idx { + vec[idx] = true; + } + + let mut vec = vec.to_vec(); + assert_eq!( + vec![BitSet::<Num>(2164261024)], + StackMap::from_slice(&vec).bitmap + ); + + vec.push(false); + vec.push(true); + let res = StackMap::from_slice(&vec); + assert_eq!( + vec![BitSet::<Num>(2164261024), BitSet::<Num>(2)], + res.bitmap + ); + + assert!(res.get_bit(5)); + assert!(res.get_bit(31)); + assert!(res.get_bit(33)); + assert!(!res.get_bit(1)); + } +} |