6 ms·

Frances Allen wrote "A Catalogue of Optimizing Transformations" in 1971. 50 years(!!!) later, they are still the backbone of optimizing compilers. I think the o

Frances Allen wrote "A Catalogue of Optimizing Transformations" in 1971. 50 years(!!!) later, they are still the backbone of optimizing compilers. I think the only major thing missing is autovectorization. She was in her 30s when she wrote it.

sanxiyn 6y ago
I think you should read it if you work on compilers, even now. But the reason is a bit different. It was the survey of the state of the art at the time, but obviously it is not the state of the art now. Then why should you read it? Because it is written in two layers. The first layer goes, we tried many optimization ideas, but only these were effective in practice: inlining, register allocation, etc. Others were not. Surprisingly, this layer is still mostly true today! This is both happy and sad depending on your view. Personally I think it testifies that compiler is a mature field, and it matured by 1970. (And that Frances Allen did lion's share of work maturing it.) The second layer is, so here is how you should do inlining, register allocation, etc. While this layer is also full of gems, it is necessarily badly outdated. The paper predates graph coloring register allocation, for example. On the other hand, ironically, the state of the art 1970s algorithms are often a good choice today when you want an algorithm that is fast and low memory. (Ironic, because they were slow and high memory at the time!) This doesn't apply when there is an important new concern, for example cache locality, but happily it mostly doesn't affect compiler. I think there should be a project to write the-state-of-the-art-in-1970s compiler. It would be a great simple and minimal alternative to GCC and LLVM, and it would also work great as a JIT code generator. We probably should name it Fran.
- sitkack 6y ago
  > On the other hand, ironically, the state of the art 1970s algorithms are often a good choice today when you want an algorithm that is fast and low memory. Simple things can run at higher speeds than complex things. Simplicity should be an architectural element, not a quality, but a feature. Your idea for the Fran compiler is excellent. Throw in METAII from Dewey Schorre and it can be language agnostic.
- mpweiher 6y ago
  Maybe I should call the backend for Objective-S Fran :-) > graph coloring register allocation I knew some people working on linear optimization, at the time one of the most performance-intensive applications around (with real money/competitiveness in many industries riding on it). The compiler that produced the best code, by quite a bit, was the IBM FORTRAN compiler (3090 was the preferred target at the time), which also didn't do graph coloring. It just allocated the registers by loops from innermost to outermost. ¯\_(ツ)_/¯\ For a simple compiler, we should also look at Wirth's works, and Wirth's rule: an optimization has to pay for itself, that is, the compiler compiling itself with the optimization both in the executable and in the source code has to be faster than without it in both places.
  - MrBuddyCasino 6y ago
    So that is were this Golang rule comes from.
  - scott_s 6y ago
    > For a simple compiler, we should also look at Wirth's works, and Wirth's rule: an optimization has to pay for itself, that is, the compiler compiling itself with the optimization both in the executable and in the source code has to be faster than without it in both places. That will result in a compiler best at optimizing programs that behave like compilers. Which may be fine for simple compilers, but it's worth keeping in mind that will not be a good compiler for domains where the programs don't behave like compilers (such as scientific computing, or even ML these days) that also want high performance.
- titzer 6y ago
  I agree with most of your comment but I don't agree that compilers was a mature field by 1970. That was before SSA, graph coloring register allocation, and even linear scan, all three of which were pretty revolutionary. I saw her 2007 Turing Award speech. I have tremendous respect for Fran and like your idea to name a codegen after her :-)
rudedogg 6y ago
Link to the paper: https://www.clear.rice.edu/comp512/Lectures/Papers/1971-allen-catalog.pdf https://www.clear.rice.edu/comp512/Lectures/Papers/1971-alle...
raverbashing 6y ago
Did the concept of SIMD even exist in 1971?
- p_l 6y ago
  Flynn's taxonomy was codified in 1966
- sanxiyn 6y ago
  Vector processors date from 1960s, but the neceesary techniques for loop analysis (using Fourier-Motzkin method) was not found till 1990s.
  - tjalfi 6y ago
    I think you are mistaken about this. Vectorizing compilers have been around since at least the late 1970s; the Cray 1[0] had a vectorizing compiler in 1978. Lamport’s Parallel Execution of DO Loops[1] was published in 1974. [0] https://en.m.wikipedia.org/wiki/Cray-1#Software https://en.m.wikipedia.org/wiki/Cray-1#Software [1] http://lamport.azurewebsites.net/pubs/do-loops.pdf http://lamport.azurewebsites.net/pubs/do-loops.pdf
- amw-zero 6y ago
  I can’t think of any noteworthy idea in computing that didn’t exist in 1971.
  - sli 6y ago
    I definitely do not have the chops for this, but I would love to see some sort of visualization that traces major, seemingly-modern computing ideas to their roots.
  - derefr 6y ago
    The Single Static Assignment form was only created in 1988, which is apparently so late that compilers are still discovering it (and the optimizations it enables) as some novelty today. (Never even mind the Single Static Information form.) I wonder if part of the reason SSA is not implemented from the start by many compilers, is precisely because it came too late to be included in seminal works like A Catalogue of Optimizing Transformations; so people that rely on those works as a canon of "classes of optimization techniques that work" won't even be aware of it. ----- More snarky: the earliest dataflow analysis paper I can find is from 1972. :)

