use std::collections::BTreeMap;
mod mir {
use serde::Deserialize;
#[derive(Deserialize, Debug)]
pub struct Crate {
pub name: String,
pub functions: Vec<Function>,
}
#[derive(Deserialize, Debug)]
pub struct Function {
pub name: String,
pub params: Vec<Local>,
pub return_ty: String,
pub locals: Vec<Local>,
pub blocks: Vec<Block>,
}
#[derive(Deserialize, Debug)]
pub struct Local {
pub index: u32,
pub name: Option<String>,
pub ty: String,
}
#[derive(Deserialize, Debug)]
pub struct Block {
pub index: u32,
pub statements: Vec<Statement>,
pub terminator: Terminator,
}
#[derive(Deserialize, Debug)]
#[serde(untagged)]
pub enum Statement {
Assign { Assign: AssignData },
}
#[derive(Deserialize, Debug)]
pub struct AssignData {
pub place: Place,
pub rvalue: Rvalue,
}
#[derive(Deserialize, Debug)]
#[serde(untagged)]
pub enum Place {
Local { Local: u32 },
}
#[derive(Deserialize, Debug)]
#[serde(untagged)]
pub enum Rvalue {
BinaryOp { BinaryOp: (String, Operand, Operand) },
Use { Use: Operand },
UnaryOp { UnaryOp: (String, Operand) },
}
#[derive(Deserialize, Debug)]
#[serde(untagged)]
pub enum Operand {
Copy { Copy: Place },
Move { Move: Place },
Constant { Constant: ConstVal },
}
#[derive(Deserialize, Debug)]
#[serde(untagged)]
pub enum ConstVal {
Scalar { Scalar: u64 },
Bool { Bool: bool },
}
#[derive(Deserialize, Debug)]
#[serde(untagged)]
pub enum Terminator {
Return(String), Goto { Goto: GotoData },
SwitchInt { SwitchInt: SwitchData },
Call { Call: CallData },
}
#[derive(Deserialize, Debug)]
pub struct GotoData {
pub target: u32,
}
#[derive(Deserialize, Debug)]
pub struct SwitchData {
pub discriminant: Operand,
pub targets: Vec<(u64, u32)>,
pub otherwise: u32,
}
#[derive(Deserialize, Debug)]
pub struct CallData {
pub func: String,
pub args: Vec<Operand>,
pub destination: Place,
pub target: u32,
}
}
fn nox_atom(v: u64) -> String { format!("{}", v) }
fn nox_cell(a: &str, b: &str) -> String { format!("[{} {}]", a, b) }
fn nox_formula(tag: u64, body: &str) -> String { nox_cell(&nox_atom(tag), body) }
fn nox_axis(addr: u64) -> String { nox_formula(0, &nox_atom(addr)) }
fn nox_quote(val: &str) -> String { nox_formula(1, val) }
fn nox_compose(subj: &str, code: &str) -> String { nox_formula(2, &nox_cell(subj, code)) }
fn nox_cons(a: &str, b: &str) -> String { nox_formula(3, &nox_cell(a, b)) }
fn nox_branch(test: &str, yes: &str, no: &str) -> String {
nox_formula(4, &nox_cell(test, &nox_cell(yes, no)))
}
fn nox_binop(tag: u64, a: &str, b: &str) -> String { nox_formula(tag, &nox_cell(a, b)) }
pub fn compile_function(func: &mir::Function) -> Result<String, String> {
let loops = detect_loops(func);
let mut ctx = CompileCtx::new(func, &loops);
let formula = ctx.compile_block(0)?;
Ok(formula)
}
struct LoopInfo {
header: u32,
carried_locals: Vec<u32>,
exit_block: u32,
body_entry: u32,
}
fn detect_loops(func: &mir::Function) -> Vec<LoopInfo> {
let mut loops = Vec::new();
let mut visited = std::collections::BTreeSet::new();
let mut stack = Vec::new();
fn successors(block: &mir::Block) -> Vec<u32> {
match &block.terminator {
mir::Terminator::Return(_) => vec![],
mir::Terminator::Goto { Goto: d } => vec![d.target],
mir::Terminator::SwitchInt { SwitchInt: d } => {
let mut s: Vec<u32> = d.targets.iter().map(|t| t.1).collect();
s.push(d.otherwise);
s
}
mir::Terminator::Call { Call: d } => vec![d.target],
}
}
fn dfs(func: &mir::Function, block_idx: u32, visited: &mut std::collections::BTreeSet<u32>,
stack: &mut Vec<u32>, loops: &mut Vec<LoopInfo>) {
visited.insert(block_idx);
stack.push(block_idx);
if let Some(block) = func.blocks.iter().find(|b| b.index == block_idx) {
for succ in successors(block) {
if stack.contains(&succ) {
let header_pos = stack.iter().position(|&b| b == succ).unwrap();
let body_blocks: Vec<u32> = stack[header_pos..].to_vec();
let mut carried = std::collections::BTreeSet::new();
for &bb_idx in &body_blocks {
if let Some(bb) = func.blocks.iter().find(|b| b.index == bb_idx) {
for stmt in &bb.statements {
let mir::Statement::Assign { Assign: data } = stmt;
let mir::Place::Local { Local: l } = data.place;
carried.insert(l);
}
if let mir::Terminator::Call { Call: d } = &bb.terminator {
let mir::Place::Local { Local: l } = d.destination;
carried.insert(l);
}
}
}
let header = func.blocks.iter().find(|b| b.index == succ).unwrap();
let (exit_block, body_entry) = match &header.terminator {
mir::Terminator::SwitchInt { SwitchInt: d } if d.targets.len() == 1 => {
(d.targets[0].1, d.otherwise)
}
_ => continue, };
let param_locals: std::collections::BTreeSet<u32> =
func.params.iter().map(|p| p.index).collect();
let carried_locals: Vec<u32> = carried.into_iter()
.filter(|l| *l != 0 && !param_locals.contains(l))
.collect();
loops.push(LoopInfo { header: succ, carried_locals, exit_block, body_entry });
} else if !visited.contains(&succ) {
dfs(func, succ, visited, stack, loops);
}
}
}
stack.pop();
}
dfs(func, 0, &mut visited, &mut stack, &mut loops);
loops
}
struct CompileCtx<'a> {
func: &'a mir::Function,
local_depth: BTreeMap<u32, u32>,
depth: u32,
num_params: u32,
loops: &'a [LoopInfo],
in_loop_body: Option<u32>, }
impl<'a> CompileCtx<'a> {
fn new(func: &'a mir::Function, loops: &'a [LoopInfo]) -> Self {
let mut local_depth = BTreeMap::new();
let num_params = func.params.len() as u32;
for (i, param) in func.params.iter().enumerate() {
local_depth.insert(param.index, num_params - 1 - i as u32);
}
Self { func, local_depth, depth: num_params, num_params, loops, in_loop_body: None }
}
fn push_binding(&mut self, local: u32) -> (BTreeMap<u32, u32>, u32) {
let saved = (self.local_depth.clone(), self.depth);
for depth in self.local_depth.values_mut() { *depth += 1; }
self.local_depth.insert(local, 0);
self.depth += 1;
saved
}
fn pop_binding(&mut self, saved: (BTreeMap<u32, u32>, u32)) {
self.local_depth = saved.0;
self.depth = saved.1;
}
fn depth_to_axis(depth: u32) -> u64 {
let mut axis: u64 = 1;
for _ in 0..=depth {
axis = axis * 2; }
(1u64 << (depth + 2)) - 2
}
fn local_axis(&self, local_idx: u32) -> Result<String, String> {
if let Some(&depth) = self.local_depth.get(&local_idx) {
Ok(nox_axis(Self::depth_to_axis(depth)))
} else {
Err(format!("local {} not in scope", local_idx))
}
}
fn compile_operand(&self, op: &mir::Operand) -> Result<String, String> {
match op {
mir::Operand::Copy { Copy: mir::Place::Local { Local: idx } }
| mir::Operand::Move { Move: mir::Place::Local { Local: idx } } => {
self.local_axis(*idx)
}
mir::Operand::Constant { Constant: mir::ConstVal::Scalar { Scalar: v } } => {
Ok(nox_quote(&nox_atom(*v)))
}
mir::Operand::Constant { Constant: mir::ConstVal::Bool { Bool: v } } => {
Ok(nox_quote(&nox_atom(if *v { 0 } else { 1 }))) }
}
}
fn compile_rvalue(&self, rv: &mir::Rvalue) -> Result<String, String> {
match rv {
mir::Rvalue::BinaryOp { BinaryOp: (op, a, b) } => {
let left = self.compile_operand(a)?;
let right = self.compile_operand(b)?;
let tag = match op.as_str() {
"Add" => 5,
"Sub" => 6,
"Mul" => 7,
"Eq" => {
let eq = nox_binop(9, &left, &right);
return Ok(nox_branch(&eq, &nox_quote("1"), &nox_quote("0")));
}
"Ne" => {
return Ok(nox_binop(9, &left, &right));
}
"Lt" => {
let lt = nox_binop(10, &left, &right);
return Ok(nox_branch(<, &nox_quote("1"), &nox_quote("0")));
}
"Le" => {
return Ok(nox_binop(10, &right, &left));
}
"Gt" => {
let lt = nox_binop(10, &right, &left);
return Ok(nox_branch(<, &nox_quote("1"), &nox_quote("0")));
}
"Ge" => {
return Ok(nox_binop(10, &left, &right));
}
"BitAnd" => 12,
"BitXor" => 11,
"Shl" => 14,
other => return Err(format!("unsupported binop: {}", other)),
};
Ok(nox_binop(tag, &left, &right))
}
mir::Rvalue::Use { Use: op } => self.compile_operand(op),
mir::Rvalue::UnaryOp { UnaryOp: (op, val) } => {
let v = self.compile_operand(val)?;
match op.as_str() {
"Not" => Ok(nox_formula(13, &v)),
"Neg" => Ok(nox_binop(6, &nox_quote("0"), &v)), other => Err(format!("unsupported unary: {}", other)),
}
}
}
}
fn compile_call(&self, call: &mir::CallData) -> Result<String, String> {
let fname = &call.func;
if fname.contains("wrapping_add") || fname.contains("unchecked_add") {
let a = self.compile_operand(&call.args[0])?;
let b = self.compile_operand(&call.args[1])?;
return Ok(nox_binop(5, &a, &b));
}
if fname.contains("wrapping_sub") || fname.contains("unchecked_sub") {
let a = self.compile_operand(&call.args[0])?;
let b = self.compile_operand(&call.args[1])?;
return Ok(nox_binop(6, &a, &b));
}
if fname.contains("wrapping_mul") || fname.contains("unchecked_mul") {
let a = self.compile_operand(&call.args[0])?;
let b = self.compile_operand(&call.args[1])?;
return Ok(nox_binop(7, &a, &b));
}
Err(format!("unsupported call: {}", fname))
}
fn compile_block(&mut self, block_idx: u32) -> Result<String, String> {
if let Some(loop_info) = self.loops.iter().find(|l| l.header == block_idx) {
if self.in_loop_body.is_some() {
return self.emit_back_edge(loop_info);
}
return self.emit_loop(loop_info);
}
let block = self.func.blocks.iter()
.find(|b| b.index == block_idx)
.ok_or_else(|| format!("block {} not found", block_idx))?;
if let mir::Terminator::Goto { Goto: goto } = &block.terminator {
if let Some(loop_info) = self.loops.iter().find(|l| l.header == goto.target) {
if self.in_loop_body.is_none() {
let mut inits = BTreeMap::new();
for stmt in &block.statements {
let mir::Statement::Assign { Assign: data } = stmt;
let mir::Place::Local { Local: dest } = data.place;
if let Ok(val) = self.compile_rvalue(&data.rvalue) {
inits.insert(dest, val);
}
}
return self.emit_loop_with_inits(loop_info, &inits);
}
}
}
self.compile_terminator(&block.terminator, &block.statements, 0)
}
fn emit_loop(&mut self, info: &LoopInfo) -> Result<String, String> {
let saved_map = self.local_depth.clone();
let saved_depth = self.depth;
let num_carried = info.carried_locals.len() as u32;
let loop_depth = 1 + num_carried + self.num_params;
self.depth = loop_depth;
for (i, &local) in info.carried_locals.iter().rev().enumerate() {
self.local_depth.insert(local, 1 + i as u32);
}
let shift = 1 + num_carried;
for (i, param) in self.func.params.iter().enumerate() {
self.local_depth.insert(param.index, shift + (self.num_params - 1 - i as u32));
}
self.in_loop_body = Some(info.header);
let header = self.func.blocks.iter().find(|b| b.index == info.header).unwrap();
let loop_formula = self.compile_terminator(&header.terminator, &header.statements, 0)?;
self.in_loop_body = None;
self.local_depth = saved_map;
self.depth = saved_depth;
self.emit_loop_init(info, &loop_formula, &BTreeMap::new())
}
fn emit_loop_with_inits(&mut self, info: &LoopInfo, inits: &BTreeMap<u32, String>) -> Result<String, String> {
let saved_map = self.local_depth.clone();
let saved_depth = self.depth;
let num_carried = info.carried_locals.len() as u32;
let loop_depth = 1 + num_carried + self.num_params;
self.depth = loop_depth;
for (i, &local) in info.carried_locals.iter().rev().enumerate() {
self.local_depth.insert(local, 1 + i as u32);
}
let shift = 1 + num_carried;
for (i, param) in self.func.params.iter().enumerate() {
self.local_depth.insert(param.index, shift + (self.num_params - 1 - i as u32));
}
self.in_loop_body = Some(info.header);
let header = self.func.blocks.iter().find(|b| b.index == info.header).unwrap();
let loop_formula = self.compile_terminator(&header.terminator, &header.statements, 0)?;
self.in_loop_body = None;
self.local_depth = saved_map;
self.depth = saved_depth;
self.emit_loop_init(info, &loop_formula, inits)
}
fn emit_loop_init(&self, info: &LoopInfo, loop_formula: &str, inits: &BTreeMap<u32, String>) -> Result<String, String> {
let mut init_subject = nox_axis(1); for &local in info.carried_locals.iter() {
let init_val = inits.get(&local)
.cloned()
.unwrap_or_else(|| nox_quote(&nox_atom(0)));
init_subject = nox_cons(&init_val, &init_subject);
}
init_subject = nox_cons(&nox_quote(loop_formula), &init_subject);
Ok(nox_compose(&init_subject, &nox_quote(loop_formula)))
}
fn emit_back_edge(&self, info: &LoopInfo) -> Result<String, String> {
let mut new_subj = nox_quote(&nox_atom(0));
for param in self.func.params.iter() {
let val = self.local_axis(param.index)?;
new_subj = nox_cons(&val, &new_subj);
}
for &local in info.carried_locals.iter() {
let val = self.local_axis(local)?;
new_subj = nox_cons(&val, &new_subj);
}
let num_carried = info.carried_locals.len() as u32;
let loop_depth = 1 + num_carried + self.num_params;
let formula_depth = self.depth - loop_depth; new_subj = nox_cons(&nox_axis(Self::depth_to_axis(formula_depth)), &new_subj);
let formula_axis = Self::depth_to_axis(formula_depth);
Ok(nox_compose(&new_subj, &nox_axis(formula_axis)))
}
fn compile_terminator(
&mut self,
term: &mir::Terminator,
stmts: &[mir::Statement],
stmt_idx: usize,
) -> Result<String, String> {
if stmt_idx < stmts.len() {
match &stmts[stmt_idx] {
mir::Statement::Assign { Assign: data } => {
let mir::Place::Local { Local: dest } = data.place;
let value = self.compile_rvalue(&data.rvalue)?;
let saved = self.push_binding(dest);
let rest = self.compile_terminator(term, stmts, stmt_idx + 1)?;
self.pop_binding(saved);
let binding = nox_cons(&value, &nox_axis(1));
return Ok(nox_compose(&binding, &nox_quote(&rest)));
}
}
}
match term {
mir::Terminator::Return(_) => {
self.local_axis(0)
}
mir::Terminator::Goto { Goto: data } => {
self.compile_block(data.target)
}
mir::Terminator::SwitchInt { SwitchInt: data } => {
let disc = self.compile_operand(&data.discriminant)?;
if data.targets.len() == 1 && data.targets[0].0 == 0 {
let zero_block = data.targets[0].1; let nonzero_block = data.otherwise; let yes = self.compile_block(zero_block)?; let no = self.compile_block(nonzero_block)?; Ok(nox_branch(&disc, &yes, &no))
} else {
Err("complex SwitchInt not supported yet".to_string())
}
}
mir::Terminator::Call { Call: data } => {
let value = self.compile_call(data)?;
let mir::Place::Local { Local: dest } = data.destination;
let saved = self.push_binding(dest);
let rest = self.compile_block(data.target)?;
self.pop_binding(saved);
let binding = nox_cons(&value, &nox_axis(1));
Ok(nox_compose(&binding, &nox_quote(&rest)))
}
}
}
}
pub fn run_mir2nox(args: &[String]) {
let mut input_path = String::new();
let mut func_filter: Option<String> = None;
let mut output_dir: Option<String> = None;
let mut i = 0;
while i < args.len() {
match args[i].as_str() {
"-f" | "--function" => {
i += 1;
if i < args.len() { func_filter = Some(args[i].clone()); }
}
"-o" => {
i += 1;
if i < args.len() { output_dir = Some(args[i].clone()); }
}
"--help" | "-h" => {
eprintln!("nox mir โ compile Rust MIR JSON to nox formulas");
eprintln!();
eprintln!("Usage:");
eprintln!(" nox mir <file.mir.json> compile all functions");
eprintln!(" nox mir <file.mir.json> -f relu compile specific function");
eprintln!(" rsc --emit=mir-rs foo.rs | nox mir -");
eprintln!();
eprintln!("Options:");
eprintln!(" -f, --function <name> compile only this function");
eprintln!(" -o <dir> output directory for .nox files");
std::process::exit(0);
}
other => { input_path = other.to_string(); }
}
i += 1;
}
let json_bytes = if input_path == "-" || input_path.is_empty() {
use std::io::Read;
let mut buf = String::new();
if input_path.is_empty() {
use std::io::IsTerminal;
if std::io::stdin().is_terminal() {
eprintln!("error: no input. Run `nox mir --help`.");
std::process::exit(1);
}
}
std::io::stdin().read_to_string(&mut buf).unwrap_or_else(|e| {
eprintln!("error reading stdin: {}", e);
std::process::exit(1);
});
buf
} else {
std::fs::read_to_string(&input_path).unwrap_or_else(|e| {
eprintln!("error reading '{}': {}", input_path, e);
std::process::exit(1);
})
};
let krate: mir::Crate = serde_json::from_str(&json_bytes).unwrap_or_else(|e| {
eprintln!("error parsing MIR JSON: {}", e);
std::process::exit(1);
});
eprintln!("crate: {} ({} functions)", krate.name, krate.functions.len());
for func in &krate.functions {
if let Some(ref filter) = func_filter {
if !func.name.contains(filter.as_str()) { continue; }
}
match compile_function(func) {
Ok(formula) => {
let params = func.params.len();
if let Some(ref dir) = output_dir {
let path = format!("{}/{}.nox", dir, func.name);
std::fs::write(&path, &formula).unwrap_or_else(|e| {
eprintln!("error writing '{}': {}", path, e);
});
eprintln!(" {} ({} params) โ {}", func.name, params, path);
} else {
eprintln!(" {} ({} params):", func.name, params);
println!("{}", formula);
}
}
Err(e) => {
eprintln!(" {} โ error: {}", func.name, e);
}
}
}
}