1 //! Implements a call frame (activation record) for the Cranelift interpreter. 2 3 use cranelift_codegen::data_value::DataValue; 4 use cranelift_codegen::ir::{Function, Value as ValueRef, types}; 5 use cranelift_entity::EntityRef; 6 use log::trace; 7 8 /// The type used for ensuring [Frame](crate::frame::Frame) entries conform to the expected memory layout. 9 pub(crate) type Entries = Vec<Option<DataValue>>; 10 11 /// Holds the mutable elements of an interpreted function call. 12 #[derive(Debug)] 13 pub struct Frame<'a> { 14 /// The currently executing function. 15 function: &'a Function, 16 /// The current mapping of SSA value-references to their actual values. For efficiency, each SSA value is used as an 17 /// index into the Vec, meaning some slots may be unused. 18 registers: Entries, 19 } 20 21 impl<'a> Frame<'a> { 22 /// Construct a new [Frame] for a function. This allocates a slot in the hash map for each SSA `Value` (renamed to 23 /// `ValueRef` here) which should mean that no additional allocations are needed while interpreting the frame. new(function: &'a Function) -> Self24 pub fn new(function: &'a Function) -> Self { 25 let num_slots = function.dfg.num_values(); 26 trace!("Create new frame for function: {}", function.signature); 27 Self { 28 function, 29 registers: vec![None; num_slots], 30 } 31 } 32 33 /// Retrieve the actual value associated with an SSA reference. 34 #[inline] get(&self, name: ValueRef) -> &DataValue35 pub fn get(&self, name: ValueRef) -> &DataValue { 36 assert!(name.index() < self.registers.len()); 37 trace!("Get {name}"); 38 &self 39 .registers 40 .get(name.index()) 41 .unwrap_or_else(|| panic!("unknown value: {name}")) 42 .as_ref() 43 .or_else(|| { 44 // We couldn't find the `name` value directly in `registers`, but it is still 45 // possible that it is aliased to another value. 46 47 // If we are looking up an undefined value it will have an invalid type, return 48 // before trying to resolve it. 49 if self.function.dfg.value_type(name) == types::INVALID { 50 return None; 51 } 52 53 let alias = self.function.dfg.resolve_aliases(name); 54 self.registers 55 .get(alias.index()) 56 .unwrap_or_else(|| panic!("unknown value: {alias}")) 57 .as_ref() 58 }) 59 .unwrap_or_else(|| panic!("empty slot: {name}")) 60 } 61 62 /// Retrieve multiple SSA references; see `get`. get_all(&self, names: &[ValueRef]) -> Vec<DataValue>63 pub fn get_all(&self, names: &[ValueRef]) -> Vec<DataValue> { 64 names.iter().map(|r| self.get(*r)).cloned().collect() 65 } 66 67 /// Assign `value` to the SSA reference `name`. 68 #[inline] set(&mut self, name: ValueRef, value: DataValue) -> Option<DataValue>69 pub fn set(&mut self, name: ValueRef, value: DataValue) -> Option<DataValue> { 70 assert!(name.index() < self.registers.len()); 71 trace!("Set {name} -> {value}"); 72 std::mem::replace(&mut self.registers[name.index()], Some(value)) 73 } 74 75 /// Assign to multiple SSA references; see `set`. set_all(&mut self, names: &[ValueRef], values: Vec<DataValue>)76 pub fn set_all(&mut self, names: &[ValueRef], values: Vec<DataValue>) { 77 assert_eq!(names.len(), values.len()); 78 for (n, v) in names.iter().zip(values) { 79 self.set(*n, v); 80 } 81 } 82 83 /// Rename all of the SSA references in `old_names` to those in `new_names`. This will remove 84 /// any old references that are not in `old_names`. TODO This performs an extra allocation that 85 /// could be removed if we copied the values in the right order (i.e. when modifying in place, 86 /// we need to avoid changing a value before it is referenced). rename(&mut self, old_names: &[ValueRef], new_names: &[ValueRef])87 pub fn rename(&mut self, old_names: &[ValueRef], new_names: &[ValueRef]) { 88 trace!("Renaming {old_names:?} -> {new_names:?}"); 89 assert_eq!(old_names.len(), new_names.len()); 90 let new_registers = vec![None; self.registers.len()]; 91 let mut old_registers = std::mem::replace(&mut self.registers, new_registers); 92 self.registers = vec![None; self.registers.len()]; 93 for (&on, &nn) in old_names.iter().zip(new_names) { 94 let value = std::mem::replace(&mut old_registers[on.index()], None); 95 self.registers[nn.index()] = value; 96 } 97 } 98 99 /// Accessor for the current entries in the frame. entries_mut(&mut self) -> &mut [Option<DataValue>]100 pub fn entries_mut(&mut self) -> &mut [Option<DataValue>] { 101 &mut self.registers 102 } 103 104 /// Accessor for the [`Function`] of this frame. function(&self) -> &'a Function105 pub fn function(&self) -> &'a Function { 106 self.function 107 } 108 } 109 110 #[cfg(test)] 111 mod tests { 112 use super::*; 113 use cranelift_codegen::ir::InstBuilder; 114 use cranelift_codegen::ir::immediates::{Ieee32, Ieee64}; 115 use cranelift_frontend::{FunctionBuilder, FunctionBuilderContext}; 116 use cranelift_reader::parse_functions; 117 118 /// Helper to create a function from CLIF IR. function(code: &str) -> Function119 fn function(code: &str) -> Function { 120 parse_functions(code).unwrap().into_iter().next().unwrap() 121 } 122 123 /// Build an empty function with a single return. empty_function() -> Function124 fn empty_function() -> Function { 125 let mut func = Function::new(); 126 let mut context = FunctionBuilderContext::new(); 127 let mut builder = FunctionBuilder::new(&mut func, &mut context); 128 let block = builder.create_block(); 129 builder.switch_to_block(block); 130 builder.ins().return_(&[]); 131 func 132 } 133 134 #[test] construction()135 fn construction() { 136 let func = empty_function(); 137 // Construction should not fail. 138 Frame::new(&func); 139 } 140 141 #[test] assignment_and_retrieval()142 fn assignment_and_retrieval() { 143 let func = function("function %test(i32) -> i32 { block0(v0:i32): return v0 }"); 144 let mut frame = Frame::new(&func); 145 let ssa_value_ref = ValueRef::from_u32(0); 146 let fortytwo = DataValue::I32(42); 147 148 // Verify that setting a valid SSA ref will make the value retrievable. 149 frame.set(ssa_value_ref, fortytwo.clone()); 150 assert_eq!(frame.get(ssa_value_ref), &fortytwo); 151 } 152 153 #[test] assignment_to_extra_slots()154 fn assignment_to_extra_slots() { 155 let func = function("function %test(i32) -> i32 { block0(v10:i32): return v10 }"); 156 let mut frame = Frame::new(&func); 157 let ssa_value_ref = ValueRef::from_u32(5); 158 let fortytwo = DataValue::I32(42); 159 160 // Due to how Cranelift organizes its SSA values, the use of v10 defines 11 slots for values 161 // to fit in--the following should work. 162 frame.set(ssa_value_ref, fortytwo.clone()); 163 assert_eq!(frame.get(ssa_value_ref), &fortytwo); 164 } 165 166 #[test] 167 #[should_panic(expected = "assertion failed: name.index() < self.registers.len()")] invalid_assignment()168 fn invalid_assignment() { 169 let func = function("function %test(i32) -> i32 { block0(v10:i32): return v10 }"); 170 let mut frame = Frame::new(&func); 171 let fortytwo = DataValue::I32(42); 172 173 // Since the SSA value ref points to 42 and the function only has 11 slots, this should 174 // fail. TODO currently this is a panic under the assumption we will not set indexes outside 175 // of the valid SSA value range but it might be better as a result. 176 frame.set(ValueRef::from_u32(11), fortytwo.clone()); 177 } 178 179 #[test] 180 #[should_panic(expected = "assertion failed: name.index() < self.registers.len()")] retrieve_nonexistent_value()181 fn retrieve_nonexistent_value() { 182 let func = empty_function(); 183 let frame = Frame::new(&func); 184 let ssa_value_ref = ValueRef::from_u32(1); 185 186 // Retrieving a non-existent value should return an error. 187 frame.get(ssa_value_ref); 188 } 189 190 #[test] 191 #[should_panic(expected = "empty slot: v5")] retrieve_and_assign_multiple_values()192 fn retrieve_and_assign_multiple_values() { 193 let func = function("function %test(i32) -> i32 { block0(v10:i32): return v10 }"); 194 let mut frame = Frame::new(&func); 195 let ssa_value_refs = [ 196 ValueRef::from_u32(2), 197 ValueRef::from_u32(4), 198 ValueRef::from_u32(6), 199 ]; 200 let values = vec![ 201 DataValue::I8(1), 202 DataValue::I8(42), 203 DataValue::F32(Ieee32::from(0.42)), 204 ]; 205 206 // We can assign and retrieve multiple (cloned) values. 207 frame.set_all(&ssa_value_refs, values.clone()); 208 let retrieved_values = frame.get_all(&ssa_value_refs); 209 assert_eq!(values, retrieved_values); 210 211 // But if we attempt to retrieve an invalid value we should get an error: 212 frame.get_all(&[ValueRef::from_u32(2), ValueRef::from_u32(5)]); 213 } 214 215 #[test] 216 #[should_panic(expected = "empty slot: v10")] rename()217 fn rename() { 218 let func = function("function %test(i32) -> i32 { block0(v10:i32): return v10 }"); 219 let mut frame = Frame::new(&func); 220 let old_ssa_value_refs = [ValueRef::from_u32(9), ValueRef::from_u32(10)]; 221 let values = vec![DataValue::I8(1), DataValue::F64(Ieee64::from(0.0))]; 222 frame.set_all(&old_ssa_value_refs, values.clone()); 223 224 // Rename the old SSA values to the new values. 225 let new_ssa_value_refs = [ValueRef::from_u32(4), ValueRef::from_u32(2)]; 226 frame.rename(&old_ssa_value_refs, &new_ssa_value_refs); 227 228 // Now we should be able to retrieve new values and the old ones should fail. 229 assert_eq!(frame.get_all(&new_ssa_value_refs), values); 230 frame.get(ValueRef::from_u32(10)); 231 } 232 233 #[test] 234 #[should_panic(expected = "empty slot: v2")] rename_duplicates_causes_inconsistency()235 fn rename_duplicates_causes_inconsistency() { 236 let func = function("function %test(i32) -> i32 { block0(v10:i32): return v10 }"); 237 let mut frame = Frame::new(&func); 238 let old_ssa_value_refs = [ValueRef::from_u32(1), ValueRef::from_u32(9)]; 239 let values = vec![DataValue::I8(1), DataValue::F64(Ieee64::from(f64::NAN))]; 240 frame.set_all(&old_ssa_value_refs, values.clone()); 241 242 // Rename the old SSA values to the new values. 243 let old_duplicated_ssa_value_refs = [ValueRef::from_u32(1), ValueRef::from_u32(1)]; 244 let new_ssa_value_refs = [ValueRef::from_u32(4), ValueRef::from_u32(2)]; 245 frame.rename(&old_duplicated_ssa_value_refs, &new_ssa_value_refs); 246 247 // If we use duplicates then subsequent renamings (v1 -> v2) will be empty. 248 frame.get(ValueRef::from_u32(2)); 249 } 250 } 251