[antlr-interest] Non-local optimizations with treewalker?

Andy Tripp antlr at jazillian.com
Sat Sep 15 13:11:26 PDT 2007


Loring Craymer wrote:
> The answer, of course, is "yes and no".  Yes, because
> capturing the semantics on which you base your
> optimizations on in a tree makes it easier to carry
> out a series of transformations.  
That sounds to me like you mean "Yes, you'll need a tree to capture 
semantics, but
that's just a starting point". i.e. a tree to gather semantics is 
necessary but not
sufficient to do any sort of transformation.
> No, because you need
> to impose a control flow graph on top of the tree
> (easy to do) 
building a control flow graph is "easy to do"? Wow! And he didn't
even mention what language he's dealing with. Good luck on easily
building a (correct and complete) control flow graph on any language with
gotos. And for extra credit, build one for COBOL in which the
control flow itself can be determined at runtime.

> and add other data structures to capture
> relationships between distant nodes in the tree during
> analysis.  Transformation passes over trees are
> interspersed with analysis passes; analysis passes
> invariably require additional data structures,
> including symbol tables, to capture the results of the
> analysis for the next transformation or code
> generation pass.
>
> So:  trees are central to syntactic/semantic
> transformation, but they are not the only tool needed
> for analysis.
>   
There are different types of "transformation" - one is "compilation", 
but another
is "translation". I'd agree that trees (and a treewalking approach)
are "central" for compilation, because the problem is not too much more than
"at this type of node in the tree, emit this code". But what Sohail 
describes
sounds to me more like translation. Here, the problem isn't at all framed as
"at this type of node...do something". Instead, it's more like "examine the
tree, looking for the following, and change the tree in the following way."

If he uses a treewalker to do what he wants, it will look like this:

block: { doOptimization1(); doOptimization2(), doOptimization3(); }

where it just so happens that these three optimizations get "kicked off"
at each block in the AST, but they would each examine and manipulate the
entire AST.

Andy
> --Loring
>
> --- Sohail Somani <sohail at taggedtype.net> wrote:
>
>   



More information about the antlr-interest mailing list