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