This document describes the intermediate representation (IR) used by the compiler. It is intended to be a complete reference: a developer should be able to understand the entire IR design without reading the source code.

1. Module Structure
2. Compilation Pipeline
3. Key Identifiers
4. Type System
5. IrModule
6. IrFunction
7. BasicBlock
8. Instruction Set
9. Terminators
10. Operations
11. Constants
12. Intrinsics
13. Global Variables
14. Global Initializers
15. CFG Analysis
16. SSA Construction
17. Phi Elimination
18. Pass Interface
19. IR Debugging
20. Key Design Decisions

The IR subsystem lives at src/ir/ and is organized into the following files and subdirectories:

All public IR types are re-exported through reexports.rs, so consumers use use crate::ir::reexports::*.

  AST
   |
   |  lowering/
   v
  Alloca-based IR  (every local is a stack slot: alloca + load/store)
   |
   |  mem2reg/
   v
  SSA IR           (scalars promoted to virtual registers with phi nodes)
   |
   |  optimization passes, then phi elimination
   v
  Backend-ready IR (phi nodes lowered to copies)

The lowering phase translates the AST into a flat, alloca-based IR where every local variable is represented as a stack slot (an Alloca instruction) accessed through Load and Store instructions. The mem2reg pass then promotes eligible allocas into SSA virtual registers, inserting Phi nodes at control-flow join points. After optimization passes run on the SSA form, phi elimination converts Phi instructions into Copy instructions, producing backend-ready IR.

BlockId uses the .LBB prefix (rather than .L) to avoid collisions with the GNU assembler's internal local labels used for RISC-V PCREL_HI20/PCREL_LO12 relocation pairs.

IrType is defined in common/types and represents the target-independent scalar types used throughout the IR:

The type system is intentionally target-independent. Backend-specific ABI details (struct passing conventions, register classification) are carried as metadata on IrFunction, IrParam, and CallInfo rather than encoded in the type system itself. Pointers are opaque at the IR level -- the IrType attached to load/store instructions determines the access width; the pointer itself carries no pointee type information.

AddressSpace (defined in common/types) is used by Load, Store, and InlineAsm to express x86 segment register overrides:

On non-x86 targets this is always Default.

IrModule is the top-level compilation unit. It contains all functions, globals, string literals, and linker directives for a translation unit.

IrModule provides a for_each_function method that runs a transformation on each defined (non-declaration) function, returning the total count of changes made. This is used by optimization passes (see Pass Interface).

IrFunction represents a single function with its parameter list, basic blocks, and ABI metadata. It has 23 fields:

Each function parameter carries ABI metadata beyond its type:

IrFunction provides a max_value_id() method that returns the highest Value ID defined in the function. It uses the cached next_value_id when available, falling back to an expensive full-IR scan otherwise. This is useful for sizing flat lookup tables indexed by Value ID.

A basic block is a labeled, straight-line sequence of instructions ending in a terminator.

The Instruction enum has exactly 38 variants, organized into the following categories.

CallInfo is a shared metadata struct used by both Call and CallIndirect:

These instructions support _Complex return values that use two registers.

Instruction provides a for_each_used_value(&self, f: impl FnMut(u32)) method that calls f for every Value ID used as an operand. This is the canonical value visitor -- all passes that need to enumerate instruction operands use this method to avoid duplicating the 38-arm match block. A convenience used_values() method collects the results into a Vec<u32>.

Terminator has an analogous for_each_used_value and used_values pair.

The dest() method returns the Option<Value> defined by the instruction, and result_type() returns the Option<IrType> of the produced value.

The Terminator enum defines the 6 block-ending control flow operations:

Methods:

• is_commutative() -- returns true for Add, Mul, And, Or, Xor.
• can_trap() -- returns true for SDiv, UDiv, SRem, URem (divide by zero causes SIGFPE). Such operations must not be speculatively executed by if-conversion.
• eval_i64(lhs, rhs) -> Option<i64> -- evaluate on two i64 operands using wrapping arithmetic. Returns None for division/remainder by zero. Unsigned operations (UDiv, URem, LShr) reinterpret the bits as u64.
• eval_i128(lhs, rhs) -> Option<i128> -- same for i128 operands.

