How Sway IR Optimization Passes Work: DCE, CSE, and Function Inlining Explained

Sway's IR optimizer uses a modular pass framework to eliminate dead code, remove redundant computations, and inline small functions before lowering to Fuel VM bytecode.

The Sway compiler transforms source code into an intermediate representation (IR) managed by the sway-ir crate in the FuelLabs/sway repository. Before emitting Fuel VM bytecode, the IR undergoes a pipeline of Sway IR optimization passes that remove waste, deduplicate work, and expand function calls to expose further optimization opportunities.

The Optimization Pass Framework in Sway IR

All optimization passes share a common infrastructure defined in sway-ir/src/pass_manager.rs and re-exported from sway-ir/src/lib.rs. This framework handles pass registration, dependency resolution, and mutability constraints.

Pass Definition and Registration

Each pass is created by a create_*_pass() function that returns a Pass struct containing the pass name, description, runner function, and dependency list. For example, Dead-Code Elimination registers itself via create_dce_pass() in sway-ir/src/optimize/dce.rs.

// Conceptual representation based on sway-ir/src/optimize/dce.rs
pub fn create_dce_pass() -> Pass {
    Pass {
        name: "dce",
        description: "Dead Code Elimination",
        runner: Runner::FunctionPass(run_dce),
        deps: vec![], // DCE has no mandatory dependencies
    }
}

Pass Dependencies and Analyses

Passes declare required analyses via the deps field. The pass manager ensures these analyses are computed once and cached for reuse. For instance, Common Sub-Expression Elimination declares dependencies on POSTORDER_NAME and DOMINATORS_NAME in sway-ir/src/optimize/cse.rs to ensure correct dominance checks during value numbering.

Dead-Code Elimination (DCE) in Sway IR

Dead-Code Elimination removes instructions, block arguments, local variables, and entire functions that do not affect program output. The implementation in sway-ir/src/optimize/dce.rs uses a worklist-driven algorithm based on use-count propagation.

How DCE Identifies Dead Values

The pass begins by computing three use-count metrics:

• num_ssa_uses: Counts how many SSA values (instructions or block arguments) reference a given Value
• num_local_uses: Tracks get_local operations per LocalVar
• num_symbol_loaded: Monitors loads of global symbols

Any instruction with zero SSA uses becomes an initial candidate for elimination, provided it lacks side effects.

The Worklist Propagation Algorithm

DCE implements an iterative worklist algorithm that propagates deadness backward through the dependency graph:

// Conceptual steps from sway-ir/src/optimize/dce.rs
while let Some(dead_value) = worklist.pop() {
    // Reduce use counts of operands
    for operand in dead_value.operands() {
        if decrement_use_count(operand) == 0 {
            worklist.push(operand);
        }
    }
    
    // Special handling for stores
    if is_removable_store(dead_value) {
        mark_store_dead(dead_value);
    }
}

The can_eliminate_value function guards against removing terminators or instructions with side effects, while is_removable_store checks whether a store writes to a symbol that is never read and hasn't escaped.

Global Dead-Code Elimination

Beyond local DCE, the globals_dce function in sway-ir/src/optimize/dce.rs performs global analysis:

1. Traverses the call graph starting from entry and fallback functions
2. Collects used globals and called functions
3. Removes unused global variables and uncalled functions

This ensures that dead code at the module level is eliminated even when individual functions appear to use it.

Common Sub-Expression Elimination (CSE) in Sway IR

Common Sub-Expression Elimination removes redundant computations by identifying instructions that produce identical results. The implementation in sway-ir/src/optimize/cse.rs employs a value-numbering scheme with dominance checks to ensure correctness across control flow.

Value Numbering and the Expr Enum

CSE maps each instruction to a hashable Expr enum representing its operation and operands:

// Conceptual representation from sway-ir/src/optimize/cse.rs
enum Expr {
    BinaryOp { op: BinaryOpKind, arg1: Value, arg2: Value },
    UnaryOp { op: UnaryOpKind, arg: Value },
    GetElemPtr { base: Value, indices: Vec<Value> },
    Phi(Vec<Value>),
    // ... other variants
}

Constants are value-numbered by their content hash, ensuring that identical literals receive the same number regardless of where they appear.

The VNTable and Iterative Refinement

The pass maintains a VNTable with two mappings:

• value_map: Value → ValueNumber – current number for each IR value
• expr_map: Expr → ValueNumber – canonical representative for each expression

The algorithm iterates in reverse post-order (RPO) (obtained from the PostOrder analysis) until convergence:

1. Initialize function arguments to map to themselves
2. For each instruction, compute its Expr via instr_to_expr
3. If expr_map contains the expression, mark the current value as a duplicate of the existing ValueNumber
4. Otherwise, assign a fresh ValueNumber and insert into expr_map
5. Repeat until no value numbers change

