What are the disadvantages of using SSA form?

Question

SSA form is common intermediate representation used in compilers where all variables are assigned to exactly once. It greatly helps with a myriad of optimizations, such as constant folding, dead code elimination, and redundancy elimination. With these advantages, there must be some disadvantages to using it. What are they?

Answer 1

Things that are not disadvantages

We'll start with some things that are sometimes considered to be disadvantages, but actually aren't. They may not be advantages, but they just aren't problems, or are problems that have convenient solutions.

Transforming to SSA form

Dominance frontier algorithms (e.g. Cytron et al) do produce minimal SSA form efficiently, at the cost of algorithmic complexity and a surprising amount of subtlety.

However, modern algorithms exist that are much simpler, and also have the advantage that SSA form can be constructed during IR building rather than as a post-pass. See, for example, Braun et al.

Transforming from SSA form

SSA form was originally considered to be an intermediate form that would then be "undone" for backend passes such as code generation, register allocation, and code scheduling.

Modern superscalar CPUs have made code scheduling even more important than it was in the 1990s, and so since it has to be done anyway, flattening SSA form and instruction scheduling can be the same thing, and spilling and register allocation can be done after scheduling.

This is such a powerful approach that many modern compilers don't have or need a general peephole optimisation pass; it can all be handled by adding more tiles to instruction selection.

Things that are disadvantages

Phi nodes are special

For all the advantages of SSA form, phi nodes can be a pain to handle correctly.

Phi nodes are sometimes like other nodes, and sometimes not like other nodes. Any optimisation pass which transforms SSA into SSA must, in general, treat phi nodes as a special case.

That they always appear at the start of a basic block is just one of many issues.

Maintaining SSA form after performing certain kinds of transformation can also be a pain, although algorithms have been developed over the last couple of decades that make this a little less painful.

State and memory models

Even 30 years later, we still don't have a single "right idea" about how to represent state modification in SSA form. The general idea is to pass some kind of token around, and possibly split state tokens if needed, but this can quickly get unwieldy.

Modern programmers are very interested in multithreading, and often rely on adherence to a documented memory model. Memory models dictate that certain operations must "happen before" other operations, especially in the presence of atomic operations, so that some results are visible in a known order when observed from a different thread on a different CPU.

None of this is impossible, but it's not always easy to represent "happens before" relationships in SSA form.

Multiple results

One of the basic assumptions of SSA form is that an expression produces one result, but in general this is not the case.

This is sometimes known as the "div/rem problem", because some CPUs (e.g. x86 and x64) have a division instruction that produces the quotient and the remainder. Asking for both is a scenario found in a large number of real programs:

int q = x / y;
int r = x % y;

Compilers such as GCC and LLVM go to some trouble to fuse quotient/remainder into a single operation if they can, but the resulting operation has two outputs. Again, it's possible to represent such things in SSA form, but it's not easy.

