logicaffeine_compile/codegen_sva/
scalar_asm.rs

1//! scalar_asm — assemble a compiled LOGOS program (the register bytecode `CompiledProgram`) into the
2//! instruction words that `soft_core_scalar.v` executes, so a REAL `.lg` program can be streamed to the
3//! Nexys A7 FPGA over UART and run on silicon (see scripts/run-on-nexys-scalar.sh).
4//!
5//! Scope: the FUNCTION-FREE scalar subset the routable core implements — the reversible/adiabatic core
6//! (opcodes 0..4), LoadConst/Move, every arithmetic / bitwise / comparison op (through the proven
7//! `alu.v`), the branches, and Show/Halt/FailWith. A strict WHITELIST rejects everything else (user
8//! functions — their register-window calling convention needs a translation pass — globals, collections,
9//! heap, structs, CRDTs, concurrency), so whatever this encoder accepts is guaranteed to run identically
10//! on `run_soft_core` (the Rust model), on the RTL, and on the chip. The op BYTE is always
11//! `binisa::opcode(op)` — the append-only ISA ABI a hardware decoder keys on — so the encoder can never
12//! silently drift from the silicon; it only lays out the operand fields per the decoder's field usage.
13//!
14//! Word layout (matches `run_soft_core` / `soft_core_scalar.v`):
15//!
16//! ```text
17//! general : [opcode:8][dst:8][a:8][b:8]     (dst=bits23:16, a=bits15:8, b=bits7:0)
18//! LoadConst: [opcode:8][dst:8][imm:16]       (imm sign-extends the low 16 bits)
19//! Jump    : [opcode:8][target:8][........]   (target = bits23:16, a 0..255 word index)
20//! JumpIf* : [opcode:8][target:8][cond:8][..] (target=bits23:16, cond=bits15:8)
21//! Show    : [opcode:8][0][src:8][0]          (src=bits15:8)
22//! ```
23//!
24//! Locked ≡ VM by `rtl.rs::tests::encode_scalar_matches_vm`.
25
26use crate::vm::binisa::opcode;
27use crate::vm::{CompiledProgram, Constant, Op, Reg};
28
29/// A register index must fit the 16-entry file (r0..r15).
30fn reg(r: Reg) -> Result<u32, String> {
31    if r > 15 {
32        return Err(format!(
33            "register r{r} exceeds the scalar core's 16-register file"
34        ));
35    }
36    Ok(r as u32)
37}
38
39/// Encode one `Op` into its soft_core_scalar word, given the program's constant pool. Returns `Err` for
40/// any op outside the chip's function-free scalar subset (the caller then knows the program isn't
41/// chip-runnable as-is).
42fn encode_op(op: &Op, constants: &[Constant]) -> Result<u32, String> {
43    let oc = opcode(op) as u32;
44    // [op][dst][a][b]
45    let w = |dst: u32, a: u32, b: u32| (oc << 24) | (dst << 16) | (a << 8) | b;
46    Ok(match op {
47        // reversible / adiabatic core
48        Op::RevAdd { place, delta } | Op::RevSub { place, delta } | Op::RevXor { place, delta } => {
49            w(reg(*place)?, reg(*delta)?, 0)
50        }
51        Op::RevNeg { place } => w(reg(*place)?, 0, 0),
52        Op::RevSwap { a, b } => w(reg(*a)?, reg(*b)?, 0),
53        // data movement
54        Op::Move { dst, src } => w(reg(*dst)?, reg(*src)?, 0),
55        Op::LoadConst { dst, idx } => {
56            let val = match constants.get(*idx as usize) {
57                Some(Constant::Int(v)) => *v,
58                Some(Constant::Bool(b)) => *b as i64,
59                Some(other) => {
60                    return Err(format!("LoadConst of a non-integer constant ({other:?}) is not chip-runnable"))
61                }
62                None => return Err(format!("LoadConst references missing constant #{idx}")),
63            };
64            // The scalar core's LoadConst SIGN-extends its 16-bit immediate, so the representable set is the
65            // signed-16-bit range. A value in [32768, 65535] (or beyond) needs a wider load the scalar core does
66            // not have — reject it (an honest boundary) rather than silently truncate its high bits.
67            if !(-32768..=32767).contains(&val) {
68                return Err(format!("constant {val} exceeds the signed 16-bit LoadConst immediate range [-32768, 32767]"));
69            }
70            (oc << 24) | (reg(*dst)? << 16) | (((val as i32) as u32) & 0xffff)
71        }
72        // Division / modulo / power are NOT in the scalar core's combinational alu.v — the full core issues
73        // them to a SEQUENTIAL shared divider the scalar core omits (they would read as 0 on silicon). Reject
74        // with an honest reason instead of emitting a word that silently computes the wrong answer.
75        Op::Div { .. }
76        | Op::Mod { .. }
77        | Op::ExactDiv { .. }
78        | Op::FloorDiv { .. }
79        | Op::DivPow2 { .. }
80        | Op::MagicDivU { .. }
81        | Op::Pow { .. } => {
82            return Err(format!(
83                "`{}` needs the sequential divider the scalar core omits — only the combinational alu.v ops \
84                 (add/sub/mul, bitwise, shifts, comparisons) run on the chip",
85                op.name()
86            ))
87        }
88        // arithmetic / bitwise / comparison — every one goes through the proven alu.v (dst, lhs->a, rhs->b)
89        Op::Add { dst, lhs, rhs }
90        | Op::Sub { dst, lhs, rhs }
91        | Op::Mul { dst, lhs, rhs }
92        | Op::Lt { dst, lhs, rhs }
93        | Op::Gt { dst, lhs, rhs }
94        | Op::LtEq { dst, lhs, rhs }
95        | Op::GtEq { dst, lhs, rhs }
96        | Op::Eq { dst, lhs, rhs }
97        | Op::NotEq { dst, lhs, rhs }
98        | Op::BitXor { dst, lhs, rhs }
99        | Op::BitAnd { dst, lhs, rhs }
100        | Op::BitOr { dst, lhs, rhs }
101        | Op::Shl { dst, lhs, rhs }
102        | Op::Shr { dst, lhs, rhs } => w(reg(*dst)?, reg(*lhs)?, reg(*rhs)?),
103        Op::Not { dst, src } => w(reg(*dst)?, reg(*src)?, 0),
104        // `Set x to x + y` compiles to AddAssign (dst = dst + src) — an in-place-Text optimization that is
105        // plain integer addition for scalars. Lower it to the proven `Add` datapath (dst, lhs=dst, rhs=src)
106        // so it uses exactly the path sum_loop already validated on silicon.
107        Op::AddAssign { dst, src } => {
108            let add = crate::vm::binisa::opcode_of_name("Add").expect("Add is a registered opcode") as u32;
109            (add << 24) | (reg(*dst)? << 16) | (reg(*dst)? << 8) | reg(*src)?
110        }
111        // control flow — the target is an absolute instruction index; for a function-free program that
112        // index is the imem word index (the code array maps 1:1), so it lowers directly.
113        Op::Jump { target } => {
114            if *target > 255 {
115                return Err(format!("jump target {target} exceeds the 256-word imem"));
116            }
117            (oc << 24) | ((*target as u32) << 16)
118        }
119        Op::JumpIfFalse { cond, target } | Op::JumpIfTrue { cond, target } => {
120            if *target > 255 {
121                return Err(format!("jump target {target} exceeds the 256-word imem"));
122            }
123            (oc << 24) | ((*target as u32) << 16) | (reg(*cond)? << 8)
124        }
125        // runtime
126        Op::Show { src } => w(0, reg(*src)?, 0),
127        Op::Halt | Op::FailWith { .. } => oc << 24,
128        // everything else (functions, globals, collections, heap, structs, CRDTs, concurrency, closures)
129        // is outside the routable scalar core — reject so the encoder's output is always chip-faithful.
130        other => return Err(format!("`{}` is outside the function-free scalar chip subset", other.name())),
131    })
132}
133
134/// The registers a scalar-subset op reads and writes — `(reads, writes)` — or `None` outside the subset.
135/// The arms are exactly `encode_op`'s accepted ops.
136fn scalar_io(op: &Op) -> Option<(Vec<Reg>, Vec<Reg>)> {
137    Some(match *op {
138        Op::RevAdd { place, delta } | Op::RevSub { place, delta } | Op::RevXor { place, delta } => {
139            (vec![place, delta], vec![place])
140        }
141        Op::RevNeg { place } => (vec![place], vec![place]),
142        Op::RevSwap { a, b } => (vec![a, b], vec![a, b]),
143        Op::Move { dst, src } | Op::Not { dst, src } => (vec![src], vec![dst]),
144        Op::LoadConst { dst, .. } => (vec![], vec![dst]),
145        Op::Add { dst, lhs, rhs }
146        | Op::Sub { dst, lhs, rhs }
147        | Op::Mul { dst, lhs, rhs }
148        | Op::Lt { dst, lhs, rhs }
149        | Op::Gt { dst, lhs, rhs }
150        | Op::LtEq { dst, lhs, rhs }
151        | Op::GtEq { dst, lhs, rhs }
152        | Op::Eq { dst, lhs, rhs }
153        | Op::NotEq { dst, lhs, rhs }
154        | Op::BitXor { dst, lhs, rhs }
155        | Op::BitAnd { dst, lhs, rhs }
156        | Op::BitOr { dst, lhs, rhs }
157        | Op::Shl { dst, lhs, rhs }
158        | Op::Shr { dst, lhs, rhs } => (vec![lhs, rhs], vec![dst]),
159        Op::AddAssign { dst, src } => (vec![dst, src], vec![dst]),
160        Op::JumpIfFalse { cond, .. } | Op::JumpIfTrue { cond, .. } => (vec![cond], vec![]),
161        Op::Show { src } => (vec![src], vec![]),
162        Op::Jump { .. } | Op::Halt | Op::FailWith { .. } => (vec![], vec![]),
163        _ => return None,
164    })
165}
166
167/// `op` with every register `r` it names replaced by `to(r)`. Only called on scalar-subset ops.
168fn rename(op: &Op, to: &dyn Fn(Reg) -> Reg) -> Op {
169    match *op {
170        Op::RevAdd { place, delta } => Op::RevAdd {
171            place: to(place),
172            delta: to(delta),
173        },
174        Op::RevSub { place, delta } => Op::RevSub {
175            place: to(place),
176            delta: to(delta),
177        },
178        Op::RevXor { place, delta } => Op::RevXor {
179            place: to(place),
180            delta: to(delta),
181        },
182        Op::RevNeg { place } => Op::RevNeg { place: to(place) },
183        Op::RevSwap { a, b } => Op::RevSwap { a: to(a), b: to(b) },
184        Op::Move { dst, src } => Op::Move {
185            dst: to(dst),
186            src: to(src),
187        },
188        Op::Not { dst, src } => Op::Not {
189            dst: to(dst),
190            src: to(src),
191        },
192        Op::LoadConst { dst, idx } => Op::LoadConst { dst: to(dst), idx },
193        Op::Add { dst, lhs, rhs } => Op::Add {
194            dst: to(dst),
195            lhs: to(lhs),
196            rhs: to(rhs),
197        },
198        Op::Sub { dst, lhs, rhs } => Op::Sub {
199            dst: to(dst),
200            lhs: to(lhs),
201            rhs: to(rhs),
202        },
203        Op::Mul { dst, lhs, rhs } => Op::Mul {
204            dst: to(dst),
205            lhs: to(lhs),
206            rhs: to(rhs),
207        },
208        Op::Lt { dst, lhs, rhs } => Op::Lt {
209            dst: to(dst),
210            lhs: to(lhs),
211            rhs: to(rhs),
212        },
213        Op::Gt { dst, lhs, rhs } => Op::Gt {
214            dst: to(dst),
215            lhs: to(lhs),
216            rhs: to(rhs),
217        },
218        Op::LtEq { dst, lhs, rhs } => Op::LtEq {
219            dst: to(dst),
220            lhs: to(lhs),
221            rhs: to(rhs),
222        },
223        Op::GtEq { dst, lhs, rhs } => Op::GtEq {
224            dst: to(dst),
225            lhs: to(lhs),
226            rhs: to(rhs),
227        },
228        Op::Eq { dst, lhs, rhs } => Op::Eq {
229            dst: to(dst),
230            lhs: to(lhs),
231            rhs: to(rhs),
232        },
233        Op::NotEq { dst, lhs, rhs } => Op::NotEq {
234            dst: to(dst),
235            lhs: to(lhs),
236            rhs: to(rhs),
237        },
238        Op::BitXor { dst, lhs, rhs } => Op::BitXor {
239            dst: to(dst),
240            lhs: to(lhs),
241            rhs: to(rhs),
242        },
243        Op::BitAnd { dst, lhs, rhs } => Op::BitAnd {
244            dst: to(dst),
245            lhs: to(lhs),
246            rhs: to(rhs),
247        },
248        Op::BitOr { dst, lhs, rhs } => Op::BitOr {
249            dst: to(dst),
250            lhs: to(lhs),
251            rhs: to(rhs),
252        },
253        Op::Shl { dst, lhs, rhs } => Op::Shl {
254            dst: to(dst),
255            lhs: to(lhs),
256            rhs: to(rhs),
257        },
258        Op::Shr { dst, lhs, rhs } => Op::Shr {
259            dst: to(dst),
260            lhs: to(lhs),
261            rhs: to(rhs),
262        },
263        Op::AddAssign { dst, src } => Op::AddAssign {
264            dst: to(dst),
265            src: to(src),
266        },
267        Op::JumpIfFalse { cond, target } => Op::JumpIfFalse {
268            cond: to(cond),
269            target,
270        },
271        Op::JumpIfTrue { cond, target } => Op::JumpIfTrue {
272            cond: to(cond),
273            target,
274        },
275        Op::Show { src } => Op::Show { src: to(src) },
276        other => other,
277    }
278}
279
280/// The scalar core's register file.
281const SCALAR_REGISTERS: usize = 16;
282
283/// Map a function-free scalar program's registers onto the core's sixteen by liveness. The VM numbers
284/// registers freely (a fresh one per `Let`, named values above the temporaries that computed them); the
285/// chip needs only as many as are ever live at once. Two registers may share a physical one unless one
286/// is live where the other is written (a `Move`'s source does not count against its destination), and
287/// the interference graph is coloured Chaitin–Briggs style — simplify below sixteen neighbours, else
288/// optimistically, then colour in reverse — lowest register first, so the result is deterministic.
289///
290/// A program already within sixteen registers is returned unchanged, so an image that fits keeps its
291/// encoding exactly. `Err` names the instruction where more than sixteen values are live at once; a
292/// program with an op outside the scalar subset is also returned unchanged, for the encoder to refuse
293/// with that op's own reason.
294pub fn allocate_scalar_registers(code: &[Op]) -> Result<Vec<Op>, String> {
295    let io: Option<Vec<(Vec<Reg>, Vec<Reg>)>> = code.iter().map(scalar_io).collect();
296    let Some(io) = io else {
297        return Ok(code.to_vec());
298    };
299    let used: std::collections::BTreeSet<Reg> = io
300        .iter()
301        .flat_map(|(r, w)| r.iter().chain(w))
302        .copied()
303        .collect();
304    if used.iter().all(|&r| (r as usize) < SCALAR_REGISTERS) {
305        return Ok(code.to_vec());
306    }
307    let n = code.len();
308    let successors = |i: usize| -> Vec<usize> {
309        match code[i] {
310            Op::Jump { target } => vec![target],
311            Op::JumpIfFalse { target, .. } | Op::JumpIfTrue { target, .. } => vec![target, i + 1],
312            Op::Halt | Op::FailWith { .. } => vec![],
313            _ => vec![i + 1],
314        }
315        .into_iter()
316        .filter(|&s| s < n)
317        .collect()
318    };
319    use std::collections::{BTreeMap, BTreeSet};
320    let mut live_in: Vec<BTreeSet<Reg>> = vec![BTreeSet::new(); n];
321    let mut live_out: Vec<BTreeSet<Reg>> = vec![BTreeSet::new(); n];
322    loop {
323        let mut changed = false;
324        for i in (0..n).rev() {
325            let out: BTreeSet<Reg> = successors(i)
326                .into_iter()
327                .flat_map(|s| live_in[s].iter().copied())
328                .collect();
329            let (reads, writes) = &io[i];
330            let mut inn: BTreeSet<Reg> = out
331                .iter()
332                .copied()
333                .filter(|r| !writes.contains(r))
334                .collect();
335            inn.extend(reads.iter().copied());
336            if out != live_out[i] || inn != live_in[i] {
337                live_out[i] = out;
338                live_in[i] = inn;
339                changed = true;
340            }
341        }
342        if !changed {
343            break;
344        }
345    }
346    let mut adj: BTreeMap<Reg, BTreeSet<Reg>> =
347        used.iter().map(|&r| (r, BTreeSet::new())).collect();
348    let mut edge = |a: Reg, b: Reg| {
349        if a != b {
350            adj.get_mut(&a).unwrap().insert(b);
351            adj.get_mut(&b).unwrap().insert(a);
352        }
353    };
354    for i in 0..n {
355        let (_, writes) = &io[i];
356        let moved_from = match code[i] {
357            Op::Move { src, .. } => Some(src),
358            _ => None,
359        };
360        for &w in writes {
361            for &l in &live_out[i] {
362                if Some(l) != moved_from {
363                    edge(w, l);
364                }
365            }
366            for &w2 in writes {
367                edge(w, w2);
368            }
369        }
370    }
371    for a in live_in[0].iter().copied().collect::<Vec<_>>() {
372        for b in live_in[0].iter().copied() {
373            edge(a, b);
374        }
375    }
376    let crowded = || {
377        (0..n)
378            .map(|i| {
379                (
380                    live_out[i]
381                        .iter()
382                        .chain(&io[i].1)
383                        .collect::<BTreeSet<_>>()
384                        .len(),
385                    i,
386                )
387            })
388            .max()
389            .unwrap_or((0, 0))
390    };
391    let mut remaining: BTreeSet<Reg> = used.clone();
392    let mut stack = Vec::with_capacity(used.len());
393    while !remaining.is_empty() {
394        let degree = |r: Reg| adj[&r].iter().filter(|x| remaining.contains(x)).count();
395        let pick = remaining
396            .iter()
397            .copied()
398            .find(|&r| degree(r) < SCALAR_REGISTERS)
399            .unwrap_or_else(|| {
400                remaining
401                    .iter()
402                    .copied()
403                    .max_by_key(|&r| (degree(r), std::cmp::Reverse(r)))
404                    .unwrap()
405            });
406        remaining.remove(&pick);
407        stack.push(pick);
408    }
409    let mut color: BTreeMap<Reg, Reg> = BTreeMap::new();
410    while let Some(r) = stack.pop() {
411        let taken: BTreeSet<Reg> = adj[&r]
412            .iter()
413            .filter_map(|x| color.get(x).copied())
414            .collect();
415        let Some(c) = (0..SCALAR_REGISTERS as Reg).find(|c| !taken.contains(c)) else {
416            let (live, at) = crowded();
417            return Err(format!(
418                "{live} values are live at once at instruction {at}, more than the scalar core's \
419                 {SCALAR_REGISTERS} registers"
420            ));
421        };
422        color.insert(r, c);
423    }
424    Ok(code.iter().map(|op| rename(op, &|r| color[&r])).collect())
425}
426
427/// Assemble a whole compiled program into soft_core_scalar imem words. Function-free only (a program with
428/// user functions returns `Err`; their calling-convention translation is a separate pass). At most 256
429/// words (the imem depth). Registers are first mapped onto the core's sixteen by liveness
430/// ([`allocate_scalar_registers`]).
431pub fn encode_soft_core_scalar(program: &CompiledProgram) -> Result<Vec<u32>, String> {
432    if !program.functions.is_empty() {
433        return Err("program defines user functions — the scalar encoder is function-free (calling-convention translation not yet implemented)".into());
434    }
435    if program.code.len() > 256 {
436        return Err(format!(
437            "{} instructions exceed the 256-word scalar imem",
438            program.code.len()
439        ));
440    }
441    allocate_scalar_registers(&program.code)?
442        .iter()
443        .enumerate()
444        .map(|(i, op)| {
445            encode_op(op, &program.constants).map_err(|e| format!("instruction {i}: {e}"))
446        })
447        .collect()
448}
449
450/// Render imem words as a `.hex` file body (one 8-hex-digit word per line) for scripts/nexys-host.py.
451pub fn to_hex(words: &[u32]) -> String {
452    let mut s = String::with_capacity(words.len() * 9);
453    for w in words {
454        s.push_str(&format!("{w:08x}\n"));
455    }
456    s
457}
458
459/// Compile a `.lg` source string all the way to soft_core_scalar imem words, through the SAME front-end
460/// and oracle-driven compiler the VM uses (so the chip runs byte-identically to `vm_outcome`). `Err` if it
461/// doesn't parse/compile, or uses anything outside the function-free scalar subset.
462pub fn compile_to_scalar_words(source: &str) -> Result<Vec<u32>, String> {
463    crate::ui_bridge::with_parsed_program(source, |parsed, interner| {
464        let (stmts, types, _policies) = parsed.map_err(|advice| format!("{advice}"))?;
465        let oracle = crate::optimize::oracle_analyze_with(stmts, interner);
466        let program =
467            crate::vm::Compiler::compile_with_oracle(stmts, interner, Some(types), Some(oracle))?;
468        encode_soft_core_scalar(&program)
469    })
470}
logicaffeine_compile/codegen_sva/scalar_asm.rs

logicaffeine_compile/codegen_sva/
scalar_asm.rs
