Comment by vidarh
10 years ago
Have you tried this approach? If so I'm curious to hear about experiences.
My own experience with far fewer stages is that while it becomes easy to understand what each stage does and how, it becomes hard to keep track of how each stage interact, as each intermediate output in effect becomes a language dialect of sorts.
I'm still not decided on whether it's a net win or loss.
Yes. I co-founded a startup building optimizing compilers for high-performance telecommunications processors in the early 2000s (acquired by Intel). In any complex software system, building powerful, composable and modular abstractions is critical for managing complexity. Having many composable passes is exactly that. We were a small team (6 people) and a modular architecture maximized our productivity and made it possible to complete with teams many times our size. We used a unified IR throughout the compiler so it had a consistent semantics, but the IR could support various canonical forms or constraints that were managed explicitly by the compiler. Instruction formation involved three steps: fragment selection by tree covering (think of load with post increment or a SIMD instruction as multiple fragments), grouping of fragments into instructions, and grouping of instructions into issue slots in the scheduler (several of our targets were VLIW). In addition to constraint, we had properties like SSA vs multiple assignment, structured control flow vs basic blocks, certain kinds of cleanup, etc. A pass could declare its requirements (SSA, structured control flow, pre-fragment) and the compiler would check the properties, possibly running passes to create them (e.g. put in SSA form). Having separate cleanup passes meant transformations didn't have to clean up after themselves, often making things vastly simpler. Analysis passes (dataflow, alias analysis, various abstraction interpretations) were independent of the properties because the IR had unified semantics. That said, it is true our compiler didn't have the fastest compile times (multiple times slower than gcc on targets we both supported), but we were a highly optimizing compiler and our generated code was significantly faster than the competing alternatives (if there were any).
> In any complex software system, building powerful, composable and modular abstractions is critical for managing complexity.
Yes, but as Wirth showed already in the 70's, you don't even need an IR in order to do this, much less separate passes.
For a highly optimizing compiler like yours the complexity might have been unavoidable anyway, though (a lot of the simplicity of Wirth's compilers comes from a long held insistence that no optimization could be added to the compiler unless it sped up the compilation of the compiler itself - in other words, it needed to be simple enough and cheap enough to apply to the compiler source code to pay for itself... needless to say this implicitly means that most Wirth-compilers omit a lot of optimizations that are usually included elsewhere, though some of his students did implement some impressive "unofficial" optimizing variations of his compilers that were also blazing fast)
You might be interested to know Scala's new compiler dotty takes the phase approach - there are 40-50 phases and logic for fusing phases together to work in one traversal.
Check it out - a list of all the phases in the source! https://github.com/lampepfl/dotty/blob/master/src/dotty/tool...
Yikes... The sheer size of the transformation code for that compiler terrifies me. I think that's a good demonstration of the type of compiler I would not want to be forced to have to work on.
Yes, I am using this approach exclusively. Nanopass (or similar frameworks like MBase) is making it very easy to introduce as many languages as you like in between your passes.
It really helps that they are different, you always know which stage you're in.
> Yes, I am using this approach exclusively.
Earlier you wrote that "And if you worry about performance, your compiler can fuse passes together in many cases."
What kind of fusion do you use in your approach?
In the last paragraph of Keep's thesis, he mentions pass fusion, citing Wadler's 1988 work on deforestation. Keep does not, however, give a working implementation.
I know of no-one doing nanopass fusion, but I'd love to be corrected.
I'm not using Nanopass directly, I've got my own similar framework (developed independently).
It is using an IR which allows to easily compare the visitor shapes (i.e., source AST, target AST, traversing order, omitted nodes), and if they do match and the second pass is not using results of any of the collectors from the first pass (too long to explain what collectors are, treat them as a kind of a constrained side effect), corresponding visitor nodes are chained together.
Deforestation is supposed to work on much lower level, and I'm not sure it's possible to deduce the original visitor shapes and traversing order from an already lowered code.
A previous version of this framework is available on github, username 'combinatorylogic' (it does not provide fusion or any other optimisations, because it's dynamically typed; A glimpse of the IR of the next version can be seen in the recform AST library, see 'ast2-...'). The current version will be published soon.
1 reply →
It is one of the key advantages that makes LLVM easier to work with than gcc.
gcc is a horrible comparison, since they for a very long time explicitly made it hard to separate out clear boundaries in an attempt to deter people from e.g. bolting on serialization at critical stages and injecting their own proprietary stuff beyond a suitable "GPL-proof" boundary.
As compilers go, I don't think gcc has been a good example of maintainable software for a very long time, if ever.