opt-lang 0.3.0

The model

One call optimizes a module; everything else is for callers who want control:

• optimize runs the default pipeline on every function with a body (Tier 1).
• Optimizer chooses the passes and their order, the number of sweeps, the work budget, validation between passes, and compaction (Tier 2).
• run_pass runs one PassKind on an ir_lang::Builder with a Budget, for callers with their own pipeline (Tier 3).
• Stats reports sizes before and after, sweeps, budget exhaustion, and per-pass counts; OptError says why optimization stopped.

The passes:

What it guarantees, and how each guarantee is checked:

Installation

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

opt-lang takes and returns ir_lang types, so use the same ir-lang release.

Without the standard library (optimization results are identical):

[dependencies]
opt-lang = { version = "0.3", default-features = false }

Quick start

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

// fn f(x: i64) -> i64 { let a = 2 + 3; (x * a) + (x * a) }
let mut m = Module::new("demo");
let f = m.declare_function("f", &Signature::new(&[Type::I64], &[Type::I64]), Linkage::Export)?;
let mut b = m.build(f)?;
let x = b.param(0)?;
let (two, three) = (b.iconst(Type::I64, 2)?, b.iconst(Type::I64, 3)?);
let a = b.add(two, three, Overflow::Wrap)?;
let p = b.mul(x, a, Overflow::Wrap)?;
let q = b.mul(x, a, Overflow::Wrap)?;
let r = b.add(p, q, Overflow::Wrap)?;
b.ret(&[r])?;

let stats = opt_lang::optimize(&mut m)?;
assert_eq!((stats.insts_before(), stats.insts_after()), (6, 3));
let text = m.display_function(f).to_string();
assert!(text.contains("const 5"));
assert!(text.contains("mul<overflow=wrap> v0, v1"));
assert!(text.contains("add<overflow=wrap> v2, v2"));
# Ok::<(), Box<dyn std::error::Error>>(())

Policies decide what may be folded

A check holds an operation whose policy can raise. With constant operands it folds to exactly what would happen at run time:

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

// i64::MAX + 1 with overflow=error: the error edge, with code 1 (E0001).
let mut m = Module::new("demo");
let f = m.declare_function("f", &Signature::new(&[], &[Type::I64]), Linkage::Export)?;
let mut b = m.build(f)?;
let max = b.iconst(Type::I64, i128::from(i64::MAX))?;
let one = b.iconst(Type::I64, 1)?;
let ok = b.create_block(&[Type::I64])?;
let err = b.create_block(&[Type::U32])?;
b.check(
    InstData::Binary { op: BinaryOp::Add, policy: Policy::overflow(Overflow::Error), args: [max, one] },
    BlockCall::with_args(ok, &[BlockArg::Result(0)]),
    BlockCall::with_args(err, &[BlockArg::ErrorCode]),
)?;
b.switch_to(ok)?;
let sum = b.block_param(ok, 0)?;
b.ret(&[sum])?;
b.switch_to(err)?;
let code = b.block_param(err, 0)?;
let wide = b.convert(ir_lang::ConvOp::Zext, Policy::NONE, code, Type::I64)?;
b.ret(&[wide])?;

opt_lang::optimize(&mut m)?;
let text = m.display_function(f).to_string();
assert!(!text.contains("check"));
assert!(text.contains("const 1\n    ret"));
# Ok::<(), Box<dyn std::error::Error>>(())

The same addition with overflow=trap stays an addition (it traps at run time); with overflow=wrap it folds to i64::MIN.

OPS v2: pow and saturate

ir-lang treats a signed pow as always fallible (a negative exponent raises NegativeExponent under every policy), so it is always a check. With a constant exponent the optimizer still simplifies it, without ever producing IR that ir-lang would refuse:

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

// fn f(x: i64) -> i64 { x ** 2 }
let mut m = Module::new("demo");
let f = m.declare_function("f", &Signature::new(&[Type::I64], &[Type::I64]), Linkage::Export)?;
let mut b = m.build(f)?;
let x = b.param(0)?;
let two = b.iconst(Type::I64, 2)?;
let ok = b.create_block(&[Type::I64])?;
let err = b.create_block(&[Type::U32])?;
b.check(
    InstData::Binary { op: BinaryOp::Pow, policy: Policy::overflow(Overflow::Trap), args: [x, two] },
    BlockCall::with_args(ok, &[BlockArg::Result(0)]),
    BlockCall::with_args(err, &[BlockArg::ErrorCode]),
)?;
b.switch_to(ok)?;
let sq = b.block_param(ok, 0)?;
b.ret(&[sq])?;
b.switch_to(err)?;
b.trap(6)?;

opt_lang::optimize(&mut m)?;
let text = m.display_function(f).to_string();
// x * x traps on exactly the same inputs; nothing can raise any more.
assert!(text.contains("mul<overflow=trap> v0, v0") && !text.contains("check"));
# Ok::<(), Box<dyn std::error::Error>>(())

x ** 0 becomes 1, x ** 1 becomes x, a negative constant exponent goes straight to the error edge with code 6, and x ** 3 under wrap keeps its check (the only valid form) but its error edge, which cannot be taken, is pointed at an unreachable block so the error handler is deleted. The full table is in docs/API.md.

Choosing the passes

use ir_lang::{Linkage, Module, Overflow, Signature, Type};
use opt_lang::{Budget, Optimizer, PassKind};

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

