(fwd) Re: Object Oriented Compiler Construction

Preston Briggs writes:
| I agree, generally. Parse trees just aren't a great representation for
| optimization (an exception might be if you have to perform
| source-to-source transformations). If you want to do optimization, I
| believe it's better to transform the parse tree into a flexible and
| efficient internal form (perhaps like Litsios' data structures).
|
| Consider an optimization like moving loop-invariant code outside a loop.
| Using a parse tree, loops can have many explicit representations and
| perhaps a few hidden ones (especially if your source language allows gotos
| or recursion). It seems easier to translate all these parse tree forms to
| a low-level form (something like assembly, with only unconditional jumps
| and conditional branches for control flow) and use a single version of the
| optimization to handle all kinds of loops.


I don't really agree with Preston's opinion of parse trees. The problem,
as Preston points out, is that the complexity of parse trees makes
analysis and transformations painful eg


    x?x:y = b[++a[++i].field],i[b];


is one of the possibilities, and analysis modules will have to check for
all the possible combinations of variables on the lhs, rhs, and so on
recursively for all array subscripts, fn parameters etc--a real pain!


So, one of the reasons for going to an assembly-like IR is that the above
hairy mess is simplified (turned into a sequence of simple arithmetic
operations + conditionals). However, if you simplify the parse trees,
then they also can be quite nice IRs. Specifically, at McGill we are
working on a very aggressive alias analysis that needs high-level
information available in the parse trees. The problem with assembly-level
IRs is that you have to re-create the structure of the program and
variable types (okay, some of it is easy eg calculating dominators, but
it's explicit in parse trees).


Two problems remain:


1) supporting gotos. Our solution is to have an automatic program
structurer.


2) exposing architectural details in the IR to the transformation phases.
eg an array on RISC architectures is implemented as a series of simple
arithmetic operations. If the parse tree represents an array reference as
a variable reference, then the individual statements are left unexposed.
However, the array variable can be decomposed into simpler operations by
another phase like in SUIF.


The real catch is writing the simplify module. It was non-trivial, but
partly because we were using GNU's C compiler front-end, and there was a
lot to learn.


If anyone is interested in the details, some technical reports are
available from our anon. ftp server wally.cs.mcgill.ca pub/doc/memos:
memo76 -- automatic structurer
memo 33 -- overview of our compiler
memo 46 -- overview of family of intermediate representations
                              memo 72 -- alias analysis paper


Chris
--
Christopher M. Donawa donawa@bnr.ca
Embedded Systems Development Technologies (613) 763-9605
Bell-Northern Research, Ottawa ON CANADA fax:(613) 763-7241
--

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