<p><a href="https://en.wikipedia.org/wiki/Static_single-assignment_form" rel="noreferrer">SSA form</a> 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?</p>

<intermediate-representation><static-single-assignment>
What are the disadvantages of using SSA form?
<h2>Things that are not disadvantages</h2>
<p>We'll start with some things that are sometimes considered to be disadvantages, but actually aren't. They may not be <em>advantages</em>, but they just aren't problems, or are problems that have convenient solutions.</p>
<p><strong>Transforming to SSA form</strong></p>
<p>Dominance frontier algorithms (e.g. <a href="https://www.cs.utexas.edu/%7Epingali/CS380C/2010/papers/ssaCytron.pdf" rel="noreferrer">Cytron et al</a>) do produce minimal SSA form efficiently, at the cost of algorithmic complexity and a surprising amount of subtlety.</p>
<p>However, modern algorithms exist that are much simpler, and also have the advantage that SSA form can be constructed <em>during</em> IR building rather than as a post-pass. See, for example, <a href="https://link.springer.com/chapter/10.1007/978-3-642-37051-9_6" rel="noreferrer">Braun et al</a>.</p>
<p><strong>Transforming from SSA form</strong></p>
<p>SSA form was originally considered to be an intermediate form that would then be &quot;undone&quot; for backend passes such as code generation, register allocation, and code scheduling.</p>
<p>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.</p>
<p>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.</p>
<h2>Things that are disadvantages</h2>
<p><strong>Phi nodes are special</strong></p>
<p>For all the advantages of SSA form, phi nodes can be a pain to handle correctly.</p>
<p>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.</p>
<p>That they always appear at the <em>start</em> of a basic block is just one of many issues.</p>
<p>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.</p>
<p><strong>State and memory models</strong></p>
<p>Even 30 years later, we still don't have a single &quot;right idea&quot; 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.</p>
<p>Modern programmers are very interested in multithreading, and often rely on adherence to a documented memory model. Memory models dictate that certain operations must &quot;happen before&quot; 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.</p>
<p>None of this is impossible, but it's not always easy to represent &quot;happens before&quot; relationships in SSA form.</p>
<p><strong>Multiple results</strong></p>
<p>One of the basic assumptions of SSA form is that an expression produces one result, but in general this is not the case.</p>
<p>This is sometimes known as the &quot;div/rem problem&quot;, 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:</p>
<pre class="lang-c prettyprint-override"><code>int q = x / y;
int r = x % y;
</code></pre>
<p>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 <em>possible</em> to represent such things in SSA form, but it's not <em>easy</em>.</p>
<p>(Just as an aside, another example is x87's <code>fsincos</code> 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.)</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<pre class="lang-c prettyprint-override"><code>/* 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 &gt; 0) {
   whatever();
}
</code></pre>
<p><strong>The repeated predecessor problem</strong></p>
<p>I don't know if this has an official name, but I'm calling it this.</p>
<p>One very common situation in real programs is if-then-else bodies that only contain variable-to-variable transfers.</p>
<pre class="lang-c prettyprint-override"><code>int x;
if (condition()) {
    x = y;
}
else {
    x = z;
}
</code></pre>
<p>What the programmer would like is for this to be implemented as a conditional move instruction, if it's available on the target CPU.</p>
<p>A straightforward translation to SSA form would produce something like this:</p>
<pre><code>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
</code></pre>
<p>This hides the real structure of the variable lifetimes, and means the compiler needs to do extra work analysing four different blocks.</p>
<p>You could start by removing one block:</p>
<pre><code>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
</code></pre>
<p>And that would certainly help, although it's not clear which block to remove. Best of all would be to remove <em>both</em> blocks:</p>
<pre><code>block_1:
    c = condition();
    if (c) then goto block_4 else goto block_4;

block_4:
    x_4 := phi(y, z);
    # etc etc
</code></pre>
<p>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.</p>
<h2>Alternatives to SSA form</h2>
<p>So what to do instead?</p>
<p><strong>Def-use chains</strong></p>
<p>Don't forget this old standby! Def-use chains provide <em>almost</em> 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.</p>
<p>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.</p>
<p><strong>Continuation-passing style</strong></p>
<p>Some compiler writers have experimented with CPS, popular with compilers for functional languages, adapted to imperative languages. After all, if <a href="https://dspace.mit.edu/handle/1721.1/5753" rel="noreferrer">lambda is the ultimate goto</a>, 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.</p>
<p>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.</p>
<p><strong>Basic block argument form</strong></p>
<p>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.</p>
<p>You don't actually <em>pass</em> 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.</p>
<p>The example above might look like this:</p>
<pre><code>block_1:
    c = condition();
    if (c) then goto block_4(y) else goto block_4(z);

block_4(x):
    # use x here
</code></pre>
<p>Then <em>within</em> a basic block, you can have a SSA-like graph representation, only without phi nodes.</p>
<p>Basic block arguments may be where mainstream IR design is headed.</p>

CC BY-SA 4.0
2023-06-09T01:46:13.053Z
2023-06-09T04:23:31.997Z
2023-06-09T04:23:31.997Z
Pseudonym
CC BY-SA 4.0
2023-06-14T10:52:58.977Z
For the multiple results of an operation, it's perfectly possible (and quite efficient) to allow tuple types for the virtual SSA registers.

