Compiler architecture

Edge compiles .edge source files into EVM bytecode through a multi-stage pipeline. The compiler uses egglog (equality saturation) as its core optimization framework at two distinct stages: once on the high-level IR and once on the emitted bytecode.

Pipeline overview

Source (.edge)
    │
    ▼
┌──────────┐
│  Lexer   │  crates/lexer/
└────┬─────┘
     │ Vec<Token>
     ▼
┌──────────┐
│  Parser  │  crates/parser/
└────┬─────┘
     │ Program (AST)
     ▼
┌───────────────────┐
│ Import Resolution │  crates/driver/ (Compiler::resolve_imports)
└────┬──────────────┘
     │ Program (AST, stdlib items merged)
     ▼
┌────────────┐
│ Type Check │  crates/typeck/
└────┬───────┘
     │ (checked marker — errors gate pipeline, result discarded)
     ▼
┌────────────────┐
│ AST → IR Lower │  crates/ir/src/to_egglog.rs
└────┬───────────┘
     │ EvmProgram (RcExpr trees)
     ▼
┌───────────────────┐
│ Rust Pre-Passes   │  var_opt, storage_hoist
└────┬──────────────┘
     │ EvmProgram (optimized)
     ▼
┌──────────────────────┐
│ Egglog EqSat (IR)    │  crates/ir/src/optimizations/*.egg
└────┬─────────────────┘  [skipped at O0]
     │ EvmProgram (extracted best-cost)
     ▼
┌─────────┐
│ Cleanup │  crates/ir/src/cleanup.rs
└────┬────┘
     │ EvmProgram (simplified state params)
     ▼
┌──────────────────────┐
│ ASM Emit (optional)  │  crates/codegen/ [if --emit=asm, exits here]
└────┬─────────────────┘
     │ EvmProgram
     ▼
┌────────────────┐
│ Expr Compiler  │  crates/codegen/src/expr_compiler.rs
└────┬───────────┘
     │ Vec<AsmInstruction>
     ▼
┌──────────────────────────┐
│ Egglog EqSat (Bytecode)  │  crates/codegen/src/bytecode_opt/
└────┬─────────────────────┘  [skipped at O0]
     │ Vec<AsmInstruction> (optimized)
     ▼
┌───────────────────────┐
│ Subroutine Extraction │  crates/codegen/src/subroutine_extract.rs
└────┬──────────────────┘  [size mode only, O2+]
     │ Vec<AsmInstruction>
     ▼
┌───────────┐
│ Assembler │  crates/codegen/src/assembler.rs
└────┬──────┘
     │ Vec<u8> (runtime bytecode)
     ▼
┌─────────────────────┐
│ Constructor Wrapper  │  crates/codegen/src/contract.rs
└────┬────────────────┘
     │ Vec<u8> (deployment bytecode)
     ▼
  Final Output

Crate map

Stage 1: Lexing

File: crates/lexer/src/lexer.rs

Converts source text into tokens. The lexer tracks a Context (Global vs Contract) to disambiguate EVM type names from opcode names (e.g., bytes32 as a type vs byte as an opcode).

• Hex literal parsing (0x/0b) requires the '0' match arm to come before the generic digit arm
• Lookback token enables context-sensitive tokenization
• Outputs Iterator<Item = Result<Token, LexError>>

Stage 2: Parsing

File: crates/parser/src/parser.rs

Recursive descent parser with Pratt parsing for operator precedence. Eagerly lexes all tokens into a Vec<Token> (dropping whitespace/comments) for O(1) random access.

Key design decisions:

• SHL/SHR operand swap happens at parse time: a << b becomes Bop(Shl, b, a) to match EVM stack order
• Produces Program { stmts: Vec<Stmt>, span }

Stage 3: Type checking

File: crates/typeck/src/checker.rs

Walks the AST, resolves types, computes storage layouts (sequential slot assignment), and generates 4-byte function selectors via keccak256("name(type1,type2,...)").

Validates types and computes storage layouts and selectors. Errors gate the pipeline; no typed AST is threaded into later stages.

Stage 4: AST → IR lowering

File: crates/ir/src/to_egglog.rs (~1700 lines)

The most complex stage. Converts edge_ast::Program into EvmProgram, an IR designed for egglog equality saturation.

Core IR type: EvmExpr

The IR is a tree of EvmExpr nodes (25 variants), reference-counted as RcExpr = Rc<EvmExpr>:

EvmContext — context-sensitive optimization

Leaf nodes (Const, Arg, Empty) carry an EvmContext parameter that tells egglog where the expression lives. This enables context-sensitive rewrites without requiring a separate pass.

Key design decisions

• State threading: IR uses explicit StateT tokens for side-effect ordering. Codegen ignores state parameters entirely, relying on Concat sequencing instead.
• Memory-backed variables: VarDecl creates LetBind/Var/VarStore/Drop nodes. LetBind(name, init, body) allocates, Var(name) reads, VarStore(name, val) writes, Drop(name) marks lifetime end.
• Store-forwarding at source: First VarStore init is extracted directly into LetBind when safe, avoiding the LetBind(x, 0, Concat(VarStore(x, real), ...)) pattern.
• Function inlining: Functions are inlined at call sites. inline_depth counter ensures return inside inlined functions produces just the value (not RETURN opcode).
• Checked arithmetic: User +, -, * lower to OpCheckedAdd/OpCheckedSub/OpCheckedMul. Internal compiler arithmetic (mapping slots, memory offsets) uses unchecked ops.
• Mapping slots: keccak256(key . base_slot) — MSTORE key at offset 0, MSTORE slot at offset 32, KECCAK256(0, 64).
• DoWhile ordering: pred_and_body = Concat(body, cond) — body side effects run before condition re-evaluation.

Stage 5: Rust pre-passes

Two Rust passes run before egglog, handling transforms that pattern matching cannot express:

5a: Variable optimization (crates/ir/src/var_opt.rs)

Counting-based transforms requiring occurrence analysis:

• Stack (DUP-based, 3 gas/read): write_count == 0, not in loop, read_count <= 8
• Memory (MSTORE/MLOAD, 6 gas each): everything else
• Drop-based free-list reclaims memory slots

5b: Storage hoisting (crates/ir/src/storage_hoist.rs)

LICM (Loop-Invariant Code Motion) for SLoad/SStore in loops:

1. Identifies constant-slot storage ops inside DoWhile bodies
2. Hoists them into LetBind locals before the loop
3. Replaces SLoad/SStore with Var/VarStore inside the loop body
4. Emits write-backs after loop exit

This pass is critical because it prevents egglog's storage forwarding rules from firing unsoundly across loop back-edges.

Also performs straight-line SStore → SLoad forwarding and dead store elimination.

Bail conditions: ExtCall in loop body, nested loops.

Stage 6: Egglog equality saturation (stage 1 — IR level)

Files: crates/ir/src/optimizations/*.egg, crates/ir/src/schedule.rs, crates/ir/src/costs.rs

The IR is serialized to S-expressions (sexp.rs), fed into an egglog e-graph with 330 optimization rules across 12 rule files, and the best-cost result is extracted.

Schedule by optimization level

Cost model

Two modes controlled by --optimize-for:

In size mode, every node costs 1, minimizing total node count. In gas mode, costs reflect EVM gas prices, so the extractor avoids expensive operations.

Egglog optimization rules

Peepholes (peepholes.egg — ruleset: peepholes)

52 rules for algebraic simplification:

Checked arithmetic peepholes (8 additional rules): CheckedAdd(x, 0) → x, CheckedMul(x, 1) → x, CheckedSub(x, x) → 0, etc.

Arithmetic optimization (arithmetic.egg — ruleset: arithmetic-opt)

31 rules for strength reduction and algebraic identities:

Storage optimization (storage.egg — ruleset: storage-opt)

16 rules for storage load/store optimization:

Same 8 rules mirrored for TLoad/TStore (transient storage).

Memory optimization (memory.egg — ruleset: memory-opt)

6 rules mirroring storage optimization for memory:

• MLoad(off, MStore(off, val, st)) → val
• MStore(off, MLoad(off, st), st) → st
• MStore(off, v, MStore(off, v2, st)) → MStore(off, v, st)
• MLoad forwarded through SStore, TStore, Log

Constant propagation (const_prop.egg — ruleset: const-prop)

1 rule for propagating constants through immutable variable chains. Works in tandem with u256-const-fold inside a saturate loop to propagate freshly folded constants.

Function inlining (inline.egg — ruleset: peepholes)

1 rule for inlining small function bodies at call sites.

Dead code elimination (dead_code.egg — ruleset: dead-code)

45 rules combining IsPure analysis with elimination rewrites:

Pure expressions: Const, Arg, Empty, Selector, Var, Drop, all Uops, most Bops (including SLoad, TLoad, MLoad), Keccak256, Select, EnvRead. Also Concat(pure, pure) and If(pure, pure, pure).

Not pure: SStore, TStore, MStore, MStore8, Log, Revert, ReturnOp, ExtCall, CheckedAdd/Sub/Mul (can revert), VarStore, LetBind.

Range analysis (range_analysis.egg — ruleset: range-analysis)

64 rules combining lattice-based interval tracking with guarded rewrites:

• upper-bound(EvmExpr) → i64 with :merge (min old new)
• lower-bound(EvmExpr) → i64 with :merge (max old new)
• u256-upper-bound/u256-lower-bound for full U256 range
• max-bits(EvmExpr) → i64
• Relations: NonZero(EvmExpr), IsBool(EvmExpr)

ImmutableVar bound propagation: When ImmutableVar(name) is asserted (by var_opt), all bounds from LetBind init are propagated to Var(name) reads. This enables checked arithmetic elision through variables.

• x / x → 1 when NonZero(x)
• x % x → 0 when NonZero(x)
• IsZero(IsZero(x)) → x when IsBool(x)
• bool & 1 → bool when IsBool

U256 constant folding (u256_const_fold.egg — ruleset: u256-const-fold)

28 rules for folding operations on LargeInt (U256) constants using a custom egglog U256 sort:

• Arithmetic: ADD, SUB, MUL, DIV, MOD, EXP
• Bitwise: AND, OR, XOR, SHL, SHR
• Comparison: EQ, LT, GT, ISZERO (6 rules with two branches each)
• Power-of-2 strength reduction on U256 values (MUL/DIV/MOD → SHL/SHR/AND)
• LargeInt → SmallInt normalization when value fits in i64

Checked arithmetic elision (checked_arithmetic.egg — ruleset: range-analysis)

27 rules combining elision and bound propagation:

Checked ops also propagate bounds (since no overflow is guaranteed): CheckedAdd(a, b) upper = upper(a) + upper(b), enabling cascading elision.

Type propagation (type_propagation.egg — ruleset: type-propagation)

59 purely additive analysis rules populating HasType and FunctionHasType relations. No rewrites. Used by other passes for type-aware optimization.

CSE (cse.egg — ruleset: cse-rules)

No explicit rules. CSE is automatic via egglog's e-graph hash-consing. Commutativity rules in peepholes.egg ensure ADD(a,b) and ADD(b,a) share an e-class.

Stage 7: Post-egglog cleanup

File: crates/ir/src/cleanup.rs

Two passes after egglog extraction:

1. State simplification: Replaces all nested state parameters (massive SStore/SLoad chains) with a simple Arg(StateT) sentinel. Codegen ignores state params entirely.
2. Dead code after halt: Removes unreachable code after ReturnOp/Revert in Concat chains.

Also runs straight-line SStore → SLoad forwarding one more time to catch patterns egglog's cross-slot rules couldn't handle.

Stage 8: Expression compiler

File: crates/codegen/src/expr_compiler.rs

Walks the EvmExpr tree and emits EVM opcodes into an Assembler. Since the EVM is a stack machine, children are compiled first (postorder), then the operator.

• let_bindings: HashMap<String, usize> — variable name → memory offset
• next_let_offset: usize — high-water mark starting at 0x80
• free_slots: Vec<usize> — reclaimed by Drop
• stack_vars: HashMap<String, usize> — maps variable name to absolute stack position when it was pushed
• stack_depth: usize — tracks current stack depth for DUP indexing
• overflow_revert_label — shared trampoline for all checked arithmetic

Memory layout: Fixed offsets starting at 0x80. No free memory pointer — the codegen never reads 0x40. Memory slots are reclaimed via free_slots after Drop, so memory usage is not monotonically increasing — slots are reused for subsequent variables in the same scope.

• CheckedAdd: b > result overflow detection (6 extra opcodes)
• CheckedSub: a < b pre-check (5 extra opcodes)
• CheckedMul: result/a != b with a==0 short-circuit (~12 extra opcodes)
• Shared overflow_revert trampoline (PUSH0, PUSH0, REVERT) emitted once

Branch handling: compile_if saves/restores stack_vars, let_bindings, free_slots per branch so that Drop/slot-reuse in one branch doesn't affect the other. Halting branches get special stack depth handling.

Stage 9: Bytecode optimization (stage 2 — egglog)

Files: crates/codegen/src/bytecode_opt/

A second egglog pass operating on AsmInstruction sequences. Splits code into basic blocks, optimizes each through egglog, and reassembles.

Schedule

Bytecode rewrite rules (~66 rules)

Pre-pass: Dead code elimination after RETURN/REVERT/STOP. Post-pass: Label aliasing (consecutive labels → keep last).

Bytecode cost model

Stage 10: Subroutine extraction

File: crates/codegen/src/subroutine_extract.rs

Size-mode only (O2+). Detects repeated instruction sequences and extracts them into JUMP-based subroutines, trading ~30 gas/call for code size reduction.

1. Find straight-line regions (between labels/jumps)
2. Find all repeated subsequences (min 3 occurrences, min 15 bytes, min 5 instructions)
3. Greedy selection of most profitable non-overlapping candidates
4. Rewrite: replace inline code with calls, append subroutine bodies

Calling convention: PushLabel(ret) + JumpTo(sub) + JUMPDEST(ret). Subroutine uses SWAP chains for stack management. PushLabel(label) only emits PUSH addr (the return address), while JumpTo(label) emits PUSH addr + JUMP. The distinction matters: PushLabel is used to push a return address onto the stack before jumping, while JumpTo performs the actual transfer of control.

savings = N * byte_size - (byte_size + sub_overhead) - N * call_overhead

Where call_overhead = 8 bytes and sub_overhead = 2 + inputs + outputs. Only candidates with savings > 0 and ≥ 3 non-overlapping occurrences are extracted.

Stage 11: Assembler

File: crates/codegen/src/assembler.rs

Converts AsmInstruction sequences into final bytecode with label resolution:

• Short jumps: PUSH1 for contracts < 256 bytes, PUSH2 otherwise
• Two-pass assembly: first pass computes label offsets, second pass emits bytes
• AsmInstruction variants: Op(Opcode), Push(Vec<u8>), Label(String), JumpTo(String), JumpITo(String), PushLabel(String), Comment(String), Raw(Vec<u8>) — Raw carries verbatim bytecode bytes (used by InlineAsm IR nodes to embed hand-coded EVM sequences); the assembler emits these bytes as-is and the optimizer never touches them.
• Label generation: fresh_label(prefix) generates "{prefix}_{N}" strings using a monotonic counter, used for all synthetic jump targets (subroutine return addresses, if/else branches, etc.)

Stage 12: Constructor wrapper

File: crates/codegen/src/contract.rs

Produces two-part deployment bytecode:

1. Constructor (init code): Runs constructor body, then CODECOPY + RETURN to deploy runtime
2. Runtime: Dispatcher + inlined function bodies

Dispatcher: IR-driven dispatch — the selector if-else chain is encoded in the IR itself. ExprCompiler compiles it directly to EVM opcodes via compile_expr(contract.runtime). There is no separate binary-search or jump-table builder; the dispatch shape is determined by the IR lowering pass upstream.

Egglog advanced features

The compiler makes heavy use of egglog's advanced capabilities:

Summary statistics