5

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];. – Ross Ridge Feb 7 '19 at 3:48
4

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

|improve this answer
  • 1
    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

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.