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

[Sohail Somani]

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.  No, because you need
> to impose a control flow graph on top of the tree
> (easy to do) 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.
>   

Thanks for your response. What exactly do you mean by "imposing a CFG on
top of the tree?" What I understand by this is you have a tree walker
pass in which you generate a CFG which points to the appropriate nodes
in the AST. Given this mapping, you can then transform as a result of
traversing the components of the graph and determining some
optimizations. This sounds to me like I would have to write some C++
code to generate a ANTLR tree which sounds like I'm using the tool wrong.

As an aside: having never written an optimizing compiler before myself,
I wonder if you can suggest any practical literature about the data
structures involved in (efficient) program optimization.

Thanks again,

Sohail