cranelift_interpreter/
frame.rs

1//! Implements a call frame (activation record) for the Cranelift interpreter.
2
3use cranelift_codegen::data_value::DataValue;
4use cranelift_codegen::ir::{types, Function, Value as ValueRef};
5use cranelift_entity::EntityRef;
6use log::trace;
7
8/// The type used for ensuring [Frame](crate::frame::Frame) entries conform to the expected memory layout.
9pub(crate) type Entries = Vec<Option<DataValue>>;
10
11/// Holds the mutable elements of an interpreted function call.
12#[derive(Debug)]
13pub 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
21impl<'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.
24    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]
35    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`.
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]
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`.
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).
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.
100    pub fn entries_mut(&mut self) -> &mut [Option<DataValue>] {
101        &mut self.registers
102    }
103
104    /// Accessor for the [`Function`] of this frame.
105    pub fn function(&self) -> &'a Function {
106        self.function
107    }
108}
109
110#[cfg(test)]
111mod tests {
112    use super::*;
113    use cranelift_codegen::ir::immediates::{Ieee32, Ieee64};
114    use cranelift_codegen::ir::InstBuilder;
115    use cranelift_frontend::{FunctionBuilder, FunctionBuilderContext};
116    use cranelift_reader::parse_functions;
117
118    /// Helper to create a function from CLIF IR.
119    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.
124    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]
135    fn construction() {
136        let func = empty_function();
137        // Construction should not fail.
138        Frame::new(&func);
139    }
140
141    #[test]
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]
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()")]
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()")]
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")]
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")]
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")]
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}
cranelift_interpreter/frame.rs

cranelift_interpreter/
frame.rs