Methods:

• eval_i64(lhs, rhs) -> bool -- evaluate on two i64 operands. Signed comparisons use Rust's native i64 ordering; unsigned comparisons reinterpret the bits as u64.
• eval_i128(lhs, rhs) -> bool -- same for i128 operands.
• eval_f64(lhs, rhs) -> bool -- evaluate on two f64 operands using IEEE 754 semantics. For floats, signed and unsigned comparison variants are equivalent since IEEE 754 defines a total ordering.

Key methods on IrConst:

• Predicates: is_zero(), is_one(), is_nonzero()
• Value extraction: to_i64(), to_i128(), to_u64(), to_f64() (returns None when not applicable)
• Construction: from_i64(val, ty), zero(ty), one(ty), ptr_int(val) (pointer-width I32 or I64)
• Type coercion: coerce_to(target_ty), coerce_to_with_src(target_ty, src_ty) (unsigned-aware), narrowed_to(ty), bool_normalize() (to I8(0)/I8(1) per C11 6.3.1.2)
• Long double constructors: long_double(v), long_double_with_bytes(v, bytes), long_double_from_i64(val), long_double_from_u64(val), long_double_from_i128(val), long_double_from_u128(val)
• Float casts: cast_float_to_target(fv, target), cast_long_double_to_target(fv, bytes, target)
• Serialization: push_le_bytes(out, size) (target-default), push_le_bytes_x86(out, size) (x87 80-bit for long doubles), push_le_bytes_riscv(out, size) (binary128 for long doubles), to_le_bytes(), x87_bytes()
• Hashing: to_hash_key() converts to ConstHashKey which uses raw bit patterns for floats, enabling constants as HashMap keys for value numbering.

IntrinsicOp defines 81 target-independent intrinsic operations. Each backend emits the appropriate native instructions for its architecture. The variants are organized by ISA extension:

Each variant name maps directly to an x86 instruction mnemonic (e.g., Pcmpeqb128 -> pcmpeqb, Aesenc128 -> aesenc). On ARM and RISC-V, backends emit the equivalent native instructions. See intrinsics.rs for the complete variant list with per-variant doc comments.

The is_pure() method returns true for intrinsics with no side effects -- pure intrinsics can be dead-code eliminated when their result is unused. Most SIMD arithmetic, shifts, shuffles, pack/unpack, insert/extract, AES-NI, CLMUL, and scalar math operations are marked pure. Intrinsics with memory or ordering side effects (fences, non-temporal stores, loads/stores) are not pure. See the is_pure() match in intrinsics.rs for the authoritative list.

IrGlobal defines a global variable with its initializer and linkage attributes:

GlobalInit represents the initializer for a global variable. It has 10 variants:

Methods on GlobalInit:

The analysis module (analysis.rs) provides shared CFG and dominator tree utilities used by mem2reg, GVN, LICM, if-conversion, and IVSR.

FlatAdj stores n variable-length rows in two flat arrays:

• offsets[i]..offsets[i+1] is the range of indices into data for row i
• data[offsets[i]..offsets[i+1]] contains the neighbors of node i

This uses exactly 2 heap allocations regardless of the number of rows (compared to n+1 for Vec<Vec<usize>>), and provides better cache locality when iterating over adjacency lists.

Access: row(i) -> &[u32] returns the neighbor slice for node i. Length: len(i) -> usize returns the number of neighbors of node i.

CfgAnalysis is a cached bundle of pre-computed analysis results that can be shared across multiple passes within a single pipeline iteration. Since passes like GVN only replace instruction operands without modifying the CFG, these results remain valid across GVN, LICM, and IVSR, avoiding redundant recomputation.

Constructed via CfgAnalysis::build(func), which calls build_label_map, build_cfg, compute_dominators, and build_dom_tree_children in sequence.

CFG construction (build_cfg) iterates over each block's terminator to extract successor edges (Branch, CondBranch, IndirectBranch, Switch). It also scans instructions for InlineAsm goto labels, which create implicit control flow edges. The function returns both predecessor and successor adjacency lists in CSR format, using only 4 heap allocations total.