Dominance Checks for Safety

CSE only replaces a value with a previously computed one if the earlier computation dominates the later use. The dominates function in sway-ir/src/optimize/cse.rs uses the dominator tree (from the DOMINATORS_NAME analysis) to verify that the candidate definition dominates the current block.

This prevents invalid replacements across control-flow joins where the earlier value might not be available on all paths.

Function Inlining in Sway IR

Function inlining replaces call sites with the body of the callee, eliminating call overhead and exposing inter-procedural optimization opportunities. The implementation in sway-ir/src/optimize/inline.rs operates at the module level using call-graph analysis and heuristics to balance code size against performance.

Inlining Heuristics and Metadata

The inline_heuristic function decides whether to inline a specific call site based on multiple criteria:

• Entry functions: Never inline functions marked as is_original_entry (contract entry points)
• User directives: Respect #[inline(always)] and #[inline(never)] attributes parsed by metadata_to_inline
• Call frequency: Always inline functions called exactly once (call_counts == 1)
• Size threshold: Inline small functions containing 12 or fewer instructions (MAX_INLINE_INSTRS_COUNT)

The is_small_fn helper evaluates block count, instruction count, and estimated stack size to identify trivial callees.

The Call Graph and Processing Order

Inlining processes functions in callee-first order to prevent invalidation of previous work:

1. Build the call graph using call_graph::build_call_graph
2. Compute callee_first_order to ensure callees are inlined into their callers before callers are themselves processed
3. This ordering guarantees that inlining a callee does not later get undone by inlining its caller

Block Splitting and Instruction Remapping

The inline_function_call function performs the actual transformation:

// Conceptual steps from sway-ir/src/optimize/inline.rs
fn inline_function_call(call_site: Instruction, caller: Function, callee: Function) {
    // 1. Split the block at the call site
    let (pre_block, post_block) = split_block_at_call(call_site);
    
    // 2. Remove the call instruction from pre_block
    remove_instruction(call_site);
    
    // 3. Create block arguments on post_block for return values
    let ret_args = create_return_arguments(post_block, callee.return_type());
    
    // 4. Clone callee body into caller, remapping values
    let value_map = clone_callee_body(callee, pre_block, post_block);
    
    // 5. Patch existing call-site data for moved instructions
    patch_call_sites(post_block, value_map);
}

The pass returns true if any inlining occurred, signaling the pass manager to run subsequent optimizations like CSE and DCE on the expanded IR.

Summary

• Sway IR optimization passes operate on the intermediate representation in the sway-ir crate before Fuel VM code generation.
• Dead-Code Elimination in sway-ir/src/optimize/dce.rs uses a worklist algorithm tracking SSA use counts to remove unused instructions, locals, and globals.
• Common Sub-Expression Elimination in sway-ir/src/optimize/cse.rs employs value-numbering with dominator checks to eliminate redundant computations across control flow.
• Function Inlining in sway-ir/src/optimize/inline.rs applies heuristics based on call frequency, size thresholds, and user metadata to expand callee bodies into callers, enabling further optimizations.

Frequently Asked Questions

How does Sway's Dead-Code Elimination handle side effects?

DCE uses the can_eliminate_value function to protect instructions with side effects. It specifically checks for terminators and non-removable stores via is_removable_store, which verifies that a store writes to a symbol that is never read and hasn't escaped. Only pure computations with zero uses are candidates for removal.

What analyses does Common Sub-Expression Elimination require?

CSE declares explicit dependencies on POSTORDER_NAME and DOMINATORS_NAME in its pass definition within sway-ir/src/optimize/cse.rs. The post-order traversal provides the reverse post-order (RPO) iteration needed for the dataflow algorithm, while the dominator tree enables the dominates check that ensures replacement candidates are available on all control-flow paths.

When does the Function Inlining pass decide to inline a call site?

The inline_heuristic function in sway-ir/src/optimize/inline.rs evaluates multiple criteria: it never inlines entry functions (is_original_entry), respects #[inline(always)] and #[inline(never)] metadata, always inlines functions called exactly once, and inlines small functions containing 12 or fewer instructions (MAX_INLINE_INSTRS_COUNT).

How do Sway IR optimization passes interact with each other?

The pass manager in sway-ir/src/pass_manager.rs orchestrates execution based on declared dependencies. Function inlining runs early to expose code for deduplication, followed by CSE to eliminate redundancies exposed by inlining, and finally DCE to clean up unused instructions and locals. Because passes return true when they modify the IR, the driver can iteratively run the pipeline until convergence.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}