Pipeline

Parser

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.

Dependency checker

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. When we meet an INVOKESTATIC or an INVOKEDYNAMIC, we mark callee as achievable and build its data flow graph the same way. After callee DFG is built, we connect caller and callee graphs the following way: for each parameter of the callee we add an edge, starting at the caller's variable which is passed to the callee's parameter. The edge must point at the callee's parameter itself. If the callee returns value, we also add an edge starting at the callee's return value and pointing to the caller's variable that receives the returning value.

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.

Optimizer

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. For example the following code

$0:
    x = ?
    y = ?
    if X then goto $1 else goto $2
$1:
    goto 3
$2:
    goto 3
$3:
    z = phi(x:$1, y:$2)
    q = x

becomes

$0:
    x = ?
    y = ?
    if X then goto $1 else goto $2
$1:
    x' = x
    goto 3
$2:
    y' = y
    goto 3
$3:
    z = phi(x':$1, y':$2)
    q = x

Then we build interference graph and then compute phi congruence classes as decribed in Translating Out of Static Single Assignment Form by Vugranam C. Sreedhar et al. In the example above we have the following congruence classes: X = {x}, Y = {y}, Z = {z, x', y'}, Q = {q}.

Now we can do greedy 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. Removing a copy we must merge its node with the original node. A resulting node inherits all edges of both merged nodes. Also congruence classes of both nodes must be merged. After such removal and class joining we should not have two adjacent nodes in the same congruence class. So removal is possible if it does not violate this condition.

Let apply reduntant copy elimination to our example above. We have the following graph:

https://dl.dropboxusercontent.com/u/29478938/interference-graph.png

In this graph nodes of the same color belong to the same phi congruence class. If we remove x' variable, we join X (red) and Z (yellow) congruence classes. Nodes x and y are both in this new class and they are adjacent. Therefore, we can't eliminate x' copy.

In contrast, let us remove y' variable. We merge Z (yellow) and Y (blue) congruence classes. y and x nodes become adjacent, but they belong to different classes, so removal is possible.

Decompiler

The idea of decompiler is based on the fact that for each reducible graph we can always build an appropriate source code, as JavaScript has an ability to break any labeled block. Even if there wasn't such ability, we could emulate it with such construction: do { ... } while (false). So we just need to build a proper block hierarchy. Initially each block should start at the jump to label and end at the label itself. But due to some blocks may overlap, we should move the beginning of block to make them nest each other.

Another fact we should notice is that we can't express back jumps this way. Instead we should compute a loop forest of our CFG. But as we also can't jump inside loop, we should reorder CFG that all nodes, belonging to one loop come one after another. We can't let any non-loop nodes be inserted between loop nodes. So we end up with the following algorithm:

1. Build a CFG loop forest.
2. Perform a depth-first search over the CFG. When we are on some node, we should first visit its successors that exit the most outer loop, then we can visit the remaining ones (i.e. successors which stay on the same loop).
3. Add all the loops into the set of blocks.
4. For each jump instruction (i.e. GOTO, IFEQ, IFNE, etc) which does not follow toward a loop back edge add a block beginning at the instruction itself and ending at the jump target label.
5. If two blocks overlap, move the later block's beginning before the beginnig of the earlier block.

Now we are ready to produce the abstract syntax tree. Notice, that we should follow the nesting block hierarchy we just have built. Each jump instruction, unless it is the instruction which follows a back edge, is represented as break label or if (condition) break label;.

After building the AST this way we apply some optimizations over the AST, in order to make the resulting code more natural and neat. The two main optimizations are these:

1. When we have the following labelled block:

   label: {
       A
       if (X) {
           B
           break label;
       }
       C
   }

   we can eliminate the break statement the following way:

   label: {
      A
      if (X) {
          B
      } else {
          C
      }
   }

   of course, if all break statements have been eliminated eliminated, we can eliminate the whole block.

2. For each usage of variable we can replace it by its declaration right-hand side, if this variable is used and declared once and the variable's usage follows immediately after its declaration.

After AST optimizations TeaVM renames all variables to corresponding registers that are computed during the previous phase.