7

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.

Improve this question
  • I think the answer is "with difficulty". In the past, compilers were worse at optimising code. SSA is one to the technologies that improved them. – JeremyP Feb 6 '19 at 10:52
  • The advantage of SSA is that is it one technique that can be used to solve several different problems, e.g. constant propagation, dead code elimination, strength reduction, register allocation, etc. There effective practical methods to address each of these separate optimization problems before SSA, and any good book on compiler writing that predates SSA will describe some of them. – alephzero Feb 6 '19 at 10:58
  • 2
    Just a general remark: While compiler design was already early on a topic for research (think Pascal), real world compilers where hacks of many different and rather empiric designs. It wasn't until the 90s that 'scientific' (and open) designs offered results on par with proprietary constructions. – Raffzahn Feb 6 '19 at 12:49
  • 3
    One "classic" reference source from 10 years before SSA was Aho and Ullman, "Principles of Compiler Design". amazon.co.uk/Principles-Compiler-Design-Alfred-Aho/dp/…. If you want to study the history of compiler writing, compare that with Aho, Sethi, and Ullman, "Compilers - Principles, Techniques and Tools" from 10 years later. amazon.co.uk/Compilers-Principles-Techniques-Alfred-Aho/dp/… – alephzero Feb 6 '19 at 17:07
  • 2
    GCC did all its optimizations on its RTL representation, which it still uses today for later optimization passes, including CSE and DSE passes, after the GIMPLE (SSA) passes (which also has CSE/DSE passes).. An exception was (and probably still is) simple constant folding, which is was done at the parse tree level, since it had to be to implement things like int foo[3 + 4];. – user722 Feb 7 '19 at 3:48
5

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 SL, the last segment in Π̅(Φ), and for each i ≤ L, the set of all Sj with j < i is examined for the occurrence of an Sj = Si. As soon as some Sj = Sj, Sj is eliminated from Π̅(Φ), and all references to Sj replaced by references to Si, 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 SL, and for each i ≤ L, the set of all Sj with j < i is examined for the occurrence of more than one reference to Si, i.e., the occurrence of Ψm, Ψn, with m ≠ n and Ψm = Ψn = i. If and only if this is the case is Si 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 S16 tagged as a cs-type segment, since Ψ01 = Ψ142 = 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.

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).

Improve this answer
7

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.

Improve this answer
  • 1
    Well, true, and I should not complain with such a nice and true quote about the merits of C :)) But I can't halt to note that the world didn't start with PCs nor their compilers - even thru they restarted from scratch. Also, C is a newcomer to the business. There are many others who got quite interesting optimization strategies already way before the first microprocessor was build - like FORTRAN 66 using statistical analysis to order the three cases of an IF - and they for sure had the CPU and memory to do so. – Raffzahn Feb 6 '19 at 13:25
  • 1
    True so far as it goes, but Cray Research had been shipping supercomputers for 12 years before 1988. Not to mention other mainframe manufacturers. Actually 512K was a huge amount of memory to run a compiler back then, when the different passes were different overlays. We used to do most of our compile-and link runs (but not executing the program being built) on our IBM S/370s in just 100K bytes. – alephzero Feb 6 '19 at 13:26
  • 1
    @Wilson - in quite a few compilers, that's correct. The earlier the compiler was, the less optimizations it performed. Though as alephzero points out, big iron is a different beast, and would have had optimizations much earlier than the PC world. – Michael Kohne Feb 6 '19 at 17:15
  • 1
    A lot of old programs used the 95-5 rule to leave 95% of the code in the less optimized C/Pascal/Fortran and hand optimize the critical 5% in assembly. The 68k and x86 processors made hand optimization beat out the compilers almost all of the time in the 80s. – Michael Shopsin Feb 6 '19 at 18:07
  • 2
    Most of the early compilers used at least peephole optimization, a technique that simply looks for repeating patterns of badly generated code (like unnecessary register saves and restores) the compiler builders knew their software frequently generated, and replaced these patterns with faster instructions (or eliminated them completely) – tofro Feb 6 '19 at 20:39
2

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.

Improve this answer
  • 5
    Could you provide some context to this answer? Very few people have the dragon book; at present, this is a link-only answer. – wizzwizz4♦ Jul 31 '19 at 12:12
  • @wizzwizz4 err, what link? – Raffzahn Oct 31 '20 at 9:12
  • 1
    @Raffzahn Maybe this one? archive.org/details/compilersprincip0000ahoa Seriously, a reference to a book is just a link to your local (university) library. – Michael Graf Oct 31 '20 at 9:21
  • 1
    @wizzwizz4 So answers are judged and meant only by SE-Nerd standards? Come on, I though this is supposed to be a welcoming environment? So I guess I need to repeat, there are many reasons to call this post out before settling on 'link only' – Raffzahn Oct 31 '20 at 10:27
  • 1
    @Raffzahn Your blatant hypocrisy here continues to amaze me. You're the most unwelcoming person active on this site. – user722 Oct 31 '20 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.