Comment by cbsmith
10 years ago
I haven't read the Nanopass Framework paper, but...
The idea of doing tons of compiler passes works well in a functional context, where functional separation i the preferred method of abstraction, and you can use composition to effectively transform all your passes into a single pass.
However, actually doing that many passes seems like it is going to end badly. Even if you don't touch disk, you're doing mean things to the memory subsystem...
Doing many passes seems to be working very well in LLVM, which is definitely not targeted at or implemented with functional languages and is not a toy compiler framework for educational purposes but a full-blown industrial strength compiler framework.
Yes, you need to take care of garbage collection (in one way or another) when you're manipulating tree and graph structures.
I can't share your opinion about "ending badly". This has been shown to be a good strategy in practice.
I always notice how badly the phone mucked it up after the edit rule passes... That should be:
"The idea of doing tons of compiler passes works well in a functional programming context, where functional separation is the preferred method of abstraction, and you can use composition to effectively transform all your passes into a single pass."
It is much more memory-efficient than thrashing a single graph over and over again. Rewriting and compacting trees is good for cache locality.
Also, for the trivial rewrites (e.g., variable renaming) your compiler can safely choose to replace a cooying rewrite with a destructive update.
> It is much more memory-efficient than thrashing a single graph over and over again. Rewriting and compacting trees is good for cache locality.
To be clear: if you are thrashing a single graph over-and-over again, you are doing many passes. Rewriting and compacting trees is just a way to make the multiple passes a bit less painful.
> if you are thrashing a single graph over-and-over again, you are doing many passes.
A single "pass" can be thrashing a graph many times too, think of the things like instcombine (in LLVM parlance) or ADCE.
Essentially, compilation is rewriting of a source AST into the target machine code. It is up to you how to structure this rewrite, but the amount of work to be done remains the same.
For a human it is much easier to structure such a rewrite as a sequence of very trivial changes. And a "sufficiently smart" compiler must realise that it can be done in less steps.
8 replies →
Its purpose is for education. It's a great course, and I wish Dybvig would create a Coursera.
Any example on how do nano-pass with F# or oCalm?