ir-lang 2.0.0-alpha.3

The model

• A Module declares functions (with a Signature and a calling-convention tag, a linkage, and attributes), globals with initializers and relocations, and aggregates (structs, packed structs, arrays) with C layout.
• A Function body is blocks of instructions ended by one terminator. Values cross edges as block arguments.
• A Builder lowers into a body and rewrites it. Every instruction is type-checked as it is added. Mutable locals lower through variables (declare_var / def_var / use_var / seal_block); GC references can be used freely and insert_statepoints relocates them.
• Module::validate checks everything; Display and parse are the textual form.
• interp (feature interp) runs it.

What it guarantees, and how each guarantee is checked:

Installation

[dependencies]
ir-lang = "2.0.0-alpha.3"

With the reference interpreter:

[dependencies]
ir-lang = { version = "2.0.0-alpha.3", features = ["interp"] }

Without the standard library:

[dependencies]
ir-lang = { version = "2.0.0-alpha.3", default-features = false }

Quick start

Build, validate, print, and parse back fn add1(x: i64) -> i64 { x + 1 }:

use ir_lang::{Linkage, Module, Overflow, Signature, Type};

let mut m = Module::new("demo");
let f = m.declare_function("add1", &Signature::new(&[Type::I64], &[Type::I64]), Linkage::Export)?;
let mut b = m.build(f)?;
let x = b.param(0)?;
let one = b.iconst(Type::I64, 1)?;
let y = b.add(x, one, Overflow::Wrap)?;
b.ret(&[y])?;

m.validate()?;
assert_eq!(
    m.to_string(),
    "module \"demo\" ptr64\nsig s0 = (i64) -> (i64) fast\n\nfunc @add1 s0 export {\nb0(v0: i64):\n    v1: i64 = const 1\n    v2: i64 = add<overflow=wrap> v0, v1\n    ret v2\n}\n"
);
assert_eq!(ir_lang::parse(&m.to_string())?.to_string(), m.to_string());
# Ok::<(), Box<dyn std::error::Error>>(())

Errors and exceptions are edges

An operation whose policy is error is a check terminator with an error edge carrying the OPS error code; a call that may throw is an invoke with a landing pad:

use ir_lang::{BinaryOp, BlockArg, BlockCall, Call, InstData, Linkage, Module, Overflow, Policy, Signature, Type};

let mut m = Module::new("demo");
let may_throw = m.declare_function("may_throw", &Signature::new(&[], &[Type::I32]), Linkage::Import)?;
let f = m.declare_function("f", &Signature::new(&[Type::I32], &[Type::I32]), Linkage::Export)?;
let mut b = m.build(f)?;
let x = b.param(0)?;
let got = b.create_block(&[Type::I32])?;
let pad = b.create_block(&[Type::Ptr])?;
b.invoke(
    Call::direct(may_throw, &[]),
    BlockCall::with_args(got, &[BlockArg::Result(0)]),
    BlockCall::with_args(pad, &[BlockArg::Exception]),
)?;

b.switch_to(got)?;
let y = b.block_param(got, 0)?;
let sum = b.create_block(&[Type::I32])?;
let overflow = b.create_block(&[Type::U32])?;
b.check(
    InstData::Binary { op: BinaryOp::Add, policy: Policy::overflow(Overflow::Error), args: [x, y] },
    BlockCall::with_args(sum, &[BlockArg::Result(0)]),
    BlockCall::with_args(overflow, &[BlockArg::ErrorCode]),
)?;
b.switch_to(sum)?;
let s = b.block_param(sum, 0)?;
b.ret(&[s])?;
b.switch_to(overflow)?;
b.trap(1)?;
b.switch_to(pad)?;
let exn = b.block_param(pad, 0)?;
b.resume(exn)?;

m.validate()?;
# Ok::<(), Box<dyn std::error::Error>>(())

Mutable locals and GC references

A front end names its mutable locals with variables and lets the builder place the block parameters; it keeps GC references in ordinary values across calls and lets insert_statepoints relocate them:

use ir_lang::{Call, CmpOp, Linkage, Module, Signature, Type};

// fn keep(r: ref, n: i64) -> ref { let mut x = r; let mut i = 0; while i < n { poll(); i += 1 } x }
let mut m = Module::new("demo");
let poll = m.declare_function("poll", &Signature::new(&[], &[]), Linkage::Import)?;
let f = m.declare_function("keep", &Signature::new(&[Type::Ref, Type::I64], &[Type::Ref]), Linkage::Export)?;
let mut b = m.build(f)?;
let (x, i) = (b.declare_var(Type::Ref)?, b.declare_var(Type::I64)?);
let (r, n) = (b.param(0)?, b.param(1)?);
b.def_var(x, r)?;
let zero = b.iconst(Type::I64, 0)?;
b.def_var(i, zero)?;
let (head, body, exit) = (b.create_block(&[])?, b.create_block(&[])?, b.create_block(&[])?);
b.jump(head, &[])?;
b.switch_to(head)?;
let iv = b.use_var(i)?;
let more = b.compare(CmpOp::Lt, iv, n)?;
b.branch(more, body, &[], exit, &[])?;
b.switch_to(body)?;
b.seal_block(body)?;
b.call(Call::direct(poll, &[]))?; // a safepoint; `x` is live across it
let iv = b.use_var(i)?;
let one = b.iconst(Type::I64, 1)?;
let i2 = b.add(iv, one, ir_lang::Overflow::Wrap)?;
b.def_var(i, i2)?;
b.jump(head, &[])?;
b.seal_block(head)?;
b.switch_to(exit)?;
b.seal_block(exit)?;
let xv = b.use_var(x)?;
b.ret(&[xv])?;
b.seal_all_blocks()?;

assert!(b.validate().is_err()); // `x` is used after the poll without relocation
let stats = b.insert_statepoints()?;
assert_eq!(stats.relocations, 1);
m.validate()?;
# Ok::<(), Box<dyn std::error::Error>>(())

Running it

With the interp feature, the reference interpreter runs a module with the exact operation semantics:

# #[cfg(feature = "interp")] {
use ir_lang::interp::{self, Outcome, Val};
use ir_lang::{Linkage, Module, Overflow, Signature, Type};

let mut m = Module::new("demo");
let f = m.declare_function("add1", &Signature::new(&[Type::I64], &[Type::I64]), Linkage::Export)?;
let mut b = m.build(f)?;
let x = b.param(0)?;
let one = b.iconst(Type::I64, 1)?;
let y = b.add(x, one, Overflow::Trap)?;
b.ret(&[y])?;

assert_eq!(interp::run(&m, f, &[Val::i64(41)])?, Outcome::Return(vec![Val::i64(42)]));
assert_eq!(interp::run(&m, f, &[Val::i64(i64::MAX)])?, Outcome::Trap(1)); // E0001
# }
# Ok::<(), Box<dyn std::error::Error>>(())

More in examples/: lower (a front end's tree into IR), rewrite (a folding pass with the rewrite API), run (the interpreter).

Performance

Measured with cargo bench (criterion) on the development machine (Windows, x86-64), library only. Throughput scales linearly from 100k to 1M instructions.

New in 2.0.0-alpha.2, measured while other builds shared the machine (the unchanged safepoint validation above varied between 11 and 40 ms in the same session, so read these as upper bounds):

The textual form is for tests and debugging; nothing on the compile path parses text.

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.