ir-lang 1.0.0

Intermediate representation and lowering from the AST.
Documentation

Installation

[dependencies]
ir-lang = "1.0"

Or from the terminal:

cargo add ir-lang

Usage

A front-end walks its own syntax tree and drives the Builder: a literal becomes a constant, an operator becomes an instruction, an if becomes two blocks and a branch, a join becomes a block parameter. The builder hands back a Value for every result, so SSA numbering is captured without tracking it by hand. When the function is built, validate confirms it is well-formed.

Lowering fn abs(x: int) -> int { if x < 0 { -x } else { x } }:

use ir_lang::{Builder, BinOp, Type, UnOp};

let mut b = Builder::new("abs", &[Type::Int], Type::Int);
let x = b.block_params(b.entry())[0];

// The merge point takes the result as a parameter.
let join = b.create_block(&[Type::Int]);
let neg_blk = b.create_block(&[]);
let pos_blk = b.create_block(&[]);

let zero = b.iconst(0);
let is_neg = b.bin(BinOp::Lt, x, zero);
b.branch(is_neg, neg_blk, &[], pos_blk, &[]);

b.switch_to(neg_blk);
let negated = b.un(UnOp::Neg, x);
b.jump(join, &[negated]);

b.switch_to(pos_blk);
b.jump(join, &[x]);

b.switch_to(join);
let result = b.block_params(join)[0];
b.ret(Some(result));

let func = b.finish();
assert!(func.validate().is_ok());

A function prints as a readable textual IR, which is handy in tests and when debugging a pass:

use ir_lang::{Builder, BinOp, Type};

let mut b = Builder::new("poly", &[Type::Int, Type::Int], Type::Int);
let a = b.block_params(b.entry())[0];
let c = b.block_params(b.entry())[1];
let sum = b.bin(BinOp::Add, a, c);
let diff = b.bin(BinOp::Sub, a, c);
let product = b.bin(BinOp::Mul, sum, diff);
b.ret(Some(product));

let text = b.finish().to_string();
assert!(text.contains("v4: int = mul v2, v3"));
assert!(text.contains("return v4"));

Construction does not check well-formedness as it goes; validate does, returning a defined error rather than panicking when the IR is wrong:

use ir_lang::{Builder, BinOp, Type, ValidationError};

// `int + bool` is not a valid operation.
let mut b = Builder::new("bad", &[Type::Int, Type::Bool], Type::Int);
let x = b.block_params(b.entry())[0];
let flag = b.block_params(b.entry())[1];
let oops = b.bin(BinOp::Add, x, flag);
b.ret(Some(oops));

assert!(matches!(
    b.finish().validate(),
    Err(ValidationError::TypeMismatch { .. })
));

See docs/API.md for the full reference, and examples/ for runnable demonstrations (cargo run --example lower_ast, cargo run --example validation).

How it works

A Function keeps its blocks and values in flat arenas addressed by dense Block and Value indices, so building and walking the IR is a linear pass over contiguous memory rather than a chase through pointers, and a pass can key a side table directly on a handle's index. Values cross control-flow joins as block parameters — a jump or branch passes one argument per target parameter — which keeps the representation flat and removes the bookkeeping of phi nodes.

validate is where correctness is enforced. It checks the structural rules (one terminator per block, branch targets that exist, argument counts and types that match the target parameters, a numeric or boolean operand where the operation requires it) and then the SSA dominance property: every use of a value is reached by its single definition. Dominators are computed with the Cooper–Harvey–Kennedy algorithm over the reachable graph, and the dominance check is a single linear walk of the dominator tree carrying one reused availability set — no per-block allocation. The reachability, dominator, and dominance walks all use an explicit stack, so a deeply nested function cannot overflow the call stack.

Status

v1.0.0 is the stable release: the public API is frozen and follows Semantic Versioning, with no breaking changes before 2.0. The surface is the IR core — the Function SSA control-flow graph, the Builder lowering interface, the textual Display, and validate — and the crate is self-contained: it defines its own machine-level Type and is driven entirely through the builder, so it pulls in no first-party dependency; a front-end maps its own AST and source types onto the IR. Every core invariant is property-tested against generated programs, the dominator and dominance algorithms were fuzzed against a brute-force reference, and the suite is verified on Linux, macOS, and Windows. See the SemVer promise.

Contributing

See dev/DIRECTIVES.md for engineering standards and the definition of done. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.