rucc_ir/
opcode.rs

1//! The instruction set.
2//!
3//! Design: `spec/08-ir.md` section 8.3.
4//!
5//! The set is small enough to enumerate and it is closed. Adding an opcode is a spec change,
6//! because the verifier, the printer, the parser, the rewrite rules and the lowering all have
7//! to learn it, and an opcode that only half of them know about is a silent miscompilation
8//! waiting for the right input.
9//!
10//! Two things are deliberately absent. There is no `getelementptr`: pointer arithmetic is
11//! [`Opcode::PtrAdd`] over a byte offset the frontend computed, because C never needs the
12//! multi-index form and its absence removes a well known source of complexity. And there is no
13//! `phi`: values arriving at a block are the block's parameters, passed by the branch, so
14//! there is no operand list positionally tied to a predecessor list kept somewhere else.
15
16use std::fmt;
17
18/// One instruction of the IR.
19///
20/// The names are the textual form exactly, so [`Opcode::name`] and [`Opcode::from_name`] are
21/// what the printer and the parser use, and neither carries a table of its own that could
22/// drift from this one.
23///
24/// The enum is not `non_exhaustive`, deliberately. The set is closed, so a pass that matches
25/// on every opcode should stop compiling when one is added rather than fall into a wildcard
26/// arm that quietly does the wrong thing.
27#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
28pub enum Opcode {
29    // Constants. A constant is an instruction rather than an operand kind, so that every
30    // operand is a value and every value has one definition, which is what makes the
31    // dominance check in the verifier a single rule rather than a rule with exceptions.
32    /// An integer constant, `iconst.i32 7`.
33    IConst,
34    /// A floating point constant, `fconst.f64 0x1.8p+1`.
35    FConst,
36    /// A vector constant with every lane the same, `splat.i8x16 0`.
37    Splat,
38    /// The address of a global or a function, `global_addr @counter`.
39    GlobalAddr,
40
41    // Arithmetic.
42    /// Integer addition.
43    Add,
44    /// Integer subtraction.
45    Sub,
46    /// Integer multiplication.
47    Mul,
48    /// Signed division.
49    SDiv,
50    /// Unsigned division.
51    UDiv,
52    /// Signed remainder, with the sign of the dividend.
53    SRem,
54    /// Unsigned remainder.
55    URem,
56    /// Bitwise and.
57    And,
58    /// Bitwise or.
59    Or,
60    /// Bitwise exclusive or.
61    Xor,
62    /// Shift left.
63    Shl,
64    /// Logical shift right, shifting in zeroes.
65    LShr,
66    /// Arithmetic shift right, shifting in the sign bit.
67    AShr,
68    /// Floating point addition.
69    FAdd,
70    /// Floating point subtraction.
71    FSub,
72    /// Floating point multiplication.
73    FMul,
74    /// Floating point division.
75    FDiv,
76    /// Floating point remainder.
77    FRem,
78    /// Floating point negation, which flips the sign bit and is not `0 - x`.
79    FNeg,
80    /// Fused multiply-add, rounded once.
81    Fma,
82
83    // Comparison.
84    /// Integer comparison, producing `i1` or a vector of `i1`.
85    ICmp,
86    /// Floating point comparison, producing `i1` or a vector of `i1`.
87    FCmp,
88
89    // Conversion.
90    /// Narrows an integer, discarding the high bits.
91    Trunc,
92    /// Widens an integer, copying the sign bit.
93    SExt,
94    /// Widens an integer, filling with zeroes.
95    ZExt,
96    /// Narrows a floating point value.
97    FPTrunc,
98    /// Widens a floating point value.
99    FPExt,
100    /// Floating point to signed integer.
101    FPToSI,
102    /// Floating point to unsigned integer.
103    FPToUI,
104    /// Signed integer to floating point.
105    SIToFP,
106    /// Unsigned integer to floating point.
107    UIToFP,
108    /// An address to an integer of the same width.
109    PtrToInt,
110    /// An integer to an address.
111    IntToPtr,
112    /// A reinterpretation of the same bits at the same width.
113    Bitcast,
114
115    // Memory.
116    /// A stack slot. In the entry block, or marked dynamic for a variable length array.
117    Alloca,
118    /// A read.
119    Load,
120    /// A write, producing no value.
121    Store,
122    /// Address arithmetic: an address and a byte offset.
123    PtrAdd,
124    /// A copy of a known size between addresses that do not overlap.
125    Memcpy,
126    /// A copy of a known size between addresses that may overlap.
127    Memmove,
128    /// A fill of a known size with one byte.
129    Memset,
130    /// An atomic read.
131    AtomicLoad,
132    /// An atomic write.
133    AtomicStore,
134    /// An atomic read-modify-write, carrying which operation in [`RmwOp`](crate::RmwOp).
135    AtomicRmw,
136    /// An atomic compare and exchange, producing the old value and whether it succeeded.
137    Cmpxchg,
138    /// A memory barrier.
139    Fence,
140
141    // Control. Every one of these is a terminator.
142    /// An unconditional branch, `jump block1(%a, %b)`.
143    Jump,
144    /// A two-way branch on an `i1`.
145    BrIf,
146    /// A multi-way branch on an integer, with a default.
147    Switch,
148    /// A return, with the values the signature says.
149    Return,
150    /// A place control cannot reach, which the frontend emits after a `noreturn` call.
151    Unreachable,
152
153    // Calls.
154    /// A call to a named function.
155    Call,
156    /// A call through an address, carrying the signature it is called with.
157    CallIndirect,
158    /// A call in tail position that reuses the frame, which is a terminator.
159    TailCall,
160
161    // Intrinsics, which is the closed part. The open part is `TargetIntrinsic`.
162    /// Count leading zeroes.
163    Ctlz,
164    /// Count trailing zeroes.
165    Cttz,
166    /// Count set bits.
167    Ctpop,
168    /// Reverse the bytes.
169    Bswap,
170    /// Reverse the bits.
171    Bitreverse,
172    /// Signed addition, producing the result and whether it overflowed.
173    SAddOverflow,
174    /// Unsigned addition, producing the result and whether it overflowed.
175    UAddOverflow,
176    /// Signed subtraction, producing the result and whether it overflowed.
177    SSubOverflow,
178    /// Unsigned subtraction, producing the result and whether it overflowed.
179    USubOverflow,
180    /// Signed multiplication, producing the result and whether it overflowed.
181    SMulOverflow,
182    /// Unsigned multiplication, producing the result and whether it overflowed.
183    UMulOverflow,
184    /// `__builtin_expect`, which is the value with a hint attached.
185    Expect,
186    /// `__builtin_unreachable` as a hint on a path, distinct from the terminator.
187    UnreachableHint,
188    /// `__builtin_prefetch`.
189    Prefetch,
190    /// `__builtin_frame_address`.
191    FrameAddress,
192    /// `__builtin_return_address`.
193    ReturnAddress,
194    /// The start of a variable argument list.
195    VaStart,
196    /// One argument off a variable argument list.
197    VaArg,
198    /// The end of a variable argument list.
199    VaEnd,
200    /// A copy of a variable argument list.
201    VaCopy,
202    /// The stack pointer, saved before a variable length array.
203    StackSave,
204    /// The stack pointer, restored after one.
205    StackRestore,
206    /// The marker a `setjmp` leaves, which pins everything live across it.
207    SetjmpMarker,
208    /// The marker a `longjmp` leaves.
209    LongjmpMarker,
210    /// A target-specific intrinsic, named rather than enumerated, for the vector builtins.
211    TargetIntrinsic,
212
213    /// Inline assembly. A terminator when it has labels, which is `asm goto`.
214    InlineAsm,
215}
216
217impl Opcode {
218    /// The textual form, which is also what the parser reads.
219    #[must_use]
220    pub const fn name(self) -> &'static str {
221        match self {
222            Self::IConst => "iconst",
223            Self::FConst => "fconst",
224            Self::Splat => "splat",
225            Self::GlobalAddr => "global_addr",
226            Self::Add => "add",
227            Self::Sub => "sub",
228            Self::Mul => "mul",
229            Self::SDiv => "sdiv",
230            Self::UDiv => "udiv",
231            Self::SRem => "srem",
232            Self::URem => "urem",
233            Self::And => "and",
234            Self::Or => "or",
235            Self::Xor => "xor",
236            Self::Shl => "shl",
237            Self::LShr => "lshr",
238            Self::AShr => "ashr",
239            Self::FAdd => "fadd",
240            Self::FSub => "fsub",
241            Self::FMul => "fmul",
242            Self::FDiv => "fdiv",
243            Self::FRem => "frem",
244            Self::FNeg => "fneg",
245            Self::Fma => "fma",
246            Self::ICmp => "icmp",
247            Self::FCmp => "fcmp",
248            Self::Trunc => "trunc",
249            Self::SExt => "sext",
250            Self::ZExt => "zext",
251            Self::FPTrunc => "fptrunc",
252            Self::FPExt => "fpext",
253            Self::FPToSI => "fptosi",
254            Self::FPToUI => "fptoui",
255            Self::SIToFP => "sitofp",
256            Self::UIToFP => "uitofp",
257            Self::PtrToInt => "ptrtoint",
258            Self::IntToPtr => "inttoptr",
259            Self::Bitcast => "bitcast",
260            Self::Alloca => "alloca",
261            Self::Load => "load",
262            Self::Store => "store",
263            Self::PtrAdd => "ptr_add",
264            Self::Memcpy => "memcpy",
265            Self::Memmove => "memmove",
266            Self::Memset => "memset",
267            Self::AtomicLoad => "atomic_load",
268            Self::AtomicStore => "atomic_store",
269            Self::AtomicRmw => "atomic_rmw",
270            Self::Cmpxchg => "cmpxchg",
271            Self::Fence => "fence",
272            Self::Jump => "jump",
273            Self::BrIf => "br_if",
274            Self::Switch => "switch",
275            Self::Return => "return",
276            Self::Unreachable => "unreachable",
277            Self::Call => "call",
278            Self::CallIndirect => "call_indirect",
279            Self::TailCall => "tail_call",
280            Self::Ctlz => "ctlz",
281            Self::Cttz => "cttz",
282            Self::Ctpop => "ctpop",
283            Self::Bswap => "bswap",
284            Self::Bitreverse => "bitreverse",
285            Self::SAddOverflow => "sadd_overflow",
286            Self::UAddOverflow => "uadd_overflow",
287            Self::SSubOverflow => "ssub_overflow",
288            Self::USubOverflow => "usub_overflow",
289            Self::SMulOverflow => "smul_overflow",
290            Self::UMulOverflow => "umul_overflow",
291            Self::Expect => "expect",
292            Self::UnreachableHint => "unreachable_hint",
293            Self::Prefetch => "prefetch",
294            Self::FrameAddress => "frame_address",
295            Self::ReturnAddress => "return_address",
296            Self::VaStart => "va_start",
297            Self::VaArg => "va_arg",
298            Self::VaEnd => "va_end",
299            Self::VaCopy => "va_copy",
300            Self::StackSave => "stacksave",
301            Self::StackRestore => "stackrestore",
302            Self::SetjmpMarker => "setjmp_marker",
303            Self::LongjmpMarker => "longjmp_marker",
304            Self::TargetIntrinsic => "target_intrinsic",
305            Self::InlineAsm => "inline_asm",
306        }
307    }
308
309    /// Every opcode, in the order they are declared.
310    ///
311    /// The parser walks this rather than holding a second table, because a second table is a
312    /// table that can disagree with the first one.
313    pub fn all() -> impl Iterator<Item = Self> {
314        ALL.iter().copied()
315    }
316
317    /// The opcode with that name, if there is one.
318    #[must_use]
319    pub fn from_name(name: &str) -> Option<Self> {
320        ALL.iter().copied().find(|op| op.name() == name)
321    }
322
323    /// Whether this ends a block.
324    ///
325    /// [`Opcode::InlineAsm`] is not here and is the one instruction whose answer depends on
326    /// the instruction rather than on the opcode: `asm goto` has successors and everything
327    /// else does not. Ask the instruction, not the opcode.
328    #[must_use]
329    pub const fn is_terminator(self) -> bool {
330        matches!(
331            self,
332            Self::Jump
333                | Self::BrIf
334                | Self::Switch
335                | Self::Return
336                | Self::Unreachable
337                | Self::TailCall
338        )
339    }
340
341    /// Whether the operands can be swapped without changing the result.
342    ///
343    /// The floating point cases are commutative even under the strictest rounding, because
344    /// swapping the operands of an addition does not change which of them is a NaN, and the
345    /// sign of a NaN result is not something we promise anything about either way.
346    #[must_use]
347    pub const fn is_commutative(self) -> bool {
348        matches!(
349            self,
350            Self::Add
351                | Self::Mul
352                | Self::And
353                | Self::Or
354                | Self::Xor
355                | Self::FAdd
356                | Self::FMul
357                | Self::SAddOverflow
358                | Self::UAddOverflow
359                | Self::SMulOverflow
360                | Self::UMulOverflow
361        )
362    }
363
364    /// Whether this reads or writes memory, or has an effect the optimizer has to preserve.
365    ///
366    /// An instruction that answers no can be deleted when nothing uses its result, moved
367    /// across a call, and merged with another one computing the same thing. Everything else
368    /// has to be argued about individually, so the conservative answer is the true one here
369    /// and the list of exceptions is the part that is checked.
370    #[must_use]
371    pub const fn has_effects(self) -> bool {
372        !matches!(
373            self,
374            Self::IConst
375                | Self::FConst
376                | Self::Splat
377                | Self::GlobalAddr
378                | Self::Add
379                | Self::Sub
380                | Self::Mul
381                | Self::SDiv
382                | Self::UDiv
383                | Self::SRem
384                | Self::URem
385                | Self::And
386                | Self::Or
387                | Self::Xor
388                | Self::Shl
389                | Self::LShr
390                | Self::AShr
391                | Self::FAdd
392                | Self::FSub
393                | Self::FMul
394                | Self::FDiv
395                | Self::FRem
396                | Self::FNeg
397                | Self::Fma
398                | Self::ICmp
399                | Self::FCmp
400                | Self::Trunc
401                | Self::SExt
402                | Self::ZExt
403                | Self::FPTrunc
404                | Self::FPExt
405                | Self::FPToSI
406                | Self::FPToUI
407                | Self::SIToFP
408                | Self::UIToFP
409                | Self::PtrToInt
410                | Self::IntToPtr
411                | Self::Bitcast
412                | Self::PtrAdd
413                | Self::Ctlz
414                | Self::Cttz
415                | Self::Ctpop
416                | Self::Bswap
417                | Self::Bitreverse
418                | Self::SAddOverflow
419                | Self::UAddOverflow
420                | Self::SSubOverflow
421                | Self::USubOverflow
422                | Self::SMulOverflow
423                | Self::UMulOverflow
424                | Self::Expect
425                | Self::FrameAddress
426                | Self::ReturnAddress
427        )
428    }
429
430    /// How many values this produces, for the opcodes where the count is fixed.
431    ///
432    /// `None` means the count comes from somewhere else: a call takes it from its signature,
433    /// and inline assembly takes it from its output constraints. A tail call is not one of
434    /// them, because whatever it returns goes straight out of the function and there is no
435    /// instruction after it to use anything.
436    #[must_use]
437    pub const fn results(self) -> Option<u8> {
438        match self {
439            Self::Call | Self::CallIndirect | Self::InlineAsm => None,
440            Self::Cmpxchg
441            | Self::SAddOverflow
442            | Self::UAddOverflow
443            | Self::SSubOverflow
444            | Self::USubOverflow
445            | Self::SMulOverflow
446            | Self::UMulOverflow => Some(2),
447            Self::Store
448            | Self::Memcpy
449            | Self::Memmove
450            | Self::Memset
451            | Self::AtomicStore
452            | Self::Fence
453            | Self::Prefetch
454            | Self::VaStart
455            | Self::VaEnd
456            | Self::VaCopy
457            | Self::StackRestore
458            | Self::UnreachableHint
459            | Self::SetjmpMarker
460            | Self::LongjmpMarker => Some(0),
461            _ if self.is_terminator() => Some(0),
462            _ => Some(1),
463        }
464    }
465
466    /// Which payload an instruction with this opcode carries.
467    ///
468    /// The printer reads the payload it finds and does not need this. The parser has only the
469    /// opcode when it reaches the operands, so this is where the two of them agree on what
470    /// comes after them. An instruction carrying a payload of some other kind prints as text
471    /// the parser cannot read back, which is why the verifier checks it against
472    /// [`Extra::kind`](crate::Extra::kind) rather than leaving it to be found later.
473    #[must_use]
474    pub const fn extra_kind(self) -> ExtraKind {
475        match self {
476            Self::IConst | Self::FConst | Self::Splat => ExtraKind::Imm,
477            Self::GlobalAddr | Self::TargetIntrinsic => ExtraKind::Symbol,
478            Self::ICmp => ExtraKind::IntPred,
479            Self::FCmp => ExtraKind::FloatPred,
480            Self::Alloca
481            | Self::Load
482            | Self::Store
483            | Self::Memcpy
484            | Self::Memmove
485            | Self::Memset
486            | Self::AtomicLoad
487            | Self::AtomicStore
488            | Self::Cmpxchg => ExtraKind::Mem,
489            Self::AtomicRmw => ExtraKind::Rmw,
490            Self::Fence => ExtraKind::Order,
491            Self::Jump | Self::BrIf => ExtraKind::Targets,
492            Self::Switch => ExtraKind::Switch,
493            Self::Call | Self::CallIndirect | Self::TailCall => ExtraKind::Call,
494            Self::InlineAsm => ExtraKind::Asm,
495            _ => ExtraKind::None,
496        }
497    }
498}
499
500/// Which of [`Extra`](crate::Extra)'s shapes an instruction carries.
501///
502/// The same list of names, without any of the payloads, so that a question about an opcode can
503/// be answered without an instruction to look at.
504#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
505pub enum ExtraKind {
506    /// Nothing.
507    None,
508    /// A constant.
509    Imm,
510    /// A name.
511    Symbol,
512    /// An integer comparison predicate.
513    IntPred,
514    /// A floating point comparison predicate.
515    FloatPred,
516    /// An access.
517    Mem,
518    /// An atomic read-modify-write.
519    Rmw,
520    /// A barrier's ordering.
521    Order,
522    /// Branch targets.
523    Targets,
524    /// A call.
525    Call,
526    /// A `switch`.
527    Switch,
528    /// Inline assembly.
529    Asm,
530}
531
532impl ExtraKind {
533    /// What it is, in words, for a message that names two of them and has to read as English.
534    #[must_use]
535    pub const fn name(self) -> &'static str {
536        match self {
537            Self::None => "nothing",
538            Self::Imm => "a constant",
539            Self::Symbol => "a name",
540            Self::IntPred => "an integer comparison",
541            Self::FloatPred => "a floating point comparison",
542            Self::Mem => "an access",
543            Self::Rmw => "a read-modify-write",
544            Self::Order => "an ordering",
545            Self::Targets => "branch targets",
546            Self::Call => "a call",
547            Self::Switch => "a switch",
548            Self::Asm => "inline assembly",
549        }
550    }
551}
552
553impl fmt::Display for Opcode {
554    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
555        f.write_str(self.name())
556    }
557}
558
559/// Every opcode, which is what [`Opcode::all`] hands out.
560///
561/// This is written out rather than derived, and the test below is what keeps it complete: it
562/// checks the count against [`Opcode::InlineAsm`], the last variant, so a new opcode that is
563/// not added here fails the build rather than going quietly missing from the parser.
564static ALL: &[Opcode] = &[
565    Opcode::IConst,
566    Opcode::FConst,
567    Opcode::Splat,
568    Opcode::GlobalAddr,
569    Opcode::Add,
570    Opcode::Sub,
571    Opcode::Mul,
572    Opcode::SDiv,
573    Opcode::UDiv,
574    Opcode::SRem,
575    Opcode::URem,
576    Opcode::And,
577    Opcode::Or,
578    Opcode::Xor,
579    Opcode::Shl,
580    Opcode::LShr,
581    Opcode::AShr,
582    Opcode::FAdd,
583    Opcode::FSub,
584    Opcode::FMul,
585    Opcode::FDiv,
586    Opcode::FRem,
587    Opcode::FNeg,
588    Opcode::Fma,
589    Opcode::ICmp,
590    Opcode::FCmp,
591    Opcode::Trunc,
592    Opcode::SExt,
593    Opcode::ZExt,
594    Opcode::FPTrunc,
595    Opcode::FPExt,
596    Opcode::FPToSI,
597    Opcode::FPToUI,
598    Opcode::SIToFP,
599    Opcode::UIToFP,
600    Opcode::PtrToInt,
601    Opcode::IntToPtr,
602    Opcode::Bitcast,
603    Opcode::Alloca,
604    Opcode::Load,
605    Opcode::Store,
606    Opcode::PtrAdd,
607    Opcode::Memcpy,
608    Opcode::Memmove,
609    Opcode::Memset,
610    Opcode::AtomicLoad,
611    Opcode::AtomicStore,
612    Opcode::AtomicRmw,
613    Opcode::Cmpxchg,
614    Opcode::Fence,
615    Opcode::Jump,
616    Opcode::BrIf,
617    Opcode::Switch,
618    Opcode::Return,
619    Opcode::Unreachable,
620    Opcode::Call,
621    Opcode::CallIndirect,
622    Opcode::TailCall,
623    Opcode::Ctlz,
624    Opcode::Cttz,
625    Opcode::Ctpop,
626    Opcode::Bswap,
627    Opcode::Bitreverse,
628    Opcode::SAddOverflow,
629    Opcode::UAddOverflow,
630    Opcode::SSubOverflow,
631    Opcode::USubOverflow,
632    Opcode::SMulOverflow,
633    Opcode::UMulOverflow,
634    Opcode::Expect,
635    Opcode::UnreachableHint,
636    Opcode::Prefetch,
637    Opcode::FrameAddress,
638    Opcode::ReturnAddress,
639    Opcode::VaStart,
640    Opcode::VaArg,
641    Opcode::VaEnd,
642    Opcode::VaCopy,
643    Opcode::StackSave,
644    Opcode::StackRestore,
645    Opcode::SetjmpMarker,
646    Opcode::LongjmpMarker,
647    Opcode::TargetIntrinsic,
648    Opcode::InlineAsm,
649];
650
651/// The ten integer comparisons.
652///
653/// Signedness is on the predicate rather than on the type, for the same reason it is on
654/// `sdiv` and `udiv`: the type space is halved and the operation says what it means.
655#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
656pub enum IntPred {
657    /// Equal.
658    Eq,
659    /// Not equal.
660    Ne,
661    /// Signed less than.
662    Slt,
663    /// Signed less than or equal.
664    Sle,
665    /// Signed greater than.
666    Sgt,
667    /// Signed greater than or equal.
668    Sge,
669    /// Unsigned less than.
670    Ult,
671    /// Unsigned less than or equal.
672    Ule,
673    /// Unsigned greater than.
674    Ugt,
675    /// Unsigned greater than or equal.
676    Uge,
677}
678
679impl IntPred {
680    /// The textual form.
681    #[must_use]
682    pub const fn name(self) -> &'static str {
683        match self {
684            Self::Eq => "eq",
685            Self::Ne => "ne",
686            Self::Slt => "slt",
687            Self::Sle => "sle",
688            Self::Sgt => "sgt",
689            Self::Sge => "sge",
690            Self::Ult => "ult",
691            Self::Ule => "ule",
692            Self::Ugt => "ugt",
693            Self::Uge => "uge",
694        }
695    }
696
697    /// The predicate with that name, if there is one.
698    #[must_use]
699    pub fn from_name(name: &str) -> Option<Self> {
700        Self::all().find(|pred| pred.name() == name)
701    }
702
703    /// Every predicate.
704    pub fn all() -> impl Iterator<Item = Self> {
705        [
706            Self::Eq,
707            Self::Ne,
708            Self::Slt,
709            Self::Sle,
710            Self::Sgt,
711            Self::Sge,
712            Self::Ult,
713            Self::Ule,
714            Self::Ugt,
715            Self::Uge,
716        ]
717        .into_iter()
718    }
719
720    /// The predicate that holds exactly when this one does not.
721    #[must_use]
722    pub const fn inverse(self) -> Self {
723        match self {
724            Self::Eq => Self::Ne,
725            Self::Ne => Self::Eq,
726            Self::Slt => Self::Sge,
727            Self::Sge => Self::Slt,
728            Self::Sle => Self::Sgt,
729            Self::Sgt => Self::Sle,
730            Self::Ult => Self::Uge,
731            Self::Uge => Self::Ult,
732            Self::Ule => Self::Ugt,
733            Self::Ugt => Self::Ule,
734        }
735    }
736
737    /// The predicate that holds when the operands are given the other way round.
738    #[must_use]
739    pub const fn swapped(self) -> Self {
740        match self {
741            Self::Eq => Self::Eq,
742            Self::Ne => Self::Ne,
743            Self::Slt => Self::Sgt,
744            Self::Sgt => Self::Slt,
745            Self::Sle => Self::Sge,
746            Self::Sge => Self::Sle,
747            Self::Ult => Self::Ugt,
748            Self::Ugt => Self::Ult,
749            Self::Ule => Self::Uge,
750            Self::Uge => Self::Ule,
751        }
752    }
753
754    /// Whether this reads its operands as signed. Equality reads them as neither.
755    #[must_use]
756    pub const fn is_signed(self) -> bool {
757        matches!(self, Self::Slt | Self::Sle | Self::Sgt | Self::Sge)
758    }
759}
760
761impl fmt::Display for IntPred {
762    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
763        f.write_str(self.name())
764    }
765}
766
767/// The floating point comparisons, ordered and unordered.
768///
769/// An ordered predicate is false if either operand is a NaN, and an unordered one is true. C's
770/// `<` is `olt` and C's `!=` is `une`, which is the whole of why both families are here.
771#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
772pub enum FloatPred {
773    /// Always false.
774    False,
775    /// Ordered and equal.
776    Oeq,
777    /// Ordered and greater than.
778    Ogt,
779    /// Ordered and greater than or equal.
780    Oge,
781    /// Ordered and less than.
782    Olt,
783    /// Ordered and less than or equal.
784    Ole,
785    /// Ordered and not equal.
786    One,
787    /// Ordered, which is to say neither operand is a NaN.
788    Ord,
789    /// Unordered, which is to say one of them is.
790    Uno,
791    /// Unordered or equal.
792    Ueq,
793    /// Unordered or greater than.
794    Ugt,
795    /// Unordered or greater than or equal.
796    Uge,
797    /// Unordered or less than.
798    Ult,
799    /// Unordered or less than or equal.
800    Ule,
801    /// Unordered or not equal.
802    Une,
803    /// Always true.
804    True,
805}
806
807impl FloatPred {
808    /// The textual form.
809    #[must_use]
810    pub const fn name(self) -> &'static str {
811        match self {
812            Self::False => "false",
813            Self::Oeq => "oeq",
814            Self::Ogt => "ogt",
815            Self::Oge => "oge",
816            Self::Olt => "olt",
817            Self::Ole => "ole",
818            Self::One => "one",
819            Self::Ord => "ord",
820            Self::Uno => "uno",
821            Self::Ueq => "ueq",
822            Self::Ugt => "ugt",
823            Self::Uge => "uge",
824            Self::Ult => "ult",
825            Self::Ule => "ule",
826            Self::Une => "une",
827            Self::True => "true",
828        }
829    }
830
831    /// The predicate with that name, if there is one.
832    #[must_use]
833    pub fn from_name(name: &str) -> Option<Self> {
834        Self::all().find(|pred| pred.name() == name)
835    }
836
837    /// Every predicate.
838    pub fn all() -> impl Iterator<Item = Self> {
839        [
840            Self::False,
841            Self::Oeq,
842            Self::Ogt,
843            Self::Oge,
844            Self::Olt,
845            Self::Ole,
846            Self::One,
847            Self::Ord,
848            Self::Uno,
849            Self::Ueq,
850            Self::Ugt,
851            Self::Uge,
852            Self::Ult,
853            Self::Ule,
854            Self::Une,
855            Self::True,
856        ]
857        .into_iter()
858    }
859
860    /// The predicate that holds exactly when this one does not.
861    #[must_use]
862    pub const fn inverse(self) -> Self {
863        match self {
864            Self::False => Self::True,
865            Self::Oeq => Self::Une,
866            Self::Ogt => Self::Ule,
867            Self::Oge => Self::Ult,
868            Self::Olt => Self::Uge,
869            Self::Ole => Self::Ugt,
870            Self::One => Self::Ueq,
871            Self::Ord => Self::Uno,
872            Self::Uno => Self::Ord,
873            Self::Ueq => Self::One,
874            Self::Ugt => Self::Ole,
875            Self::Uge => Self::Olt,
876            Self::Ult => Self::Oge,
877            Self::Ule => Self::Ogt,
878            Self::Une => Self::Oeq,
879            Self::True => Self::False,
880        }
881    }
882
883    /// The predicate that holds when the operands are given the other way round.
884    #[must_use]
885    pub const fn swapped(self) -> Self {
886        match self {
887            Self::Ogt => Self::Olt,
888            Self::Olt => Self::Ogt,
889            Self::Oge => Self::Ole,
890            Self::Ole => Self::Oge,
891            Self::Ugt => Self::Ult,
892            Self::Ult => Self::Ugt,
893            Self::Uge => Self::Ule,
894            Self::Ule => Self::Uge,
895            same => same,
896        }
897    }
898
899    /// Whether this is false when either operand is a NaN.
900    ///
901    /// [`FloatPred::False`] and [`FloatPred::True`] are neither ordered nor unordered, since
902    /// they do not look at their operands at all, and both answer no here.
903    #[must_use]
904    pub const fn is_ordered(self) -> bool {
905        matches!(
906            self,
907            Self::Oeq | Self::Ogt | Self::Oge | Self::Olt | Self::Ole | Self::One | Self::Ord
908        )
909    }
910}
911
912impl fmt::Display for FloatPred {
913    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
914        f.write_str(self.name())
915    }
916}
917
918#[cfg(test)]
919mod tests {
920    use super::*;
921
922    #[test]
923    fn every_opcode_is_in_the_table() {
924        // `InlineAsm` is the last variant, so its discriminant plus one is how many there are.
925        // A new opcode declared after it moves this number, and a new opcode declared before
926        // it and not added to `ALL` moves the length, so either mistake fails here.
927        assert_eq!(ALL.len(), Opcode::InlineAsm as usize + 1);
928        for (position, &op) in ALL.iter().enumerate() {
929            assert_eq!(op as usize, position, "{op} is out of order in ALL");
930        }
931    }
932
933    #[test]
934    fn every_opcode_has_its_own_name_and_finds_it_again() {
935        let mut names: Vec<&str> = Opcode::all().map(Opcode::name).collect();
936        let total = names.len();
937        names.sort_unstable();
938        names.dedup();
939        assert_eq!(names.len(), total, "two opcodes share a name");
940        for op in Opcode::all() {
941            assert_eq!(Opcode::from_name(op.name()), Some(op));
942        }
943        assert_eq!(Opcode::from_name("phi"), None);
944        assert_eq!(Opcode::from_name("getelementptr"), None);
945        assert_eq!(Opcode::from_name(""), None);
946    }
947
948    #[test]
949    fn the_terminators_are_the_ones_control_leaves_by() {
950        let terminators: Vec<&str> =
951            Opcode::all().filter(|op| op.is_terminator()).map(Opcode::name).collect();
952        assert_eq!(terminators, ["jump", "br_if", "switch", "return", "unreachable", "tail_call"]);
953    }
954
955    #[test]
956    fn a_terminator_produces_nothing() {
957        for op in Opcode::all().filter(|op| op.is_terminator()) {
958            assert_eq!(op.results(), Some(0), "{op}");
959        }
960    }
961
962    #[test]
963    fn the_pair_producing_opcodes_are_the_ones_with_a_flag_beside_the_value() {
964        let pairs: Vec<&str> =
965            Opcode::all().filter(|op| op.results() == Some(2)).map(Opcode::name).collect();
966        assert_eq!(
967            pairs,
968            [
969                "cmpxchg",
970                "sadd_overflow",
971                "uadd_overflow",
972                "ssub_overflow",
973                "usub_overflow",
974                "smul_overflow",
975                "umul_overflow"
976            ]
977        );
978    }
979
980    #[test]
981    fn memory_has_effects_and_arithmetic_does_not() {
982        for op in [Opcode::Load, Opcode::Store, Opcode::Call, Opcode::Alloca, Opcode::Fence] {
983            assert!(op.has_effects(), "{op}");
984        }
985        for op in [Opcode::Add, Opcode::FDiv, Opcode::ICmp, Opcode::PtrAdd, Opcode::IConst] {
986            assert!(!op.has_effects(), "{op}");
987        }
988    }
989
990    #[test]
991    fn commuting_is_only_claimed_where_it_holds() {
992        assert!(Opcode::Add.is_commutative());
993        assert!(Opcode::FAdd.is_commutative());
994        assert!(!Opcode::Sub.is_commutative());
995        assert!(!Opcode::FDiv.is_commutative());
996        assert!(!Opcode::Shl.is_commutative());
997    }
998
999    #[test]
1000    fn an_integer_predicate_inverts_and_swaps_back_to_itself() {
1001        for pred in IntPred::all() {
1002            assert_eq!(pred.inverse().inverse(), pred);
1003            assert_eq!(pred.swapped().swapped(), pred);
1004            assert_eq!(IntPred::from_name(pred.name()), Some(pred));
1005        }
1006        assert_eq!(IntPred::Slt.inverse(), IntPred::Sge);
1007        assert_eq!(IntPred::Slt.swapped(), IntPred::Sgt);
1008        assert_eq!(IntPred::from_name("lt"), None);
1009    }
1010
1011    #[test]
1012    fn a_floating_predicate_inverts_across_the_ordered_line() {
1013        for pred in FloatPred::all() {
1014            assert_eq!(pred.inverse().inverse(), pred);
1015            assert_eq!(pred.swapped().swapped(), pred);
1016            assert_eq!(FloatPred::from_name(pred.name()), Some(pred));
1017        }
1018        // Inverting has to cross the line, because the negation of an ordered comparison is
1019        // true when an operand is a NaN. This is where `!(a < b)` stops being `a >= b`. The
1020        // two constants are outside it: neither of them looks at its operands.
1021        for pred in FloatPred::all().filter(|p| !matches!(p, FloatPred::False | FloatPred::True)) {
1022            assert_ne!(pred.is_ordered(), pred.inverse().is_ordered(), "{pred}");
1023        }
1024        assert_eq!(FloatPred::Olt.inverse(), FloatPred::Uge);
1025        assert_eq!(FloatPred::Olt.swapped(), FloatPred::Ogt);
1026    }
1027
1028    #[test]
1029    fn swapping_a_predicate_keeps_it_ordered_or_unordered() {
1030        for pred in FloatPred::all() {
1031            assert_eq!(pred.is_ordered(), pred.swapped().is_ordered(), "{pred}");
1032        }
1033        for pred in IntPred::all() {
1034            assert_eq!(pred.is_signed(), pred.swapped().is_signed(), "{pred}");
1035        }
1036    }
1037
1038    #[test]
1039    fn no_two_predicates_share_a_name_within_their_family() {
1040        for names in [
1041            IntPred::all().map(IntPred::name).collect::<Vec<_>>(),
1042            FloatPred::all().map(FloatPred::name).collect::<Vec<_>>(),
1043        ] {
1044            let total = names.len();
1045            let mut names = names;
1046            names.sort_unstable();
1047            names.dedup();
1048            assert_eq!(names.len(), total);
1049        }
1050    }
1051}
rucc_ir/opcode.rs

rucc_ir/
opcode.rs
