Register allocation

After TeaVM have all of optimizations performed, it should convert program out of SSA form, because it is hard to express phi functions in JavaScript code. We both eliminate phi's and do register allocation in one pass. JavaScript doesn't have real "registers", as a phisycal CPU does. But as in SSA it can be a lot of variables, we should try to reduce the number of the variables. A significant part of register allocation algorithm is used for this purpose. This part includes liveness analysis, interference graph building and graph coloring. We use a slightly modified version of graph coloring with an additional phases of inserting copies, bulding phi congruence classes and eliminating redundant copies.

First, we insert copies of variables before passing them to a phi function. The following code:

$0:
    input x
    input y
    if C then goto $1 else goto $2
$1:
    goto $2
$2:
    z = phi(x:$1, y:$0)
    print z
    q = x + 1
    print q

becomes

$0:
    input x
    input y
    if C then goto $1 else goto $0'
$1:
    x' = x
    goto $2
$0':
    y' = y
    goto $2
$2:
    z = phi(x':$1, y':$0')
    print z
    q = x + 1
    print q

Notice, that sometimes we need to create additional basic blocks. This happens when we deal with conditional jumps, which follow to a phi function. In that case we should copy variables separately along each execution path.

We obtain liveness information. There are many well-known algorithms for performing liveness analysis. According to the liveness information we then build an interference graph. Interference graph is graph where nodes stand for variables and there is an edge between A and B nodes iff A and B live-out at the same instruction. It is pretty easy task: as we have liveness information in all instructions we can just iterate through all instructions and add edge between each pair of variables in live-in set. After all we compute phi congruence classes as decribed in Translating Out of Static Single Assignment Form by Vugranam C. Sreedhar et al. Variables are in the same phi congruence class if they appear in the same phi instruction. In the example above we have the following interference graph, where each color means separate phi congruence class:

Now we can do a 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. When we merge two nodes of interference graph, the following two things happen:

• A new node appears instead of two original ones; it inherits all the edges of original nodes.
• Phi congruence classes of both original variable and its copy are joined.

After such removal and class joining we must not have two adjacent nodes in the same congruence class. So removal is possible if it does not violate this condition.

Let remove redundant copies from our graph. If we remove x' variable, we join red and yellow congruence classes. Nodes x and y' are both in this new "orange" class and they are adjacent. Therefore, we can't eliminate x' copy.

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

Now we apply coloring and get the following graph.

Nodes x', y and z have the same color as they are in the same phi congruence class. Finally, we can rename variables to their colors and just omit all phi functions. We rewrite our example the following way:

$0:
    input red
    input yellow
    if C then goto $1 else goto $0'
$1:
    yellow = red
    goto $2
$0':
    goto $2
$2:
    print yellow
    red = red + 1
    print red

But for now we don't rename variables, as we need our initial SSA information for decompilation phase.