Reverse postorder (compute_reverse_postorder) performs a DFS from the entry block (block 0) and collects blocks in postorder, then reverses. This ordering is required by the dominator algorithm and ensures that each block is processed after its dominator.

Dominator computation (compute_dominators) uses the Cooper-Harvey-Kennedy algorithm. It iterates over blocks in reverse postorder, computing the immediate dominator of each block as the intersection of its already-processed predecessors' dominators. The intersect function walks two fingers up the dominator tree, guided by RPO numbering, until they meet at the common dominator. The algorithm converges in a small number of iterations for reducible CFGs (typically 2-3 passes over the RPO).

Dominance frontiers (compute_dominance_frontiers) are computed from the predecessor lists and the idom array. For each join point (block with 2 or more predecessors), a runner walks up the dominator tree from each predecessor, adding the join point to every block's frontier along the way, stopping when it reaches the join point's immediate dominator. The result is Vec<FxHashSet<usize>> where df[b] is the dominance frontier of block b.

SSA construction follows a two-phase approach, modeled after the LLVM strategy.

Every local variable is lowered to an Alloca instruction (a stack slot) accessed through Load and Store instructions. Function parameters get a ParamRef instruction to make their initial value visible, followed by a Store to the parameter's alloca. This representation is simple to generate because every variable reference translates to a load or store through the alloca pointer, regardless of control flow complexity. No SSA renaming or phi placement is needed at this stage.

entry:
    %1 = alloca i32, 4, 4       // int x;
    %2 = alloca i32, 4, 4       // int y;
    %3 = paramref 0, i32        // incoming parameter value
    store %3, %1, i32           // x = param0
    ...
    %5 = load %1, i32           // read x
    %6 = binop add %5, const(1) // x + 1
    store %6, %2, i32           // y = x + 1

The mem2reg pass promotes eligible allocas to SSA registers using the standard algorithm, implemented in 6 steps (as numbered in the implementation):

1. Identify promotable allocas -- an alloca is promotable if it is scalar (size <= MAX_PROMOTABLE_ALLOCA_SIZE = 8 bytes), accessed only by Load/Store (not address-taken by GetElementPtr, Memcpy, VaStart, inline asm memory-only constraints, etc.), and not marked volatile.

2. Build CFG -- construct predecessor and successor adjacency lists from block terminators (and inline asm goto edges).

3. Compute dominator tree -- using the Cooper-Harvey-Kennedy algorithm.

4. Compute dominance frontiers -- for phi placement.

5. Insert phi nodes -- at the iterated dominance frontiers of each alloca's defining blocks (blocks containing stores to that alloca).

6. Rename variables -- via dominator-tree DFS, maintaining a stack of reaching definitions for each alloca. Replace loads with the current reaching definition and update the stack at stores. Fill in phi node operands from predecessor reaching definitions.

After mem2reg, the original alloca/load/store sequences are replaced with direct value references and phi nodes, yielding proper SSA form.

The pass runs twice during compilation:

• Before inlining (promote_allocas): promotes non-parameter allocas. Parameter allocas are kept because the inliner assumes they exist for argument passing.
• After inlining (promote_allocas_with_params): promotes all allocas including parameters, since inlining is complete and parameter values are now explicit via ParamRef + Store.

Phi elimination (mem2reg/phi_eliminate.rs) runs after all SSA optimizations and before backend codegen. It converts each Phi instruction into Copy instructions. Three cases are handled:

Direct copies are inserted at the end of each predecessor block (before the terminator):

pred_block:
    %phi1_dest = copy src1
    %phi2_dest = copy src2
    <terminator>

