Re: Number of compiler passes

On Mon, 21 Jul 2008 16:29:15 +0200, Michiel <m.helvensteijn@gmail.com>
wrote:


>... is there still a reason to limit the amount of passes a compiler
>makes? Sure, with each additional pass there will be some overhead, but
>other than that, is there a disadvantage I'm missing?
>
>In particular, I'm working on a source-to-source compiler at the moment.
>>From my own language to C. It now has the following stages:
>
>* Flex + Bison to create AST
>* 1 Over AST to find declarations (and re-declarations)
>* 2 Over AST to detect which variables are used in which functions
>* 3 Over AST to find undeclared references
>* 4 Over AST to find the type of each expression and note type mismatches
>* 5 Over AST to find the access-type (read/write/both) of each expression
>* 6 Over AST to perform optimizations
>* 7 Over AST to translate to target language
>
>Pass 2 to 4 may seem excessive, but I believe they are necessary because of
>the following features:
>* Var/function declarations anywhere in the code (incl. nested functions)
>* Forward referencing of constant functions and constant variables
>
>Some of the stages could be merged, I suppose. But it would not help code
>readability or provability to do so.


The only disadvantage to many passes is having to store symbol and
analysis data that future passes may require.


You don't give much detail of your language, but I don't see how
"readability or provability" would be harmed by combining passes 1 & 2
and passes 3 & 4. [I numbered them above for convenience]


Assuming variables must be declared, processing declarations gives you
all you need - the symbol table(s) you construct will provide scoping
for non-local variables and functions. I don't see a need for two
passes.


Similarly, undeclared references will not be represented in your
symbol table. They will be caught when you look them up to determine
their type. You can assign them a special nil type so going forward
any expressions using them fail to type properly.


I don't know what you mean by "access-type" of an expression - unless
you're talking about I/O in which case I still don't know what you
mean. We could be having a terminology disconnect - to my mind an
"expression" always computes or side effects, so it always reads
operands and sometimes writes a result.


I would think that your optimization phase itself would consist of
multiple passes as a number of optimizations are possible even on an
AST form.


And since you are targeting C from a language that has nested
functions, you might actually need more than one pass to affect the
translation. Simple function nesting as in Pascal can be handled
easily, but full closures as in Lisp requires constructing runtime
data structures and a lot more analysis.


George

Return to the comp.compilers page.
Search the comp.compilers archives again.