trident/ir/lir/mod.rs
1//! LIR — Low-level Intermediate Representation.
2//!
3//! Three-address form with virtual registers and flat control flow.
4//! Designed for register-machine targets (x86-64, ARM64, RISC-V).
5//!
6//! The LIR mirrors TIR's 4-tier structure:
7//! Tier 0: Structure (control flow, program structure, passthrough)
8//! Tier 1: Universal (arithmetic, I/O, memory, assertions, hash, events, storage)
9//! Tier 2: Provable (sponge, merkle)
10//! Tier 3: Recursion (extension field, FRI folding)
11//!
12//! Key differences from TIR:
13//! - Explicit virtual registers (`Reg`) instead of implicit stack
14//! - Three-address: `Add(dst, src1, src2)` instead of stack consumption
15//! - Flat control flow: `Branch`/`Jump`/`LabelDef` instead of nested bodies
16//! - No Dup/Swap/Pop — register machines don't need stack manipulation
17
18pub mod convert;
19pub mod lower;
20
21use std::fmt;
22
23// ─── Virtual Register ─────────────────────────────────────────────
24
25/// A virtual register. Physical mapping is decided per-target during
26/// register allocation.
27#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
28pub struct Reg(pub u32);
29
30impl fmt::Display for Reg {
31 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
32 write!(f, "v{}", self.0)
33 }
34}
35
36// ─── Label ────────────────────────────────────────────────────────
37
38/// A control-flow label for flat branch/jump targets.
39#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
40pub struct Label(pub String);
41
42impl Label {
43 pub fn new(name: impl Into<String>) -> Self {
44 Self(name.into())
45 }
46}
47
48impl fmt::Display for Label {
49 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
50 write!(f, "{}", self.0)
51 }
52}
53
54// ─── LIR Operations ──────────────────────────────────────────────
55
56/// 53 LIR operations. Higher tier = narrower target set.
57///
58/// **Tier 0 — Structure** (every program, every target)
59/// Control flow (5), Program structure (4), Passthrough (2) = 11
60///
61/// **Tier 1 — Universal** (compiles to every target)
62/// Register (2), Arithmetic (15), I/O (3), Memory (4),
63/// Assertions (1), Hash (1), Events (2), Storage (2) = 30
64///
65/// **Tier 2 — Provable** (requires a proof-capable target)
66/// Sponge (4), Merkle (2) = 6
67///
68/// **Tier 3 — Recursion** (requires recursive verification capability)
69/// Extension field (2), Folding (2), Verification (2) = 6
70///
71/// Total: 11 + 30 + 6 + 6 = 53 variants
72#[derive(Debug, Clone)]
73pub enum LIROp {
74 // ═══════════════════════════════════════════════════════════════
75 // Tier 0 — Structure (11)
76 // The scaffolding. Present in every program, on every target.
77 // ═══════════════════════════════════════════════════════════════
78
79 // ── Control flow (5) ──
80 /// Direct call to a named function.
81 Call(String),
82 /// Return from the current function.
83 Return,
84 /// Halt execution.
85 Halt,
86 /// Conditional branch: if `cond` is nonzero jump to `if_true`, else `if_false`.
87 Branch {
88 cond: Reg,
89 if_true: Label,
90 if_false: Label,
91 },
92 /// Unconditional jump.
93 Jump(Label),
94
95 // ── Program structure (4) ──
96 /// Label definition (branch/jump target).
97 LabelDef(Label),
98 /// Function entry point.
99 FnStart(String),
100 /// Function end marker.
101 FnEnd,
102 /// Program entry point.
103 Entry(String),
104
105 // ── Passthrough (2) ──
106 /// Comment text (lowering adds target-specific prefix).
107 Comment(String),
108 /// Inline assembly passed through verbatim.
109 Asm { lines: Vec<String> },
110
111 // ═══════════════════════════════════════════════════════════════
112 // Tier 1 — Universal (30)
113 // Compiles to every target. Register primitives, arithmetic,
114 // I/O, memory, hashing, events, storage.
115 // ═══════════════════════════════════════════════════════════════
116
117 // ── Register (2) ──
118 /// Load an immediate value into a register.
119 LoadImm(Reg, u64),
120 /// Register-to-register move.
121 Move(Reg, Reg),
122
123 // ── Arithmetic (15) ──
124 /// dst = src1 + src2 (mod p)
125 Add(Reg, Reg, Reg),
126 /// dst = src1 * src2 (mod p)
127 Mul(Reg, Reg, Reg),
128 /// dst = (src1 == src2) ? 1 : 0
129 Eq(Reg, Reg, Reg),
130 /// dst = (src1 < src2) ? 1 : 0
131 Lt(Reg, Reg, Reg),
132 /// dst = src1 & src2 (bitwise)
133 And(Reg, Reg, Reg),
134 /// dst = src1 | src2 (bitwise)
135 Or(Reg, Reg, Reg),
136 /// dst = src1 ^ src2 (bitwise)
137 Xor(Reg, Reg, Reg),
138 /// (dst_quot, dst_rem) = divmod(src1, src2)
139 DivMod {
140 dst_quot: Reg,
141 dst_rem: Reg,
142 src1: Reg,
143 src2: Reg,
144 },
145 /// dst = src1 << src2
146 Shl(Reg, Reg, Reg),
147 /// dst = src1 >> src2
148 Shr(Reg, Reg, Reg),
149 /// dst = multiplicative inverse of src (in the field)
150 Invert(Reg, Reg),
151 /// (dst_hi, dst_lo) = split(src) — decompose into two limbs
152 Split { dst_hi: Reg, dst_lo: Reg, src: Reg },
153 /// dst = floor(log2(src))
154 Log2(Reg, Reg),
155 /// dst = base ^ exp
156 Pow(Reg, Reg, Reg),
157 /// dst = popcount(src)
158 PopCount(Reg, Reg),
159
160 // ── I/O (3) ──
161 /// Read `count` values from public input into consecutive regs starting at `dst`.
162 ReadIo { dst: Reg, count: u32 },
163 /// Write `count` values from consecutive regs starting at `src` to public output.
164 WriteIo { src: Reg, count: u32 },
165 /// Read `count` nondeterministic hint values into consecutive regs starting at `dst`.
166 Hint { dst: Reg, count: u32 },
167
168 // ── Memory (4) ──
169 /// dst = mem[base + offset]
170 Load { dst: Reg, base: Reg, offset: i32 },
171 /// mem[base + offset] = src
172 Store { src: Reg, base: Reg, offset: i32 },
173 /// Load `width` consecutive words from mem[base] into regs starting at `dst`.
174 LoadMulti { dst: Reg, base: Reg, width: u32 },
175 /// Store `width` consecutive words from regs starting at `src` to mem[base].
176 StoreMulti { src: Reg, base: Reg, width: u32 },
177
178 // ── Assertions (1) ──
179 /// Assert `count` consecutive regs starting at `src` are all nonzero.
180 Assert { src: Reg, count: u32 },
181
182 // ── Hash (1) ──
183 /// dst = hash(src..src+count). Width is metadata for optimization.
184 Hash { dst: Reg, src: Reg, count: u32 },
185
186 // ── Events (2) ──
187 /// Reveal an observable event. Fields in consecutive regs starting at `src`.
188 Reveal {
189 name: String,
190 tag: u64,
191 src: Reg,
192 field_count: u32,
193 },
194 /// Seal (hash-commit) an event.
195 Seal {
196 name: String,
197 tag: u64,
198 src: Reg,
199 field_count: u32,
200 },
201
202 // ── RAM (2) ──
203 /// Read from RAM. Key in `key`, result in `dst`.
204 RamRead { dst: Reg, key: Reg, width: u32 },
205 /// Write to RAM. Key in `key`, value in `src`.
206 RamWrite { key: Reg, src: Reg, width: u32 },
207
208 // ═══════════════════════════════════════════════════════════════
209 // Tier 2 — Provable (6)
210 // Requires a proof-capable target. Sponge construction and Merkle
211 // authentication have no meaningful equivalent on conventional VMs.
212 // ═══════════════════════════════════════════════════════════════
213
214 // ── Sponge (4) ──
215 /// Initialize sponge state in `dst`.
216 SpongeInit(Reg),
217 /// Absorb `src` into sponge `state`.
218 SpongeAbsorb { state: Reg, src: Reg },
219 /// Squeeze output from sponge `state` into `dst`.
220 SpongeSqueeze { dst: Reg, state: Reg },
221 /// Absorb from memory address `addr` into sponge `state`.
222 SpongeLoad { state: Reg, addr: Reg },
223
224 // ── Merkle (2) ──
225 /// One Merkle authentication step.
226 MerkleStep { dst: Reg, node: Reg, sibling: Reg },
227 /// Merkle step reading sibling from memory at `addr`.
228 MerkleLoad { dst: Reg, node: Reg, addr: Reg },
229
230 // ═══════════════════════════════════════════════════════════════
231 // Tier 3 — Recursion (6)
232 // STARK-in-STARK verification primitives. Extension field
233 // arithmetic, FRI folding steps, and proof verification blocks.
234 // ═══════════════════════════════════════════════════════════════
235
236 // ── Extension field (2) ──
237 /// dst = src1 * src2 in the extension field.
238 ExtMul(Reg, Reg, Reg),
239 /// dst = inverse of src in the extension field.
240 ExtInvert(Reg, Reg),
241
242 // ── Folding (2) ──
243 /// Fold extension field elements.
244 FoldExt { dst: Reg, src1: Reg, src2: Reg },
245 /// Fold base field elements.
246 FoldBase { dst: Reg, src1: Reg, src2: Reg },
247
248 // ── Verification (2) ──
249 /// Recursive proof verification block start marker.
250 /// The verification ops follow until ProofBlockEnd.
251 ProofBlock { program_hash: String },
252 /// End of a proof verification block.
253 ProofBlockEnd,
254}
255
256// ─── Display ──────────────────────────────────────────────────────
257
258impl fmt::Display for LIROp {
259 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
260 match self {
261 // Tier 0
262 LIROp::Call(label) => write!(f, "call {}", label),
263 LIROp::Return => write!(f, "ret"),
264 LIROp::Halt => write!(f, "halt"),
265 LIROp::Branch {
266 cond,
267 if_true,
268 if_false,
269 } => {
270 write!(f, "br {}, {}, {}", cond, if_true, if_false)
271 }
272 LIROp::Jump(label) => write!(f, "jmp {}", label),
273 LIROp::LabelDef(label) => write!(f, "{}:", label),
274 LIROp::FnStart(name) => write!(f, "fn {}:", name),
275 LIROp::FnEnd => write!(f, "fn_end"),
276 LIROp::Entry(main) => write!(f, "entry {}", main),
277 LIROp::Comment(text) => write!(f, "// {}", text),
278 LIROp::Asm { lines } => write!(f, "asm({} lines)", lines.len()),
279
280 // Tier 1
281 LIROp::LoadImm(dst, val) => write!(f, "li {}, {}", dst, val),
282 LIROp::Move(dst, src) => write!(f, "mv {}, {}", dst, src),
283 LIROp::Add(d, a, b) => write!(f, "add {}, {}, {}", d, a, b),
284 LIROp::Mul(d, a, b) => write!(f, "mul {}, {}, {}", d, a, b),
285 LIROp::Eq(d, a, b) => write!(f, "eq {}, {}, {}", d, a, b),
286 LIROp::Lt(d, a, b) => write!(f, "lt {}, {}, {}", d, a, b),
287 LIROp::And(d, a, b) => write!(f, "and {}, {}, {}", d, a, b),
288 LIROp::Or(d, a, b) => write!(f, "or {}, {}, {}", d, a, b),
289 LIROp::Xor(d, a, b) => write!(f, "xor {}, {}, {}", d, a, b),
290 LIROp::DivMod {
291 dst_quot,
292 dst_rem,
293 src1,
294 src2,
295 } => {
296 write!(f, "divmod {}, {}, {}, {}", dst_quot, dst_rem, src1, src2)
297 }
298 LIROp::Shl(d, a, b) => write!(f, "shl {}, {}, {}", d, a, b),
299 LIROp::Shr(d, a, b) => write!(f, "shr {}, {}, {}", d, a, b),
300 LIROp::Invert(d, s) => write!(f, "inv {}, {}", d, s),
301 LIROp::Split {
302 dst_hi,
303 dst_lo,
304 src,
305 } => {
306 write!(f, "split {}, {}, {}", dst_hi, dst_lo, src)
307 }
308 LIROp::Log2(d, s) => write!(f, "log2 {}, {}", d, s),
309 LIROp::Pow(d, b, e) => write!(f, "pow {}, {}, {}", d, b, e),
310 LIROp::PopCount(d, s) => write!(f, "popcnt {}, {}", d, s),
311 LIROp::ReadIo { dst, count } => write!(f, "read_io {}, {}", dst, count),
312 LIROp::WriteIo { src, count } => write!(f, "write_io {}, {}", src, count),
313 LIROp::Hint { dst, count } => write!(f, "hint {}, {}", dst, count),
314 LIROp::Load { dst, base, offset } => {
315 write!(f, "ld {}, [{}+{}]", dst, base, offset)
316 }
317 LIROp::Store { src, base, offset } => {
318 write!(f, "st {}, [{}+{}]", src, base, offset)
319 }
320 LIROp::LoadMulti { dst, base, width } => {
321 write!(f, "ldm {}, [{}], {}", dst, base, width)
322 }
323 LIROp::StoreMulti { src, base, width } => {
324 write!(f, "stm {}, [{}], {}", src, base, width)
325 }
326 LIROp::Assert { src, count } => {
327 write!(f, "assert {}, {}", src, count)
328 }
329 LIROp::Hash { dst, src, count } => {
330 write!(f, "hash {}, {}, {}", dst, src, count)
331 }
332 LIROp::Reveal {
333 name,
334 src,
335 field_count,
336 ..
337 } => {
338 write!(f, "reveal {}({}, {})", name, src, field_count)
339 }
340 LIROp::Seal {
341 name,
342 src,
343 field_count,
344 ..
345 } => {
346 write!(f, "seal {}({}, {})", name, src, field_count)
347 }
348 LIROp::RamRead { dst, key, width } => {
349 write!(f, "ram_read {}, {}, {}", dst, key, width)
350 }
351 LIROp::RamWrite { key, src, width } => {
352 write!(f, "ram_write {}, {}, {}", key, src, width)
353 }
354
355 // Tier 2
356 LIROp::SpongeInit(d) => write!(f, "sponge_init {}", d),
357 LIROp::SpongeAbsorb { state, src } => {
358 write!(f, "sponge_absorb {}, {}", state, src)
359 }
360 LIROp::SpongeSqueeze { dst, state } => {
361 write!(f, "sponge_squeeze {}, {}", dst, state)
362 }
363 LIROp::SpongeLoad { state, addr } => {
364 write!(f, "sponge_load {}, {}", state, addr)
365 }
366 LIROp::MerkleStep { dst, node, sibling } => {
367 write!(f, "merkle_step {}, {}, {}", dst, node, sibling)
368 }
369 LIROp::MerkleLoad { dst, node, addr } => {
370 write!(f, "merkle_load {}, {}, {}", dst, node, addr)
371 }
372
373 // Tier 3
374 LIROp::ExtMul(d, a, b) => write!(f, "ext_mul {}, {}, {}", d, a, b),
375 LIROp::ExtInvert(d, s) => write!(f, "ext_inv {}, {}", d, s),
376 LIROp::FoldExt { dst, src1, src2 } => {
377 write!(f, "fold_ext {}, {}, {}", dst, src1, src2)
378 }
379 LIROp::FoldBase { dst, src1, src2 } => {
380 write!(f, "fold_base {}, {}, {}", dst, src1, src2)
381 }
382 LIROp::ProofBlock { program_hash } => {
383 write!(f, "proof_block {}", program_hash)
384 }
385 LIROp::ProofBlockEnd => write!(f, "proof_block_end"),
386 }
387 }
388}
389
390// ─── Tests ────────────────────────────────────────────────────────
391
392#[cfg(test)]
393mod tests;