cranelift_codegen/ir/
memflags.rs

1//! Memory operation flags.
2
3use super::TrapCode;
4use crate::HashMap;
5use crate::entity::{self, PrimaryMap};
6pub use crate::machinst::MachMemFlags;
7use alloc::borrow::Cow;
8use core::fmt;
9use core::hash::{Hash, Hasher};
10use core::ops::Index;
11use core::str::FromStr;
12use cranelift_entity::{entity_impl, packed_option::PackedOption};
13
14#[cfg(feature = "enable-serde")]
15use serde_derive::{Deserialize, Serialize};
16
17/// Endianness of a memory access.
18#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
19pub enum Endianness {
20    /// Little-endian
21    Little,
22    /// Big-endian
23    Big,
24}
25
26/// An opaque reference to an alias region.
27///
28/// Alias regions identify disjoint categories of memory for alias analysis.
29/// Two memory operations in different alias regions are known not to alias.
30#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
31#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
32pub struct AliasRegion(u32);
33entity_impl!(AliasRegion, "region");
34
35/// Data describing an alias region.
36#[derive(Clone, Debug, PartialEq, Eq, Hash)]
37#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
38pub struct AliasRegionData {
39    /// A unique, user-defined identifier for this alias region.
40    ///
41    /// Alias regions are deduplicated based on this identifier.
42    ///
43    /// This deduplication happens during inlining, for example, when a
44    /// callee's alias regions are merged with the caller's. Therefore, when
45    /// inlining is enabled this identifier should be globally unique across
46    /// the whole compilation. When inlining is disabled, it is sufficient
47    /// to be unique within the context of a single function.
48    pub user_id: u32,
49
50    /// Description of this alias region, e.g. "vmctx", "funcref table",
51    /// "global 42", or "gc struct `LinkedList` field `tail`".
52    ///
53    /// This only exists for printing in the CLIF text format.
54    pub description: Cow<'static, str>,
55}
56
57/// An opaque reference to memory operation flags stored in a
58/// [`MemFlagsSet`].
59///
60/// `MemFlags` is a u16 entity index that refers to a [`MemFlagsData`] entry in
61/// the [`MemFlagsSet`] stored in the
62/// [`DataFlowGraph`](super::dfg::DataFlowGraph).
63#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
64#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
65pub struct MemFlags(u16);
66
67impl MemFlags {
68    /// Create a new `MemFlags` from a `u32` index.
69    ///
70    /// Returns `None` if the index doesn't fit in a `u16`.
71    pub fn with_number(n: u32) -> Option<Self> {
72        let val = u16::try_from(n).ok()?;
73        if val == u16::MAX {
74            None
75        } else {
76            Some(Self(val))
77        }
78    }
79}
80
81impl entity::EntityRef for MemFlags {
82    #[inline]
83    fn new(index: usize) -> Self {
84        let val = u16::try_from(index).expect("MemFlags index overflow");
85        Self(val)
86    }
87
88    #[inline]
89    fn index(self) -> usize {
90        usize::from(self.0)
91    }
92}
93
94impl entity::packed_option::ReservedValue for MemFlags {
95    #[inline]
96    fn reserved_value() -> Self {
97        Self(u16::MAX)
98    }
99
100    #[inline]
101    fn is_reserved_value(&self) -> bool {
102        self.0 == u16::MAX
103    }
104}
105
106impl MemFlags {
107    /// Create a new instance from a `u32`.
108    #[inline]
109    pub fn from_u32(x: u32) -> Self {
110        Self(u16::try_from(x).unwrap())
111    }
112
113    /// Return the underlying index value as a `u32`.
114    #[inline]
115    pub fn as_u32(self) -> u32 {
116        u32::from(self.0)
117    }
118
119    /// Return the raw bit encoding for this instance.
120    #[inline]
121    pub fn as_bits(self) -> u32 {
122        u32::from(self.0)
123    }
124
125    /// Create a new instance from the raw bit encoding.
126    #[inline]
127    pub fn from_bits(x: u32) -> Self {
128        Self(u16::try_from(x).unwrap())
129    }
130}
131
132impl fmt::Display for MemFlags {
133    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
134        write!(f, "memflags{}", self.0)
135    }
136}
137
138impl fmt::Debug for MemFlags {
139    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
140        (self as &dyn fmt::Display).fmt(f)
141    }
142}
143
144/// Flags for memory operations like load/store.
145///
146/// Each of these flags introduce a limited form of undefined behavior. The flags each enable
147/// certain optimizations that need to make additional assumptions. Generally, the semantics of a
148/// program does not change when a flag is removed, but adding a flag will.
149///
150/// In addition, the flags determine the endianness of the memory access.  By default,
151/// any memory access uses the native endianness determined by the target ISA.  This can
152/// be overridden for individual accesses by explicitly specifying little- or big-endian
153/// semantics via the flags.
154#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
155#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
156pub struct MemFlagsData {
157    /// Backend-facing memory-operation flags.
158    flags: MachMemFlags,
159
160    /// The alias region for this memory operation, if any.
161    region: PackedOption<AliasRegion>,
162}
163
164const fn no_alias_region() -> PackedOption<AliasRegion> {
165    PackedOption::new(AliasRegion(u32::MAX))
166}
167
168impl MemFlagsData {
169    /// Create a new empty set of flags.
170    pub const fn new() -> Self {
171        Self {
172            flags: MachMemFlags::new(),
173            region: no_alias_region(),
174        }
175    }
176
177    /// Create a set of flags representing an access from a "trusted" address, meaning it's
178    /// known to be aligned and non-trapping.
179    pub const fn trusted() -> Self {
180        Self::new().with_notrap().with_aligned()
181    }
182
183    /// Reads the alias region that this memory operation works with.
184    pub fn alias_region(self) -> Option<AliasRegion> {
185        self.region.expand()
186    }
187
188    /// Sets the alias region that this works on to the specified `region`.
189    pub fn with_alias_region(mut self, region: Option<AliasRegion>) -> Self {
190        self.region = region.into();
191        self
192    }
193
194    /// Sets the alias region that this works on to the specified `region`.
195    pub fn set_alias_region(&mut self, region: Option<AliasRegion>) {
196        self.region = region.into();
197    }
198
199    /// Set a flag bit by name.
200    ///
201    /// Returns true if the flag was found and set, false for an unknown flag
202    /// name.
203    ///
204    /// # Errors
205    ///
206    /// Returns an error message if the `name` is known but couldn't be applied
207    /// due to it being a semantic error.
208    pub fn set_by_name(&mut self, name: &str) -> Result<bool, &'static str> {
209        *self = match name {
210            "notrap" => self.with_trap_code(None),
211            "aligned" => self.with_aligned(),
212            "readonly" => self.with_readonly(),
213            "little" => {
214                if self.flags.explicit_endianness() == Some(Endianness::Big) {
215                    return Err("cannot set both big and little endian bits");
216                }
217                self.with_endianness(Endianness::Little)
218            }
219            "big" => {
220                if self.flags.explicit_endianness() == Some(Endianness::Little) {
221                    return Err("cannot set both big and little endian bits");
222                }
223                self.with_endianness(Endianness::Big)
224            }
225            "can_move" => self.with_can_move(),
226
227            other => match TrapCode::from_str(other) {
228                Ok(code) => self.with_trap_code(Some(code)),
229                Err(()) => return Ok(false),
230            },
231        };
232        Ok(true)
233    }
234
235    /// Return endianness of the memory access.  This will return the endianness
236    /// explicitly specified by the flags if any, and will default to the native
237    /// endianness otherwise.  The native endianness has to be provided by the
238    /// caller since it is not explicitly encoded in CLIF IR -- this allows a
239    /// front end to create IR without having to know the target endianness.
240    pub const fn endianness(self, native_endianness: Endianness) -> Endianness {
241        self.flags.endianness(native_endianness)
242    }
243
244    /// Return endianness of the memory access, if explicitly specified.
245    ///
246    /// If the endianness is not explicitly specified, this will return `None`,
247    /// which means "native endianness".
248    pub const fn explicit_endianness(self) -> Option<Endianness> {
249        self.flags.explicit_endianness()
250    }
251
252    /// Set endianness of the memory access.
253    pub fn set_endianness(&mut self, endianness: Endianness) {
254        *self = self.with_endianness(endianness);
255    }
256
257    /// Set endianness of the memory access, returning new flags.
258    pub const fn with_endianness(mut self, endianness: Endianness) -> Self {
259        self.flags = self.flags.with_endianness(endianness);
260        self
261    }
262
263    /// Test if this memory operation cannot trap.
264    ///
265    /// By default `MemFlags` will assume that any load/store can trap and is
266    /// associated with a `TrapCode::HeapOutOfBounds` code. If the trap code is
267    /// configured to `None` though then this method will return `true` and
268    /// indicates that the memory operation will not trap.
269    ///
270    /// If this returns `true` then the memory is *accessible*, which means
271    /// that accesses will not trap. This makes it possible to delete an unused
272    /// load or a dead store instruction.
273    ///
274    /// This flag does *not* mean that the associated instruction can be
275    /// code-motioned to arbitrary places in the function so long as its data
276    /// dependencies are met. This only means that, given its current location
277    /// in the function, it will never trap. See the `can_move` method for more
278    /// details.
279    pub const fn notrap(self) -> bool {
280        self.trap_code().is_none()
281    }
282
283    /// Sets the trap code for this `MemFlagsData` to `None`.
284    pub fn set_notrap(&mut self) {
285        *self = self.with_notrap();
286    }
287
288    /// Sets the trap code for this `MemFlagsData` to `None`, returning the new
289    /// flags.
290    pub const fn with_notrap(self) -> Self {
291        self.with_trap_code(None)
292    }
293
294    /// Is this memory operation safe to move so long as its data dependencies
295    /// remain satisfied?
296    ///
297    /// If this is `true`, then it is okay to code motion this instruction to
298    /// arbitrary locations, in the function, including across blocks and
299    /// conditional branches, so long as data dependencies (and trap ordering,
300    /// if any) are upheld.
301    ///
302    /// If this is `false`, then this memory operation's safety potentially
303    /// relies upon invariants that are not reflected in its data dependencies,
304    /// and therefore it is not safe to code motion this operation. For example,
305    /// this operation could be in a block that is dominated by a control-flow
306    /// bounds check, which is not reflected in its operands, and it would be
307    /// unsafe to code motion it above the bounds check, even if its data
308    /// dependencies would still be satisfied.
309    pub const fn can_move(self) -> bool {
310        self.flags.can_move()
311    }
312
313    /// Set the `can_move` flag.
314    pub const fn set_can_move(&mut self) {
315        *self = self.with_can_move();
316    }
317
318    /// Set the `can_move` flag, returning new flags.
319    pub const fn with_can_move(mut self) -> Self {
320        self.flags = self.flags.with_can_move();
321        self
322    }
323
324    /// Test if the `aligned` flag is set.
325    ///
326    /// By default, Cranelift memory instructions work with any unaligned effective address. If the
327    /// `aligned` flag is set, the instruction is permitted to trap or return a wrong result if the
328    /// effective address is misaligned.
329    pub const fn aligned(self) -> bool {
330        self.flags.aligned()
331    }
332
333    /// Set the `aligned` flag.
334    pub fn set_aligned(&mut self) {
335        *self = self.with_aligned();
336    }
337
338    /// Set the `aligned` flag, returning new flags.
339    pub const fn with_aligned(mut self) -> Self {
340        self.flags = self.flags.with_aligned();
341        self
342    }
343
344    /// Test if the `readonly` flag is set.
345    ///
346    /// Loads with this flag have no memory dependencies.
347    /// This results in undefined behavior if the dereferenced memory is mutated at any time
348    /// between when the function is called and when it is exited.
349    pub const fn readonly(self) -> bool {
350        self.flags.readonly()
351    }
352
353    /// Set the `readonly` flag.
354    pub fn set_readonly(&mut self) {
355        *self = self.with_readonly();
356    }
357
358    /// Set the `readonly` flag, returning new flags.
359    pub const fn with_readonly(mut self) -> Self {
360        self.flags = self.flags.with_readonly();
361        self
362    }
363    /// Get the trap code to report if this memory access traps.
364    ///
365    /// A `None` trap code indicates that this memory access does not trap.
366    pub const fn trap_code(self) -> Option<TrapCode> {
367        self.flags.trap_code()
368    }
369
370    /// Configures these flags with the specified trap code `code`.
371    ///
372    /// A trap code indicates that this memory operation cannot be optimized
373    /// away and it must "stay where it is" in the programs. Traps are
374    /// considered side effects, for example, and have meaning through the trap
375    /// code that is communicated and which instruction trapped.
376    pub const fn with_trap_code(mut self, code: Option<TrapCode>) -> Self {
377        self.flags = self.flags.with_trap_code(code);
378        self
379    }
380}
381
382impl From<MemFlagsData> for MachMemFlags {
383    fn from(flags: MemFlagsData) -> Self {
384        flags.flags
385    }
386}
387
388impl From<MachMemFlags> for MemFlagsData {
389    fn from(flags: MachMemFlags) -> Self {
390        Self {
391            flags,
392            region: no_alias_region(),
393        }
394    }
395}
396
397impl fmt::Display for MemFlagsData {
398    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
399        write!(f, "{}", self.flags)?;
400        match self.alias_region() {
401            None => {}
402            Some(region) => write!(f, " {region}")?,
403        }
404        Ok(())
405    }
406}
407
408#[derive(Clone, Copy, Debug, PartialEq, Eq)]
409pub struct MemFlagsSetOverflow;
410
411/// A deduplicated set of mem flags.
412#[derive(Clone, Debug)]
413#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
414pub struct MemFlagsSet {
415    mem_flags: PrimaryMap<MemFlags, MemFlagsData>,
416    dedupe_map: HashMap<MemFlagsData, MemFlags>,
417}
418
419impl PartialEq for MemFlagsSet {
420    fn eq(&self, other: &Self) -> bool {
421        self.mem_flags == other.mem_flags
422    }
423}
424
425impl Eq for MemFlagsSet {}
426
427impl Hash for MemFlagsSet {
428    fn hash<H: Hasher>(&self, state: &mut H) {
429        self.mem_flags.hash(state);
430    }
431}
432
433impl MemFlagsSet {
434    /// Create a new empty set.
435    pub fn new() -> Self {
436        Self {
437            mem_flags: PrimaryMap::new(),
438            dedupe_map: HashMap::new(),
439        }
440    }
441
442    /// Insert new mem flags into this set.
443    ///
444    /// Returns an existing `MemFlags` if the data already exists.
445    pub fn insert(&mut self, data: MemFlagsData) -> Result<MemFlags, MemFlagsSetOverflow> {
446        if let Some(&existing) = self.dedupe_map.get(&data) {
447            return Ok(existing);
448        }
449        let next = u32::try_from(self.mem_flags.len())
450            .ok()
451            .and_then(MemFlags::with_number)
452            .ok_or(MemFlagsSetOverflow)?;
453        let key = self.mem_flags.push(data);
454        debug_assert_eq!(key, next);
455        self.dedupe_map.insert(data, key);
456        Ok(key)
457    }
458
459    /// Insert new mem flags into this set, panicking if the index does not fit.
460    pub fn insert_unchecked(&mut self, data: MemFlagsData) -> MemFlags {
461        match self.insert(data) {
462            Ok(flags) => flags,
463            Err(_) => panic!("MemFlags index overflow"),
464        }
465    }
466
467    /// Returns `true` if the given mem flags reference is valid.
468    pub fn is_valid(&self, mf: MemFlags) -> bool {
469        self.mem_flags.is_valid(mf)
470    }
471
472    /// Clear the set.
473    pub fn clear(&mut self) {
474        *self = Self::new();
475    }
476
477    /// Find the entity index for an existing [`MemFlagsData`] value.
478    pub fn get(&self, data: MemFlagsData) -> Option<MemFlags> {
479        self.dedupe_map.get(&data).copied()
480    }
481}
482
483// NB: Do not implement `IndexMut` because mem flags data is deduped and shared
484// by many instructions.
485impl Index<MemFlags> for MemFlagsSet {
486    type Output = MemFlagsData;
487
488    fn index(&self, mf: MemFlags) -> &MemFlagsData {
489        &self.mem_flags[mf]
490    }
491}
492
493/// A deduplicated set of alias regions.
494///
495/// Deduplication is based on `user_id`; the description string is not
496/// considered.
497#[derive(Clone, PartialEq)]
498#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
499pub struct AliasRegionSet {
500    alias_regions: PrimaryMap<AliasRegion, AliasRegionData>,
501    dedupe_map: HashMap<u32, AliasRegion>,
502}
503
504impl Hash for AliasRegionSet {
505    fn hash<H: Hasher>(&self, state: &mut H) {
506        self.alias_regions.hash(state);
507    }
508}
509
510impl AliasRegionSet {
511    /// Create a new empty set.
512    pub fn new() -> Self {
513        Self {
514            alias_regions: PrimaryMap::new(),
515            dedupe_map: HashMap::new(),
516        }
517    }
518
519    /// Insert a new alias region into this set.
520    ///
521    /// Returns an existing `AliasRegion` if one with the same `user_id`
522    /// already exists.
523    pub fn insert(&mut self, data: AliasRegionData) -> AliasRegion {
524        if let Some(&existing) = self.dedupe_map.get(&data.user_id) {
525            return existing;
526        }
527        let user_id = data.user_id;
528        let key = self.alias_regions.push(data);
529        self.dedupe_map.insert(user_id, key);
530        key
531    }
532
533    /// Push a new alias region, bypassing deduplication.
534    ///
535    /// This is used by the CLIF text parser to faithfully represent the
536    /// source text. The verifier will then check for duplicate `user_id`s.
537    pub fn push(&mut self, data: AliasRegionData) -> AliasRegion {
538        let user_id = data.user_id;
539        let key = self.alias_regions.push(data);
540        self.dedupe_map.insert(user_id, key);
541        key
542    }
543
544    /// Returns `true` if this set already contains a region with the given
545    /// `user_id`.
546    pub fn contains(&self, user_id: u32) -> bool {
547        self.dedupe_map.contains_key(&user_id)
548    }
549
550    /// Returns `true` if the given alias region reference is valid.
551    pub fn is_valid(&self, ar: AliasRegion) -> bool {
552        self.alias_regions.is_valid(ar)
553    }
554
555    /// Return the number of alias regions in the set.
556    pub fn len(&self) -> usize {
557        self.alias_regions.len()
558    }
559
560    /// Iterate over all alias regions and their data.
561    pub fn iter(&self) -> impl Iterator<Item = (AliasRegion, &AliasRegionData)> {
562        self.alias_regions.iter()
563    }
564
565    /// Clear the set.
566    pub fn clear(&mut self) {
567        self.alias_regions.clear();
568        self.dedupe_map.clear();
569    }
570}
571
572// NB: Do not implement `IndexMut` because alias region data is deduped and
573// shared by many mem flags.
574impl Index<AliasRegion> for AliasRegionSet {
575    type Output = AliasRegionData;
576
577    fn index(&self, ar: AliasRegion) -> &AliasRegionData {
578        &self.alias_regions[ar]
579    }
580}
581
582#[cfg(test)]
583mod tests {
584    use super::*;
585    use cranelift_entity::EntityRef;
586
587    #[test]
588    fn roundtrip_traps() {
589        for trap in TrapCode::non_user_traps().iter().copied() {
590            let _flags = MemFlagsData::new().with_trap_code(Some(trap));
591        }
592        let _flags = MemFlagsData::new().with_trap_code(None);
593    }
594
595    #[test]
596    fn cannot_set_big_and_little() {
597        let _big = MemFlagsData::new().with_endianness(Endianness::Big);
598
599        let _little = MemFlagsData::new().with_endianness(Endianness::Little);
600    }
601
602    #[test]
603    fn only_one_region() {
604        let region0 = AliasRegion::new(0);
605        let region1 = AliasRegion::new(1);
606        let flags = MemFlagsData::new().with_alias_region(Some(region0));
607        assert_eq!(flags.alias_region(), Some(region0));
608
609        let flags = flags.with_alias_region(Some(region1));
610        assert_eq!(flags.alias_region(), Some(region1));
611
612        let flags = flags.with_alias_region(None);
613        assert_eq!(flags.alias_region(), None);
614    }
615
616    #[test]
617    fn clear_removes_entries() {
618        let mut set = MemFlagsSet::new();
619        let trusted = set.insert(MemFlagsData::trusted()).unwrap();
620        let custom = MemFlagsData::new()
621            .with_endianness(Endianness::Big)
622            .with_alias_region(Some(AliasRegion::new(0)));
623        let custom_key = set.insert(custom).unwrap();
624        assert!(set.is_valid(trusted));
625        assert!(set.is_valid(custom_key));
626
627        set.clear();
628
629        assert!(!set.is_valid(trusted));
630        assert!(!set.is_valid(custom_key));
631        let trusted = set.insert(MemFlagsData::trusted()).unwrap();
632        assert_eq!(set[trusted], MemFlagsData::trusted());
633    }
634}
cranelift_codegen/ir/memflags.rs

cranelift_codegen/ir/
memflags.rs
