←back to thread

Why SSA Compilers?

(mcyoung.xyz)
158 points transpute | 2 comments | | HN request time: 0.022s | source
Show context
rdtsc ◴[] No.45674959[source]
I like the style of the blog but a minor nit I'd change is have a definition what SSA is right at the top. It discusses SSA for quite a while "SSA is a property of intermediate representations (IRs)", "it's frequently used" and only 10 paragraphs down actually defines what SSA is

> SSA stands for “static single assignment”, and was developed in the 80s as a way to enhance the existing three-argument code (where every statement is in the form x = y op z) so that every program was circuit-like, using a very similar procedure to the one described above.

I understand it's one of those "well if you don't know what it is, the post is not for you" but I think it's a nice article and could get people who are not familiar with the details interested in it

> The reason this works so well is because we took a function with mutation, and converted it into a combinatorial circuit, a type of digital logic circuit that has no state, and which is very easy to analyze.

That's an interesting insight, it made sense to me. I only dealt with SSA when decompiling bytecode or debugging compiler issues, and never knew why it was needed, but that sort of made it click.

replies(5): >>45675058 #>>45675212 #>>45676248 #>>45676424 #>>45679311 #
strbean ◴[] No.45675212[source]
I learned a bit about SSA in a compiler course. Among many other things, it is crucial for register assignment. You want to know each distinct value that will exist, and the lifetimes of those values, in order to give each a register. Then, if have more distinct values existing at one time than you have registers, you have to push stuff to the stack.
replies(1): >>45676308 #
1. tylerhou ◴[] No.45676308[source]
It is not critical for register assignment -- in fact, SSA makes register assignment more difficult (see the swap problem; the lost copy problem).

Lifetime analysis is important for register assignment, and SSA can make lifetime analysis easier, but plenty of non-SSA compilers (lower-tier JIT compilers often do not use SSA because SSA is heavyweight) are able to register allocate just fine without it.

replies(1): >>45678305 #
2. tonfa ◴[] No.45678305[source]
One nice thing is that it makes register assignment polynomial (the coloring of SSA variables graph is polynomial since it's not an arbitrary graph).