Generating x86-64 Assembly
Our IR can name as many temporaries as it needs, but the processor has a fixed set of registers. We now need to decide where values live and how machine instructions use them. I'd like to keep this translation easy to inspect, even at the cost of extra instructions.
Code generation takes an operation such as %7 = mul %3, %4 and emits assembly for it, including any register moves and stack accesses it needs. Calls also have to follow the target's rules for passing arguments and returning results.
Why this phase matters
A program can pass every frontend check and still be translated incorrectly. The backend needs to preserve registers where required, align the stack, and make callers and callees agree on argument and return locations.
Supporting targets such as x86-64, ARM64, WebAssembly, and embedded chips also means handling their operating-system interfaces, object formats, and relocation models. rustc relies on LLVM for much of this work. C exposes many machine concepts in its source language, though its backends still face these choices. Java and Python often target virtual machines first; JavaScript engines can generate native code using runtime feedback.
MicroRust chooses a single concrete target: x86-64 System V assembly. The examples below use Linux symbol spelling and Intel syntax. The companion also emits macOS Mach-O assembly with leading underscores on external symbols. We will keep it textual and conservative.
What we are building here
We'll add a backend module to main.rs. Its assembly function receives the IrProgram from earlier phases and returns assembly text. Reading and parsing example.mrs remain the driver's earlier steps.
We are translating the optimized IR from the previous post into assembly text that the platform assembler can consume. The target model is intentionally simple:
- integers are 32-bit values
- function arguments use the System V integer argument registers
- return values come back in
eax - locals live in stack slots
- temporaries are evaluated with a small set of scratch registers
- calls go through symbol names
We'll start by storing values on the stack and using scratch registers while computing them. It gives us a translation we can inspect before considering a more ambitious register allocator.
System V x86-64 passes the first six integer arguments in registers. Our frontend rejects functions with more than six parameters, so we do not silently ignore stack arguments. For 32-bit integer values, the relevant register names are:
arg0 -> edi
arg1 -> esi
arg2 -> edx
arg3 -> ecx
arg4 -> r8d
arg5 -> r9d
return -> eaxA calling convention specifies where arguments and return values go, which registers a function may overwrite, and how the stack should be arranged. Two compilation units can assemble and link successfully despite disagreeing about this contract. The error then appears at runtime, when one function reads its arguments from the wrong place.
For add, the source is:
fn add(a: i32, b: i32) -> i32 {
return a + b;
}The IR is:
fn add(a, b):
bb0:
%0 = load a
%1 = load b
%2 = add %0, %1
return %2The unoptimized translation reserves stack space for both parameters and temporaries. Here is its complete arithmetic routine, with a descriptive overflow label:
.intel_syntax noprefix
.text
.globl mr_add
mr_add:
push rbp
mov rbp, rsp
sub rsp, 32
mov DWORD PTR [rbp - 4], edi
mov DWORD PTR [rbp - 8], esi
mov eax, DWORD PTR [rbp - 4]
mov DWORD PTR [rbp - 12], eax
mov eax, DWORD PTR [rbp - 8]
mov DWORD PTR [rbp - 16], eax
mov eax, DWORD PTR [rbp - 12]
add eax, DWORD PTR [rbp - 16]
jo L_add_overflow
mov DWORD PTR [rbp - 20], eax
mov eax, DWORD PTR [rbp - 20]
mov rsp, rbp
pop rbp
ret
L_add_overflow:
call microrust_trap
ud2Computing edi + esi directly and checking overflow would take fewer instructions. For now, storing parameters on the stack lets us handle them like other locals. We can revisit the extra memory accesses once this translation works.
Instruction selection is the process of choosing target instructions for IR operations. For constants:
%2 = const 8we can emit:
mov eax, 8For addition:
%5 = add %3, %4we might load the left value into eax, then add the right:
mov eax, DWORD PTR [rbp - 12]
add eax, DWORD PTR [rbp - 16]
jo L_overflowThe backend needs a location map:
struct Frame {
locals: HashMap<SymbolId, usize>,
value_base: usize,
size: usize,
}Frame maps local IDs to byte offsets. Slots for temporary values follow, indexed by value ID. We store every computed value in its slot. A register allocator would keep values in hardware registers and spill some to memory when space ran out. Graph coloring, linear scan, and PBQP are among the approaches used, often with target-specific changes. We'll defer that work.
The stack frame holds locals, spilled temporaries, saved registers, and sometimes outgoing call arguments. A function prologue sets it up:
push rbp
mov rbp, rsp
sub rsp, 48The matching epilogue restores the stack before returning:
mov rsp, rbp
pop rbp
retWe round the frame size up to a multiple of 16; twelve 4-byte slots already fit in 48 bytes. System V requires stack alignment at call boundaries. On entry, the pushed return address leaves rsp eight bytes short of a 16-byte boundary. Saving rbp restores alignment, and subtracting a multiple of 16 preserves it. A library call is a useful test here because it may expose an alignment error that arithmetic alone misses.
After loading the left operand into eax, the emitter selects the non-division instruction and checks its overflow flag:
let instruction = match op {
BinOp::Add => "add",
BinOp::Sub => "sub",
BinOp::Mul => "imul",
BinOp::Div => unreachable!(),
};
writeln!(
out,
" {instruction} eax, DWORD PTR [rbp - {}]\n jo {trap}",
frame.value(*right)
)
.unwrap();Division needs different preparation from addition or multiplication. x86-64 integer division uses eax and edx together. For signed 32-bit division, we load the dividend into eax, sign-extend into edx:eax with cdq, then divide by the operand:
mov eax, DWORD PTR [rbp - 12]
cdq
idiv DWORD PTR [rbp - 16]These instructions show only the division itself. Before them, the emitter checks for a zero divisor and i32::MIN, -1, which would make idiv fault. Those guards call microrust_trap to report failure and exit. Addition, subtraction, and multiplication use jo for overflow.
A call needs argument registers prepared instead. Given this IR:
%8 = call add(%6, %7)we place arguments in registers, call the symbol, then store eax:
mov edi, DWORD PTR [rbp - 24]
mov esi, DWORD PTR [rbp - 28]
call mr_add
mov DWORD PTR [rbp - 32], eaxprintln! remains special. We can lower it to a runtime helper like microrust_print_i32:
mov edi, DWORD PTR [rbp - 36]
call microrust_print_i32The companion implements that helper in C, using a fixed-width type and its matching format macro:
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
void microrust_print_i32(int32_t value) {
printf("%" PRId32 "\n", value);
}The generated assembly now references microrust_print_i32, whose implementation lives in a separate runtime object. The linker will need that definition when building the executable.
For a terminator such as return %2, the backend places %2 in eax before restoring the frame and executing ret:
mov eax, DWORD PTR [rbp - 20]
mov rsp, rbp
pop rbp
retA unit return needs the epilogue without a result value. We prefix source function symbols with mr_; a separate C-ABI main wrapper calls mr_main and sets eax to zero. That prevents a leftover printf result from becoming the exit status. Some compilers share an epilogue across returns. MicroRust emits it at each return, which is sufficient for these small functions.
On Apple Silicon, cc -arch x86_64 assembles and links this target, and Rosetta is needed to execute it. ./microrustc run example.mrs instead interprets our IR on the host; it does not execute the generated machine code. Native tests cover the latter separately.
The examples use Intel-style assembly, with instructions such as mov dst, src. AT&T syntax reverses the operands and prefixes registers with %. There are also differences among macOS assemblers, GNU assemblers, and LLVM's integrated assembler. Choosing a dialect consistently matters when passing the emitted text to an assembler.
Calling conventions distinguish caller-saved and callee-saved registers. On System V x86-64, rax, rcx, rdx, rsi, rdi, and r8 through r11 are caller-saved: a caller needing their values after a call must save them. A callee that uses rbx, rbp, or r12 through r15 must restore them before returning. Those are callee-saved registers.
Our stack-based strategy stores values before calls and reloads them afterward, avoiding much of this register bookkeeping at the cost of extra memory accesses. Keeping values in registers across instructions would require liveness analysis: determining which values will be used again. The allocator needs that information to decide what to keep and what to spill.
Fewer live IR values reduce register pressure, making allocation easier. Better instruction selection can also remove moves, while an allocator can keep frequently used values in registers. These changes improve generated code without changing the source language.
If the program prints 16 instead of 24, we can compare the IR and assembly. Did resolution choose the wrong binding, lowering load x instead of y, or the emitter overwrite eax before storing the result? Keeping the translation readable helps us locate the mistake.
Java bytecode generation faces a different target contract. A JVM instruction sequence manipulates an operand stack and symbolic references. Python bytecode targets the Python virtual machine. Ruby has YARV instructions. JavaScript engines may generate machine code but can also fall back, patch, or deoptimize when runtime assumptions break. Native Rust code generation ultimately needs machine code, and rustc uses LLVM to avoid hand-writing every backend from scratch.
We now have assembly for the IR, with printing supplied by the runtime helper.
Run this version
Add the backend to the same main.rs. This version retains the frontend, IR, optimizer, and runner, then adds asm. It can write x86-64 assembly using either Linux or macOS symbol conventions. Emitting the text does not require an assembler yet.
These are the source files to keep. Any golden.mrs saved earlier can stay beside them; the commands below use example.mrs:
microrust/
|-- main.rs
`-- example.mrsReplace the contents of main.rs with this complete version, or compare it with the additions you've made while reading. The listing already includes the earlier phases.
main.rs: compiler through assembly generation
// Chapter 08: add assembly generation.
use std::fmt;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Span {
pub start: usize,
pub end: usize,
}
#[derive(Debug, Clone)]
pub struct Error {
pub phase: &'static str,
pub span: Span,
pub message: String,
}
impl Error {
pub fn new(phase: &'static str, span: Span, message: impl Into<String>) -> Self {
Self {
phase,
span,
message: message.into(),
}
}
pub fn render(&self, path: &str, source: &str) -> String {
let start = self.span.start.min(source.len());
let prefix = &source[..start];
let line = prefix.bytes().filter(|b| *b == b'\n').count() + 1;
let column = prefix.rsplit('\n').next().unwrap_or("").chars().count() + 1;
let text = source.lines().nth(line - 1).unwrap_or("");
format!(
"{}\n --> {path}:{line}:{column}\n{line} | {text}\n | {}^",
self,
" ".repeat(column - 1)
)
}
}
impl fmt::Display for Error {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{} error: {}", self.phase, self.message)
}
}
impl std::error::Error for Error {}
// Later phases will use the source spans retained in the AST.
#[allow(dead_code)]
mod syntax {
use crate::{Error, Span};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TokenKind {
Fn,
Let,
Return,
Ident,
Int,
String,
I32,
Plus,
Minus,
Star,
Slash,
Colon,
Semicolon,
Comma,
LParen,
RParen,
LBrace,
RBrace,
Arrow,
Eq,
Bang,
Eof,
}
#[derive(Debug, Clone)]
pub struct Token {
pub kind: TokenKind,
pub lexeme: String,
pub span: Span,
}
pub fn ident_or_keyword(text: &str) -> TokenKind {
match text {
"fn" => TokenKind::Fn,
"let" => TokenKind::Let,
"return" => TokenKind::Return,
"i32" => TokenKind::I32,
_ => TokenKind::Ident,
}
}
pub fn lex(source: &str) -> Result<Vec<Token>, Error> {
let bytes = source.as_bytes();
let mut pos = 0;
let mut tokens = Vec::new();
while pos < bytes.len() {
if bytes[pos].is_ascii_whitespace() {
pos += 1;
continue;
}
if source[pos..].starts_with("//!")
|| (source[pos..].starts_with("///") && !source[pos..].starts_with("////"))
{
return Err(Error::new(
"lex",
Span {
start: pos,
end: pos + 3,
},
"doc comments are outside MicroRust",
));
}
if source[pos..].starts_with("//") {
while pos < bytes.len() && bytes[pos] != b'\n' {
pos += 1;
}
continue;
}
let start = pos;
let c = bytes[pos];
pos += 1;
let kind = if c.is_ascii_alphabetic() || c == b'_' {
while pos < bytes.len()
&& (bytes[pos].is_ascii_alphanumeric() || bytes[pos] == b'_')
{
pos += 1;
}
ident_or_keyword(&source[start..pos])
} else if c.is_ascii_digit() {
while pos < bytes.len() && bytes[pos].is_ascii_digit() {
pos += 1;
}
TokenKind::Int
} else {
match c {
b'+' => TokenKind::Plus,
b'-' if bytes.get(pos) == Some(&b'>') => {
pos += 1;
TokenKind::Arrow
}
b'-' => TokenKind::Minus,
b'*' => TokenKind::Star,
b'/' if bytes.get(pos) == Some(&b'*') => {
return Err(Error::new(
"lex",
Span {
start,
end: pos + 1,
},
"block comments are outside MicroRust; use //",
))
}
b'/' => TokenKind::Slash,
b':' => TokenKind::Colon,
b';' => TokenKind::Semicolon,
b',' => TokenKind::Comma,
b'(' => TokenKind::LParen,
b')' => TokenKind::RParen,
b'{' => TokenKind::LBrace,
b'}' => TokenKind::RBrace,
b'=' => TokenKind::Eq,
b'!' => TokenKind::Bang,
b'"' => {
while pos < bytes.len() && bytes[pos] != b'"' {
if !bytes[pos].is_ascii() || matches!(bytes[pos], b'\\' | b'\n' | b'\r')
{
return Err(Error::new(
"lex",
Span { start, end: pos },
"only the unescaped format string \"{}\" is supported",
));
}
pos += 1;
}
if pos == bytes.len() {
return Err(Error::new(
"lex",
Span { start, end: pos },
"unterminated string",
));
}
pos += 1;
TokenKind::String
}
_ => {
let ch = source[start..].chars().next().unwrap();
return Err(Error::new(
"lex",
Span {
start,
end: start + ch.len_utf8(),
},
format!("unexpected character '{ch}'"),
));
}
}
};
tokens.push(Token {
kind,
lexeme: source[start..pos].into(),
span: Span { start, end: pos },
});
}
tokens.push(Token {
kind: TokenKind::Eof,
lexeme: String::new(),
span: Span {
start: pos,
end: pos,
},
});
Ok(tokens)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Type {
I32,
Unit,
Never,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BinOp {
Add,
Sub,
Mul,
Div,
}
#[derive(Debug, Clone)]
pub struct Program {
pub functions: Vec<Function>,
}
#[derive(Debug, Clone)]
pub struct Function {
pub name: String,
pub span: Span,
pub params: Vec<Param>,
pub return_type: Type,
pub body: Block,
}
#[derive(Debug, Clone)]
pub struct Param {
pub name: String,
pub span: Span,
}
#[derive(Debug, Clone)]
pub struct Block {
pub statements: Vec<Stmt>,
pub tail: Option<Box<Expr>>,
pub span: Span,
}
#[derive(Debug, Clone)]
pub enum Stmt {
Let {
name: String,
span: Span,
value: Expr,
},
Return {
value: Option<Expr>,
span: Span,
},
Expr(Expr),
}
#[derive(Debug, Clone)]
pub struct Expr {
pub kind: ExprKind,
pub span: Span,
}
#[derive(Debug, Clone)]
pub enum ExprKind {
Int(i32),
Name(String),
Binary {
op: BinOp,
left: Box<Expr>,
right: Box<Expr>,
},
Call {
callee: String,
args: Vec<Expr>,
},
Println {
value: Box<Expr>,
},
Block(Block),
}
impl BinOp {
pub fn checked(self, a: i32, b: i32) -> Option<i32> {
match self {
Self::Add => a.checked_add(b),
Self::Sub => a.checked_sub(b),
Self::Mul => a.checked_mul(b),
Self::Div => a.checked_div(b),
}
}
}
pub struct Parser {
tokens: Vec<Token>,
pos: usize,
}
impl Parser {
pub fn new(tokens: Vec<Token>) -> Self {
Self { tokens, pos: 0 }
}
fn peek(&self) -> &Token {
&self.tokens[self.pos]
}
fn advance(&mut self) -> Token {
let t = self.peek().clone();
if t.kind != TokenKind::Eof {
self.pos += 1;
}
t
}
fn error(&self, message: &str) -> Error {
Error::new("parse", self.peek().span, message)
}
fn eat(&mut self, kind: TokenKind) -> bool {
if self.peek().kind == kind {
self.advance();
true
} else {
false
}
}
fn expect(&mut self, kind: TokenKind) -> Result<Token, Error> {
if self.peek().kind == kind {
Ok(self.advance())
} else {
Err(self.error(&format!("expected {kind:?}, found {:?}", self.peek().kind)))
}
}
fn ident(&mut self) -> Result<Token, Error> {
let token = self.expect(TokenKind::Ident)?;
// A restricted scanner must not turn Rust keywords into valid user names.
const RESERVED: &[&str] = &[
"_", "as", "async", "await", "break", "const", "continue", "crate", "dyn", "else",
"enum", "extern", "false", "for", "if", "impl", "in", "loop", "match", "mod",
"move", "mut", "pub", "ref", "self", "Self", "static", "struct", "super", "trait",
"true", "type", "unsafe", "use", "where", "while", "abstract", "become", "box",
"do", "final", "macro", "override", "priv", "typeof", "unsized", "virtual",
"yield", "try", "gen",
];
if RESERVED.contains(&token.lexeme.as_str()) {
return Err(Error::new(
"parse",
token.span,
"reserved Rust word is not an identifier",
));
}
Ok(token)
}
pub fn parse(mut self) -> Result<Program, Error> {
let mut functions = Vec::new();
while self.peek().kind != TokenKind::Eof {
functions.push(self.parse_function()?);
}
Ok(Program { functions })
}
fn parse_function(&mut self) -> Result<Function, Error> {
self.expect(TokenKind::Fn)?;
let name = self.ident()?;
self.expect(TokenKind::LParen)?;
let mut params = Vec::new();
while self.peek().kind != TokenKind::RParen {
let param = self.ident()?;
self.expect(TokenKind::Colon)?;
self.expect(TokenKind::I32)?;
params.push(Param {
name: param.lexeme,
span: param.span,
});
if !self.eat(TokenKind::Comma) {
break;
}
}
self.expect(TokenKind::RParen)?;
let return_type = if self.eat(TokenKind::Arrow) {
self.expect(TokenKind::I32)?;
Type::I32
} else {
Type::Unit
};
let body = self.parse_block()?;
Ok(Function {
name: name.lexeme,
span: name.span,
params,
return_type,
body,
})
}
fn parse_block(&mut self) -> Result<Block, Error> {
let start = self.expect(TokenKind::LBrace)?.span.start;
let mut statements = Vec::new();
let mut tail = None;
while self.peek().kind != TokenKind::RBrace {
if self.peek().kind == TokenKind::Eof {
return Err(self.error("unclosed block"));
}
if self.eat(TokenKind::Let) {
let name = self.ident()?;
self.expect(TokenKind::Colon)?;
self.expect(TokenKind::I32)?;
self.expect(TokenKind::Eq)?;
let value = self.parse_expr(0)?;
self.expect(TokenKind::Semicolon)?;
statements.push(Stmt::Let {
name: name.lexeme,
span: name.span,
value,
});
} else if self.peek().kind == TokenKind::Return {
let span = self.advance().span;
let value = if self.peek().kind == TokenKind::Semicolon {
None
} else {
Some(self.parse_expr(0)?)
};
self.expect(TokenKind::Semicolon)?;
statements.push(Stmt::Return { value, span });
} else {
let value = self.parse_expr(0)?;
if self.eat(TokenKind::Semicolon) {
statements.push(Stmt::Expr(value));
} else {
tail = Some(Box::new(value));
break;
}
}
}
let end = self.expect(TokenKind::RBrace)?.span.end;
Ok(Block {
statements,
tail,
span: Span { start, end },
})
}
fn current_infix(&self) -> Option<(BinOp, u8, u8)> {
match self.peek().kind {
TokenKind::Plus => Some((BinOp::Add, 20, 21)),
TokenKind::Minus => Some((BinOp::Sub, 20, 21)),
TokenKind::Star => Some((BinOp::Mul, 30, 31)),
TokenKind::Slash => Some((BinOp::Div, 30, 31)),
_ => None,
}
}
fn parse_expr(&mut self, min_bp: u8) -> Result<Expr, Error> {
let mut left = self.parse_prefix()?;
while let Some((op, left_bp, right_bp)) = self.current_infix() {
if left_bp < min_bp {
break;
}
self.advance();
let right = self.parse_expr(right_bp)?;
let span = Span {
start: left.span.start,
end: right.span.end,
};
left = Expr {
kind: ExprKind::Binary {
op,
left: Box::new(left),
right: Box::new(right),
},
span,
};
}
Ok(left)
}
fn parse_prefix(&mut self) -> Result<Expr, Error> {
match self.peek().kind {
TokenKind::Int => {
let t = self.advance();
let n = t.lexeme.parse::<i32>().map_err(|_| {
Error::new("parse", t.span, "integer literal is outside 0..=2147483647")
})?;
Ok(Expr {
kind: ExprKind::Int(n),
span: t.span,
})
}
TokenKind::Ident => {
let name = self.ident()?;
let kind = if self.eat(TokenKind::Bang) {
if name.lexeme != "println" {
return Err(Error::new(
"parse",
name.span,
"only println! is supported",
));
}
self.expect(TokenKind::LParen)?;
let format = self.expect(TokenKind::String)?;
if format.lexeme != "\"{}\"" {
return Err(Error::new(
"parse",
format.span,
"expected format string \"{}\"",
));
}
self.expect(TokenKind::Comma)?;
let value = self.parse_expr(0)?;
self.expect(TokenKind::RParen)?;
ExprKind::Println {
value: Box::new(value),
}
} else if self.eat(TokenKind::LParen) {
let mut args = Vec::new();
while self.peek().kind != TokenKind::RParen {
args.push(self.parse_expr(0)?);
if !self.eat(TokenKind::Comma) {
break;
}
}
self.expect(TokenKind::RParen)?;
ExprKind::Call {
callee: name.lexeme,
args,
}
} else {
ExprKind::Name(name.lexeme)
};
let end = self.tokens[self.pos - 1].span.end;
Ok(Expr {
kind,
span: Span {
start: name.span.start,
end,
},
})
}
TokenKind::LParen => {
self.advance();
let expr = self.parse_expr(0)?;
self.expect(TokenKind::RParen)?;
Ok(expr)
}
TokenKind::LBrace => {
let block = self.parse_block()?;
let span = block.span;
Ok(Expr {
kind: ExprKind::Block(block),
span,
})
}
_ => Err(self.error("expected expression")),
}
}
}
}
#[allow(dead_code)]
mod semantics {
use crate::syntax::{Block, Expr, ExprKind, Program, Stmt, Type};
use crate::{Error, Span};
use std::collections::{HashMap, HashSet};
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct SymbolId(pub usize);
#[derive(Debug, Clone)]
pub struct Symbol {
pub name: String,
pub kind: SymbolKind,
pub span: Span,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SymbolKind {
Function,
Local,
Parameter,
}
pub struct ResolvedProgram {
pub ast: Program,
pub symbols: Vec<Symbol>,
pub names: HashMap<usize, SymbolId>,
pub globals: HashMap<String, SymbolId>,
}
struct Resolver {
symbols: Vec<Symbol>,
names: HashMap<usize, SymbolId>,
globals: HashMap<String, SymbolId>,
scopes: Vec<HashMap<String, SymbolId>>,
}
pub fn resolve(ast: Program) -> Result<ResolvedProgram, Error> {
let mut r = Resolver {
symbols: vec![],
names: HashMap::new(),
globals: HashMap::new(),
scopes: vec![],
};
for f in &ast.functions {
if r.globals.contains_key(&f.name) {
return Err(Error::new(
"resolve",
f.span,
format!("duplicate function `{}`", f.name),
));
}
let id = r.declare(&f.name, SymbolKind::Function, f.span);
r.globals.insert(f.name.clone(), id);
}
for f in &ast.functions {
r.scopes.push(HashMap::new());
for p in &f.params {
if r.scopes.last().unwrap().contains_key(&p.name) {
return Err(Error::new("resolve", p.span, "duplicate parameter"));
}
let id = r.declare(&p.name, SymbolKind::Parameter, p.span);
r.scopes.last_mut().unwrap().insert(p.name.clone(), id);
}
r.block(&f.body)?;
r.scopes.pop();
}
Ok(ResolvedProgram {
ast,
symbols: r.symbols,
names: r.names,
globals: r.globals,
})
}
impl Resolver {
fn declare(&mut self, name: &str, kind: SymbolKind, span: Span) -> SymbolId {
let id = SymbolId(self.symbols.len());
self.symbols.push(Symbol {
name: name.into(),
kind,
span,
});
self.names.insert(span.start, id);
id
}
fn lookup_local(&self, name: &str) -> Option<SymbolId> {
self.scopes
.iter()
.rev()
.find_map(|scope| scope.get(name).copied())
}
fn block(&mut self, block: &Block) -> Result<(), Error> {
self.scopes.push(HashMap::new());
for stmt in &block.statements {
match stmt {
Stmt::Let { name, span, value } => {
self.expr(value)?;
let id = self.declare(name, SymbolKind::Local, *span);
self.scopes.last_mut().unwrap().insert(name.clone(), id);
}
Stmt::Return { value, .. } => {
if let Some(value) = value {
self.expr(value)?;
}
}
Stmt::Expr(value) => self.expr(value)?,
}
}
if let Some(tail) = &block.tail {
self.expr(tail)?;
}
self.scopes.pop();
Ok(())
}
fn expr(&mut self, expr: &Expr) -> Result<(), Error> {
match &expr.kind {
ExprKind::Int(_) => {}
ExprKind::Name(name) => {
let id = self.lookup_local(name).ok_or_else(|| {
Error::new(
"resolve",
expr.span,
format!("cannot find local `{name}` in this scope"),
)
})?;
self.names.insert(expr.span.start, id);
}
ExprKind::Binary { left, right, .. } => {
self.expr(left)?;
self.expr(right)?;
}
ExprKind::Call { callee, args } => {
if self.lookup_local(callee).is_some() {
return Err(Error::new(
"resolve",
expr.span,
format!("`{callee}` is a local, not a callable function"),
));
}
let id = self.globals.get(callee).copied().ok_or_else(|| {
Error::new(
"resolve",
expr.span,
format!("cannot find function `{callee}`"),
)
})?;
self.names.insert(expr.span.start, id);
for arg in args {
self.expr(arg)?;
}
}
ExprKind::Println { value } => self.expr(value)?,
ExprKind::Block(block) => self.block(block)?,
}
Ok(())
}
}
#[derive(Debug, Clone)]
pub struct FnSig {
pub params: Vec<Type>,
pub ret: Type,
}
pub struct TypedProgram {
pub resolved: ResolvedProgram,
pub signatures: HashMap<SymbolId, FnSig>,
pub types: HashMap<(usize, usize), Type>,
}
pub fn type_check(resolved: ResolvedProgram) -> Result<TypedProgram, Error> {
let main = resolved
.ast
.functions
.iter()
.find(|f| f.name == "main")
.ok_or_else(|| Error::new("type", Span { start: 0, end: 0 }, "missing fn main()"))?;
if !main.params.is_empty() || main.return_type != Type::Unit {
return Err(Error::new(
"type",
main.span,
"main must have no parameters and return unit",
));
}
let mut signatures = HashMap::new();
for f in &resolved.ast.functions {
if f.params.len() > 6 {
return Err(Error::new(
"type",
f.span,
"MicroRust supports at most six parameters",
));
}
signatures.insert(
resolved.globals[&f.name],
FnSig {
params: vec![Type::I32; f.params.len()],
ret: f.return_type,
},
);
}
let mut c = Checker {
resolved: &resolved,
signatures: &signatures,
types: HashMap::new(),
exits: HashSet::new(),
ret: Type::Unit,
};
for f in &resolved.ast.functions {
c.ret = f.return_type;
let actual = c.block(&f.body)?;
expect_type(f.return_type, actual, f.body.span)?;
}
let types = c.types;
Ok(TypedProgram {
resolved,
signatures,
types,
})
}
fn expect_type(expected: Type, actual: Type, span: Span) -> Result<(), Error> {
if actual == expected || actual == Type::Never {
Ok(())
} else {
Err(Error::new(
"type",
span,
format!("expected {expected:?}, found {actual:?}"),
))
}
}
struct Checker<'a> {
resolved: &'a ResolvedProgram,
signatures: &'a HashMap<SymbolId, FnSig>,
types: HashMap<(usize, usize), Type>,
exits: HashSet<(usize, usize)>,
ret: Type,
}
impl Checker<'_> {
fn block(&mut self, block: &Block) -> Result<Type, Error> {
let mut diverges = false;
for stmt in &block.statements {
match stmt {
Stmt::Let { value, .. } => {
let ty = self.expr(value)?;
expect_type(Type::I32, ty, value.span)?;
diverges |= self.exits.contains(&(value.span.start, value.span.end));
}
Stmt::Return { value, span } => {
let actual = match value {
Some(value) => self.expr(value)?,
None => Type::Unit,
};
expect_type(self.ret, actual, *span)?;
diverges = true;
}
Stmt::Expr(value) => {
self.expr(value)?;
diverges |= self.exits.contains(&(value.span.start, value.span.end));
}
}
}
let ty = if let Some(expr) = &block.tail {
let ty = self.expr(expr)?;
diverges |= self.exits.contains(&(expr.span.start, expr.span.end));
ty
} else if diverges {
Type::Never
} else {
Type::Unit
};
if diverges {
self.exits.insert((block.span.start, block.span.end));
}
// An explicit tail still has to type-check, even when unreachable.
Ok(ty)
}
fn expr(&mut self, expr: &Expr) -> Result<Type, Error> {
let ty = match &expr.kind {
ExprKind::Int(_) | ExprKind::Name(_) => Type::I32,
ExprKind::Binary { left, right, .. } => {
let a = self.expr(left)?;
let b = self.expr(right)?;
expect_type(Type::I32, a, left.span)?;
expect_type(Type::I32, b, right.span)?;
if a == Type::Never || b == Type::Never {
Type::Never
} else {
Type::I32
}
}
ExprKind::Call { callee, args } => {
let sig = self.signatures[&self.resolved.names[&expr.span.start]].clone();
if args.len() != sig.params.len() {
return Err(Error::new(
"type",
expr.span,
format!(
"function `{callee}` expects {} arguments but got {}",
sig.params.len(),
args.len()
),
));
}
let mut diverges = false;
for (arg, expected) in args.iter().zip(&sig.params) {
let actual = self.expr(arg)?;
expect_type(*expected, actual, arg.span)?;
diverges |= actual == Type::Never;
}
if diverges {
Type::Never
} else {
sig.ret
}
}
ExprKind::Println { value } => {
let ty = self.expr(value)?;
expect_type(Type::I32, ty, value.span)?;
if ty == Type::Never {
Type::Never
} else {
Type::Unit
}
}
ExprKind::Block(block) => self.block(block)?,
};
let exits = match &expr.kind {
ExprKind::Binary { left, right, .. } => {
self.exits.contains(&(left.span.start, left.span.end))
|| self.exits.contains(&(right.span.start, right.span.end))
}
ExprKind::Call { args, .. } => args
.iter()
.any(|arg| self.exits.contains(&(arg.span.start, arg.span.end))),
ExprKind::Println { value } => {
self.exits.contains(&(value.span.start, value.span.end))
}
ExprKind::Block(block) => self.exits.contains(&(block.span.start, block.span.end)),
_ => false,
};
if exits {
self.exits.insert((expr.span.start, expr.span.end));
}
self.types.insert((expr.span.start, expr.span.end), ty);
Ok(ty)
}
}
}
#[allow(dead_code)]
mod ir {
use crate::semantics::{SymbolId, TypedProgram};
use crate::syntax::{BinOp, Block, Expr, ExprKind, Stmt, Type};
use crate::{Error, Span};
use std::collections::{HashMap, HashSet};
pub type ValueId = usize;
pub type LocalId = SymbolId;
#[derive(Debug, Clone)]
pub struct IrProgram {
pub functions: Vec<IrFunction>,
}
#[derive(Debug, Clone)]
pub struct IrFunction {
pub name: String,
pub params: Vec<LocalId>,
pub ret: Type,
pub block: BasicBlock,
pub value_count: usize,
}
#[derive(Debug, Clone)]
pub struct BasicBlock {
pub instrs: Vec<SpannedInstr>,
pub terminator: Terminator,
}
#[derive(Debug, Clone)]
pub struct SpannedInstr {
pub instr: Instr,
pub span: Span,
}
#[derive(Debug, Clone)]
pub enum Instr {
Const {
dst: ValueId,
value: i32,
},
LoadLocal {
dst: ValueId,
local: LocalId,
},
StoreLocal {
local: LocalId,
src: ValueId,
},
Binary {
dst: ValueId,
op: BinOp,
left: ValueId,
right: ValueId,
},
Call {
dst: Option<ValueId>,
name: String,
args: Vec<ValueId>,
},
Println {
value: ValueId,
},
}
#[derive(Debug, Clone, Copy)]
pub enum Terminator {
Return(Option<ValueId>),
}
impl Instr {
pub fn destination(&self) -> Option<ValueId> {
match self {
Self::Const { dst, .. }
| Self::LoadLocal { dst, .. }
| Self::Binary { dst, .. } => Some(*dst),
Self::Call { dst, .. } => *dst,
_ => None,
}
}
pub fn inputs(&self) -> Vec<ValueId> {
match self {
Self::Binary { left, right, .. } => vec![*left, *right],
Self::StoreLocal { src, .. } => vec![*src],
Self::Println { value } => vec![*value],
Self::Call { args, .. } => args.clone(),
_ => vec![],
}
}
pub fn has_side_effects(&self) -> bool {
// Checked arithmetic can trap even if its result is never used.
!matches!(self, Self::Const { .. } | Self::LoadLocal { .. })
}
}
pub fn lower(typed: &TypedProgram) -> IrProgram {
let mut functions = Vec::new();
for f in &typed.resolved.ast.functions {
let mut l = Lowerer {
typed,
instrs: vec![],
terminator: None,
next: 0,
};
let tail = l.block(&f.body);
let terminator = l.terminator.unwrap_or(Terminator::Return(tail));
functions.push(IrFunction {
name: f.name.clone(),
params: f
.params
.iter()
.map(|p| typed.resolved.names[&p.span.start])
.collect(),
ret: f.return_type,
block: BasicBlock {
instrs: l.instrs,
terminator,
},
value_count: l.next,
});
}
IrProgram { functions }
}
struct Lowerer<'a> {
typed: &'a TypedProgram,
instrs: Vec<SpannedInstr>,
terminator: Option<Terminator>,
next: usize,
}
impl Lowerer<'_> {
fn new_value(&mut self) -> ValueId {
let id = self.next;
self.next += 1;
id
}
fn emit(&mut self, instr: Instr, span: Span) {
self.instrs.push(SpannedInstr { instr, span });
}
fn block(&mut self, block: &Block) -> Option<ValueId> {
for stmt in &block.statements {
if self.terminator.is_some() {
return None;
}
match stmt {
Stmt::Let { span, value, .. } => {
if let Some(src) = self.expr(value) {
let local = self.typed.resolved.names[&span.start];
self.emit(Instr::StoreLocal { local, src }, *span);
}
}
Stmt::Return { value, .. } => {
let value = value.as_ref().and_then(|v| self.expr(v));
if self.terminator.is_none() {
self.terminator = Some(Terminator::Return(value));
}
}
Stmt::Expr(expr) => {
self.expr(expr);
}
}
}
if self.terminator.is_some() {
None
} else {
block.tail.as_ref().and_then(|e| self.expr(e))
}
}
fn expr(&mut self, expr: &Expr) -> Option<ValueId> {
if self.terminator.is_some() {
return None;
}
let instr = match &expr.kind {
ExprKind::Int(value) => Instr::Const {
dst: self.new_value(),
value: *value,
},
ExprKind::Name(_) => Instr::LoadLocal {
dst: self.new_value(),
local: self.typed.resolved.names[&expr.span.start],
},
ExprKind::Binary { op, left, right } => {
let left = self.expr(left)?;
let right = self.expr(right)?;
Instr::Binary {
dst: self.new_value(),
op: *op,
left,
right,
}
}
ExprKind::Call { callee, args } => {
let mut values = Vec::new();
for arg in args {
values.push(self.expr(arg)?);
}
let sig = &self.typed.signatures[&self.typed.resolved.names[&expr.span.start]];
let dst = if sig.ret == Type::I32 {
Some(self.new_value())
} else {
None
};
Instr::Call {
dst,
name: callee.clone(),
args: values,
}
}
ExprKind::Println { value } => Instr::Println {
value: self.expr(value)?,
},
ExprKind::Block(block) => return self.block(block),
};
let dst = instr.destination();
self.emit(instr, expr.span);
dst
}
}
pub fn fold_constants(block: &mut BasicBlock) {
let mut constants = HashMap::<ValueId, i32>::new();
let mut locals = HashMap::<LocalId, i32>::new();
for item in &mut block.instrs {
let replacement = match &item.instr {
Instr::Const { value, .. } => Some(*value),
Instr::LoadLocal { local, .. } => locals.get(local).copied(),
Instr::Binary {
op, left, right, ..
} => constants
.get(left)
.zip(constants.get(right))
.and_then(|(a, b)| op.checked(*a, *b)),
Instr::StoreLocal { local, src } => {
if let Some(value) = constants.get(src) {
locals.insert(*local, *value);
} else {
locals.remove(local);
}
None
}
_ => None,
};
if let (Some(dst), Some(value)) = (item.instr.destination(), replacement) {
constants.insert(dst, value);
item.instr = Instr::Const { dst, value };
}
}
}
pub fn eliminate_dead_code(block: &mut BasicBlock) {
let mut used = HashSet::new();
let mut needed_locals = HashSet::new();
if let Terminator::Return(Some(value)) = block.terminator {
used.insert(value);
}
let mut kept = Vec::new();
for item in block.instrs.drain(..).rev() {
let live = item
.instr
.destination()
.is_some_and(|dst| used.contains(&dst));
let keep = match &item.instr {
Instr::StoreLocal { local, .. } => needed_locals.remove(local),
_ => live || item.instr.has_side_effects(),
};
if keep {
if let Instr::LoadLocal { local, .. } = &item.instr {
needed_locals.insert(*local);
}
used.extend(item.instr.inputs());
kept.push(item);
}
}
kept.reverse();
block.instrs = kept;
}
pub fn optimize(program: &mut IrProgram) {
for function in &mut program.functions {
fold_constants(&mut function.block);
eliminate_dead_code(&mut function.block);
}
}
pub fn verify(program: &IrProgram) -> Result<(), Error> {
let bad = |message| Error::new("IR", Span { start: 0, end: 0 }, message);
for f in &program.functions {
let mut values = HashSet::new();
let mut locals: HashSet<_> = f.params.iter().copied().collect();
for item in &f.block.instrs {
let instr = &item.instr;
if instr.inputs().iter().any(|v| !values.contains(v)) {
return Err(bad("value used before definition"));
}
if let Some(dst) = instr.destination() {
if dst >= f.value_count || !values.insert(dst) {
return Err(bad("invalid or duplicate destination"));
}
}
match instr {
Instr::LoadLocal { local, .. } if !locals.contains(local) => {
return Err(bad("load from uninitialized local"))
}
Instr::StoreLocal { local, .. } => {
locals.insert(*local);
}
Instr::Call { name, args, dst } => {
let callee = program
.functions
.iter()
.find(|c| c.name == *name)
.ok_or_else(|| bad("missing callee"))?;
if args.len() != callee.params.len()
|| dst.is_some() != (callee.ret == Type::I32)
{
return Err(bad("invalid IR call signature"));
}
}
_ => {}
}
}
let Terminator::Return(value) = f.block.terminator;
if value.is_some_and(|v| !values.contains(&v))
|| value.is_some() != (f.ret == Type::I32)
{
return Err(bad("invalid IR return"));
}
}
Ok(())
}
pub fn execute(program: &IrProgram) -> Result<Vec<i32>, Error> {
verify(program)?;
let mut runner = Runner {
program,
output: vec![],
budget: 1_000_000,
};
runner.call("main", &[], 0)?;
Ok(runner.output)
}
struct Runner<'a> {
program: &'a IrProgram,
output: Vec<i32>,
budget: usize,
}
impl Runner<'_> {
fn call(&mut self, name: &str, args: &[i32], depth: usize) -> Result<Option<i32>, Error> {
let error = |message| Error::new("runtime", Span { start: 0, end: 0 }, message);
if depth >= 256 {
return Err(error("IR runner call-depth limit reached"));
}
let f = self
.program
.functions
.iter()
.find(|f| f.name == name)
.ok_or_else(|| error("unknown function"))?;
let mut locals: HashMap<LocalId, i32> =
f.params.iter().copied().zip(args.iter().copied()).collect();
let mut values = vec![0; f.value_count];
for item in &f.block.instrs {
if self.budget == 0 {
return Err(error("IR runner instruction limit reached"));
}
self.budget -= 1;
match &item.instr {
Instr::Const { dst, value } => values[*dst] = *value,
Instr::LoadLocal { dst, local } => values[*dst] = locals[local],
Instr::StoreLocal { local, src } => {
locals.insert(*local, values[*src]);
}
Instr::Binary {
dst,
op,
left,
right,
} => {
values[*dst] =
op.checked(values[*left], values[*right]).ok_or_else(|| {
Error::new(
"runtime",
item.span,
"integer overflow or division by zero",
)
})?;
}
Instr::Call { dst, name, args } => {
let args: Vec<_> = args.iter().map(|v| values[*v]).collect();
let result = self.call(name, &args, depth + 1)?;
if let Some(dst) = dst {
values[*dst] = result.expect("verified i32 call");
}
}
Instr::Println { value } => self.output.push(values[*value]),
}
}
let Terminator::Return(value) = f.block.terminator;
Ok(value.map(|v| values[v]))
}
}
pub fn display(program: &IrProgram) -> String {
let mut text = String::new();
for f in &program.functions {
text.push_str(&format!("fn {}({:?}):\nbb0:\n", f.name, f.params));
for item in &f.block.instrs {
let line = match &item.instr {
Instr::Const { dst, value } => format!("%{dst} = const {value}"),
Instr::LoadLocal { dst, local } => format!("%{dst} = load #{}", local.0),
Instr::StoreLocal { local, src } => format!("store #{}, %{src}", local.0),
Instr::Binary {
dst,
op,
left,
right,
} => format!(
"%{dst} = {} %{left}, %{right}",
format!("{op:?}").to_lowercase()
),
Instr::Call { dst, name, args } => format!(
"{}call {name}({})",
dst.map_or(String::new(), |d| format!("%{d} = ")),
args.iter()
.map(|a| format!("%{a}"))
.collect::<Vec<_>>()
.join(", ")
),
Instr::Println { value } => format!("println %{value}"),
};
text.push_str(&format!(" {line}\n"));
}
let Terminator::Return(value) = f.block.terminator;
text.push_str(&format!(
" return{}\n",
value.map_or(String::new(), |v| format!(" %{v}"))
));
}
text
}
}
#[allow(dead_code)]
mod backend {
use crate::ir::{Instr, IrFunction, IrProgram, Terminator};
use crate::semantics::SymbolId;
use crate::syntax::BinOp;
use std::collections::HashMap;
use std::fmt::Write as _;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Target {
Linux,
Macos,
}
impl Target {
pub fn host() -> Result<Self, String> {
if cfg!(target_os = "macos") {
Ok(Self::Macos)
} else if cfg!(all(target_os = "linux", target_arch = "x86_64")) {
Ok(Self::Linux)
} else {
Err("native builds require x86-64 Linux or macOS (Rosetta on Apple Silicon); use run for the portable IR runner".into())
}
}
fn symbol(self, name: &str) -> String {
match self {
Self::Linux => name.to_owned(),
Self::Macos => format!("_{name}"),
}
}
}
struct Frame {
locals: HashMap<SymbolId, usize>,
value_base: usize,
size: usize,
}
impl Frame {
fn new(f: &IrFunction) -> Self {
let mut locals = HashMap::new();
for local in f
.params
.iter()
.copied()
.chain(f.block.instrs.iter().filter_map(|i| match i.instr {
Instr::StoreLocal { local, .. } => Some(local),
_ => None,
}))
{
let offset = (locals.len() + 1) * 4;
locals.entry(local).or_insert(offset);
}
let value_base = locals.len() * 4;
let size = (value_base + f.value_count * 4).div_ceil(16) * 16;
Self {
locals,
value_base,
size,
}
}
fn value(&self, id: usize) -> usize {
self.value_base + (id + 1) * 4
}
}
pub fn assembly(program: &IrProgram, target: Target) -> String {
let mut out = String::from(".intel_syntax noprefix\n.text\n");
let regs = ["edi", "esi", "edx", "ecx", "r8d", "r9d"];
// Keep the C process entry separate from Rust's unit-valued main.
let main = target.symbol("main");
let entry = target.symbol("mr_main");
writeln!(out, ".globl {main}\n{main}:\n push rbp\n mov rbp, rsp\n call {entry}\n xor eax, eax\n pop rbp\n ret").unwrap();
for (index, f) in program.functions.iter().enumerate() {
let name = target.symbol(&format!("mr_{}", f.name));
let frame = Frame::new(f);
let trap = format!("L_microrust_trap_{index}");
writeln!(
out,
".globl {name}\n{name}:\n push rbp\n mov rbp, rsp\n sub rsp, {}",
frame.size
)
.unwrap();
for (param, reg) in f.params.iter().zip(regs) {
writeln!(
out,
" mov DWORD PTR [rbp - {}], {reg}",
frame.locals[param]
)
.unwrap();
}
for item in &f.block.instrs {
match &item.instr {
Instr::Const { dst, value } => {
writeln!(
out,
" mov DWORD PTR [rbp - {}], {value}",
frame.value(*dst)
)
.unwrap();
}
Instr::LoadLocal { dst, local } => {
writeln!(
out,
" mov eax, DWORD PTR [rbp - {}]\n mov DWORD PTR [rbp - {}], eax",
frame.locals[local],
frame.value(*dst)
)
.unwrap();
}
Instr::StoreLocal { local, src } => {
writeln!(
out,
" mov eax, DWORD PTR [rbp - {}]\n mov DWORD PTR [rbp - {}], eax",
frame.value(*src),
frame.locals[local]
)
.unwrap();
}
Instr::Binary {
dst,
op,
left,
right,
} => {
writeln!(out, " mov eax, DWORD PTR [rbp - {}]", frame.value(*left))
.unwrap();
match op {
BinOp::Div => {
// Guard both idiv traps so failure follows the same runtime path.
writeln!(out, " mov ecx, DWORD PTR [rbp - {}]\n test ecx, ecx\n jz {trap}\n cmp eax, -2147483648\n jne L_div_ok_{index}_{dst}\n cmp ecx, -1\n je {trap}\nL_div_ok_{index}_{dst}:\n cdq\n idiv ecx", frame.value(*right)).unwrap();
}
_ => {
let instruction = match op {
BinOp::Add => "add",
BinOp::Sub => "sub",
BinOp::Mul => "imul",
BinOp::Div => unreachable!(),
};
writeln!(
out,
" {instruction} eax, DWORD PTR [rbp - {}]\n jo {trap}",
frame.value(*right)
)
.unwrap();
}
}
writeln!(out, " mov DWORD PTR [rbp - {}], eax", frame.value(*dst))
.unwrap();
}
Instr::Call { dst, name, args } => {
for (arg, reg) in args.iter().zip(regs) {
writeln!(
out,
" mov {reg}, DWORD PTR [rbp - {}]",
frame.value(*arg)
)
.unwrap();
}
writeln!(out, " call {}", target.symbol(&format!("mr_{name}"))).unwrap();
if let Some(dst) = dst {
writeln!(out, " mov DWORD PTR [rbp - {}], eax", frame.value(*dst))
.unwrap();
}
}
Instr::Println { value } => {
writeln!(
out,
" mov edi, DWORD PTR [rbp - {}]\n call {}",
frame.value(*value),
target.symbol("microrust_print_i32")
)
.unwrap();
}
}
}
let Terminator::Return(value) = f.block.terminator;
if let Some(value) = value {
writeln!(out, " mov eax, DWORD PTR [rbp - {}]", frame.value(value)).unwrap();
}
writeln!(
out,
" mov rsp, rbp\n pop rbp\n ret\n{trap}:\n call {}\n ud2",
target.symbol("microrust_trap")
)
.unwrap();
}
if matches!(target, Target::Linux) {
out.push_str(".section .note.GNU-stack,\"\",@progbits\n");
}
out
}
}
fn expression(expr: &syntax::Expr) -> String {
use syntax::ExprKind;
match &expr.kind {
ExprKind::Int(value) => value.to_string(),
ExprKind::Name(name) => name.clone(),
ExprKind::Binary { op, left, right } => {
let symbol = match op {
syntax::BinOp::Add => "+",
syntax::BinOp::Sub => "-",
syntax::BinOp::Mul => "*",
syntax::BinOp::Div => "/",
};
format!("({} {symbol} {})", expression(left), expression(right))
}
ExprKind::Call { callee, args } => {
let args = args.iter().map(expression).collect::<Vec<_>>().join(", ");
format!("{callee}({args})")
}
ExprKind::Println { value } => format!("println({})", expression(value)),
ExprKind::Block(block) => format!("{{ {} }}", statements(block).join(" ")),
}
}
fn statements(block: &syntax::Block) -> Vec<String> {
let mut lines = Vec::new();
for statement in &block.statements {
let line = match statement {
syntax::Stmt::Let { name, value, .. } => {
format!("let {name}: i32 = {};", expression(value))
}
syntax::Stmt::Return { value, .. } => match value {
Some(value) => format!("return {};", expression(value)),
None => "return;".into(),
},
syntax::Stmt::Expr(value) => format!("{};", expression(value)),
};
lines.push(line);
}
if let Some(tail) = &block.tail {
lines.push(format!("tail {}", expression(tail)));
}
lines
}
fn print_tree(program: &syntax::Program) {
for function in &program.functions {
let params = function
.params
.iter()
.map(|param| format!("{}: i32", param.name))
.collect::<Vec<_>>()
.join(", ");
println!(
"fn {}({params}) -> {:?}",
function.name, function.return_type
);
for line in statements(&function.body) {
println!(" {line}");
}
}
}
fn main() {
if let Err(error) = run() {
eprintln!("{error}");
std::process::exit(1);
}
}
fn run() -> Result<(), String> {
const USAGE: &str = "usage: microrustc <tokens|ast|resolve|check|ir|run|asm> FILE [--no-opt] [-o OUTPUT] [--target linux|macos]";
let mut args = std::env::args().skip(1);
let mode = args.next().ok_or(USAGE)?;
if !["tokens", "ast", "resolve", "check", "ir", "run", "asm"].contains(&mode.as_str()) {
return Err(USAGE.into());
}
let mut path = None;
let mut output = None;
let mut target = None;
let mut optimize = true;
while let Some(arg) = args.next() {
match arg.as_str() {
"--no-opt" if matches!(mode.as_str(), "ir" | "run" | "asm") => optimize = false,
"-o" if matches!(mode.as_str(), "asm") => {
output = Some(args.next().ok_or("missing output path")?);
}
"--target" if matches!(mode.as_str(), "asm") => {
target = Some(match args.next().as_deref() {
Some("linux") => backend::Target::Linux,
Some("macos") => backend::Target::Macos,
_ => return Err("expected linux or macos".into()),
});
}
_ if arg.starts_with('-') => return Err(format!("unknown option {arg}")),
_ if path.is_none() => path = Some(arg),
_ => return Err("more than one source file".into()),
}
}
let path = path.ok_or(USAGE)?;
let source = std::fs::read_to_string(&path).map_err(|error| format!("{path}: {error}"))?;
let render = |error: Error| error.render(&path, &source);
let tokens = syntax::lex(&source).map_err(render)?;
if mode == "tokens" {
print_tokens(&tokens);
return Ok(());
}
let ast = syntax::Parser::new(tokens).parse().map_err(render)?;
if mode == "ast" {
print_tree(&ast);
return Ok(());
}
let resolved = semantics::resolve(ast).map_err(render)?;
if mode == "resolve" {
print_symbols(&resolved);
return Ok(());
}
let typed = semantics::type_check(resolved).map_err(render)?;
if mode == "check" {
println!("checked {path}");
return Ok(());
}
let mut program = ir::lower(&typed);
ir::verify(&program).map_err(render)?;
if optimize {
ir::optimize(&mut program);
ir::verify(&program).map_err(render)?;
}
match mode.as_str() {
"ir" => print!("{}", ir::display(&program)),
"run" => {
for value in ir::execute(&program).map_err(render)? {
println!("{value}");
}
}
"asm" => {
let target = target.map_or_else(backend::Target::host, Ok)?;
let assembly = backend::assembly(&program, target);
if let Some(output) = output {
std::fs::write(&output, assembly).map_err(|e| e.to_string())?;
println!("wrote {output}");
} else {
print!("{assembly}");
}
}
_ => unreachable!(),
}
Ok(())
}
fn print_tokens(tokens: &[syntax::Token]) {
for token in tokens {
println!(
"{:?} {:?} {}..{}",
token.kind, token.lexeme, token.span.start, token.span.end
);
}
}
fn print_symbols(program: &semantics::ResolvedProgram) {
for (index, symbol) in program.symbols.iter().enumerate() {
println!("#{index} {:?} {}", symbol.kind, symbol.name);
}
}The new backend module contains the target names, stack-frame layout, and instruction emitter. asm receives the IR produced by our existing pipeline. -o writes the assembly to a file; without it, the command prints the assembly.
Keep the same canonical input in example.mrs:
fn add(a: i32, b: i32) -> i32 {
return a + b;
}
fn main() {
let x: i32 = 5 + 3;
let y: i32 = x * 2;
let result: i32 = add(x, y);
println!("{}", result);
}From the parent of your microrust folder, run these commands. If you're already inside microrust, omit the first line:
cd microrust
rustc main.rs -o microrustc
./microrustc asm example.mrs --target linux -o example.s
./microrustc run example.mrsThe expected output is:
wrote example.s
24Open example.s and find mr_add, mr_main, and the call to microrust_print_i32. This command deliberately uses Linux spelling so it matches the assembly discussed above. --target macos produces the leading underscores required by the macOS assembler. Both choices still target x86-64.
The 24 above comes from the IR runner. The assembly file hasn't been executed. Try ./microrustc asm example.mrs --target linux --no-opt -o unoptimized.s and compare the two files. The unoptimized version should retain more arithmetic in main, while both versions still have to follow the calling convention.
All earlier inspection commands remain available. If a load or call looks wrong in assembly, ./microrustc ir example.mrs --no-opt gives us the instructions that reached the backend.
The emitted text still contains symbolic references and unknown addresses. An assembler will encode the instructions, but some references must wait for linking. We'll inspect how those are recorded in object files and relocation.