Re: source-code optimizer (was RE: I'm totally baffled.)

[Doug Currie <e@...>]

Friday, November 12, 2004, 12:04:15 PM, Quinn wrote:

>> > The question is now -- what am I going to do with a Lua parser? ;-)

> Roberto replied:

>> A source-code optimizer? :)  Because local variables correspond to
>> registers in the virtual machine, there are several optimizations
>> that can be done at source level (assuming that ocasional metamethods
>> are well-behaved):
>>
>> - constant-expression evaluation
>> - constant propagation
>> - moving loop invariants out of the loop
>> - CSE elimination
>> - minimization of number of local variables used by a function

> That seems about right. The side-effect of a $-parse is a tree, and thus the
> above optimizations seem reasonable to try. Constant expression evaluation
> is probably the easiest to achieve with what I've got here[...]

I urge you to look at Single Static Assignment (SSA) form. It would
involve adding a pseudo operation in your tree temporarily (phi), but
it makes many optimizations much easier.

For example, after SSA conversion, Wegman and Zadeck's Sparse
Conditional Constant (SCC) algorithm can be used to find constant
expressions, constant conditions, and unreachable code.

Mark N. Wegman and F. Kenneth Zadeck.
Constant propagation with conditional branches.
ACM Transactions on Programming Languages and Systems, 13(2):181-210, April 1991.

Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck
Efficiently computing static single assignment form and the control dependence graph
ACM Transactions on Programming Languages and Systems (TOPLAS)
Volume 13 ,  Issue 4  (October 1991)

e