News for hackers. Stuff that matters.
Re:Want to Write a Compiler? Read These Two Papers (2008) by vidarh on Thursday December 24, 2015 @06:47AM (#10787885)
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.

Re:Want to Write a Compiler? Read These Two Papers (2008) by cottonseed on Thursday December 24, 2015 @04:18PM (#10789607)
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).
Re:Want to Write a Compiler? Read These Two Papers (2008) by vidarh on Wednesday December 30, 2015 @07:32AM (#10811808)
> 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)

Re:Want to Write a Compiler? Read These Two Papers (2008) by bonobo3000 on Thursday December 24, 2015 @07:53AM (#10788005)
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...

Re:Want to Write a Compiler? Read These Two Papers (2008) by vidarh on Wednesday December 30, 2015 @07:38AM (#10811825)
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.
Re:Want to Write a Compiler? Read These Two Papers (2008) by sklogic on Thursday December 24, 2015 @08:26AM (#10788072)
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.

Re:Want to Write a Compiler? Read These Two Papers (2008) by ky3 on Thursday December 24, 2015 @09:04AM (#10788162)
> 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.

Re:Want to Write a Compiler? Read These Two Papers (2008) by sklogic on Thursday December 24, 2015 @09:19AM (#10788209)
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.

Re:Want to Write a Compiler? Read These Two Papers (2008) by ky3 on Thursday December 24, 2015 @09:43AM (#10788291)
The repo looks to be here:

https://github.com/combinatorylogic/clike

Because you have a functional and also imperative language (pfront?) that your compiler is written in, you avoid memory churn by ensuring "visitor nodes are chained together", is that right?

So pass fusion for compiling clike does away with the destructive matching and rebuilding of untransformed subexpressions by linking pointers back to the original.

Re:Want to Write a Compiler? Read These Two Papers (2008) by fanf2 on Friday December 25, 2015 @11:15AM (#10791532)
It is one of the key advantages that makes LLVM easier to work with than gcc.
Re:Want to Write a Compiler? Read These Two Papers (2008) by vidarh on Wednesday December 30, 2015 @09:29AM (#10812144)
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.