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#[cfg(test)]
368mod tests {
369    use super::*;
370
371    #[test]
372    fn a_flag_set_is_two_bytes() {
373        assert_eq!(size_of::<Flags>(), 2);
374    }
375
376    #[test]
377    fn every_flag_has_a_name_and_finds_it_again() {
378        for &(flag, name) in NAMED {
379            assert_eq!(Flags::from_name(name), Some(flag), "{name}");
380            assert_eq!(flag.to_string(), format!(".{name}"));
381        }
382        assert_eq!(Flags::from_name("poison"), None);
383        assert_eq!(Flags::from_name(""), None);
384    }
385
386    #[test]
387    fn no_two_flags_share_a_bit() {
388        let mut seen = 0u16;
389        for &(flag, name) in NAMED {
390            assert_eq!(flag.bits().count_ones(), 1, "{name} is not one bit");
391            assert_eq!(seen & flag.bits(), 0, "{name} shares a bit");
392            seen |= flag.bits();
393        }
394    }
395
396    #[test]
397    fn fast_is_exactly_the_six_fast_math_flags() {
398        let named: Vec<&str> = Flags::FAST.iter().map(|(_, name)| name).collect();
399        assert_eq!(named, ["nnan", "ninf", "nsz", "arcp", "contract", "reassoc"]);
400        assert!(!Flags::FAST.contains(Flags::NSW));
401        assert!(!Flags::FAST.contains(Flags::VOLATILE));
402    }
403
404    #[test]
405    fn the_empty_set_prints_as_nothing() {
406        assert!(Flags::NONE.is_empty());
407        assert_eq!(Flags::NONE.to_string(), "");
408        assert_eq!(Flags::NONE.iter().count(), 0);
409    }
410
411    #[test]
412    fn flags_print_as_the_suffix_the_textual_form_uses() {
413        assert_eq!((Flags::NSW | Flags::NUW).to_string(), ".nsw.nuw");
414        // Whatever order they were combined in, the printer writes them in one order, which
415        // is what a byte for byte round trip needs.
416        assert_eq!((Flags::NUW | Flags::NSW).to_string(), ".nsw.nuw");
417    }
418
419    #[test]
420    fn intersecting_is_what_a_rewrite_keeps() {
421        let one = Flags::NSW | Flags::NUW;
422        let other = Flags::NSW;
423        assert_eq!(one.intersection(other), Flags::NSW);
424        assert_eq!(one.without(Flags::NSW), Flags::NUW);
425        assert!(one.contains(Flags::NSW));
426        assert!(!other.contains(Flags::NUW));
427    }
428
429    #[test]
430    fn wrapping_flags_go_on_arithmetic_and_nowhere_else() {
431        assert!(Flags::legal_on(Opcode::Add).contains(Flags::NSW));
432        assert!(Flags::legal_on(Opcode::Shl).contains(Flags::NUW));
433        assert!(!Flags::legal_on(Opcode::Add).contains(Flags::EXACT));
434        assert!(!Flags::legal_on(Opcode::FAdd).contains(Flags::NSW));
435        assert!(!Flags::legal_on(Opcode::Load).contains(Flags::NSW));
436        assert!(Flags::legal_on(Opcode::SDiv).contains(Flags::EXACT));
437        assert!(Flags::legal_on(Opcode::FMul).contains(Flags::CONTRACT));
438        assert!(Flags::legal_on(Opcode::Store).contains(Flags::VOLATILE));
439        assert!(Flags::legal_on(Opcode::Jump).is_empty());
440    }
441
442    #[test]
443    fn every_flag_is_legal_on_something() {
444        for &(flag, name) in NAMED {
445            assert!(
446                Opcode::all().any(|op| Flags::legal_on(op).contains(flag)),
447                "{name} is legal nowhere, so nothing can ever set it"
448            );
449        }
450    }
451
452    #[test]
453    fn a_load_cannot_release_and_a_store_cannot_acquire() {
454        assert!(MemOrder::Acquire.is_valid_for_load());
455        assert!(!MemOrder::Release.is_valid_for_load());
456        assert!(!MemOrder::AcqRel.is_valid_for_load());
457        assert!(MemOrder::Release.is_valid_for_store());
458        assert!(!MemOrder::Acquire.is_valid_for_store());
459        assert!(MemOrder::SeqCst.is_valid_for_load());
460        assert!(MemOrder::SeqCst.is_valid_for_store());
461    }
462
463    #[test]
464    fn not_atomic_is_valid_for_no_atomic_operation() {
465        assert!(!MemOrder::NotAtomic.is_valid_for_load());
466        assert!(!MemOrder::NotAtomic.is_valid_for_store());
467        assert!(!MemOrder::NotAtomic.is_valid_for_rmw());
468        assert_eq!(MemOrder::default(), MemOrder::NotAtomic);
469    }
470
471    #[test]
472    fn every_ordering_and_operation_finds_its_name_again() {
473        for order in MemOrder::all() {
474            assert_eq!(MemOrder::from_name(order.name()), Some(order));
475        }
476        for op in RmwOp::all() {
477            assert_eq!(RmwOp::from_name(op.name()), Some(op));
478        }
479        assert_eq!(MemOrder::from_name("consume"), None);
480        assert_eq!(RmwOp::from_name("fmul"), None);
481    }
482
483    #[test]
484    fn the_floating_read_modify_writes_are_the_two_that_have_one() {
485        let floats: Vec<&str> = RmwOp::all().filter(|op| op.is_float()).map(RmwOp::name).collect();
486        assert_eq!(floats, ["fadd", "fsub"]);
487    }
488}
rucc_ir/flags.rs

rucc_ir/
flags.rs
