The Single Static Assignment form was only created in 1988, which is apparently so late that compilers are still discovering it (and the optimizations it enables) as some novelty today.
(Never even mind the Single Static Information form.)
I wonder if part of the reason SSA is not implemented from the start by many compilers, is precisely because it came too late to be included in seminal works like A Catalogue of Optimizing Transformations; so people that rely on those works as a canon of "classes of optimization techniques that work" won't even be aware of it.
-----
More snarky: the earliest dataflow analysis paper I can find is from 1972. :)
I think SSA is not implemented from the start by many compilers is because many compilers are 30+ years old.
More seriously, my recollection (having been about 20 years since I last took a compilers course) is that it took a while for even researchers to be convinced of the advantages of SSA, as the transformation causes a quadratic blowup in code size for the worst case (but it turns out to be less in real-world cases).
Also Sussman & Steele proposed CPS in 1975 which is closely related to SSA.
A 30-year-old compiler would still have come out in 1990, well after SSA-based optimizations were discovered. But maybe I'm expecting too much in thinking that the author of a flagship optimizing compiler should be up-to-date on CS research in compiler optimization, before deciding the architecture of their compiler.
(Also, plenty of the compilers and/or JITs that I'm talking about are far newer. The first attempt to get a JVM to use SSA optimization during JIT — within SafeTSA — only occurred in 2000. Such an approach was copied by pretty much every JVM implementation by 2005, suggesting that a legacy of incompatible architecture was never the problem, but rather that JVM implementors just didn't think it was a worthwhile technique until they saw it demonstrated for their particular workloads.)
CPS is closely theoretically related to SSA (it carries equivalent information across lexical boundaries) but CPS isn't a basis for optimization transforms in the same way that SSA is. You can't hoist loop invariants using CPS... as far as I know, at least.
> But maybe I'm expecting too much in thinking that the author of a flagship optimizing compiler should be up-to-date on CS research in compiler optimization, before deciding the architecture of their compiler.
In 1990 I don't think SSA was broadly considered to be the basis of a good optimizing compiler the way it is today. So the "author of a flagship optimizing compiler" would be gambling on an unknown that looked good in a couple new papers. The Cytron paper on how to efficiently compute it came out in 1991. So SSA was still a WIP.
It wasn't really until the late 1990s IMO, that SSA became widespread and into the 2000s when it became the standard.
Someone else already replied to your first paragraph, so I'll reply to your second:
The safe TSA papers from 2000-2001 were the papers that showed that SSA was practical in a JIT environment. The fact that this approach was adopted less than 5 years after those papers come out suggest that compiler authors are in fact reading research papers.
Rearchitecting a production JIT to use a different IR for theoretical gains when nobody's demonstrated those gains on a toy JIT is high risk and demonstrating those gains on a toy JIT is research, not development.
I think a lot of now big, "professional" projects started as people's non serious hobby projects.
If you just want to write a compiler for fun, I can understand not reading up on state of the art theory beforehand. And then it's accidentally actually useful to other people and it's too far into development to change the fundamental architecture.
Agree. I worked on MIMD systems in the 1980s that seemed cutting edge at the time. Then in 2001 I toured the Concrete, ND phased array radar facility where I saw a 16-cpu machine built by Western Electric in 1969 that had essentially the same architecture.
I definitely do not have the chops for this, but I would love to see some sort of visualization that traces major, seemingly-modern computing ideas to their roots.