sanxiyn 6y ago

I think you should read it if you work on compilers, even now. But the reason is a bit different. It was the survey of the state of the art at the time, but obviously it is not the state of the art now. Then why should you read it? Because it is written in two layers. The first layer goes, we tried many optimization ideas, but only these were effective in practice: inlining, register allocation, etc. Others were not. Surprisingly, this layer is still mostly true today! This is both happy and sad depending on your view. Personally I think it testifies that compiler is a mature field, and it matured by 1970. (And that Frances Allen did lion's share of work maturing it.) The second layer is, so here is how you should do inlining, register allocation, etc. While this layer is also full of gems, it is necessarily badly outdated. The paper predates graph coloring register allocation, for example. On the other hand, ironically, the state of the art 1970s algorithms are often a good choice today when you want an algorithm that is fast and low memory. (Ironic, because they were slow and high memory at the time!) This doesn't apply when there is an important new concern, for example cache locality, but happily it mostly doesn't affect compiler. I think there should be a project to write the-state-of-the-art-in-1970s compiler. It would be a great simple and minimal alternative to GCC and LLVM, and it would also work great as a JIT code generator. We probably should name it Fran.

sitkack 6y ago
> On the other hand, ironically, the state of the art 1970s algorithms are often a good choice today when you want an algorithm that is fast and low memory. Simple things can run at higher speeds than complex things. Simplicity should be an architectural element, not a quality, but a feature. Your idea for the Fran compiler is excellent. Throw in METAII from Dewey Schorre and it can be language agnostic.
mpweiher 6y ago
Maybe I should call the backend for Objective-S Fran :-) > graph coloring register allocation I knew some people working on linear optimization, at the time one of the most performance-intensive applications around (with real money/competitiveness in many industries riding on it). The compiler that produced the best code, by quite a bit, was the IBM FORTRAN compiler (3090 was the preferred target at the time), which also didn't do graph coloring. It just allocated the registers by loops from innermost to outermost. ¯\_(ツ)_/¯\ For a simple compiler, we should also look at Wirth's works, and Wirth's rule: an optimization has to pay for itself, that is, the compiler compiling itself with the optimization both in the executable and in the source code has to be faster than without it in both places.
- MrBuddyCasino 6y ago
  So that is were this Golang rule comes from.
- scott_s 6y ago
  > For a simple compiler, we should also look at Wirth's works, and Wirth's rule: an optimization has to pay for itself, that is, the compiler compiling itself with the optimization both in the executable and in the source code has to be faster than without it in both places. That will result in a compiler best at optimizing programs that behave like compilers. Which may be fine for simple compilers, but it's worth keeping in mind that will not be a good compiler for domains where the programs don't behave like compilers (such as scientific computing, or even ML these days) that also want high performance.
titzer 6y ago
I agree with most of your comment but I don't agree that compilers was a mature field by 1970. That was before SSA, graph coloring register allocation, and even linear scan, all three of which were pretty revolutionary. I saw her 2007 Turing Award speech. I have tremendous respect for Fran and like your idea to name a codegen after her :-)

rudedogg 6y ago

Link to the paper: https://www.clear.rice.edu/comp512/Lectures/Papers/1971-allen-catalog.pdf https://www.clear.rice.edu/comp512/Lectures/Papers/1971-alle...

raverbashing 6y ago

Did the concept of SIMD even exist in 1971?

p_l 6y ago
Flynn's taxonomy was codified in 1966
sanxiyn 6y ago
Vector processors date from 1960s, but the neceesary techniques for loop analysis (using Fourier-Motzkin method) was not found till 1990s.
- tjalfi 6y ago
  I think you are mistaken about this. Vectorizing compilers have been around since at least the late 1970s; the Cray 1[0] had a vectorizing compiler in 1978. Lamport’s Parallel Execution of DO Loops[1] was published in 1974. [0] https://en.m.wikipedia.org/wiki/Cray-1#Software https://en.m.wikipedia.org/wiki/Cray-1#Software [1] http://lamport.azurewebsites.net/pubs/do-loops.pdf http://lamport.azurewebsites.net/pubs/do-loops.pdf
amw-zero 6y ago
I can’t think of any noteworthy idea in computing that didn’t exist in 1971.
- sli 6y ago
  I definitely do not have the chops for this, but I would love to see some sort of visualization that traces major, seemingly-modern computing ideas to their roots.
- derefr 6y ago
  The Single Static Assignment form was only created in 1988, which is apparently so late that compilers are still discovering it (and the optimizations it enables) as some novelty today. (Never even mind the Single Static Information form.) I wonder if part of the reason SSA is not implemented from the start by many compilers, is precisely because it came too late to be included in seminal works like A Catalogue of Optimizing Transformations; so people that rely on those works as a canon of "classes of optimization techniques that work" won't even be aware of it. ----- More snarky: the earliest dataflow analysis paper I can find is from 1972. :)