I worked on a [generalised SSA](https://combinatorylogic.github.io/mbase-docs/ssa-fold.pdf) IR that allows to abstract from any particularities of instructions, types and whatnot, handling only the SSA aspect of the code representation.
SK-logic
CC BY-SA 4.0
2023-06-14T13:34:46.310Z
That certainly works. The sea of nodes uses a similar technique of introducing projection nodes. I'm curious how well instruction selection from SSA form works?
Pseudonym
CC BY-SA 4.0
2023-06-14T15:45:17.337Z
LLVM is using an intermediate DAG representation, and, curiously, they get out of SSA when already in DAG, not before. One reason for doing this is that SSA can make register allocation heuristics a bit easier (though it's up to discussion if the result is closer to optimal than for the more heavy heuristics).

In my ([significantly simpler](https://github.com/combinatorylogic/soc/blob/devel/backends/c2/emit.hl)) backends I just do instruction selection on a flat 3-address code after getting out of an SSA, and then do register allocation separately.
SK-logic
<p>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.</p>
<p>In the former case, the question devolves into one about the disadvantages of &quot;immutable languages&quot;; <a href="https://languagedesign.stackexchange.com/q/444/89">this Q&amp;A</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?</p>
<ul>
<li>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.</li>
<li>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 <a href="https://en.wikipedia.org/wiki/Graph_coloring" rel="noreferrer">graph colouring problem</a> even for a fixed number of registers (greater than 2).</li>
<li>Some of the optimisations you mention are possible without SSA form; constant folding can be done when constructing an <a href="https://en.wikipedia.org/wiki/Abstract_semantic_graph" rel="noreferrer">abstract semantic graph</a> (ASG), and dead code elimination can be done by reachability analysis on the <a href="https://en.wikipedia.org/wiki/Control_flow_graph" rel="noreferrer">control-flow graph</a> (CFG).</li>
</ul>
<p>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 <a href="https://en.wikipedia.org/wiki/LLVM#Intermediate_representation" rel="noreferrer">LLVM IR</a>, 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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-06-08T16:34:32.117Z
2023-06-08T16:34:32.117Z
kaya3
CC BY-SA 4.0
2023-06-08T16:49:35.517Z
Yes I meant SSA as in internal IR. I'll clarify in the question.
Seggan
CC BY-SA 4.0
2023-06-08T16:51:57.087Z
@Seggan I don't think there was anything wrong with the question; and the considerations about SSA form (used internally in the compiler) are still different for "immutable languages" because either no transform will be required, or the transform will be much easier to implement.
kaya3
<p>Here are some disadvantages:</p>
<ul>
<li><p><strong>Increased memory usage:</strong> 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.</p>
</li>
<li><p><strong>Increased compile time:</strong> 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.</p>
</li>
<li><p><strong>Difficulty in handling mutable variables:</strong> 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.</p>
</li>
</ul>

CC BY-SA 4.0
2023-06-08T16:31:08.343Z
2023-06-08T16:31:08.343Z
The Thonnu
CC BY-SA 4.0
2023-06-09T17:38:22.130Z
I'm not sure if I agree with this... I'd say that compilation times are actually a selling point of SSA, because many optimizations are faster to perform in SSA. Mutable variables are also fine, that's what the phi nodes are for.
hugomg
CC BY-SA 4.0
2023-06-14T10:50:16.433Z
SSA is designed specifically to handle mutable variables. You would not need an SSA otherwise, you'd already be in an SSA if everything was immutable.
SK-logic
# What are the disadvantages of using SSA form?
Posted by: username_0 on 2023-06-08
[SSA form](https://en.wikipedia.org/wiki/Static_single-assignment_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?
**Tags:** intermediate-representation static-single-assignment
---
## 3 answers
### Answer by username_1 on 2023-06-09. Score: 14
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.
> **Comments:**
> **username_2** (2023-06-14): For the multiple results of an operation, it's perfectly possible (and quite efficient) to allow tuple types for the virtual SSA registers.

I worked on a [generalised SSA](https://combinatorylogic.github.io/mbase-docs/ssa-fold.pdf) IR that allows to abstract from any particularities of instructions, types and whatnot, handling only the SSA aspect of the code representation.  
> **username_1** (2023-06-14): That certainly works. The sea of nodes uses a similar technique of introducing projection nodes. I'm curious how well instruction selection from SSA form works?  
> **username_2** (2023-06-14): LLVM is using an intermediate DAG representation, and, curiously, they get out of SSA when already in DAG, not before. One reason for doing this is that SSA can make register allocation heuristics a bit easier (though it's up to discussion if the result is closer to optimal than for the more heavy heuristics).

In my ([significantly simpler](https://github.com/combinatorylogic/soc/blob/devel/backends/c2/emit.hl)) backends I just do instruction selection on a flat 3-address code after getting out of an SSA, and then do register allocation separately.  
---
### Answer by username_3 on 2023-06-08. Score: 5
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](https://languagedesign.stackexchange.com/q/444/89) 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](https://en.wikipedia.org/wiki/Graph_coloring) 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](https://en.wikipedia.org/wiki/Abstract_semantic_graph) (ASG), and dead code elimination can be done by reachability analysis on the [control-flow graph](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/LLVM#Intermediate_representation), 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.
> **Comments:**
> **username_0** (2023-06-08): Yes I meant SSA as in internal IR. I'll clarify in the question.  
> **username_3** (2023-06-08): @Seggan I don't think there was anything wrong with the question; and the considerations about SSA form (used internally in the compiler) are still different for "immutable languages" because either no transform will be required, or the transform will be much easier to implement.  
---
### Answer by username_4 on 2023-06-08. Score: 2
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.
> **Comments:**
> **username_5** (2023-06-09): I'm not sure if I agree with this... I'd say that compilation times are actually a selling point of SSA, because many optimizations are faster to perform in SSA. Mutable variables are also fine, that's what the phi nodes are for.  
> **username_2** (2023-06-14): SSA is designed specifically to handle mutable variables. You would not need an SSA otherwise, you'd already be in an SSA if everything was immutable.  
---
