How was dataflow analysis performed before SSA?

Question

If we look at something like LLVM or the GNU Compiler Collection, Dalvik and many others, their intermediate representation (IR) uses SSA (Static Single Assignment form), as part of their Data-Flow Analysis, to essentially make sure that variables are immutable, so that they are easier to analyse and this makes it easier to implement optimisations that alter the way a computation is made, for example:

• Common subexpression elimination: it is easier to identify a common subexpression in an SSA language, since it's essentially a node in a binary tree, which can be compared, along with the daughter nodes.

• Constant folding/constant propagation: of course, if two variables are immutable, then it's much easier to prove that they're going to have exactly the same value.

• Dead store elimination: For each value calculated by a program, SSA shows exactly where it is used, so of course as a side effect it will also prove that it is not used (that is, it may be discarded).

And a similar bullet point could be made for many other kinds of optimisations that compilers perform, especially the ones that typically happen before the first passes of machine code generation.

The problem is that SSA was apparently only introduced in 1988, but I am sure that optimisations that alter the dataflow such as the above, were attempted long before then. They certainly have been mentioned before then, going by the citations on the Wikipedia page for global subexpression elimination for example. So what were common ways to approach this problem before 1988 when SSA was first mentioned?

---

Clarification: I'm not asking if there were compilers that didn't bother! There's a use-case for them as well, but what I'm interested in is some of the methods that compilers used to perform the dataflow analysis and how they allowed for the optimisation to take place.

Answer 1

The original FORTRAN I compiler, which was later expanded into the FORTRAN II compiler, did some pretty sophisticated optimizations. It was written in 1954–1956, back when many programmers thought it was impossible for a computer to generate machine code comparable in efficiency to what humans could write. Hence the FORTRAN team focused heavily on getting the compiler to produce an efficient object program.

One of the authors, Peter Sheridan, wrote an article in 1959 about the method used by the compiler to translate expressions (citation below). Here is what it says regarding common subexpression elimination:

The next stage of optimization involves the “elimination” of common subexpressions, so as to avoid redundant computation. This is accomplished in two steps:

1. Beginning with S_L, the last segment in Π̅(Φ), and for each i ≤ L, the set of all S_j with j < i is examined for the occurrence of an S_j = S_i. As soon as some S_j = S_j, S_j is eliminated from Π̅(Φ), and all references to S_j replaced by references to S_i, i.e., if some Ψ_k = j, then j is set equal to i.

2. Having eliminated, by (1), common segments, we now eliminate common subexpressions. Beginning with S_L, and for each i ≤ L, the set of all S_j with j < i is examined for the occurrence of more than one reference to S_i, i.e., the occurrence of Ψ_m, Ψ_n, with m ≠ n and Ψ_m = Ψ_n = i. If and only if this is the case is S_i tagged as a common subexpression (what we call a cs-type segment).

Procedures (1) and (2) together assure the elimination of outermost common subexpressions. Thus, if

Φ = A * (B * C) + SINF(A * (B * C)),

then

[Π̅(Φ) = (0,+,1)(0,+,14)(1,*,A)(1,*,7)(7,*,B)(7,*,C)(14,⊕,SINF)(14,⊕,16)(16,*,A) (16,*,22)(22,*,B)(22,*,C)].

Procedures (1) and (2) reduce Π̅ to

(0,+,16)(0,+,14)(14,⊕,SINF)(14,⊕,16)(16,*,A)(16,*,22)(22,*,B)(22,*,C),

with S₁₆ tagged as a cs-type segment, since Ψ₀¹ = Ψ₁₄² = 16.

Remember that this was before our modern ideas of how to implement programming languages. The formalization described in Sheridan's article is rather complicated, and I'm not going to try to explain the notation in this answer. The point is that early optimization techniques, from before we came up with things like SSA, were not necessarily ad hoc or bad or hacky. Quite a bit of thought and mathematical analysis went into the development of FORTRAN I.

Citation for the article:

P.B. Sheridan. The arithmetic translator-compiler of the IBM FORTRAN automatic coding system. Communications of the ACM, Volume 2, Number 2, February 1959, pages 9–21. (PDF)

See the Software Preservation Group's website for primary resources on implementations of other early languages. In many cases source code listings for compilers or interpreters are available.

• ALGOL: http://www.softwarepreservation.org/projects/ALGOL
• Lisp: http://www.softwarepreservation.org/projects/LISP

Regarding the first FORTRAN compilers, only FORTRAN II's source code seems to have survived; however, as I mentioned, FORTRAN II was derived directly from FORTRAN I, and the main changes were extensions. A listing of FORTRAN II can be found in a couple different forms here (courtesy, again, of the Software Preservation Group).

Answer 2

Quite frequently it wasn't.

When your compiler is running on a 286 with 512K of memory, using floppies for storage, the optimizations by the compiler are very localized if they exist at all. Frequently the compiler wasn't even bright enough to eliminate variables that were declared but never used, let alone ones that got assignments but were never read.

You know that saying 'C is a high-level assembly language'? That was very close to literally true in the early days. At that time the compilers pretty much translated statements from the language into an equivalent assembly form, assigned registers and memory locations on the stack as needed and called it a day. There simply wasn't CPU or storage for the compiler to get particularly intelligent.

Answer 3

I think the answer is the dataflow analysis part of the dragon book. Take common subexpression elimination for example, available expression analysis will be performed to achieve this optimization for non-SSA IR.