← Back to context

Comment by Animats

10 years ago

I was amused by "The authors promote using dozens or hundreds of compiler passes, each being as simple as possible."

That's kind of a desperation move. There was a COBOL compiler for the IBM 1401 with about 79 passes.[1] They only had 4K or so of memory, but they had fast tape drives, so each pass read the previous intermediate form, did some processing on it, and wrote out the next intermediate form. Except for the passes which did sorts.

[1] http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/140x/C2...

14 comments

Animats

Reply
hawkice  10 years ago

Not a bad way of organizing code, though, at least for relative beginners like me. I'm sure there are more clever things to do, or things that aren't quite possible to do reasonably or efficiently with independent small passes, but I like the way it lets me chunk everything I want to do. So maybe it started because there wasn't any other option -- but pretty good advice in the context of the article.

sklogic  10 years ago

This is the only sane approach. Small passes are easy to write, easy to understand and easy to reason about.

And if yoy worry about performance, your compiler can fuse passes together in many cases.

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

    • cottonseed  10 years ago

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

      1 reply →

    • sklogic  10 years ago

      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.

      3 replies →

srean  10 years ago

Now, if they were written as generators or coroutines you may have a winner (RAM allowing).