(Just as an aside, another example is x87's fsincos instruction, which does exactly what you think it does. Even on CPUs or GPUs without a combined sin/cos instruction, it often pays to fuse sin and cos when it can be done, so that domain checks and range reduction can be done once rather than twice. LLVM expends a lot of effort on this very common case.)

This is related to memory models, because many atomic operations such as atomic load (but not atomic store!) and compare/exchange produce both a result and a sequence token.

Having nodes with multiple outputs also complicates tiling-based instruction selection; classic algorithms for code generation on DAGs require more subtle handling if nodes can have multiple results.

And finally, instruction tiles themselves may also have multiple logical results! Apart from div/rem, consider an arithmetic instruction which also affects processor flags which you could then branch on.

/* On a CPU with arithmetic instructions that affect flags,
   it would be nice not to have an explicit test-against-zero
   instruction here, and just use the flags from the subtraction.
*/
x = a - b;
if (x > 0) {
   whatever();
}

The repeated predecessor problem

I don't know if this has an official name, but I'm calling it this.

One very common situation in real programs is if-then-else bodies that only contain variable-to-variable transfers.

int x;
if (condition()) {
    x = y;
}
else {
    x = z;
}

What the programmer would like is for this to be implemented as a conditional move instruction, if it's available on the target CPU.

A straightforward translation to SSA form would produce something like this:

block_1:
    c = condition();
    if (c) then goto block_2 else goto block_3;

block_2:
    x_2 := y;
    goto block_4;

block_3:
    x_3 := z;
    goto block_4;

block_4:
    x_4 := phi(x_2, x_3);
    # etc etc

This hides the real structure of the variable lifetimes, and means the compiler needs to do extra work analysing four different blocks.

You could start by removing one block:

block_1:
    c = condition();
    if (c) then goto block_4 else goto block_3;

block_3:
    x_3 := z;
    goto block_4;

block_4:
    x_4 := phi(y, x_3);
    # etc etc

And that would certainly help, although it's not clear which block to remove. Best of all would be to remove both blocks:

block_1:
    c = condition();
    if (c) then goto block_4 else goto block_4;

block_4:
    x_4 := phi(y, z);
    # etc etc

However, this is not valid SSA form! And it's hard to capture capture this in a variant of SSA form, because most algorithms that work on SSA form are not designed for the same block to appear more than once in a block's predecessors.

Alternatives to SSA form

So what to do instead?

Def-use chains

Don't forget this old standby! Def-use chains provide almost the same information as SSA form; the only catch is that they don't describe the paths along which definitions reach, which is what makes SSA form attractive in the first place.

This also doesn't give you a graph representation, with all the advantages that this implies. Still, depending on what optimisations you need, it might get you 90% of the way there with much less implementation effort.

Continuation-passing style

Some compiler writers have experimented with CPS, popular with compilers for functional languages, adapted to imperative languages. After all, if lambda is the ultimate goto, why not just represent gotos as lambdas in your IR? State-modification operations can also be implemented in a purely functional style with state tokens.

CPS is appealing because you do get all of the machinery developed for functional languages, but it isn't without its problems. After all, it isn't the graph representation that you might want for instruction selection and scheduling.

Basic block argument form

BBA form is a hybrid of SSA form and CPS, with the idea being that all values used by a basic block and the blocks that it dominates are passed explicitly.

You don't actually pass continuations as you would in CPS, but block invocations have essentially the same semantics as tail calls, so a lot of optimisation approaches that work on CPS work here, too.

The example above might look like this:

block_1:
    c = condition();
    if (c) then goto block_4(y) else goto block_4(z);

block_4(x):
    # use x here

Then within a basic block, you can have a SSA-like graph representation, only without phi nodes.

Basic block arguments may be where mainstream IR design is headed.

Answer 2

There's two ways of approaching this question. SSA form could be imposed on the user, like in pure functional languages where all variables are immutable (i.e. assigned only once each); or it could be an implementation detail of the compiler, so that code with mutable variables is transformed into SSA form during compilation.

In the former case, the question devolves into one about the disadvantages of "immutable languages"; this Q&A has plenty of good answers about that, so I'll address the latter, i.e. what are the downsides of using SSA form as an intermediate representation in a compiler?

• It is not trivial to actually perform the transformation, particularly for variables which are mutated in a loop, where the number of assignments to the variable is not statically known.
• Typically a second transformation back out of SSA form is also needed, where each SSA variable is associated with a register in such a way that the same register isn't used for two variables with overlapping lifetimes. Doing this optimally is not trivial; it's an NP-complete graph colouring problem even for a fixed number of registers (greater than 2).
• Some of the optimisations you mention are possible without SSA form; constant folding can be done when constructing an abstract semantic graph (ASG), and dead code elimination can be done by reachability analysis on the control-flow graph (CFG).

All of that said, if you want to achieve advanced low-level optimisations then you are better off compiling to a third-party intermediate representation (IR) such as LLVM IR, and then taking advantage of the optimising compiler which already exists for that IR; the existing optimising compiler can generally do far better than you can, except for domain-specific optimisations which rely on context that the backend doesn't know about.

In that case, the choice of whether to perform an SSA transform yourself is wholly determined by whether it's required by the IR you target. Some backends require you to do the transform yourself, while others will do it for you.

Answer 3

Here are some disadvantages:

• Increased memory usage: SSA form introduces additional variables, which can lead to increased memory usage. This is because each occurrence of a variable in the original program is represented by a new variable in SSA form, resulting in redundant storage.

• Increased compile time: The transformation from the original code to SSA form involves additional analysis and rewriting steps. This can increase the compilation time, especially for larger programs, as the compiler needs to perform more computations and maintain the SSA form throughout the optimisation process.

• Difficulty in handling mutable variables: SSA form is designed for immutable variables, where each variable is assigned exactly once. Handling mutable variables, such as those modified within loops or conditional branches, can be challenging in SSA form.