First, I would like to introduce myself by saying that I am the Zadeck
of the "Wegman and Zadeck" that invented SSA form. Second, I would
like to say that writing optimizing compilers back then was very hard:
optimizing compilers were only produced for the large mainframes from
IBM, CDC, Univac, or DEC. They were expensive to develop and were
only available on machines that were used for scientific computing.
There were no optimizing compilers for PCs - PCs were too slow and too
small for for the number crunching needed for scientific computing.
The analysis techniques in these optimizing compilers were based on a
series of papers, primarily by Fran Allen, John Cocke, Ken Kennedy,
Jacob Schwartz and Jeffery Ullman. There were many other people
involved in the area. Googling these names, and looking at their
bibliographies will find most of the early work because the area was
very small. Some textbooks from that time are listed at the end of
this posting.
Briefly, the idea behind many of these techniques was to analyze the
program enough to produce a set of propositions that you wished to
prove. These facts would be represented as positions in a vector.
Simple facts, that were either true or false could be represented as a
single bit packed into a word vector, more complex facts took more
space. You then needed to construct a function for every point in the
program that modeled how the set of facts changed by execution of that
program location. Then you propagated the information around the
program until you reached a fixed point. There are a large number of
papers devoted to how you can set up the vectors to solve particular
problems and perform this propagation efficiently.
Asymptotically, the techniques are very slow. The general forms of
the techniques took between N log(N) and N**2 vector operations over
the program and the size of the vectors scaled with the size of the
program. Specialized techniques were developed that used only N
vector operations but were only worked on a restricted class of
programs. SSA form is almost always always linear in the size of the
program so as programs and machines got bigger, it became a better
fit. Also, SSA form is produced once during the compilation and kept
up to date as the program is transformed. Data flow analysis has to
be redone for every optimization pass. Today's optimizing compilers
may perform up to 100 passes. It was not unusual in these early
compilers for a program that was only 100 lines long to take minutes
to compile with optimization.
You can still see a use of dataflow analysis in a modern project in
the GCC compilers. The high-level, machine independent, optimizations
are preformed using SSA form, but the low-level machine dependent
backends perform optimizations driven by dataflow analysis. GCC
predates SSA form becoming mainstream. It was never consided cost
effective to update the backends given the large number of legacy
architectures that GCC supports.
The following books provide good descriptions of the area. The first
one is "the Dragon Book". It was an undergraduate textbook and was
printed in large quantities. It is likely available on the used
market. The other two are deeper treatments of the area are likely
impossible to find unless someone has posted them online.
@BOOK { Aho86a,
Title = "Compilers: Principles, Techniques, and Tools ",
Author = "Aho, A. V. and Sethi, R. and Ullman, J. D.",
Publisher = AddisonWesley,
Year = 1986,
}
@BOOK { Hecht77a,
Title = "Flow Analysis of Computer Programs",
Author = "Hecht, M. S.",
Publisher = Elsevier,
Year = 1977,
}
@BOOK { Muchnick81a,
Title = "Program Flow Analysis",
Editor = "Muchnick, S. S. and Jones, N. D.",
Publisher = "Prentice-Hall",
Year = 1981,
}
int foo[3 + 4];.