qcode/value/insn/mnemonic.rs
1use crate::value::{
2 LocalValueId,
3 function::FunctionId,
4 insn::{
5 Apply, Assert, BadInsn, Binary, Branch, BranchInd, CBranch, Call, CallInd, Carry, Extract,
6 FloatToFloat, FloatToInt, Gep, IntToFloat, IntrinsicApp, IsFloatNaN, Load, LzCount, Map,
7 PCodeOp, PopCount, Range, Return, ReturnValue, SBorrow, SCarry, Scan, Sext, Store, Switch,
8 TailCall, Tuple, Unary, Zext,
9 },
10};
11use smallvec::SmallVec;
12
13/// Operand list returned by [`MnemonicKind::args`]. Inline-stores up to two
14/// operands (covering every fixed-arity instruction — binops, casts, loads,
15/// flags, …), so the pervasive per-instruction operand walks in the analysis
16/// passes don't heap-allocate. Variable-arity ops (calls, tuples, `scan`) spill
17/// to the heap only when they exceed two operands.
18pub type Args = SmallVec<[LocalValueId; 2]>;
19
20/// Implemented by each concrete instruction type.
21///
22/// Provides the common interface that [`Mnemonic`] dispatches to: a short
23/// opcode string, argument enumeration, and terminator status.
24pub trait MnemonicKind {
25 /// Short textual opcode, e.g. `"load"`, `"int_add"`, `"branch"`.
26 fn opcode(&self) -> &'static str;
27
28 // TODO: replace with a visitor pattern to avoid the need for this method
29 /// Returns the [`LocalValueId`]s of all operands consumed by this instruction.
30 fn args(&self) -> Args;
31
32 /// Returns `true` if this instruction ends a basic block.
33 ///
34 /// Terminators are: [`Branch`], [`CBranch`], [`BranchInd`], [`Switch`], [`Call`],
35 /// [`CallInd`], and [`Return`].
36 fn is_terminator(&self) -> bool {
37 false
38 }
39}
40
41/// The operation performed by an [`Instruction`](crate::value::Instruction).
42///
43/// `Mnemonic` is a closed enum over all supported IR operations. It is
44/// `#[non_exhaustive]` so that new operations can be added without requiring
45/// downstream crates to update exhaustive match arms.
46///
47/// # Categories
48///
49/// | Variants | Category |
50/// |---|---|
51/// | [`Load`], [`Store`] | Memory access |
52/// | [`Branch`], [`CBranch`], [`BranchInd`], [`Switch`], [`Call`], [`CallInd`], [`Return`], [`ReturnValue`], [`BadInsn`] | Control flow (terminators) |
53/// | [`Unop`](Mnemonic::Unop) | Unary integer/float/bool operations |
54/// | [`Binop`](Mnemonic::Binop) | Binary integer/float/bool operations |
55/// | [`Zext`], [`Sext`], [`Range`], [`IntToFloat`], [`FloatToInt`], [`FloatToFloat`] | Type casts and bit extraction |
56/// | [`IsFloatNaN`], [`PopCount`], [`LzCount`], [`Carry`], [`SCarry`], [`SBorrow`] | Bit/flag operations |
57/// | [`PCodeOp`] | User-defined or architecture-specific operation |
58/// | [`Intrinsic`](crate::value::insn::intrinsic::Intrinsic) | Pure named intrinsic function (e.g. `rol`, `ror`) |
59#[non_exhaustive]
60#[derive(Debug, Clone, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
61pub enum Mnemonic {
62 /// Load a value from a memory space.
63 Load(Load),
64 /// Store a value to a memory space.
65 Store(Store),
66 /// Unconditional direct branch to a static target block.
67 Branch(Branch),
68 /// Conditional branch: taken when the condition operand is non-zero.
69 CBranch(CBranch),
70 /// Unconditional indirect branch to a dynamically-computed address.
71 BranchInd(BranchInd),
72 /// Multi-way dispatch on an integer scrutinee — a resolved jump table.
73 Switch(Switch),
74 /// Direct call to a known function.
75 Call(Call),
76 /// Tail call: a function-level transfer of control to another function's
77 /// entry (thunk / tail jump). Carries a [`FunctionId`], never a foreign
78 /// block — see [`TailCall`].
79 TailCall(TailCall),
80 /// Value-level application of a pure lambda function.
81 Apply(Apply),
82 /// Indirect call through a computed function pointer.
83 CallInd(CallInd),
84 /// Return from the current function.
85 Return(Return),
86 /// Value return from a lambda function.
87 ReturnValue(ReturnValue),
88 /// Bytes that do not decode to a valid instruction. A terminator with no
89 /// successors (see [`BadInsn`]).
90 BadInsn(BadInsn),
91 /// A unary integer, float, or boolean operation.
92 Unop(Unary),
93 /// A binary integer, float, or boolean operation.
94 Binop(Binary),
95 /// Extract a contiguous byte range from a value.
96 Range(Range),
97 /// Convert an integer to a floating-point value.
98 IntToFloat(IntToFloat),
99 /// Convert a floating-point value to a different float width.
100 FloatToFloat(FloatToFloat),
101 /// Convert a floating-point value to an integer (truncate toward zero).
102 FloatToInt(FloatToInt),
103 /// Zero-extend a value to a wider integer.
104 Zext(Zext),
105 /// Sign-extend a value to a wider integer.
106 Sext(Sext),
107 /// Test whether a floating-point value is NaN.
108 IsFloatNaN(IsFloatNaN),
109 /// Count the number of set bits (population count / Hamming weight).
110 PopCount(PopCount),
111 /// Count leading zero bits.
112 LzCount(LzCount),
113 /// Unsigned addition carry-out flag.
114 Carry(Carry),
115 /// Signed addition carry-out (overflow) flag.
116 SCarry(SCarry),
117 /// Signed subtraction borrow flag.
118 SBorrow(SBorrow),
119 /// Assert when resolving an execution trace
120 Assert(Assert),
121 /// A user-defined or architecture-specific p-code operation.
122 PCodeOp(PCodeOp),
123 /// A pure named intrinsic function (e.g. `rol`, `ror`). Categorically pure:
124 /// no memory or observable side effects.
125 Intrinsic(IntrinsicApp),
126 /// Build an aggregate (tuple) value from ordered fields.
127 Tuple(Tuple),
128 /// Project a single field out of an aggregate value.
129 Extract(Extract),
130 /// Compute the address of a struct field (typed, named pointer arithmetic).
131 Gep(Gep),
132 /// Total element-wise map over an array value (a projectable loop).
133 Map(Map),
134 /// Total left-scan (prefix fold) over an array value: a projectable loop
135 /// whose per-element write depends on the previous iteration's result.
136 Scan(Scan),
137}
138
139impl Mnemonic {
140 /// The unresolved direct-callee slot carried by this mnemonic, if any.
141 pub fn minted_callee_slot(&self) -> Option<u32> {
142 match self {
143 Self::Call(call) => call.target.minted(),
144 Self::TailCall(call) => call.target.minted(),
145 Self::Apply(apply) => apply.target.minted(),
146 Self::Map(map) => map.body.minted(),
147 Self::Scan(scan) => scan.body.minted(),
148 _ => None,
149 }
150 }
151
152 /// Resolve one pass-local direct-callee placeholder to its installed
153 /// function ID. Returns whether this mnemonic contained that placeholder.
154 pub fn resolve_minted_callee(&mut self, slot: u32, real: FunctionId) -> bool {
155 let callee = match self {
156 Self::Call(call) => Some(&mut call.target),
157 Self::TailCall(call) => Some(&mut call.target),
158 Self::Apply(apply) => Some(&mut apply.target),
159 Self::Map(map) => Some(&mut map.body),
160 Self::Scan(scan) => Some(&mut scan.body),
161 _ => None,
162 };
163 let Some(callee) = callee else {
164 return false;
165 };
166 if *callee != super::Callee::Minted(slot) {
167 return false;
168 }
169 *callee = super::Callee::Real(real);
170 true
171 }
172
173 fn as_kind(&self) -> &dyn MnemonicKind {
174 match self {
175 Mnemonic::Load(m) => m,
176 Mnemonic::Store(m) => m,
177 Mnemonic::Branch(m) => m,
178 Mnemonic::CBranch(m) => m,
179 Mnemonic::BranchInd(m) => m,
180 Mnemonic::Switch(m) => m,
181 Mnemonic::Call(m) => m,
182 Mnemonic::TailCall(m) => m,
183 Mnemonic::Apply(m) => m,
184 Mnemonic::CallInd(m) => m,
185 Mnemonic::Return(m) => m,
186 Mnemonic::ReturnValue(m) => m,
187 Mnemonic::BadInsn(m) => m,
188 Mnemonic::Range(m) => m,
189 Mnemonic::Unop(m) => m,
190 Mnemonic::Binop(m) => m,
191 Mnemonic::IsFloatNaN(m) => m,
192 Mnemonic::IntToFloat(m) => m,
193 Mnemonic::FloatToFloat(m) => m,
194 Mnemonic::FloatToInt(m) => m,
195 Mnemonic::Zext(m) => m,
196 Mnemonic::Sext(m) => m,
197 Mnemonic::PopCount(m) => m,
198 Mnemonic::LzCount(m) => m,
199 Mnemonic::Carry(m) => m,
200 Mnemonic::SCarry(m) => m,
201 Mnemonic::SBorrow(m) => m,
202 Mnemonic::Assert(m) => m,
203 Mnemonic::PCodeOp(m) => m,
204 Mnemonic::Intrinsic(m) => m,
205 Mnemonic::Tuple(m) => m,
206 Mnemonic::Extract(m) => m,
207 Mnemonic::Gep(m) => m,
208 Mnemonic::Map(m) => m,
209 Mnemonic::Scan(m) => m,
210 }
211 }
212
213 pub fn opcode(&self) -> &'static str {
214 self.as_kind().opcode()
215 }
216
217 pub fn is_terminator(&self) -> bool {
218 self.as_kind().is_terminator()
219 }
220
221 /// Whether an instruction must be kept even if its result has no users:
222 /// it writes memory, transfers control, calls, asserts, or invokes an
223 /// opaque p-code op. This is the single source of truth shared by DCE
224 /// (which must not delete these) and the emitter (which must always print
225 /// them); keep the two in agreement by routing both through here.
226 pub fn has_side_effects(&self) -> bool {
227 matches!(
228 self,
229 Mnemonic::Store(_)
230 | Mnemonic::Call(_)
231 | Mnemonic::CallInd(_)
232 | Mnemonic::PCodeOp(_)
233 | Mnemonic::Assert(_)
234 ) || self.is_terminator()
235 }
236
237 /// The callee of a direct [`Call`] or body of a [`Map`], or `None`
238 /// (including indirect [`CallInd`] calls, whose target is not statically
239 /// known). Used to maintain the reverse call graph.
240 pub fn call_target(&self) -> Option<FunctionId> {
241 match self {
242 Mnemonic::Call(call) => call.target.real(),
243 Mnemonic::TailCall(tc) => tc.target.real(),
244 Mnemonic::Apply(apply) => apply.target.real(),
245 Mnemonic::Map(map) => map.body.real(),
246 Mnemonic::Scan(scan) => scan.body.real(),
247 _ => None,
248 }
249 }
250
251 /// The statically-known CFG target blocks this mnemonic branches to — the
252 /// `Branch` target and both `CBranch` arms — as bare body-local indices. Empty
253 /// for non-branch or indirect terminators (a `BranchInd` resolves to computed
254 /// addresses, not a static block). Strict IR locality (context-split ruling 2)
255 /// guarantees each target lives in this terminator's own arena, so a caller
256 /// with the owning function in hand recovers the full `BlockId` via
257 /// `BlockId::new(func, local)`.
258 pub fn target_blocks(&self) -> smallvec::SmallVec<[crate::value::LocalBlockId; 2]> {
259 match self {
260 Mnemonic::Branch(b) => smallvec::smallvec![b.target],
261 Mnemonic::CBranch(c) => smallvec::smallvec![c.success_block, c.failure_block],
262 // Every arm plus the default, if it has one: a resolved dispatch
263 // knows all of its successors statically.
264 Mnemonic::Switch(s) => s
265 .cases
266 .iter()
267 .map(|case| case.target)
268 .chain(s.default)
269 .collect(),
270 _ => smallvec::SmallVec::new(),
271 }
272 }
273
274 pub fn args(&self) -> Args {
275 self.as_kind().args()
276 }
277
278 /// Replace every occurrence of `old` with `new` in this instruction's operands.
279 pub fn replace_value(&mut self, old: LocalValueId, new: LocalValueId) {
280 match self {
281 Mnemonic::Load(m) => {
282 if m.ptr == old {
283 m.ptr = new;
284 }
285 }
286 Mnemonic::Store(m) => {
287 if m.ptr == old {
288 m.ptr = new;
289 }
290 if m.src == old {
291 m.src = new;
292 }
293 }
294 Mnemonic::CBranch(m) => {
295 if m.condition == old {
296 m.condition = new;
297 }
298 m.success_args.iter_mut().for_each(|a| {
299 if *a == old {
300 *a = new;
301 }
302 });
303 m.failure_args.iter_mut().for_each(|a| {
304 if *a == old {
305 *a = new;
306 }
307 });
308 }
309 Mnemonic::BranchInd(m) => {
310 if m.ptr == old {
311 m.ptr = new;
312 }
313 }
314 Mnemonic::Switch(m) => {
315 if m.scrutinee == old {
316 m.scrutinee = new;
317 }
318 for case in m.cases.iter_mut() {
319 case.args.iter_mut().for_each(|a| {
320 if *a == old {
321 *a = new;
322 }
323 });
324 }
325 m.default_args.iter_mut().for_each(|a| {
326 if *a == old {
327 *a = new;
328 }
329 });
330 }
331 Mnemonic::Call(m) => {
332 m.args.iter_mut().for_each(|a| {
333 if *a == old {
334 *a = new;
335 }
336 });
337 }
338 Mnemonic::TailCall(m) => {
339 m.args.iter_mut().for_each(|a| {
340 if *a == old {
341 *a = new;
342 }
343 });
344 }
345 Mnemonic::Apply(m) => {
346 m.args.iter_mut().for_each(|a| {
347 if *a == old {
348 *a = new;
349 }
350 });
351 }
352 Mnemonic::CallInd(m) => {
353 if m.ptr == old {
354 m.ptr = new;
355 }
356 m.args.iter_mut().for_each(|a| {
357 if *a == old {
358 *a = new;
359 }
360 });
361 }
362 Mnemonic::Return(m) => {
363 if m.ptr == old {
364 m.ptr = new;
365 }
366 if let Some(v) = m.value.as_mut()
367 && *v == old
368 {
369 *v = new;
370 }
371 }
372 Mnemonic::ReturnValue(m) => {
373 if m.value == old {
374 m.value = new;
375 }
376 }
377 // No operands to rewrite.
378 Mnemonic::BadInsn(_) => {}
379 Mnemonic::Unop(m) => {
380 if m.src == old {
381 m.src = new;
382 }
383 }
384 Mnemonic::Binop(m) => {
385 if m.lhs == old {
386 m.lhs = new;
387 }
388 if m.rhs == old {
389 m.rhs = new;
390 }
391 }
392 Mnemonic::Range(m) => {
393 if m.src == old {
394 m.src = new;
395 }
396 }
397 Mnemonic::Zext(m) => {
398 if m.src == old {
399 m.src = new;
400 }
401 }
402 Mnemonic::Sext(m) => {
403 if m.src == old {
404 m.src = new;
405 }
406 }
407 Mnemonic::IntToFloat(m) => {
408 if m.src == old {
409 m.src = new;
410 }
411 }
412 Mnemonic::FloatToFloat(m) => {
413 if m.src == old {
414 m.src = new;
415 }
416 }
417 Mnemonic::FloatToInt(m) => {
418 if m.src == old {
419 m.src = new;
420 }
421 }
422 Mnemonic::IsFloatNaN(m) => {
423 if m.src == old {
424 m.src = new;
425 }
426 }
427 Mnemonic::PopCount(m) => {
428 if m.src == old {
429 m.src = new;
430 }
431 }
432 Mnemonic::LzCount(m) => {
433 if m.src == old {
434 m.src = new;
435 }
436 }
437 Mnemonic::Carry(m) => {
438 if m.lhs == old {
439 m.lhs = new;
440 }
441 if m.rhs == old {
442 m.rhs = new;
443 }
444 }
445 Mnemonic::SCarry(m) => {
446 if m.lhs == old {
447 m.lhs = new;
448 }
449 if m.rhs == old {
450 m.rhs = new;
451 }
452 }
453 Mnemonic::SBorrow(m) => {
454 if m.lhs == old {
455 m.lhs = new;
456 }
457 if m.rhs == old {
458 m.rhs = new;
459 }
460 }
461 Mnemonic::PCodeOp(m) => {
462 m.args.iter_mut().for_each(|a| {
463 if *a == old {
464 *a = new;
465 }
466 });
467 if let Some(v) = m.dst.as_mut()
468 && *v == old
469 {
470 *v = new;
471 }
472 }
473 Mnemonic::Branch(m) => {
474 m.args.iter_mut().for_each(|a| {
475 if *a == old {
476 *a = new;
477 }
478 });
479 }
480 Mnemonic::Intrinsic(m) => {
481 m.args.iter_mut().for_each(|a| {
482 if *a == old {
483 *a = new;
484 }
485 });
486 }
487 Mnemonic::Tuple(m) => {
488 m.fields.iter_mut().for_each(|a| {
489 if *a == old {
490 *a = new;
491 }
492 });
493 }
494 Mnemonic::Assert(m) => {
495 if m.condition == old {
496 m.condition = new;
497 }
498 }
499 Mnemonic::Extract(m) => {
500 if m.agg == old {
501 m.agg = new;
502 }
503 }
504 Mnemonic::Gep(m) => {
505 if m.base == old {
506 m.base = new;
507 }
508 }
509 Mnemonic::Map(m) => {
510 // `body` is a function symbol, not a value operand — left intact.
511 if m.src == old {
512 m.src = new;
513 }
514 m.captures.iter_mut().for_each(|a| {
515 if *a == old {
516 *a = new;
517 }
518 });
519 }
520 Mnemonic::Scan(m) => {
521 // `body` is a function symbol, not a value operand — left intact.
522 if m.init == old {
523 m.init = new;
524 }
525 if m.src == old {
526 m.src = new;
527 }
528 m.captures.iter_mut().for_each(|a| {
529 if *a == old {
530 *a = new;
531 }
532 });
533 }
534 }
535 }
536}