Pipeline
Parser gets .class files and produces intermediate representation, so called model. TeaVM uses SSA form to represent code. It uses standard algorithm to build SSA, based on dominators and dominator frontiers. The algorithm description is available in the paper by R. Cytron et al. The TeaVM implementation does not try to reduce the number of phi functions, relying on further stages of pipeline.
TeaVM has a very smart dependency checker to cut off a large amount of unnecessary methods. Instead of checking class-to-class dependency, TeaVM tries to figure dependencies on method level. It is a little tricky thing to deal with virtual methods, as for each call site you have to know which implementations are available. So TeaVM uses idea, described in the paper by Vijay Sundaresan et al. For each achievable method we build a data flow graph. For every NEW, LDC, ANEWARRAY we put class name to the instruction value receiver (i.e. variable which gets result of instruction execution). Then we propagate all the class names along DFG's edges. When we meet INVOKEVIRTUAL or INVOKEINTERFACE instructions, we search for the corresponding method implementation and build its DFG. We connect DFGs of methods according to variables passed by caller. So we end up with a global data flow graph where each node represents a variable in some method and for each variable we know a set of classes which achieve this variable. Of course, we always deal with false positive.
Optimizations are done in a standard way. TeaVM is planned to have all major optimizations such as inlining global value numbering, loop invariant motion and others. One of the most important optimization is de-virtualization, which requires dependency information and therefore is done at the previous stage.
After all of the optimizations applied, TeaVM makes both phi elimination and register allocation. Before doing register allocation, we insert copies of all phi arguments. Then we build interference graph and compute phi congruence classes as decribed in Translating Out of Static Single Assignment Form by Vugranam C. Sreedhar et al. Now we can do graph coloring with one little exception: nodes belonging to one phi congruence class must be of the same color. Before coloring we can eliminate copies that we made at the first step. We can remove a node if there are no adjacent nodes in the same phi congruence class.