The blog post doesn't mention integer overflows. If integers wrap around on overflow, min(INT_MIN - 1, 0 - 1) = -1 but min(INT_MIN, 0) - 1 = INT_MAX. However, in PHP the values are converted to floats, which should preserve the equation min(a -c, b - c) = min(a, b) - c.
SSA is standard for the middle end but not for the backend. According to my knowledge there are only two compilers with an SSA-based backend: libFirm (www.libfirm.org) and the Go compiler.
Obviously no backend is in SSA format after register allocation, but before allocation what do other compilers use if not SSA? Is there some kind of low-level LLVM and GCC IR separate from the front-end and middle one? That isn't in SSA?
I know that the C2 and Graal compilers are SSA all the way until register allocation is done.
You can stay in SSA form even after register allocation. In libFirm the assigned registers are just attributes of the values in the SSA representation. There was some additional discussion regarding this in [1].
GCC uses a separate representation (RTL) for their backend that is not in SSA form [2]. LLVM stays in SSA form for some backend phases but lowers the SSA form before register allocation (as also mentioned in [1]).
I took a quick look at the C2 and the Graal compiler. C2 seems to use LLVM's code generator (and thus lowers SSA before register allocation) but Graal seems to support SSA-based register allocation, nice.
Yep. A while ago I found myself needing to recompile the Linux kernel for Android, and I was amazed at how fast the build was (I think I last built a kernel in the 90s). It took a lot less time than it takes Android to start up!
After libfirm [1], the Go compiler now seems to be the second mature compiler with an SSA-based backend. I hope more compilers will follow.
I missed some references to corresponding papers in the source code. For instance, is the register allocator an implementation of "Linear Scan Register Allocation on SSA Form" [2]?
Also some facts mention in comments [3] are a bit scary but I guess this will be resolved over time.
Most of LLVM's backend is SSA, actually.
At some point it lowers out of SSA, but you have to do that at some point anyway.
It happens that LLVM does instruction selection and scheduling on SSA but not regalloc (it does phi elimination before regalloc, though uses ssa based liveness info in regalloc)
My take: Who cares? If someone wants to make register allocation SSA based, and demonstrates code or speed or maintenance or whatever benefits, great.
There are theoretical benefits, but in practice, LLVM does pretty well with it's current scheme.
Because of this, it's not really near the top of any todo list, nor should it be.
> At some point it lowers out of SSA, but you have to do that at some point anyway.
libfirm never goes out of SSA (since it uses a graph-based representation it's simply impossible: the data dependency edges need one target). It converts the programm to CSSA and assigns the same register to all phi operands. When finally emitting the program, phi nodes emit nothing.
Okay, sure, this is pretty much the same thing for a graph based IR.
You can argue this isn't a form of lowering, but in practice, it doesn't matter.
Note that your claim "(since it uses a graph-based representation it's simply impossible: the data dependency edges need one target)"
is wrong :)
SSA also requires that things have a single, unique, reaching definition.
The fact that the graph edges have one target does not guarantee this (it is instead a representation that requires this for correctness)
Open64 is another compiler with factored use-def chains like this (though the rest is not graph based), and has the same issue -
If you hoist something to various valid points (IE across existing live ranges), it's possible to generate multiple reaching definitions. This is because the dataflow definition of reaching definitions is not "whatever is on the end of this graph edge". So the fact that the graph edges only point to one of those definitions just makes the graph edges wrong.
So it's not impossible, but libfirm avoids it or performs the necessary phi insertion in various places to avoid creating invalid SSA for the representation it has.
(Note: It is possible to have IR's where the only ordering is a data dependence ordering, and so the graph is the source of truth and where it points is where it points. There are also representations where the control flow is implied by the graph nodes. In these representations, what you say would be correct. From what i know of libfirm, it has basic blocks and control flow edges, and it uses that to give some ordering. In this world, it's possible to screw up the SSA properties with pretty simple operations, and make the graph no longer correct)
> So it's not impossible, but libfirm avoids it or performs the necessary phi insertion in various places to avoid creating invalid SSA for the representation it has.
It's impossible to have one edge pointing to multiple reaching definitions.
Of course, but I think you missed the point of what i said.
Which was: It's possible to get into situations where that that node could have multiple possible reaching definitions, even if it only points to one at a given time. That is still not SSA.
In that case, the edge is just wrong, even if it only points to one arbitrarily selected possible reaching definition.
In short: Your argument is "it's SSA because the data structures only allow for a single reaching definition".
This is not right. If i don't insert phi nodes, and just have the IR point at random reaching definitions, it's not magically SSA, because there is not actually a unique reaching definition for each point, it just happens you've pointed the edges at arbitrarily selected reaching definitions (IE made the graph wrong :P)
> There are theoretical benefits, but in practice, LLVM does pretty well with it's current scheme.
I think having a decoupled spilling phase is nice feature of the SSA-based scheme. However, I don't say that LLVM (or GCC) should switch to the SSA-based scheme. I just appreciate that the Go compiler switched to the SSA-based scheme, because it may bring some new insights to the research community.
SSA is not a pre-req to a decoupled spilling phase :)
In fact, the guy who wrote LLVM's current register allocation did his thesis on decoupled SSA register allocation - http://www.theses.fr/2012ENSL0777
But he still decided not to go that way in LLVM when decoupling regalloc from spilling.
"because it may bring some new insights to the research community."
No offense, but this seems pretty unlikely. It's been 10 years and the number of production optimizing compilers that use SSA based regalloc (for example) is still hovering close to 0.
Sad (because i helped fund a ton of that research), but true.
The same thing is sadly true of libfirm. While a really impressive piece of work, it hasn't spurred much that i can see ...
I've written a graph-coloring register assigner that stayed in SSA form in an optimizing compiler for the Cray X1 and BlackWidow architectures. The key idea is to treat each phi function as being a copy, perhaps coalescable, located at the foot of each of the block's predecessors. Works great.
As stated in [1] they use a variant of "Simple and Efficient Construction of Static Single Assignment Form" [2], which does not require a dominator tree (or a liveness analysis).
