11

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.

8
  • 1
    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
    Commented Feb 6, 2019 at 10:52
  • 1
    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
    Commented Feb 6, 2019 at 10:58
  • 3
    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
    Commented Feb 6, 2019 at 12:49
  • 4
    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
    Commented Feb 6, 2019 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
    Commented Feb 7, 2019 at 3:48

4 Answers 4

7

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 iL, 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 iL, 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 mn 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).

18

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,
}
12
  • 1
    How well suited is SSA to a language where accesses to a[i] and b[j] might access the same storage even if a!=b and i!=j? IMHO much strife could be avoided if C were split into recognized distinct dialects, one of which would use an abstraction model that would be a good fit for SSA but a poor fit for some tasks, and one of which would process loads and stores using "older" styles of optimization analysis based on sequencing. Do you share my perception that SSA is excellent for some tasks, but compiler writers exhibit a "when all you have is a hammer, everything is a nail" attitude?
    – supercat
    Commented Sep 1, 2023 at 15:30
  • 1
    The short answer is, better than in dfa, but not very good. In general, this kind of alias analysis in a c like language is intractable. This is not because of the rep of the analysis, but that the semantics of the language allow too much weird stuff to be done to pointer. In more modern strongly typed, garbage collected languages it is not possible to play as loose with pointer and so the analysis is more tractable. The key here is that you cannot do weird stuff or you mess up the gc. Commented Sep 2, 2023 at 17:18
  • 1
    Why do you suppose compiler writers aren't willing to recognize the legitimacy of C code that doesn't fit the SSA model, and process such code reasonably efficiently, while also offering a dialect that has no pretext of compatibility with all existing legitimate C code but could offer improved performance for code that is amenable to SSA? A mode which treated all accesses to objects whose address is taken as volatile could offer performance that was vastly better than -O0, but compatibility with many other programs that would otherwise require -O0 setting.
    – supercat
    Commented Sep 2, 2023 at 17:29
  • 1
    I think you are confusing several issues. There are likely over several hundred thousand people who have or do program using gcc. The languages that gcc supports have well defined semantics. There is no room for deviation from those semantics is considered a bug, a possibly a bug that could be exploited as a security hole. None of this has anything to do with ssa form. It has to do with supporting a product that everyone agrees on the meaning of correctness. Ssa form is used in most of todays compilers because it supports a semantic model that is easy to reason about Commented Sep 2, 2023 at 18:42
  • 1
    Is there any specification anywhere that would authorize the way clang and gcc treat godbolt.org/z/Evzhd6W6h ? By my reading of the Standard, behavior would be defined as having test(y,0) set y[0] to 2 and return 2 if x is one element and y immediately follows x, and setting y[0] to 1 and returning 1 otherwise. Both clang and gcc, however, simultaneously assume that the expression p+i is equivalent to x[1], and that the y[0] at the end will yield the value that was earlier assigned using an lvalue of the y[0] form. What do you think causes that?
    – supercat
    Commented Sep 3, 2023 at 22:05
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.

9
  • 2
    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
    Commented Feb 6, 2019 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
    Commented Feb 6, 2019 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. Commented Feb 6, 2019 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. Commented Feb 6, 2019 at 18:07
  • 3
    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
    Commented Feb 6, 2019 at 20:39
1

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.

12
  • 6
    Could you provide some context to this answer? Very few people have the dragon book; at present, this is a link-only answer.
    – wizzwizz4
    Commented Jul 31, 2019 at 12:12
  • 2
    @Raffzahn Maybe this one? archive.org/details/compilersprincip0000ahoa Seriously, a reference to a book is just a link to your local (university) library. Commented Oct 31, 2020 at 9:21
  • 1
    @wizzwizz4 I bet if I kick one of my bookshelf a dozend books with dragons on the title fall out. A link is only a link when it can be followed by an average reader, not a nerd already fixiated on the topic. So again, there are many reasons to delete that post, being link only is none of them.
    – Raffzahn
    Commented Oct 31, 2020 at 10:20
  • 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
    Commented Oct 31, 2020 at 10:27
  • 3
    @Raffzahn Your blatant hypocrisy here continues to amaze me. You're the most unwelcoming person active on this site.
    – user722
    Commented Oct 31, 2020 at 18:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .