Archive for July, 2008

Optimisations in SimpleLisp

27 July 2008

Now, after a bit more work since my last post, when I compile the SimpleLisp interpreter, I get the following optimisations applied:

Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression '161l[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.
Factoring expression '161l[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.
Factoring expression '("type error in ""[java.lang.String] ++ (fn[java.lang.String] ++ """[java.lang.String])[java.lang.String])[java.lang.String]' of class jkit.core.FlowGraph$BinOp out of loop.
Factoring expression 'cs[java.lang.Class[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'cs[java.lang.Class[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'es[org.simplelisp.interpreter.LispExpr[]].length[int]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression '(!true[boolean])[boolean]' of class jkit.core.FlowGraph$UnOp out of loop.
Factoring expression '(!whitespace[boolean])[boolean]' of class jkit.core.FlowGraph$UnOp out of loop.
Factoring expression '(!whitespace[boolean])[boolean]' of class jkit.core.FlowGraph$UnOp out of loop.
Factoring expression '(!whitespace[boolean])[boolean]' of class jkit.core.FlowGraph$UnOp out of loop.
Factoring expression '(!whitespace[boolean])[boolean]' of class jkit.core.FlowGraph$UnOp out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].params[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].params[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression '17f[org.simplelisp.interpreter.LispExternal].params[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].params[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression '17f[org.simplelisp.interpreter.LispExternal].params[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].params[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression '17f[org.simplelisp.interpreter.LispExternal].body[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].body[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression '17f[org.simplelisp.interpreter.LispExternal].body[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].body[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].body[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression 'this[org.simplelisp.interpreter.LispExternal].body[java.util.List]' of class jkit.core.FlowGraph$Deref out of loop.
Factoring expression '(1[int] + this[org.simplelisp.interpreter.LispFunction].numEval[int])[int]' of class jkit.core.FlowGraph$BinOp out of loop.
Factoring expression '(1[int] + this[org.simplelisp.interpreter.LispFunction].numEval[int])[int]' of class jkit.core.FlowGraph$BinOp out of loop.
Factoring expression '5es[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.
Factoring expression '5es[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.
Factoring expression '(l[int] + 6[int])[int]' of class jkit.core.FlowGraph$BinOp out of loop.
Factoring expression '(l[int] + 6[int])[int]' of class jkit.core.FlowGraph$BinOp out of loop.
Factoring expression '13es[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.
Factoring expression '13es[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.
Factoring expression '(l[int] + 6[int])[int]' of class jkit.core.FlowGraph$BinOp out of loop.
Factoring expression '(l[int] + 6[int])[int]' of class jkit.core.FlowGraph$BinOp out of loop.
Factoring expression '13es[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.
Factoring expression '13es[org.simplelisp.interpreter.LispList].size()[int]' of class jkit.core.FlowGraph$Invoke out of loop.

Note that these include some traditional loop invariant code movement optimisations as well as my particular optimisation of pure method calls, as allowed by the more general approach I mentioned recently.

A little refactoring generalises to allow a little more optimisation

24 July 2008

Up till now, my optimisation stage would only move expressions out of loops if they were exactly one of the cases discussed (Array.length or call to a pure method meeting various conditions). In doing the checking required to detect when such movement was safe, however, I had a method in my code called isInvariantReference which checks whether a given expression can be guaranteed not to change within the loop, such as if it is a constant, a local variable which is not assigned to in the loop, an arithmetic expression with all parts meeting the same condition, or various other types of expression which will not change value. This is needed, for example, as part of the condition imposed on arguments to the pure method call for it to be able to be moved out of the loop.

I realised that this isInvariantReference method was in fact doing a very similar thing to my checks for expressions that can be moved out of the loop. By combining the two, I can move compound expressions rather than just the actual method calls or field dereferences, and so make the optimisation slightly more effective. The change I made was to have isInvariantReference also detect the Array.length and pure method call cases, and then replace the part that previously detected these cases with a call to isInvariantReference (and some other simple checks, to prevent infinite recursion). This means that the usual loop invariant code motion optimisations can be made in addition to my new optimisations. This refactoring also results in a little less code duplication in my compiler stage.

For example, take the code snippet below:

for (int i = 0; i < listA.size() * listB.size(); ++i) {
System.out.println(listA.getWith(i, listB));
}

Assuming the appropriate conditions are met, this code would before have been optimised to something like this:

int $invariant0 = listA.size();
int $invariant1 = listB.size();
for (int i = 0; i < $invariant0 * $invariant1; ++i) {
System.out.println(listA.getWith(i, listB));
}

It will now be transformed into something like this:

int $invariant0 = listA.size() * listB.size();
for (int i = 0; i < $invariant0; ++i) {
System.out.println(listA.getWith(i, listB));
}

This saves a local variable and a multiplication each time through the loop.

Many other examples are possible. To be honest this is not likely to be a big improvement over the optimisation as it stood before, but it still seems worth doing, even if only because it makes the code nicer.

Milestone 2

22 July 2008

I submitted my milestone 2 report a few of days ago. You can read it here.

Annotating SimpleLisp

16 July 2008

I have now added a fair number of annotations to Dave’s SimpleLisp interpreter, and tested compiling it with my loop invariant code movement optimisations. Results were moderately encouraging: there were a fair number of cases where the Array.length optimisation could be applied, and a few for pure methods (all of which were lengths of collection types).

Writing milestone 2 report…

12 July 2008

I have been spending the last several days writing my second milestone report. I hope to have a mostly complete draft ready soon, so that I can send it to my supervisor and others for review and comments. It is due on Sunday 2008-07-20.