cranelift_codegen/ir/
constant.rs

1//! Constants
2//!
3//! The constant pool defined here allows Cranelift to avoid emitting the same constant multiple
4//! times. As constants are inserted in the pool, a handle is returned; the handle is a Cranelift
5//! Entity. Inserting the same data multiple times will always return the same handle.
6//!
7//! Future work could include:
8//! - ensuring alignment of constants within the pool,
9//! - bucketing constants by size.
10
11use crate::ir::immediates::{IntoBytes, V128Imm};
12use crate::ir::Constant;
13use alloc::collections::BTreeMap;
14use alloc::vec::Vec;
15use core::fmt;
16use core::iter::FromIterator;
17use core::slice::Iter;
18use core::str::{from_utf8, FromStr};
19use cranelift_entity::EntityRef;
20
21#[cfg(feature = "enable-serde")]
22use serde::{Deserialize, Serialize};
23
24/// This type describes the actual constant data. Note that the bytes stored in this structure are
25/// expected to be in little-endian order; this is due to ease-of-use when interacting with
26/// WebAssembly values, which are [little-endian by design].
27///
28/// [little-endian by design]: https://github.com/WebAssembly/design/blob/master/Portability.md
29#[derive(Clone, Hash, Eq, PartialEq, Debug, Default, PartialOrd, Ord)]
30#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
31pub struct ConstantData(Vec<u8>);
32
33impl FromIterator<u8> for ConstantData {
34    fn from_iter<T: IntoIterator<Item = u8>>(iter: T) -> Self {
35        let v = iter.into_iter().collect();
36        Self(v)
37    }
38}
39
40impl From<Vec<u8>> for ConstantData {
41    fn from(v: Vec<u8>) -> Self {
42        Self(v)
43    }
44}
45
46impl From<&[u8]> for ConstantData {
47    fn from(v: &[u8]) -> Self {
48        Self(v.to_vec())
49    }
50}
51
52impl From<V128Imm> for ConstantData {
53    fn from(v: V128Imm) -> Self {
54        Self(v.to_vec())
55    }
56}
57
58impl ConstantData {
59    /// Return the number of bytes in the constant.
60    pub fn len(&self) -> usize {
61        self.0.len()
62    }
63
64    /// Check if the constant contains any bytes.
65    pub fn is_empty(&self) -> bool {
66        self.0.is_empty()
67    }
68
69    /// Return the data as a slice.
70    pub fn as_slice(&self) -> &[u8] {
71        self.0.as_slice()
72    }
73
74    /// Convert the data to a vector.
75    pub fn into_vec(self) -> Vec<u8> {
76        self.0
77    }
78
79    /// Iterate over the constant's bytes.
80    pub fn iter(&self) -> Iter<u8> {
81        self.0.iter()
82    }
83
84    /// Add new bytes to the constant data.
85    pub fn append(mut self, bytes: impl IntoBytes) -> Self {
86        let mut to_add = bytes.into_bytes();
87        self.0.append(&mut to_add);
88        self
89    }
90
91    /// Expand the size of the constant data to `expected_size` number of bytes by adding zeroes
92    /// in the high-order byte slots.
93    pub fn expand_to(mut self, expected_size: usize) -> Self {
94        if self.len() > expected_size {
95            panic!(
96                "The constant data is already expanded beyond {} bytes",
97                expected_size
98            )
99        }
100        self.0.resize(expected_size, 0);
101        self
102    }
103}
104
105impl fmt::Display for ConstantData {
106    /// Print the constant data in hexadecimal format, e.g. 0x000102030405060708090a0b0c0d0e0f.
107    /// This function will flip the stored order of bytes--little-endian--to the more readable
108    /// big-endian ordering.
109    ///
110    /// ```
111    /// use cranelift_codegen::ir::ConstantData;
112    /// let data = ConstantData::from([3, 2, 1, 0, 0].as_ref()); // note the little-endian order
113    /// assert_eq!(data.to_string(), "0x0000010203");
114    /// ```
115    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
116        if !self.is_empty() {
117            write!(f, "0x")?;
118            for b in self.0.iter().rev() {
119                write!(f, "{:02x}", b)?;
120            }
121        }
122        Ok(())
123    }
124}
125
126impl FromStr for ConstantData {
127    type Err = &'static str;
128
129    /// Parse a hexadecimal string to `ConstantData`. This is the inverse of `Display::fmt`.
130    ///
131    /// ```
132    /// use cranelift_codegen::ir::ConstantData;
133    /// let c: ConstantData = "0x000102".parse().unwrap();
134    /// assert_eq!(c.into_vec(), [2, 1, 0]);
135    /// ```
136    fn from_str(s: &str) -> Result<Self, &'static str> {
137        if s.len() <= 2 || &s[0..2] != "0x" {
138            return Err("Expected a hexadecimal string, e.g. 0x1234");
139        }
140
141        // clean and check the string
142        let cleaned: Vec<u8> = s[2..]
143            .as_bytes()
144            .iter()
145            .filter(|&&b| b as char != '_')
146            .cloned()
147            .collect(); // remove 0x prefix and any intervening _ characters
148
149        if cleaned.is_empty() {
150            Err("Hexadecimal string must have some digits")
151        } else if cleaned.len() % 2 != 0 {
152            Err("Hexadecimal string must have an even number of digits")
153        } else if cleaned.len() > 32 {
154            Err("Hexadecimal string has too many digits to fit in a 128-bit vector")
155        } else {
156            let mut buffer = Vec::with_capacity((s.len() - 2) / 2);
157            for i in (0..cleaned.len()).step_by(2) {
158                let pair = from_utf8(&cleaned[i..i + 2])
159                    .or_else(|_| Err("Unable to parse hexadecimal pair as UTF-8"))?;
160                let byte = u8::from_str_radix(pair, 16)
161                    .or_else(|_| Err("Unable to parse as hexadecimal"))?;
162                buffer.insert(0, byte);
163            }
164            Ok(Self(buffer))
165        }
166    }
167}
168
169/// Maintains the mapping between a constant handle (i.e.  [`Constant`](crate::ir::Constant)) and
170/// its constant data (i.e.  [`ConstantData`](crate::ir::ConstantData)).
171#[derive(Clone, PartialEq, Hash)]
172#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
173pub struct ConstantPool {
174    /// This mapping maintains the insertion order as long as Constants are created with
175    /// sequentially increasing integers.
176    ///
177    /// It is important that, by construction, no entry in that list gets removed. If that ever
178    /// need to happen, don't forget to update the `Constant` generation scheme.
179    handles_to_values: BTreeMap<Constant, ConstantData>,
180
181    /// Mapping of hashed `ConstantData` to the index into the other hashmap.
182    ///
183    /// This allows for deduplication of entries into the `handles_to_values` mapping.
184    values_to_handles: BTreeMap<ConstantData, Constant>,
185}
186
187impl ConstantPool {
188    /// Create a new constant pool instance.
189    pub fn new() -> Self {
190        Self {
191            handles_to_values: BTreeMap::new(),
192            values_to_handles: BTreeMap::new(),
193        }
194    }
195
196    /// Empty the constant pool of all data.
197    pub fn clear(&mut self) {
198        self.handles_to_values.clear();
199        self.values_to_handles.clear();
200    }
201
202    /// Insert constant data into the pool, returning a handle for later referencing; when constant
203    /// data is inserted that is a duplicate of previous constant data, the existing handle will be
204    /// returned.
205    pub fn insert(&mut self, constant_value: ConstantData) -> Constant {
206        if let Some(cst) = self.values_to_handles.get(&constant_value) {
207            return *cst;
208        }
209
210        let constant_handle = Constant::new(self.len());
211        self.set(constant_handle, constant_value);
212        constant_handle
213    }
214
215    /// Retrieve the constant data given a handle.
216    pub fn get(&self, constant_handle: Constant) -> &ConstantData {
217        assert!(self.handles_to_values.contains_key(&constant_handle));
218        self.handles_to_values.get(&constant_handle).unwrap()
219    }
220
221    /// Link a constant handle to its value. This does not de-duplicate data but does avoid
222    /// replacing any existing constant values. use `set` to tie a specific `const42` to its value;
223    /// use `insert` to add a value and return the next available `const` entity.
224    pub fn set(&mut self, constant_handle: Constant, constant_value: ConstantData) {
225        let replaced = self
226            .handles_to_values
227            .insert(constant_handle, constant_value.clone());
228        assert!(
229            replaced.is_none(),
230            "attempted to overwrite an existing constant {:?}: {:?} => {:?}",
231            constant_handle,
232            &constant_value,
233            replaced.unwrap()
234        );
235        self.values_to_handles
236            .insert(constant_value, constant_handle);
237    }
238
239    /// Iterate over the constants in insertion order.
240    pub fn iter(&self) -> impl Iterator<Item = (&Constant, &ConstantData)> {
241        self.handles_to_values.iter()
242    }
243
244    /// Iterate over mutable entries in the constant pool in insertion order.
245    pub fn entries_mut(&mut self) -> impl Iterator<Item = &mut ConstantData> {
246        self.handles_to_values.values_mut()
247    }
248
249    /// Return the number of constants in the pool.
250    pub fn len(&self) -> usize {
251        self.handles_to_values.len()
252    }
253
254    /// Return the combined size of all of the constant values in the pool.
255    pub fn byte_size(&self) -> usize {
256        self.handles_to_values.values().map(|c| c.len()).sum()
257    }
258}
259
260#[cfg(test)]
261mod tests {
262    use super::*;
263    use std::string::ToString;
264
265    #[test]
266    fn empty() {
267        let sut = ConstantPool::new();
268        assert_eq!(sut.len(), 0);
269    }
270
271    #[test]
272    fn insert() {
273        let mut sut = ConstantPool::new();
274        sut.insert(vec![1, 2, 3].into());
275        sut.insert(vec![4, 5, 6].into());
276        assert_eq!(sut.len(), 2);
277    }
278
279    #[test]
280    fn insert_duplicate() {
281        let mut sut = ConstantPool::new();
282        let a = sut.insert(vec![1, 2, 3].into());
283        sut.insert(vec![4, 5, 6].into());
284        let b = sut.insert(vec![1, 2, 3].into());
285        assert_eq!(a, b);
286    }
287
288    #[test]
289    fn clear() {
290        let mut sut = ConstantPool::new();
291        sut.insert(vec![1, 2, 3].into());
292        assert_eq!(sut.len(), 1);
293
294        sut.clear();
295        assert_eq!(sut.len(), 0);
296    }
297
298    #[test]
299    fn iteration_order() {
300        let mut sut = ConstantPool::new();
301        sut.insert(vec![1, 2, 3].into());
302        sut.insert(vec![4, 5, 6].into());
303        sut.insert(vec![1, 2, 3].into());
304        let data = sut.iter().map(|(_, v)| v).collect::<Vec<&ConstantData>>();
305        assert_eq!(data, vec![&vec![1, 2, 3].into(), &vec![4, 5, 6].into()]);
306    }
307
308    #[test]
309    fn get() {
310        let mut sut = ConstantPool::new();
311        let data = vec![1, 2, 3];
312        let handle = sut.insert(data.clone().into());
313        assert_eq!(sut.get(handle), &data.into());
314    }
315
316    #[test]
317    fn set() {
318        let mut sut = ConstantPool::new();
319        let handle = Constant::with_number(42).unwrap();
320        let data = vec![1, 2, 3];
321        sut.set(handle, data.clone().into());
322        assert_eq!(sut.get(handle), &data.into());
323    }
324
325    #[test]
326    #[should_panic]
327    fn disallow_overwriting_constant() {
328        let mut sut = ConstantPool::new();
329        let handle = Constant::with_number(42).unwrap();
330        sut.set(handle, vec![].into());
331        sut.set(handle, vec![1].into());
332    }
333
334    #[test]
335    #[should_panic]
336    fn get_nonexistent_constant() {
337        let sut = ConstantPool::new();
338        let a = Constant::with_number(42).unwrap();
339        sut.get(a); // panics, only use constants returned by ConstantPool
340    }
341
342    #[test]
343    fn display_constant_data() {
344        assert_eq!(ConstantData::from([0].as_ref()).to_string(), "0x00");
345        assert_eq!(ConstantData::from([42].as_ref()).to_string(), "0x2a");
346        assert_eq!(
347            ConstantData::from([3, 2, 1, 0].as_ref()).to_string(),
348            "0x00010203"
349        );
350        assert_eq!(
351            ConstantData::from(3735928559u32.to_le_bytes().as_ref()).to_string(),
352            "0xdeadbeef"
353        );
354        assert_eq!(
355            ConstantData::from(0x0102030405060708u64.to_le_bytes().as_ref()).to_string(),
356            "0x0102030405060708"
357        );
358    }
359
360    #[test]
361    fn iterate_over_constant_data() {
362        let c = ConstantData::from([1, 2, 3].as_ref());
363        let mut iter = c.iter();
364        assert_eq!(iter.next(), Some(&1));
365        assert_eq!(iter.next(), Some(&2));
366        assert_eq!(iter.next(), Some(&3));
367        assert_eq!(iter.next(), None);
368    }
369
370    #[test]
371    fn add_to_constant_data() {
372        let d = ConstantData::from([1, 2].as_ref());
373        let e = d.append(i16::from(3u8));
374        assert_eq!(e.into_vec(), vec![1, 2, 3, 0])
375    }
376
377    #[test]
378    fn extend_constant_data() {
379        let d = ConstantData::from([1, 2].as_ref());
380        assert_eq!(d.expand_to(4).into_vec(), vec![1, 2, 0, 0])
381    }
382
383    #[test]
384    #[should_panic]
385    fn extend_constant_data_to_invalid_length() {
386        ConstantData::from([1, 2].as_ref()).expand_to(1);
387    }
388
389    #[test]
390    fn parse_constant_data_and_restringify() {
391        // Verify that parsing of `from` succeeds and stringifies to `to`.
392        fn parse_ok(from: &str, to: &str) {
393            let parsed = from.parse::<ConstantData>().unwrap();
394            assert_eq!(parsed.to_string(), to);
395        }
396
397        // Verify that parsing of `from` fails with `error_msg`.
398        fn parse_err(from: &str, error_msg: &str) {
399            let parsed = from.parse::<ConstantData>();
400            assert!(
401                parsed.is_err(),
402                "Expected a parse error but parsing succeeded: {}",
403                from
404            );
405            assert_eq!(parsed.err().unwrap(), error_msg);
406        }
407
408        parse_ok("0x00", "0x00");
409        parse_ok("0x00000042", "0x00000042");
410        parse_ok(
411            "0x0102030405060708090a0b0c0d0e0f00",
412            "0x0102030405060708090a0b0c0d0e0f00",
413        );
414        parse_ok("0x_0000_0043_21", "0x0000004321");
415
416        parse_err("", "Expected a hexadecimal string, e.g. 0x1234");
417        parse_err("0x", "Expected a hexadecimal string, e.g. 0x1234");
418        parse_err(
419            "0x042",
420            "Hexadecimal string must have an even number of digits",
421        );
422        parse_err(
423            "0x00000000000000000000000000000000000000000000000000",
424            "Hexadecimal string has too many digits to fit in a 128-bit vector",
425        );
426        parse_err("0xrstu", "Unable to parse as hexadecimal");
427        parse_err("0x__", "Hexadecimal string must have some digits");
428    }
429
430    #[test]
431    fn verify_stored_bytes_in_constant_data() {
432        assert_eq!("0x01".parse::<ConstantData>().unwrap().into_vec(), [1]);
433        assert_eq!(ConstantData::from([1, 0].as_ref()).0, [1, 0]);
434        assert_eq!(ConstantData::from(vec![1, 0, 0, 0]).0, [1, 0, 0, 0]);
435    }
436
437    #[test]
438    fn check_constant_data_endianness_as_uimm128() {
439        fn parse_to_uimm128(from: &str) -> Vec<u8> {
440            from.parse::<ConstantData>()
441                .unwrap()
442                .expand_to(16)
443                .into_vec()
444        }
445
446        assert_eq!(
447            parse_to_uimm128("0x42"),
448            [0x42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
449        );
450        assert_eq!(
451            parse_to_uimm128("0x00"),
452            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
453        );
454        assert_eq!(
455            parse_to_uimm128("0x12345678"),
456            [0x78, 0x56, 0x34, 0x12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
457        );
458        assert_eq!(
459            parse_to_uimm128("0x1234_5678"),
460            [0x78, 0x56, 0x34, 0x12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
461        );
462    }
463}
cranelift_codegen/ir/constant.rs

cranelift_codegen/ir/
constant.rs
