rucc_ir/
flags.rs

1//! Instruction flags, atomic orderings, and the read-modify-write operations.
2//!
3//! Design: `spec/08-ir.md` section 8.4.
4//!
5//! A flag is a licence the frontend grants the optimizer, and every one of them is tied to
6//! something the C standard leaves undefined. `-fwrapv` is implemented by not setting
7//! [`Flags::NSW`], and that is the whole of it.
8//!
9//! **There is no poison.** An `add nsw` that overflows does not produce a value that taints
10//! everything downstream. It produces an unspecified but stable value, meaning two reads of it
11//! agree, and `nsw` licenses only the specific rewrites the rule set proves sound under the
12//! assumption that the overflow does not happen. The cost is real, and it is that arithmetic
13//! cannot be speculated across control flow as aggressively. The benefit is that every rewrite
14//! is locally justifiable, which is what keeps the rule set verifiable, and that a wrong answer
15//! cannot travel from somewhere the user cannot see to somewhere they can.
16//!
17//! The fast-math flags sit on individual instructions rather than in a global mode, so
18//! `-ffast-math` is a decision the frontend makes per expression. That is what keeps link time
19//! optimization across a unit built with it and a unit built without it correct.
20
21use std::fmt;
22
23use crate::Opcode;
24
25/// The flags on one instruction.
26///
27/// A bitset rather than a struct of `bool`s, because it rides along in the instruction table
28/// and two bytes there is two bytes per instruction in every function in the program.
29#[derive(Clone, Copy, PartialEq, Eq, Default, Hash)]
30pub struct Flags(u16);
31
32impl Flags {
33    /// No flags, which is what `-O0` and `-fwrapv` and a plain unsigned addition all produce.
34    pub const NONE: Self = Self(0);
35
36    /// No signed wrap. Signed overflow is undefined, so the optimizer may assume it does not
37    /// happen. `-fwrapv` stops the frontend setting this and nothing else changes.
38    pub const NSW: Self = Self(1 << 0);
39    /// No unsigned wrap. Set only where the frontend knows it from the source, since C's
40    /// unsigned arithmetic wraps by definition and most unsigned arithmetic does not get this.
41    pub const NUW: Self = Self(1 << 1);
42    /// The shift or division is exact, so no bits are discarded and no remainder is dropped.
43    pub const EXACT: Self = Self(1 << 2);
44
45    /// No NaN operands or results.
46    pub const NNAN: Self = Self(1 << 3);
47    /// No infinite operands or results.
48    pub const NINF: Self = Self(1 << 4);
49    /// The sign of a zero does not matter.
50    pub const NSZ: Self = Self(1 << 5);
51    /// A division may become a multiplication by the reciprocal.
52    pub const ARCP: Self = Self(1 << 6);
53    /// A multiplication and an addition may be contracted into one rounding.
54    pub const CONTRACT: Self = Self(1 << 7);
55    /// The operation may be reassociated, which is the one that changes results the most.
56    pub const REASSOC: Self = Self(1 << 8);
57
58    /// The access is `volatile`, so it happens exactly once and is never moved or merged.
59    pub const VOLATILE: Self = Self(1 << 9);
60    /// The result does not alias anything else reachable, which is what `restrict` gives.
61    pub const NOALIAS: Self = Self(1 << 10);
62
63    /// Every fast-math flag, which is what `-ffast-math` sets on an expression.
64    pub const FAST: Self = Self(
65        Self::NNAN.0
66            | Self::NINF.0
67            | Self::NSZ.0
68            | Self::ARCP.0
69            | Self::CONTRACT.0
70            | Self::REASSOC.0,
71    );
72
73    /// The underlying bits, for the printer and for hashing an instruction.
74    #[must_use]
75    pub const fn bits(self) -> u16 {
76        self.0
77    }
78
79    /// Whether nothing is set.
80    #[must_use]
81    pub const fn is_empty(self) -> bool {
82        self.0 == 0
83    }
84
85    /// Whether every flag in `other` is set here.
86    #[must_use]
87    pub const fn contains(self, other: Self) -> bool {
88        self.0 & other.0 == other.0
89    }
90
91    /// Both sets.
92    #[must_use]
93    pub const fn union(self, other: Self) -> Self {
94        Self(self.0 | other.0)
95    }
96
97    /// The flags in both sets.
98    ///
99    /// This is what a rewrite does when it replaces two instructions with one: a licence
100    /// granted on one of them and not the other is not a licence over the result.
101    #[must_use]
102    pub const fn intersection(self, other: Self) -> Self {
103        Self(self.0 & other.0)
104    }
105
106    /// This set without the flags in `other`.
107    #[must_use]
108    pub const fn without(self, other: Self) -> Self {
109        Self(self.0 & !other.0)
110    }
111
112    /// The flags that mean anything on that opcode.
113    ///
114    /// Anything outside this is a verifier failure rather than something ignored, because a
115    /// flag on an instruction that does not read it is a flag somebody meant to put somewhere
116    /// else.
117    #[must_use]
118    pub const fn legal_on(opcode: Opcode) -> Self {
119        match opcode {
120            Opcode::Add | Opcode::Sub | Opcode::Mul | Opcode::Shl => Self::NSW.union(Self::NUW),
121            Opcode::SDiv | Opcode::UDiv | Opcode::LShr | Opcode::AShr => Self::EXACT,
122            Opcode::FAdd
123            | Opcode::FSub
124            | Opcode::FMul
125            | Opcode::FDiv
126            | Opcode::FRem
127            | Opcode::FNeg
128            | Opcode::Fma
129            | Opcode::FCmp => Self::FAST,
130            Opcode::Load | Opcode::Store | Opcode::Memcpy | Opcode::Memmove | Opcode::Memset => {
131                Self::VOLATILE
132            }
133            Opcode::InlineAsm => Self::VOLATILE,
134            Opcode::Alloca | Opcode::PtrAdd => Self::NOALIAS,
135            _ => Self::NONE,
136        }
137    }
138
139    /// Every flag that is set, with its name, in the order the printer writes them.
140    pub fn iter(self) -> impl Iterator<Item = (Self, &'static str)> {
141        NAMED.iter().copied().filter(move |&(flag, _)| self.contains(flag))
142    }
143
144    /// The flag with that name, if there is one.
145    #[must_use]
146    pub fn from_name(name: &str) -> Option<Self> {
147        NAMED.iter().find(|&&(_, named)| named == name).map(|&(flag, _)| flag)
148    }
149}
150
151impl std::ops::BitOr for Flags {
152    type Output = Self;
153
154    fn bitor(self, other: Self) -> Self {
155        self.union(other)
156    }
157}
158
159impl std::ops::BitOrAssign for Flags {
160    fn bitor_assign(&mut self, other: Self) {
161        *self = self.union(other);
162    }
163}
164
165impl fmt::Display for Flags {
166    /// The suffix form the textual IR uses, `add.nsw`, with a leading dot on each flag and
167    /// nothing at all when the set is empty.
168    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
169        for (_, name) in self.iter() {
170            write!(f, ".{name}")?;
171        }
172        Ok(())
173    }
174}
175
176impl fmt::Debug for Flags {
177    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
178        if self.is_empty() {
179            return f.write_str("Flags::NONE");
180        }
181        fmt::Display::fmt(self, f)
182    }
183}
184
185/// Each flag with its name, in printing order.
186static NAMED: &[(Flags, &str)] = &[
187    (Flags::NSW, "nsw"),
188    (Flags::NUW, "nuw"),
189    (Flags::EXACT, "exact"),
190    (Flags::NNAN, "nnan"),
191    (Flags::NINF, "ninf"),
192    (Flags::NSZ, "nsz"),
193    (Flags::ARCP, "arcp"),
194    (Flags::CONTRACT, "contract"),
195    (Flags::REASSOC, "reassoc"),
196    (Flags::VOLATILE, "volatile"),
197    (Flags::NOALIAS, "noalias"),
198];
199
200/// How strongly an atomic operation is ordered against everything around it.
201///
202/// These are C11's, minus `consume`, which every compiler in existence widens to `acquire`
203/// because nobody can implement it as specified and the standard committee has said so.
204#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
205pub enum MemOrder {
206    /// Not atomic at all, which is what an ordinary load or store is.
207    #[default]
208    NotAtomic,
209    /// Atomic, with no ordering against anything else.
210    Relaxed,
211    /// Nothing after this in program order moves before it.
212    Acquire,
213    /// Nothing before this in program order moves after it.
214    Release,
215    /// Both, for a read-modify-write.
216    AcqRel,
217    /// Both, and a single total order over every sequentially consistent operation.
218    SeqCst,
219}
220
221impl MemOrder {
222    /// The textual form.
223    #[must_use]
224    pub const fn name(self) -> &'static str {
225        match self {
226            Self::NotAtomic => "not_atomic",
227            Self::Relaxed => "relaxed",
228            Self::Acquire => "acquire",
229            Self::Release => "release",
230            Self::AcqRel => "acq_rel",
231            Self::SeqCst => "seq_cst",
232        }
233    }
234
235    /// The ordering with that name, if there is one.
236    #[must_use]
237    pub fn from_name(name: &str) -> Option<Self> {
238        Self::all().find(|order| order.name() == name)
239    }
240
241    /// Every ordering, weakest first.
242    pub fn all() -> impl Iterator<Item = Self> {
243        [Self::NotAtomic, Self::Relaxed, Self::Acquire, Self::Release, Self::AcqRel, Self::SeqCst]
244            .into_iter()
245    }
246
247    /// Whether this ordering can be asked of a load.
248    ///
249    /// A load cannot release, because there is nothing it published.
250    #[must_use]
251    pub const fn is_valid_for_load(self) -> bool {
252        matches!(self, Self::Relaxed | Self::Acquire | Self::SeqCst)
253    }
254
255    /// Whether this ordering can be asked of a store.
256    ///
257    /// A store cannot acquire, because it read nothing to synchronise with.
258    #[must_use]
259    pub const fn is_valid_for_store(self) -> bool {
260        matches!(self, Self::Relaxed | Self::Release | Self::SeqCst)
261    }
262
263    /// Whether this ordering can be asked of a read-modify-write, which is any of them.
264    #[must_use]
265    pub const fn is_valid_for_rmw(self) -> bool {
266        !matches!(self, Self::NotAtomic)
267    }
268}
269
270impl fmt::Display for MemOrder {
271    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
272        f.write_str(self.name())
273    }
274}
275
276/// Which operation an `atomic_rmw` performs.
277#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
278pub enum RmwOp {
279    /// Replace, returning the old value.
280    Xchg,
281    /// Integer addition.
282    Add,
283    /// Integer subtraction.
284    Sub,
285    /// Bitwise and.
286    And,
287    /// Bitwise and, then complement, which is the one hardware sometimes has natively.
288    Nand,
289    /// Bitwise or.
290    Or,
291    /// Bitwise exclusive or.
292    Xor,
293    /// Signed maximum.
294    SMax,
295    /// Signed minimum.
296    SMin,
297    /// Unsigned maximum.
298    UMax,
299    /// Unsigned minimum.
300    UMin,
301    /// Floating point addition.
302    FAdd,
303    /// Floating point subtraction.
304    FSub,
305}
306
307impl RmwOp {
308    /// The textual form.
309    #[must_use]
310    pub const fn name(self) -> &'static str {
311        match self {
312            Self::Xchg => "xchg",
313            Self::Add => "add",
314            Self::Sub => "sub",
315            Self::And => "and",
316            Self::Nand => "nand",
317            Self::Or => "or",
318            Self::Xor => "xor",
319            Self::SMax => "smax",
320            Self::SMin => "smin",
321            Self::UMax => "umax",
322            Self::UMin => "umin",
323            Self::FAdd => "fadd",
324            Self::FSub => "fsub",
325        }
326    }
327
328    /// The operation with that name, if there is one.
329    #[must_use]
330    pub fn from_name(name: &str) -> Option<Self> {
331        Self::all().find(|op| op.name() == name)
332    }
333
334    /// Every operation.
335    pub fn all() -> impl Iterator<Item = Self> {
336        [
337            Self::Xchg,
338            Self::Add,
339            Self::Sub,
340            Self::And,
341            Self::Nand,
342            Self::Or,
343            Self::Xor,
344            Self::SMax,
345            Self::SMin,
346            Self::UMax,
347            Self::UMin,
348            Self::FAdd,
349            Self::FSub,
350        ]
351        .into_iter()
352    }
353
354    /// Whether this operates on a floating point value rather than an integer.
355    #[must_use]
356    pub const fn is_float(self) -> bool {
357        matches!(self, Self::FAdd | Self::FSub)
358    }
359}
360
361impl fmt::Display for RmwOp {
362    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
363        f.write_str(self.name())
364    }
365}
366
367/// What kind of storage a memory safety instance is, which is `class` of
368/// `spec/safe-memory/04-safety-model.md` section 4.1.
369///
370/// It is on `meta_begin` because judgement J4 writes it when the instance is created, and the
371/// one place it is read afterwards is J6: `free` is permitted on an allocated instance and on
372/// no other kind, which is what makes freeing a stack address a report rather than a crash in
373/// the allocator.
374#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
375pub enum StorageClass {
376    /// A global or a static local, which lives as long as the program does.
377    Static,
378    /// A local, which lives as long as its block does.
379    Automatic,
380    /// Storage an allocator handed out, and the only kind `free` may be given.
381    Allocated,
382    /// A mapping, from `mmap` or its equivalent.
383    Mapped,
384    /// A device register window, where a read is not a read of anything the program wrote.
385    Mmio,
386    /// Storage a device owns, which is what a DMA buffer is while the transfer runs.
387    Device,
388    /// A function, which is what the address of one points at.
389    Function,
390    /// A string or compound literal, which the implementation may have merged with another.
391    Literal,
392}
393
394impl StorageClass {
395    /// The textual form.
396    #[must_use]
397    pub const fn name(self) -> &'static str {
398        match self {
399            Self::Static => "static",
400            Self::Automatic => "automatic",
401            Self::Allocated => "allocated",
402            Self::Mapped => "mapped",
403            Self::Mmio => "mmio",
404            Self::Device => "device",
405            Self::Function => "function",
406            Self::Literal => "literal",
407        }
408    }
409
410    /// The class with that name, if there is one.
411    #[must_use]
412    pub fn from_name(name: &str) -> Option<Self> {
413        Self::all().find(|class| class.name() == name)
414    }
415
416    /// Every class, in the order document 04 lists them.
417    pub fn all() -> impl Iterator<Item = Self> {
418        [
419            Self::Static,
420            Self::Automatic,
421            Self::Allocated,
422            Self::Mapped,
423            Self::Mmio,
424            Self::Device,
425            Self::Function,
426            Self::Literal,
427        ]
428        .into_iter()
429    }
430}
431
432impl fmt::Display for StorageClass {
433    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
434        f.write_str(self.name())
435    }
436}
437
438/// Who a range of memory belongs to while it is out of the monitor's authority.
439///
440/// Judgement J7 of `spec/safe-memory/04-safety-model.md`, which is the one that has no analogue
441/// in any existing tool. A range handed to a device is a range the program must not touch until
442/// it comes back, and saying which of the three it went to is what lets the report name what the
443/// program broke rather than only that it broke something.
444#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
445pub enum Owner {
446    /// A device, which is what the DMA ownership contract hands a buffer to.
447    Device,
448    /// Code compiled without the instrumentation, per document 10.
449    Uninstrumented,
450    /// The kernel, across a system call that writes into the range.
451    Kernel,
452}
453
454impl Owner {
455    /// The textual form.
456    #[must_use]
457    pub const fn name(self) -> &'static str {
458        match self {
459            Self::Device => "device",
460            Self::Uninstrumented => "uninstrumented",
461            Self::Kernel => "kernel",
462        }
463    }
464
465    /// The owner with that name, if there is one.
466    #[must_use]
467    pub fn from_name(name: &str) -> Option<Self> {
468        Self::all().find(|owner| owner.name() == name)
469    }
470
471    /// Every owner.
472    pub fn all() -> impl Iterator<Item = Self> {
473        [Self::Device, Self::Uninstrumented, Self::Kernel].into_iter()
474    }
475}
476
477impl fmt::Display for Owner {
478    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
479        f.write_str(self.name())
480    }
481}
482
483#[cfg(test)]
484mod tests {
485    use super::*;
486
487    #[test]
488    fn a_flag_set_is_two_bytes() {
489        assert_eq!(size_of::<Flags>(), 2);
490    }
491
492    #[test]
493    fn every_flag_has_a_name_and_finds_it_again() {
494        for &(flag, name) in NAMED {
495            assert_eq!(Flags::from_name(name), Some(flag), "{name}");
496            assert_eq!(flag.to_string(), format!(".{name}"));
497        }
498        assert_eq!(Flags::from_name("poison"), None);
499        assert_eq!(Flags::from_name(""), None);
500    }
501
502    #[test]
503    fn no_two_flags_share_a_bit() {
504        let mut seen = 0u16;
505        for &(flag, name) in NAMED {
506            assert_eq!(flag.bits().count_ones(), 1, "{name} is not one bit");
507            assert_eq!(seen & flag.bits(), 0, "{name} shares a bit");
508            seen |= flag.bits();
509        }
510    }
511
512    #[test]
513    fn fast_is_exactly_the_six_fast_math_flags() {
514        let named: Vec<&str> = Flags::FAST.iter().map(|(_, name)| name).collect();
515        assert_eq!(named, ["nnan", "ninf", "nsz", "arcp", "contract", "reassoc"]);
516        assert!(!Flags::FAST.contains(Flags::NSW));
517        assert!(!Flags::FAST.contains(Flags::VOLATILE));
518    }
519
520    #[test]
521    fn the_empty_set_prints_as_nothing() {
522        assert!(Flags::NONE.is_empty());
523        assert_eq!(Flags::NONE.to_string(), "");
524        assert_eq!(Flags::NONE.iter().count(), 0);
525    }
526
527    #[test]
528    fn flags_print_as_the_suffix_the_textual_form_uses() {
529        assert_eq!((Flags::NSW | Flags::NUW).to_string(), ".nsw.nuw");
530        // Whatever order they were combined in, the printer writes them in one order, which
531        // is what a byte for byte round trip needs.
532        assert_eq!((Flags::NUW | Flags::NSW).to_string(), ".nsw.nuw");
533    }
534
535    #[test]
536    fn intersecting_is_what_a_rewrite_keeps() {
537        let one = Flags::NSW | Flags::NUW;
538        let other = Flags::NSW;
539        assert_eq!(one.intersection(other), Flags::NSW);
540        assert_eq!(one.without(Flags::NSW), Flags::NUW);
541        assert!(one.contains(Flags::NSW));
542        assert!(!other.contains(Flags::NUW));
543    }
544
545    #[test]
546    fn wrapping_flags_go_on_arithmetic_and_nowhere_else() {
547        assert!(Flags::legal_on(Opcode::Add).contains(Flags::NSW));
548        assert!(Flags::legal_on(Opcode::Shl).contains(Flags::NUW));
549        assert!(!Flags::legal_on(Opcode::Add).contains(Flags::EXACT));
550        assert!(!Flags::legal_on(Opcode::FAdd).contains(Flags::NSW));
551        assert!(!Flags::legal_on(Opcode::Load).contains(Flags::NSW));
552        assert!(Flags::legal_on(Opcode::SDiv).contains(Flags::EXACT));
553        assert!(Flags::legal_on(Opcode::FMul).contains(Flags::CONTRACT));
554        assert!(Flags::legal_on(Opcode::Store).contains(Flags::VOLATILE));
555        assert!(Flags::legal_on(Opcode::Jump).is_empty());
556    }
557
558    #[test]
559    fn every_flag_is_legal_on_something() {
560        for &(flag, name) in NAMED {
561            assert!(
562                Opcode::all().any(|op| Flags::legal_on(op).contains(flag)),
563                "{name} is legal nowhere, so nothing can ever set it"
564            );
565        }
566    }
567
568    #[test]
569    fn a_load_cannot_release_and_a_store_cannot_acquire() {
570        assert!(MemOrder::Acquire.is_valid_for_load());
571        assert!(!MemOrder::Release.is_valid_for_load());
572        assert!(!MemOrder::AcqRel.is_valid_for_load());
573        assert!(MemOrder::Release.is_valid_for_store());
574        assert!(!MemOrder::Acquire.is_valid_for_store());
575        assert!(MemOrder::SeqCst.is_valid_for_load());
576        assert!(MemOrder::SeqCst.is_valid_for_store());
577    }
578
579    #[test]
580    fn not_atomic_is_valid_for_no_atomic_operation() {
581        assert!(!MemOrder::NotAtomic.is_valid_for_load());
582        assert!(!MemOrder::NotAtomic.is_valid_for_store());
583        assert!(!MemOrder::NotAtomic.is_valid_for_rmw());
584        assert_eq!(MemOrder::default(), MemOrder::NotAtomic);
585    }
586
587    #[test]
588    fn every_ordering_and_operation_finds_its_name_again() {
589        for order in MemOrder::all() {
590            assert_eq!(MemOrder::from_name(order.name()), Some(order));
591        }
592        for op in RmwOp::all() {
593            assert_eq!(RmwOp::from_name(op.name()), Some(op));
594        }
595        assert_eq!(MemOrder::from_name("consume"), None);
596        assert_eq!(RmwOp::from_name("fmul"), None);
597    }
598
599    #[test]
600    fn the_floating_read_modify_writes_are_the_two_that_have_one() {
601        let floats: Vec<&str> = RmwOp::all().filter(|op| op.is_float()).map(RmwOp::name).collect();
602        assert_eq!(floats, ["fadd", "fsub"]);
603    }
604
605    #[test]
606    fn every_storage_class_and_owner_finds_its_name_again() {
607        for class in StorageClass::all() {
608            assert_eq!(StorageClass::from_name(class.name()), Some(class));
609        }
610        for owner in Owner::all() {
611            assert_eq!(Owner::from_name(owner.name()), Some(owner));
612        }
613        // The eight of document 04 and no more. `heap` is what a reader would guess and the
614        // model does not have it, since what the allocator hands out is `allocated`.
615        assert_eq!(StorageClass::all().count(), 8);
616        assert_eq!(StorageClass::from_name("heap"), None);
617        assert_eq!(Owner::from_name("hardware"), None);
618    }
619}
rucc_ir/flags.rs

rucc_ir/
flags.rs
