Linking MicroRust Into an Executable
Our program's object file calls microrust_print_i32 without containing its implementation. The assembler records a relocation, and the linker must find a definition of microrust_print_i32 among the objects and libraries it receives. If it can't, the build fails with an undefined-symbol error.
Linking combines those separately compiled pieces. It resolves symbols, assigns final addresses, and applies relocations to create an executable the operating system loader can use.
Why this phase matters
Even this small program needs runtime helpers and startup code. Larger builds may also include generated code and libraries from several languages. The linker combines them according to the platform's conventions.
Linking also lets us combine code written in different languages. Rust can call C through FFI, C can call assembly, and MicroRust can use a C helper for printing. The object files must expose the right symbols and agree on the ABI, or application binary interface. That includes calling conventions, data layout, and symbol visibility.
Rust builds also involve crate metadata, rlibs, static and dynamic libraries, system libraries, panic runtimes, allocators, and procedural macro artifacts. Here we need a runtime object that defines microrust_print_i32 for our generated object to call.
What we are building here
We are adding a final driver step after object file generation. The compiler emits assembly. The assembler produces main.o. A small runtime source file produces runtime.o. The linker combines them into an executable.
We'll add a build command to microrustc. It runs the frontend and IR passes, then asks the backend to assemble and link their output. The compiler stays in main.rs; the C runtime supplies helpers for the generated program.
Our tiny runtime helper is written in C:
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
void microrust_print_i32(int32_t value) {
printf("%" PRId32 "\n", value);
}The generated MicroRust assembly calls it:
mov edi, DWORD PTR [rbp - 12]
call microrust_print_i32The object file for the MicroRust program has an undefined symbol:
undefined:
microrust_print_i32The runtime object defines it:
defined:
microrust_print_i32The linker matches the undefined reference to the runtime's definition, then patches the call site using the helper's final address.
To examine an ordinary external call without adding another language feature, we can use two C translation units. The companion keeps this test in fixtures/linking/. The first defines the helper:
// helper.c
int add_one(int x) {
return x + 1;
}The second contains its caller and a declaration of the helper's signature:
#include <stdio.h>
int add_one(int x);
int main(void) {
printf("%d\n", add_one(41));
return 0;
}The declaration lets C type-check the call to add_one. MicroRust has no equivalent syntax, so we can't split its source functions this way. The linker resolves the C call when both objects are supplied. Without the helper object, it reports something like:
undefined reference to `add_one`The missing definition is discovered at link time because each unit was compiled independently. A valid call in one unit doesn't establish that the build will supply its implementation.
Static linking includes needed library code in the executable. Dynamic linking leaves references to shared libraries, resolved at startup or later. Static executables can be more self-contained. Shared libraries can save disk and memory and allow updates without rebuilding every caller, but they introduce search-path and version-compatibility concerns.
MicroRust's runtime helper can be linked statically by compiling runtime.c into an object and passing it directly:
cc main.o runtime.o -o mainThis links the helper's code directly into the executable. It does not make the entire program statically linked: printf will usually still come from a shared C library. On macOS both input objects must be x86-64 and the final driver also needs -arch x86_64.
Making runtime a shared library would give the executable a dynamic dependency, and the link command would name that library. Passing the object directly is sufficient for our build.
Link order can matter for static archives. A linker often scans libraries left to right, extracting archive members only when they satisfy a symbol already seen as unresolved. That explains the order in a command such as:
cc main.o -lmThe math library follows main.o, allowing its definitions to satisfy that object's references. Some linkers may fail if -lm comes first. Build systems usually arrange the order. MicroRust passes plain objects, so archive extraction isn't involved here.
Java avoids native linking for ordinary application code by targeting the JVM, where symbolic references are resolved by class loading and verification. Python and Ruby load modules dynamically with their runtime's import mechanisms, though native extension modules still meet the system linker. JavaScript in browsers has a very different deployment model, but WebAssembly brings linking concepts back under another name: imports, exports, modules, and instantiation.
Cargo handles the linker invocation for ordinary Rust builds. When calling between Rust and C, we still need to specify the ABI: extern "C" tells Rust which calling convention to use at that boundary.
The companion's driver performs the final steps in a unique temporary directory:
pub fn build_executable(program: &IrProgram, output: &Path, target: Target) -> Result<(), String> {
let work = WorkDir::new()?;
let asm = work.0.join("main.s");
let object = work.0.join("main.o");
let runtime = work.0.join("runtime.c");
let runtime_object = work.0.join("runtime.o");
std::fs::write(&asm, assembly(program, target)).map_err(|e| e.to_string())?;
std::fs::write(&runtime, RUNTIME).map_err(|e| e.to_string())?;
assemble(&asm, &object, target)?;
run(target
.cc()
.arg("-std=c11")
.arg("-c")
.arg(&runtime)
.arg("-o")
.arg(&runtime_object))?;
link(&object, &runtime_object, output, target)
}The driver passes paths as arguments without constructing shell commands, includes stderr on failure, and cleans up temporary files when the build scope ends. This keeps an old main.o from confusing a later test. Using the platform toolchain also gives us its handling of object formats, startup files, and system libraries, as it does for many production compilers.
Before Rust's main runs, platform startup code initializes process state, prepares arguments and the environment, and performs runtime setup. The linker includes startup objects defining the entry symbol, often something like _start, that eventually calls main.
Our generated main wrapper uses the C ABI, calls the unit-valued mr_main, and returns zero to the platform runtime. Using cc as the final driver supplies the expected startup files and standard libraries. Invoking the linker directly would make those inputs our responsibility too, including the details needed for the program to start and exit correctly.
The executable records the layout of main, mr_add, and microrust_print_i32 for the loader. On a supported host, it can run our canonical program:
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);
}The repository tests compare this program with rustc, the portable IR runner, and native executables built both with and without optimization. All should exit successfully and print:
24That is the expected result after translating our arithmetic, bindings, calls, and output. Ownership, borrowing, patterns, traits, generics, and modules remain outside the language; println! is still a special case. We also lack production diagnostics, incremental compilation, cross-crate metadata, and a substantial optimizer. We do now have a build that shows where the runtime and linker fit.
With dynamic linking, a linked executable may still have entries for the dynamic loader to resolve at startup. The loader maps shared libraries, applies dynamic relocations, and resolves imports according to platform rules before transferring control to startup code. Lazy binding can defer some symbol resolution until the first call.
Including the runtime object directly avoids a shared-library dependency for that helper. Other dynamic dependencies can still prevent a program from running on another machine if a library is missing, incompatible, or exports different symbols. This is where toolchains also depend on loaders, package systems, and operating systems.
Link-time optimization, or LTO, keeps IR available across compilation units late in the build. That allows inlining and dead code removal across file or crate boundaries, at the cost of a more involved final build. Without it, the compiler processing main may not have add_one's body to inspect. The linker can find the machine-code definition without having enough information to fold the call. We won't implement LTO here.
Library authors need stable binary interfaces, while application authors weigh build time against runtime speed. Both work within the operating system's loader and security requirements. The file formats and linker flags we've used are part of that agreement. For our own build, an undefined-symbol error gives us a starting question: which object should provide the missing definition?
Run this version
This is the final version of main.rs. It keeps every earlier command and adds build, which emits assembly, creates the program object, compiles the runtime, and links the executable.
The C runtime is a raw string inside the Rust file. The driver writes it into its temporary build directory when needed. You don't need to create or copy a separate runtime.c to follow this version.
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: complete compiler with linking
// Chapter 10: add linking and the embedded runtime.
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 _;
use std::path::{Path, PathBuf};
use std::process::Command;
use std::sync::atomic::{AtomicU64, Ordering};
#[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}"),
}
}
fn cc(self) -> Command {
let mut cc = Command::new("cc");
if matches!(self, Self::Macos) {
cc.args(["-arch", "x86_64"]);
}
cc
}
}
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
}
pub const RUNTIME: &str = r#"#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
void microrust_print_i32(int32_t value) {
printf("%" PRId32 "\n", value);
}
_Noreturn void microrust_trap(void) {
fputs("MicroRust: integer overflow or division by zero\n", stderr);
exit(1);
}
"#;
fn run(command: &mut Command) -> Result<(), String> {
let output = command
.output()
.map_err(|e| format!("cannot run {command:?}: {e}"))?;
if output.status.success() {
Ok(())
} else {
Err(format!(
"{command:?} failed:\n{}",
String::from_utf8_lossy(&output.stderr)
))
}
}
static NEXT_DIR: AtomicU64 = AtomicU64::new(0);
pub struct WorkDir(pub PathBuf);
impl WorkDir {
pub fn new() -> Result<Self, String> {
for _ in 0..100 {
let path = std::env::temp_dir().join(format!(
"microrust-{}-{}",
std::process::id(),
NEXT_DIR.fetch_add(1, Ordering::Relaxed)
));
match std::fs::create_dir(&path) {
Ok(()) => return Ok(Self(path)),
Err(e) if e.kind() == std::io::ErrorKind::AlreadyExists => continue,
Err(e) => return Err(e.to_string()),
}
}
Err("cannot allocate build directory".into())
}
}
impl Drop for WorkDir {
fn drop(&mut self) {
let _ = std::fs::remove_dir_all(&self.0);
}
}
pub fn assemble(asm: &Path, object: &Path, target: Target) -> Result<(), String> {
run(target.cc().arg("-c").arg(asm).arg("-o").arg(object))
}
pub fn link(
object: &Path,
runtime: &Path,
output: &Path,
target: Target,
) -> Result<(), String> {
run(target.cc().arg(object).arg(runtime).arg("-o").arg(output))
}
pub fn build_executable(
program: &IrProgram,
output: &Path,
target: Target,
) -> Result<(), String> {
let work = WorkDir::new()?;
let asm = work.0.join("main.s");
let object = work.0.join("main.o");
let runtime = work.0.join("runtime.c");
let runtime_object = work.0.join("runtime.o");
std::fs::write(&asm, assembly(program, target)).map_err(|e| e.to_string())?;
std::fs::write(&runtime, RUNTIME).map_err(|e| e.to_string())?;
assemble(&asm, &object, target)?;
run(target
.cc()
.arg("-std=c11")
.arg("-c")
.arg(&runtime)
.arg("-o")
.arg(&runtime_object))?;
link(&object, &runtime_object, output, target)
}
pub fn build_object(program: &IrProgram, output: &Path, target: Target) -> Result<(), String> {
let work = WorkDir::new()?;
let asm = work.0.join("main.s");
std::fs::write(&asm, assembly(program, target)).map_err(|e| e.to_string())?;
assemble(&asm, output, target)
}
}
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|object|build> 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", "object", "build",
]
.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" | "object" | "build") => {
optimize = false
}
"-o" if matches!(mode.as_str(), "asm" | "object" | "build") => {
output = Some(args.next().ok_or("missing output path")?);
}
"--target" if matches!(mode.as_str(), "asm" | "object" | "build") => {
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}");
}
}
"object" | "build" => {
let target = target.map_or_else(backend::Target::host, Ok)?;
if target != backend::Target::host()? {
return Err("object files and executables require the host platform's target; use asm for other targets".into());
}
if mode == "build" {
let output = output.as_deref().unwrap_or("a.out");
backend::build_executable(&program, std::path::Path::new(output), target)?;
println!("built {output}");
} else {
let output = output.as_deref().unwrap_or("a.o");
backend::build_object(&program, std::path::Path::new(output), target)?;
println!("wrote {output}");
}
}
_ => 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 pieces are RUNTIME, link, and build_executable. The embedded runtime includes both integer printing and the arithmetic-failure helper used by our checked instructions. The compiler itself still builds with Rust's standard library alone; generating an executable also needs cc and the platform's development libraries.
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 build example.mrs -o example
./microrustc run example.mrsThe expected output is:
built example
24The build creates example, while run checks the same input through the IR interpreter. The printed 24 at this point is from that interpreter, not the newly linked program.
On x86-64 Linux or an Intel Mac, run the executable below. On Apple Silicon, executing our x86-64 target also requires Rosetta. If the shell reports Bad CPU type in executable, the link may have succeeded even though the host cannot execute this target. The IR runner remains useful, but its result is not verification of the native backend.
./exampleOn a supported execution host, it should exit successfully and print:
24For a second native check, rebuild with ./microrustc build example.mrs --no-opt -o example-unoptimized, then run ./example-unoptimized. It should also print 24. Compare with rustc -C overflow-checks=yes --crate-name example example.mrs -o example-rust followed by ./example-rust. All three use the same source file.
The earlier commands still work: tokens, ast, resolve, check, ir, run, asm, and object. Keep main.rs as your compiler source. The assembly, objects, and executables are outputs you can regenerate; none needs to be pasted back into the compiler.
Measuring the executable
We can now return to the 2,000 unused bindings from chapter 07. Keep that unused.mrs in the same folder and use the compiler we just rebuilt from this chapter's listing. If you skipped the earlier experiment, its short helper will recreate the input.
Build the same source twice, changing only the optimization switch. From inside microrust, run:
./microrustc build unused.mrs --no-opt -o unused-unoptimized
./microrustc build unused.mrs -o unused-optimized
ls -l unused-unoptimized unused-optimizedThe first two commands report which executable they built. In the ls -l listing, the size column gives bytes. On macOS 27.0.1, with Apple's Clang 21.0.0 toolchain assembling and linking our x86-64 output, I measured 53,792 bytes without optimization and 8,728 bytes with optimization.
Both builds use the same runtime and linker settings. The difference comes from removing the unused stores and constants before code generation. There is no arithmetic to fold in those declarations. The remaining executable still contains startup and runtime code, along with file-format information and alignment space. It won't shrink to the size of the few instructions left in our IR.
Your exact sizes may differ with the operating system and toolchain. I used ls -l because ls -lh rounds the values; du normally reports allocated disk space instead of the file's byte length. This input is deliberately large enough to make the reduction visible despite alignment. With a smaller example, fewer instructions might leave the total file size unchanged.
On a host that can execute our x86-64 output, check both binaries:
./unused-unoptimized
./unused-optimizedThe expected output is unchanged:
24
24The Mac used for the size measurement could link these files but could not execute them: its x86-64 probe reported Bad CPU type in executable. Both portable IR runs and the rustc reference printed 24 there.
I later ran the same experiment on Ubuntu x86-64 with GCC 13.3.0. The executables measured 57,160 bytes without optimization and 16,200 bytes with it; both printed 24. The native tests also passed for the canonical program, the other test inputs, and arithmetic failures, with and without optimization. That verifies the Linux output; execution of the macOS output remains a separate check.
There is another limit worth keeping separate. Our backend still reserves temporary stack slots using the original value count, even after instructions disappear. We have reduced generated code and executable size, but have not yet compacted all that stack storage. Smaller files, lower memory use, and faster execution are different measurements.
Our little compiler has reached a natural stopping point. We've followed the same small program from lexing through type checking and lowering to machine code and a linked executable. It's satisfying to see the pieces come together after working through them one at a time. Before we finish, let's look at rustc in the finale and see what we'd need to change or add to support more of Rust.