Lowering Expressions Into IR
Our AST still resembles the source we parsed. That's convenient for checking declarations and expressions, but code generation needs operations with explicit inputs, results, and execution order.
Lowering translates the tree into an intermediate representation, or IR: a simpler form owned by the compiler. For let y: i32 = x * 2;, it records steps closer to "load x, multiply by 2, store in y." I find this easier to inspect between phases, and each operation can be transformed separately.
Why this phase matters
An IR separates the backend from source syntax. Optimizers can work on values regardless of whether they came from a let binding, a block expression, or an expanded macro. Code generation then handles the IR's operations without needing to understand parser decisions.
Production compilers often use several IRs. After parsing and macro expansion, rustc builds HIR (High-level Intermediate Representation), a simplified version of the source tree that still resembles Rust. Later, MIR (Mid-level Intermediate Representation) expresses function bodies as simpler operations with explicit paths between them. This helps the compiler check how values and references are used, including whether borrowing rules are respected.
The default backend uses LLVM, a toolkit for optimizing code and generating machine instructions. LLVM IR is the lower-level representation passed to that toolkit. It describes operations such as arithmetic and memory access, with their types made explicit. LLVM optimizes this form before producing machine code.
Java compilers and CPython, the standard Python implementation, produce bytecode: instructions for a virtual machine, a program that executes them. Java bytecode also provides a portable execution format. JavaScript engines may use several internal forms as runtime profiling supplies more information about how a program behaves while running.
We'll use one IR in MicroRust, keeping it readable enough to inspect between passes.
What we are building here
We'll add an ir module inside the same main.rs. The driver calls ir::lower with the TypedProgram from the previous phase. The source has already passed scanning, parsing, resolution, and type checking before we reach this function.
We are lowering the typed AST from semantic analysis into a small three-address-code style IR. Three-address code means most instructions have at most two inputs and one output:
t0 = 5 + 3
x = t0The "three addresses" are the result and two operands. We'll name temporary values %0, %1, and so on, and give source locals their own storage slots.
Our IR has functions, basic blocks, and instructions. With no branches, each function stores exactly one block:
#[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,
}A basic block is a straight-line sequence with one entry and one normal exit, recorded by its terminator. Ordinary control flow cannot enter or leave in the middle. Checked arithmetic can still stop the process; we don't model recoverable exception edges. With no if or while, each MicroRust function needs only one block, ending in a return.
The instruction set is small:
#[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>),
}SSA, or static single assignment, gives every variable name in the IR exactly one assignment. When execution paths meet, a phi node selects the value coming from whichever path was taken and gives the result a new name. For example, if one branch produces 3 and another produces 7, the phi node carries forward the value from the branch that ran.
Making data flow explicit this way helps many optimizations. Our IR borrows the idea of assigning temporaries once, but keeps user locals in separate storage rather than converting the whole function to SSA.
Lowering an i32 expression produces a value ID. This binary-expression arm in Lowerer::expr evaluates the left operand before the right:
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,
}
}The containing method emits this instruction and returns its destination. Its return type is Option<ValueId> because unit expressions produce no integer. A separate terminator field records an early return, so absence of a value alone does not confuse unit with an exited function. Unit calls use Call { dst: None, .. }, and block expressions lower their statements followed by their tail.
Take this small snippet:
fn main() {
let z: i32 = (1 + 2) * (3 + 4);
println!("{}", z);
}The AST naturally nests the arithmetic. The IR flattens it:
fn main:
bb0:
%0 = const 1
%1 = const 2
%2 = add %0, %1
%3 = const 3
%4 = const 4
%5 = add %3, %4
%6 = mul %2, %5
store z, %6
%7 = load z
println %7
returnThe additions now have named results that feed the multiply. The optimizer and backend can handle these recurring instruction forms without walking a nested expression.
The statement-lowering loop handles an explicit return with this arm:
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));
}
}If lowering the return expression itself has already returned from a nested block, we preserve that first terminator. Otherwise this arm records the enclosing return. The loop stops emitting instructions once a terminator exists. Instructions after it would be unreachable in that block. Adding if would require conditional branch terminators, while while would introduce back edges. Those connections between basic blocks form a control-flow graph, or CFG.
A CFG represents possible execution paths, using basic blocks as nodes and jumps as edges. Our current functions have a particularly simple graph:
bb0 -> returnThere's only one block here, with a return at its exit. Later passes can use this representation even though we don't yet need branches.
If we later add if, the shape changes quickly:
fn choose(flag: bool) -> i32 {
if flag {
return 1;
}
return 2;
}This is valid Rust, but its boolean parameter and if are outside MicroRust. A lowered graph would have an entry block, blocks for the branches, and terminators connecting them. At a join, an SSA phi node selects a value based on which block led to the join. We won't implement phi nodes, but they help explain why control-flow analysis often needs a graph rather than a tree.
The canonical add function lowers cleanly:
fn add(a, b):
bb0:
%0 = load a
%1 = load b
%2 = add %0, %1
return %2And main becomes:
fn main:
bb0:
%0 = const 5
%1 = const 3
%2 = add %0, %1
store x, %2
%3 = load x
%4 = const 2
%5 = mul %3, %4
store y, %5
%6 = load x
%7 = load y
%8 = call add(%6, %7)
store result, %8
%9 = load result
println %9
returnThe AST's Stmt::Let represents a source let declaration. In the IR, storage and values handle its effect, so we don't need a separate Let instruction. Parentheses can disappear too: once parsing has established the grouping, they have no runtime meaning to preserve.
We retain source spans so a diagnostic, such as division by zero, can point to the original expression. Production compilers carry source and debug information through transformations too. Our IR runner uses these spans; the native backend doesn't yet emit debug information:
#[derive(Debug, Clone)]
pub struct SpannedInstr {
pub instr: Instr,
pub span: Span,
}Each instruction keeps its span alongside its lowered operation.
We allocate temporaries in traversal order, giving the same typed AST the same instruction order. This keeps tests and examples stable without instruction scheduling. Larger compilers may tolerate some internal nondeterminism, though caching and reproducible builds benefit from predictable output.
This IR is closer to what the backend needs, though it still has unlimited temporaries, abstract locals, and symbolic function names. Choosing registers and machine instructions will be a separate step.
C compilers commonly lower early into forms that expose operations and control flow. Java bytecode uses a stack, with expressions becoming pushes and operations; Python bytecode does the same for a dynamic runtime. JavaScript engines often begin with AST-like forms and lower into typed or untyped IR depending on the optimization tier. The choice of representation reflects the work each implementation needs to do next.
We can test lowering before involving the backend: let x: i32 = 5 + 3; should produce const, const, add, and store. Printed IR also lets us compare a block before and after a transformation. I find that easier than reconstructing what happened from an object file; larger compilers provide intermediate dumps for the same reason.
Run this version
Keep the existing frontend in main.rs and add the ir module below. This version also includes a small IR runner. I want to be able to execute the instructions we have just built before asking a machine-code backend to translate them.
Our source files stay in the same folder:
microrust/
|-- main.rs
`-- example.mrsReplace main.rs with the complete listing. It already contains the earlier phases. Keep any golden.mrs file beside it; there is no new chapter directory to create.
main.rs: compiler through IR lowering
// Chapter 06: add IR lowering and execution.
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 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 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
}
}
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> FILE";
let mut args = std::env::args().skip(1);
let mode = args.next().ok_or(USAGE)?;
if !["tokens", "ast", "resolve", "check", "ir", "run"].contains(&mode.as_str()) {
return Err(USAGE.into());
}
let path = args.next().ok_or(USAGE)?;
if args.next().is_some() {
return Err(USAGE.into());
}
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 program = ir::lower(&typed);
ir::verify(&program).map_err(render)?;
if mode == "ir" {
print!("{}", ir::display(&program));
} else {
for value in ir::execute(&program).map_err(render)? {
println!("{value}");
}
}
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 part begins at mod ir. lower walks the checked tree, verify checks the resulting instruction references, and display prints them. run interprets those same instructions. The checked arithmetic helper on BinOp is shared with the optimizer we'll add next.
Use the same canonical program 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);
}Rebuild the compiler, inspect its IR, then run that IR. Start in the folder containing microrust, or skip cd if you're already inside it:
cd microrust
rustc main.rs -o microrustc
./microrustc ir example.mrs
./microrustc run example.mrsThe output should be:
fn add([SymbolId(2), SymbolId(3)]):
bb0:
%0 = load #2
%1 = load #3
%2 = add %0, %1
return %2
fn main([]):
bb0:
%0 = const 5
%1 = const 3
%2 = add %0, %1
store #4, %2
%3 = load #4
%4 = const 2
%5 = mul %3, %4
store #5, %5
%6 = load #4
%7 = load #5
%8 = call add(%6, %7)
store #6, %8
%9 = load #6
println %9
return
24The local IDs agree with the resolver: #4 is x, #5 is y, and #6 is result. The % names belong to temporary values within each function. After the IR dump, 24 comes from the separate run command.
This is the first version that can execute our MicroRust program. It does so by interpreting IR on the host, not by generating native instructions. The runner has a 256-call-depth limit and a one-million-instruction limit. It buffers printed integers until the run succeeds, so a failing run doesn't reproduce the output timing of the native program we'll build later.
Try the nested arithmetic example earlier in this chapter; its result should be 21. Also try a return inside a block expression. The IR should stop at that return instead of emitting later instructions. The earlier tokens, ast, resolve, and check commands are still available when you need to trace a problem back through the compiler.
We can now inspect and run the lowered program. Its 5 + 3 still takes several instructions, even though both operands are known. In optimization, we'll compute that result before the program runs.