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