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 // Selection.
96 /// One of two values, chosen by a bit. `select c, a, b` is `a` when `c` is one.
97 ///
98 /// This is what control flow becomes when it stops being control flow.
99 /// `spec/optimizer/22-phiopt-and-if-conversion.md` section 22.2 makes it the lowering target
100 /// for a diamond whose two arms compute a value, and the reason it is an opcode rather than a
101 /// pattern is that it is the form the rule set is written against: `select(c, a, a) -> a` and
102 /// `select(c, 1, 0) -> zext(c)` are ordinary rules once the shape has a name.
103 ///
104 /// Both arms are evaluated, which is the whole point and also the whole danger. Whatever
105 /// produces one of these owes the argument that evaluating the arm that is not chosen is
106 /// harmless, and section 22.6 is the list of ways that argument goes wrong.
107 Select,
108
109 // Conversion.
110 /// Narrows an integer, discarding the high bits.
111 Trunc,
112 /// Widens an integer, copying the sign bit.
113 SExt,
114 /// Widens an integer, filling with zeroes.
115 ZExt,
116 /// Narrows a floating point value.
117 FPTrunc,
118 /// Widens a floating point value.
119 FPExt,
120 /// Floating point to signed integer.
121 FPToSI,
122 /// Floating point to unsigned integer.
123 FPToUI,
124 /// Signed integer to floating point.
125 SIToFP,
126 /// Unsigned integer to floating point.
127 UIToFP,
128 /// An address to an integer of the same width.
129 PtrToInt,
130 /// An integer to an address.
131 IntToPtr,
132 /// A reinterpretation of the same bits at the same width.
133 Bitcast,
134
135 // Memory.
136 /// Memory as the function found it, which is where a memory SSA chain starts.
137 ///
138 /// It produces one `mem` and takes nothing, and it belongs at the top of the entry block.
139 /// GCC calls the same thing the default definition of `.MEM` and LLVM calls it
140 /// `liveOnEntry`. It exists as an instruction rather than as a parameter of the entry block
141 /// because the entry block's parameters are the function's parameters and the verifier
142 /// checks them against the signature, and memory is not an argument anybody passed.
143 MemEntry,
144 /// A stack slot. In the entry block, or marked dynamic for a variable length array.
145 Alloca,
146 /// A read.
147 Load,
148 /// A write, producing no value.
149 Store,
150 /// Address arithmetic: an address and a byte offset.
151 PtrAdd,
152 /// A copy of a known size between addresses that do not overlap.
153 Memcpy,
154 /// A copy of a known size between addresses that may overlap.
155 Memmove,
156 /// A fill of a known size with one byte.
157 Memset,
158 /// An atomic read.
159 AtomicLoad,
160 /// An atomic write.
161 AtomicStore,
162 /// An atomic read-modify-write, carrying which operation in [`RmwOp`](crate::RmwOp).
163 AtomicRmw,
164 /// An atomic compare and exchange, producing the old value and whether it succeeded.
165 Cmpxchg,
166 /// A memory barrier.
167 Fence,
168
169 // Memory safety. Design: `spec/safe-memory/06-instrumentation.md` section 6.2.2. None of
170 // these is emitted unless `-fsafety` asked for it, and a function compiled without it
171 // contains not one of them.
172 /// The capability of a pointer value, taken from the pointer's provenance.
173 CapOf,
174 /// The capability in the auxiliary slot beside a stored pointer, read back.
175 ///
176 /// A pointer written to memory and read again has to bring its capability with it, and where
177 /// the capability lives is document 05's question rather than this one's. What this says is
178 /// that a capability comes back from an address, which is enough for every pass above.
179 CapLoad,
180 /// The other half of [`Opcode::CapLoad`], writing one into the slot beside a pointer.
181 CapStore,
182 /// The capability that permits nothing, which is what a null pointer has.
183 CapNull,
184 /// A capability narrowed to a sub-object of what it covered.
185 ///
186 /// Only under `-fsafety-subobject`. Narrowing is what catches an overflow from one member of
187 /// a struct into the next, and it is separate because C code that walks off the end of a
188 /// member on purpose exists and a project has to be able to say so.
189 CapNarrow,
190 /// The capability for an address that arrived from outside, recovered from the planes.
191 CapRecover,
192 /// How many bytes from an address on the capability covers, asking for no more than a limit.
193 ///
194 /// Three operands, the capability, the address and how many bytes the asker wants, and one
195 /// integer result that is never more than that limit. It is what
196 /// `spec/safe-memory/07-check-elimination.md` section 7.4 needs to split a loop: the checked
197 /// part and the unchecked part are divided at `min(n, extent / sizeof(T))`, and the extent is
198 /// the half of that a compiler cannot work out on its own.
199 ///
200 /// The limit is an operand because under milestone S1 answering means walking the lifetime
201 /// plane, and a walk that stops at the number of bytes the loop was going to read anyway is
202 /// bounded by the work the loop is already doing. An answer smaller than the truth costs
203 /// iterations in the checked half and is never wrong, which is what makes stopping early
204 /// allowed. Once a capability carries its own bounds, which is milestone S2, this is a
205 /// subtraction on the capability and the limit is one `min`.
206 CapExtent,
207 /// How many bytes below an address on the capability covers, asking for no more than a limit.
208 ///
209 /// The mirror of [`Opcode::CapExtent`], with the same three operands and the same kind of
210 /// answer. What it counts is the bytes ending at the address rather than the bytes starting
211 /// there, so an answer of `n` says that `[addr - n, addr)` belongs to one thing. The address
212 /// itself is one past what is asked about, which is what a walk from high to low needs: the
213 /// question is about where the walk ends up, and where it ends up is below where it began.
214 ///
215 /// The ownership asked about is the byte below the address rather than the byte at it, since
216 /// the address may be one past the end of the object and the object is what the question is
217 /// about. Everything else, the limit operand and why an answer short of the truth is allowed,
218 /// is [`Opcode::CapExtent`]'s.
219 CapExtentBack,
220 /// An access is within its capability's bounds, aligned, and permitted.
221 ///
222 /// The size and the alignment are the access's, and they are in the memory payload rather
223 /// than in operands because they are what the front end knew and not what the program
224 /// computed.
225 ///
226 /// A third operand overrides how many bytes are asked about, and it exists for the one check
227 /// the front end did not write. `spec/safe-memory/07-check-elimination.md` section 7.4 replaces
228 /// the checks in a loop that runs `n` times with one check over `n * sizeof(T)` bytes, and that
229 /// is a length the program computes rather than one anybody knew when the access was parsed. The
230 /// payload still holds the alignment and the type information of the access the check came from,
231 /// and its size becomes the size of one of them rather than the size of the question.
232 CheckBounds,
233 /// The capability's provenance is still live.
234 CheckLive,
235 /// The access agrees with the type plane, which is the effective type rule of C 6.5.
236 CheckType,
237 /// The bytes the access reads have been written.
238 CheckInit,
239 /// A pointer derived from another stays inside the capability the first one had.
240 ///
241 /// Three operands, because the answer is about the new pointer and the question is about
242 /// the old one's capability.
243 CheckDeriv,
244 /// The metadata this access is about to consult has not been changed under it.
245 CheckRace,
246 /// This read did not reach a byte another `restrict` pointer of the same block wrote.
247 ///
248 /// Judgement J8, which document 09 section 9.6 specifies and which document 04 section 4.6
249 /// keeps out of J1 because it is a statement about a pair of accesses rather than about one.
250 /// The payload holds the size of the access and the two numbers saying which pointer it went
251 /// through, and those are the same two [`crate::Restrict`] carries on the access itself.
252 ///
253 /// Read and write are two opcodes rather than one with a flag on it, because every bit of
254 /// [`crate::Flags`] is spoken for and because the operand would then be a constant the program
255 /// does not compute, which is the thing [`Opcode::CheckBounds`] says belongs in the payload.
256 CheckRestrictRead,
257 /// The same about a write, which is the half of the pair that makes the other half a violation.
258 ///
259 /// Two accesses that both only read are not a violation of anything, so what the scope records
260 /// is which of them wrote and the check refuses a pair only when at least one did.
261 CheckRestrictWrite,
262 /// A storage instance begins here, over a range, with a class.
263 ///
264 /// Judgement J4. This is the `alloca` for an automatic instance and the allocator's report
265 /// for an allocated one, and the range is a pointer and a length in registers rather than a
266 /// payload, because the length of a variable length array is not known when the instruction
267 /// is written down.
268 MetaBegin,
269 /// A storage instance ends here, which is judgement J5.
270 ///
271 /// Every capability for it fails from this point on and keeps failing after the address is
272 /// handed out again, which is what makes the check a use after free check rather than a use
273 /// after reallocation one.
274 MetaEnd,
275 /// The effective type of a range is now this one.
276 MetaType,
277 /// The effective types of a range are now the ones the range it was copied from had.
278 ///
279 /// Three operands, because a copy has two ranges and one length: the destination, the source,
280 /// and how many bytes moved. A `memcpy` does not store through a type, so there is no type to
281 /// name here and naming one would be wrong: C 6.5 says the copied bytes keep the effective type
282 /// they had, whatever that was, and the only place that is written down is the plane over the
283 /// source.
284 MetaTypeCopy,
285 /// The bytes of a range are now initialized.
286 MetaInit,
287 /// The bytes of a range are now initialized wherever the range they were copied from was.
288 ///
289 /// Three operands, for the reason [`Opcode::MetaTypeCopy`] has three. A copy does not write
290 /// values of its own, so whether a destination byte holds anything is whether the byte it came
291 /// from did, and the only place that is written down is the plane over the source. That is what
292 /// makes a structure filled member by member and then copied whole still have padding nothing
293 /// wrote, which is the infoleak the plane is for.
294 MetaInitCopy,
295 /// A range leaves the monitor's authority, or comes back, which is judgement J7.
296 MetaTransfer,
297 /// A declared exemption starts here, with the reason it was declared.
298 ///
299 /// Not an optimization hint. Everything between this and its `safe_region_end` is code the
300 /// monitor is told not to judge, so the reason it carries is a trust set entry, and
301 /// `spec/safe-memory/10-boundaries.md` section 10.2 counts them per build precisely so that
302 /// a reviewer can read what a binary's guarantee rests on.
303 SafeRegionBegin,
304 /// The end of the region the last `safe_region_begin` opened.
305 SafeRegionEnd,
306 /// A block that declares `restrict` pointers begins here, over a slot to keep its record in.
307 ///
308 /// The operand is the storage the record lives in, which is the block's own stack slot, and the
309 /// payload says how large it is. The clique the block was given is [`crate::Restrict::clique`]
310 /// of the payload and how many pointers it declares is [`crate::Restrict::base`], which is the
311 /// one place that field counts bases rather than naming one.
312 ///
313 /// A marker rather than something the front end could fold into the accesses, because the
314 /// promise is about the block's dynamic extent: a function called twice has made the promise
315 /// twice, and what the second call reached says nothing about the first.
316 RestrictEnter,
317 /// The block the last `restrict_enter` opened ends here.
318 ///
319 /// The operand is the same slot, so that the record can be unlinked from whatever encloses it
320 /// without the runtime having to keep a list of its own.
321 RestrictLeave,
322
323 // Control. Every one of these is a terminator.
324 /// An unconditional branch, `jump block1(%a, %b)`.
325 Jump,
326 /// A two-way branch on an `i1`.
327 BrIf,
328 /// A multi-way branch on an integer, with a default.
329 Switch,
330 /// A branch to an address, `indirect_br %0, block1, block2`.
331 ///
332 /// The targets are every block control can arrive at, which is what makes the edges of a
333 /// computed `goto` ordinary edges: nothing else in the compiler has to know that the
334 /// address decides which one it is. A target that is not listed is a branch that does not
335 /// happen, so a frontend that leaves one out has made a promise on the program's behalf.
336 IndirectBr,
337 /// A return, with the values the signature says.
338 Return,
339 /// A place control cannot reach, which the frontend emits after a `noreturn` call.
340 Unreachable,
341
342 // Calls.
343 /// A call to a named function.
344 Call,
345 /// A call through an address, carrying the signature it is called with.
346 CallIndirect,
347 /// A call in tail position that reuses the frame, which is a terminator.
348 TailCall,
349
350 // Intrinsics, which is the closed part. The open part is `TargetIntrinsic`.
351 /// Count leading zeroes.
352 Ctlz,
353 /// Count trailing zeroes.
354 Cttz,
355 /// Count set bits.
356 Ctpop,
357 /// Reverse the bytes.
358 Bswap,
359 /// Reverse the bits.
360 Bitreverse,
361 /// Signed addition, producing the result and whether it overflowed.
362 SAddOverflow,
363 /// Unsigned addition, producing the result and whether it overflowed.
364 UAddOverflow,
365 /// Signed subtraction, producing the result and whether it overflowed.
366 SSubOverflow,
367 /// Unsigned subtraction, producing the result and whether it overflowed.
368 USubOverflow,
369 /// Signed multiplication, producing the result and whether it overflowed.
370 SMulOverflow,
371 /// Unsigned multiplication, producing the result and whether it overflowed.
372 UMulOverflow,
373 /// `__builtin_expect`, which is the value with a hint attached.
374 Expect,
375 /// `__builtin_unreachable` as a hint on a path, distinct from the terminator.
376 UnreachableHint,
377 /// `__builtin_prefetch`.
378 Prefetch,
379 /// `__builtin_frame_address`.
380 FrameAddress,
381 /// `__builtin_return_address`.
382 ReturnAddress,
383 /// The start of a variable argument list.
384 VaStart,
385 /// One argument off a variable argument list, which moves the list on as it reads it. Two
386 /// of these on one list are two arguments and never one argument read twice, so whatever
387 /// decides which instructions may be folded together has to leave these alone.
388 VaArg,
389 /// One argument off a variable argument list, when that argument is an object rather than a
390 /// value, which is what a `struct` or a `union` read out of one is.
391 ///
392 /// It answers the address of the object rather than the object, because an aggregate is not
393 /// a value and there is nothing for one result to be. Where the object arrives in registers
394 /// there is no address until something makes one, so what this asks of a target is a place
395 /// to put the registers and the address of that place, which is the copy every psABI's own
396 /// description of the algorithm makes. It moves the list on for the reason [`Opcode::VaArg`]
397 /// does.
398 VaObject,
399 /// The end of a variable argument list.
400 VaEnd,
401 /// A copy of a variable argument list.
402 VaCopy,
403 /// The stack pointer, saved before a variable length array.
404 StackSave,
405 /// The stack pointer, restored after one.
406 StackRestore,
407 /// The marker a `setjmp` leaves, which pins everything live across it.
408 SetjmpMarker,
409 /// The marker a `longjmp` leaves.
410 LongjmpMarker,
411 /// A target-specific intrinsic, named rather than enumerated, for the vector builtins.
412 TargetIntrinsic,
413
414 /// Inline assembly. A terminator when it has labels, which is `asm goto`.
415 InlineAsm,
416}
417
418impl Opcode {
419 /// The textual form, which is also what the parser reads.
420 #[must_use]
421 pub const fn name(self) -> &'static str {
422 match self {
423 Self::IConst => "iconst",
424 Self::FConst => "fconst",
425 Self::Splat => "splat",
426 Self::GlobalAddr => "global_addr",
427 Self::BlockAddr => "block_addr",
428 Self::Add => "add",
429 Self::Sub => "sub",
430 Self::Mul => "mul",
431 Self::SDiv => "sdiv",
432 Self::UDiv => "udiv",
433 Self::SRem => "srem",
434 Self::URem => "urem",
435 Self::And => "and",
436 Self::Or => "or",
437 Self::Xor => "xor",
438 Self::Shl => "shl",
439 Self::LShr => "lshr",
440 Self::AShr => "ashr",
441 Self::FAdd => "fadd",
442 Self::FSub => "fsub",
443 Self::FMul => "fmul",
444 Self::FDiv => "fdiv",
445 Self::FRem => "frem",
446 Self::FNeg => "fneg",
447 Self::Fma => "fma",
448 Self::ICmp => "icmp",
449 Self::FCmp => "fcmp",
450 Self::Select => "select",
451 Self::Trunc => "trunc",
452 Self::SExt => "sext",
453 Self::ZExt => "zext",
454 Self::FPTrunc => "fptrunc",
455 Self::FPExt => "fpext",
456 Self::FPToSI => "fptosi",
457 Self::FPToUI => "fptoui",
458 Self::SIToFP => "sitofp",
459 Self::UIToFP => "uitofp",
460 Self::PtrToInt => "ptrtoint",
461 Self::IntToPtr => "inttoptr",
462 Self::Bitcast => "bitcast",
463 Self::MemEntry => "mem_entry",
464 Self::Alloca => "alloca",
465 Self::Load => "load",
466 Self::Store => "store",
467 Self::PtrAdd => "ptr_add",
468 Self::Memcpy => "memcpy",
469 Self::Memmove => "memmove",
470 Self::Memset => "memset",
471 Self::AtomicLoad => "atomic_load",
472 Self::AtomicStore => "atomic_store",
473 Self::AtomicRmw => "atomic_rmw",
474 Self::Cmpxchg => "cmpxchg",
475 Self::Fence => "fence",
476 Self::CapOf => "cap_of",
477 Self::CapLoad => "cap_load",
478 Self::CapStore => "cap_store",
479 Self::CapNull => "cap_null",
480 Self::CapNarrow => "cap_narrow",
481 Self::CapRecover => "cap_recover",
482 Self::CapExtent => "cap_extent",
483 Self::CapExtentBack => "cap_extent_back",
484 Self::CheckBounds => "check_bounds",
485 Self::CheckLive => "check_live",
486 Self::CheckType => "check_type",
487 Self::CheckInit => "check_init",
488 Self::CheckDeriv => "check_deriv",
489 Self::CheckRace => "check_race",
490 Self::CheckRestrictRead => "check_restrict_read",
491 Self::CheckRestrictWrite => "check_restrict_write",
492 Self::MetaBegin => "meta_begin",
493 Self::MetaEnd => "meta_end",
494 Self::MetaType => "meta_type",
495 Self::MetaTypeCopy => "meta_type_copy",
496 Self::MetaInit => "meta_init",
497 Self::MetaInitCopy => "meta_init_copy",
498 Self::MetaTransfer => "meta_transfer",
499 Self::SafeRegionBegin => "safe_region_begin",
500 Self::SafeRegionEnd => "safe_region_end",
501 Self::RestrictEnter => "restrict_enter",
502 Self::RestrictLeave => "restrict_leave",
503 Self::Jump => "jump",
504 Self::BrIf => "br_if",
505 Self::Switch => "switch",
506 Self::IndirectBr => "indirect_br",
507 Self::Return => "return",
508 Self::Unreachable => "unreachable",
509 Self::Call => "call",
510 Self::CallIndirect => "call_indirect",
511 Self::TailCall => "tail_call",
512 Self::Ctlz => "ctlz",
513 Self::Cttz => "cttz",
514 Self::Ctpop => "ctpop",
515 Self::Bswap => "bswap",
516 Self::Bitreverse => "bitreverse",
517 Self::SAddOverflow => "sadd_overflow",
518 Self::UAddOverflow => "uadd_overflow",
519 Self::SSubOverflow => "ssub_overflow",
520 Self::USubOverflow => "usub_overflow",
521 Self::SMulOverflow => "smul_overflow",
522 Self::UMulOverflow => "umul_overflow",
523 Self::Expect => "expect",
524 Self::UnreachableHint => "unreachable_hint",
525 Self::Prefetch => "prefetch",
526 Self::FrameAddress => "frame_address",
527 Self::ReturnAddress => "return_address",
528 Self::VaStart => "va_start",
529 Self::VaArg => "va_arg",
530 Self::VaObject => "va_object",
531 Self::VaEnd => "va_end",
532 Self::VaCopy => "va_copy",
533 Self::StackSave => "stacksave",
534 Self::StackRestore => "stackrestore",
535 Self::SetjmpMarker => "setjmp_marker",
536 Self::LongjmpMarker => "longjmp_marker",
537 Self::TargetIntrinsic => "target_intrinsic",
538 Self::InlineAsm => "inline_asm",
539 }
540 }
541
542 /// Every opcode, in the order they are declared.
543 ///
544 /// The parser walks this rather than holding a second table, because a second table is a
545 /// table that can disagree with the first one.
546 pub fn all() -> impl Iterator<Item = Self> {
547 ALL.iter().copied()
548 }
549
550 /// The opcode with that name, if there is one.
551 #[must_use]
552 pub fn from_name(name: &str) -> Option<Self> {
553 ALL.iter().copied().find(|op| op.name() == name)
554 }
555
556 /// Whether this ends a block.
557 ///
558 /// [`Opcode::InlineAsm`] is not here and is the one instruction whose answer depends on
559 /// the instruction rather than on the opcode: `asm goto` has successors and everything
560 /// else does not. Ask the instruction, not the opcode.
561 #[must_use]
562 pub const fn is_terminator(self) -> bool {
563 matches!(
564 self,
565 Self::Jump
566 | Self::BrIf
567 | Self::Switch
568 | Self::IndirectBr
569 | Self::Return
570 | Self::Unreachable
571 | Self::TailCall
572 )
573 }
574
575 /// Whether the operands can be swapped without changing the result.
576 ///
577 /// The floating point cases are commutative even under the strictest rounding, because
578 /// swapping the operands of an addition does not change which of them is a NaN, and the
579 /// sign of a NaN result is not something we promise anything about either way.
580 #[must_use]
581 pub const fn is_commutative(self) -> bool {
582 matches!(
583 self,
584 Self::Add
585 | Self::Mul
586 | Self::And
587 | Self::Or
588 | Self::Xor
589 | Self::FAdd
590 | Self::FMul
591 | Self::SAddOverflow
592 | Self::UAddOverflow
593 | Self::SMulOverflow
594 | Self::UMulOverflow
595 )
596 }
597
598 /// Whether this reads or writes memory, or has an effect the optimizer has to preserve.
599 ///
600 /// An instruction that answers no can be deleted when nothing uses its result, moved
601 /// across a call, and merged with another one computing the same thing. Everything else
602 /// has to be argued about individually, so the conservative answer is the true one here
603 /// and the list of exceptions is the part that is checked.
604 #[must_use]
605 pub const fn has_effects(self) -> bool {
606 !matches!(
607 self,
608 Self::IConst
609 | Self::FConst
610 | Self::Splat
611 | Self::GlobalAddr
612 | Self::BlockAddr
613 | Self::Add
614 | Self::Sub
615 | Self::Mul
616 | Self::SDiv
617 | Self::UDiv
618 | Self::SRem
619 | Self::URem
620 | Self::And
621 | Self::Or
622 | Self::Xor
623 | Self::Shl
624 | Self::LShr
625 | Self::AShr
626 | Self::FAdd
627 | Self::FSub
628 | Self::FMul
629 | Self::FDiv
630 | Self::FRem
631 | Self::FNeg
632 | Self::Fma
633 | Self::ICmp
634 | Self::FCmp
635 | Self::Select
636 | Self::Trunc
637 | Self::SExt
638 | Self::ZExt
639 | Self::FPTrunc
640 | Self::FPExt
641 | Self::FPToSI
642 | Self::FPToUI
643 | Self::SIToFP
644 | Self::UIToFP
645 | Self::PtrToInt
646 | Self::IntToPtr
647 | Self::Bitcast
648 | Self::PtrAdd
649 | Self::Ctlz
650 | Self::Cttz
651 | Self::Ctpop
652 | Self::Bswap
653 | Self::Bitreverse
654 | Self::SAddOverflow
655 | Self::UAddOverflow
656 | Self::SSubOverflow
657 | Self::USubOverflow
658 | Self::SMulOverflow
659 | Self::UMulOverflow
660 | Self::Expect
661 | Self::FrameAddress
662 | Self::ReturnAddress
663 | Self::MemEntry
664 // Three of the capability instructions are arithmetic on a pointer's
665 // provenance and touch nothing. The other three do: `cap_load` and
666 // `cap_store` are an access, and `cap_recover` reads the planes.
667 | Self::CapOf
668 | Self::CapNull
669 | Self::CapNarrow
670 )
671 }
672
673 /// Whether an instruction with this opcode touches memory.
674 ///
675 /// This is what decides whether it takes a memory operand once memory SSA is built, per
676 /// document 09 of `spec/optimizer`. It is written as the exceptions to touching memory
677 /// rather than as a list of what does, for the reason document 08.6 gives about the escape
678 /// analysis: an opcode added later has to end up on the conservative side by default, and a
679 /// list of what touches memory would silently leave a new one out.
680 ///
681 /// `mem_entry` answers no. It produces memory rather than touching it, which is the whole
682 /// of what it is for.
683 #[must_use]
684 pub const fn touches_memory(self) -> bool {
685 if !self.has_effects() {
686 return false;
687 }
688 !matches!(
689 self,
690 // Fresh storage nothing could have been reading, and the pointer that names it.
691 Self::Alloca
692 // The stack pointer, which is a register and not memory. Putting it back is a
693 // different matter and is below, because it takes storage away.
694 | Self::StackSave
695 // Control, which goes somewhere rather than touching anything. A tail call is
696 // not here, because it is a call.
697 | Self::Jump
698 | Self::BrIf
699 | Self::Switch
700 | Self::IndirectBr
701 | Self::Return
702 | Self::Unreachable
703 | Self::UnreachableHint
704 )
705 }
706
707 /// Whether an instruction with this opcode writes memory, and so produces a new version of
708 /// it rather than only reading the version it was given.
709 ///
710 /// Everything that touches memory writes it except the ones that plainly do not. A `fence`
711 /// writes nothing and is still a write here, because document 09.5 says an atomic or a
712 /// barrier is a definition nothing walks past, and giving it one is how that is expressed
713 /// in a representation whose only ordering is the memory chain.
714 ///
715 /// The checks read the planes and change nothing, which
716 /// `spec/safe-memory/06-instrumentation.md` section 6.2.4 states as the word `readonly`. A
717 /// check that trapped is a program that stopped and there is no version of memory after it
718 /// for anything to observe, so the trap costs nothing here. What it does cost is that a
719 /// check may not be moved across a plane write, and that is the memory chain saying so
720 /// rather than this.
721 #[must_use]
722 pub const fn writes_memory(self) -> bool {
723 self.touches_memory()
724 && !matches!(
725 self,
726 Self::Load
727 | Self::AtomicLoad
728 | Self::Prefetch
729 | Self::CapLoad
730 | Self::CapRecover
731 | Self::CapExtent
732 | Self::CapExtentBack
733 | Self::CheckBounds
734 | Self::CheckLive
735 | Self::CheckType
736 | Self::CheckInit
737 | Self::CheckDeriv
738 | Self::CheckRace
739 )
740 }
741
742 /// How many values this produces, for the opcodes where the count is fixed.
743 ///
744 /// `None` means the count comes from somewhere else: a call takes it from its signature,
745 /// and inline assembly takes it from its output constraints. A tail call is not one of
746 /// them, because whatever it returns goes straight out of the function and there is no
747 /// instruction after it to use anything.
748 #[must_use]
749 pub const fn results(self) -> Option<u8> {
750 match self {
751 Self::Call | Self::CallIndirect | Self::InlineAsm => None,
752 Self::Cmpxchg
753 | Self::SAddOverflow
754 | Self::UAddOverflow
755 | Self::SSubOverflow
756 | Self::USubOverflow
757 | Self::SMulOverflow
758 | Self::UMulOverflow => Some(2),
759 Self::Store
760 | Self::Memcpy
761 | Self::Memmove
762 | Self::Memset
763 | Self::AtomicStore
764 | Self::Fence
765 | Self::Prefetch
766 | Self::VaStart
767 | Self::VaEnd
768 | Self::VaCopy
769 | Self::StackRestore
770 | Self::UnreachableHint
771 | Self::SetjmpMarker
772 | Self::LongjmpMarker
773 | Self::CapStore
774 | Self::CheckBounds
775 | Self::CheckLive
776 | Self::CheckType
777 | Self::CheckInit
778 | Self::CheckDeriv
779 | Self::CheckRace
780 | Self::CheckRestrictRead
781 | Self::CheckRestrictWrite
782 | Self::MetaBegin
783 | Self::MetaEnd
784 | Self::MetaType
785 | Self::MetaTypeCopy
786 | Self::MetaInit
787 | Self::MetaInitCopy
788 | Self::MetaTransfer
789 | Self::SafeRegionBegin
790 | Self::SafeRegionEnd
791 | Self::RestrictEnter
792 | Self::RestrictLeave => Some(0),
793 _ if self.is_terminator() => Some(0),
794 _ => Some(1),
795 }
796 }
797
798 /// Whether an instruction with this opcode produces a capability.
799 ///
800 /// Five of the eight `cap` instructions. The other three consume one instead: `cap_store`
801 /// writes it beside a pointer, and `cap_extent` and `cap_extent_back` ask it a question about
802 /// itself and answer with a number. The reason this is a question about the opcode rather than
803 /// about the
804 /// result type is that the verifier asks it the other way round: it walks the results looking
805 /// for a `cap` and needs to know whether the instruction under it was entitled to make one.
806 #[must_use]
807 pub const fn makes_capability(self) -> bool {
808 matches!(
809 self,
810 Self::CapOf | Self::CapLoad | Self::CapNull | Self::CapNarrow | Self::CapRecover
811 )
812 }
813
814 /// Which payload an instruction with this opcode carries.
815 ///
816 /// The printer reads the payload it finds and does not need this. The parser has only the
817 /// opcode when it reaches the operands, so this is where the two of them agree on what
818 /// comes after them. An instruction carrying a payload of some other kind prints as text
819 /// the parser cannot read back, which is why the verifier checks it against
820 /// [`Extra::kind`](crate::Extra::kind) rather than leaving it to be found later.
821 #[must_use]
822 pub const fn extra_kind(self) -> ExtraKind {
823 match self {
824 Self::IConst | Self::FConst | Self::Splat => ExtraKind::Imm,
825 Self::GlobalAddr | Self::TargetIntrinsic => ExtraKind::Symbol,
826 Self::ICmp => ExtraKind::IntPred,
827 Self::FCmp => ExtraKind::FloatPred,
828 Self::Alloca
829 | Self::Load
830 | Self::Store
831 | Self::Memcpy
832 | Self::Memmove
833 | Self::Memset
834 | Self::AtomicLoad
835 | Self::AtomicStore
836 | Self::Cmpxchg
837 // Three of the checks are about a run of bytes and the payload is where the size
838 // of that run is, along with the alignment `check_bounds` wants and the aliasing
839 // node `check_type` compares against. The other three ask a question about a
840 // pointer and not about a range, so they carry nothing.
841 | Self::CheckBounds
842 | Self::CheckType
843 | Self::CheckInit
844 // The two `restrict` checks and the marker that opens their scope. The first two carry
845 // the size of the access and the two numbers saying which pointer it went through, and
846 // the third carries the size of the slot and the numbers describing the scope itself.
847 | Self::CheckRestrictRead
848 | Self::CheckRestrictWrite
849 | Self::RestrictEnter => ExtraKind::Mem,
850 // The plane writes. What each one needs beyond the range is different, and the range
851 // itself is operands, since the length of a variable length array is a value.
852 Self::MetaBegin => ExtraKind::Class,
853 Self::MetaTransfer => ExtraKind::Owner,
854 Self::MetaType => ExtraKind::Node,
855 Self::SafeRegionBegin => ExtraKind::Reason,
856 Self::VaObject => ExtraKind::VaObject,
857 Self::AtomicRmw => ExtraKind::Rmw,
858 Self::Fence => ExtraKind::Order,
859 Self::Jump | Self::BrIf | Self::BlockAddr | Self::IndirectBr => ExtraKind::Targets,
860 Self::Switch => ExtraKind::Switch,
861 Self::Call | Self::CallIndirect | Self::TailCall => ExtraKind::Call,
862 Self::InlineAsm => ExtraKind::Asm,
863 _ => ExtraKind::None,
864 }
865 }
866}
867
868/// Which of [`Extra`](crate::Extra)'s shapes an instruction carries.
869///
870/// The same list of names, without any of the payloads, so that a question about an opcode can
871/// be answered without an instruction to look at.
872#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
873pub enum ExtraKind {
874 /// Nothing.
875 None,
876 /// A constant.
877 Imm,
878 /// A name.
879 Symbol,
880 /// An integer comparison predicate.
881 IntPred,
882 /// A floating point comparison predicate.
883 FloatPred,
884 /// An access.
885 Mem,
886 /// An atomic read-modify-write.
887 Rmw,
888 /// A barrier's ordering.
889 Order,
890 /// Branch targets.
891 Targets,
892 /// A call.
893 Call,
894 /// A `switch`.
895 Switch,
896 /// Inline assembly.
897 Asm,
898 /// An object read off a variable argument list.
899 VaObject,
900 /// What kind of storage an instance is.
901 Class,
902 /// Who a range of memory went to.
903 Owner,
904 /// A metadata node.
905 Node,
906 /// Why a declared exemption is there.
907 Reason,
908}
909
910impl ExtraKind {
911 /// What it is, in words, for a message that names two of them and has to read as English.
912 #[must_use]
913 pub const fn name(self) -> &'static str {
914 match self {
915 Self::None => "nothing",
916 Self::Imm => "a constant",
917 Self::Symbol => "a name",
918 Self::IntPred => "an integer comparison",
919 Self::FloatPred => "a floating point comparison",
920 Self::Mem => "an access",
921 Self::Rmw => "a read-modify-write",
922 Self::Order => "an ordering",
923 Self::Targets => "branch targets",
924 Self::Call => "a call",
925 Self::Switch => "a switch",
926 Self::Asm => "inline assembly",
927 Self::VaObject => "an object off a variable argument list",
928 Self::Class => "a storage class",
929 Self::Owner => "an owner",
930 Self::Node => "a metadata node",
931 Self::Reason => "a reason",
932 }
933 }
934}
935
936impl fmt::Display for Opcode {
937 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
938 f.write_str(self.name())
939 }
940}
941
942/// Every opcode, which is what [`Opcode::all`] hands out.
943///
944/// This is written out rather than derived, and the test below is what keeps it complete: it
945/// checks the count against [`Opcode::InlineAsm`], the last variant, so a new opcode that is
946/// not added here fails the build rather than going quietly missing from the parser.
947static ALL: &[Opcode] = &[
948 Opcode::IConst,
949 Opcode::FConst,
950 Opcode::Splat,
951 Opcode::GlobalAddr,
952 Opcode::BlockAddr,
953 Opcode::Add,
954 Opcode::Sub,
955 Opcode::Mul,
956 Opcode::SDiv,
957 Opcode::UDiv,
958 Opcode::SRem,
959 Opcode::URem,
960 Opcode::And,
961 Opcode::Or,
962 Opcode::Xor,
963 Opcode::Shl,
964 Opcode::LShr,
965 Opcode::AShr,
966 Opcode::FAdd,
967 Opcode::FSub,
968 Opcode::FMul,
969 Opcode::FDiv,
970 Opcode::FRem,
971 Opcode::FNeg,
972 Opcode::Fma,
973 Opcode::ICmp,
974 Opcode::FCmp,
975 Opcode::Select,
976 Opcode::Trunc,
977 Opcode::SExt,
978 Opcode::ZExt,
979 Opcode::FPTrunc,
980 Opcode::FPExt,
981 Opcode::FPToSI,
982 Opcode::FPToUI,
983 Opcode::SIToFP,
984 Opcode::UIToFP,
985 Opcode::PtrToInt,
986 Opcode::IntToPtr,
987 Opcode::Bitcast,
988 Opcode::MemEntry,
989 Opcode::Alloca,
990 Opcode::Load,
991 Opcode::Store,
992 Opcode::PtrAdd,
993 Opcode::Memcpy,
994 Opcode::Memmove,
995 Opcode::Memset,
996 Opcode::AtomicLoad,
997 Opcode::AtomicStore,
998 Opcode::AtomicRmw,
999 Opcode::Cmpxchg,
1000 Opcode::Fence,
1001 Opcode::CapOf,
1002 Opcode::CapLoad,
1003 Opcode::CapStore,
1004 Opcode::CapNull,
1005 Opcode::CapNarrow,
1006 Opcode::CapRecover,
1007 Opcode::CapExtent,
1008 Opcode::CapExtentBack,
1009 Opcode::CheckBounds,
1010 Opcode::CheckLive,
1011 Opcode::CheckType,
1012 Opcode::CheckInit,
1013 Opcode::CheckDeriv,
1014 Opcode::CheckRace,
1015 Opcode::CheckRestrictRead,
1016 Opcode::CheckRestrictWrite,
1017 Opcode::MetaBegin,
1018 Opcode::MetaEnd,
1019 Opcode::MetaType,
1020 Opcode::MetaTypeCopy,
1021 Opcode::MetaInit,
1022 Opcode::MetaInitCopy,
1023 Opcode::MetaTransfer,
1024 Opcode::SafeRegionBegin,
1025 Opcode::SafeRegionEnd,
1026 Opcode::RestrictEnter,
1027 Opcode::RestrictLeave,
1028 Opcode::Jump,
1029 Opcode::BrIf,
1030 Opcode::Switch,
1031 Opcode::IndirectBr,
1032 Opcode::Return,
1033 Opcode::Unreachable,
1034 Opcode::Call,
1035 Opcode::CallIndirect,
1036 Opcode::TailCall,
1037 Opcode::Ctlz,
1038 Opcode::Cttz,
1039 Opcode::Ctpop,
1040 Opcode::Bswap,
1041 Opcode::Bitreverse,
1042 Opcode::SAddOverflow,
1043 Opcode::UAddOverflow,
1044 Opcode::SSubOverflow,
1045 Opcode::USubOverflow,
1046 Opcode::SMulOverflow,
1047 Opcode::UMulOverflow,
1048 Opcode::Expect,
1049 Opcode::UnreachableHint,
1050 Opcode::Prefetch,
1051 Opcode::FrameAddress,
1052 Opcode::ReturnAddress,
1053 Opcode::VaStart,
1054 Opcode::VaArg,
1055 Opcode::VaObject,
1056 Opcode::VaEnd,
1057 Opcode::VaCopy,
1058 Opcode::StackSave,
1059 Opcode::StackRestore,
1060 Opcode::SetjmpMarker,
1061 Opcode::LongjmpMarker,
1062 Opcode::TargetIntrinsic,
1063 Opcode::InlineAsm,
1064];
1065
1066/// The ten integer comparisons.
1067///
1068/// Signedness is on the predicate rather than on the type, for the same reason it is on
1069/// `sdiv` and `udiv`: the type space is halved and the operation says what it means.
1070#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
1071pub enum IntPred {
1072 /// Equal.
1073 Eq,
1074 /// Not equal.
1075 Ne,
1076 /// Signed less than.
1077 Slt,
1078 /// Signed less than or equal.
1079 Sle,
1080 /// Signed greater than.
1081 Sgt,
1082 /// Signed greater than or equal.
1083 Sge,
1084 /// Unsigned less than.
1085 Ult,
1086 /// Unsigned less than or equal.
1087 Ule,
1088 /// Unsigned greater than.
1089 Ugt,
1090 /// Unsigned greater than or equal.
1091 Uge,
1092}
1093
1094impl IntPred {
1095 /// The textual form.
1096 #[must_use]
1097 pub const fn name(self) -> &'static str {
1098 match self {
1099 Self::Eq => "eq",
1100 Self::Ne => "ne",
1101 Self::Slt => "slt",
1102 Self::Sle => "sle",
1103 Self::Sgt => "sgt",
1104 Self::Sge => "sge",
1105 Self::Ult => "ult",
1106 Self::Ule => "ule",
1107 Self::Ugt => "ugt",
1108 Self::Uge => "uge",
1109 }
1110 }
1111
1112 /// The predicate with that name, if there is one.
1113 #[must_use]
1114 pub fn from_name(name: &str) -> Option<Self> {
1115 Self::all().find(|pred| pred.name() == name)
1116 }
1117
1118 /// Every predicate.
1119 pub fn all() -> impl Iterator<Item = Self> {
1120 [
1121 Self::Eq,
1122 Self::Ne,
1123 Self::Slt,
1124 Self::Sle,
1125 Self::Sgt,
1126 Self::Sge,
1127 Self::Ult,
1128 Self::Ule,
1129 Self::Ugt,
1130 Self::Uge,
1131 ]
1132 .into_iter()
1133 }
1134
1135 /// The predicate that holds exactly when this one does not.
1136 #[must_use]
1137 pub const fn inverse(self) -> Self {
1138 match self {
1139 Self::Eq => Self::Ne,
1140 Self::Ne => Self::Eq,
1141 Self::Slt => Self::Sge,
1142 Self::Sge => Self::Slt,
1143 Self::Sle => Self::Sgt,
1144 Self::Sgt => Self::Sle,
1145 Self::Ult => Self::Uge,
1146 Self::Uge => Self::Ult,
1147 Self::Ule => Self::Ugt,
1148 Self::Ugt => Self::Ule,
1149 }
1150 }
1151
1152 /// The predicate that holds when the operands are given the other way round.
1153 #[must_use]
1154 pub const fn swapped(self) -> Self {
1155 match self {
1156 Self::Eq => Self::Eq,
1157 Self::Ne => Self::Ne,
1158 Self::Slt => Self::Sgt,
1159 Self::Sgt => Self::Slt,
1160 Self::Sle => Self::Sge,
1161 Self::Sge => Self::Sle,
1162 Self::Ult => Self::Ugt,
1163 Self::Ugt => Self::Ult,
1164 Self::Ule => Self::Uge,
1165 Self::Uge => Self::Ule,
1166 }
1167 }
1168
1169 /// Whether this reads its operands as signed. Equality reads them as neither.
1170 #[must_use]
1171 pub const fn is_signed(self) -> bool {
1172 matches!(self, Self::Slt | Self::Sle | Self::Sgt | Self::Sge)
1173 }
1174}
1175
1176impl fmt::Display for IntPred {
1177 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1178 f.write_str(self.name())
1179 }
1180}
1181
1182/// The floating point comparisons, ordered and unordered.
1183///
1184/// An ordered predicate is false if either operand is a NaN, and an unordered one is true. C's
1185/// `<` is `olt` and C's `!=` is `une`, which is the whole of why both families are here.
1186#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
1187pub enum FloatPred {
1188 /// Always false.
1189 False,
1190 /// Ordered and equal.
1191 Oeq,
1192 /// Ordered and greater than.
1193 Ogt,
1194 /// Ordered and greater than or equal.
1195 Oge,
1196 /// Ordered and less than.
1197 Olt,
1198 /// Ordered and less than or equal.
1199 Ole,
1200 /// Ordered and not equal.
1201 One,
1202 /// Ordered, which is to say neither operand is a NaN.
1203 Ord,
1204 /// Unordered, which is to say one of them is.
1205 Uno,
1206 /// Unordered or equal.
1207 Ueq,
1208 /// Unordered or greater than.
1209 Ugt,
1210 /// Unordered or greater than or equal.
1211 Uge,
1212 /// Unordered or less than.
1213 Ult,
1214 /// Unordered or less than or equal.
1215 Ule,
1216 /// Unordered or not equal.
1217 Une,
1218 /// Always true.
1219 True,
1220}
1221
1222impl FloatPred {
1223 /// The textual form.
1224 #[must_use]
1225 pub const fn name(self) -> &'static str {
1226 match self {
1227 Self::False => "false",
1228 Self::Oeq => "oeq",
1229 Self::Ogt => "ogt",
1230 Self::Oge => "oge",
1231 Self::Olt => "olt",
1232 Self::Ole => "ole",
1233 Self::One => "one",
1234 Self::Ord => "ord",
1235 Self::Uno => "uno",
1236 Self::Ueq => "ueq",
1237 Self::Ugt => "ugt",
1238 Self::Uge => "uge",
1239 Self::Ult => "ult",
1240 Self::Ule => "ule",
1241 Self::Une => "une",
1242 Self::True => "true",
1243 }
1244 }
1245
1246 /// The predicate with that name, if there is one.
1247 #[must_use]
1248 pub fn from_name(name: &str) -> Option<Self> {
1249 Self::all().find(|pred| pred.name() == name)
1250 }
1251
1252 /// Every predicate.
1253 pub fn all() -> impl Iterator<Item = Self> {
1254 [
1255 Self::False,
1256 Self::Oeq,
1257 Self::Ogt,
1258 Self::Oge,
1259 Self::Olt,
1260 Self::Ole,
1261 Self::One,
1262 Self::Ord,
1263 Self::Uno,
1264 Self::Ueq,
1265 Self::Ugt,
1266 Self::Uge,
1267 Self::Ult,
1268 Self::Ule,
1269 Self::Une,
1270 Self::True,
1271 ]
1272 .into_iter()
1273 }
1274
1275 /// The predicate that holds exactly when this one does not.
1276 #[must_use]
1277 pub const fn inverse(self) -> Self {
1278 match self {
1279 Self::False => Self::True,
1280 Self::Oeq => Self::Une,
1281 Self::Ogt => Self::Ule,
1282 Self::Oge => Self::Ult,
1283 Self::Olt => Self::Uge,
1284 Self::Ole => Self::Ugt,
1285 Self::One => Self::Ueq,
1286 Self::Ord => Self::Uno,
1287 Self::Uno => Self::Ord,
1288 Self::Ueq => Self::One,
1289 Self::Ugt => Self::Ole,
1290 Self::Uge => Self::Olt,
1291 Self::Ult => Self::Oge,
1292 Self::Ule => Self::Ogt,
1293 Self::Une => Self::Oeq,
1294 Self::True => Self::False,
1295 }
1296 }
1297
1298 /// The predicate that holds when the operands are given the other way round.
1299 #[must_use]
1300 pub const fn swapped(self) -> Self {
1301 match self {
1302 Self::Ogt => Self::Olt,
1303 Self::Olt => Self::Ogt,
1304 Self::Oge => Self::Ole,
1305 Self::Ole => Self::Oge,
1306 Self::Ugt => Self::Ult,
1307 Self::Ult => Self::Ugt,
1308 Self::Uge => Self::Ule,
1309 Self::Ule => Self::Uge,
1310 same => same,
1311 }
1312 }
1313
1314 /// Whether this is false when either operand is a NaN.
1315 ///
1316 /// [`FloatPred::False`] and [`FloatPred::True`] are neither ordered nor unordered, since
1317 /// they do not look at their operands at all, and both answer no here.
1318 #[must_use]
1319 pub const fn is_ordered(self) -> bool {
1320 matches!(
1321 self,
1322 Self::Oeq | Self::Ogt | Self::Oge | Self::Olt | Self::Ole | Self::One | Self::Ord
1323 )
1324 }
1325}
1326
1327impl fmt::Display for FloatPred {
1328 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1329 f.write_str(self.name())
1330 }
1331}
1332
1333#[cfg(test)]
1334mod tests {
1335 use super::*;
1336
1337 #[test]
1338 fn every_opcode_is_in_the_table() {
1339 // `InlineAsm` is the last variant, so its discriminant plus one is how many there are.
1340 // A new opcode declared after it moves this number, and a new opcode declared before
1341 // it and not added to `ALL` moves the length, so either mistake fails here.
1342 assert_eq!(ALL.len(), Opcode::InlineAsm as usize + 1);
1343 for (position, &op) in ALL.iter().enumerate() {
1344 assert_eq!(op as usize, position, "{op} is out of order in ALL");
1345 }
1346 }
1347
1348 #[test]
1349 fn every_opcode_name_is_one_word_the_reader_can_take() {
1350 // The textual form keeps the dot for the type suffix and the flags, so an opcode with a
1351 // dot in it reads back as a shorter opcode with a suffix that is not a type. The safety
1352 // instructions are spelled `cap_of` and not `cap.of` for this reason, and the
1353 // specification says so at `spec/safe-memory/06-instrumentation.md` section 6.2.2.
1354 for opcode in Opcode::all() {
1355 let name = opcode.name();
1356 assert!(!name.is_empty(), "an opcode with no name");
1357 assert!(
1358 name.bytes().all(|b| b.is_ascii_lowercase() || b.is_ascii_digit() || b == b'_'),
1359 "{name} is not one word"
1360 );
1361 }
1362 }
1363
1364 #[test]
1365 fn every_opcode_has_its_own_name_and_finds_it_again() {
1366 let mut names: Vec<&str> = Opcode::all().map(Opcode::name).collect();
1367 let total = names.len();
1368 names.sort_unstable();
1369 names.dedup();
1370 assert_eq!(names.len(), total, "two opcodes share a name");
1371 for op in Opcode::all() {
1372 assert_eq!(Opcode::from_name(op.name()), Some(op));
1373 }
1374 assert_eq!(Opcode::from_name("phi"), None);
1375 assert_eq!(Opcode::from_name("getelementptr"), None);
1376 assert_eq!(Opcode::from_name(""), None);
1377 }
1378
1379 #[test]
1380 fn the_terminators_are_the_ones_control_leaves_by() {
1381 let terminators: Vec<&str> =
1382 Opcode::all().filter(|op| op.is_terminator()).map(Opcode::name).collect();
1383 assert_eq!(
1384 terminators,
1385 ["jump", "br_if", "switch", "indirect_br", "return", "unreachable", "tail_call"]
1386 );
1387 }
1388
1389 #[test]
1390 fn a_terminator_produces_nothing() {
1391 for op in Opcode::all().filter(|op| op.is_terminator()) {
1392 assert_eq!(op.results(), Some(0), "{op}");
1393 }
1394 }
1395
1396 #[test]
1397 fn the_pair_producing_opcodes_are_the_ones_with_a_flag_beside_the_value() {
1398 let pairs: Vec<&str> =
1399 Opcode::all().filter(|op| op.results() == Some(2)).map(Opcode::name).collect();
1400 assert_eq!(
1401 pairs,
1402 [
1403 "cmpxchg",
1404 "sadd_overflow",
1405 "uadd_overflow",
1406 "ssub_overflow",
1407 "usub_overflow",
1408 "smul_overflow",
1409 "umul_overflow"
1410 ]
1411 );
1412 }
1413
1414 #[test]
1415 fn the_capability_instructions_are_the_ones_that_make_a_capability() {
1416 let makers: Vec<Opcode> = Opcode::all().filter(|op| op.makes_capability()).collect();
1417 assert_eq!(
1418 makers,
1419 vec![
1420 Opcode::CapOf,
1421 Opcode::CapLoad,
1422 Opcode::CapNull,
1423 Opcode::CapNarrow,
1424 Opcode::CapRecover
1425 ]
1426 );
1427 // The other three read a capability rather than making one. `cap_store` writes it out and
1428 // produces nothing at all, and the two extent queries answer with a number.
1429 assert!(!Opcode::CapStore.makes_capability());
1430 assert_eq!(Opcode::CapStore.results(), Some(0));
1431 assert!(!Opcode::CapExtent.makes_capability());
1432 assert_eq!(Opcode::CapExtent.results(), Some(1));
1433 assert!(!Opcode::CapExtentBack.makes_capability());
1434 assert_eq!(Opcode::CapExtentBack.results(), Some(1));
1435 for opcode in makers {
1436 assert_eq!(opcode.results(), Some(1), "{}", opcode.name());
1437 }
1438 }
1439
1440 #[test]
1441 fn a_check_reads_the_planes_and_writes_nothing() {
1442 let checks = [
1443 Opcode::CheckBounds,
1444 Opcode::CheckLive,
1445 Opcode::CheckType,
1446 Opcode::CheckInit,
1447 Opcode::CheckDeriv,
1448 Opcode::CheckRace,
1449 ];
1450 for opcode in checks {
1451 let name = opcode.name();
1452 // It traps, so it stays where it was put and nothing deletes it for having no
1453 // result. It reads a plane, so it takes a memory operand. It writes nothing, so
1454 // the access after it reads the version the check was given.
1455 assert!(opcode.has_effects(), "{name}");
1456 assert!(opcode.touches_memory(), "{name}");
1457 assert!(!opcode.writes_memory(), "{name}");
1458 assert_eq!(opcode.results(), Some(0), "{name}");
1459 }
1460 }
1461
1462 #[test]
1463 fn a_restrict_check_writes_memory_because_it_records_what_it_saw() {
1464 // The one place the sentence above does not hold. Every other check reads a plane and
1465 // leaves it alone, so the optimizer may hoist one out of a loop or keep the later of two
1466 // identical ones. These record the range they were asked about into the block's own slot,
1467 // so a check that ran twice saw two accesses and a check that was hoisted saw one, and
1468 // either rewrite changes what the next one answers. Saying they write memory is how the
1469 // memory chain refuses both.
1470 let recording = [
1471 Opcode::CheckRestrictRead,
1472 Opcode::CheckRestrictWrite,
1473 Opcode::RestrictEnter,
1474 Opcode::RestrictLeave,
1475 ];
1476 for opcode in recording {
1477 let name = opcode.name();
1478 assert!(opcode.has_effects(), "{name}");
1479 assert!(opcode.touches_memory(), "{name}");
1480 assert!(opcode.writes_memory(), "{name}");
1481 assert_eq!(opcode.results(), Some(0), "{name}");
1482 }
1483 }
1484
1485 #[test]
1486 fn the_capability_instructions_that_touch_memory_are_the_five_that_have_to() {
1487 // `cap_load` and `cap_store` are an access to the slot beside a pointer, and `cap_recover`
1488 // and the two extent queries read the planes. The other three are arithmetic on a
1489 // provenance the program already had, so the optimizer may treat them as it treats
1490 // `ptr_add`.
1491 assert!(!Opcode::CapOf.has_effects());
1492 assert!(!Opcode::CapNull.has_effects());
1493 assert!(!Opcode::CapNarrow.has_effects());
1494 assert!(Opcode::CapLoad.touches_memory() && !Opcode::CapLoad.writes_memory());
1495 assert!(Opcode::CapRecover.touches_memory() && !Opcode::CapRecover.writes_memory());
1496 assert!(Opcode::CapExtent.touches_memory() && !Opcode::CapExtent.writes_memory());
1497 assert!(Opcode::CapExtentBack.touches_memory() && !Opcode::CapExtentBack.writes_memory());
1498 assert!(Opcode::CapStore.writes_memory());
1499 }
1500
1501 #[test]
1502 fn memory_has_effects_and_arithmetic_does_not() {
1503 for op in [Opcode::Load, Opcode::Store, Opcode::Call, Opcode::Alloca, Opcode::Fence] {
1504 assert!(op.has_effects(), "{op}");
1505 }
1506 for op in [Opcode::Add, Opcode::FDiv, Opcode::ICmp, Opcode::PtrAdd, Opcode::IConst] {
1507 assert!(!op.has_effects(), "{op}");
1508 }
1509 }
1510
1511 #[test]
1512 fn commuting_is_only_claimed_where_it_holds() {
1513 assert!(Opcode::Add.is_commutative());
1514 assert!(Opcode::FAdd.is_commutative());
1515 assert!(!Opcode::Sub.is_commutative());
1516 assert!(!Opcode::FDiv.is_commutative());
1517 assert!(!Opcode::Shl.is_commutative());
1518 }
1519
1520 #[test]
1521 fn an_integer_predicate_inverts_and_swaps_back_to_itself() {
1522 for pred in IntPred::all() {
1523 assert_eq!(pred.inverse().inverse(), pred);
1524 assert_eq!(pred.swapped().swapped(), pred);
1525 assert_eq!(IntPred::from_name(pred.name()), Some(pred));
1526 }
1527 assert_eq!(IntPred::Slt.inverse(), IntPred::Sge);
1528 assert_eq!(IntPred::Slt.swapped(), IntPred::Sgt);
1529 assert_eq!(IntPred::from_name("lt"), None);
1530 }
1531
1532 #[test]
1533 fn a_floating_predicate_inverts_across_the_ordered_line() {
1534 for pred in FloatPred::all() {
1535 assert_eq!(pred.inverse().inverse(), pred);
1536 assert_eq!(pred.swapped().swapped(), pred);
1537 assert_eq!(FloatPred::from_name(pred.name()), Some(pred));
1538 }
1539 // Inverting has to cross the line, because the negation of an ordered comparison is
1540 // true when an operand is a NaN. This is where `!(a < b)` stops being `a >= b`. The
1541 // two constants are outside it: neither of them looks at its operands.
1542 for pred in FloatPred::all().filter(|p| !matches!(p, FloatPred::False | FloatPred::True)) {
1543 assert_ne!(pred.is_ordered(), pred.inverse().is_ordered(), "{pred}");
1544 }
1545 assert_eq!(FloatPred::Olt.inverse(), FloatPred::Uge);
1546 assert_eq!(FloatPred::Olt.swapped(), FloatPred::Ogt);
1547 }
1548
1549 #[test]
1550 fn swapping_a_predicate_keeps_it_ordered_or_unordered() {
1551 for pred in FloatPred::all() {
1552 assert_eq!(pred.is_ordered(), pred.swapped().is_ordered(), "{pred}");
1553 }
1554 for pred in IntPred::all() {
1555 assert_eq!(pred.is_signed(), pred.swapped().is_signed(), "{pred}");
1556 }
1557 }
1558
1559 #[test]
1560 fn no_two_predicates_share_a_name_within_their_family() {
1561 for names in [
1562 IntPred::all().map(IntPred::name).collect::<Vec<_>>(),
1563 FloatPred::all().map(FloatPred::name).collect::<Vec<_>>(),
1564 ] {
1565 let total = names.len();
1566 let mut names = names;
1567 names.sort_unstable();
1568 names.dedup();
1569 assert_eq!(names.len(), total);
1570 }
1571 }
1572}