logo
CHEATSHEETSTOOLSABOUT中文

Programming Languages - Static Single-Assignment (SSA)

Static Single-Assignment (SSA) form is an intermediate representation (IR) property used in modern optimizing compilers (such as LLVM, GCC, and Java's HotSpot VMM) where every variable is assigned a value exactly once, and every variable is defined before it is used.

If a source program reassigns a variable multiple times, an SSA-based compiler renames each assignment to a distinct, versioned variable name.

Basic Transformation Example

Consider this non-SSA C-like code where y and x are assigned multiple times:

// Non-SSA Form
y = 1;
y = 2;
x = y + 1;

In SSA form, each assignment creates a unique, immutable variable version:

// SSA Form
y_1 = 1
y_2 = 2
x_1 = y_2 + 1

Because y_1 is never modified after definition, compiler passes can easily prove that y_1 is dead code and optimize x_1 to 2 + 1 = 3 via simple constant propagation without tracking complex variable lifetimes across assignments.

Control Flow and the Phi (φ) Function

When control flow branches and merges (e.g., if-else blocks or loops), a variable's value at a merge point depends on which execution path was taken. SSA handles this using a pseudo-instruction called a Phi (φ) function.

Example: Conditional Execution

// Non-SSA Code
if (condition) {
    x = 5;
} else {
    x = 10;
}
print(x);

When converted to SSA form, x gets versioned inside each branch, and a φ function selects the correct version at the join point:

// SSA Form
if (condition) {
    x_1 = 5
} else {
    x_2 = 10
}
x_3 = phi(x_1, x_2)   // Selects x_1 if coming from 'if' block, x_2 if from 'else' block
print(x_3)

At CPU code generation time, φ functions are resolved by inserting standard mov instructions along the incoming control-flow edges.

Why Compilers Use SSA

SSA drastically simplifies and speeds up program analysis and compiler optimizations:

  • Explicit Data Flow (Def-Use Chains): Every variable usage directly points to its single definition point. Compilers do not need to perform expensive data-flow analysis (like reaching definitions) to know where a value came from.
  • Simplified Optimizations:
    • Constant Propagation: If x_1 = 5, replacing all uses of x_1 with 5 is trivially safe.
    • Dead Code Elimination: If a versioned variable x_2 is never referenced in any right-hand side expression, its assignment instruction can be removed.
    • Global Value Numbering (GVN): Redundant expressions across different basic blocks are easier to detect and eliminate.
  • Sparser Representations: Sparse conditional constant propagation (SCCP) runs in linear time under SSA rather than quadratic time under non-SSA IRs.

SSA IR vs Java bytecode

While both SSA IR (Static Single-Assignment Intermediate Representation) and Java Bytecode are intermediate representations used in language runtime and compiler toolchains, they are designed around fundamentally different computational models and execution goals.

Core Conceptual Distinction

  • SSA IR is an infinite-register, register-based graph representation optimized for static analysis and code optimization inside compilers (e.g., LLVM IR, GCC GIMPLE, HotSpot C2 JIT).
  • Java Bytecode is a stack-based instruction set designed for compact binary distribution, platform independence, and lightweight interpretation by the Java Virtual Machine (JVM).

Key Technical Comparison

Feature SSA Intermediate Representation Java Bytecode
Execution Model Register Machine (Infinite SSA registers) Stack Machine (Operand Stack + Local Variables)
Variable Assignment Immutable: Every variable (v1, v2, ...) is defined exactly once Mutable: Local variable slots (istore_1, iload_1) can be overwritten repeatedly
Control Flow Join Explicit Phi (φ) functions merge values at control flow joins Stack alignment: Value positions are implicit on the operand stack across basic blocks
Primary Design Goal Ease of compiler optimization (Constant propagation, GVN, DCE) Compact classfile size, portability, and fast interpretation/verification
Representation Format Typically held in memory as an AST/Graph structure during compilation Stored on disk as a compact .class binary stream of bytecodes
Explicit Data Flow Direct Use-Def chains: Every read points directly to its single instruction writer Implicit via stack operations: Data flows by pushing onto and popping off the evaluation stack

Side-by-Side Code Example

Consider this simple C/Java construct:

int compute(boolean cond) {
    int x;
    if (cond) {
        x = 10;
    } else {
        x = 20;
    }
    return x + 5;
}

Java Bytecode (Stack-Based)

Java Bytecode uses local variable array slots and an operand stack. Variable slot 1 (x) is overwritten in both branches:

  0: iload_1         // Push 'cond' parameter onto operand stack
  1: ifeq          10 // Jump to else block (offset 10) if cond == 0
  4: bipush        10 // Push 10 onto stack
  6: istore_2         // Store 10 into local variable slot 2 (x)
  7: goto          13 // Jump to merge point
 10: bipush        20 // Push 20 onto stack
 12: istore_2         // Store 20 into local variable slot 2 (x)
 13: iload_2          // Load x (slot 2) onto stack
 14: iconst_5         // Push 5 onto stack
 15: iadd             // Pop two values, add them, push result
 16: ireturn          // Return result

SSA IR (Register-Based with φ node)

SSA IR uses uniquely named virtual registers and an explicit φ instruction to resolve x at the control flow join point:

entry:
  br i1 %cond, label %then, label %else

then:
  %x.then = add i32 10, 0
  br label %merge

else:
  %x.else = add i32 20, 0
  br label %merge

merge:
  %x.3 = phi i32 [ %x.then, %then ], [ %x.else, %else ]
  %result = add i32 %x.3, 5
  ret i32 %result

How They Work Together in the JVM

Java Bytecode and SSA IR are not mutually exclusive—they represent different stages of a program's lifecycle in the JVM execution pipeline:

[ Java Source Code ]
        │  javac (Static Compilation)
        ▼
[ Java Bytecode ] ──► Classloader / Interpreter / Tier 1 JIT (C1)
        │
        │  Hot Spot Triggered (Tier 2 JIT / C2 / Graal)
        ▼
[ SSA IR (Sea of Nodes / C2 IR) ] ──► Optimizations (Inlining, GVN, Escape Analysis)
        │
        ▼
[ Native Machine Code (x86_64 / AArch64) ]
  1. Distribution Stage: javac compiles Java source code into Java Bytecode. The stack machine model is ideal here because bytecode instructions are small (often 1 to 3 bytes long), keeping .class files compact for downloading and fast for the interpreter to parse.
  2. JIT Compilation Stage: When a method becomes "hot", JIT compilers like HotSpot C2 or Graal transform the stack-based Java Bytecode into an SSA-based intermediate representation (e.g., C2's "Sea of Nodes" IR).
  3. Optimization & Code Gen: The JIT performs high-level optimizations (global value numbering, escape analysis, loop unrolling) directly on the SSA graph before lowering it to physical machine registers.

In different langauges

Compilers approach SSA in distinct ways depending on their architecture, execution speed goals, and analysis needs. These "flavors" range from low-level register representations to high-level domain-specific graphs.

Go: Internal SSA (cmd/compile/internal/ssa) vs. External SSA (golang.org/x/tools/go/ssa)

Go has two completely distinct SSA implementations because they serve different audiences: the compiler vs. tooling authors.

Go Internal SSA (cmd/compile/internal/ssa)

  • Role: The backend of the official gc compiler.
  • Target Audience: Code generation (lowering Go code down to assembly for amd64, arm64, etc.).
  • Characteristics:
  • Machine-Oriented: Starts abstract, but progressively lowers ops into architecture-specific assembly instructions (e.g., OpAMD64MOVQload).
  • Values & Blocks: Represents code using a dense array of Value and Block structs optimized for compilation speed.
  • Location Aware: Tracks registers and stack slots directly on Value objects during register allocation.

Go External SSA (golang.org/x/tools/go/ssa)

  • Role: A library for static analysis tools (linters, staticcheck, security scanners, godoc, call-graph analyzers).
  • Target Audience: Developers writing Go code analysis tools.
  • Characteristics:
  • High-Level & Language-Aware: Preserves Go's high-level semantics—types, interfaces, channels, maps, goroutines, and defer statements are first-class constructs.
  • Architecture Agnostic: Never lowers to machine instructions or physical registers.
  • Immutable AST-like Graph: Designed for easy traversal and querying rather than mutating or emitting machine code.

LLVM IR: Modern Standard-Bearer (Flat Textual/Bitcode SSA)

LLVM IR is a low-level, strongly-typed, infinite-register SSA.

  • Explicit phi Instructions: Uses classic phi nodes at control flow join points:
%res = phi i32 [ %a, %bb1 ], [ %b, %bb2 ]
  • Strict SSA Discipline: Every virtual register (%1, %val) is immutable and strictly defined before use.
  • Flat Basic Block Structure: Functions are lists of basic blocks; basic blocks are lists of instructions ending with a single terminator instruction (br, ret, switch).
  • Mem2Reg Pass: LLVM relies heavily on the mem2reg pass, which converts stack allocations (alloca/load/store) into SSA registers and phi nodes automatically.

GCC SSA IR: GIMPLE SSA

GCC uses GIMPLE as its intermediate representation, which is converted into SSA form early in the optimization pipeline before being lowered to RTL (Register Transfer Language).

  • Statement-Based: Unlike LLVM's expression/register-centric view, GIMPLE SSA operates on simplified 3-address C-like statements.
  • Virtual Operands (VDEF / VUSE): Because C handles raw pointers and memory aliases, GCC annotates memory access statements with virtual SSA variables to track memory dependencies:
# VDEF <mem_2>
*ptr_1 = 42;   ; Tracks memory mutation in SSA form
  • Pointer Aliasing Integration: GCC’s SSA flavor is built specifically to integrate with its pointer alias analysis engine directly within the IR.

Block Argument / Functional SSA (Swift SIL, MLIR, WebAssembly)

Instead of using explicit phi nodes, this modern flavor models basic blocks like functions that accept arguments.

  • How It Works: A branch instruction passes values directly to the destination block's parameters.
// Swift SIL / MLIR Style
bb1:
  br bb3(%val_then : $Int64)  ; Pass argument to bb3

bb2:
  br bb3(%val_else : $Int64)  ; Pass argument to bb3

bb3(%res : $Int64):           ; %res acts as the phi node
  return %res : $Int64
  • Advantages: Mathematically equivalent to Continuation-Passing Style (CPS) in functional languages. It eliminates phi nodes entirely, making transformations and optimizations cleaner to implement.
  • Key Users: Swift Intermediate Language (SIL), MLIR (Multi-Level Intermediate Representation), Rust's Cranelift backend.

Graph-Based / "Sea of Nodes" SSA (HotSpot C2, Graal, V8 TurboFan)

Used primarily in high-performance JIT compilers, the Sea of Nodes flavor drops basic block boundaries altogether during optimization.

  • No Basic Blocks: Control flow and data flow are represented as nodes in a single unified graph.
  • Data & Control Edges: A node points to its inputs (data dependencies) as well as its execution control inputs (control dependencies).
  • Benefits for JITs: Allows aggressive global optimizations (like Global Value Numbering and Loop Invariant Code Motion) without the overhead of constantly rebuilding control flow graphs (CFGs).
  • Schedule Stage: Basic blocks are only reconstructed at the very end when generating physical machine code.

Rust

In the Rust compiler ecosystem, SSA isn't just a single IR stage—it is used at three distinct levels of abstraction, each serving a completely different purpose in the compilation pipeline.

[ Rust Source Code ]
        │
        ▼
[ HIR (High-Level IR) ]           <-- AST-like, non-SSA (type checking, trait resolution)
        │
        ▼
[ MIR (Mid-Level IR) ]           <-- SSA-like (CFG + Control Flow, Borrow Checking)
        │
        ▼
[ LLVM IR / Cranelift IR ]       <-- Pure SSA (Optimizations, Codegen, Machine Lowering)
        │
        ▼
[ Native Machine Code ]

Mid-Level IR (MIR): SSA-like for Borrow Checking

Before Rust generates LLVM IR, rustc transforms code into MIR. MIR is a control flow graph (CFG) consisting of basic blocks (bb0, bb1, ...) and local variables (_1, _2, ...).

  • Role: Powers Rust's core language invariants—specifically the Borrow Checker, match-statement exhaustion, drop elaboration, and const evaluation.
  • Is MIR Pure SSA? No, MIR is "SSA-like" (or semi-SSA).
  • Local variables (_1, _2) represent stack locations/places.
  • While rustc assigns values in a structured basic block graph, places in MIR can be mutated and reassigned across basic blocks without explicit phi nodes.
  • This decision was deliberate: borrow checking requires tracking the lifecycle and mutations of specific memory locations, which pure SSA value-renaming would obscure.
// Example MIR basic block snippet
bb0: {
    _1 = const 5_i32;       // Place _1 assigned
    _2 = Lt(_1, const 10);  // Read _1
    switchInt(_2) -> [0: bb2, otherwise: bb1];
}

Backend 1: LLVM IR (The Default Heavyweight)

For standard cargo build --release, rustc lowers MIR into LLVM IR.

  • Flavor: Classic, flat, infinite-register SSA with explicit phi nodes (as covered in the LLVM section earlier).
  • Role: High-level optimizations (loop unrolling, dead code elimination, auto-vectorization) and machine code generation (x86_64, aarch64, riscv, WebAssembly).
  • Rust Context: rustc passes rich metadata to LLVM IR (such as noalias attributes derived from Rust's &mut references), allowing LLVM's SSA optimization passes to optimize Rust code even more aggressively than equivalent C/C++ code.

Backend 2: Cranelift (The Fast JIT/Debug Alternative)

rustc also supports Cranelift (via cg_clif) as an alternative code-generation backend, primarily used to drastically speed up debug compilation times during development.

  • Flavor: Block Argument SSA (Functional-style SSA, similar to Swift SIL and MLIR).
  • How it handles joins: Cranelift eliminates phi nodes entirely. Instead, basic blocks take arguments directly when jumped to:
// Cranelift SSA IR concept
block0:
    v0 = iconst.i32 10
    v1 = iconst.i32 20
    brif v2, block1(v0), block2(v1)  ; Pass v0 or v1 as argument

block3(v3: i32):                     ; v3 acts as the phi node
    v4 = iadd v3, v5
    return v4
Loading...