Archive for June, 2008

Non-immutable classes, and edge expressions

23 June 2008

I finally have a reasonable version of the optimisation I planned at the beginning of this project working well. Rather than requiring all the classes passed as arguments to pure methods to be immutable, I can do sufficient analysis (along with yet more annotations) to satisfy a weaker requirement. Pure method calls can safely be moved out of loops if (as before) each argument is an invariant reference and either a primitive type or an immutable class type (marked by the @Immutable annotation), but I can now detect a third case, where the following three conditions are all met:

  1. The reference is unique; specifically, it is a local variable annotated @Unique.
  2. There are no statements in the loop which change the object via the reference (i.e. no calls to const methods that are neither @Pure nor @Const).
  3. There is nothing to change objects referenced within the object (the class is marked as @Encapsulated)

The extra annotations (@Unique and @Encapsulated) absolve me from having to solve the aliasing problem, passing the problem onto the programmer (who hopefully understands how eir program works and where aliasing can happen) instead. The @Encapsulated annotation in the last condition is defined to mean that there are guaranteed not to be any references into the internal structure of objects of the class, so the only way to change the state of the object is by calling methods on it.

While I was testing this, I realised that my optimiser did not consider expressions on flow graph edges (which is how JKit expresses conditions in its intermediate representation) at all, neither trying to factor them nor checking them when it looks for statements that might modify an object. To rectify this I had to first compute the set of relevant edges by finding all edges in the flow graph having both source and destination within the set of points in the LoopBody region. I then used this edge set as well as the Point set when factoring expressions and when looking for expressions that might change an object.


16 June 2008

So I need to evaluate the optimisations I have so far. It has been suggested by Dave that his SimpleLisp interpreter and the JKit parser might make good tests.

I have had a look through SimpleLisp, and though there are a number of places where methods like List.size() are called inside loops, none of the classes in question are immutable. It thus seems that it will be necessary to implement the next stage of the optimiser (checking whether anything in the loop body will change the object in question) before any useful optimisation can be performed, in this program at least. This is fairly much what I expected, and likely to be the case in many programs.


10 June 2008

Wow, it has been a while since I posted here. I have been really busy with other projects, assignments and the COMP413 exam, but now I have a few days to work on this project and have made some progress.

I now have my optimiser actually moving method calls out of loops, in a (relatively) simple but still useful case. It is possible to safely move a method call if the method is annotated as @pure and for each argument to the method call (including the target object):

  • The variable (primitive value or reference) is invariant within the loop, i.e. it always has the same value or points to the same object, and
  • either:
    • It is of a primitive type, or
    • the class type is immutable (annotated as @immutable at the class declaration)

I have successfully implemented the code to check for this case and factor the method call out of the loop (as I earlier did for @moveable methods and dereferences of Array.length under certain conditions).

The more general case is when, rather than the class being immutable, the compiler can check that

  • The reference (variable) is annotated as @unique, meaning that there are guaranteed to be no aliases, and
  • there are no statements in the loop which change the object via the reference (i.e. no calls to non-@const methods), and
  • there is nothing to change objects referenced within the object.

It is fairly clear how to check the first two parts, but I cannot yet see how to check the third condition.

I probably have not described this very well. Oh well. I will have to write a full report eventually.