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:
- The reference is unique; specifically, it is a local variable annotated @Unique.
- 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).
- 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.