logicaffeine_compile/vm/
peephole.rs

1//! ★ THE IR PEEPHOLE ★ — a semantics-preserving `CompiledProgram → CompiledProgram`
2//! transform: block-local forward **copy-propagation** followed by **dead-move
3//! elimination**. It exists for the backends that lower the bytecode straight to a
4//! final target with no downstream optimizing assembler — RISC-V asm, WASM, the
5//! spatial fabric. gcc already performs exactly this coalescing for the C tier
6//! (register-to-register moves fold away, dead copies vanish), so C does not need
7//! it; the flat backends ship the VM compiler's move cascades verbatim without it.
8//!
9//! The measured target is the swap idiom. `Set a to b. Set b to t.` lowers to a
10//! five-move cascade through fresh temps every loop iteration:
11//! ```text
12//!   Move R10 = R8   Move R11 = R3   Move R1 = R11   Move R12 = R10   Move R3 = R12
13//! ```
14//! Copy-propagation rewrites the temp reads to their roots and the now-dead temp
15//! moves fall to DCE, leaving the optimal `Move R1 = R3. Move R3 = R8.` — three
16//! fewer ops in the hottest loop, per iteration.
17//!
18//! ## Soundness — the asymmetry that makes it safe
19//!
20//! A wrong coalesce miscompiles every backend, so the register model is deliberately
21//! one-sided:
22//! - `reads` is a **superset** of the true reads (over-approximate). Liveness can
23//!   then never *under*-count a use, so a still-needed value is never judged dead.
24//! - `kills` is a **subset** of the registers an op FULLY overwrites
25//!   (under-approximate). Liveness can then never *over*-count a def, so a live range
26//!   is never cut short.
27//! - `clobbers` = `kills ∪ mutates` invalidates a copy on BOTH its key and its
28//!   value side. This is what keeps copy-propagation sound under LOGOS's
29//!   **value-semantics collections**: after `Move x = list`, mutating OR reassigning
30//!   `list` must kill the `x = list` fact, because a copy-on-write push makes `x` and
31//!   `list` diverge.
32//! - The in-place-mutated collection/struct register is **never rewritable** — pushing
33//!   to `x` (a copy of `list`) is not the same as pushing to `list` once value
34//!   semantics clone on write, so a read that is really an in-place mutation site is
35//!   left untouched.
36//! - Only `Move` ops are ever deleted (their semantics are total and side-effect free);
37//!   and only when the destination is provably dead or the move is a self-copy.
38//!
39//! Every register classifier below is EXHAUSTIVE on `Op` (no `_` arm): a newly added
40//! instruction fails to compile until it is classified, so no op can silently escape
41//! the model. `peephole_soundness_lock` proves `program_outcome(peephole(P)) ==
42//! program_outcome(P)` over the corpus + a fuzzer, and that the op count strictly drops
43//! on the swap-idiom programs.
44
45use super::instruction::{CompiledProgram, Op, Reg};
46use std::collections::{HashMap, HashSet};
47
48/// Run the peephole to a fixpoint, in place. Copy-propagate once (a single forward
49/// pass fully resolves within-block chains, because the copy map stores roots), then
50/// iterate liveness + dead-move elimination until no move is removed.
51pub fn peephole(program: &mut CompiledProgram) {
52    copy_propagate(program);
53    loop {
54        let live_out = liveness(program);
55        let dead = dead_moves(program, &live_out);
56        if dead.is_empty() {
57            break;
58        }
59        remove_ops(program, &dead);
60    }
61}
62
63// ───────────────────────── control-flow model ─────────────────────────
64
65/// The absolute jump/branch targets `op` can transfer control to (NOT the fallthrough).
66fn branch_targets(op: &Op) -> Vec<usize> {
67    match op {
68        Op::Jump { target } => vec![*target],
69        Op::JumpIfFalse { target, .. } | Op::JumpIfTrue { target, .. } => vec![*target],
70        Op::IterNext { exit, .. } => vec![*exit],
71        _ => vec![],
72    }
73}
74
75/// A terminator ends its basic block — control does not fall through to `pc + 1`.
76fn is_hard_terminator(op: &Op) -> bool {
77    matches!(
78        op,
79        Op::Jump { .. } | Op::Return { .. } | Op::ReturnNothing | Op::Halt | Op::FailWith { .. }
80    )
81}
82
83/// Whether `op` is a branch (conditional or iterator step) — it has BOTH a jump target
84/// and a fallthrough successor, and starts a new block after it.
85fn is_branch(op: &Op) -> bool {
86    matches!(
87        op,
88        Op::JumpIfFalse { .. } | Op::JumpIfTrue { .. } | Op::IterNext { .. }
89    )
90}
91
92/// The successors of the op at `pc` (fallthrough + branch targets), respecting function
93/// region walls: a fallthrough into a function `entry_pc` is not a real edge (Main ends
94/// in `Halt` before the bodies, each body ends in a `Return`), so it is dropped.
95pub(crate) fn successors(pc: usize, code: &[Op], entries: &HashSet<usize>) -> Vec<usize> {
96    let op = &code[pc];
97    let mut succ = branch_targets(op);
98    if !is_hard_terminator(op) {
99        let next = pc + 1;
100        if next < code.len() && !entries.contains(&next) {
101            succ.push(next);
102        }
103    }
104    succ
105}
106
107/// The leaders (basic-block heads) of the flat program: pc 0, every function entry, every
108/// branch/jump target, and every op immediately after a branch or terminator. The copy map
109/// resets at each leader (a join may be entered from predecessors with different copies).
110fn leaders(program: &CompiledProgram) -> HashSet<usize> {
111    let code = &program.code;
112    let mut ls: HashSet<usize> = HashSet::new();
113    ls.insert(0);
114    for f in &program.functions {
115        ls.insert(f.entry_pc);
116    }
117    for (pc, op) in code.iter().enumerate() {
118        for t in branch_targets(op) {
119            ls.insert(t);
120        }
121        if (is_hard_terminator(op) || is_branch(op)) && pc + 1 < code.len() {
122            ls.insert(pc + 1);
123        }
124    }
125    ls
126}
127
128fn function_entries(program: &CompiledProgram) -> HashSet<usize> {
129    program.functions.iter().map(|f| f.entry_pc).collect()
130}
131
132// ───────────────────────── register effects (exhaustive) ─────────────────────────
133
134/// Push a `[start, start + count)` register range.
135fn push_range(out: &mut Vec<Reg>, start: Reg, count: u16) {
136    for i in 0..count {
137        out.push(start.wrapping_add(i));
138    }
139}
140
141/// A SUPERSET of the registers `op` reads — the ISA's exhaustive read set, with a closure's capture
142/// window taken from the program.
143fn reads(op: &Op, program: &CompiledProgram, out: &mut Vec<Reg>) {
144    op.for_each_read_reg(
145        |func| {
146            program
147                .functions
148                .get(func as usize)
149                .map_or(0, |f| f.captures.len())
150        },
151        |r| out.push(r),
152    );
153}
154
155/// The registers `op` FULLY overwrites — a SUBSET of true defs (under-approximate: an
156/// in-place *mutation* is NOT a kill, it is a read that keeps the value live). Exhaustive.
157fn kills(op: &Op, out: &mut Vec<Reg>) {
158    match op {
159        Op::LoadConst { dst, .. }
160        | Op::Move { dst, .. }
161        | Op::Add { dst, .. }
162        | Op::Sub { dst, .. }
163        | Op::Mul { dst, .. }
164        | Op::Div { dst, .. }
165        | Op::ExactDiv { dst, .. }
166        | Op::FloorDiv { dst, .. }
167        | Op::Mod { dst, .. }
168        | Op::DivPow2 { dst, .. }
169        | Op::MagicDivU { dst, .. }
170        | Op::Lt { dst, .. }
171        | Op::Gt { dst, .. }
172        | Op::LtEq { dst, .. }
173        | Op::GtEq { dst, .. }
174        | Op::Eq { dst, .. }
175        | Op::ApproxEq { dst, .. }
176        | Op::NotEq { dst, .. }
177        | Op::Not { dst, .. }
178        | Op::Concat { dst, .. }
179        | Op::SeqConcat { dst, .. }
180        | Op::Pow { dst, .. }
181        | Op::BitXor { dst, .. }
182        | Op::BitAnd { dst, .. }
183        | Op::BitOr { dst, .. }
184        | Op::Shl { dst, .. }
185        | Op::Shr { dst, .. }
186        | Op::Index { dst, .. }
187        | Op::IndexUnchecked { dst, .. }
188        | Op::Length { dst, .. }
189        | Op::Contains { dst, .. }
190        | Op::SliceOp { dst, .. }
191        | Op::DeepClone { dst, .. }
192        | Op::FormatValue { dst, .. }
193        | Op::UnionOp { dst, .. }
194        | Op::IntersectOp { dst, .. }
195        | Op::GetField { dst, .. }
196        | Op::TestArm { dst, .. }
197        | Op::BindArm { dst, .. }
198        | Op::NewList { dst, .. }
199        | Op::NewEmptyList { dst, .. }
200        | Op::NewEmptyListWithCapacity { dst, .. }
201        | Op::NewEmptyListFixed { dst, .. }
202        | Op::NewEmptyListI32 { dst, .. }
203        | Op::NewEmptySet { dst, .. }
204        | Op::NewEmptyMap { dst, .. }
205        | Op::NewEmptyMapWithCapacity { dst, .. }
206        | Op::NewRange { dst, .. }
207        | Op::NewTuple { dst, .. }
208        | Op::NewStruct { dst, .. }
209        | Op::NewInductive { dst, .. }
210        | Op::NewCrdt { dst, .. }
211        | Op::MakeClosure { dst, .. }
212        | Op::Args { dst, .. }
213        | Op::LoadToday { dst, .. }
214        | Op::LoadNow { dst, .. }
215        | Op::GlobalGet { dst, .. }
216        | Op::Call { dst, .. }
217        | Op::CallBuiltin { dst, .. }
218        | Op::CallValue { dst, .. }
219        | Op::ListPop { dst, .. }
220        | Op::ChanNew { dst, .. }
221        | Op::ChanRecv { dst, .. }
222        | Op::ChanTrySend { dst, .. }
223        | Op::ChanTryRecv { dst, .. }
224        | Op::TaskAwait { dst, .. }
225        | Op::SelectWait { dst_arm: dst }
226        | Op::NetMakePeer { dst, .. }
227        | Op::NetAwait { dst, .. }
228        | Op::BigIntWide { dst, .. }
229        | Op::Tcp { dst, .. }
230        | Op::SpawnHandle { dst, .. } => out.push(*dst),
231        // dst = R[dst] + R[src] — dst is written (also read, tracked in `reads`)
232        Op::AddAssign { dst, .. } => out.push(*dst),
233        // the reversible core rewrites its place / swaps a,b (also reads them)
234        Op::RevAdd { place, .. }
235        | Op::RevSub { place, .. }
236        | Op::RevXor { place, .. }
237        | Op::RevNeg { place } => out.push(*place),
238        Op::RevSwap { a, b } => {
239            out.push(*a);
240            out.push(*b);
241        }
242        // a select recv arm's received value lands in `var`
243        Op::SelectArmRecv { var, .. } => out.push(*var),
244        // tuple destructure writes a whole window
245        Op::DestructureTuple { start, count, .. } => push_range(out, *start, *count),
246        // NetSync writes the merged counter back to dst (also reads it)
247        Op::NetSync { dst, .. } => out.push(*dst),
248        // ops that overwrite nothing (mutate in place, effect only, or pure control)
249        Op::RemoveFrom { .. }
250        | Op::SetIndex { .. }
251        | Op::SetIndexUnchecked { .. }
252        | Op::ListPush { .. }
253        | Op::ListPushField { .. }
254        | Op::SetAdd { .. }
255        | Op::StructInsert { .. }
256        | Op::CrdtBump { .. }
257        | Op::CrdtMerge { .. }
258        | Op::CrdtJoin { .. }
259        | Op::CrdtAppend { .. }
260        | Op::CrdtResolve { .. }
261        | Op::EnsureOwned { .. }
262        | Op::GlobalSet { .. }
263        | Op::Return { .. }
264        | Op::ReturnNothing
265        | Op::Show { .. }
266        | Op::Obs { .. }
267        | Op::Sleep { .. }
268        | Op::IterPrepare { .. }
269        | Op::IterNext { .. }
270        | Op::IterPop
271        | Op::RegionBoundsGuard { .. }
272        | Op::CheckPolicy { .. }
273        | Op::ChanSend { .. }
274        | Op::ChanClose { .. }
275        | Op::Spawn { .. }
276        | Op::TaskAbort { .. }
277        | Op::SelectArmTimeout { .. }
278        | Op::NetConnect { .. }
279        | Op::NetListen { .. }
280        | Op::NetSend { .. }
281        | Op::NetStream { .. }
282        | Op::Serve { .. }
283        | Op::Jump { .. }
284        | Op::JumpIfFalse { .. }
285        | Op::JumpIfTrue { .. }
286        | Op::Halt
287        | Op::FailWith { .. } => {}
288    }
289}
290
291/// The registers an op mutates IN PLACE (read + kept, not a kill). A copy touching such a
292/// register must be invalidated (value semantics: the mutated buffer diverges from a copy).
293pub(crate) fn mutates(op: &Op, out: &mut Vec<Reg>) {
294    match op {
295        Op::ListPush { list, .. } => out.push(*list),
296        Op::ListPushField { obj, .. } => out.push(*obj),
297        Op::SetAdd { set, .. } => out.push(*set),
298        Op::RemoveFrom { collection, .. } => out.push(*collection),
299        Op::SetIndex { collection, .. } | Op::SetIndexUnchecked { collection, .. } => {
300            out.push(*collection)
301        }
302        Op::StructInsert { obj, .. } => out.push(*obj),
303        Op::CrdtBump { obj, .. } => out.push(*obj),
304        Op::CrdtMerge { target, .. } | Op::CrdtJoin { target, .. } => out.push(*target),
305        Op::CrdtAppend { seq, .. } => out.push(*seq),
306        Op::CrdtResolve { obj, .. } => out.push(*obj),
307        Op::ListPop { list, .. } => out.push(*list),
308        // a copy-on-write barrier may re-seat the register's buffer identity
309        Op::EnsureOwned { reg } => out.push(*reg),
310        // EXHAUSTIVE (no `_`): every op that mutates NO register in place. A future op that mutates
311        // a register must be moved above, or its copies would not be invalidated — a miscompile.
312        Op::LoadConst { .. }
313        | Op::Move { .. }
314        | Op::Add { .. }
315        | Op::AddAssign { .. }
316        | Op::Sub { .. }
317        | Op::Mul { .. }
318        | Op::Div { .. }
319        | Op::ExactDiv { .. }
320        | Op::FloorDiv { .. }
321        | Op::Mod { .. }
322        | Op::DivPow2 { .. }
323        | Op::MagicDivU { .. }
324        | Op::Lt { .. }
325        | Op::Gt { .. }
326        | Op::LtEq { .. }
327        | Op::GtEq { .. }
328        | Op::Eq { .. }
329        | Op::ApproxEq { .. }
330        | Op::NotEq { .. }
331        | Op::Not { .. }
332        | Op::Concat { .. }
333        | Op::SeqConcat { .. }
334        | Op::Pow { .. }
335        | Op::BitXor { .. }
336        | Op::BitAnd { .. }
337        | Op::BitOr { .. }
338        | Op::Shl { .. }
339        | Op::Shr { .. }
340        | Op::RevAdd { .. }
341        | Op::RevSub { .. }
342        | Op::RevXor { .. }
343        | Op::RevNeg { .. }
344        | Op::RevSwap { .. }
345        | Op::Index { .. }
346        | Op::IndexUnchecked { .. }
347        | Op::Length { .. }
348        | Op::Contains { .. }
349        | Op::SliceOp { .. }
350        | Op::DeepClone { .. }
351        | Op::FormatValue { .. }
352        | Op::UnionOp { .. }
353        | Op::IntersectOp { .. }
354        | Op::GetField { .. }
355        | Op::TestArm { .. }
356        | Op::BindArm { .. }
357        | Op::NewRange { .. }
358        | Op::NewList { .. }
359        | Op::NewEmptyList { .. }
360        | Op::NewEmptyListWithCapacity { .. }
361        | Op::NewEmptyListFixed { .. }
362        | Op::NewEmptyListI32 { .. }
363        | Op::NewEmptySet { .. }
364        | Op::NewEmptyMap { .. }
365        | Op::NewEmptyMapWithCapacity { .. }
366        | Op::NewTuple { .. }
367        | Op::NewStruct { .. }
368        | Op::NewInductive { .. }
369        | Op::NewCrdt { .. }
370        | Op::MakeClosure { .. }
371        | Op::Args { .. }
372        | Op::LoadToday { .. }
373        | Op::LoadNow { .. }
374        | Op::GlobalGet { .. }
375        | Op::GlobalSet { .. }
376        | Op::Call { .. }
377        | Op::CallBuiltin { .. }
378        | Op::CallValue { .. }
379        | Op::Return { .. }
380        | Op::ReturnNothing
381        | Op::Show { .. }
382        | Op::Obs { .. }
383        | Op::Sleep { .. }
384        | Op::IterPrepare { .. }
385        | Op::IterNext { .. }
386        | Op::IterPop
387        | Op::DestructureTuple { .. }
388        | Op::RegionBoundsGuard { .. }
389        | Op::CheckPolicy { .. }
390        | Op::BigIntWide { .. }
391        | Op::ChanNew { .. }
392        | Op::ChanSend { .. }
393        | Op::ChanRecv { .. }
394        | Op::ChanTrySend { .. }
395        | Op::ChanTryRecv { .. }
396        | Op::ChanClose { .. }
397        | Op::Spawn { .. }
398        | Op::SpawnHandle { .. }
399        | Op::TaskAwait { .. }
400        | Op::TaskAbort { .. }
401        | Op::SelectArmRecv { .. }
402        | Op::SelectArmTimeout { .. }
403        | Op::SelectWait { .. }
404        | Op::NetConnect { .. }
405        | Op::NetListen { .. }
406        | Op::NetSend { .. }
407        | Op::NetStream { .. }
408        | Op::NetAwait { .. }
409        | Op::NetMakePeer { .. }
410        | Op::NetSync { .. }
411        | Op::Tcp { .. }
412        | Op::Serve { .. }
413        | Op::Jump { .. }
414        | Op::JumpIfFalse { .. }
415        | Op::JumpIfTrue { .. }
416        | Op::Halt
417        | Op::FailWith { .. } => {}
418    }
419}
420
421/// The registers whose current value this op invalidates as a copy source/target:
422/// everything it fully overwrites plus everything it mutates in place.
423fn clobbers(op: &Op, out: &mut Vec<Reg>) {
424    kills(op, out);
425    mutates(op, out);
426}
427
428/// Visit every REWRITABLE read field of `op` by mutable reference — the pure scalar value
429/// reads copy-propagation may substitute. Deliberately EXCLUDES: range operands (a call's
430/// arg window must stay contiguous), in-place-mutated collection/struct registers (value
431/// semantics would diverge), the read-modify-write `dst` of `AddAssign`/reversible ops, and
432/// speculative/effectful operands left untouched out of caution. Everything omitted here is
433/// still counted by [`reads`] for liveness — it simply is not a substitution site.
434fn for_each_rewritable_read(op: &mut Op, f: &mut impl FnMut(&mut Reg)) {
435    match op {
436        Op::Add { lhs, rhs, .. }
437        | Op::Sub { lhs, rhs, .. }
438        | Op::Mul { lhs, rhs, .. }
439        | Op::Div { lhs, rhs, .. }
440        | Op::ExactDiv { lhs, rhs, .. }
441        | Op::FloorDiv { lhs, rhs, .. }
442        | Op::Mod { lhs, rhs, .. }
443        | Op::Lt { lhs, rhs, .. }
444        | Op::Gt { lhs, rhs, .. }
445        | Op::LtEq { lhs, rhs, .. }
446        | Op::GtEq { lhs, rhs, .. }
447        | Op::Eq { lhs, rhs, .. }
448        | Op::ApproxEq { lhs, rhs, .. }
449        | Op::NotEq { lhs, rhs, .. }
450        | Op::Concat { lhs, rhs, .. }
451        | Op::SeqConcat { lhs, rhs, .. }
452        | Op::Pow { lhs, rhs, .. }
453        | Op::BitXor { lhs, rhs, .. }
454        | Op::BitAnd { lhs, rhs, .. }
455        | Op::BitOr { lhs, rhs, .. }
456        | Op::Shl { lhs, rhs, .. }
457        | Op::Shr { lhs, rhs, .. }
458        | Op::UnionOp { lhs, rhs, .. }
459        | Op::IntersectOp { lhs, rhs, .. } => {
460            f(lhs);
461            f(rhs);
462        }
463        Op::DivPow2 { lhs, .. } | Op::MagicDivU { lhs, .. } => f(lhs),
464        Op::Move { src, .. }
465        | Op::Not { src, .. }
466        | Op::DeepClone { src, .. }
467        | Op::FormatValue { src, .. } => f(src),
468        Op::AddAssign { src, .. } => f(src),
469        Op::Index {
470            collection, index, ..
471        }
472        | Op::IndexUnchecked {
473            collection, index, ..
474        } => {
475            f(collection);
476            f(index);
477        }
478        Op::Length { collection, .. } => f(collection),
479        Op::Contains {
480            collection, value, ..
481        } => {
482            f(collection);
483            f(value);
484        }
485        Op::SliceOp {
486            collection,
487            start,
488            end,
489            ..
490        } => {
491            f(collection);
492            f(start);
493            f(end);
494        }
495        Op::GetField { obj, .. } => f(obj),
496        Op::NewRange { start, end, .. } => {
497            f(start);
498            f(end);
499        }
500        Op::NewEmptyListWithCapacity { capacity, .. }
501        | Op::NewEmptyMapWithCapacity { capacity, .. } => f(capacity),
502        Op::CallValue { callee, .. } => f(callee),
503        Op::CrdtMerge { source, .. } | Op::CrdtJoin { source, .. } => f(source),
504        Op::JumpIfFalse { cond, .. } | Op::JumpIfTrue { cond, .. } => f(cond),
505        Op::GlobalSet { src, .. } => f(src),
506        Op::Return { src } => f(src),
507        Op::Show { src } => f(src),
508        Op::DestructureTuple { src, .. } => f(src),
509        // NOT rewritten: range windows, in-place mutation sites, rmw dst, reversible core,
510        // speculative guards, effectful/concurrency/net operands, no-read ops.
511        //
512        // TestArm / BindArm targets are also LEFT UNTOUCHED: they are the SCRUTINEE of a pattern
513        // match, a typed anchor the flat backends' static kind-inference positionally couples (the
514        // riscv/wasm emitters key a `BindArm`'s payload type on the immediately preceding `TestArm`
515        // having the SAME target register). Rewriting one but not the other — copy-prop resets at the
516        // arm-block leader, so only the in-condition-block TestArm is rewritten while the arm-body
517        // BindArm keeps the original register — breaks that coupling and pushes the (still ≡VM)
518        // program out of the backend's enum fragment. The coalescing win is on scalar loop temps, not
519        // enum scrutinees, so excluding these costs nothing. (peephole_soundness_lock/enum_inspect +
520        // riscv_aot_lock pin it.)
521        Op::TestArm { .. }
522        | Op::BindArm { .. }
523        | Op::LoadConst { .. }
524        | Op::RevSwap { .. }
525        | Op::RevXor { .. }
526        | Op::RevNeg { .. }
527        | Op::RevAdd { .. }
528        | Op::RevSub { .. }
529        | Op::EnsureOwned { .. }
530        | Op::Call { .. }
531        | Op::CallBuiltin { .. }
532        | Op::MakeClosure { .. }
533        | Op::CheckPolicy { .. }
534        | Op::ListPushField { .. }
535        | Op::GlobalGet { .. }
536        | Op::ReturnNothing
537        | Op::NewList { .. }
538        | Op::NewEmptyList { .. }
539        | Op::NewEmptyListFixed { .. }
540        | Op::NewEmptyListI32 { .. }
541        | Op::NewEmptySet { .. }
542        | Op::NewEmptyMap { .. }
543        | Op::NewTuple { .. }
544        | Op::ListPush { .. }
545        | Op::SetAdd { .. }
546        | Op::RemoveFrom { .. }
547        | Op::SetIndex { .. }
548        | Op::SetIndexUnchecked { .. }
549        | Op::RegionBoundsGuard { .. }
550        | Op::NewStruct { .. }
551        | Op::StructInsert { .. }
552        | Op::NewInductive { .. }
553        | Op::CrdtBump { .. }
554        | Op::BigIntWide { .. }
555        | Op::NewCrdt { .. }
556        | Op::CrdtAppend { .. }
557        | Op::CrdtResolve { .. }
558        | Op::IterPrepare { .. }
559        | Op::IterNext { .. }
560        | Op::IterPop
561        | Op::ListPop { .. }
562        | Op::Sleep { .. } => {}
563        // remaining effectful / concurrency / net / temporal — operands left untouched
564        Op::LoadToday { .. }
565        | Op::LoadNow { .. }
566        | Op::Args { .. }
567        | Op::Obs { .. }
568        | Op::ChanNew { .. }
569        | Op::ChanSend { .. }
570        | Op::ChanRecv { .. }
571        | Op::ChanTrySend { .. }
572        | Op::ChanTryRecv { .. }
573        | Op::ChanClose { .. }
574        | Op::Spawn { .. }
575        | Op::SpawnHandle { .. }
576        | Op::TaskAwait { .. }
577        | Op::TaskAbort { .. }
578        | Op::SelectArmRecv { .. }
579        | Op::SelectArmTimeout { .. }
580        | Op::SelectWait { .. }
581        | Op::NetConnect { .. }
582        | Op::NetListen { .. }
583        | Op::NetSend { .. }
584        | Op::NetStream { .. }
585        | Op::NetAwait { .. }
586        | Op::NetMakePeer { .. }
587        | Op::NetSync { .. }
588        | Op::Tcp { .. }
589        | Op::Serve { .. }
590        | Op::Jump { .. }
591        | Op::Halt
592        | Op::FailWith { .. } => {}
593    }
594}
595
596// ───────────────────────── copy-propagation ─────────────────────────
597
598/// Block-local forward copy-propagation: within each basic block, track `copy[d] = s`
599/// meaning "register `d` currently holds a copy of register `s`", and rewrite each
600/// rewritable read of `d` to `s`. The map stores ROOTS (a Move's source is itself
601/// substituted before insertion), so a chain `d←c←b` resolves to `b` in one pass. Resets
602/// at every block leader; invalidates on every clobber (key and value side).
603fn copy_propagate(program: &mut CompiledProgram) {
604    let ls = leaders(program);
605    let mut copy: HashMap<Reg, Reg> = HashMap::new();
606    let mut scratch: Vec<Reg> = Vec::new();
607    for pc in 0..program.code.len() {
608        if ls.contains(&pc) {
609            copy.clear();
610        }
611        let op = &mut program.code[pc];
612        // 1. substitute rewritable reads through the current copies
613        for_each_rewritable_read(op, &mut |r| {
614            if let Some(&s) = copy.get(r) {
615                *r = s;
616            }
617        });
618        // capture the (now-substituted) Move shape before we reborrow immutably
619        let mov = if let Op::Move { dst, src } = *op {
620            Some((dst, src))
621        } else {
622            None
623        };
624        // 2. invalidate every copy the op clobbers (key or value side); a call also writes each argument register
625        //    a `mutable` parameter lends, with the parameter's final value
626        scratch.clear();
627        clobbers(&program.code[pc], &mut scratch);
628        if let Op::Call {
629            func, args_start, ..
630        } = program.code[pc]
631        {
632            if let Some(f) = program.functions.get(func as usize) {
633                scratch.extend(
634                    f.mutable_param_regs
635                        .iter()
636                        .map(|p| args_start.wrapping_add(*p)),
637                );
638            }
639        }
640        if !scratch.is_empty() {
641            copy.retain(|k, v| !scratch.contains(k) && !scratch.contains(v));
642        }
643        // 3. a real Move records a fresh copy fact (self-moves record nothing)
644        if let Some((dst, src)) = mov {
645            if dst != src {
646                copy.insert(dst, src);
647            }
648        }
649    }
650}
651
652// ───────────────────────── liveness ─────────────────────────
653
654/// Iterative backward liveness over the whole code vector. `live_out[pc]` is the set of
655/// registers live on exit from `pc`. Function bodies are disjoint CFG islands (Main ends in
656/// `Halt`, bodies in `Return`, and `Call` does not edge into a body), so per-frame registers
657/// never interfere.
658fn liveness(program: &CompiledProgram) -> Vec<HashSet<Reg>> {
659    let code = &program.code;
660    let n = code.len();
661    let entries = function_entries(program);
662    let succ: Vec<Vec<usize>> = (0..n).map(|pc| successors(pc, code, &entries)).collect();
663
664    let mut read_sets: Vec<Vec<Reg>> = Vec::with_capacity(n);
665    let mut kill_sets: Vec<Vec<Reg>> = Vec::with_capacity(n);
666    for op in code {
667        let mut r = Vec::new();
668        reads(op, program, &mut r);
669        read_sets.push(r);
670        let mut k = Vec::new();
671        kills(op, &mut k);
672        kill_sets.push(k);
673    }
674    // A function's exit reads its `mutable` parameters: the caller takes each one's final value back out of the
675    // argument register it lent (`CompiledFunction::mutable_param_regs`), so the last write to one is never dead.
676    for f in program
677        .functions
678        .iter()
679        .filter(|f| !f.mutable_param_regs.is_empty())
680    {
681        let mut seen = HashSet::new();
682        let mut stack = vec![f.entry_pc];
683        while let Some(pc) = stack.pop() {
684            if pc >= n || !seen.insert(pc) {
685                continue;
686            }
687            if matches!(code[pc], Op::Return { .. } | Op::ReturnNothing) {
688                read_sets[pc].extend(f.mutable_param_regs.iter().copied());
689            }
690            stack.extend(succ[pc].iter().copied());
691        }
692    }
693
694    let mut live_in: Vec<HashSet<Reg>> = vec![HashSet::new(); n];
695    let mut live_out: Vec<HashSet<Reg>> = vec![HashSet::new(); n];
696    let mut changed = true;
697    while changed {
698        changed = false;
699        for pc in (0..n).rev() {
700            let mut out = HashSet::new();
701            for &s in &succ[pc] {
702                for &r in &live_in[s] {
703                    out.insert(r);
704                }
705            }
706            // live_in = reads ∪ (live_out − kills)
707            let mut new_in = out.clone();
708            for k in &kill_sets[pc] {
709                new_in.remove(k);
710            }
711            for &r in &read_sets[pc] {
712                new_in.insert(r);
713            }
714            if out != live_out[pc] {
715                live_out[pc] = out;
716                changed = true;
717            }
718            if new_in != live_in[pc] {
719                live_in[pc] = new_in;
720                changed = true;
721            }
722        }
723    }
724    live_out
725}
726
727// ───────────────────────── dead-move elimination ─────────────────────────
728
729/// The indices of `Move` ops that are removable: a self-copy (`dst == src`, a no-op), or a
730/// move whose destination is not live on exit (a dead assignment). Only `Move` — total and
731/// side-effect free — is ever a candidate.
732fn dead_moves(program: &CompiledProgram, live_out: &[HashSet<Reg>]) -> Vec<usize> {
733    let mut dead = Vec::new();
734    for (pc, op) in program.code.iter().enumerate() {
735        if let Op::Move { dst, src } = op {
736            if dst == src || !live_out[pc].contains(dst) {
737                dead.push(pc);
738            }
739        }
740    }
741    dead
742}
743
744/// Delete the ops at `dead` (sorted, unique) and renumber every absolute code position that
745/// refers to a pc: branch/jump targets, iterator exits, function entry points, and the
746/// pc-keyed `loop_locals` map. A target that pointed at a deleted op moves to the next kept op.
747fn remove_ops(program: &mut CompiledProgram, dead: &[usize]) {
748    if dead.is_empty() {
749        return;
750    }
751    let dead_set: HashSet<usize> = dead.iter().copied().collect();
752    let n = program.code.len();
753    // new_pc[old] = number of kept ops strictly before `old` = new index of the next kept op
754    let mut new_pc = vec![0usize; n + 1];
755    let mut kept = 0usize;
756    for old in 0..n {
757        new_pc[old] = kept;
758        if !dead_set.contains(&old) {
759            kept += 1;
760        }
761    }
762    new_pc[n] = kept;
763
764    // rebuild the code vector, remapping the surviving branch/exit targets
765    let mut code: Vec<Op> = Vec::with_capacity(kept);
766    for (old, mut op) in program.code.drain(..).enumerate() {
767        if dead_set.contains(&old) {
768            continue;
769        }
770        match &mut op {
771            Op::Jump { target }
772            | Op::JumpIfFalse { target, .. }
773            | Op::JumpIfTrue { target, .. } => {
774                *target = new_pc[*target];
775            }
776            Op::IterNext { exit, .. } => {
777                *exit = new_pc[*exit];
778            }
779            _ => {}
780        }
781        code.push(op);
782    }
783    program.code = code;
784
785    for f in &mut program.functions {
786        f.entry_pc = new_pc[f.entry_pc];
787    }
788    if !program.loop_locals.is_empty() {
789        program.loop_locals = program
790            .loop_locals
791            .drain()
792            .map(|(pc, v)| (new_pc[pc], v))
793            .collect();
794    }
795    // A site mark moves to the next surviving op, so the range it opens starts where it did.
796    for (pc, _) in &mut program.site_at {
797        *pc = new_pc[*pc as usize] as u32;
798    }
799    // A declaration names the op that DEFINES its value; one whose op is gone names nothing.
800    program.declared_types = std::mem::take(&mut program.declared_types)
801        .into_iter()
802        .filter(|(pc, _)| !dead_set.contains(&(*pc as usize)))
803        .map(|(pc, bt)| (new_pc[pc as usize] as u32, bt))
804        .collect();
805}
806
807#[cfg(test)]
808#[path = "../../../logicaffeine_tests/unit/logicaffeine_compile/vm/peephole/tests.rs"]
809mod tests;
logicaffeine_compile/vm/peephole.rs

logicaffeine_compile/vm/
peephole.rs
