This article (and a number around it) miss the underlying point of SSA entirely.
SSA exists (or at least, was done) because of bitvector dataflow time bounds. All the other interesting reasoning about blah blah blah is mostly just people making up reasons they think people did stuff. It also promotes an NIH view of the world that didn't exist.
(CPS wasn't even introduced until 1976, and i'm not aware of anybody proving any of the nice properties of SSA about it until after SSA existed. If someone has a reference otherwise, i'd love to see it)
I can state this with such flat assertion because Zadeck was my officemate at IBM for a few years, so he told me why it did it. He hated staring at bitvectors because he is dyslexic. Motivation is funny sometimes.
For a large class of problems, bitvector dataflow can be done in O(N) bitvector operations. However, each operation/iteration requires N time to perform the bitvector union/intersection/whatever.
Hence the total time bound was N^2 overall.
That was thought to be the end of it.
There were elimination dataflow approaches still left open, but these are complicated.
(Wegman was, among other things, an expert in elimination based dataflow methods)
There were approaches to incremental dataflow, and complex ways to try to work around this for specific problems.
Zadeck's thesis was on ways to start to approach breaking these barriers with techniques different than used before.
You can see most of SSA in it:
https://scholarship.rice.edu/handle/1911/15877
In fact, when he initially suggested it, he was told it was "impossible and i can prove it", but he explained, correctly, that Tarjan/et al proved a very specific thing, and he was using a way not encumbered by those proofs.
(The later parts of this story reduce to "two groups of IBM researchers discovered the problems they were trying to solve were the same even though they appear different". I'll skip this)
In practice, SSA was the first real approach that made it easy and trivial to break bitvector bound for large classes of dataflow problems (constant propagation, etc).
That is why it is used in compilers.
As mentioned, despite this article (and a few others) claiming CPS did it first, i'm not aware of anyone in CPS land claiming or proving anything related to this until well after SSA became popular.
It's O(N^2) where N is the number of blocks (vertices).
(In a complete graph of N vertices, there are N^2 edges)
Papers switch between the two (elimination based methods are often in terms of edges, non-elimination in terms of number of blocks)
They do in fact take constant time if they are constant size independent of program, but they are often not.
They are usually linear in the number of variables/blocks.
For those linear in the number of blocks, the total time bound comes to N^3 (and N^2 log N for a class of problems).
For those linear in the number of variables O(V*N^2).
For those constant sized, the time bounds are correct since the operations take constant time.
(and FWIW: This group of people has probably forgotten more about program analysis than the rest of us will ever know)
SSA exists (or at least, was done) because of bitvector dataflow time bounds. All the other interesting reasoning about blah blah blah is mostly just people making up reasons they think people did stuff. It also promotes an NIH view of the world that didn't exist.
(CPS wasn't even introduced until 1976, and i'm not aware of anybody proving any of the nice properties of SSA about it until after SSA existed. If someone has a reference otherwise, i'd love to see it)
I can state this with such flat assertion because Zadeck was my officemate at IBM for a few years, so he told me why it did it. He hated staring at bitvectors because he is dyslexic. Motivation is funny sometimes.
For a large class of problems, bitvector dataflow can be done in O(N) bitvector operations. However, each operation/iteration requires N time to perform the bitvector union/intersection/whatever. Hence the total time bound was N^2 overall.
It was proven in the early to mid seventies this was the best you can do by Tarjan, when he wasn't busy efficiently solving every other graph problem known to CS at the time: http://i.stanford.edu/pub/cstr/reports/cs/tr/76/547/CS-TR-76...
That was thought to be the end of it. There were elimination dataflow approaches still left open, but these are complicated. (Wegman was, among other things, an expert in elimination based dataflow methods)
There were approaches to incremental dataflow, and complex ways to try to work around this for specific problems.
Zadeck's thesis was on ways to start to approach breaking these barriers with techniques different than used before. You can see most of SSA in it: https://scholarship.rice.edu/handle/1911/15877
In fact, when he initially suggested it, he was told it was "impossible and i can prove it", but he explained, correctly, that Tarjan/et al proved a very specific thing, and he was using a way not encumbered by those proofs.
(The later parts of this story reduce to "two groups of IBM researchers discovered the problems they were trying to solve were the same even though they appear different". I'll skip this)
In practice, SSA was the first real approach that made it easy and trivial to break bitvector bound for large classes of dataflow problems (constant propagation, etc).
That is why it is used in compilers.
As mentioned, despite this article (and a few others) claiming CPS did it first, i'm not aware of anyone in CPS land claiming or proving anything related to this until well after SSA became popular.