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