opt-lang 0.2.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.2"
ir-lang  = "=2.0.0-alpha.1"

Without the standard library (optimization results are identical):

[dependencies]
opt-lang = { version = "0.2", 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.

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.

Every figure includes the input validation each optimizer run performs (about 4 ms at 100k and 60 ms at 1M instructions). 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. The builder has no "move instruction" and its remove_block_param scans every block, so the passes move an instruction by re-inserting a copy and forwarding its results, and remove many block parameters at once by rebuilding the affected blocks and retargeting their edges in one pass.
• 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. Everything else is fair game.
• 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 or strength reduction, and fma is not constant-folded. 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/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.