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

[Sohail Somani]

Andy Tripp wrote:
> I think that unless your language is pretty trivial, the treewalker
> approach will
> be a mess for most non-trivial translation tasks. And I'd consider
> even something
> as simple as this to be non-trivial. Here, you show a simple example,
> but presumably
> combine multiple calls to f(x), and have to do some sort of validation
> that
> the calls are equivalent. For example, these should match:
>
> int x = 1;
> v = f(x); ...
> w = v(1);
>
> ...but these shouldn't:
> v = f(x) + 1;
> ...
> w = f(x);
>

I'm not sure you entirely understood what I was trying to do. The idea
is that computing f(x) is expensive. If the language has no
side-effects, then calling f(x) always gives the same result. Therefore,
if you can "match" (I'm not entirely sure that I want to use that term)
f(x) in more than one subexpression within some lexical scope, then you
can replace all computations of f(x) with t where t = f(x).
> ...and, control flow analysis needs to be done to check the "...".
> Suppose the "..." contains  a call to some function that passes "x" as
> an argument.
> Can "x" be changed by the called function? It all depends on the
> language and the type of x
> (e.g. in Java, Objects are passed by reference, but primitives by value).
>

Yep, thats why I specified no side-effects in my original post. I know
its a cop-out!
> So a treewalker is good if you're just saying "at this type of node in
> the AST, do the following...",
> but here, you'd want to say "within the following block, search for
> matching function calls that
> are assigned to different variables, make sure that the first variable
> is never changed before the
> 2nd call, and make the following change..."
>
> See http://www.antlr.org/article/1170602723163/treewalkers.html
> for a more complete rant.
>

Oh I've definitely seen that one :-)

Sohail