Your favorite abstract tree syntax optimization

Question

If you were building a compiler, which AST level optimization would be most enjoyable?

Answer 1

The optimization that is best suited for AST (and not, say, CFG) is tail call optimization: if you see a form subtree:

RETURN CALL f ARGS x, y, ... 

You can replace it with a jump to f . If f(a, b) is a function in which the callback appears, replacing is as simple as:

 a = x; b = y JUMP to root of tree 

It’s easiest for me to imagine this jump as a special “restart” operator, which translates AST-> CFG as an edge back to the first node. Moving to other functions is a bit more complicated since you cannot just set local variables, you really need to think about how the arguments are passed to them and prepare to translate them at a lower level. For example, AST may require a special node that can instruct a later pass to overwrite the current stack stack with arguments and jump accordingly.

Answer 2

Basically, you cannot do interesting optimizations at the AST level, because you need information on how data is transferred from one part of the program to another. Although the data flow is implicit in the meaning of the AST, it is difficult to determine it by checking only the AST, therefore, people building compilers and optimizers create other representations of programs (including symbol tables, flowchart diagrams, achievement definitions, data flow and SSA forms, etc. .).

Having a parser for a language is an easy part of parsing / manipulating that language. You need everything you need to do to do a good job.

If you have all of these other ideas, you might consider optimizing at the AST level. Most compiler developers are not bothered; they are converted to a data stream representation and simply optimize it. But if you want to reproduce the source code with the changes, you need an AST. You will also need a cute printer that allows you to restore the source code. If you go this far, you will get the original source of the program conversion system.

The DMS Software Reengineering Toolkit is a system that converts ASTs using all of these other views to provide the analysis needed for the transformations.

Answer 3

One of the advantages of using optimizations in AST is that it can shorten the execution time of some back-end optimizations. However, I believe that these optimizations should be done from a strong point, because you can prevent further optimization of the code.

Thus, IMO - one simple but interesting optimization used at the AST level or in the process of generating IR - is the simplification of Boolean expressions of the form (1 || 2) or (2 <3 || A), etc. to their net result. I find some simple peephole optimizations to be useful.