What is SSA?

  • SSA (Static Single Assignment) is a program representation where each variable (value) is assigned exactly once.
  • In traditional code, a variable may be assigned multiple times, but in SSA form, every new value gets a new name (register).
  • LLVM IR is fundamentally in SSA form, which makes it easier for the compiler to track variable usage and perform optimizations.

Example

Consider the following C code:

int y = f();
int z;
if (y < 0)
    z = y + 1;
else
    z = y + 2;
return z;

In LLVM IR, the variable z is assigned in two branches. In SSA form, LLVM IR introduces different names for each branch and merges them using a φ (phi) node:

define i32 @example() {
entry:
  %call = call i32 @f()               ; store result of f() into %call (y)
  %cmp = icmp slt i32 %call, 0        ; compare y < 0
  br i1 %cmp, label %if.then, label %if.else

if.then:                              ; then block
  %add = add nsw i32 %call, 1         ; y + 1
  br label %if.end

if.else:                              ; else block
  %add1 = add nsw i32 %call, 2        ; y + 2
  br label %if.end

if.end:                               ; merge block
  %z.0 = phi i32 [ %add, %if.then ], [ %add1, %if.else ]
  ret i32 %z.0
}
  • %call represents y.
  • %add is the then branch value of z (y+1).
  • %add1 is the else branch value of z (y+2).
  • The phi node %z.0 = phi i32 [...] merges values: if control comes from %if.then, choose %add; if from %if.else, choose %add1.
  • Thus, %z.0 represents z in SSA form, assigned exactly once.

Why SSA?

  • In SSA, once a value is defined, it is immutable. Any new value requires a new name.
  • This makes it easy for compilers to follow the definition-use chain of each value, which is crucial for optimizations such as dead code elimination and constant propagation.
  • In the example, %z.0 is defined once and used consistently. Without SSA, z would have multiple assignments, making analysis more complex.

mem2reg Optimization

  • When LLVM IR is generated at -O0 (no optimizations), variables may initially appear as alloca and store in memory.
  • LLVM’s mem2reg optimization pass promotes stack-allocated variables into registers, converting them into SSA values.
  • This includes inserting φ-nodes where necessary, ensuring later optimization passes can work on pure SSA form.

In Summary…

  • SSA ensures that each value is defined once and never reassigned.
  • Phi nodes are a special construct used to reconcile values from different control-flow paths.
  • SSA simplifies value tracking and transformations, providing the foundation for LLVM’s powerful optimizations.

Updated: