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.

Register allocator

Main article: Register allocation

JavaScript doesn't have physical registers as a CPU does. But we perform register allocation to reduce a number of variables, as SSA usually has a lot of them. We actually don't come out of SSA form. Instead we allocate registers in the way that for all of the phi's arguments and the phi result receiver the same registers are allocated. Of course, we sometimes have to introduce copies to make such allocation 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:

The first optimization. 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. For example, if there are no references to label1 in A, B and C, we could rewrite our example the following way:

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

The second optimization. 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.

Consider the following code:

a = foo()
b = bar()
c = a - b

We apply subtraction in left-to-right order. Thus, we should eliminate temporal declaration in backwards order, i.e. from right to left. Let us apply optimization:

a = foo()
c = a - bar();

and after the second application we have the following:

c = foo() - bar();

Notice, that we must always apply this optimization in the backwards computation order, as otherwise we may alter the method call order. And if these methods both have side effects, we loose the original meaning. Moreover, we can change the computation order in general, that leads to altering of liveness information. But as our register allocation and phi elimination relies in the original liveness information, we change our code meaning.

After AST optimizations TeaVM renames all variables to corresponding registers that are computed during the previous phase. If only we renamed variables at the previous phase, we loose information abount the number of usages.