When phis form a cycle (e.g., a swap pattern where phi1 reads from phi2's dest and vice versa), a two-phase temporary protocol is used to avoid the lost-copy problem. The pass analyzes the copy graph per predecessor to detect cycles and introduces shared temporaries:

pred_block:
    %tmp1 = copy src1     // save source before it's overwritten
    <terminator>

target_block:
    %phi1_dest = copy %tmp1  // restore from temporary
    ... rest of block ...

When a predecessor block has multiple successors (e.g., a CondBranch) and the target block has phis, placing copies at the end of the predecessor would execute them on ALL outgoing paths, corrupting values on other edges. To fix this, the critical edge is split by inserting a new trampoline block that contains only the phi copies and branches unconditionally to the target. Trampoline block IDs are allocated from a global counter (computed as the maximum block ID across all functions) to avoid label collisions.

Optimization passes consume and transform the SSA IR. The pass pipeline lives in src/passes/ (see passes/README.md for the complete pass-by-pass reference). This section describes how passes interact with the IR.

A per-function optimization pass is a function with signature:

fn my_pass(func: &mut IrFunction) -> usize

It takes a mutable reference to a single function and returns the number of changes made (0 = no changes). This change count drives the fixed-point iteration: the pipeline re-runs passes until no more changes occur or a diminishing-returns threshold is reached.

IrModule::for_each_function(f) iterates over all defined (non-declaration) functions and calls f on each, accumulating the total change count. This is the standard way to apply a per-function pass to the entire module.

For passes that need CFG/dominator analysis (GVN, LICM, IVSR), the pipeline builds a shared CfgAnalysis once per function and passes it to all three. Since GVN only replaces operands without modifying the CFG, the analysis remains valid across all three passes.

The optimization pipeline runs inlining first (with its own mem2reg passes), then enters a fixed-point loop (up to 3 iterations) over these per-function passes:

1. CFG simplification
2. Copy propagation
3. Division-by-constant strength reduction (first iteration only, 64-bit targets only)
4. Integer narrowing
5. Algebraic simplification
6. Constant folding
7. GVN (Global Value Numbering) -- shares CfgAnalysis with LICM and IVSR
8. LICM (Loop-Invariant Code Motion)
9. IVSR (Induction Variable Strength Reduction, first iteration only)
10. If-conversion
11. Copy propagation (second round)
12. DCE (Dead Code Elimination)
13. CFG simplification (second round)
14. IPCP (Interprocedural Constant Propagation)

After the fixed-point loop, dead static function elimination removes unreferenced static functions. Each per-function pass has dependency tracking: it only runs if it or its upstream passes made changes in the previous iteration, avoiding redundant work. See passes/README.md for the complete dependency graph and per-pass documentation.

There is no structured textual IR format (unlike LLVM's .ll files). All IR types derive Debug, so Rust's {:?} formatter can dump any IR structure, though the output is verbose.

The inliner contains a private dump_function_ir helper that prints a human-readable IR dump to stderr. It is activated via the CCC_INLINE_DUMP_IR environment variable.

Other useful environment variables for debugging the IR pipeline:

1. Alloca-based lowering, then mem2reg. This separates concerns: the lowering pass handles C semantics without worrying about SSA, and mem2reg handles SSA construction without knowing C. This is the same strategy used by LLVM.

2. Numeric Value(u32) IDs. Values are identified by Value(u32), not string names. This simplifies the IR, avoids name collision issues, enables flat lookup tables indexed by Value ID, and makes value comparison a simple integer comparison.

3. Target-independent types. The IR uses abstract types (I8 through I128, U8 through U128, F32, F64, F128, Ptr, Void) and delegates ABI details (calling conventions, register assignment, struct layout) to the backend. Backend-specific metadata is carried on IrFunction, IrParam, and CallInfo.

4. Dual-representation LongDouble. IrConst::LongDouble(f64, [u8; 16]) carries both an f64 approximation for constant folding and the raw IEEE 754 binary128 bytes for precise code emission. This avoids the need for a software f128 implementation while preserving precision where it matters.

5. Canonical for_each_used_value() visitor. A single method on Instruction that visits all used values. All optimization passes use this instead of duplicating the 38-arm match block, ensuring consistency and reducing maintenance burden.

6. CSR adjacency lists. The CFG uses flat CSR storage (FlatAdj) instead of Vec<Vec<usize>> because build_cfg is called per-function by multiple passes (GVN, LICM, if-conversion, mem2reg). The flat layout reduces heap allocations from n+1 to 2 per build_cfg call and improves cache locality.