Why SSA Compilers?

I like this article a lot but it doesn't answer the question of "Why SSA?".

Sure, a graph representation is nice, but that isn't a unique property of SSA. You can have graph IRs that aren't SSA at all.

And sure, SSA makes some optimizations easy, but it also makes other operations more difficult. When you consider that, plus the fact that going into and out of SSA is quite involved, it doesn't seem like SSA is worth the fuss.

So why SSA?

Well, it turns out compilers have sequencing issues. If you view compilation as a series of small code transformations, your representation goes from A -> B, then B -> C, then C -> D and so on. At least, that's how it works for non-optimizing compilers.

For optimizing compilers however, passes want to loop. Whenever an optimization is found, previous passes should be run again with new inputs... if possible. The easiest way to ensure this is to make all optimizations input and output the same representation. So A -> B is no good. We want A -> A: a singular representation.

So if we want a singular representation, let's pick a good one right? One that works reasonably well for most things. That's why SSA is useful: it's a decently good singular representation we can use for every pass.

In the basic block with arguments variation there is no going in and out of SSA.

While iterating optimizations is nice, I think you missed the main point of SSA.

SSA makes dataflow between operations explicit; it completely eliminates the original (incidental) names from programs. Because of that, all dataflow problems (particularly forward dataflow problems) get vastly simpler.

With SSA you can throw basically all forward dataflow problems (particularly with monotonic transformations) into a single pass and they all benefit each other. Without SSA, you have every single transformation tripping over itself to deal with names from the source program and introducing transformations that might confuse other analyses.

I know we teach different compiler optimizations at different stages, but it's really important to realize that all of them need to work together and that having each as a separate pass is a good way to fail at the phase ordering problem.

And going further with the sea-of-nodes representation just makes them all more powerful; I really do recommend reading Cliff Click's thesis.