TC-S, FAQ

Is SSA form really efficient?

As SSA form adds a lot of temporaries to prevent redefinitions, the question of its efficiency is a valid one.

For simple programs, SSA is too time consuming to be worth it. It becomes efficient when we have large programs, such as those usually seen in real life and which require a lot of optimizations.

SSA allows for more efficient optimizations than on a simple LIR program, and simplifies dataflow analysis.

Are there other forms used for optimizations?

SSA is the most common form of IR used for optimizing imperative languages, but it is not the only one. It is widely used in LLVM IR, GCC GIMPLE, etc.

Continuation-passing style (CPS) or A-Normal form (ANF) are two forms used by compilers for functional languages to make optimizations. They are widely used in ML, F#, partially in Haskell, etc.

Ownership SSA (O-SSA) is a specialized SSA form used primarily in Swift [1]. It is a refinement of SSA that tracks ownership and lifetime of values, especially around move-only (no copy) semantics, copying, and borrowing concepts, all important for memory safety and optimization in modern languages. Rust MIR (Mid-level IR) also serves a similar purpose.

SSA vs DSA

Static Single Assignment (SSA) form is a program representation where each variable is statically assigned exactly once in the program text/IR.

Dynamic Single Assignment (DSA), enforces the single assignment property at runtime rather than on the program text/IR. In DSA, each memory location can be written to exactly once during execution. This differs significantly from SSA.

Consider a simple loop:

sum = 0
for (i = 0; i < 10; ++i)
  {
    sum += i
  }

SSA allows dynamic re-assignment via Phi-Nodes:

i_0 = 0
sum_0 = 0
loop:
  i_1 = φ(i_0, i_2)
  sum_1 = φ(sum_0, sum_2)
  sum_2 = sum_2 + i_1
  i_2 = i_1 + 1
  if (i_1 < 10) goto loop

DSA would use a different memory location for each variable version. Assuming an array representation for each variable:

i[0] = 0
sum[0] = 0

// j in [1; 9]
i[j] = i[j - 1] + 1
sum[j] = sum[j - 1] + i[j]

Footnotes