Comment by sklogic
10 years ago
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.
> Essentially, compilation is rewriting of a source AST into the target machine code.
While that is true of most modern compilers, do consider that there's the whole Wirth school of compilers that don't use an AST at all but generate machine code directly during parsing.
> For a human it is much easier to structure such a rewrite as a sequence of very trivial changes.
I'm not convinced, as I've written elsewhere, because while the changes may be trivial, you need to keep track of what a program is expected to look like in between each stage, and that becomes harder the more stages you introduce. E.g. my forever-in-progress Ruby compiler has a stage where it makes closures explicit: It allocates an environment to store variables in and rewrites variable accesses accordingly. For following stages the language I'm working on is different: I can no longer use closures.
The more stages you have, the more language dialects you need to manage to mentally separate when working on the stages. And if you decide you need to reorder stages, you often have painful work to adapt the rewrites to their new dialects.
The end result looks very simple. But try to make changes and it's not necessarily nearly as simple.
5 replies →
> 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.
See, the problem is, for the "sufficiently smart" compiler to easily realize this is possible, the passes need to be purely functional. It turns out, most programmers struggle with understanding functional programming...
1 reply →