IR & Optimization

SSA intermediate representation and optimization passes.

The IR (intermediate representation) is the bridge between the parser’s AST and the constraint backends. It uses Static Single Assignment form — every variable is defined exactly once.

SSA Variables

struct SsaVar(pub u32);

Each SsaVar is a unique, immutable variable identified by an integer. The IrProgram allocates them sequentially via fresh_var().

Instructions

The IR has 19 instruction variants. Each defines exactly one result variable:

Data

Arithmetic

Control Flow

Assertions

Boolean Logic

Comparisons

Cryptographic

IrProgram

struct IrProgram {
    instructions: Vec<Instruction>,
    next_var: u32,
    var_names: HashMap<SsaVar, String>,   // source names for errors
    var_types: HashMap<SsaVar, IrType>,   // Field or Bool
}

The program is a flat list of instructions — no phi-nodes needed because circuits have no dynamic branching. Type metadata (IrType::Field or IrType::Bool) is set by type annotations and used by backends to skip redundant boolean enforcement.

IR Lowering

IrLowering converts the AST into an IrProgram:

// With explicit declarations
IrLowering::lower_circuit(source, public_vars, witness_vars) -> IrProgram

// With in-source declarations
IrLowering::lower_self_contained(source) -> (pub_names, wit_names, IrProgram)

Key Lowering Rules

• let bindings are aliases — no instruction emitted, the name maps to an existing SsaVar
• if/else compiles to Mux(cond, then_val, else_val)
• for loops are statically unrolled (max 10,000 iterations)
• Function calls are inlined at each call site with recursion detection via call_stack
• Arrays are EnvValue::Array(Vec<SsaVar>) — indexing must be compile-time constant
• len(arr) is resolved at compile time to a constant

Environment

Variables are tracked via HashMap<String, EnvValue>:

enum EnvValue {
    Scalar(SsaVar),
    Array(Vec<SsaVar>),
}

Optimization Passes

The optimizer runs three passes sequentially via passes::optimize(&mut program):

1. Constant Folding (const_fold)

A forward O(n) pass that evaluates operations on known constants:

• Arithmetic: Const(3) + Const(5) → Const(8)
• Identity: x * 1 → x, x + 0 → x
• Annihilation: x * 0 → Const(0)
• Self-operations: x - x → Const(0), x / x → Const(1) (when x is a non-zero constant)
• Boolean logic: folds Not, And, Or on constant operands
• Comparisons: folds IsEq, IsNeq, IsLt, IsLe on constant operands (canonical limb comparison)
• Range checks: verifies RangeCheck on constants, replaces with pass-through

2. Dead Code Elimination (dce)

A backward pass that removes instructions whose results are never used.

Eliminable (pure): Const, Add, Sub, Neg

Conservative (may have side effects or be expensive): Mul, Div, Mux, PoseidonHash, RangeCheck, Not, And, Or, IsEq, IsNeq, IsLt, IsLe, Assert

Never eliminated: AssertEq, Input, RangeCheck, Assert (side-effecting)

3. Boolean Propagation (bool_prop)

A forward O(n) pass that computes the set of SSA variables proven to be boolean (0 or 1). The backends use this set to skip redundant boolean enforcement constraints.

Seeds (known boolean):

• Const(0) and Const(1)
• Comparison results: IsEq, IsNeq, IsLt, IsLe
• RangeCheck(x, 1) targets
• Assert operands and results
• Variables with IrType::Bool annotation

Propagation:

• Not(x) → result is boolean if x is boolean
• And(a, b) → result is boolean if both are boolean
• Or(a, b) → result is boolean if both are boolean
• Mux(c, t, f) → result is boolean if both t and f are boolean

Taint Analysis (taint)

An additional analysis pass (not part of optimize()) that runs as a diagnostic:

1. Forward taint propagation: marks all SSA variables derived from inputs
2. Backward constraint reachability: marks variables used by assertions/constraints

Warnings:

• UnderConstrained: an input influences no constraint — potential soundness issue
• UnusedInput: an input is declared but never used

IR Evaluator

ir::eval::evaluate(program, inputs) provides concrete forward evaluation of an IrProgram:

evaluate(program: &IrProgram, inputs: &HashMap<String, FieldElement>)
    -> Result<HashMap<SsaVar, FieldElement>, EvalError>

Used by compile_ir_with_witness() for early validation before constraint generation. Error variants: MissingInput, DivisionByZero, AssertionFailed, AssertEqFailed, RangeCheckFailed, UndefinedVar.

Source Files