Optimisation Framework

[Matthew Tuck]

I think it would be nice to design the optimiser using a framework. 
That is, an optimiser independent of the language it operates on.  It
would still be imperative though.

Why would you want to do this?  Well I've been think about the whole
process of optimisation.  Basically, at the low-level, certain
optimisations are very difficult if not near impossible to perform,
hence we only do them at the high level.  Whereas certain optimisations
might only be done at the low level, such as machine dependent
optimisations.  But some might want to be done at both levels.  Why?

Well, first of all, because they're relevant.  I can think of dead-code
elimination, code inlining and constant folding just off the top of my
head.

A lot of this would get done at the high level, but there more be more
opportunities introduced by translation to the low level.  By the same
token, the high level would be quicker, and doing optimisations here
allows more to be known about the program, which could in turn lead to
performing some optimisation that could only happen at the high-level.

So if you accept that you might want to do the same optimsiation at
multiple levels, you would want to try to abstract the algorithms that
perform these algorithms.  Basically you would do that through abstract
data types.  For example, each language would have a "statement"
element, and a way of finding the dependencies between statements, for
possible statement reordering.  You could use this at both levels to
find something like this:

if Condition then
	A := 3
	B := 4
	C := 6
else
	A := 5
	B := MyConstant
end if

No obvious optimisation, but what if you determine that MyConstant is
always 4?  You get:

if Condition then
	A := 3
	B := 4
	C := 6
else
	A := 5
	B := 4
end if

Obviously you want to pull out the b := 4.  But you can't put it before
the loop since it's not at the head of the True branch, and likewise for
the foot of the loop.  But, knowing that the statements have no
dependencies, you could put it in either place.

So the gist is we can write our algorithms independent of what level we
operate on.  I think that would be good for writing smaller compilers.

So what would be the architecture of the framework?  Well basically
there would be several objects.  You would extend the objects for your
actual language, filling in the blanks and integrating langauge-specific
algorithms with the framework's language-independent algorithms.

Been done before?

-- 
     Matthew Tuck - Software Developer & All-Round Nice Guy
                              ***
       Check out the Ultra programming language project!
              http://www.box.net.au/~matty/ultra/