Posts Tagged ‘jkit’

Constant folding etc.

17 April 2008

To make a start with writing optimisation stages in JKit I have written a simple constant folding optimisation stage. This will do some simple compile-time evaluation of arithmetic expressions, for example turning int x = 1 + 2; into int x = 3;.

After talking to Lindsay yesterday we have decided that the next step is for me to write some code to traverse the flow graph to find loops, in particular to identify which vertices are the tops of loops. I still need to work out where this and other information discovered during the traversal should be stored: perhaps in the flow graph somehow, perhaps in separate data structures kept locally, or maybe somewhere else.

As a first step to doing the actual code movement of loop invariants I will probably add an annotation for certain method calls to say that they certainly can be moved (e.g. if they just return a constant value and have no side-effects). The next step will probably be more annotations for objects which the programmer guarantees will have no aliases (somewhat like ownership, I think), or perhaps some sort of immutability.

Lindsay suggested that another possible direction is to do some sort of constant folding / propagation for immutable objects like Strings (for the length() method, for example), or partially immutable objects like arrays where the length cannot change. The length could be found once and cached in a local variable, or it might be possible to infer the length from how the array is constructed. For example, it would be nice if the following code:

int[] a = new int[n];

could be transformed to

int[] a = new int[n];


SSA; loop optimisations

11 April 2008

Unfortunately it seems that JKit does not currently implement any SSA (Single Static Assignment) transformation. This is annoying, because SSA would make the code movement optimisations I am looking at easier.

On another note, I read [1] this week. This paper looks at what benefit there would be in doing traditional loop transformations in a Java compiler, given that JVM typically do some optimisation in there JIT compiler anyway. The authors find that these optimisations are generally worthwhile, which suggests that my optimisations are also likely to be worthwhile. Traditional loop transformations like this will probably be my first step in working towards moving pure function calls out of loops. I am working with IR (JKIL) though, rather than bytecode.

  1. Simon Hammond and David Lacey, “Loop Transformations in the Ahead-of-Time Optimization of Java Bytecode,” in Proceedings of the 15th International Conference on Compiler Construction, ed. Alan Mycroft and Andreas Zeller (Springer Verlag, 2006)