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

[Andy Tripp]

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);

...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).

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.

Andy

Sohail Somani wrote:
> Hi,
>
> Is it feasible/intelligent to do non-local optimizations with an antlr
> (2.7.6) treewalker? I specify 2.7.6 because the readme for antlr3 says
> that it might crash on syntax errors!
>
> For example, assuming immutable variables and no side-effects:
>
> v = f(x)
> ...
> w = f(x)
>
> I'd like to transform into:
>
> temp = f(x)
> v = temp
> ...
> w = temp
>
> I think it isn't the smartest thing to use treewalkers for this but I'd
> like to be wrong, preferably with a verbose beat down as to why
>   
> Thanks,
>
> Sohail
>
>