// Tier 2: value numbering and dead code only, at most two sweeps, a fixed
// budget, and the validator after every pass.
let stats = Optimizer::new()
    .passes(&[PassKind::Gvn, PassKind::Dce])
    .max_iterations(2)
    .budget(1 << 20)
    .validate(true)
    .run(&mut m)?;
assert_eq!(stats.insts_after(), 2);
assert_eq!(stats.pass(PassKind::Gvn).changes(), 1);

// Tier 3: one pass on a builder.
let mut budget = Budget::unlimited();
assert!(!opt_lang::run_pass(&mut m.edit(f)?, PassKind::Gvn, &mut budget)?);
# Ok::<(), Box<dyn std::error::Error>>(())

Examples

Runnable programs in examples/:

Performance

Every pass is a constant number of linear walks over the function (plus the O(E log V) dominator tree), so time grows linearly with size; the cost per instruction rises once the function no longer fits in cache (about 1.6x for the pipeline between 100k and 1M instructions). Measured with the benchmarks in benches/ on functions of the typical shape (see below), x86_64, Rust 1.95 stable, release profile, Windows 11, on a machine also running other builds; each figure is one run of one pass, or the whole pipeline to its fixpoint, on the unoptimized function. Library-only figures: building the IR is not included.

These are 0.3.0 figures (ir-lang 2.0.0-alpha.3). Against 0.2.0's code on the same ir-lang and machine, the moves through Builder::move_inst made simplify-cfg about 23% and licm 18-28% faster; the other passes are within this machine's run-to-run spread (about ±10%). Two bulk-edit benchmarks, edit/simplify-cfg-merge (merging a 50,000-block chain) and edit/dce-dead-params (removing 350,000 block parameters), measure the rewrites alone: ~31 ms (-32% to -53% over two runs) and ~34 ms (no change to -16% over two runs).

Every figure includes the input validation each optimizer run performs (about 4 ms at 100k and 60 ms at 1M instructions, measured for 0.2.0). The pipeline compacts a function between passes once most of its arena is tombstones, which keeps later sweeps on dense tables.

The typical shape is what a front end lowers ordinary code into: arithmetic with a constant subexpression, the same value computed twice, a dead value, a diamond joined by a block parameter, a branch on a constant, and every fourth unit a counted loop with an invariant product. On it the pipeline removes 63.8% of the instructions (76,674 to 27,787 at 100k; 766,674 to 277,787 at 1M) and 63.0% of the blocks (30,004 to 11,114), in three sweeps. Those are the numbers for that shape only; real code has less redundancy.

cargo bench --bench bench

Criterion writes per-benchmark reports to target/criterion/; the reduction figures are printed to stderr. Numbers vary by CPU; use the trend across runs, not a single absolute.

Design notes

• Analysis first, then rewrite. Each pass computes everything it will do before it changes the function, and the IR is rewritten only through the ir-lang Builder, which type-checks every insertion. A pass that cannot be paid for from the budget changes nothing.
• Bulk edits in linear time. Instructions are moved with Builder::move_inst (O(1); handle and results kept) and block parameters are removed in bulk with Builder::remove_block_params (one linear pass), both added to ir-lang for this crate.
• GC references are never moved. A ref, or a value derived from one, is never made a constant, value-numbered, or hoisted: moving it across a safepoint would break the IR's statepoint rules. No pass moves a call or safepoint or edits a GC list, so statepoints placed by insert_statepoints stay valid and it does not need to run again (the tests check that it would add nothing).
• Folding without std. core lacks floor, round, sqrt, and their kin on the MSRV; the folder implements them from the bit representation (rounding by clearing fraction bits, the square root by an exact integer root), so no_std builds fold exactly what std builds fold. A float operation whose result is a NaN is not folded: OPS lets a machine produce any quiet NaN, and folding would fix one payload at compile time.
• The pipeline is pass-lang. The sweep loop is a pass_lang::PassManager run to a fixpoint. pass-lang's errors carry only a message, so the typed OptError travels beside it and is what callers see.

What is not done yet, plainly: no memory optimizations (loads are not value-numbered or forwarded across stores, dead stores are not removed), no inlining, no SROA, no loop canonicalization, no strength reduction beyond x ** 2 to x * x, and fma is not constant-folded. ir-lang alpha.3's validator, which runs on every input, is quadratic on a deep chain of blocks whose error edges join one handler (about 0.3 s at 5,000 and 6.7 s at 20,000 such blocks in a debug build); opt-lang's own passes are linear there. Calls are never removed, even to functions marked readnone (the attribute is an unchecked hint). See dev/ROADMAP.md.

Testing

cargo test                       # unit + integration + property + doctests
cargo test --no-default-features # no_std + alloc
cargo clippy --all-targets --all-features -- -D warnings
cargo bench --bench bench

tests/differential.rs is the core of the suite: random programs, run in the ir-lang reference interpreter before and after optimization. tests/gc.rs does the same for programs with GC references and safepoints, tests/variables.rs for programs built with ir-lang's variable API and automatic statepoints, tests/passes.rs pins down each pass on hand-written IR, tests/hostile.rs feeds deep, long, and wide functions and tiny budgets, and tests/scale.rs checks the figures quoted above. Every rust example in this README and in docs/API.md is compiled and run as a doctest.

Cross-platform support

• Linux (x86_64, aarch64)
• macOS (x86_64, Apple Silicon)
• Windows (x86_64)

The crate uses no operating-system facilities and no platform-specific code; a function optimizes to the same IR on every platform.

Contributing

See REPS.md for the engineering standards every change is held to, dev/DIRECTIVES.md for the definition of done, and dev/ROADMAP.md for what comes next. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.