What is Static Single Assignment ?

Have you written code like this ?

int add(int a, int b){
    return a + b
}

into weired form like below:

define i32 @add(i32 %a, i32 %b) #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  store i32 %a, i32* %1, align 4
  store i32 %b, i32* %2, align 4
  %3 = load i32, i32* %1, align 4
  %4 = load i32, i32* %2, align 4
  %5 = add nsw i32 %3, %4
  ret i32 %5
}

This is lowering expression of a + b into what called Static Single Assignment (example above is LLVM SSA form), so what is that:

A program is defined to be in SSA form if each variable is a target of exactly one assignment statement in the program text.

In simple way, SSA can be done in simple algebra operation:

x = 3
y = x * 2
y = 4
z = x * y

Turn into only single and immutable variable only form:

x1 = 3
y1 = x1 * 2
y2 = 4
z = x1 * y2

All variable is unique and it maintain its data movement. it wouldn't be confusing to determine whether y is x * 2 or 4, (CPU do this math rather than us, but us nescessary to verify it correctness)

In it application, This form is commonly use in compiler when it generate Intermediate Representation from evaluation model of Abstract Syntax Tree that had been examined by various semantic analysis, type system checking, and so on.

So instead doing this:

  • f(a) = a + 8 (syntaxs form)

  • Fn(a, Add(VarCall(a), Num(8))) (AST form)

  • /a.+ a 8 (Lambda Calculi form)

define i32 @fn_a(i32 %a) {
  %1 = alloca i32, align 4
  store i32 %a,i32* %1, align 4
  %2 = load i32, i32* %2, align 4
  %3 = add nsw i32 %2, 8, align 4
  ret i32 %3
}
  • (LLVM SSA form)

In LLVM SSA form, we see there alloca, store, load which mean this memory operation to handle memory for storing and loading value into operation. Also in this form we could see where and when data is moving.

This only basic form that I know so far, the more that can be found at : SSA Book.

And if you want to hack it more, Godbolt Compiler Explorer will huge help for you.